alg: prune chains with unused intermediate values

[mmcloughlin]

When testing changes to the allocator related to #129 I was running the allocator on chains randomly generated by alg/rand.SolverGenerator. This test triggered an assertion in the allocator:

addchain/acc/pass/alloc.go

Lines 51 to 55 in 2cfd897

	// The output operand variable now becomes available.
	v, ok := allocation[inst.Output.Index]
	if !ok {
	return errutil.AssertionFailure("output operand %d missing allocation", inst.Output.Index)
	}

Allocation is done like liveness analysis: the instructions are processed in reverse and variables are allocated as they are read, freed when they're written to. Therefore this assertion would trigger if the operand is never read after it's written.

It appears this is actually what's happening. See the example:

Example

    exec_test.go:21: pre:
        [1] ← 2 * [0]
        [2] ← 2 * [1]
        [3] ← [0] + [2]
        [4] ← [0] + [3] 		exec_test.go:29: assertion failure: output operand 4 missing allocation
        [5] ← [2] + [3]
        [6] ← [2] + [5]
        [7] ← [1] + [6]
        [8] ← [2] + [7]
        [9] ← [1] + [8]
        [10] ← [1] + [9]
        [11] ← [2] + [10]
        [12] ← [1] + [11]
        [13] ← [1] + [12]
        [14] ← [8] + [12]
        [16] ← [14] ≪ 2
        [17] ← [3] + [16]
        [25] ← [17] ≪ 8
        [26] ← [5] + [25]
        [35] ← [26] ≪ 9
        [36] ← [13] + [35]
        [40] ← [36] ≪ 4
        [41] ← [7] + [40]
        [47] ← [41] ≪ 6
        [48] ← [9] + [47]
        [53] ← [48] ≪ 5
        [54] ← [13] + [53]
        [62] ← [54] ≪ 8
        [63] ← [9] + [62]
        [67] ← [63] ≪ 4
        [68] ← [6] + [67]
        [74] ← [68] ≪ 6
        [75] ← [13] + [74]
        [80] ← [75] ≪ 5
        [81] ← [8] + [80]
        [86] ← [81] ≪ 5
        [87] ← [11] + [86]
        [95] ← [87] ≪ 8
        [96] ← [10] + [95]
        [102] ← [96] ≪ 6
        [103] ← [10] + [102]
        [107] ← [103] ≪ 4
        [108] ← [6] + [107]
        [116] ← [108] ≪ 8
        [117] ← [5] + [116]
        [121] ← [117] ≪ 4
        [122] ← [3] + [121]
        [129] ← [122] ≪ 7
        [130] ← [13] + [129]
        [138] ← [130] ≪ 8
        [139] ← [3] + [138]
        [146] ← [139] ≪ 7
        [147] ← [8] + [146]
        [153] ← [147] ≪ 6
        [154] ← [9] + [153]
        [161] ← [154] ≪ 7
        [162] ← [12] + [161]
        [169] ← [162] ≪ 7
        [170] ← [12] + [169]
        [181] ← [170] ≪ 11
        [182] ← [11] + [181]
        [183] ← 2 * [182]
        [184] ← [0] + [183]
        [191] ← [184] ≪ 7
        [192] ← [0] + [191]

It seems there's either a bug somewhere, perhaps in the conversion from addchain.Program to ir.Program, or this is a trivial optimization pass that could be added to alg/opt.

[mmcloughlin]

No, although I did hit that independently when messing around. Definitely could use a little deadcode pass. I don’t think it shows up much in practice, because the other generators don’t generate dead chain entries.

https://twitter.com/commaok/status/1454905655660187653