[llvm-bugs] [Bug 26049] New: llvm should not emit any compiler-rt calls for division/modulo involving quotients that are powers of two

[via llvm-bugs]

https://llvm.org/bugs/show_bug.cgi?id=26049

            Bug ID: 26049
           Summary: llvm should not emit any compiler-rt calls for
                    division/modulo involving quotients that are powers of
                    two
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: mgottesman at apple.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

This is an old bug by majnemer. I am just moving it upstream since I am not
going to have time to look at it.

Consider:

unsigned long long howmany(unsigned long long x, unsigned y) {
    return (x % y == 0) ? (x / y) : ((x / y) + 1);
}
unsigned long long howmany2(unsigned long long x, unsigned r) {
    return howmany(x, (1U << r));
}

llvm generates:
_howmany2:
@ BB#0:                                 @ %entry
    push    {r4, r5, r6, r7, lr}
    add    r7, sp, #12
    push.w    {r8, r10}
    movs    r3, #1
    mov    r5, r0
    lsl.w    r6, r3, r2
    mov    r0, r5
    mov    r2, r6
    movs    r3, #0
    mov    r4, r1
    blx    ___udivdi3
    mov    r8, r0
    mov    r10, r1
    mov    r0, r5
    mov    r1, r4
    mov    r2, r6
    movs    r3, #0
    blx    ___umoddi3
    orrs    r0, r1
    it    ne
    movne    r0, #1
    adds.w    r0, r0, r8
    adc    r1, r10, #0
    pop.w    {r8, r10}
    pop    {r4, r5, r6, r7, pc}

all we need is:
unsigned long long howmany3(unsigned long long x, unsigned r) {
    unsigned rem = (unsigned)(x & ((1U << r) - 1U));
    unsigned long long quot = x >> r;
    return quot + !!rem;
}

which llvm turns into the more reasonable:
    rsb.w    r3, r2, #32
    sub.w    r12, r2, #32
    lsr.w    r9, r0, r2
    cmp.w    r12, #0
    lsl.w    r3, r1, r3
    orr.w    r9, r9, r3
    lsr.w    r3, r1, r12
    mov.w    r12, #1
    it    lt
    movlt    r3, r9
    lsr.w    r9, r1, r2
    lsl.w    r1, r12, r2
    subs    r1, #1
    ands    r0, r1
    it    ne
    movne    r0, #1
    adds    r0, r0, r3
    adc    r1, r9, #0
    bx    lr

----

This was the proposed patch:

----
Index: lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp    (revision 159020)
+++ lib/Transforms/InstCombine/InstCombineMulDivRem.cpp    (working copy)
@@ -630,9 +630,18 @@
   }

   // Turn A % (C << N), where C is 2^k, into A & ((C << N)-1)  
-  if (match(Op1, m_Shl(m_Power2(), m_Value()))) {
-    Constant *N1 = Constant::getAllOnesValue(I.getType());
-    Value *Add = Builder->CreateAdd(Op1, N1);
+  if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
+      match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
+    Value *Shr;
+    ZExtInst *Z = dyn_cast<ZExtInst>(Op1);
+    if (Z)
+      Shr = Z->getOperand(0);
+    else
+      Shr = Op1;
+    Constant *N1 = Constant::getAllOnesValue(Shr->getType());
+    Value *Add = Builder->CreateAdd(Shr, N1);
+    if (Z)
+      Add = Builder->CreateZExt(Add, Z->getDestTy());
     return BinaryOperator::CreateAnd(Op0, Add);
   }
----

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20160106/9bdecaff/attachment.html>