Hello, I was looking into the expression folding strategies of SCEV and found out that we don't fold multiplication and divisions: define void @test12(i32) { entry: %1 = udiv i32 %0, 123 %2 = mul i32 %1, 123 %3 = udiv i32 %2, 123 %4 = mul i32 %3, 123 ret void } Will give: %4 = mul i32 %3, 123 --> (123 * ((123 * (%0 /u 123)) /u 123)) U: [0,-36) S: [0,-36) Is there a specific reason for that, or can I add a folding rule? Maybe the problem is that division can round off some lsb, and multiplication can wrap around some msb, and therefore we can't easily simplify those. But even adding "exact" on udiv and "nuw nsw" on mul does not help. Best regard. -- *Alexandre Isoard* -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170906/596858d0/attachment.html>
> On Sep 6, 2017, at 7:44 AM, Alexandre Isoard via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Hello, > > I was looking into the expression folding strategies of SCEV and found out that we don't fold multiplication and divisions: > > define void @test12(i32) { > entry: > %1 = udiv i32 %0, 123 > %2 = mul i32 %1, 123 > %3 = udiv i32 %2, 123 > %4 = mul i32 %3, 123 > ret void > } > > Will give: > > %4 = mul i32 %3, 123 > --> (123 * ((123 * (%0 /u 123)) /u 123)) U: [0,-36) S: [0,-36) > > Is there a specific reason for that, or can I add a folding rule? > > Maybe the problem is that division can round off some lsb, and multiplication can wrap around some msb, and therefore we can't easily simplify those. But even adding "exact" on udiv and "nuw nsw" on mul does not help.Hi Alexandre, The general problem is that mul and div are defined to have 2’s complement semantics (unless they are marked as being undefined on overflow). As such, "x*123/123” is not a noop. Similarly, "x/123*123” is not a noop for many cases like x = 12. -Chris
Hi Alexandre, On Wed, Sep 6, 2017 at 7:44 AM, Alexandre Isoard via llvm-dev <llvm-dev at lists.llvm.org> wrote:> I was looking into the expression folding strategies of SCEV and found out > that we don't fold multiplication and divisions: > > define void @test12(i32) { > entry: > %1 = udiv i32 %0, 123 > %2 = mul i32 %1, 123 > %3 = udiv i32 %2, 123 > %4 = mul i32 %3, 123 > ret void > } > > Will give: > > %4 = mul i32 %3, 123 > --> (123 * ((123 * (%0 /u 123)) /u 123)) U: [0,-36) S: [0,-36) > > Is there a specific reason for that, or can I add a folding rule? > > Maybe the problem is that division can round off some lsb, and > multiplication can wrap around some msb, and therefore we can't easily > simplify those. But even adding "exact" on udiv and "nuw nsw" on mul doesSCEV does not have an internal representation for exact UDiv, so it can only apply local rules, like in ScalarEvolution::getUDivExactExpr. To fix this you could either add a bit on SCEVUDivExpr that tracks exactness and add another peephole rule to getMulExpr. -- Sanjoy> not help. > > Best regard. > > -- > Alexandre Isoard > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >