Bit masks for various optimizations.
Initialize block information.
Do optimizations based on if we know an expression is 0 or !=0, even though we don't know anything else.
Build DAGs (basically find all the common subexpressions). Must be done after all other optimizations, because most of them depend on the trees being trees, not DAGs. The general strategy is: Compute available expressions (AEs) For each block stick together nodes that match, keeping AEs up to date For each block unstick unprofitable common subexpressions (this is generally target-dependent)
Constant propagation. Also detects use of variable before any possible def.
Do copy propagation. Copy propagation elems are of the form OPvar=OPvar, and they are in go.expnod[].
Mark all dead variables. Only worry about register candidates. Compute live ranges for register candidates. Be careful not to compute live ranges for members of structures (CLMOS).
Remove side effect of assignment elem.
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.
Find all the reaching defs of OPvar e.
////////////////////////////
Loop invariant and induction variable elimination. Input: iter which optimization iteration we are on
Update rd vector. Input: n assignment elem or function call elem or OPasm elem rd reaching def vector to update (clear bits for defs we kill, set bit for n (which is the def we are genning)) vecdim go.defnod.length
Definition elem vector, used for reaching definitions.
Copyright (C) 1986-1998 by Symantec Copyright (C) 2000-2023 by The D Language Foundation, All Rights Reserved
Distributed under the Boost Software License, Version 1.0. https://www.boost.org/LICENSE_1_0.txt
Global optimizer declarations
Compiler implementation of the D programming language.