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