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.ir.IfCmp;
019import org.jikesrvm.compilers.opt.ir.Label;
020import org.jikesrvm.compilers.opt.ir.BasicBlock;
021import org.jikesrvm.compilers.opt.ir.Instruction;
022import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
023
024/**
025 * This class represents a diamond (if-then-else) structure in the
026 * control-flow graph.
027 */
028final class Diamond {
029  /**
030   * The top of the diamond
031   */
032  private final BasicBlock top;
033
034  /**
035   * The bottom of the diamond
036   */
037  private final BasicBlock bottom;
038
039  /**
040   * The "taken" branch of the diamond (might be null)
041   */
042  private final BasicBlock taken;
043
044  /**
045   * The "not-taken" branch of the diamond (might be null)
046   */
047  private final BasicBlock notTaken;
048
049  /**
050   * @return the top of the diamond
051   */
052  BasicBlock getTop() {
053    return top;
054  }
055
056  /**
057   * @return the bottom of the diamond
058   */
059  BasicBlock getBottom() {
060    return bottom;
061  }
062
063  /**
064   * @return the "taken" branch of the diamond (might be {@code null})
065   */
066  BasicBlock getTaken() {
067    return taken;
068  }
069
070  /**
071   * @return the "not-taken" branch of the diamond (might be {@code null})
072   */
073  BasicBlock getNotTaken() {
074    return notTaken;
075  }
076
077  Diamond(BasicBlock top, BasicBlock taken, BasicBlock notTaken, BasicBlock bottom) {
078    this.top = top;
079    this.taken = taken;
080    this.notTaken = notTaken;
081    this.bottom = bottom;
082  }
083
084  /**
085   * See if bb is the root of a diamond.  If so, return an Diamond
086   * representing the structure.
087   *
088   * @param bb possible root of a diamond
089   * @return a structure representing the diamond, {@code null} if not
090   * applicable.
091   */
092  static Diamond buildDiamond(BasicBlock bb) {
093    if (bb.getNumberOfNormalOut() != 2) return null;
094
095    // Identify the two out nodes from bb.
096    Enumeration<BasicBlock> outNodes = bb.getNormalOut();
097    BasicBlock out1 = outNodes.nextElement();
098    BasicBlock out2 = outNodes.nextElement();
099    int out1In = out1.getNumberOfIn();
100    int out2In = out2.getNumberOfIn();
101
102    if (out1In == 1 && out2In == 1) {
103      // look for the case where the diamond has four non-empty blocks.
104      if (out1.getNumberOfNormalOut() == 1 && out2.getNumberOfNormalOut() == 1) {
105        BasicBlock b1 = out1.getNormalOut().nextElement();
106        BasicBlock b2 = out2.getNormalOut().nextElement();
107        if (b1 == b2) {
108          return fourElementDiamond(bb, out1, out2, b1);
109        }
110      }
111    } else if (out1In == 1) {
112      // check for a 3-element diamond
113      if (out1.getNumberOfNormalOut() == 1) {
114        BasicBlock b1 = out1.getNormalOut().nextElement();
115        if (b1 == out2) {
116          return threeElementDiamond(bb, out1, out2);
117        }
118      }
119    } else if (out2In == 1) {
120      // check for a 3-element diamond
121      if (out2.getNumberOfNormalOut() == 1) {
122        BasicBlock b2 = out2.getNormalOut().nextElement();
123        if (b2 == out1) {
124          return threeElementDiamond(bb, out2, out1);
125        }
126      }
127    }
128    // didn't find a diamond
129    return null;
130  }
131
132  private static Diamond fourElementDiamond(BasicBlock top, BasicBlock left, BasicBlock right,
133                                                BasicBlock bottom) {
134
135    Instruction cb = top.firstBranchInstruction();
136    // for now we only support IfCmp diamonds.
137    if (VM.VerifyAssertions) VM._assert(IfCmp.conforms(cb));
138
139    BranchOperand takenTarget = IfCmp.getTarget(cb);
140    if (Label.getBlock(takenTarget.target).block == left) {
141      return new Diamond(top, left, right, bottom);
142    } else {
143      return new Diamond(top, right, left, bottom);
144    }
145  }
146
147  private static Diamond threeElementDiamond(BasicBlock top, BasicBlock side, BasicBlock bottom) {
148
149    Instruction cb = top.firstBranchInstruction();
150    // for now we only support IfCmp diamonds.
151    if (VM.VerifyAssertions) VM._assert(IfCmp.conforms(cb));
152
153    BranchOperand takenTarget = IfCmp.getTarget(cb);
154    if (Label.getBlock(takenTarget.target).block == side) {
155      return new Diamond(top, side, null, bottom);
156    } else {
157      return new Diamond(top, null, side, bottom);
158    }
159  }
160
161  @Override
162  public String toString() {
163    return "[" + top + "," + taken + "," + notTaken + "," + bottom + "]";
164  }
165}