From e027d74733de7dc086c9d2190d14884e9240ce89 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Wed, 18 Mar 2015 00:41:29 +0000 Subject: [PATCH] [SCEV] Make isImpliedCond smarter. Summary: This change teaches isImpliedCond to infer things like "X sgt 0" => "X - 1 sgt -1". The `ConstantRange` class has the logic to do the heavy lifting, this change simply gets ScalarEvolution to exploit that when reasonable. Depends on D8345 Reviewers: atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D8346 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@232576 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ScalarEvolution.h | 9 ++++ lib/Analysis/ScalarEvolution.cpp | 44 +++++++++++++++++++ .../ScalarEvolution/infer-via-ranges.ll | 30 +++++++++++++ 3 files changed, 83 insertions(+) create mode 100644 test/Analysis/ScalarEvolution/infer-via-ranges.ll diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index e1d1aa3bfac..4360414e856 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -535,6 +535,15 @@ namespace llvm { const SCEV *FoundLHS, const SCEV *FoundRHS); + /// isImpliedCondOperandsViaRanges - Test whether the condition described by + /// Pred, LHS, and RHS is true whenever the condition described by Pred, + /// FoundLHS, and FoundRHS is true. Utility function used by + /// isImpliedCondOperands. + bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + const SCEV *FoundLHS, + const SCEV *FoundRHS); + /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is /// in the header of its containing loop, we know the loop executes a /// constant number of times, and the PHI node is just a recurrence diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index dfef7296848..a2d99a6ef0c 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -6942,6 +6942,9 @@ bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const SCEV *FoundLHS, const SCEV *FoundRHS) { + if (isImpliedCondOperandsViaRanges(Pred, LHS, RHS, FoundLHS, FoundRHS)) + return true; + return isImpliedCondOperandsHelper(Pred, LHS, RHS, FoundLHS, FoundRHS) || // ~x < ~y --> x > y @@ -7079,6 +7082,47 @@ ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, return false; } +/// isImpliedCondOperandsViaRanges - helper function for isImpliedCondOperands. +/// Tries to get cases like "X `sgt` 0 => X - 1 `sgt` -1". +bool ScalarEvolution::isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, + const SCEV *LHS, + const SCEV *RHS, + const SCEV *FoundLHS, + const SCEV *FoundRHS) { + if (!isa(RHS) || !isa(FoundRHS)) + // The restriction on `FoundRHS` be lifted easily -- it exists only to + // reduce the compile time impact of this optimization. + return false; + + const SCEVAddExpr *AddLHS = dyn_cast(LHS); + if (!AddLHS || AddLHS->getOperand(1) != FoundLHS || + !isa(AddLHS->getOperand(0))) + return false; + + APInt ConstFoundRHS = cast(FoundRHS)->getValue()->getValue(); + + // `FoundLHSRange` is the range we know `FoundLHS` to be in by virtue of the + // antecedent "`FoundLHS` `Pred` `FoundRHS`". + ConstantRange FoundLHSRange = + ConstantRange::makeAllowedICmpRegion(Pred, ConstFoundRHS); + + // Since `LHS` is `FoundLHS` + `AddLHS->getOperand(0)`, we can compute a range + // for `LHS`: + APInt Addend = + cast(AddLHS->getOperand(0))->getValue()->getValue(); + ConstantRange LHSRange = FoundLHSRange.add(ConstantRange(Addend)); + + // We can also compute the range of values for `LHS` that satisfy the + // consequent, "`LHS` `Pred` `RHS`": + APInt ConstRHS = cast(RHS)->getValue()->getValue(); + ConstantRange SatisfyingLHSRange = + ConstantRange::makeSatisfyingICmpRegion(Pred, ConstRHS); + + // The antecedent implies the consequent if every value of `LHS` that + // satisfies the antecedent also satisfies the consequent. + return SatisfyingLHSRange.contains(LHSRange); +} + // Verify if an linear IV with positive stride can overflow when in a // less-than comparison, knowing the invariant term of the comparison, the // stride and the knowledge of NSW/NUW flags on the recurrence. diff --git a/test/Analysis/ScalarEvolution/infer-via-ranges.ll b/test/Analysis/ScalarEvolution/infer-via-ranges.ll new file mode 100644 index 00000000000..3627c3ab45d --- /dev/null +++ b/test/Analysis/ScalarEvolution/infer-via-ranges.ll @@ -0,0 +1,30 @@ +; RUN: opt -indvars -S < %s | FileCheck %s + +define void @infer_via_ranges(i32 *%arr, i32 %n) { +; CHECK-LABEL: @infer_via_ranges + entry: + %first.itr.check = icmp sgt i32 %n, 0 + %start = sub i32 %n, 1 + br i1 %first.itr.check, label %loop, label %exit + + loop: +; CHECK-LABEL: loop: + %idx = phi i32 [ %start, %entry ] , [ %idx.dec, %in.bounds ] + %idx.dec = sub i32 %idx, 1 + %abc = icmp sge i32 %idx, 0 +; CHECK: br i1 true, label %in.bounds, label %out.of.bounds + br i1 %abc, label %in.bounds, label %out.of.bounds + + in.bounds: +; CHECK-LABEL: in.bounds: + %addr = getelementptr i32, i32* %arr, i32 %idx + store i32 0, i32* %addr + %next = icmp sgt i32 %idx.dec, -1 + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} -- 2.34.1