[LLVMdev] Reassociate and Canonicalization of Expressions

[Chad Rosier]

> Hi Chad,
>
> Thanks for you answer.
>
>> On Feb 4, 2015, at 11:22 AM, Chad Rosier <mcrosier at codeaurora.org>
>> wrote:
>>
>>>> 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.
>
> Yes.
>
>>
>>>>
>>>> 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.
>
> I’m all for keeping the assertion, but do we agree that the answer is
> “yes” to my two questions above?
> Enforcing a “final” result after one run can be quite involved, and
> I’m asking for clarification on the expectation here before spending too
> much time on that.

IMO, I think these are reasonable expectations and if you can enforce
these expectations for the common cases, great.  However, if it doubles
your effort to get the remaining 1% exposed by fuzzing, then I don't think
it would be worth your time.

Personally, I would like to invest more time in adding support for vector
operations (I had a patch up on Phabricator at one point).  I'm sure there
are also lots of other types of simplifications that could be added to
this pass.

Just my opinion though.. :)

>>
>> How you would propose relax the asserts?  Are the asserts hitting code
>> in
>> the wild or is it just your fuzz tests?
>
> Only the fuzzer, so I don’t have a high priority on fixing this. But
> since I started, I rather finish the job.
>
> By relaxing the assertions, I meant being tolerant to expression for which
> nodes have not been fully canonicalized.
> Again, I’m not suggesting we actually relax these assertions. Just that
> we clarify the expectation either way.
>
> Thanks,
>
> Mehdi
>
>>
>> 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
>>>
>>>
>>
>>
>
>