summaryrefslogtreecommitdiff
path: root/chapter11/README.md
diff options
context:
space:
mode:
Diffstat (limited to 'chapter11/README.md')
-rw-r--r--chapter11/README.md19
1 files changed, 16 insertions, 3 deletions
diff --git a/chapter11/README.md b/chapter11/README.md
index a2dc753c..4c5b6412 100644
--- a/chapter11/README.md
+++ b/chapter11/README.md
@@ -123,7 +123,7 @@ We have already alluded to several components of the GCM algorithm in passing ab
infinite loops and create a dummy edge connecting the loop to the Stop node.
* Loops are already identified in the Simple SoN graph, so we do not need a loop discovery step. However, we need to compute the loop depth associated with each CFG node.
* In [Chapter 6](../chapter06/README.md) we explained the concept of Dominators. Dominators are key to the GCM algo, and we extend our incremental dominator discovery algo to
- ensure that it meets the requirements of the algo (TODO did we enhance it in this chapter?).
+ ensure that it meets the requirements of the algo.
* We already mentioned the two phases of the algo - the Early Scheduling and the Late Scheduling.
* In addition, we need to add anti-dependency edges between Loads and Stores in certain scenarios to enforce correct execution order.
* There are a few changes to our Node hierarchy to help us implement the GCM algo more conveniently. These changes do not conceptually alter the Node hierarchy we inherited from the previous chapters.
@@ -482,8 +482,21 @@ The code for computing the late schedule is shown below.
## Inserting Anti Dependencies
-To ensure that Loads and Stores to the same memory location are correctly ordered,
-we insert anti-dependencies when a Load's path up the dominator tree crosses the path of a Store that is the user of the Load's memory input.
+To ensure that Loads and Stores to the same memory location are correctly ordered, we insert an edge from the Load to the Store as described below.
+We call these edges anti-dependencies because they do not represent the Def-Use dependency that we normally capture in SoN, and are purely present as scheduling constraints.
+
+We compute anti-dependencies DURING running schedule late. This is because we rely on the early-schedule, and the late-schedule of the Load's uses (before scheduling the Load).
+
+Looking backwards from the Load we follow the memory edge to the "memory definer" - a start-mem-projection, or a phi-mem, or a store.
+We look forwards from the mem-def to all its mem-def users. There is always at least one; there may be many. These completely (all of it) and exactly (no doubling up) cover the forward memory space, sort of like a network flow problem - but we limit our analysis to same-alias,
+because for example, a start-mem-proj produces all aliases. This gives us a candidate set of mem-defs; some of these need the anti-dependency on the Load, but not all.
+
+Since we're in the middle of "schedule late", we have already computed all the late schedules of a Load's users, and we have the Loads "Least Common Ancestor" of uses, the LCA or late position.
+We inspect the set of mem-defs that might impact the Load, and either add an anti-dependency from Store to Load, or raise the Loads effective LCA.
+For Phi mem-defs, we look at the Phi inputs and place an effective use on that block; this will be used to raise the Load's LCA.
+For stores, we do the same - until/unless we find stores with the SAME block as the Load's LCA. Then we add the anti-dependency edge to force ordering within the same block.
+
+The implementation is shown below.
```java
private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late) {