diff options
author | Sanjoy Das <sanjoy@playingwithpointers.com> | 2014-12-15 22:50:15 +0000 |
---|---|---|
committer | Sanjoy Das <sanjoy@playingwithpointers.com> | 2014-12-15 22:50:15 +0000 |
commit | 4555b6d870db7b4d5b68cc8fc7f12d0d6e3769af (patch) | |
tree | 924de6d9f014c8c4d58c14bb8c4c9103746033fe /llvm | |
parent | dad56868819e04c1cf4de361d0f9811d4f41559a (diff) | |
download | bcm5719-llvm-4555b6d870db7b4d5b68cc8fc7f12d0d6e3769af.tar.gz bcm5719-llvm-4555b6d870db7b4d5b68cc8fc7f12d0d6e3769af.zip |
Teach ScalarEvolution to exploit min and max expressions when proving
isKnownPredicate.
The motivation for this change is to optimize away checks in loops
like this:
limit = min(t, len)
for (i = 0 to limit)
if (i >= len || i < 0) throw_array_of_of_bounds();
a[i] = ...
Differential Revision: http://reviews.llvm.org/D6635
llvm-svn: 224285
Diffstat (limited to 'llvm')
-rw-r--r-- | llvm/lib/Analysis/ScalarEvolution.cpp | 101 | ||||
-rw-r--r-- | llvm/test/Transforms/IndVarSimplify/backedge-on-min-max.ll | 453 |
2 files changed, 546 insertions, 8 deletions
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 06ae9c16d14..d1b73e35c49 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -6886,6 +6886,85 @@ bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred, getNotSCEV(FoundLHS)); } + +/// If Expr computes ~A, return A else return nullptr +static const SCEV *MatchNotExpr(const SCEV *Expr) { + const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Expr); + if (!Add || Add->getNumOperands() != 2) return nullptr; + + const SCEVConstant *AddLHS = dyn_cast<SCEVConstant>(Add->getOperand(0)); + if (!(AddLHS && AddLHS->getValue()->getValue().isAllOnesValue())) + return nullptr; + + const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1)); + if (!AddRHS || AddRHS->getNumOperands() != 2) return nullptr; + + const SCEVConstant *MulLHS = dyn_cast<SCEVConstant>(AddRHS->getOperand(0)); + if (!(MulLHS && MulLHS->getValue()->getValue().isAllOnesValue())) + return nullptr; + + return AddRHS->getOperand(1); +} + + +/// Is MaybeMaxExpr an SMax or UMax of Candidate and some other values? +template<typename MaxExprType> +static bool IsMaxConsistingOf(const SCEV *MaybeMaxExpr, + const SCEV *Candidate) { + const MaxExprType *MaxExpr = dyn_cast<MaxExprType>(MaybeMaxExpr); + if (!MaxExpr) return false; + + auto It = std::find(MaxExpr->op_begin(), MaxExpr->op_end(), Candidate); + return It != MaxExpr->op_end(); +} + + +/// Is MaybeMinExpr an SMin or UMin of Candidate and some other values? +template<typename MaxExprType> +static bool IsMinConsistingOf(ScalarEvolution &SE, + const SCEV *MaybeMinExpr, + const SCEV *Candidate) { + const SCEV *MaybeMaxExpr = MatchNotExpr(MaybeMinExpr); + if (!MaybeMaxExpr) + return false; + + return IsMaxConsistingOf<MaxExprType>(MaybeMaxExpr, SE.getNotSCEV(Candidate)); +} + + +/// Is LHS `Pred` RHS true on the virtue of LHS or RHS being a Min or Max +/// expression? +static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, + ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS) { + switch (Pred) { + default: + return false; + + case ICmpInst::ICMP_SGE: + std::swap(LHS, RHS); + // fall through + case ICmpInst::ICMP_SLE: + return + // min(A, ...) <= A + IsMinConsistingOf<SCEVSMaxExpr>(SE, LHS, RHS) || + // A <= max(A, ...) + IsMaxConsistingOf<SCEVSMaxExpr>(RHS, LHS); + + case ICmpInst::ICMP_UGE: + std::swap(LHS, RHS); + // fall through + case ICmpInst::ICMP_ULE: + return + // min(A, ...) <= A + IsMinConsistingOf<SCEVUMaxExpr>(SE, LHS, RHS) || + // A <= max(A, ...) + IsMaxConsistingOf<SCEVUMaxExpr>(RHS, LHS); + } + + llvm_unreachable("covered switch fell through?!"); +} + /// isImpliedCondOperandsHelper - Test whether the condition described by /// Pred, LHS, and RHS is true whenever the condition described by Pred, /// FoundLHS, and FoundRHS is true. @@ -6894,6 +6973,12 @@ ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const SCEV *FoundLHS, const SCEV *FoundRHS) { + auto IsKnownPredicateFull = + [this](ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) { + return isKnownPredicateWithRanges(Pred, LHS, RHS) || + IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS); + }; + switch (Pred) { default: llvm_unreachable("Unexpected ICmpInst::Predicate value!"); case ICmpInst::ICMP_EQ: @@ -6903,26 +6988,26 @@ ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, break; case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_SLE: - if (isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, LHS, FoundLHS) && - isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, RHS, FoundRHS)) + if (IsKnownPredicateFull(ICmpInst::ICMP_SLE, LHS, FoundLHS) && + IsKnownPredicateFull(ICmpInst::ICMP_SGE, RHS, FoundRHS)) return true; break; case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_SGE: - if (isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, LHS, FoundLHS) && - isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, RHS, FoundRHS)) + if (IsKnownPredicateFull(ICmpInst::ICMP_SGE, LHS, FoundLHS) && + IsKnownPredicateFull(ICmpInst::ICMP_SLE, RHS, FoundRHS)) return true; break; case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: - if (isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, LHS, FoundLHS) && - isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, RHS, FoundRHS)) + if (IsKnownPredicateFull(ICmpInst::ICMP_ULE, LHS, FoundLHS) && + IsKnownPredicateFull(ICmpInst::ICMP_UGE, RHS, FoundRHS)) return true; break; case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_UGE: - if (isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, LHS, FoundLHS) && - isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, RHS, FoundRHS)) + if (IsKnownPredicateFull(ICmpInst::ICMP_UGE, LHS, FoundLHS) && + IsKnownPredicateFull(ICmpInst::ICMP_ULE, RHS, FoundRHS)) return true; break; } diff --git a/llvm/test/Transforms/IndVarSimplify/backedge-on-min-max.ll b/llvm/test/Transforms/IndVarSimplify/backedge-on-min-max.ll new file mode 100644 index 00000000000..250ff9a2eca --- /dev/null +++ b/llvm/test/Transforms/IndVarSimplify/backedge-on-min-max.ll @@ -0,0 +1,453 @@ +; RUN: opt < %s -indvars -S | FileCheck %s + +;; --- signed --- + +define void @min.signed.1(i32* %a, i32 %a_len, i32 %n) { +; CHECK-LABEL: @min.signed.1 + entry: + %smin.cmp = icmp slt i32 %a_len, %n + %smin = select i1 %smin.cmp, i32 %a_len, i32 %n + %entry.cond = icmp slt i32 0, %smin + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp slt i32 %idx, %a_len + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp slt i32 %idx.inc, %smin + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @min.signed.2(i32* %a, i32 %a_len, i32 %n) { +; CHECK-LABEL: @min.signed.2 + entry: + %smin.cmp = icmp slt i32 %a_len, %n + %smin = select i1 %smin.cmp, i32 %a_len, i32 %n + %entry.cond = icmp slt i32 0, %smin + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp sgt i32 %a_len, %idx + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp slt i32 %idx.inc, %smin + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @min.signed.3(i32* %a, i32 %n) { +; CHECK-LABEL: @min.signed.3 + entry: + %smin.cmp = icmp slt i32 42, %n + %smin = select i1 %smin.cmp, i32 42, i32 %n + %entry.cond = icmp slt i32 0, %smin + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp slt i32 %idx, 42 + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp slt i32 %idx.inc, %smin + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @min.signed.4(i32* %a, i32 %n) { +; CHECK-LABEL: @min.signed.4 + entry: + %smin.cmp = icmp slt i32 42, %n + %smin = select i1 %smin.cmp, i32 42, i32 %n + %entry.cond = icmp slt i32 0, %smin + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp sgt i32 42, %idx + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp slt i32 %idx.inc, %smin + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @max.signed.1(i32* %a, i32 %a_len, i32 %n) { +; CHECK-LABEL: @max.signed.1 + entry: + %smax.cmp = icmp sgt i32 %a_len, %n + %smax = select i1 %smax.cmp, i32 %a_len, i32 %n + %entry.cond = icmp sgt i32 0, %smax + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp sgt i32 %idx, %a_len + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp sgt i32 %idx.inc, %smax + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @max.signed.2(i32* %a, i32 %a_len, i32 %n) { +; CHECK-LABEL: @max.signed.2 + entry: + %smax.cmp = icmp sgt i32 %a_len, %n + %smax = select i1 %smax.cmp, i32 %a_len, i32 %n + %entry.cond = icmp sgt i32 0, %smax + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp slt i32 %a_len, %idx + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp sgt i32 %idx.inc, %smax + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @max.signed.3(i32* %a, i32 %n, i32 %init) { +; CHECK-LABEL: @max.signed.3 + entry: + %smax.cmp = icmp sgt i32 42, %n + %smax = select i1 %smax.cmp, i32 42, i32 %n + %entry.cond = icmp sgt i32 %init, %smax + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ %init, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp sgt i32 %idx, 42 + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp sgt i32 %idx.inc, %smax + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @max.signed.4(i32* %a, i32 %n, i32 %init) { +; CHECK-LABEL: @max.signed.4 + entry: + %smax.cmp = icmp sgt i32 42, %n + %smax = select i1 %smax.cmp, i32 42, i32 %n + %entry.cond = icmp sgt i32 %init, %smax + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ %init, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp slt i32 42, %idx + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp sgt i32 %idx.inc, %smax + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +;; --- unsigned --- + +define void @min.unsigned.1(i32* %a, i32 %a_len, i32 %n) { +; CHECK-LABEL: @min.unsigned.1 + entry: + %umin.cmp = icmp ult i32 %a_len, %n + %umin = select i1 %umin.cmp, i32 %a_len, i32 %n + %entry.cond = icmp ult i32 5, %umin + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp ult i32 %idx, %a_len + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp ult i32 %idx.inc, %umin + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @min.unsigned.2(i32* %a, i32 %a_len, i32 %n) { +; CHECK-LABEL: @min.unsigned.2 + entry: + %umin.cmp = icmp ult i32 %a_len, %n + %umin = select i1 %umin.cmp, i32 %a_len, i32 %n + %entry.cond = icmp ult i32 5, %umin + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp ugt i32 %a_len, %idx + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp ult i32 %idx.inc, %umin + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @min.unsigned.3(i32* %a, i32 %n) { +; CHECK-LABEL: @min.unsigned.3 + entry: + %umin.cmp = icmp ult i32 42, %n + %umin = select i1 %umin.cmp, i32 42, i32 %n + %entry.cond = icmp ult i32 5, %umin + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp ult i32 %idx, 42 + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp ult i32 %idx.inc, %umin + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @min.unsigned.4(i32* %a, i32 %n) { +; CHECK-LABEL: @min.unsigned.4 + entry: + %umin.cmp = icmp ult i32 42, %n + %umin = select i1 %umin.cmp, i32 42, i32 %n + %entry.cond = icmp ult i32 5, %umin + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp ugt i32 42, %idx + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp ult i32 %idx.inc, %umin + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @max.unsigned.1(i32* %a, i32 %a_len, i32 %n) { +; CHECK-LABEL: @max.unsigned.1 + entry: + %umax.cmp = icmp ugt i32 %a_len, %n + %umax = select i1 %umax.cmp, i32 %a_len, i32 %n + %entry.cond = icmp ugt i32 5, %umax + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp ugt i32 %idx, %a_len + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp ugt i32 %idx.inc, %umax + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @max.unsigned.2(i32* %a, i32 %a_len, i32 %n) { +; CHECK-LABEL: @max.unsigned.2 + entry: + %umax.cmp = icmp ugt i32 %a_len, %n + %umax = select i1 %umax.cmp, i32 %a_len, i32 %n + %entry.cond = icmp ugt i32 5, %umax + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ 5, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp ult i32 %a_len, %idx + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp ugt i32 %idx.inc, %umax + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @max.unsigned.3(i32* %a, i32 %n, i32 %init) { +; CHECK-LABEL: @max.unsigned.3 + entry: + %umax.cmp = icmp ugt i32 42, %n + %umax = select i1 %umax.cmp, i32 42, i32 %n + %entry.cond = icmp ugt i32 %init, %umax + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ %init, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp ugt i32 %idx, 42 + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp ugt i32 %idx.inc, %umax + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} + +define void @max.unsigned.4(i32* %a, i32 %n, i32 %init) { +; CHECK-LABEL: @max.unsigned.4 + entry: + %umax.cmp = icmp ugt i32 42, %n + %umax = select i1 %umax.cmp, i32 42, i32 %n + %entry.cond = icmp ugt i32 %init, %umax + br i1 %entry.cond, label %loop, label %exit + + loop: + %idx = phi i32 [ %init, %entry ], [ %idx.inc, %latch ] + %idx.inc = add i32 %idx, 1 + %in.bounds = icmp ult i32 42, %idx + br i1 %in.bounds, label %ok, label %latch +; CHECK: br i1 true, label %ok, label %latch + + ok: + %addr = getelementptr i32* %a, i32 %idx + store i32 %idx, i32* %addr + br label %latch + + latch: + %be.cond = icmp ugt i32 %idx.inc, %umax + br i1 %be.cond, label %loop, label %exit + + exit: + ret void +} |