Introduction #

Recently, I implemented Sparse Conditional Constant Propagation(SCCP) in Golang.

SCCP is an old but useful optimization, the detailed algorithm was described in Mark N. Wegman, F. Kenneth Zadeck: Constant Propagation with Conditional Branches TOPLAS 1991.

This algorithm uses three level lattice for SSA value

      Top        undefined
     / | \
 .. 1  2  3 ..   constant
     \ | /
     Bottom      not constant

It starts with optimistically assuming that all SSA values are initially Top and then propagates constant facts only along reachable control flow paths Since some basic blocks are not visited yet, corresponding inputs of phi become Top, we use the meet(phi) to compute its lattice.

    Top ∩ any = any
    Bottom ∩ any = Bottom
    ConstantA ∩ ConstantA = ConstantA
    ConstantA ∩ ConstantB = Bottom

Each lattice value is lowered most twice(Top to Constant, Constant to Bottom) due to lattice depth, resulting in a fast convergence speed of the algorithm.

SCCP Example #

The following is a typical example that demonstrates the benefits of SCCP compared to various optimization combinations:

//go:noinline
func dummy() {}

//go:noinline
func tt() {
	for i := int64(0); i >= 128; i++ {
		dummy()
	}
}

The corresponding SSA is as follows:

b1:
v1 (?) = InitMem <mem>
v4 (?) = Const64 <int64> [0] (i[int64])
v6 (?) = Const64 <int64> [128]
v12 (?) = Const64 <int64> [1]
Plain → b2 (+91)

b2: ← b1 b4
v5 (91) = Phi <int64> v4 v13 (i[int64])
v16 (94) = Phi <mem> v1 v10
v7 (+91) = Leq64 <bool> v6 v5
If v7 → b4 b5 (likely) (91)

b4: ← b2
v9 (+92) = StaticCall <mem> {AuxCall{main.dummy}} v16
v10 (92) = SelectN <mem> [0] v9
v13 (+91) = Add64 <int64> v5 v12 (i[int64])
Plain → b2 (91)

b5: ← b2
v14 (+94) = MakeResult <mem> v16
Ret v14 (94)

Initially, SCCP propagates constants along b1->b2. When it encounters v5#Phi, it optimistically assumes that the lattice of v13, which is the second parameter of the Phi and has not been visited in basic block b4, is Top. It calculates a constant lattice of value 0 for v5 = Phi(Const,Top). Then, v7 (+91) = Leq64 <bool> v6 v5(128 <= 0) evaluates to false and is used as the control value to determine subsequent control flow, so only b2->b5 is propagated. Finally, the control flow ends. The transformed SSA is as follows:

b5:
v1 (?) = InitMem <mem>
v14 (+94) = MakeResult <mem> v1
Ret v14 (94)

The entire loop is removed. In this way, SCCP can discover optimization opportunities that cannot be found by just combining constant folding and constant propagation and dead code elimination separately.

This advantage is usually manifested when code involves loops. Because loops have back edges, which often produce uncertain Phi values that are difficult to prove as constants in other optimizations, SCCP can take advantage of this. According to the aforementioned rules, SCCP simulates execution along the control flow and when it encounters a Phi, it can optimistically assume that the Phi is a constant and continue propagating constant facts along the control flow based on this assumption.

Performance evaluation #

In practice, when to run SCCP is also something worth considering. Running SCCP optimization in the early stages of compilation can identify more constants, eliminate more dead code, and fold more constant calculations. Running SCCP in the later stages of compilation can discover optimization opportunities that were not found by earlier optimizations. We compared the performance of running SCCP at different critical stages:

Placement	Constant	Deadcode
before early deadcode	451088	96553
before pre-opt deadcode	329419	116650
before opt deadcode	6078	765
before gcse deadcode	3539	763
before generic deadcode	2735	545
before lower	2444	535

I conservatively propose to only place SCCP before generic deadcode. Ideally I think it should be performed both before generic deadcode and before early deadcode

Future work #

There is still a lot of work to be done in the future, and here are some that come to my mind at the moment (in order of difficulty):

• Support more basic constant types, such as OpConstNil, OpConstString
• Support constant folding for more operations
• Extend the constant lattice, implement value range propagation, at least achieving what prove pass can currently do, and eventually removing prove pass.
• Support interprocedural SCCP that awares of function invocations.