Fix crash in LICM due to unreachable uses after LCSSA

[aemerson]

Summary

This patch fixes a crash in LICM due to an unreachable use being missed by LCSSA (pr19798).

As LCSSA needs to check uses of all loop definitions, I've had to remove the early-exit optimisation to avoid scanning uses of blocks which don't dominate loop exits (and it's associated test). This may have an impact on compile times for large loops, but I'm not sure of any alternatives here.

Review appreciated.

[aemerson]

Clean up tests a bit.

[chandlerc]

Generally, the strategy seems fine here. I share the concern over compile time regressions though.

Have you been able to collect any numbers to see how bad this is? The test suite, spec, or anything else with a decent diversity of loops would seem to be suitable....

[aemerson]

No, I haven't done any compile-time benchmarking. When I get some free time I'll throw this patch at LNT and report back the results.

Cheers,
Amara

lib/Transforms/Utils/LCSSA.cpp

static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
   for (Use &U : Inst.uses()) {
     Instruction *User = cast<Instruction>(U.getUser());
     BasicBlock *UserBB = User->getParent();
     if (PHINode *PN = dyn_cast<PHINode>(User))
       UserBB = PN->getIncomingBlock(U);
 
     if (InstBB != UserBB && !L.contains(UserBB))
       UsesToRewrite.push_back(&U);
+
+    // Kill any unreachable uses. We do this so loop passes can safely make
+    // the assumption that all external users of loop defs are PHIs.
+    if (!isa<PHINode>(User) && !DT.dominates(&Inst, User))
+      User->replaceUsesOfWith(&Inst, UndefValue::get(Inst.getType()));
   }
 
   // If there are no uses outside the loop, exit with no change.
   if (UsesToRewrite.empty())
     return false;
 
   ++NumLCSSA; // We are applying the transformation
 
static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
   for (unsigned i = 0, e = AddedPHIs.size(); i != e; ++i) {
     if (AddedPHIs[i]->use_empty())
       AddedPHIs[i]->eraseFromParent();
   }
 
   return true;
 }
 
-/// Return true if the specified block dominates at least
-/// one of the blocks in the specified list.
-static bool
-blockDominatesAnExit(BasicBlock *BB,
-                     DominatorTree &DT,
-                     const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
-  DomTreeNode *DomNode = DT.getNode(BB);
-  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
-    if (DT.dominates(DomNode, DT.getNode(ExitBlocks[i])))
-      return true;
-
-  return false;
-}
-
 bool llvm::formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE) {
   bool Changed = false;
 
   // Get the set of exiting blocks.
   SmallVector<BasicBlock *, 8> ExitBlocks;
   L.getExitBlocks(ExitBlocks);
 
   if (ExitBlocks.empty())
     return false;
 
   PredIteratorCache PredCache;
 
   // Look at all the instructions in the loop, checking to see if they have uses
   // outside the loop.  If so, rewrite those uses.
   for (Loop::block_iterator BBI = L.block_begin(), BBE = L.block_end();
        BBI != BBE; ++BBI) {
     BasicBlock *BB = *BBI;
 
-    // For large loops, avoid use-scanning by using dominance information:  In
-    // particular, if a block does not dominate any of the loop exits, then none
-    // of the values defined in the block could be used outside the loop.
-    if (!blockDominatesAnExit(BB, DT, ExitBlocks))
-      continue;
-
     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
       // Reject two common cases fast: instructions with no uses (like stores)
       // and instructions with one use that is in the same block as this.
       if (I->use_empty() ||
           (I->hasOneUse() && I->user_back()->getParent() == BB &&
            !isa<PHINode>(I->user_back())))
         continue;
 

test/Transforms/LCSSA/unreachable-use.ll

-; RUN: opt < %s -lcssa -S -verify-loop-info | grep "[%]tmp33 = load i1\*\* [%]tmp"
-; PR6546
-
-; LCSSA doesn't need to transform uses in blocks not reachable
-; from the entry block.
-
-define fastcc void @dfs() nounwind {
-bb:
-  br label %bb44
-
-bb44:
-  br i1 undef, label %bb7, label %bb45
-
-bb7:
-  %tmp = bitcast i1** undef to i1**
-  br label %bb15
-
-bb15:
-  br label %bb44
-
-bb32:
-  %tmp33 = load i1** %tmp, align 8
-  br label %bb45
-
-bb45:
-  unreachable
-}

test/Transforms/LCSSA/unreachable-uses-undef.ll

+; RUN: opt < %s -lcssa -S -verify-loop-info | FileCheck %s
+; ModuleID = 'licm.c'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define i32 @func(i32 %a, i32 %b) #0 {
+  %1 = icmp sgt i32 %a, 0
+  br i1 %1, label %.lr.ph, label %._crit_edge
+
+.lr.ph:                                           ; preds = %0, %.lr.ph
+  %i.02 = phi i32 [ %4, %.lr.ph ], [ 0, %0 ]
+  %c.01 = phi i32 [ %3, %.lr.ph ], [ undef, %0 ]
+  %2 = tail call i32 @func2(i32 %a) #2
+  %3 = add nsw i32 %2, %c.01
+  %4 = add nsw i32 %i.02, 1
+  %exitcond = icmp eq i32 %4, %a
+  %tmp = icmp eq i32 %4, %3
+  br i1 %exitcond, label %._crit_edge, label %.lr.ph
+
+.deaduse:
+  br i1 %tmp, label %.deaduse, label %.deaduse
+; CHECK: .deaduse
+; CHECK-NEXT: br i1 undef
+
+._crit_edge:                                      ; preds = %.lr.ph, %0
+  %c.0.lcssa = phi i32 [ undef, %0 ], [ %3, %.lr.ph ]
+  ret i32 %c.0.lcssa
+}
+
+declare i32 @func2(i32) #1

test/Transforms/LICM/pr19798-lcssa-unreachable-crash.ll

+; RUN: opt < %s -licm -S -verify-loop-info | FileCheck %s
+; ModuleID = 'test2.bc'
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.9.0"
+
+@b = internal global i32 0, align 4
+
+; Function Attrs: nounwind ssp uwtable
+define i32 @main() #0 {
+for.cond1thread-pre-split.lr.ph:
+  %c = alloca i32, align 4
+  store i32 0, i32* %c, align 4
+  %a = alloca i32, align 4
+  store i32 0, i32* %a, align 4
+  %a.promoted = load i32* %a, align 4, !tbaa !1
+  %0 = icmp sgt i32 %a.promoted, 0
+  br label %for.cond1thread-pre-split
+
+for.cond1thread-pre-splitthread-pre-split:        ; preds = %for.inc12
+  %.pr15.pr = load i32* %c, align 4
+  br label %for.cond1thread-pre-split
+
+for.cond1thread-pre-split:                        ; preds = %for.cond1thread-pre-splitthread-pre-split, %for.cond1thread-pre-split.lr.ph
+  %.pr15 = phi i32 [ %.pr15.pr, %for.cond1thread-pre-splitthread-pre-split ], [ 0, %for.cond1thread-pre-split.lr.ph ]
+  %inc1320 = phi i32 [ %a.promoted, %for.cond1thread-pre-split.lr.ph ], [ %inc13, %for.cond1thread-pre-splitthread-pre-split ]
+  %cmp217 = icmp slt i32 %.pr15, 1
+  br i1 %cmp217, label %for.body3.lr.ph, label %for.inc12
+
+for.body3.lr.ph:                                  ; preds = %for.cond1thread-pre-split
+  %tobool7 = icmp eq i32 %inc1320, 0
+  %c.promoted = load i32* %c, align 4, !tbaa !1
+  %1 = icmp sgt i32 %c.promoted, 0
+  br label %for.inc9
+
+for.body6:                                        ; preds = %for.body6, %for.body6
+  br i1 %tobool7, label %for.body6, label %for.body6 ; Unreachable use!
+; CHECK: for.body6
+; CHECK-NEXT: br i1 undef
+
+for.inc9:                                         ; preds = %for.inc9, %for.body3.lr.ph
+  %inc1018 = phi i32 [ %c.promoted, %for.body3.lr.ph ], [ %inc10, %for.inc9 ]
+  %inc10 = add nsw i32 %inc1018, 1
+  %cmp2 = icmp slt i32 %inc1018, 0
+  br i1 %cmp2, label %for.inc9, label %for.cond1.for.inc12_crit_edge
+
+for.cond1.for.inc12_crit_edge:                    ; preds = %for.inc9
+  %c.promoted.op = add i32 %c.promoted, 1
+  %2 = select i1 %1, i32 %c.promoted.op, i32 1
+  store i32 %2, i32* %c, align 4, !tbaa !1
+  br label %for.inc12
+
+for.inc12:                                        ; preds = %for.cond1.for.inc12_crit_edge, %for.cond1thread-pre-split
+  %inc13 = add nsw i32 %inc1320, 1
+  %cmp = icmp slt i32 %inc1320, 0
+  br i1 %cmp, label %for.cond1thread-pre-splitthread-pre-split, label %for.end14
+
+for.end14:                                        ; preds = %for.inc12
+  %a.promoted.op = add i32 %a.promoted, 1
+  %3 = select i1 %0, i32 %a.promoted.op, i32 1
+  store i32 %3, i32* %a, align 4, !tbaa !1
+  ret i32 0
+}
+
+attributes #0 = { nounwind ssp uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = metadata !{metadata !"clang version 3.5.0 "}
+!1 = metadata !{metadata !2, metadata !2, i64 0}
+!2 = metadata !{metadata !"int", metadata !3, i64 0}
+!3 = metadata !{metadata !"omnipotent char", metadata !4, i64 0}
+!4 = metadata !{metadata !"Simple C/C++ TBAA"}