From bbc1da8dedf77c0dd3845e09c2d78024d8738646 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Tue, 17 Aug 2010 22:50:37 +0000 Subject: Tweak IVUsers' concept of "interesting" to exclude add recurrences where the step value is an induction variable from an outer loop, to avoid trouble trying to re-expand such expressions. This effectively hides such expressions from indvars and lsr, which prevents them from getting into trouble. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@111317 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/IVUsers.cpp | 28 ++++++++++-------- test/CodeGen/X86/licm-nested.ll | 2 +- test/CodeGen/X86/lsr-interesting-step.ll | 51 ++++++++++++++++++++++++++++++++ 3 files changed, 68 insertions(+), 13 deletions(-) create mode 100644 test/CodeGen/X86/lsr-interesting-step.ll diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp index bd43026015..fd514336be 100644 --- a/lib/Analysis/IVUsers.cpp +++ b/lib/Analysis/IVUsers.cpp @@ -38,27 +38,31 @@ Pass *llvm::createIVUsersPass() { /// isInteresting - Test whether the given expression is "interesting" when /// used by the given expression, within the context of analyzing the /// given loop. -static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L) { - // Anything loop-invariant is interesting. - if (!isa(S) && S->isLoopInvariant(L)) - return true; - +static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, + ScalarEvolution *SE) { // An addrec is interesting if it's affine or if it has an interesting start. if (const SCEVAddRecExpr *AR = dyn_cast(S)) { // Keep things simple. Don't touch loop-variant strides. if (AR->getLoop() == L) return AR->isAffine() || !L->contains(I); - // Otherwise recurse to see if the start value is interesting. - return isInteresting(AR->getStart(), I, L); + // Otherwise recurse to see if the start value is interesting, and that + // the step value is not interesting, since we don't yet know how to + // do effective SCEV expansions for addrecs with interesting steps. + return isInteresting(AR->getStart(), I, L, SE) && + !isInteresting(AR->getStepRecurrence(*SE), I, L, SE); } - // An add is interesting if any of its operands is. + // An add is interesting if exactly one of its operands is interesting. if (const SCEVAddExpr *Add = dyn_cast(S)) { + bool AnyInterestingYet = false; for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end(); OI != OE; ++OI) - if (isInteresting(*OI, I, L)) - return true; - return false; + if (isInteresting(*OI, I, L, SE)) { + if (AnyInterestingYet) + return false; + AnyInterestingYet = true; + } + return AnyInterestingYet; } // Nothing else is interesting here. @@ -84,7 +88,7 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) { // If we've come to an uninteresting expression, stop the traversal and // call this a user. - if (!isInteresting(ISE, I, L)) + if (!isInteresting(ISE, I, L, SE)) return false; SmallPtrSet UniqueUsers; diff --git a/test/CodeGen/X86/licm-nested.ll b/test/CodeGen/X86/licm-nested.ll index 71685bb5b8..870f687e56 100644 --- a/test/CodeGen/X86/licm-nested.ll +++ b/test/CodeGen/X86/licm-nested.ll @@ -1,4 +1,4 @@ -; RUN: llc -mtriple=x86_64-apple-darwin -march=x86-64 < %s -stats -info-output-file - | grep machine-licm | grep 2 +; RUN: llc -mtriple=x86_64-apple-darwin -march=x86-64 < %s -stats -info-output-file - | grep machine-licm | grep 3 ; MachineLICM should be able to hoist the symbolic addresses out of ; the inner loops. diff --git a/test/CodeGen/X86/lsr-interesting-step.ll b/test/CodeGen/X86/lsr-interesting-step.ll new file mode 100644 index 0000000000..4b7050bd50 --- /dev/null +++ b/test/CodeGen/X86/lsr-interesting-step.ll @@ -0,0 +1,51 @@ +; RUN: llc < %s -march=x86-64 -relocation-model=static -mtriple=x86_64-unknown-linux-gnu + +; The inner loop should require only one add (and no leas either). +; rdar://8100380 + +; CHECK: BB0_4: +; CHECK-NEXT: movb $0, flags(%rdx) +; CHECK-NEXT: addq %rcx, %rdx +; CHECK-NEXT: cmpq $8192, %rdx +; CHECK-NEXT: jl + +@flags = external global [8192 x i8], align 16 ; <[8192 x i8]*> [#uses=1] + +define void @foo() nounwind { +entry: + %tmp = icmp slt i64 2, 8192 ; [#uses=1] + br i1 %tmp, label %bb, label %bb21 + +bb: ; preds = %entry + br label %bb7 + +bb7: ; preds = %bb, %bb17 + %tmp8 = phi i64 [ %tmp18, %bb17 ], [ 2, %bb ] ; [#uses=2] + %tmp9 = icmp slt i64 2, 8192 ; [#uses=1] + br i1 %tmp9, label %bb10, label %bb17 + +bb10: ; preds = %bb7 + br label %bb11 + +bb11: ; preds = %bb10, %bb11 + %tmp12 = phi i64 [ %tmp14, %bb11 ], [ 2, %bb10 ] ; [#uses=2] + %tmp13 = getelementptr inbounds [8192 x i8]* @flags, i64 0, i64 %tmp12 ; [#uses=1] + store i8 0, i8* %tmp13, align 1 + %tmp14 = add nsw i64 %tmp12, %tmp8 ; [#uses=2] + %tmp15 = icmp slt i64 %tmp14, 8192 ; [#uses=1] + br i1 %tmp15, label %bb11, label %bb16 + +bb16: ; preds = %bb11 + br label %bb17 + +bb17: ; preds = %bb16, %bb7 + %tmp18 = add nsw i64 %tmp8, 1 ; [#uses=2] + %tmp19 = icmp slt i64 %tmp18, 8192 ; [#uses=1] + br i1 %tmp19, label %bb7, label %bb20 + +bb20: ; preds = %bb17 + br label %bb21 + +bb21: ; preds = %bb20, %entry + ret void +} -- cgit v1.2.3