From 95cc1acbe32a0fe759d9063e6fa7978b68517ad1 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sun, 30 Jun 2024 16:58:08 +0100 Subject: #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 --- chapter11/README.md | 19 ++++++++++++++++--- 1 file changed, 16 insertions(+), 3 deletions(-) (limited to 'chapter11/README.md') 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) { -- cgit v1.2.3