Index: lib/Transforms/Utils/LCSSA.cpp =================================================================== --- lib/Transforms/Utils/LCSSA.cpp +++ lib/Transforms/Utils/LCSSA.cpp @@ -74,6 +74,11 @@ 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(User) && !DT.dominates(&Inst, User)) + User->replaceUsesOfWith(&Inst, UndefValue::get(Inst.getType())); } // If there are no uses outside the loop, exit with no change. @@ -166,20 +171,6 @@ 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 &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; @@ -198,12 +189,6 @@ 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. Index: test/Transforms/LCSSA/unreachable-use.ll =================================================================== --- test/Transforms/LCSSA/unreachable-use.ll +++ /dev/null @@ -1,27 +0,0 @@ -; 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 -} Index: test/Transforms/LCSSA/unreachable-uses-undef.ll =================================================================== --- /dev/null +++ test/Transforms/LCSSA/unreachable-uses-undef.ll @@ -0,0 +1,31 @@ +; 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 Index: test/Transforms/LICM/pr19798-lcssa-unreachable-crash.ll =================================================================== --- /dev/null +++ test/Transforms/LICM/pr19798-lcssa-unreachable-crash.ll @@ -0,0 +1,72 @@ +; 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"}