[LLVMdev] Reassociate and Canonicalization of Expressions

Mehdi Amini
2015-02-02T19:12:39Z

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.