Iterative Backward Reachability

2022-04-iterative-reachability.md

Iterative Backward Reachability

This should replace the current non-iterative Reachability. The current non-iterative algorithm would only make sense when uses are post-dominating and we change it to propagate in DFS RPO order. But this algorithm should very seldom need to iterate anyway. So we should probably use it instead.

Input:

• dominating def

• uses (gens) - during initialization only

• barriers (kills) - as a callback only

State:

• discoveredBlockList (BasicBlockSetVector)

• notReachableAtEntryBlockWorklist (BasicBlockWorklist)

• genBlocks (BasicBlockSet)

• killBlocks (BasicBlockSet)

• notReachableAtExitBlocks (BasicBlockSet) (not to be confused with unreachable exit blocks)

• barrierInstructions

• barrierBlocks

Data flow state:

isReachableAtExit(block):
-> discoveredBlockList.contains(block) && !notReachableBlockExits(block)

isReachableAtEntry(block):
-> (isReachableAtExit(block) && !killBlocks(block))
   || genBlocks(block)
   
meetOverSuccessors(block):
  for succ in block.successors:
      if !isReachableAtEntry(succ) { return NotReachable }

Data flow transfer:

propagateIntoPredecessor(block):
  if isReachableAtExit(block) {
    notReachableAtExitBlocks.insert(block)
    if !genBlocks(block) {
       notReachableAtEntryBlockWorklist.push(block)
    }
  }

Step 1a: initialize data flow

Finds all the local barriers within blocks.

Seeds the discovered block list.

for each use:

push this block on the discovered block list

walk backward in the block from the use:

if isKill(inst) {
  killBlocks.insert(block)
  return; // stop walking
}

Step 1b: perform local data flow

Initializes the gen/kill sets and computes the optimisically reachable region.

Iterate over the discovered block list, indexing into the list as it grows:

1a. add current block to the gen or kill set. remember to check phis. It may already be a kill block from step 0. Add kill blocks to notReachableAtEntryBlockWorklist.

1b. if this is not the def block, push all predecessors onto the discovered block list

All reachable blocks are now discovered optimistically.

Step 1c. DFS-based pessimistic data flow

Here, the client can choose to do pessimistic data flow in addition to or instead of iterative data flow. The client can layer as many pessimistic data flows as it wants in a single traversal of the region by providing a visitInstruction callback.

Perform forward DFS from the def blocks

When DFS finishes a block, meet over successors, then process it backward

The client can even update gen/kill sets at this time. There is no need to repeat local data flow as long as any changes correctly summarize the entire block.

For example: the client can keep track of live access scopes at every point. At a kill, check all live scopes. Add a new kill for any end_access instructions. If the end_access block is in the "gen" set, iterate to find the new gen/kill status. Otherwise, just mark it a kill block.

Step 2: propagate global data flow

Propagates not-reachable information from barriers within the optimisically reachable region.

2a. Handle region exits and seed the global data flow worklist

Iterate over all discovered blocks in backward order (or RPO if we have it):

if meetOverSuccessors(block) == NotReachable) {
   notReachableAtExitBlocks.insert(block)
   if !genBlocks(block) {
     notReachableAtEntryBlockWorklist.push(block)
   }
}

2b. Propagate along predecessors

while block = notReachableAtEntryBlockWorklist.pop():
  for preds in block.predecessors:
    propagateIntoPredecessor(pred)

Step 3: Find barriers

Find local instruction barriers in use blocks. Iterate backward over use blocks starting at the use:

if isKill(inst):
    barrierInstructions.insert(inst);

Iterate over the discovered blocks:

if isReachableAtExit(block) && killBlocks.contains(block) {
  for inst in block.reverse {
    if isKill(inst) {
      barrierInstructions.insert(inst);
      return;
    }
}
if !isReachableAtExit(block) {
  for succ in block.successors {
    if isReachableAtEntry(succ) {
      barrierBlocks.insert(block)
    }
  }
}