Dataflow: Do Not Confuse These For every dataflow problem, immediately identify: direction: forward or backward meet: union or intersection boundary condition initial value transfer function High-yield table: Reaching Definitions: forward, union, may analysis Available Expressions: forward, intersection, must analysis Liveness: backward, union, may analysis Very Busy Expressions: backward, intersection, must analysis Mental rule: union = may exist on some path intersection = must exist on all paths forward = facts move with execution backward = facts needed by future execution Dataflow equation skeleton: Forward: in[B] = meet out[preds] out[B] = gen[B] ∪ (in[B] - kill[B]) Backward: out[B] = meet in[succs] in[B] = gen/use[B] ∪ (out[B] - kill/def[B]) Convergence reason: finite lattice + monotone transfer functions => fixpoint Dominators / Loops Memorize: a dominates b iff every path from entry to b goes through a. idom(b) = closest strict dominator of b. back edge n -> h iff h dominates…
No comments yet. Log in to reply on the Fediverse. Comments will appear here.