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