[LLVMdev] Reassociate and Canonicalization of Expressions

[Mehdi Amini]

Hi,

I encountered some bugs in Reassociate [1] where we are hitting some assertions:

    assert(!Duplicates.count(Factor) &&
               "Shouldn't have two constant factors, missed a canonicalize");
    assert(NumAddedValues > 1 && "Each occurrence should contribute a value”);

My understanding is that these assertions enforce that when processing an expression tree, we expect that the nodes have already been canonicalized by Reassociate.

I infer that there should be *one* canonicalization for a function and it should be deterministic, i.e. if I run Reassociate two times I expect that the second one does not make any change.

However right now we are far from that. I have multiple patches in flight to improve the situation, but the situation is still not perfect. Before going further I’d like some clarification on the expectation of Reassociate:

- Is there one expected canonicalization in all cases?
- Do we expect that running multiple times Reassociate in a row does not change the result after the first run?

If the answer is no, then I think the two assertions should be relaxed.

Bonus question: how does InstCombine behave wrt to the two questions above?

Thanks,

— 
Mehdi

[1] : I am stressing it with a fuzzer for a specific language based on LLVM and Reassociate is used later in the pipeline.