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.Enumeration;
016
017import org.jikesrvm.VM;
018import org.jikesrvm.compilers.opt.dfsolver.DF_LatticeCell;
019import org.jikesrvm.compilers.opt.dfsolver.DF_System;
020import org.jikesrvm.compilers.opt.ir.BasicBlock;
021import org.jikesrvm.compilers.opt.ir.IR;
022
023/**
024 * Implementation of the dataflow equation system to calculate dominators.
025 */
026class DominatorSystem extends DF_System {
027
028  /**
029   * The governing IR.
030   */
031  private final IR ir;
032
033  /**
034   * Default constructor.
035   * @param ir the governing IR
036   */
037  DominatorSystem(IR ir) {
038    this.ir = ir;
039    setupEquations();
040  }
041
042  /**
043   * Go through each basic block in the IR, and add equations
044   * to the system as required.
045   * <p> Uses the algorithm contained in Dragon book, pg. 670-1.
046   * <pre>
047   *     D(n0) := { n0 }
048   *     for n in N - { n0 } do D(n) := N;
049   *     while changes to any D(n) occur do
050   *       for n in N - {n0} do
051   *           D(n) := {n} U (intersect of D(p) over all predecessors p of n)
052   * </pre>
053   */
054  void setupEquations() {
055    // loop through each basic block in the IR
056    for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
057      BasicBlock bb = e.nextElement();
058      // add a data-flow equation for this basic block
059      // DOM(n) = {n} MEET {pred(n)}
060      DF_LatticeCell dom = findOrCreateCell(bb);
061      DF_LatticeCell[] pred = getCellsForPredecessors(bb);
062      newEquation(dom, DominatorOperator.MEET, pred);
063    }
064  }
065
066  /**
067   * Initialize the lattice variables (Dominator sets) for
068   * each basic block.
069   */
070  @Override
071  protected void initializeLatticeCells() {
072    if (Dominators.COMPUTE_POST_DOMINATORS) {
073      BasicBlock exit = ir.cfg.exit();
074      DominatorCell last = (DominatorCell) getCell(exit);
075      for (final DF_LatticeCell latticeCell : cells.values()) {
076        DominatorCell cell = (DominatorCell) latticeCell;
077        if (cell == last) {
078          cell.addSingleBlock(cell.block);
079        } else {
080          cell.setTOP(ir);
081        }
082      }
083    } else {
084      BasicBlock start = ir.cfg.entry();
085      DominatorCell first = (DominatorCell) getCell(start);
086      for (final DF_LatticeCell latticeCell : cells.values()) {
087        DominatorCell cell = (DominatorCell) latticeCell;
088        if (cell == first) {
089          cell.addSingleBlock(cell.block);
090        } else {
091          cell.setTOP(ir);
092        }
093      }
094    }
095  }
096
097  /**
098   * Initialize the work list for the dataflow equation system.
099   * <p> The initial work list is every equation containing the start
100   * node.
101   */
102  @Override
103  protected void initializeWorkList() {
104    if (Dominators.COMPUTE_POST_DOMINATORS) {
105      // Add every equation to work list (to be safe)
106      // WARNING: an "end node" may be part of a cycle
107      for (Enumeration<BasicBlock> e = ir.getBasicBlocks(); e.hasMoreElements();) {
108        BasicBlock bb = e.nextElement();
109        addCellAppearancesToWorkList(getCell(bb));
110      }
111    } else {
112      DominatorCell first = (DominatorCell) getCell(ir.cfg.entry());
113      addCellAppearancesToWorkList(first);
114    }
115  }
116
117  /**
118   * Get the DF_LatticeCell key corresponding to a basic block
119   * @param bb the basic block
120   * @return the key (just the block itself)
121   */
122  Object getKey(BasicBlock bb) {
123    return bb;
124  }
125
126  /**
127   * Make a new DF_LatticeCell key corresponding to a basic block
128   * @param key the basic block
129   * @return the new cell
130   */
131  @Override
132  protected DF_LatticeCell makeCell(Object key) {
133    return new DominatorCell((BasicBlock) key, ir);
134  }
135
136  /**
137   * @param bb the basic block
138   * @return a list of lattice cells corresponding to the
139   *  predecessors of a basic block
140   */
141  DF_LatticeCell[] getCellsForPredecessors(BasicBlock bb) {
142    if (Dominators.COMPUTE_POST_DOMINATORS) {
143      /****
144       if ( bb.mayThrowUncaughtException() ) {
145       if (Dominators.DEBUG) VM.sysWrite("LOCATION #1 ...\n");
146       // Include exit node as an output node
147       DF_LatticeCell s[] = new DF_LatticeCell[bb.getNumberOfOut()+1];
148       Enumeration<BasicBlock> e = bb.getOut();
149       for (int i=0; i<s.length-1; i++ ) {
150       BasicBlock p = e.next();
151       s[i] = findOrCreateCell(getKey(p));
152       }
153       s[s.length-1] = findOrCreateCell(getKey(ir.cfg.exit()));
154       return s;
155       }
156       else
157       ****/
158      {
159        if (Dominators.DEBUG) {
160          VM.sysWrite("LOCATION #2 ...\n");
161        }
162        DF_LatticeCell[] s = new DF_LatticeCell[bb.getNumberOfOut()];
163        Enumeration<BasicBlock> e = bb.getOut();
164        for (int i = 0; i < s.length; i++) {
165          BasicBlock p = e.nextElement();
166          s[i] = findOrCreateCell(getKey(p));
167        }
168        return s;
169      }
170    } else {
171      if (Dominators.DEBUG) {
172        System.out.println("LOCATION #3 ...");
173      }
174      DF_LatticeCell[] s = new DF_LatticeCell[bb.getNumberOfIn()];
175      Enumeration<BasicBlock> e = bb.getIn();
176      for (int i = 0; i < s.length; i++) {
177        BasicBlock p = e.nextElement();
178        s[i] = findOrCreateCell(getKey(p));
179      }
180      return s;
181    }
182  }
183}