001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.compilers.opt.controlflow;
014
015import java.util.ArrayList;
016import java.util.Enumeration;
017
018import org.jikesrvm.compilers.opt.ir.BasicBlock;
019import org.jikesrvm.compilers.opt.util.SpaceEffGraphEdge;
020import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
021import org.jikesrvm.util.BitVector;
022
023/**
024 * A node in the LST (Loop Structure Tree)
025 */
026public class LSTNode extends SpaceEffGraphNode {
027
028  /**
029   * Basic block which is the loop head
030   */
031  public final BasicBlock header;
032
033  /**
034   * Basic blocks in the loop
035   */
036  BitVector loop;
037
038  /**
039   * The depth of the loop
040   */
041  int depth;
042
043  /**
044   * If the loop is entered from the loopHeader x times,
045   * then the loopHead is executed loopMultiplier * x times.
046   */
047  float loopMultiplier;
048
049  /**
050   * The CFG Edges that are exits from the loop.
051   */
052  ArrayList<Edge> loopExits;
053
054  LSTNode(BasicBlock bb) {
055    header = bb;
056  }
057
058  /**
059   * Copy constructor
060   *
061   * @param node for copying
062   */
063  protected LSTNode(LSTNode node) {
064    header = node.header;
065    loop = node.loop;
066    depth = node.depth;
067    loopMultiplier = node.loopMultiplier;
068    loopExits = node.loopExits;
069  }
070
071  public BasicBlock getHeader() {
072    return header;
073  }
074
075  public BitVector getLoop() {
076    return loop;
077  }
078
079  @Override
080  public String toString() {
081    StringBuilder node = new StringBuilder();
082    for (int i = 0; i < depth; i++) {
083      node.append('\t');
084    }
085    node.append(header);
086    node.append(' ');
087    node.append(loop);
088    node.append(' ');
089    node.append(loopExits);
090    node.append('\n');
091    return node.toString();
092  }
093
094  public LSTNode getParent() {
095    return (LSTNode) inNodes().nextElement();
096  }
097
098  public Enumeration<LSTNode> getChildren() {
099    return new Enumeration<LSTNode>() {
100      private SpaceEffGraphEdge _edge = _outEdgeStart;
101
102      @Override
103      public boolean hasMoreElements() {
104        return _edge != null;
105      }
106
107      @Override
108      public LSTNode nextElement() {
109        SpaceEffGraphEdge e = _edge;
110        _edge = e.getNextOut();
111        return (LSTNode) e.toNode();
112      }
113    };
114  }
115
116  public void initializeLoopExits() {
117    loopExits = new ArrayList<Edge>();
118  }
119
120  public void addLoopExit(BasicBlock source, BasicBlock target, float prob) {
121    loopExits.add(new Edge(source, target, prob));
122  }
123
124  static final class Edge {
125    final BasicBlock source;
126    final BasicBlock target;
127    final float probability;
128
129    Edge(BasicBlock s, BasicBlock t, float p) {
130      source = s;
131      target = t;
132      probability = p;
133    }
134
135    @Override
136    public String toString() {
137      return source + "->" + target + " prob = " + probability;
138    }
139  }
140
141}