Flattening without losing sharing

A compiler can reorganize an expression without changing its answers. Two useful ideas are sharing a repeated calculation and flattening a chain of the same operation. They solve different problems, and a careless flattening step can undo useful sharing. We will build one access rule, transform its graph, and follow the values through each version. We will also count instructions and elementary combinations separately. That distinction explains why a shorter instruction list is not automatically less work or a faster program. Our fictional rule has five inputs. The letter A means approved staff, and B means identity verified. Both are required for every permitted request. C means within access hours, and D means at the office. These two conditions define the ordinary access route. E means special approval, which provides an alternative route. Each input is a yes-or-no condition, encoded as one or zero. We will keep these meanings visible while the letters become part of the graph. First compute S: approved staff and verified identity. Next compute P: within access hours and at the office. The ordinary route, L, requires both S and P. The special route, R, requires S and special approval E. Both routes depend on the same eligibility condition S. The final result F is L or R. This is inclusive or: either route can allow access, and having both routes true also allows access. Use inputs one, one, zero, one, one in A through E order. S is one and one, giving one. P is zero and one, giving zero. The ordinary route combines S one with P zero, giving zero. The special route combines S one with E one, giving one. Finally, zero or one gives one. Access is allowed through the special route. Keep these intermediate values; they will let us check every transformation against the same request. Written out separately, the two routes both contain A and B. A direct evaluation of each written copy can repeat that calculation. Common subexpression elimination, or C S E, recognizes matching expression structure and gives the common calculation one result slot. Both routes can read S from that slot. The current baseline uses structural matching. It does not need the two written occurrences to be the same object in memory. This is distinct from proving arbitrary differently written formulas equivalent. Now consider an and chain on its own. Both groupings require A, B, and C all to be one. That is why changing the parentheses preserves the answer for every input, not just for a few examples. For inputs one, one, zero, the left grouping first computes one and one, giving one. The right grouping first computes one and zero, giving zero. Both complete calculations finish at zero. For three ones, both finish at one. We can represent the chain as one instruction with three operands. Under the simple binary evaluation we are counting, it still takes two combinations. One instruction does not mean one binary operation. Return to our access graph. A consumer is an operation that uses a computed value. L uses S, and R also uses S. S therefore has two consumer edges. P is used only by L. P has one consumer, and both P and L perform and. P is the private same-operation child we can absorb into its parent. These two observations must be made together: the operation matches, and the child has only one consumer. The current sharing-aware baseline uses that distinction when it flattens associative chains. Replace the reference to private P inside L with P's operands, C and D. L becomes a three-input and of S, C, and D. P no longer needs its own instruction in this plan. Its work has been incorporated into L. The inputs C and D have not vanished. Leave S as a separate shared value. Both routes still read it. We have flattened the private chain while preserving the calculation that serves two consumers. Run the same request again. S remains one. For the flattened left instruction, combine S one with C zero to get zero, then combine that zero with D one. L remains zero. R still combines the shared S one with E one, giving one. F combines zero or one, so the final answer remains allow. This trace explains the example. Separately, we checked all thirty-two assignments of the five independent inputs. The original and flattened plans agree on every one. Suppose we also splice S into both consumers. L becomes an and of A, B, C, and D. R becomes an and of A, B, and E. These expressions still describe the same Boolean function. But in the simple instruction execution shown here, the left instruction combines A and B, and the right instruction combines A and B again. The shared calculation has been duplicated. We are not adding another optimization pass that rediscovers the common calculation. Under this stated plan, splicing the shared child preserves correctness while losing useful reuse. The original shared plan has five operator instructions, each combining two values. That gives five binary combinations. We are counting operator instructions, not input loads. After flattening only P, there are four operator instructions. S takes one combination, L takes two, R takes one, and F takes one. The total is still five. After also splicing S, there are three operator instructions. L now takes three combinations, R takes two, and F takes one. The total has risen to six. The shortest instruction list does more binary combining in this example. Now remove special approval by changing only E from one to zero. S is still one, and the ordinary route is still zero because C is zero. The right route now computes one and zero, giving zero. The final result is zero or zero, which is zero. All three plans deny this request. Their outputs change together because they implement the same function. Their instruction structure and repeated work differ. Those are the properties the transformation is changing. The same-operation condition matters. Consider A and the grouped expression B or C. The child is or, while the parent is and. Set A to zero and both B and C to one. Inside the original grouping, B or C gives one, and A and one gives zero. Changing the expression to A and B, then or C, gives zero or one, which is one. The answer changed. That is not the valid associative flattening we have been using. The current structural C S E baseline follows this sharing-aware rule. In this teaching expression, its actual emitted operator counts match the original and private-only plans we have shown. The always-splice plan is our explicit contrast. Its extra binary combination explains a possible source of wasted work; it is not the production baseline being relabeled. None of these counts is an elapsed-time measurement. To claim a speed difference, compare the actual implementations with the same inputs, outputs, lifecycle, and timed boundary. Sharing gives a common calculation one reusable value. Flattening merges a private chain of the same associative operation into its parent. Use both ideas together: absorb private chains while protecting children whose values serve more than one consumer. Then check the answers, read instruction and operation counts separately, and measure before claiming speed. That is how flattening can simplify a program's organization without silently giving away its sharing.