diff options
| -rw-r--r-- | TODO | 45 | ||||
| -rw-r--r-- | docs/passes.txt | 7 | ||||
| -rw-r--r-- | docs/range_analysis.txt | 108 | ||||
| -rw-r--r-- | docs/sccvn.txt | 37 |
4 files changed, 197 insertions, 0 deletions
@@ -0,0 +1,45 @@ +Conversion to SSA form, could maybe be done in two phases: +1. Build up initial tree of block parameters, something like +get_in(block b) { + b->visited = true + bitset gen = 0 + bitset in = 0 + + for i in b->insns { + if i.in1 not in gen { + add i.in1 to in + } + + if i.in2 not in gen { + add i.in2 to in + } + + add i.out to gen + } + + /* recursion, but presumably the user's programs are reasonable + * in size. Otherwise we can probably build up some piecewise + * construct that iterates normally until it converges or something + */ + bitset s1 = get_in(b->s1) + bitset s2 = get_in(b->s2) + + add from s1 not in gen to in + add from s2 not in gen to in +} + +2. Within each block, allocate unique temporary variables. + +This should result in SSA form with block arguments? + +In SSA form, calculate (approximate) value ranges. Assign each location +some value range, [min, max], and propagate functions that calculate the ranges +wherever possible. Where min==max, the location can be replaced by min and the +constants propagated. Generally already checked blocks would not need to be +checked, unless one of the input parameters' range was undefined but became +defined, or was a constant but became a range, or was positive/negative but the +range expanded to be negative/positive as well. + +Do register allocation + +Do instruction generation diff --git a/docs/passes.txt b/docs/passes.txt new file mode 100644 index 0000000..7d527a2 --- /dev/null +++ b/docs/passes.txt @@ -0,0 +1,7 @@ +1. Input -> SSA block parameter form +2. First ABI lowering +3. Boolean expression to branch conditions wherever possible (also sort operands +wherever possible? so instead of 5 + i2 it becomes i2 + 5 or something?) +4. SCCVN (+ weak value range instead of just constant propagation?) +5. Register allocation +6. Instruction selection (pattern matching?) diff --git a/docs/range_analysis.txt b/docs/range_analysis.txt new file mode 100644 index 0000000..752a8ff --- /dev/null +++ b/docs/range_analysis.txt @@ -0,0 +1,108 @@ +Here's an approximate order of steps that I'm thinking about: + +Block0(): + n0 = 4 + goto Block1(n0, 0) + +Block1(n1, i0): + j0 = i0 + n0 + i1 = i0 + 1 + i1 < 5 Block1(n1, i1) else Block2() + +Block2(): + nop + +=> +n0 = U +n1 = U +i0 = U +j0 = U +i1 = U + +=> +n0 = [4, 4] +n1 = U +i0 = U +j0 = U +i1 = U + +=> +n0 = [4, 4] +n1 = [4, 4] +i0 = [0, 0] +j0 = U +i1 = U + +=> +n0 = [4, 4] +n1 = [4, 4] +i0 = [0, 0] +j0 = [4, 4] +i1 = U + +=> +n0 = [4, 4] +n1 = [4, 4] +i0 = [0, 0] +j0 = [4, 4] +i1 = [1, 1] + +/* here's the branch */ +n1 = minmax([4, 4], [4, 4]) = [4, 4] +i0 = minmax(i0, maxmin(i1, [-inf, 4])) = minmax(i0, [1, 4]) = [0, 4] +i0 changed, so recalculate block? +maxmin() here is to signify that the absolute highest value i0 could have +is the branch condition value, with i1 giving the lowest possible value. +Not entirely sure if that's all it takes, but at least this fairly trivial +example seems to work. Should check how comparison results fare, like +"b0 = r1 < 5 + b0 == 1 Block0 ..." + +One (radical) option would be to ban comparisons completely and just force the +compiler to output branches everywhere, at which point it would then probably be +necessary to pattern match the hardware instructions or something to +'reimplement' comparisons. + +=> +n0 = [4, 4] +n1 = [4, 4] +i0 = [0, 4] +j0 = [4, 4] +i1 = [1, 1] + +=> +n0 = [4, 4] +n1 = [4, 4] +i0 = [0, 4] +j0 = [4, 8] +i1 = [1, 5] + +/* here's the branch again */ +n1 = minmax([4, 4], [4, 4]) = [4, 4] // no change +i0 = minmax(i0, maxmin(i1, [-inf, 4])) = minmax(i0, [1, 4]) = [0, 4] +no change so don't recalculate block? + + +=== + +The above works alright, but the compiler is likely easier to implement if the +optimizer accepts stuff like + + b0 = i5 < 5 + bnz b0 Block1(...) else Block2(...) + +bnz/bez are the weakest for of branch and doesn't provide any good info on +limits (full blown SCEV as in GCC would likely be required for that), but we can +add a pass that tries to move 'trivial' branches to + + i5 < 5 Block1(...) else Block2(...) + +as this gives more context to the blocks that follow, even if just a little bit. +Could still be useful for the range analysis. + +In the weak case, bnz/beq, we must perform a weak widening of all parameters in +the blocks, i.e. if the new range max is larger, it must be increased to +infinity, and if the new range min is smaller, it must be decreased to negative +infinity. If any ranges changed, mark the block as not done yet and should be +recomputed. Note that the weak widening applies to the stronger conditonal +branches as well for all parameters except where the condition register is used. diff --git a/docs/sccvn.txt b/docs/sccvn.txt new file mode 100644 index 0000000..aea7d23 --- /dev/null +++ b/docs/sccvn.txt @@ -0,0 +1,37 @@ +Strongly connected components could be a cool pass to implement, it +handles constant folding (seems like most passes have some support for constant +folding?) and certain kinds of common subexpression elimination. + +The paper I'm mainly looking at is https://www.cs.rice.edu/~keith/Publications/SCCVN.pdf + +The algorithm (in short) is + +for all SSA names i + VN [i] <- T +repeat + done <- TRUE + for all blocks b in reverse postorder + for all definitions x in b + temp <- lookup(x:op; VN[x[1]]; VN[x[2]]; x) + if VN[x] != temp + done <- FALSE + VN[x] <- temp + Remove all entries from the hash table +until done + +Where lookup computes a unique hash for x, in C I guess it could just be +op VN1 VN2 +32 64 64 + +The lookup returns the name of the expression if found, otherwise adds the name x to +the map. The paper extends this by adding a map where each SSA name also uses +the constant propagation lattice (TODO: can we use a range lattice? or is that +too much in one pass?) + +To make sure a + b and b + a are the same, I guess each expression node should +sort its inputs. + +SCC is in the name, but I wonder if being strongly connected is necessary for +the algorithm or if it only speeds up the computation as doing it in that order +ensures values are 'final' when the block (or block group) is finished, whereas +otherwise the whole graph seems to be iterated on excessively? |