From 498d3113c35d8d4f80e4d79ac9b75c3980bfc8c3 Mon Sep 17 00:00:00 2001 From: Andrew Kaylor Date: Wed, 10 Aug 2016 18:56:35 +0000 Subject: [PATCH] [IndVarSimplify] Eliminate zext of a signed IV when the IV is known to be non-negative Patch by Li Huang Differential Revision: https://reviews.llvm.org/D18867 llvm-svn: 278269 --- llvm/lib/Transforms/Scalar/IndVarSimplify.cpp | 9 ++- .../Transforms/IndVarSimplify/iv-widen-elim-ext.ll | 82 ++++++++++++++++++++++ 2 files changed, 89 insertions(+), 2 deletions(-) create mode 100644 llvm/test/Transforms/IndVarSimplify/iv-widen-elim-ext.ll diff --git a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp index 4f6dbd9..4cb2d0d 100644 --- a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -36,6 +36,7 @@ #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" @@ -1281,7 +1282,8 @@ Instruction *WidenIV::widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) { } } // Our raison d'etre! Eliminate sign and zero extension. - if (IsSigned ? isa(DU.NarrowUse) : isa(DU.NarrowUse)) { + if ((isa(DU.NarrowUse) && (IsSigned || DU.NeverNegative)) || + (isa(DU.NarrowUse) && (!IsSigned || DU.NeverNegative))) { Value *NewDef = DU.WideDef; if (DU.NarrowUse->getType() != WideType) { unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType()); @@ -1370,9 +1372,12 @@ Instruction *WidenIV::widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) { /// void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) { const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef); + // isKnownPredicate is enough for most cases but still need isKnownNonNegative + // here to work around conservatism in ScalarEvolution about no-wrap flags. bool NeverNegative = SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV, - SE->getConstant(NarrowSCEV->getType(), 0)); + SE->getConstant(NarrowSCEV->getType(), 0)) || + isKnownNonNegative(NarrowDef, NarrowDef->getModule()->getDataLayout()); for (User *U : NarrowDef->users()) { Instruction *NarrowUser = cast(U); diff --git a/llvm/test/Transforms/IndVarSimplify/iv-widen-elim-ext.ll b/llvm/test/Transforms/IndVarSimplify/iv-widen-elim-ext.ll new file mode 100644 index 0000000..97635b5 --- /dev/null +++ b/llvm/test/Transforms/IndVarSimplify/iv-widen-elim-ext.ll @@ -0,0 +1,82 @@ +; RUN: opt < %s -indvars -S | FileCheck %s + +target datalayout = "p:64:64:64-n32:64" + +; When widening IV and its users, trunc and zext/sext are not needed +; if the original 32-bit user is known to be non-negative, whether +; the IV is considered signed or unsigned. +define void @foo(i32* %A, i32* %B, i32* %C, i32 %N) { +; CHECK-LABEL: @foo( +; CHECK-NOT: zext +; CHECK-NOT: sext +entry: + %cmp1 = icmp slt i32 0, %N + br i1 %cmp1, label %for.body.lr.ph, label %for.end + +for.body.lr.ph: ; preds = %entry + br label %for.body + +for.body: ; preds = %for.body.lr.ph, %for.inc + %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ] + %idxprom = sext i32 %i.02 to i64 + %arrayidx = getelementptr inbounds i32, i32* %B, i64 %idxprom + %0 = load i32, i32* %arrayidx, align 4 + %add = add nsw i32 %i.02, 2 + %idxprom1 = zext i32 %add to i64 + %arrayidx2 = getelementptr inbounds i32, i32* %C, i64 %idxprom1 + %1 = load i32, i32* %arrayidx2, align 4 + %add3 = add nsw i32 %0, %1 + %idxprom4 = zext i32 %i.02 to i64 + %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %idxprom4 + store i32 %add3, i32* %arrayidx5, align 4 + br label %for.inc + +for.inc: ; preds = %for.body + %inc = add nsw i32 %i.02, 1 + %cmp = icmp slt i32 %inc, %N + br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge + +for.cond.for.end_crit_edge: ; preds = %for.inc + br label %for.end + +for.end: ; preds = %for.cond.for.end_crit_edge, %entry + ret void +} + +define void @foo1(i32* %A, i32* %B, i32* %C, i32 %N) { +; CHECK-LABEL: @foo1( +; CHECK-NOT: zext +; CHECK-NOT: sext +entry: + %cmp1 = icmp slt i32 0, %N + br i1 %cmp1, label %for.body.lr.ph, label %for.end + +for.body.lr.ph: ; preds = %entry + br label %for.body + +for.body: ; preds = %for.body.lr.ph, %for.inc + %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ] + %idxprom = zext i32 %i.02 to i64 + %arrayidx = getelementptr inbounds i32, i32* %B, i64 %idxprom + %0 = load i32, i32* %arrayidx, align 4 + %add = add nsw i32 %i.02, 2 + %idxprom1 = sext i32 %add to i64 + %arrayidx2 = getelementptr inbounds i32, i32* %C, i64 %idxprom1 + %1 = load i32, i32* %arrayidx2, align 4 + %add3 = add nsw i32 %0, %1 + %idxprom4 = sext i32 %i.02 to i64 + %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %idxprom4 + store i32 %add3, i32* %arrayidx5, align 4 + br label %for.inc + +for.inc: ; preds = %for.body + %inc = add nsw i32 %i.02, 1 + %cmp = icmp slt i32 %inc, %N + br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge + +for.cond.for.end_crit_edge: ; preds = %for.inc + br label %for.end + +for.end: ; preds = %for.cond.for.end_crit_edge, %entry + ret void +} -- 2.7.4