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