On Fri, Jul 10, 2009 at 8:35 PM, Dan Gohman<gohman at apple.com> wrote:> > > On Jul 10, 2009, at 2:03 PM, Ryan Flynn <parseerror at gmail.com> wrote: > >> I've addressed a "TODO" in ConstantRange and several in its unit test >> by implementing a stricter "multiply" method (it had been returning a >> "full" set for anything that wasn't "empty", which broader than >> necessary) >> and updated the unit test to match, but I'm not completely confident >> that I understand ConstantRange and APInt and was hoping someone more >> familiar might take a quick look and give me some feedback. >> Thanks in advance. > > Thanks for working on this! Here are some comments: > > The overflow check isn't sufficient. Unlike add, multiply can wrap > around multiple times, so it needs a more involved check. One way to > do this would be to extend the operands out to twice their original > width, do the multiply, and then check for overflow. > > For the unit tests, please check for specific values instead of > checking that One.multiply(Wrap) is equal to Wrap.multply(One) for > example, so that it won't report a pass if it both sides have the same > wrong value. > >> >> Ryan >> >> P.S. - Also, I'm not totally sure if it's appropriate to ask for this >> here, but I thought it was more so than to llvm-commit, please let me >> know otherwise as I am new around here. > > llvm-commits is the usual place for patches, but this works too. > > Dan >Dan, Thanks for the feedback, I will work on it. Ryan
Hi Ryan, In this case there already is an implementation for this, it's just hard to find being in the internals of the LoopVR pass. I'm planning to pull the multiply and udiv support out of there. Your patch looks good but beyond what Dan mentioned you have a bug calculating NewUpper: the constant ranges are half-open intervals where "[5, 10)" includes the value 9 but not 10. This means you need to subtract 1 before multiplying the uppers then add one on when you're done otherwise you end up with [5, 11) * [1, 3) = [5, 33) when it should equal [5, 21). Nick Ryan Flynn wrote:> On Fri, Jul 10, 2009 at 8:35 PM, Dan Gohman<gohman at apple.com> wrote: >> >> On Jul 10, 2009, at 2:03 PM, Ryan Flynn <parseerror at gmail.com> wrote: >> >>> I've addressed a "TODO" in ConstantRange and several in its unit test >>> by implementing a stricter "multiply" method (it had been returning a >>> "full" set for anything that wasn't "empty", which broader than >>> necessary) >>> and updated the unit test to match, but I'm not completely confident >>> that I understand ConstantRange and APInt and was hoping someone more >>> familiar might take a quick look and give me some feedback. >>> Thanks in advance. >> Thanks for working on this! Here are some comments: >> >> The overflow check isn't sufficient. Unlike add, multiply can wrap >> around multiple times, so it needs a more involved check. One way to >> do this would be to extend the operands out to twice their original >> width, do the multiply, and then check for overflow. >> >> For the unit tests, please check for specific values instead of >> checking that One.multiply(Wrap) is equal to Wrap.multply(One) for >> example, so that it won't report a pass if it both sides have the same >> wrong value. >> >>> Ryan >>> >>> P.S. - Also, I'm not totally sure if it's appropriate to ask for this >>> here, but I thought it was more so than to llvm-commit, please let me >>> know otherwise as I am new around here. >> llvm-commits is the usual place for patches, but this works too. >> >> Dan >> > > Dan, > > Thanks for the feedback, I will work on it. > > Ryan > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On Sat, Jul 11, 2009 at 5:06 PM, Nick Lewycky<nicholas at mxc.ca> wrote:> Hi Ryan, > > In this case there already is an implementation for this, it's just hard > to find being in the internals of the LoopVR pass. I'm planning to pull > the multiply and udiv support out of there. > > Your patch looks good but beyond what Dan mentioned you have a bug > calculating NewUpper: the constant ranges are half-open intervals where > "[5, 10)" includes the value 9 but not 10. This means you need to > subtract 1 before multiplying the uppers then add one on when you're > done otherwise you end up with [5, 11) * [1, 3) = [5, 33) when it should > equal [5, 21). > > Nick > > Ryan Flynn wrote: >> On Fri, Jul 10, 2009 at 8:35 PM, Dan Gohman<gohman at apple.com> wrote: >>> >>> On Jul 10, 2009, at 2:03 PM, Ryan Flynn <parseerror at gmail.com> wrote: >>> >>>> I've addressed a "TODO" in ConstantRange and several in its unit test >>>> by implementing a stricter "multiply" method (it had been returning a >>>> "full" set for anything that wasn't "empty", which broader than >>>> necessary) >>>> and updated the unit test to match, but I'm not completely confident >>>> that I understand ConstantRange and APInt and was hoping someone more >>>> familiar might take a quick look and give me some feedback. >>>> Thanks in advance. >>> Thanks for working on this! Here are some comments: >>> >>> The overflow check isn't sufficient. Unlike add, multiply can wrap >>> around multiple times, so it needs a more involved check. One way to >>> do this would be to extend the operands out to twice their original >>> width, do the multiply, and then check for overflow. >>> >>> For the unit tests, please check for specific values instead of >>> checking that One.multiply(Wrap) is equal to Wrap.multply(One) for >>> example, so that it won't report a pass if it both sides have the same >>> wrong value. >>> >>>> Ryan >>>> >>>> P.S. - Also, I'm not totally sure if it's appropriate to ask for this >>>> here, but I thought it was more so than to llvm-commit, please let me >>>> know otherwise as I am new around here. >>> llvm-commits is the usual place for patches, but this works too. >>> >>> Dan >>> >> >> Dan, >> >> Thanks for the feedback, I will work on it. >> >> Ryan >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >Nick, Thank you for pointing out the bug, and seeing as how you're planning to refactor existing stuff anyways i will leave this one to you. Ryan