[LSR] canonicalize Prod*(1<<C) to Prod<<C

[jingyue]

Summary

Because LSR happens at a late stage where mul of a power of 2 is
typically canonicalized to shl, this canonicalization emits code that
can be better CSE'ed.

[jingyue]

lib/Analysis/ScalarEvolutionExpander.cpp

792

Btw, visitUDivExpr does similar canonicalization too.

[majnemer]

lib/Analysis/ScalarEvolutionExpander.cpp

771–774

You could write this most concisely as:

// Canonicalize Prod*(1<<C) to Prod<<C.
if (match(W, m_Power2()) {
  ...
}

771–774

s/most/more

[jingyue]

Simplify the code with match(m_Power2). Thanks David!

[jingyue]

ping?

[sanjoy]

I don't see anything wrong with this change, but I also do not know LSR well enough to LGTM it. I suppose you'll have to wait for Andy to chime in.

[majnemer]

lib/Analysis/ScalarEvolutionExpander.cpp

31–32

I'd add using namespace PatternMatch; here.

772

With the using declaration, we can remove the scope qualifiers here.

772–778

Seeing the continue here is a little confusing, can we just make it an if/else?

774–775

I'd use Constant::getIntegerValue instead as it handles the case where Ty is a vector type.

[jingyue]

using namespace PatternMatch and some other minor changes

[jingyue]

Thanks for the review, David.

lib/Analysis/ScalarEvolutionExpander.cpp

31–32

done

772

done

772–778

done

774–775

Vector types are not SCEVable, so SCEV::getType() never returns a vector type. But it doesn't harm to add an assert.

[majnemer]

LGTM

[atrick]

Sorry I dropped this review. You change is fine with me.

lib/Analysis/ScalarEvolutionExpander.cpp

 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
+using namespace PatternMatch;
 
 /// ReuseOrCreateCast - Arrange for there to be a cast of V to Ty at IP,
 /// reusing an existing cast if a suitable one exists, moving an existing
 /// cast if a suitable one exists but isn't in the right place, or
 /// creating a new one.
 Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty,
                                        Instruction::CastOps Op,
                                        BasicBlock::iterator IP) {
Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) {
 
   // Sort by loop. Use a stable sort so that constants follow non-constants.
   std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(*SE.DT));
 
   // Emit instructions to mul all the operands. Hoist as much as possible
   // out of loops.
   Value *Prod = nullptr;
   for (SmallVectorImpl<std::pair<const Loop *, const SCEV *> >::iterator
-       I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E; ) {
+       I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E; ++I) {
     const SCEV *Op = I->second;
     if (!Prod) {
       // This is the first operand. Just expand it.
       Prod = expand(Op);
-      ++I;
     } else if (Op->isAllOnesValue()) {
       // Instead of doing a multiply by negative one, just do a negate.
       Prod = InsertNoopCastOfTo(Prod, Ty);
       Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod);
-      ++I;
     } else {
       // A simple mul.
       Value *W = expandCodeFor(Op, Ty);
       Prod = InsertNoopCastOfTo(Prod, Ty);
       // Canonicalize a constant to the RHS.
       if (isa<Constant>(Prod)) std::swap(Prod, W);
+      const APInt *RHS;
+      if (match(W, m_Power2(RHS))) {
+        // Canonicalize Prod*(1<<C) to Prod<<C.
+        assert(!Ty->isVectorTy() && "vector types are not SCEVable");
+        Prod = InsertBinop(Instruction::Shl, Prod,
+                           ConstantInt::get(Ty, RHS->logBase2()));
+      } else {
         Prod = InsertBinop(Instruction::Mul, Prod, W);
-      ++I;
+      }
     }
   }
 
   return Prod;
 }
 
 Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) {
   Type *Ty = SE.getEffectiveSCEVType(S->getType());
 
   Value *LHS = expandCodeFor(S->getLHS(), Ty);
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) {
     const APInt &RHS = SC->getValue()->getValue();
     if (RHS.isPowerOf2())
       return InsertBinop(Instruction::LShr, LHS,
                          ConstantInt::get(Ty, RHS.logBase2()));
   }
 
   Value *RHS = expandCodeFor(S->getRHS(), Ty);
   return InsertBinop(Instruction::UDiv, LHS, RHS);
 }
 

test/Transforms/LoopIdiom/basic.ll

for.body:                                         ; preds = %entry, %for.body
   %inc = add nsw i64 %i.011, 1
   %exitcond = icmp eq i64 %inc, %Size
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 ; CHECK-LABEL: @test2(
 ; CHECK: br i1 %cmp10,
-; CHECK: %0 = mul i64 %Size, 4
+; CHECK: %0 = shl i64 %Size, 2
 ; CHECK: call void @llvm.memset.p0i8.i64(i8* %Base1, i8 1, i64 %0, i32 4, i1 false)
 ; CHECK-NOT: store
 }
 
 ; This is a case where there is an extra may-aliased store in the loop, we can't
 ; promote the memset.
 define void @test3(i32* %Base, i64 %Size, i8 *%MayAlias) nounwind ssp {
 entry:

test/Transforms/LoopReroll/nonconst_lb.ll

 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 ; CHECK-LABEL: @foo
 ; CHECK: for.body.preheader:                               ; preds = %entry
 ; CHECK:   %0 = add i32 %n, -1
 ; CHECK:   %1 = sub i32 %0, %m
 ; CHECK:   %2 = lshr i32 %1, 2
-; CHECK:   %3 = mul i32 %2, 4
+; CHECK:   %3 = shl i32 %2, 2
 ; CHECK:   %4 = add i32 %m, %3
 ; CHECK:   %5 = add i32 %4, 3
 ; CHECK:   br label %for.body
 
 ; CHECK: for.body:                                         ; preds = %for.body, %for.body.preheader
 ; CHECK:   %indvar = phi i32 [ %indvar.next, %for.body ], [ 0, %for.body.preheader ]
 ; CHECK:   %6 = add i32 %m, %indvar
 ; CHECK:   %arrayidx = getelementptr inbounds i32, i32* %B, i32 %6
for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 ; CHECK-LABEL: @daxpy_ur
 ; CHECK: for.body.preheader:
 ; CHECK:   %0 = add i32 %n, -1
 ; CHECK:   %1 = sub i32 %0, %rem
 ; CHECK:   %2 = lshr i32 %1, 2
-; CHECK:   %3 = mul i32 %2, 4
+; CHECK:   %3 = shl i32 %2, 2
 ; CHECK:   %4 = add i32 %rem, %3
 ; CHECK:   %5 = add i32 %4, 3
 ; CHECK:   br label %for.body
 
 ; CHECK: for.body:
 ; CHECK:   %indvar = phi i32 [ %indvar.next, %for.body ], [ 0, %for.body.preheader ]
 ; CHECK:   %6 = add i32 %rem, %indvar
 ; CHECK:   %arrayidx = getelementptr inbounds float, float* %dy, i32 %6

test/Transforms/LoopStrengthReduce/2011-10-06-ReusePhi.ll

 ; RUN: opt -loop-reduce -S < %s | FileCheck %s
 ;
 ; Test LSR's intelligence regarding phi reuse.
 ; Verify that scaled GEPs are not reused. rdar://5064068
 
 target triple = "x86-apple-darwin"
 
 ; Provide legal integer types.
 target datalayout = "n8:16:32:64"
 
 
 ; CHECK-LABEL: @test(
 ; multiplies are hoisted out of the loop
 ; CHECK: while.body.lr.ph:
-; CHECK: mul i64
-; CHECK: mul i64
+; CHECK: shl i64
+; CHECK: shl i64
 ; GEPs are ugly
 ; CHECK: while.body:
 ; CHECK: phi
 ; CHECK: phi
 ; CHECK: phi
 ; CHECK: phi
 ; CHECK-NOT: phi
 ; CHECK: bitcast float* {{.*}} to i1*

test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll

 ; RUN: opt -loop-reduce -S < %s | FileCheck %s
 ; PR9939
 
 ; LSR should properly handle the post-inc offset when folding the
 ; non-IV operand of an icmp into the IV.
 
 ; CHECK:   [[r1:%[a-z0-9]+]] = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
 ; CHECK:   [[r2:%[a-z0-9]+]] = lshr i64 [[r1]], 1
-; CHECK:   [[r3:%[a-z0-9]+]] = mul i64 [[r2]], 2
+; CHECK:   [[r3:%[a-z0-9]+]] = shl i64 [[r2]], 1
 ; CHECK:   br label %for.body
 ; CHECK: for.body:
 ; CHECK:   %lsr.iv2 = phi i64 [ %lsr.iv.next, %for.body ], [ [[r3]], %for.body.lr.ph ]
 ; CHECK:   %lsr.iv.next = add i64 %lsr.iv2, -2
 ; CHECK:   %lsr.iv.next3 = inttoptr i64 %lsr.iv.next to i16*
 ; CHECK:   %cmp27 = icmp eq i16* %lsr.iv.next3, null
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"

test/Transforms/LoopStrengthReduce/shl.ll

+; RUN: opt < %s -loop-reduce -gvn -S | FileCheck %s
+
+target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
+
+define void @_Z3fooPfll(float* nocapture readonly %input, i64 %n, i64 %s) {
+; CHECK-LABEL: @_Z3fooPfll(
+entry:
+  %mul = shl nsw i64 %s, 2
+; CHECK: %mul = shl i64 %s, 2
+  tail call void @_Z3bazl(i64 %mul) #2
+; CHECK-NEXT: call void @_Z3bazl(i64 %mul)
+  %cmp.5 = icmp sgt i64 %n, 0
+  br i1 %cmp.5, label %for.body.preheader, label %for.cond.cleanup
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.cond.cleanup.loopexit:                        ; preds = %for.body
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %i.06 = phi i64 [ %add, %for.body ], [ 0, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds float, float* %input, i64 %i.06
+; LoopStrengthReduce should reuse %mul as the stride.
+; CHECK: getelementptr i1, i1* {{[^,]+}}, i64 %mul
+  %0 = load float, float* %arrayidx, align 4
+  tail call void @_Z3barf(float %0) #2
+  %add = add nsw i64 %i.06, %s
+  %cmp = icmp slt i64 %add, %n
+  br i1 %cmp, label %for.body, label %for.cond.cleanup.loopexit
+}
+
+declare void @_Z3bazl(i64)
+
+declare void @_Z3barf(float)