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     */
013    package org.jikesrvm.compilers.opt.controlflow;
014    
015    import java.util.ArrayList;
016    import java.util.Enumeration;
017    
018    import org.jikesrvm.compilers.opt.ir.BasicBlock;
019    import org.jikesrvm.compilers.opt.util.SpaceEffGraphEdge;
020    import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
021    import org.jikesrvm.util.BitVector;
022    
023    /**
024     * A node in the LST (Loop Structure Tree)
025     */
026    public 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      public String toString() {
080        String tab = "";
081        for (int i = 0; i < depth; i++) {
082          tab += "\t";
083        }
084        return tab + header + " " + loop + " " + loopExits + "\n";
085      }
086    
087      public LSTNode getParent() { return (LSTNode) inNodes().next(); }
088    
089      public Enumeration<LSTNode> getChildren() {
090        return new Enumeration<LSTNode>() {
091          private SpaceEffGraphEdge _edge = _outEdgeStart;
092    
093          public boolean hasMoreElements() { return _edge != null; }
094    
095          public LSTNode nextElement() {
096            SpaceEffGraphEdge e = _edge;
097            _edge = e.getNextOut();
098            return (LSTNode) e.toNode();
099          }
100        };
101      }
102    
103      public void initializeLoopExits() {
104        loopExits = new ArrayList<Edge>();
105      }
106    
107      public void addLoopExit(BasicBlock source, BasicBlock target, float prob) {
108        loopExits.add(new Edge(source, target, prob));
109      }
110    
111      static final class Edge {
112        final BasicBlock source;
113        final BasicBlock target;
114        final float probability;
115    
116        Edge(BasicBlock s, BasicBlock t, float p) {
117          source = s;
118          target = t;
119          probability = p;
120        }
121    
122        public String toString() {
123          return source + "->" + target + " prob = " + probability;
124        }
125      }
126    
127    }