From 51d40aea3b6e74dea4b3c6680f00921441a30522 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Tue, 8 Dec 2015 00:13:17 +0000 Subject: [PATCH] [SCEVExpander] Have hoistIVInc preserve LCSSA Summary: (Note: the problematic invocation of hoistIVInc that caused PR24804 came from IndVarSimplify, not from SCEVExpander itself) Fixes PR24804. Test case by David Majnemer. Reviewers: hfinkel, majnemer, atrick, mzolotukhin Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15058 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@254976 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LoopInfo.h | 73 +++++++++++++++++++++++ lib/Analysis/ScalarEvolutionExpander.cpp | 3 + test/Transforms/IndVarSimplify/pr24804.ll | 25 ++++++++ 3 files changed, 101 insertions(+) create mode 100644 test/Transforms/IndVarSimplify/pr24804.ll diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 9196250233c..616d6ad1761 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -37,6 +37,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" #include "llvm/Pass.h" #include @@ -681,6 +682,78 @@ public: // it as a replacement will not break LCSSA form. return ToLoop->contains(getLoopFor(From->getParent())); } + + /// \brief Checks if moving a specific instruction can break LCSSA in any + /// loop. + /// + /// Return true if moving \p Inst to before \p NewLoc will break LCSSA, + /// assuming that the function containing \p Inst and \p NewLoc is currently + /// in LCSSA form. + bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) { + assert(Inst->getFunction() == NewLoc->getFunction() && + "Can't reason about IPO!"); + + auto *OldBB = Inst->getParent(); + auto *NewBB = NewLoc->getParent(); + + // Movement within the same loop does not break LCSSA (the equality check is + // to avoid doing a hashtable lookup in case of intra-block movement). + if (OldBB == NewBB) + return true; + + auto *OldLoop = getLoopFor(OldBB); + auto *NewLoop = getLoopFor(NewBB); + + if (OldLoop == NewLoop) + return true; + + // Check if Outer contains Inner; with the null loop counting as the + // "outermost" loop. + auto Contains = [](const Loop *Outer, const Loop *Inner) { + return !Outer || Outer->contains(Inner); + }; + + // To check that the movement of Inst to before NewLoc does not break LCSSA, + // we need to check two sets of uses for possible LCSSA violations at + // NewLoc: the users of NewInst, and the operands of NewInst. + + // If we know we're hoisting Inst out of an inner loop to an outer loop, + // then the uses *of* Inst don't need to be checked. + + if (!Contains(NewLoop, OldLoop)) { + for (Use &U : Inst->uses()) { + auto *UI = cast(U.getUser()); + auto *UBB = isa(UI) ? cast(UI)->getIncomingBlock(U) + : UI->getParent(); + if (UBB != NewBB && getLoopFor(UBB) != NewLoop) + return false; + } + } + + // If we know we're sinking Inst from an outer loop into an inner loop, then + // the *operands* of Inst don't need to be checked. + + if (!Contains(OldLoop, NewLoop)) { + // See below on why we can't handle phi nodes here. + if (isa(Inst)) + return false; + + for (Use &U : Inst->operands()) { + auto *DefI = dyn_cast(U.get()); + if (!DefI) + return false; + + // This would need adjustment if we allow Inst to be a phi node -- the + // new use block won't simply be NewBB. + + auto *DefBlock = DefI->getParent(); + if (DefBlock != NewBB && getLoopFor(DefBlock) != NewLoop) + return false; + } + } + + return true; + } }; // Allow clients to walk the list of nested loops... diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index 8c5805e9d16..abfcfbafb32 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -933,6 +933,9 @@ bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) { !SE.DT.dominates(InsertPos->getParent(), IncV->getParent())) return false; + if (!SE.LI.movementPreservesLCSSAForm(IncV, InsertPos)) + return false; + // Check that the chain of IV operands leading back to Phi can be hoisted. SmallVector IVIncs; for(;;) { diff --git a/test/Transforms/IndVarSimplify/pr24804.ll b/test/Transforms/IndVarSimplify/pr24804.ll new file mode 100644 index 00000000000..6f89481853a --- /dev/null +++ b/test/Transforms/IndVarSimplify/pr24804.ll @@ -0,0 +1,25 @@ +; RUN: opt -indvars -loop-idiom -loop-deletion -S < %s | FileCheck %s + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Checking for a crash + +define void @f(i32* %a) { +; CHECK-LABEL: @f( +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %for.cond, %entry + %iv = phi i32 [ 0, %entry ], [ %add, %for.inc ], [ %iv, %for.cond ] + %add = add nsw i32 %iv, 1 + %idxprom = sext i32 %add to i64 + %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom + br i1 undef, label %for.cond, label %for.inc + +for.inc: ; preds = %for.cond + br i1 undef, label %for.cond, label %for.end + +for.end: ; preds = %for.inc + ret void +} -- 2.34.1