From 589bf0865ccd10d36f406d622c0160be249343e1 Mon Sep 17 00:00:00 2001 From: Dale Johannesen Date: Mon, 1 Dec 2008 22:00:01 +0000 Subject: [PATCH] Consider only references to an IV within the loop when figuring out the base of the IV. This produces better code in the example. (Addresses use (IV) instead of (BASE,IV) - a significant improvement on low-register machines like x86). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60374 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopStrengthReduce.cpp | 32 +++++++++++++++---- .../2008-12-01-loop-iv-used-outside-loop.ll | 28 ++++++++++++++++ 2 files changed, 54 insertions(+), 6 deletions(-) create mode 100644 test/CodeGen/X86/2008-12-01-loop-iv-used-outside-loop.ll diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 78bd50e98a4..b3a508e863c 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -643,7 +643,9 @@ void BasedUser::RewriteInstructionToUseNewBase(const SCEVHandle &NewBase, // cases (e.g. use of a post-incremented induction variable) the NewBase // value will be pinned to live somewhere after the original computation. // In this case, we have to back off. - if (!isUseOfPostIncrementedValue) { + // However, do not insert new code inside the loop when the reference + // is outside. + if (!isUseOfPostIncrementedValue && L->contains(Inst->getParent())) { if (NewBasePt && isa(OperandValToReplace)) { InsertPt = NewBasePt; ++InsertPt; @@ -921,14 +923,16 @@ static void SeparateSubExprs(std::vector &SubExprs, /// (a+c+d) -> (a+c). The common expression is *removed* from the Bases. static SCEVHandle RemoveCommonExpressionsFromUseBases(std::vector &Uses, - ScalarEvolution *SE) { + ScalarEvolution *SE, Loop *L) { unsigned NumUses = Uses.size(); - // Only one use? Use its base, regardless of what it is! + // Only one use? If inside the loop, use its base, regardless of what it is; + // if outside, use 0. SCEVHandle Zero = SE->getIntegerSCEV(0, Uses[0].Base->getType()); SCEVHandle Result = Zero; if (NumUses == 1) { - std::swap(Result, Uses[0].Base); + if (L->contains(Uses[0].Inst->getParent())) + std::swap(Result, Uses[0].Base); return Result; } @@ -941,7 +945,13 @@ RemoveCommonExpressionsFromUseBases(std::vector &Uses, std::vector UniqueSubExprs; std::vector SubExprs; + uint64_t NumUsesInsideLoop = 0; for (unsigned i = 0; i != NumUses; ++i) { + // For this purpose, consider only uses that are inside the loop. + if (!L->contains(Uses[i].Inst->getParent())) + continue; + NumUsesInsideLoop++; + // If the base is zero (which is common), return zero now, there are no // CSEs we can find. if (Uses[i].Base == Zero) return Zero; @@ -961,7 +971,7 @@ RemoveCommonExpressionsFromUseBases(std::vector &Uses, std::map::iterator I = SubExpressionUseCounts.find(UniqueSubExprs[i]); assert(I != SubExpressionUseCounts.end() && "Entry not found?"); - if (I->second == NumUses) { // Found CSE! + if (I->second == NumUsesInsideLoop) { // Found CSE! Result = SE->getAddExpr(Result, I->first); } else { // Remove non-cse's from SubExpressionUseCounts. @@ -974,6 +984,10 @@ RemoveCommonExpressionsFromUseBases(std::vector &Uses, // Otherwise, remove all of the CSE's we found from each of the base values. for (unsigned i = 0; i != NumUses; ++i) { + // For this purpose, consider only uses that are inside the loop. + if (!L->contains(Uses[i].Inst->getParent())) + continue; + // Split the expression into subexprs. SeparateSubExprs(SubExprs, Uses[i].Base, SE); @@ -1166,7 +1180,7 @@ SCEVHandle LoopStrengthReduce::CollectIVUsers(const SCEVHandle &Stride, // "A+B"), emit it to the preheader, then remove the expression from the // UsersToProcess base values. SCEVHandle CommonExprs = - RemoveCommonExpressionsFromUseBases(UsersToProcess, SE); + RemoveCommonExpressionsFromUseBases(UsersToProcess, SE, L); // Next, figure out what we can represent in the immediate fields of // instructions. If we can represent anything there, move it to the imm @@ -1450,6 +1464,12 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride, // Add BaseV to the PHI value if needed. RewriteExpr = SE->getAddExpr(RewriteExpr, SE->getUnknown(BaseV)); + // If this reference is not in the loop and we have a Common base, + // that has been added into the induction variable and must be + // subtracted off here. + if (HaveCommonExprs && !L->contains(User.Inst->getParent())) + RewriteExpr = SE->getMinusSCEV(RewriteExpr, CommonExprs); + User.RewriteInstructionToUseNewBase(RewriteExpr, NewBasePt, Rewriter, L, this, DeadInsts); diff --git a/test/CodeGen/X86/2008-12-01-loop-iv-used-outside-loop.ll b/test/CodeGen/X86/2008-12-01-loop-iv-used-outside-loop.ll new file mode 100644 index 00000000000..48de9670163 --- /dev/null +++ b/test/CodeGen/X86/2008-12-01-loop-iv-used-outside-loop.ll @@ -0,0 +1,28 @@ +; RUN: llvm-as < %s | llc -mtriple=i386-apple-darwin | grep -v lea +; ModuleID = '' +target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128" +target triple = "i386-apple-darwin9.5" + +define i8* @test(i8* %Q, i32* %L) nounwind { +entry: + br label %bb1 + +bb: ; preds = %bb1, %bb1 + %indvar.next = add i32 %P.0.rec, 1 ; [#uses=1] + br label %bb1 + +bb1: ; preds = %bb, %entry + %P.0.rec = phi i32 [ 0, %entry ], [ %indvar.next, %bb ] ; [#uses=3] + %P.0 = getelementptr i8* %Q, i32 %P.0.rec ; [#uses=2] + %0 = load i8* %P.0, align 1 ; [#uses=1] + switch i8 %0, label %bb3 [ + i8 12, label %bb + i8 42, label %bb + ] + +bb3: ; preds = %bb1 + %P.0.sum = add i32 %P.0.rec, 2 ; [#uses=1] + %1 = getelementptr i8* %Q, i32 %P.0.sum ; [#uses=1] + store i8 4, i8* %1, align 1 + ret i8* %P.0 +} -- 2.34.1