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