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.depgraph; 014 015 import org.jikesrvm.compilers.opt.ir.operand.Operand; 016 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand; 017 import org.jikesrvm.compilers.opt.util.SpaceEffGraphEdge; 018 019 /** 020 * Dependence graph edges: connect operands of different instructions 021 * represented by dependence graph nodes. 022 */ 023 public final class DepGraphEdge extends SpaceEffGraphEdge implements DepGraphConstants { 024 /** 025 * Does this edge represent a register true dependence? 026 * @return {@code true} if yes, {@code false} otherwise 027 */ 028 public boolean isRegTrue() { return (scratch & REG_TRUE) != 0; } 029 030 /** 031 * Does this edge represent a register anti-dependence? 032 * @return {@code true} if yes, {@code false} otherwise 033 */ 034 public boolean isRegAnti() { return (scratch & REG_ANTI) != 0; } 035 036 /** 037 * Does this edge represent a register output dependence? 038 * @return {@code true} if yes, {@code false} otherwise 039 */ 040 public boolean isRegOutput() { return (scratch & REG_OUTPUT) != 0; } 041 042 /** 043 * Does this edge represent a register may def? 044 * @return {@code true} if yes, {@code false} otherwise 045 */ 046 public boolean isRegMayDef() { return (scratch & REG_MAY_DEF) != 0; } 047 048 /** 049 * Does this edge represent a memory true dependence? 050 * @return {@code true} if yes, {@code false} otherwise 051 */ 052 public boolean isMemTrue() { return (scratch & MEM_TRUE) != 0; } 053 054 /** 055 * Does this edge represent a memory anti-dependence? 056 * @return {@code true} if yes, {@code false} otherwise 057 */ 058 public boolean isMemAnti() { return (scratch & MEM_ANTI) != 0; } 059 060 /** 061 * Does this edge represent a memory output dependence? 062 * @return {@code true} if yes, {@code false} otherwise 063 */ 064 public boolean isMemOutput() { return (scratch & MEM_OUTPUT) != 0; } 065 066 /** 067 * Does this edge represent a memory reads-kill dependence? 068 * @return {@code true} if yes, {@code false} otherwise 069 */ 070 public boolean isMemReadsKill() { return (scratch & MEM_READS_KILL) != 0; } 071 072 /** 073 * Does this edge represent a control dependence? 074 * @return {@code true} if yes, {@code false} otherwise 075 */ 076 public boolean isControl() { return (scratch & CONTROL) != 0; } 077 078 /** 079 * Does this edge represent an exception-exception dependence? 080 * @return {@code true} if yes, {@code false} otherwise 081 */ 082 public boolean isExceptionE() { return (scratch & EXCEPTION_E) != 0; } 083 084 /** 085 * Does this edge represent an exception-store dependence? 086 * @return {@code true} if yes, {@code false} otherwise 087 */ 088 public boolean isExceptionMS() { return (scratch & EXCEPTION_MS) != 0; } 089 090 /** 091 * Does this edge represent an exception-load dependence? 092 * @return {@code true} if yes, {@code false} otherwise 093 */ 094 public boolean isExceptionML() { return (scratch & EXCEPTION_ML) != 0; } 095 096 /** 097 * Does this edge represent an exception-register live dependence? 098 * @return {@code true} if yes, {@code false} otherwise 099 */ 100 public boolean isExceptionR() { return (scratch & EXCEPTION_R) != 0; } 101 102 /** 103 * Does this edge represent a guard true dependence? 104 * @return {@code true} if yes, {@code false} otherwise 105 */ 106 public boolean isGuardTrue() { return (scratch & GUARD_TRUE) != 0; } 107 108 /** 109 * Does this edge represent a guard anti-dependence? 110 * @return {@code true} if yes, {@code false} otherwise 111 */ 112 public boolean isGuardAnti() { return (scratch & GUARD_ANTI) != 0; } 113 114 /** 115 * Does this edge represent a guard output dependence? 116 * @return {@code true} if yes, {@code false} otherwise 117 */ 118 public boolean isGuardOutput() { return (scratch & GUARD_OUTPUT) != 0; } 119 120 /** 121 * Does a given edge represent a register true dependence? 122 * Use to avoid a cast from SpaceEffGraphEdge to DepGraphEdge. 123 * @param edge the edge to test 124 * @return {@code true} if yes, {@code false} otherwise 125 */ 126 public static boolean isRegTrue(SpaceEffGraphEdge edge) { 127 return (edge.getInfo() & REG_TRUE) != 0; 128 } 129 130 /** 131 * Does a given edge represent a register anti-dependence? 132 * Use to avoid a cast from SpaceEffGraphEdge to DepGraphEdge. 133 * @param edge the edge to test 134 * @return {@code true} if yes, {@code false} otherwise 135 */ 136 public static boolean isRegAnti(SpaceEffGraphEdge edge) { 137 return (edge.getInfo() & REG_ANTI) != 0; 138 } 139 140 /** 141 * Does a given edge represent a register output dependence? 142 * Use to avoid a cast from SpaceEffGraphEdge to DepGraphEdge. 143 * @param edge the edge to test 144 * @return {@code true} if yes, {@code false} otherwise 145 */ 146 public static boolean isRegOutput(SpaceEffGraphEdge edge) { 147 return (edge.getInfo() & REG_OUTPUT) != 0; 148 } 149 150 /** 151 * The destination operand (of a REG_TRUE dependence) 152 */ 153 private RegisterOperand _destOperand; 154 155 /** 156 * Augment the type of the dependence edge. 157 * @param type the additional type for the edge 158 */ 159 void addDepType(int type) { scratch |= type; } 160 161 /** 162 * @param sourceNode source dependence graph node 163 * @param destNode destination dependence graph node 164 * @param depKind the type of the dependence edge 165 */ 166 DepGraphEdge(DepGraphNode sourceNode, DepGraphNode destNode, int depKind) { 167 this(null, sourceNode, destNode, depKind); 168 } 169 170 /** 171 * Constructor for dependence graph edge of a REG_TRUE dependence 172 * from sourceNode to destNode due to destOp 173 * @param destOp destination operand 174 * @param sourceNode source dependence graph node 175 * @param destNode destination dependence graph node 176 * @param depKind the type of the dependence edge 177 */ 178 DepGraphEdge(RegisterOperand destOp, DepGraphNode sourceNode, DepGraphNode destNode, int depKind) { 179 super(sourceNode, destNode); 180 _destOperand = destOp; 181 setInfo(depKind); 182 } 183 184 /** 185 * Get the type of the dependence edge. 186 * @return type of the dependence edge 187 */ 188 int depKind() { 189 return getInfo(); 190 } 191 192 /** 193 * Get the destination operand. 194 * @return destination operand 195 */ 196 RegisterOperand destOperand() { 197 return _destOperand; 198 } 199 200 /** 201 * Get the string representation of edge type (used for printing). 202 * @return string representation of edge type 203 */ 204 @Override 205 public String getTypeString() { 206 String result = ""; 207 if (isRegTrue()) { 208 result += " REG_TRUE "; 209 } 210 if (isRegAnti()) { 211 result += " REG_ANTI "; 212 } 213 if (isRegOutput()) { 214 result += " REG_OUT "; 215 } 216 if (isMemTrue()) { 217 result += " MEM_TRUE "; 218 } 219 if (isMemAnti()) { 220 result += " MEM_ANTI "; 221 } 222 if (isMemOutput()) { 223 result += " MEM_OUT "; 224 } 225 if (isMemReadsKill()) { 226 result += " MEM_READS_KILL "; 227 } 228 if (isControl()) { 229 result += " CONTROL "; 230 } 231 if (isExceptionE()) { 232 result += " EXCEP_E "; 233 } 234 if (isExceptionMS()) { 235 result += " EXCEP_MS "; 236 } 237 if (isExceptionML()) { 238 result += " EXCEP_ML "; 239 } 240 if (isExceptionR()) { 241 result += " EXCEP_R "; 242 } 243 if (isGuardTrue()) { 244 result += " GUARD_TRUE "; 245 } 246 if (isGuardAnti()) { 247 result += " GUARD_ANTI "; 248 } 249 if (isGuardOutput()) { 250 result += " GUARD_OUT "; 251 } 252 if (isRegMayDef()) { 253 result += " REG_MAY_DEF"; 254 } 255 return result; 256 } 257 258 /** 259 * Returns the string representation of the edge. 260 * @return string representation of the edge 261 */ 262 @Override 263 public String toString() { 264 return _fromNode + " ---> " + _toNode + getTypeString(); 265 } 266 267 /** 268 * Returns the string representation of the end node (used for printing). 269 * @return string representation of the end node 270 * @see SpaceEffGraphEdge#toNodeString() 271 */ 272 @Override 273 public String toNodeString() { 274 return getTypeString() + " " + _toNode; 275 } 276 277 /** 278 * Returns the string representation of the start node (used for printing). 279 * @return string representation of the start node 280 * @see SpaceEffGraphEdge#fromNodeString() 281 */ 282 @Override 283 public String fromNodeString() { 284 return getTypeString() + " " + _fromNode; 285 } 286 287 /** 288 * Return the input edge for a given node that corresponds to a given operand. 289 * @param n destination node 290 * @param op destination operand 291 * @return input edge or {@code null} if not found 292 */ 293 public static DepGraphEdge findInputEdge(DepGraphNode n, Operand op) { 294 for (DepGraphEdge inEdge = (DepGraphEdge) n.firstInEdge(); inEdge != null; inEdge = 295 (DepGraphEdge) inEdge.getNextIn()) { 296 if (inEdge.destOperand() == op) { 297 return inEdge; 298 } 299 } 300 return null; // edge not found 301 } 302 } 303 304 305