llvm dev - Feb 2015 - [LLVMdev] Reassociate and Canonicalization of Expressions

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.

Ping.

> On Feb 2, 2015, at 11:12 AM, Mehdi Amini <mehdi.amini at apple.com>
wrote:
> 
> 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.
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

>> On Feb 2, 2015, at 11:12 AM, Mehdi Amini <mehdi.amini at
apple.com> wrote:
>>
>> 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.
I don't think deterministic is the right word (as the pass in
deterministic, AFAICT), but I get what you're saying.  You infer we should
always arrive at one final solution once the pass has run.
>>
>> 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.
IMHO, I think these asserts are a good idea and we should work towards
enforcing these assumptions.  One alternative would be to add a slew of
test cases to ensure functionality doesn't regress and relax the asserts,
but I'd still prefer the assertions to be in place.

How you would propose relax the asserts?  Are the asserts hitting code in
the wild or is it just your fuzz tests?

I do appreciate your work on cleaning up the pass and I certainly don't
want to block your efforts, but again I do think these assertions are good
in general.

 Chad
>>
>> 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.
>>
>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>