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      @Override
080      public String toString() {
081        String tab = "";
082        for (int i = 0; i < depth; i++) {
083          tab += "\t";
084        }
085        return tab + header + " " + loop + " " + loopExits + "\n";
086      }
087    
088      public LSTNode getParent() {
089        return (LSTNode) inNodes().nextElement();
090      }
091    
092      public Enumeration<LSTNode> getChildren() {
093        return new Enumeration<LSTNode>() {
094          private SpaceEffGraphEdge _edge = _outEdgeStart;
095    
096          @Override
097          public boolean hasMoreElements() { return _edge != null; }
098    
099          @Override
100          public LSTNode nextElement() {
101            SpaceEffGraphEdge e = _edge;
102            _edge = e.getNextOut();
103            return (LSTNode) e.toNode();
104          }
105        };
106      }
107    
108      public void initializeLoopExits() {
109        loopExits = new ArrayList<Edge>();
110      }
111    
112      public void addLoopExit(BasicBlock source, BasicBlock target, float prob) {
113        loopExits.add(new Edge(source, target, prob));
114      }
115    
116      static final class Edge {
117        final BasicBlock source;
118        final BasicBlock target;
119        final float probability;
120    
121        Edge(BasicBlock s, BasicBlock t, float p) {
122          source = s;
123          target = t;
124          probability = p;
125        }
126    
127        @Override
128        public String toString() {
129          return source + "->" + target + " prob = " + probability;
130        }
131      }
132    
133    }