Index: include/llvm/Analysis/CmpInstAnalysis.h =================================================================== --- /dev/null +++ include/llvm/Analysis/CmpInstAnalysis.h @@ -0,0 +1,71 @@ +//===-- CmpInstAnalysis.h - Utils to help fold compare insts ----*- C++ -*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CMPINSTANALYSIS_H +#define LLVM_ANALYSIS_CMPINSTANALYSIS_H + +#include "llvm/IR/InstrTypes.h" + +namespace llvm { + class ICmpInst; + class Value; + + /// Encode a icmp predicate into a three bit mask. These bits are carefully + /// arranged to allow folding of expressions such as: + /// + /// (A < B) | (A > B) --> (A != B) + /// + /// Note that this is only valid if the first and second predicates have the + /// same sign. It is illegal to do: (A u< B) | (A s> B) + /// + /// Three bits are used to represent the condition, as follows: + /// 0 A > B + /// 1 A == B + /// 2 A < B + /// + /// <=> Value Definition + /// 000 0 Always false + /// 001 1 A > B + /// 010 2 A == B + /// 011 3 A >= B + /// 100 4 A < B + /// 101 5 A != B + /// 110 6 A <= B + /// 111 7 Always true + /// + unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred = false); + + /// This is the complement of getICmpCode, which turns an opcode and two + /// operands into either a constant true or false, or the predicate for a new + /// ICmp instruction. The sign is passed in to determine which kind of + /// predicate to use in the new icmp instruction. + /// Non-NULL return value will be a true or false constant. + /// NULL return means a new ICmp is needed. The predicate for which is output + /// in NewICmpPred. + Value *getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, + CmpInst::Predicate &NewICmpPred); + + /// Return true if both predicates match sign or if at least one of them is an + /// equality comparison (which is signless). + bool PredicatesFoldable(CmpInst::Predicate p1, CmpInst::Predicate p2); + + /// Decompose an icmp into the form ((X & Mask) pred 0) if possible. The + /// returned predicate is either == or !=. Returns false if decomposition + /// fails. + bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred, + Value *&X, APInt &Mask); + +} // end namespace llvm + +#endif Index: include/llvm/Transforms/Utils/CmpInstAnalysis.h =================================================================== --- include/llvm/Transforms/Utils/CmpInstAnalysis.h +++ /dev/null @@ -1,70 +0,0 @@ -//===-- CmpInstAnalysis.h - Utils to help fold compare insts ----*- C++ -*-===// -// -// 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 -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TRANSFORMS_UTILS_CMPINSTANALYSIS_H -#define LLVM_TRANSFORMS_UTILS_CMPINSTANALYSIS_H - -#include "llvm/IR/InstrTypes.h" - -namespace llvm { - class ICmpInst; - class Value; - - /// Encode a icmp predicate into a three bit mask. These bits are carefully - /// arranged to allow folding of expressions such as: - /// - /// (A < B) | (A > B) --> (A != B) - /// - /// Note that this is only valid if the first and second predicates have the - /// same sign. It is illegal to do: (A u< B) | (A s> B) - /// - /// Three bits are used to represent the condition, as follows: - /// 0 A > B - /// 1 A == B - /// 2 A < B - /// - /// <=> Value Definition - /// 000 0 Always false - /// 001 1 A > B - /// 010 2 A == B - /// 011 3 A >= B - /// 100 4 A < B - /// 101 5 A != B - /// 110 6 A <= B - /// 111 7 Always true - /// - unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred = false); - - /// This is the complement of getICmpCode, which turns an opcode and two - /// operands into either a constant true or false, or the predicate for a new - /// ICmp instruction. The sign is passed in to determine which kind of - /// predicate to use in the new icmp instruction. - /// Non-NULL return value will be a true or false constant. - /// NULL return means a new ICmp is needed. The predicate for which is output - /// in NewICmpPred. - Value *getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, - CmpInst::Predicate &NewICmpPred); - - /// Return true if both predicates match sign or if at least one of them is an - /// equality comparison (which is signless). - bool PredicatesFoldable(CmpInst::Predicate p1, CmpInst::Predicate p2); - - /// Decompose an icmp into the form ((X & Y) pred Z) if possible. The returned - /// predicate is either == or !=. Returns false if decomposition fails. - bool decomposeBitTestICmp(const ICmpInst *I, CmpInst::Predicate &Pred, - Value *&X, Value *&Y, Value *&Z); - -} // end namespace llvm - -#endif Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -18,6 +18,7 @@ CallGraphSCCPass.cpp CallPrinter.cpp CaptureTracking.cpp + CmpInstAnalysis.cpp CostModel.cpp CodeMetrics.cpp ConstantFolding.cpp Index: lib/Analysis/CmpInstAnalysis.cpp =================================================================== --- /dev/null +++ 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 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; +} Index: lib/Analysis/InstructionSimplify.cpp =================================================================== --- lib/Analysis/InstructionSimplify.cpp +++ 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 @@ /// 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 @@ 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 @@ 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))) { Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -12,11 +12,11 @@ //===----------------------------------------------------------------------===// #include "InstCombineInternal.h" +#include "llvm/Analysis/CmpInstAnalysis.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/PatternMatch.h" -#include "llvm/Transforms/Utils/CmpInstAnalysis.h" #include "llvm/Transforms/Utils/Local.h" using namespace llvm; using namespace PatternMatch; @@ -292,6 +292,18 @@ return NewMask; } +// Adapts the external decomposeBitTestICmp for local use. +static bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred, + Value *&X, Value *&Y, Value *&Z) { + APInt Mask; + if (!llvm::decomposeBitTestICmp(LHS, RHS, Pred, X, Mask)) + return false; + + Y = ConstantInt::get(LHS->getType(), Mask); + Z = ConstantInt::get(RHS->getType(), 0); + return true; +} + /// Handle (icmp(A & B) ==/!= C) &/| (icmp(A & D) ==/!= E). /// Return the set of pattern classes (from MaskedICmpType) that both LHS and /// RHS satisfy. @@ -316,7 +328,7 @@ Value *L2 = LHS->getOperand(1); Value *L11, *L12, *L21, *L22; // Check whether the icmp can be decomposed into a bit test. - if (decomposeBitTestICmp(LHS, PredL, L11, L12, L2)) { + if (decomposeBitTestICmp(L1, L2, PredL, L11, L12, L2)) { L21 = L22 = L1 = nullptr; } else { // Look for ANDs in the LHS icmp. @@ -347,7 +359,7 @@ Value *R2 = RHS->getOperand(1); Value *R11, *R12; bool Ok = false; - if (decomposeBitTestICmp(RHS, PredR, R11, R12, R2)) { + if (decomposeBitTestICmp(R1, R2, PredR, R11, R12, R2)) { if (R11 == L11 || R11 == L12 || R11 == L21 || R11 == L22) { A = R11; D = R12; Index: lib/Transforms/Utils/CMakeLists.txt =================================================================== --- lib/Transforms/Utils/CMakeLists.txt +++ lib/Transforms/Utils/CMakeLists.txt @@ -7,7 +7,6 @@ BypassSlowDivision.cpp CloneFunction.cpp CloneModule.cpp - CmpInstAnalysis.cpp CodeExtractor.cpp CtorUtils.cpp DemoteRegToStack.cpp Index: lib/Transforms/Utils/CmpInstAnalysis.cpp =================================================================== --- lib/Transforms/Utils/CmpInstAnalysis.cpp +++ /dev/null @@ -1,108 +0,0 @@ -//===- 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/Transforms/Utils/CmpInstAnalysis.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/Instructions.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(const ICmpInst *I, CmpInst::Predicate &Pred, - Value *&X, Value *&Y, Value *&Z) { - ConstantInt *C = dyn_cast(I->getOperand(1)); - if (!C) - return false; - - switch (I->getPredicate()) { - default: - return false; - case ICmpInst::ICMP_SLT: - // X < 0 is equivalent to (X & SignMask) != 0. - if (!C->isZero()) - return false; - Y = ConstantInt::get(I->getContext(), APInt::getSignMask(C->getBitWidth())); - Pred = ICmpInst::ICMP_NE; - break; - case ICmpInst::ICMP_SGT: - // X > -1 is equivalent to (X & SignMask) == 0. - if (!C->isMinusOne()) - return false; - Y = ConstantInt::get(I->getContext(), APInt::getSignMask(C->getBitWidth())); - Pred = ICmpInst::ICMP_EQ; - break; - case ICmpInst::ICMP_ULT: - // X getValue().isPowerOf2()) - return false; - Y = ConstantInt::get(I->getContext(), -C->getValue()); - Pred = ICmpInst::ICMP_EQ; - break; - case ICmpInst::ICMP_UGT: - // X >u 2^n-1 is equivalent to (X & ~(2^n-1)) != 0. - if (!(C->getValue() + 1).isPowerOf2()) - return false; - Y = ConstantInt::get(I->getContext(), ~C->getValue()); - Pred = ICmpInst::ICMP_NE; - break; - } - - X = I->getOperand(0); - Z = ConstantInt::getNullValue(C->getType()); - return true; -}