Compute available expressions (AEs). That is, expressions whose result is still current. Bin = the set of AEs reaching the beginning of B. Bout = the set of AEs reaching the end of B.
Compute copy propagation info (CPs). Very similar to AEs (the same code is used). Using RDs for copy propagation is WRONG! That is, set of copy statements still valid. Bin = the set of CPs reaching the beginning of B. Bout = the set of CPs reaching the end of B.
Do live variable analysis (LVs). A variable is 'live' at some point if there is a subsequent use of it before a redefinition. Binlv = the set of variables live at the beginning of B. Boutlv = the set of variables live at the end of B. Bgen = set of variables used before any definition in B. Bkill = set of variables unambiguously defined before any use in B. Note that Bgen & Bkill = 0.
Compute reaching definitions (RDs). That is, for each block B and each program variable X find all elems that could be the last elem that defines X along some path to B. Binrd = the set of defs reaching the beginning of B. Boutrd = the set of defs reaching the end of B. Bkillrd = set of defs that are killed by some def in B. Bgenrd = set of defs in B that reach the end of B.
Compute very busy expressions(VBEs). That is,expressions that are evaluated along separate paths. Bin = the set of VBEs at the beginning of B. Bout = the set of VBEs at the end of B. Bgen = set of expressions X+Y such that X+Y is evaluated before any def of X or Y. Bkill = set of expressions X+Y such that X or Y could be defined before X+Y is computed. Note that gen and kill are mutually exclusive.
Compute GEN and KILL vectors only for AEs. defkill and starkill are assumed to be already set up correctly. go.expnod[] is assumed to be set up correctly.
Code to do the Data Flow Analysis (doesn't act on the data).