[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.. :)

In other words, I don't think we have to implement the pass is such as way
as to guarantee idempotence; we have bigger fish to fry.

>
>>>
>>> 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
>>>>
>>>>
>>>
>>>
>>
>>
>
>
>