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 static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.CONTROL;
016 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.EXCEPTION_E;
017 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.EXCEPTION_MS;
018 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.EXCEPTION_R;
019 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.GUARD_ANTI;
020 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.GUARD_OUTPUT;
021 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.GUARD_TRUE;
022 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.MEM_ANTI;
023 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.MEM_OUTPUT;
024 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.MEM_READS_KILL;
025 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.MEM_TRUE;
026 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.REG_ANTI;
027 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.REG_MAY_DEF;
028 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.REG_OUTPUT;
029 import static org.jikesrvm.compilers.opt.depgraph.DepGraphConstants.REG_TRUE;
030 import static org.jikesrvm.compilers.opt.ir.Operators.GET_CAUGHT_EXCEPTION;
031 import static org.jikesrvm.compilers.opt.ir.Operators.GET_TIME_BASE;
032 import static org.jikesrvm.compilers.opt.ir.Operators.IR_PROLOGUE;
033 import static org.jikesrvm.compilers.opt.ir.Operators.SET_CAUGHT_EXCEPTION;
034 import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_BEGIN;
035 import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_END;
036
037 import org.jikesrvm.ArchitectureSpecificOpt.PhysicalDefUse;
038 import org.jikesrvm.compilers.opt.ir.BasicBlock;
039 import org.jikesrvm.compilers.opt.ir.BasicBlockEnumeration;
040 import org.jikesrvm.compilers.opt.ir.ExceptionHandlerBasicBlock;
041 import org.jikesrvm.compilers.opt.ir.IR;
042 import org.jikesrvm.compilers.opt.ir.Instruction;
043 import org.jikesrvm.compilers.opt.ir.LocationCarrier;
044 import org.jikesrvm.compilers.opt.ir.OperandEnumeration;
045 import org.jikesrvm.compilers.opt.ir.Operator;
046 import org.jikesrvm.compilers.opt.ir.Register;
047 import org.jikesrvm.compilers.opt.ir.operand.LocationOperand;
048 import org.jikesrvm.compilers.opt.ir.operand.Operand;
049 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
050 import org.jikesrvm.compilers.opt.liveness.LiveSet;
051 import org.jikesrvm.compilers.opt.util.SpaceEffGraph;
052
053 /**
054 * Dependence Graph for a single basic block in the program.
055 *
056 * <p> June 1998 extensions by Vivek Sarkar:
057 * <ul>
058 * <li> 1. Fix direction of register anti dependences
059 * <li> 2. Add conservative memory dependences (suitable for low opt level)
060 * </ul>
061 *
062 * <p>Jul 1998, Harini Srinivasan:
063 * made node list doubly linked list. Changes reflected in
064 * depgraph construction. No calls to getDepGraphNode().
065 *
066 * <p> Dec 1998-March 1999, Mauricio Serrano:
067 * several modifications to the memory efficiency of the graph.
068 * added edges for calls.
069 *
070 * <p> 2000-2001, Dave Grove:
071 * <ul>
072 * <li> add support to handle implicit def/uses of physical registers correctly
073 * <li> large scale refactor and cleanup
074 * <li> more precise treatment of exceptions, control and acquire/release
075 * </ul>
076 */
077 public final class DepGraph extends SpaceEffGraph {
078
079 /**
080 * Set of variables that are live on entry to at least one catch block that
081 * is reachable via a PEI in currentBlock.
082 * This is an approximatation of the more precise set, but can be done in
083 * linear time; doing the most precise thing (computing the set for
084 * every PEI and using each individual set to create the necessary
085 * dependences) is quadratic, and probably doesn't help very much anyways.
086 */
087 private final LiveSet handlerLiveSet;
088
089 /**
090 * The basic block we are processing
091 */
092 private final BasicBlock currentBlock;
093
094 /**
095 * The ir we are processing
096 */
097 private final IR ir;
098
099 /**
100 * Constructor (computes the dependence graph!).
101 *
102 * @param ir the IR to compute the dependence graph for
103 * @param start instruction to start computation from
104 * @param end instruction to end computation at
105 * @param currentBlock the basic block that the instructions are living in
106 */
107 public DepGraph(IR ir, Instruction start, Instruction end, BasicBlock currentBlock) {
108 this.currentBlock = currentBlock;
109 this.ir = ir;
110 handlerLiveSet = new LiveSet();
111 computeHandlerLiveSet();
112 createNodes(start, end);
113 computeForwardDependences(start, end);
114 computeBackwardDependences(start, end);
115 computeControlAndBarrierDependences(start, end);
116 }
117
118 /**
119 * Determine the set of variables live on entry to any handler
120 * block that is reachable from currentBlock
121 */
122 private void computeHandlerLiveSet() {
123 if (ir.getHandlerLivenessComputed() && currentBlock.hasExceptionHandlers()) {
124 BasicBlockEnumeration e = currentBlock.getExceptionalOut();
125 while (e.hasMoreElements()) {
126 ExceptionHandlerBasicBlock handlerBlock = (ExceptionHandlerBasicBlock) e.next();
127 handlerLiveSet.add(handlerBlock.getLiveSet());
128 }
129 }
130 }
131
132 /**
133 * Create the dependency graph nodes for instructions start to end
134 */
135 private void createNodes(Instruction start, Instruction end) {
136 for (Instruction p = start; ; p = p.nextInstructionInCodeOrder()) {
137 DepGraphNode pnode = new DepGraphNode(p);
138 addGraphNode(pnode);
139 if (p == end) {
140 break;
141 }
142 }
143 }
144
145 /**
146 * Compute flow and output dependences by doing a forward
147 * traversal of the instructions from start to end.
148 */
149 private void computeForwardDependences(Instruction start, Instruction end) {
150 boolean readsKill = ir.options.READS_KILL;
151 DepGraphNode lastStoreNode = null;
152 DepGraphNode lastExceptionNode = null;
153 DepGraphNode lastLoadNode = null; // only used if reads kill
154
155 clearRegisters(start, end);
156
157 for (DepGraphNode pnode = (DepGraphNode) firstNode(); pnode != null; pnode =
158 (DepGraphNode) pnode.getNext()) {
159 Instruction p = pnode.instruction();
160
161 // (1) Add edges due to registers
162 int useMask = p.operator().implicitUses;
163 int defMask = p.operator().implicitDefs;
164 if (p.isTSPoint()) {
165 useMask |= PhysicalDefUse.maskTSPUses;
166 defMask |= PhysicalDefUse.maskTSPDefs;
167 }
168 for (OperandEnumeration uses = p.getUses(); uses.hasMoreElements();) {
169 computeForwardDependencesUse(uses.next(), pnode, lastExceptionNode);
170 }
171 for (PhysicalDefUse.PDUEnumeration uses = PhysicalDefUse.enumerate(useMask, ir); uses.hasMoreElements();)
172 {
173 Register r = uses.nextElement();
174 computeImplicitForwardDependencesUse(r, pnode);
175 }
176 for (OperandEnumeration defs = p.getDefs(); defs.hasMoreElements();) {
177 computeForwardDependencesDef(defs.next(), pnode, lastExceptionNode);
178 }
179 for (PhysicalDefUse.PDUEnumeration defs = PhysicalDefUse.enumerate(defMask, ir); defs.hasMoreElements();)
180 {
181 Register r = defs.nextElement();
182 computeImplicitForwardDependencesDef(r, pnode);
183 }
184
185 // (2) Add edges due to memory
186 boolean isStore = p.isImplicitStore();
187 boolean isLoad = p.isImplicitLoad();
188 if (isStore || isLoad) {
189 // If readsKill then add memory model memory dependence from prior load
190 // NOTE: In general alias relationships are not transitive and therefore
191 // we cannot exit this loop early.
192 if (readsKill && isLoad) {
193 for (DepGraphNode lnode = lastLoadNode; lnode != null; lnode = (DepGraphNode) lnode.getPrev()) {
194 if (lnode.instruction().isImplicitLoad() &&
195 LocationOperand.mayBeAliased(getLocation(p), getLocation(lnode.instruction()))) {
196 lnode.insertOutEdge(pnode, MEM_READS_KILL);
197 }
198 }
199 lastLoadNode = pnode;
200 }
201 // Add output/flow memory dependence from prior potentially aliased stores.
202 // NOTE: In general alias relationships are not transitive and therefore
203 // we cannot exit this loop early.
204 for (DepGraphNode snode = lastStoreNode; snode != null; snode = (DepGraphNode) snode.getPrev()) {
205 if (snode.instruction().isImplicitStore() &&
206 LocationOperand.mayBeAliased(getLocation(p), getLocation(snode.instruction()))) {
207 snode.insertOutEdge(pnode, isStore ? MEM_OUTPUT : MEM_TRUE);
208 }
209 }
210 if (isStore) {
211 lastStoreNode = pnode;
212 if (lastExceptionNode != null) {
213 lastExceptionNode.insertOutEdge(pnode, EXCEPTION_MS);
214 }
215 }
216 }
217
218 // (3) Add edges due to exception state/exceptional control flow.
219 if (p.isPEI()) {
220 if (lastExceptionNode != null) {
221 lastExceptionNode.insertOutEdge(pnode, EXCEPTION_E);
222 }
223 lastExceptionNode = pnode;
224 }
225 }
226 }
227
228 /**
229 * Compute anti dependences by doing a backwards
230 * traversal of the instructions from start to end.
231 */
232 private void computeBackwardDependences(Instruction start, Instruction end) {
233 clearRegisters(start, end);
234
235 DepGraphNode lastStoreNode = null;
236 DepGraphNode lastExceptionNode = null;
237 for (DepGraphNode pnode = (DepGraphNode) lastNode(); pnode != null; pnode =
238 (DepGraphNode) pnode.getPrev()) {
239 Instruction p = pnode.instruction();
240
241 // (1) Add edges due to registers
242 int useMask = p.operator().implicitUses;
243 int defMask = p.operator().implicitDefs;
244 if (p.isTSPoint()) {
245 useMask |= PhysicalDefUse.maskTSPUses;
246 defMask |= PhysicalDefUse.maskTSPDefs;
247 }
248 for (OperandEnumeration uses = p.getUses(); uses.hasMoreElements();) {
249 computeBackwardDependencesUse(uses.next(), pnode, lastExceptionNode);
250 }
251 for (PhysicalDefUse.PDUEnumeration uses = PhysicalDefUse.enumerate(useMask, ir); uses.hasMoreElements();)
252 {
253 Register r = uses.nextElement();
254 computeImplicitBackwardDependencesUse(r, pnode);
255 }
256 for (OperandEnumeration defs = p.getDefs(); defs.hasMoreElements();) {
257 computeBackwardDependencesDef(defs.next(), pnode, lastExceptionNode);
258 }
259 for (PhysicalDefUse.PDUEnumeration defs = PhysicalDefUse.enumerate(defMask, ir); defs.hasMoreElements();)
260 {
261 Register r = defs.nextElement();
262 computeImplicitBackwardDependencesDef(r, pnode);
263 }
264
265 // (2) Add edges due to memory
266 boolean isStore = p.isImplicitStore();
267 boolean isLoad = p.isImplicitLoad();
268 if (isStore) {
269 if (lastExceptionNode != null) {
270 pnode.insertOutEdge(lastExceptionNode, EXCEPTION_MS);
271 }
272 lastStoreNode = pnode;
273 } else if (isLoad) {
274 // NOTE: In general alias relationships are not transitive and therefore
275 // we cannot exit this loop early.
276 for (DepGraphNode snode = lastStoreNode; snode != null; snode = (DepGraphNode) snode.getNext()) {
277 if (snode.instruction().isImplicitStore() &&
278 LocationOperand.mayBeAliased(getLocation(p), getLocation(snode.instruction()))) {
279 pnode.insertOutEdge(snode, MEM_ANTI);
280 }
281 }
282 }
283
284 if (p.isPEI()) {
285 lastExceptionNode = pnode;
286 }
287 }
288 }
289
290 /**
291 * Compute control and barrier (acquire/release) dependences
292 * in two passes (one forward, one reverse over the instructions
293 * from start to end.
294 */
295 private void computeControlAndBarrierDependences(Instruction start, Instruction end) {
296 // (1) In a forward pass, we add the following dependences:
297 // a) No load instruction may rise above an acquire
298 // b) No instruction may rise above an UNINT_BEGIN (conservative),
299 // a yieldpoint (we placed the yieldpoints where we wanted them),
300 // a GET_CAUGHT_EXCEPTION, or an IR_PROLOGUE.
301 // c) No GC point may rise above an UNINT_END
302 DepGraphNode lastTotalBarrier = null;
303 DepGraphNode lastGCBarrier = null;
304 DepGraphNode lastAcquire = null;
305 for (DepGraphNode pnode = (DepGraphNode) firstNode(); pnode != null; pnode =
306 (DepGraphNode) pnode.getNext()) {
307 Instruction p = pnode.instruction();
308 if (lastTotalBarrier != null) {
309 lastTotalBarrier.insertOutEdge(pnode, CONTROL);
310 }
311 if (lastGCBarrier != null) {
312 lastGCBarrier.insertOutEdge(pnode, CONTROL);
313 }
314 if (lastAcquire != null && p.isImplicitLoad()) {
315 lastAcquire.insertOutEdge(pnode, CONTROL);
316 }
317 Operator pop = p.operator();
318 if (p.isYieldPoint() || pop == IR_PROLOGUE || pop == UNINT_BEGIN || pop == GET_TIME_BASE || pop == GET_CAUGHT_EXCEPTION) {
319 lastTotalBarrier = pnode;
320 }
321 if (pop == UNINT_END) {
322 lastGCBarrier = pnode;
323 }
324 if (p.isAcquire() || p.isDynamicLinkingPoint()) {
325 lastAcquire = pnode;
326 }
327 }
328
329 // (2) In a backward pass we add the following dependences:
330 // a) No store instruction may sink below a release.
331 // b) No instruction may sink below an UNINT_END (conservative),
332 // a branch/return, a SET_CAUGHT_EXCEPTION, or a yieldpoint
333 // (again want to pin yieldpoints).
334 // c) No GC point may sink below an UNINT_BEGIN
335 lastTotalBarrier = null;
336 lastGCBarrier = null;
337 DepGraphNode lastRelease = null;
338 for (DepGraphNode pnode = (DepGraphNode) lastNode(); pnode != null; pnode =
339 (DepGraphNode) pnode.getPrev()) {
340 Instruction p = pnode.instruction();
341 if (lastTotalBarrier != null) {
342 pnode.insertOutEdge(lastTotalBarrier, CONTROL);
343 }
344 if (lastGCBarrier != null) {
345 pnode.insertOutEdge(lastGCBarrier, CONTROL);
346 }
347 if (lastRelease != null && p.isImplicitStore()) {
348 pnode.insertOutEdge(lastRelease, CONTROL);
349 }
350 Operator pop = p.operator();
351 if (p.isBranch() || p.isReturn() || p.isYieldPoint() || pop == UNINT_END || pop == GET_TIME_BASE || pop == SET_CAUGHT_EXCEPTION) {
352 lastTotalBarrier = pnode;
353 }
354 if (pop == UNINT_BEGIN) {
355 lastGCBarrier = pnode;
356 }
357 if (p.isRelease() || p.isDynamicLinkingPoint()) {
358 lastRelease = pnode;
359 }
360 }
361 }
362
363 /**
364 * Compute forward dependences from a given use to a given node.
365 * @param op source operand
366 * @param destNode destination node
367 * @param lastExceptionNode node representing the last PEI
368 */
369 private void computeForwardDependencesUse(Operand op, DepGraphNode destNode,
370 DepGraphNode lastExceptionNode) {
371 if (!(op instanceof RegisterOperand)) return;
372 RegisterOperand regOp = (RegisterOperand) op;
373 DepGraphNode sourceNode = regOp.getRegister().dNode();
374
375 // if there is an element in the regTableDef[regNum] slot, set
376 // the flow dependence edge.
377 if (sourceNode != null) {
378 if (regOp.getRegister().isValidation()) {
379 sourceNode.insertOutEdge(destNode, GUARD_TRUE);
380 } else {
381 for (PhysicalDefUse.PDUEnumeration e =
382 PhysicalDefUse.enumerate(PhysicalDefUse.maskTSPDefs, ir); e.hasMoreElements();) {
383 Register r = e.nextElement();
384 if (regOp.getRegister() == r) {
385 sourceNode.insertOutEdge(destNode, REG_MAY_DEF);
386 return;
387 }
388 }
389 sourceNode.insertRegTrueOutEdge(destNode, regOp);
390 }
391 }
392 }
393
394 /**
395 * Compute forward dependences from a given def to a given node.
396 * @param op source operand
397 * @param destNode destination node
398 * @param lastExceptionNode node representing the last PEI
399 */
400 private void computeForwardDependencesDef(Operand op, DepGraphNode destNode,
401 DepGraphNode lastExceptionNode) {
402 if (!(op instanceof RegisterOperand)) return;
403 RegisterOperand regOp = (RegisterOperand)op;
404 DepGraphNode sourceNode = regOp.getRegister().dNode();
405
406 if (sourceNode != null) {
407 // create output dependence edge from sourceNode to destNode.
408 int type = regOp.getRegister().isValidation() ? GUARD_OUTPUT : REG_OUTPUT;
409 sourceNode.insertOutEdge(destNode, type);
410 }
411
412 // pin the def below the previous exception node if the register
413 // being defined may be live in some reachable catch block
414 if (lastExceptionNode != null && regOp.getRegister().spansBasicBlock() && currentBlock.hasExceptionHandlers()) {
415 if (!ir.getHandlerLivenessComputed() || handlerLiveSet.contains(regOp.getRegister())) {
416 lastExceptionNode.insertOutEdge(destNode, EXCEPTION_R);
417 }
418 }
419
420 // update depGraphNode information in register.
421 regOp.getRegister().setdNode(destNode);
422 }
423
424 /**
425 * Compute backward dependences from a given use to a given node.
426 * @param op source operand
427 * @param destNode destination node
428 * @param lastExceptionNode node representing the last PEI
429 */
430 private void computeBackwardDependencesUse(Operand op, DepGraphNode destNode,
431 DepGraphNode lastExceptionNode) {
432 if (!(op instanceof RegisterOperand)) return;
433 RegisterOperand regOp = (RegisterOperand) op;
434 DepGraphNode sourceNode = regOp.getRegister().dNode();
435 if (sourceNode != null) {
436 int type = regOp.getRegister().isValidation() ? GUARD_ANTI : REG_ANTI;
437 // create antidependence edge.
438 // NOTE: sourceNode contains the def and destNode contains the use.
439 destNode.insertOutEdge(sourceNode, type);
440 }
441 }
442
443 /**
444 * Compute backward dependences from a given def to a given node.
445 * @param op source operand
446 * @param destNode destination node
447 * @param lastExceptionNode node representing the last PEI
448 */
449 private void computeBackwardDependencesDef(Operand op, DepGraphNode destNode,
450 DepGraphNode lastExceptionNode) {
451 if (!(op instanceof RegisterOperand)) return;
452 RegisterOperand regOp = (RegisterOperand) op;
453
454 // pin the def above the next exception node if the register
455 // being defined may be live in some reachable catch block
456 if (lastExceptionNode != null && regOp.getRegister().spansBasicBlock() && currentBlock.hasExceptionHandlers()) {
457 if (!ir.getHandlerLivenessComputed() || handlerLiveSet.contains(regOp.getRegister())) {
458 destNode.insertOutEdge(lastExceptionNode, EXCEPTION_R);
459 }
460 }
461 regOp.getRegister().setdNode(destNode);
462 }
463
464 /**
465 * Compute implicit forward dependences from a given register use
466 * to a given node.
467 * @param r source register
468 * @param destNode destination node
469 */
470 private void computeImplicitForwardDependencesUse(Register r, DepGraphNode destNode) {
471 DepGraphNode sourceNode = r.dNode();
472 if (sourceNode != null) {
473 for (PhysicalDefUse.PDUEnumeration e =
474 PhysicalDefUse.enumerate(PhysicalDefUse.maskTSPDefs, ir); e.hasMoreElements();) {
475 Register r2 = e.nextElement();
476 if (r == r2) {
477 sourceNode.insertOutEdge(destNode, REG_MAY_DEF);
478 return;
479 }
480 }
481 sourceNode.insertOutEdge(destNode, REG_TRUE);
482 }
483 }
484
485 /**
486 * Compute implicit forward dependences from a given register def
487 * to a given node.
488 * @param r source register
489 * @param destNode destination node
490 */
491 private void computeImplicitForwardDependencesDef(Register r, DepGraphNode destNode) {
492 DepGraphNode sourceNode = r.dNode();
493 if (sourceNode != null) {
494 sourceNode.insertOutEdge(destNode, REG_OUTPUT);
495 }
496 r.setdNode(destNode);
497 }
498
499 /**
500 * Compute implicit backward dependences from a given register use
501 * to a given node.
502 * @param r source register
503 * @param destNode destination node
504 */
505 private void computeImplicitBackwardDependencesUse(Register r, DepGraphNode destNode) {
506 DepGraphNode sourceNode = r.dNode();
507 if (sourceNode != null) {
508 // create antidependence edge.
509 // NOTE: sourceNode contains the def and destNode contains the use.
510 destNode.insertOutEdge(sourceNode, REG_ANTI);
511 }
512 }
513
514 /**
515 * Compute implicit backward dependences from a given register def
516 * to a given node.
517 * @param r source register
518 * @param destNode destination node
519 */
520 private void computeImplicitBackwardDependencesDef(Register r, DepGraphNode destNode) {
521 r.setdNode(destNode);
522 }
523
524 /**
525 * Get the location of a given load or store instruction.
526 * @param s the instruction to get the location from.
527 */
528 private LocationOperand getLocation(Instruction s) {
529 // This extra conforms check wouldn't be necessary if the DepGraph
530 // code was distinguishing between explict load/stores which have
531 // locations and implicit load/stores which don't.
532 return LocationCarrier.conforms(s) ? LocationCarrier.getLocation(s) : null;
533 }
534
535 /**
536 * Initialize (clear) the dNode field in Register for all registers
537 * in this basic block by setting them to null.
538 * Handles both explicit and implict use/defs.
539 * @param start the first opt instruction in the region
540 * @param end the last opt instruction in the region
541 */
542 private void clearRegisters(Instruction start, Instruction end) {
543 for (Instruction p = start; ; p = p.nextInstructionInCodeOrder()) {
544 for (OperandEnumeration ops = p.getOperands(); ops.hasMoreElements();) {
545 Operand op = ops.next();
546 if (op instanceof RegisterOperand) {
547 RegisterOperand rOp = (RegisterOperand) op;
548 rOp.getRegister().setdNode(null);
549 }
550 }
551 if (p == end) break;
552 }
553 for (PhysicalDefUse.PDUEnumeration e = PhysicalDefUse.enumerateAllImplicitDefUses(ir); e.hasMoreElements();)
554 {
555 Register r = e.nextElement();
556 r.setdNode(null);
557 }
558 }
559
560 /**
561 * Print the dependence graph to standard out.
562 */
563 public void printDepGraph() {
564 System.out.println(toString());
565 System.out.println("-----------------------------------");
566 }
567 }