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