Chad Rosier
2015-Feb-04 20:06 UTC
[LLVMdev] Reassociate and Canonicalization of Expressions
> 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 >>> >>> >> >> > >
Chad Rosier
2015-Feb-04 20:16 UTC
[LLVMdev] Reassociate and Canonicalization of Expressions
>> 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 >>>> >>>> >>> >>> >> >> > > >
Mehdi Amini
2015-Feb-05 00:51 UTC
[LLVMdev] Reassociate and Canonicalization of Expressions
> On Feb 4, 2015, at 12:16 PM, Chad Rosier <mcrosier at codeaurora.org> wrote: > >>> 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 idempotenceYet the current assertions rely on it.> ; we have bigger fish to fry.I like the metaphor :) Mehdi> >> >>>> >>>> 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