value_numbering
hash-consed values and the partition lattice for global value numbering.
a Value says how a value is computed: a Leaf is what a location (a variable,
a memory cell, ...) holds, a Constant is a literal and an Apply is a pure
operator applied to values. values are hash-consed, so equal values are the same
object.
a ValueUniverse is the finite set of values a program computes. a state is a
partition of the universe, where values in one class are equal at that program
point. it is a tuple giving each value the index of the first value in its class,
so equal partitions are equal tuples, and the class is the value number.
states are congruences: if the args of two applies are equal, so are the applies.
meet keeps the equalities two states share and assign updates a state for a
write. a write to a leaf changes every value that reads it, and the leaf joins
the class of the written value through a member the write didn't change. there
are finitely many partitions, so a dataflow analysis over them terminates, loops
included, without naming merged values (phis).
Apply
dataclass
¶
Constant
dataclass
¶
Bases: Value
a literal, interned by its exact type and bits, so 0.0 and -0.0 differ
Source code in src/finch/symbolic/value_numbering.py
Leaf
dataclass
¶
Value
¶
ValueUniverse
¶
a finite set of values, closed under taking args. a state is a tuple giving each value the index of the first value in its class.
Source code in src/finch/symbolic/value_numbering.py
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 | |
assign(state, leaf, value=None)
¶
the state after writing value to leaf, or an unknown value if None
Source code in src/finch/symbolic/value_numbering.py
empty()
¶
meet(state_1, state_2)
¶
the equalities both states have
Source code in src/finch/symbolic/value_numbering.py
number(state, value)
¶
the class of value in state, or None if it isn't in the universe