summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Analysis')
-rw-r--r--llvm/lib/Analysis/CMakeLists.txt1
-rw-r--r--llvm/lib/Analysis/CmpInstAnalysis.cpp109
-rw-r--r--llvm/lib/Analysis/InstructionSimplify.cpp52
3 files changed, 131 insertions, 31 deletions
diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt
index 161709a4846..45268dd5c76 100644
--- a/llvm/lib/Analysis/CMakeLists.txt
+++ b/llvm/lib/Analysis/CMakeLists.txt
@@ -18,6 +18,7 @@ add_llvm_library(LLVMAnalysis
CallGraphSCCPass.cpp
CallPrinter.cpp
CaptureTracking.cpp
+ CmpInstAnalysis.cpp
CostModel.cpp
CodeMetrics.cpp
ConstantFolding.cpp
diff --git a/llvm/lib/Analysis/CmpInstAnalysis.cpp b/llvm/lib/Analysis/CmpInstAnalysis.cpp
new file mode 100644
index 00000000000..079811fe9a2
--- /dev/null
+++ b/llvm/lib/Analysis/CmpInstAnalysis.cpp
@@ -0,0 +1,109 @@
+//===- CmpInstAnalysis.cpp - Utils to help fold compares ---------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file holds routines to help analyse compare instructions
+// and fold them into constants or other compare instructions
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CmpInstAnalysis.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/PatternMatch.h"
+
+using namespace llvm;
+
+unsigned llvm::getICmpCode(const ICmpInst *ICI, bool InvertPred) {
+ ICmpInst::Predicate Pred = InvertPred ? ICI->getInversePredicate()
+ : ICI->getPredicate();
+ switch (Pred) {
+ // False -> 0
+ case ICmpInst::ICMP_UGT: return 1; // 001
+ case ICmpInst::ICMP_SGT: return 1; // 001
+ case ICmpInst::ICMP_EQ: return 2; // 010
+ case ICmpInst::ICMP_UGE: return 3; // 011
+ case ICmpInst::ICMP_SGE: return 3; // 011
+ case ICmpInst::ICMP_ULT: return 4; // 100
+ case ICmpInst::ICMP_SLT: return 4; // 100
+ case ICmpInst::ICMP_NE: return 5; // 101
+ case ICmpInst::ICMP_ULE: return 6; // 110
+ case ICmpInst::ICMP_SLE: return 6; // 110
+ // True -> 7
+ default:
+ llvm_unreachable("Invalid ICmp predicate!");
+ }
+}
+
+Value *llvm::getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS,
+ CmpInst::Predicate &NewICmpPred) {
+ switch (Code) {
+ default: llvm_unreachable("Illegal ICmp code!");
+ case 0: // False.
+ return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
+ case 1: NewICmpPred = Sign ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; break;
+ case 2: NewICmpPred = ICmpInst::ICMP_EQ; break;
+ case 3: NewICmpPred = Sign ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; break;
+ case 4: NewICmpPred = Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; break;
+ case 5: NewICmpPred = ICmpInst::ICMP_NE; break;
+ case 6: NewICmpPred = Sign ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; break;
+ case 7: // True.
+ return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1);
+ }
+ return nullptr;
+}
+
+bool llvm::PredicatesFoldable(ICmpInst::Predicate p1, ICmpInst::Predicate p2) {
+ return (CmpInst::isSigned(p1) == CmpInst::isSigned(p2)) ||
+ (CmpInst::isSigned(p1) && ICmpInst::isEquality(p2)) ||
+ (CmpInst::isSigned(p2) && ICmpInst::isEquality(p1));
+}
+
+bool llvm::decomposeBitTestICmp(Value *LHS, Value *RHS,
+ CmpInst::Predicate &Pred,
+ Value *&X, APInt &Mask) {
+ const APInt *C;
+ if (!match(RHS, PatternMatch::m_APInt(C)))
+ return false;
+
+ switch (Pred) {
+ default:
+ return false;
+ case ICmpInst::ICMP_SLT:
+ // X < 0 is equivalent to (X & SignMask) != 0.
+ if (!C->isNullValue())
+ return false;
+ Mask = APInt::getSignMask(C->getBitWidth());
+ Pred = ICmpInst::ICMP_NE;
+ break;
+ case ICmpInst::ICMP_SGT:
+ // X > -1 is equivalent to (X & SignMask) == 0.
+ if (!C->isAllOnesValue())
+ return false;
+ Mask = APInt::getSignMask(C->getBitWidth());
+ Pred = ICmpInst::ICMP_EQ;
+ break;
+ case ICmpInst::ICMP_ULT:
+ // X <u 2^n is equivalent to (X & ~(2^n-1)) == 0.
+ if (!C->isPowerOf2())
+ return false;
+ Mask = -*C;
+ Pred = ICmpInst::ICMP_EQ;
+ break;
+ case ICmpInst::ICMP_UGT:
+ // X >u 2^n-1 is equivalent to (X & ~(2^n-1)) != 0.
+ if (!(*C + 1).isPowerOf2())
+ return false;
+ Mask = ~*C;
+ Pred = ICmpInst::ICMP_NE;
+ break;
+ }
+
+ X = LHS;
+ return true;
+}
diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index 9729629b167..d155f6b4803 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -23,6 +23,7 @@
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/CmpInstAnalysis.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/MemoryBuiltins.h"
@@ -3620,32 +3621,29 @@ static Value *simplifySelectBitTest(Value *TrueVal, Value *FalseVal, Value *X,
/// An alternative way to test if a bit is set or not uses sgt/slt instead of
/// eq/ne.
-static Value *simplifySelectWithFakeICmpEq(Value *CmpLHS, Value *TrueVal,
- Value *FalseVal,
- bool TrueWhenUnset) {
+static Value *simplifySelectWithFakeICmpEq(Value *CmpLHS, Value *CmpRHS,
+ ICmpInst::Predicate Pred,
+ Value *TrueVal, Value *FalseVal) {
+ Value *X;
+ APInt Mask;
+ if (!decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask))
+ return nullptr;
+
unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();
if (!BitWidth)
return nullptr;
- APInt MinSignedValue;
- Value *X;
- if (match(CmpLHS, m_Trunc(m_Value(X))) && (X == TrueVal || X == FalseVal)) {
+ Value *ExtX;
+ if (match(X, m_Trunc(m_Value(ExtX))) &&
+ (ExtX == TrueVal || ExtX == FalseVal)) {
// icmp slt (trunc X), 0 <--> icmp ne (and X, C), 0
// icmp sgt (trunc X), -1 <--> icmp eq (and X, C), 0
- unsigned DestSize = CmpLHS->getType()->getScalarSizeInBits();
- MinSignedValue = APInt::getSignedMinValue(DestSize).zext(BitWidth);
- } else {
- // icmp slt X, 0 <--> icmp ne (and X, C), 0
- // icmp sgt X, -1 <--> icmp eq (and X, C), 0
- X = CmpLHS;
- MinSignedValue = APInt::getSignedMinValue(BitWidth);
+ X = ExtX;
+ Mask = Mask.zext(BitWidth);
}
- if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, X, &MinSignedValue,
- TrueWhenUnset))
- return V;
-
- return nullptr;
+ return simplifySelectBitTest(TrueVal, FalseVal, X, &Mask,
+ Pred == ICmpInst::ICMP_EQ);
}
/// Try to simplify a select instruction when its condition operand is an
@@ -3658,9 +3656,6 @@ static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
if (!match(CondVal, m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS))))
return nullptr;
- // FIXME: This code is nearly duplicated in InstCombine. Using/refactoring
- // decomposeBitTestICmp() might help.
- // FIXME this should support ICMP_SLE/SGE forms as well
if (ICmpInst::isEquality(Pred) && match(CmpRHS, m_Zero())) {
Value *X;
const APInt *Y;
@@ -3668,18 +3663,13 @@ static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
if (Value *V = simplifySelectBitTest(TrueVal, FalseVal, X, Y,
Pred == ICmpInst::ICMP_EQ))
return V;
- } else if (Pred == ICmpInst::ICMP_SLT && match(CmpRHS, m_Zero())) {
- // Comparing signed-less-than 0 checks if the sign bit is set.
- if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, TrueVal, FalseVal,
- false))
- return V;
- } else if (Pred == ICmpInst::ICMP_SGT && match(CmpRHS, m_AllOnes())) {
- // Comparing signed-greater-than -1 checks if the sign bit is not set.
- if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, TrueVal, FalseVal,
- true))
- return V;
}
+ // Check for other compares that behave like bit test.
+ if (Value *V = simplifySelectWithFakeICmpEq(CmpLHS, CmpRHS, Pred,
+ TrueVal, FalseVal))
+ return V;
+
if (CondVal->hasOneUse()) {
const APInt *C;
if (match(CmpRHS, m_APInt(C))) {
OpenPOWER on IntegriCloud