#80 #85 apply bug fixes from chapter10 (#89)

* #80 #85 apply bug fixes from chapter10

* #85 #80 more detail regarding anti-dependency

* Remove Util.eq

Was enforced interning of strings, not needed here.

---------

Co-authored-by: Cliff Click <cliffc@acm.org>

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) {