[SimplifyIndVars] Ignore dead users

[mkazantsev]

Summary

IndVarSimplify sometimes makes transforms basing on users that are trivially dead. In particular,
if DCE wasn't run before it, there may be a dead sext/zext in loop that will trigger widening
transforms, however it makes no sense to do it.

This patch teaches IndVarsSimplify ignore the mist trivial cases of that.

[sanjoy]

lgtm

lib/Transforms/Utils/SimplifyIndVar.cpp

839 ↗

(On Diff #150608)

How about isInstructionTriviallyDead?

Also, please add a short comment here on why this is needed.

llvm/trunk/lib/Transforms/Utils/SimplifyIndVar.cpp

 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "indvars"
 
 STATISTIC(NumElimIdentity, "Number of IV identities eliminated");
 STATISTIC(NumElimOperand,  "Number of IV operands folded into a use");
 STATISTIC(NumFoldedUser, "Number of IV users folded into a constant");
void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) {
   // do for loop header phis that use each other.
   pushIVUsers(CurrIV, L, Simplified, SimpleIVUsers);
 
   while (!SimpleIVUsers.empty()) {
     std::pair<Instruction*, Instruction*> UseOper =
       SimpleIVUsers.pop_back_val();
     Instruction *UseInst = UseOper.first;
 
+    // If a user of the IndVar is trivially dead, we prefer just to mark it dead
+    // rather than try to do some complex analysis or transformation (such as
+    // widening) basing on it.
+    // TODO: Propagate TLI and pass it here to handle more cases.
+    if (isInstructionTriviallyDead(UseInst, /* TLI */ nullptr)) {
+      DeadInsts.emplace_back(UseInst);
+      continue;
+    }
+
     // Bypass back edges to avoid extra work.
     if (UseInst == CurrIV) continue;
 
     // Try to replace UseInst with a loop invariant before any other
     // simplifications.
     if (replaceIVUserWithLoopInvariant(UseInst))
       continue;
 

llvm/trunk/test/Analysis/ScalarEvolution/2012-05-29-MulAddRec.ll

 ; RUN: opt < %s -S -indvars -loop-unroll | FileCheck %s
 ;
 ; loop-unroll fully unrolls the inner loop, creating an interesting
 ; chain of multiplication. indvars forces SCEV to run again on the
 ; outer loop. While reducing the recurrence at %mul3, unsigned integer overflow
 ; causes one of the terms to reach zero. This forces all multiples in
 ; the recurrence to be zero, reducing the whole thing to a constant expression.
 ;
 ; PR12929: cast<Ty>() argument of incompatible type
 
+declare void @use(i8 %x)
+
 ; CHECK: @func
 ; CHECK: for.cond:
 ; CHECK: %inc1 = phi i8 [ 0, %entry ], [ %0, %for.body ]
 ; CHECK: br label %for.body
 
 ; CHECK: for.body:
 ; CHECK: %inc.9 = add i8 %inc.8, 1
 ; CHECK: %0 = add i8 %inc1, 10
for.cond.loopexit:                                ; preds = %for.body
   %0 = add i8 %inc1, 10
   %indvars.iv.next = add i8 %indvars.iv, 10
   br label %for.cond
 
 for.cond:                                         ; preds = %for.cond.loopexit, %entry
   %indvars.iv = phi i8 [ %indvars.iv.next, %for.cond.loopexit ], [ 10, %entry ]
   %mul3 = phi i8 [ undef, %entry ], [ %mul.lcssa, %for.cond.loopexit ]
   %inc1 = phi i8 [ 0, %entry ], [ %0, %for.cond.loopexit ]
+  call void @use(i8 %inc1)
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %for.cond
   %inc26 = phi i8 [ %inc1, %for.cond ], [ %inc, %for.body ]
   %mul45 = phi i8 [ %mul3, %for.cond ], [ %mul, %for.body ]
   %inc = add i8 %inc26, 1
   %mul = mul i8 %inc26, %mul45
+  call void @use(i8 %inc)
   %exitcond = icmp ne i8 %inc, %indvars.iv
   br i1 %exitcond, label %for.body, label %for.cond.loopexit
 }

llvm/trunk/test/Analysis/ScalarEvolution/guards.ll

 ; RUN: opt -S -indvars < %s | FileCheck %s
 
 ; Check that SCEV is able to recognize and use guards to prove
 ; conditions gaurding loop entries and backedges.  This isn't intended
 ; to be a comprehensive test of SCEV's simplification capabilities,
 ; tests directly testing e.g. if SCEV can elide a sext should go
 ; elsewhere.
 
 target datalayout = "n8:16:32:64"
 
 declare void @llvm.experimental.guard(i1, ...)
 
+declare void @use(i64 %x)
+
 define void @test_1(i1* %cond_buf, i32* %len_buf) {
 ; CHECK-LABEL: @test_1(
 entry:
   %len = load i32, i32* %len_buf, !range !{i32 1, i32 2147483648}
   br label %loop
 
 loop:
 ; CHECK: loop:

 ; CHECK:  %iv.inc.cmp = icmp ult i64 %indvars.iv.next, [[LEN_ZEXT]]
 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %iv.inc.cmp) [ "deopt"() ]
 ; CHECK: leave:
 
   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
   %iv.inc = add i32 %iv, 1
 
   %iv.sext = sext i32 %iv to i64
+  call void @use(i64 %iv.sext)
 
   %iv.inc.cmp = icmp slt i32 %iv.inc, %len
   call void(i1, ...) @llvm.experimental.guard(i1 %iv.inc.cmp) [ "deopt"() ]
 
   %becond = icmp ne i32 %iv, %n
   br i1 %becond, label %loop, label %leave
 
 leave:

llvm/trunk/test/Transforms/IndVarSimplify/2011-09-10-widen-nsw.ll

 ; RUN: opt < %s -indvars -S | FileCheck %s
 ; Test WidenIV::GetExtendedOperandRecurrence.
 ; %add, %sub and %mul should be extended to i64 because it is nsw, even though its
 ; sext cannot be hoisted outside the loop.
 
 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"
 
+declare void @use(i64 %x)
+
 define void @test() nounwind {
 entry:
   br i1 undef, label %for.body11, label %for.end285
 
 for.body11:                                       ; preds = %entry
   %shl = shl i32 1, 1
   %shl132 = shl i32 %shl, 1
   br label %for.body153
 
 for.body153:                                      ; preds = %for.body153, %for.body11
   br i1 undef, label %for.body170, label %for.body153
 
 ; CHECK: add nuw nsw i64 %indvars.iv, 1
 ; CHECK: sub nsw i64 %indvars.iv, 2
 ; CHECK: sub nsw i64 4, %indvars.iv
 ; CHECK: mul nuw nsw i64 %indvars.iv, 8
 for.body170:                                      ; preds = %for.body170, %for.body153
   %i2.19 = phi i32 [ %add249, %for.body170 ], [ 0, %for.body153 ]
 
   %add = add nsw i32 %i2.19, 1
   %add.idxprom = sext i32 %add to i64
+  call void @use(i64 %add.idxprom)
 
   %sub = sub nsw i32 %i2.19, 2
   %sub.idxprom = sext i32 %sub to i64
+  call void @use(i64 %sub.idxprom)
 
   %sub.neg = sub nsw i32 4, %i2.19
   %sub.neg.idxprom = sext i32 %sub.neg to i64
+  call void @use(i64 %sub.neg.idxprom)
 
   %mul = mul nsw i32 %i2.19, 8
   %mul.idxprom = sext i32 %mul to i64
+  call void @use(i64 %mul.idxprom)
 
   %add249 = add nsw i32 %i2.19, %shl132
   br label %for.body170
 for.end285:                                       ; preds = %entry
   ret void
 }

llvm/trunk/test/Transforms/IndVarSimplify/iv-widen.ll

 ; RUN: opt < %s -indvars -S | FileCheck %s
 ; RUN: opt -lcssa -loop-simplify -S < %s | opt -S -passes='require<targetir>,require<scalar-evolution>,require<domtree>,loop(indvars)'
 
 ; Provide legal integer types.
 target datalayout = "n8:16:32:64"
 
 
 target triple = "x86_64-apple-darwin"
 
+declare void @use(i64 %x)
+
 ; CHECK-LABEL: @loop_0
 ; CHECK-LABEL: B18:
 ; Only one phi now.
-; CHECK: phi
+; CHECK: phi i64
 ; CHECK-NOT: phi
 ; One trunc for the gep.
 ; CHECK: trunc i64 %indvars.iv to i32
 ; One trunc for the dummy() call.
 ; CHECK-LABEL: exit24:
 ; CHECK: trunc i64 {{.*}}lcssa.wide to i32
 define void @loop_0(i32* %a) {
 Prologue:
   br i1 undef, label %B18, label %B6
 
 B18:                                        ; preds = %B24, %Prologue
   %.02 = phi i32 [ 0, %Prologue ], [ %tmp33, %B24 ]
   %tmp23 = zext i32 %.02 to i64
+  call void @use(i64 %tmp23)
+  %tmp33 = add i32 %.02, 1
+  %o = getelementptr i32, i32* %a, i32 %.02
+  %v = load i32, i32* %o
+  %t = icmp eq i32 %v, 0
+  br i1 %t, label %exit24, label %B24
+
+B24:                                        ; preds = %B18
+  %t2 = icmp eq i32 %tmp33, 20
+  br i1 %t2, label %B6, label %B18
+
+B6:                                       ; preds = %Prologue
+  ret void
+
+exit24:                      ; preds = %B18
+  call void @dummy(i32 %.02)
+  unreachable
+}
+
+; Make sure that dead zext is removed and no widening happens.
+; CHECK-LABEL: @loop_0.dead
+; CHECK: phi i32
+; CHECK-NOT: zext
+; CHECK-NOT: trunc
+define void @loop_0.dead(i32* %a) {
+Prologue:
+  br i1 undef, label %B18, label %B6
+
+B18:                                        ; preds = %B24, %Prologue
+  %.02 = phi i32 [ 0, %Prologue ], [ %tmp33, %B24 ]
+  %tmp23 = zext i32 %.02 to i64
   %tmp33 = add i32 %.02, 1
   %o = getelementptr i32, i32* %a, i32 %.02
   %v = load i32, i32* %o
   %t = icmp eq i32 %v, 0
   br i1 %t, label %exit24, label %B24
 
 B24:                                        ; preds = %B18
   %t2 = icmp eq i32 %tmp33, 20

llvm/trunk/test/Transforms/IndVarSimplify/lftr-reuse.ll

 ; RUN: opt < %s -indvars -S | FileCheck %s
 ;
 ; Make sure that indvars can perform LFTR without a canonical IV.
 
 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"
 
 ; Perform LFTR using the original pointer-type IV.
 
+declare void @use(double %x)
+
 ;  for(char* p = base; p < base + n; ++p) {
 ;    *p = p-base;
 ;  }
 define void @ptriv(i8* %base, i32 %n) nounwind {
 entry:
   %idx.ext = sext i32 %n to i64
   %add.ptr = getelementptr inbounds i8, i8* %base, i64 %idx.ext
   %cmp1 = icmp ult i8* %base, %add.ptr

 
 loop:
   %rowidx = phi i32 [ 0, %entry ], [ %row.inc, %loop ]
   %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ]
   %diagidx = add nsw i32 %rowidx, %i
   %diagidxw = sext i32 %diagidx to i64
   %matrixp = getelementptr inbounds [0 x double], [0 x double]* %matrix, i32 0, i64 %diagidxw
   %v1 = load double, double* %matrixp
+  call void @use(double %v1)
   %iw = sext i32 %i to i64
   %vectorp = getelementptr inbounds [0 x double], [0 x double]* %vector, i32 0, i64 %iw
   %v2 = load double, double* %vectorp
+  call void @use(double %v2)
   %row.inc = add nsw i32 %rowidx, %ilead
   %i.inc = add nsw i32 %i, 1
   %cmp196 = icmp slt i32 %i.inc, %irow
   br i1 %cmp196, label %loop, label %return
 
 return:
   ret void
 }
 
 ; Avoid generating extra code to materialize a trip count. Skip LFTR.
 define void @unguardedloop([0 x double]* %matrix, [0 x double]* %vector,
                            i32 %irow, i32 %ilead) nounwind {
 entry:
   br label %loop
 
 ; CHECK: entry:
 ; CHECK-NOT: zext
 ; CHECK-NOT: add
 ; CHECK: loop:
 ; CHECK: phi i64
-; CHECK: phi i64
 ; CHECK-NOT: phi
 ; CHECK: icmp slt
 ; CHECK: br i1
 loop:
   %rowidx = phi i32 [ 0, %entry ], [ %row.inc, %loop ]
   %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ]
   %diagidx = add nsw i32 %rowidx, %i
   %diagidxw = sext i32 %diagidx to i64

llvm/trunk/test/Transforms/IndVarSimplify/loop-invariant-conditions.ll

 ; CHECK: %cmp1 = icmp slt i64 %start, -1
   %cmp1 = icmp slt i64 %indvars.iv, -1
   br i1 %cmp1, label %for.end, label %loop
 
 for.end:                                          ; preds = %if.end, %entry
   ret void
 }
 
+declare void @use(i1 %x)
+
 ; check that we handle conditions with loop invariant operands which
 ; *aren't* in the header - this is a very rare and fragile case where
 ; we have a "loop" which is known to run exactly one iteration but
 ; haven't yet simplified the uses of the IV
 define void @test10() {
 ; CHECK-LABEL: @test10
 entry:
   br label %loop

 
 latch:
   %phi2 = phi i32 [ %phi1, %left ], [ %dec, %right ]
   ; CHECK: %cmp = icmp slt i32 -1, undef
   %cmp = icmp slt i32 %phi2, undef
   br i1 true, label %exit, label %loop
 
 exit:
+  call void @use(i1 %cmp)
   ret void
 }
 
 ; check that we can figure out that iv.next > 1 from the facts that iv >= 0 and
 ; iv.start != 0.
 define void @test11(i64* %inc_ptr) {
 ; CHECK-LABEL: @test11
 entry:

llvm/trunk/test/Transforms/IndVarSimplify/no-iv-rewrite.ll

latch:                         ; preds = %for.inc50.i
   %ptr.inc = getelementptr inbounds %structIF, %structIF* %ptr.iv, i64 1
   %next.inc = getelementptr inbounds %structIF, %structIF* %ptr.inc, i64 0, i32 0
   br label %loop
 
 exit:
   ret void
 }
 
+declare void @use32(i32 %x)
+declare void @use64(i64 %x)
+
 ; Test a widened IV that is used by a phi on different paths within the loop.
 ;
 ; CHECK: for.body:
 ; CHECK: phi i64
 ; CHECK: trunc i64
 ; CHECK: if.then:
 ; CHECK: for.inc:
 ; CHECK: phi i32

 if.then33:
   br label %for.inc
 
 if.else:
   br i1 undef, label %if.then97, label %for.inc
 
 if.then97:
   %idxprom100 = sext i32 %iv to i64
+  call void @use64(i64 %idxprom100)
   br label %for.inc
 
 for.inc:
   %kmin.1 = phi i32 [ %iv, %if.then33 ], [ 0, %if.then ], [ %iv, %if.then97 ], [ 0, %if.else ]
+  call void @use32(i32 %kmin.1)
   %inc = add nsw i32 %iv, 1
   br i1 undef, label %for.body, label %for.end
 
 for.end:
   ret void
 }

llvm/trunk/test/Transforms/IndVarSimplify/pr25578.ll

 ; RUN: opt < %s -indvars -S | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
+declare void @use(i64 %x)
+
 ; CHECK-LABEL: @foo
 define void @foo() {
 entry:
   br label %L1_header
 
 L1_header:
   br label %L2_header
 
 ; CHECK: L2_header:
 ; CHECK: %[[INDVAR:.*]] = phi i64
 ; CHECK: %[[TRUNC:.*]] = trunc i64 %[[INDVAR]] to i32
 L2_header:
   %i = phi i32 [ 0, %L1_header ], [ %i_next, %L2_latch ]
   %i_prom = sext i32 %i to i64
+  call void @use(i64 %i_prom)
   br label %L3_header
 
 L3_header:
   br i1 undef, label %L3_latch, label %L2_exiting_1
 
 L3_latch:
   br i1 undef, label %L3_header, label %L2_exiting_2