Index: llvm/include/llvm/ADT/APInt.h =================================================================== --- llvm/include/llvm/ADT/APInt.h +++ llvm/include/llvm/ADT/APInt.h @@ -15,6 +15,7 @@ #ifndef LLVM_ADT_APINT_H #define LLVM_ADT_APINT_H +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" #include @@ -96,7 +97,7 @@ unsigned BitWidth; ///< The number of bits in this APInt. - friend struct DenseMapAPIntKeyInfo; + friend struct DenseMapInfo; friend class APSInt; @@ -2288,6 +2289,29 @@ /// from Src into IntVal, which is assumed to be wide enough and to hold zero. void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes); +/// Provide DenseMapInfo for APInt. +template <> struct DenseMapInfo { + static inline APInt getEmptyKey() { + APInt V(nullptr, 0); + V.U.VAL = 0; + return V; + } + + static inline APInt getTombstoneKey() { + APInt V(nullptr, 0); + V.U.VAL = 1; + return V; + } + + static unsigned getHashValue(const APInt &Key) { + return static_cast(hash_value(Key)); + } + + static bool isEqual(const APInt &LHS, const APInt &RHS) { + return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS; + } +}; + } // namespace llvm #endif Index: llvm/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/include/llvm/Transforms/IPO/Attributor.h +++ llvm/include/llvm/Transforms/IPO/Attributor.h @@ -97,6 +97,7 @@ #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/STLExtras.h" @@ -115,6 +116,7 @@ #include "llvm/IR/PassManager.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/DOTGraphTraits.h" #include "llvm/Support/GraphWriter.h" #include "llvm/Support/TimeProfiler.h" @@ -3348,6 +3350,191 @@ static const char ID; }; +/// A class for a set state. +/// The assumed boolean state indicates whether the corresponding set is full +/// set or not. If the assumed state is false, this is the worst state. The +/// worst state (invalid state) of set of potential values is when the set +/// contains every possible value (i.e. we cannot in any way limit the value +/// that the target position can take). That never happens naturally, we only +/// force it. As for the conditions under which we force it, see +/// AAPotentialValues. +template > +struct PotentialValuesState : BooleanState { + using SetTy = DenseSet; + + PotentialValuesState() : BooleanState(true) {} + + PotentialValuesState(bool IsValid) : BooleanState(IsValid) {} + + /// Return this set. We should check whether this set is valid or not by + /// isValidState() before calling this function. + const SetTy &getAssumedSet() const { + assert(isValidState() && "This set shoud not be used when it is invalid!"); + return Set; + } + + bool operator==(const PotentialValuesState &RHS) const { + if (isValidState() != RHS.isValidState()) + return false; + if (!isValidState() && !RHS.isValidState()) + return true; + return Set == RHS.getAssumedSet(); + } + + /// Maximum number of potential values to be tracked. + /// This is set by -attributor-max-potential-values command line option + static unsigned MaxPotentialValues; + + /// Return empty set as the best state of potential values. + static PotentialValuesState getBestState() { + return PotentialValuesState(true); + } + + static PotentialValuesState getBestState(PotentialValuesState &PVS) { + return getBestState(); + } + + /// Return full set as the worst state of potential values. + static PotentialValuesState getWorstState() { + return PotentialValuesState(false); + } + + /// Union assumed set with the passed value. + void unionAssumed(const MemberTy &C) { insert(C); } + + /// Union assumed set with assumed set of the passed state \p PVS. + void unionAssumed(const PotentialValuesState &PVS) { unionWith(PVS); } + + /// "Clamp" this state with \p PVS. + PotentialValuesState operator^=(const PotentialValuesState &PVS) { + unionAssumed(PVS); + return *this; + } + + PotentialValuesState operator&=(const PotentialValuesState &PVS) { + unionAssumed(PVS); + return *this; + } + +private: + /// Check the size of this set, and invalidate when the size is no + /// less than \p MaxPotentialValues threshold. + void checkAndInvalidate() { + if (Set.size() >= MaxPotentialValues) + indicatePessimisticFixpoint(); + } + + /// Insert an element into this set. + void insert(const MemberTy &C) { + if (!isValidState()) + return; + Set.insert(C); + checkAndInvalidate(); + } + + /// Take union with R. + void unionWith(const PotentialValuesState &R) { + /// If this is a full set, do nothing.; + if (!isValidState()) + return; + /// If R is full set, change L to a full set. + if (!R.isValidState()) { + indicatePessimisticFixpoint(); + return; + } + for (const MemberTy &C : R.Set) + Set.insert(C); + checkAndInvalidate(); + } + + /// Take intersection with R. + void intersectWith(const PotentialValuesState &R) { + /// If R is a full set, do nothing. + if (!R.isValidState()) + return; + /// If this is a full set, change this to R. + if (!isValidState()) { + *this = R; + return; + } + SetTy IntersectSet; + for (const MemberTy &C : Set) { + if (R.Set.count(C)) + IntersectSet.insert(C); + } + Set = IntersectSet; + } + + /// Container for potential values + SetTy Set; +}; + +using PotentialConstantIntValuesState = PotentialValuesState; + +raw_ostream &operator<<(raw_ostream &OS, + const PotentialConstantIntValuesState &R); + +/// An abstract interface for potential values analysis. +/// +/// This AA collects potential values for each IR position. +/// An assumed set of potential values is initialized with the empty set (the +/// best state) and it will grow monotonically as we find more potential values +/// for this position. +/// The set might be forced to the worst state, that is, to contain every +/// possible value for this position in 2 cases. +/// 1. We surpassed the \p MaxPotentialValues threshold. This includes the +/// case that this position is affected (e.g. because of an operation) by a +/// Value that is in the worst state. +/// 2. We tried to initialize on a Value that we cannot handle (e.g. an +/// operator we do not currently handle). +/// +/// TODO: Support values other than constant integers. +struct AAPotentialValues + : public StateWrapper { + using Base = StateWrapper; + AAPotentialValues(const IRPosition &IRP, Attributor &A) : Base(IRP) {} + + /// See AbstractAttribute::getState(...). + PotentialConstantIntValuesState &getState() override { return *this; } + const PotentialConstantIntValuesState &getState() const override { + return *this; + } + + /// Create an abstract attribute view for the position \p IRP. + static AAPotentialValues &createForPosition(const IRPosition &IRP, + Attributor &A); + + /// Return assumed constant for the associated value + Optional + getAssumedConstantInt(Attributor &A, + const Instruction *CtxI = nullptr) const { + if (!isValidState()) + return nullptr; + if (getAssumedSet().size() == 1) + return cast(ConstantInt::get(getAssociatedValue().getType(), + *(getAssumedSet().begin()))); + if (getAssumedSet().size() == 0) + return llvm::None; + + return nullptr; + } + + /// See AbstractAttribute::getName() + const std::string getName() const override { return "AAPotentialValues"; } + + /// See AbstractAttribute::getIdAddr() + const char *getIdAddr() const override { return &ID; } + + /// This function should return true if the type of the \p AA is + /// AAPotentialValues + static bool classof(const AbstractAttribute *AA) { + return (AA->getIdAddr() == &ID); + } + + /// Unique ID (due to the unique address) + static const char ID; +}; + /// Run options, used by the pass manager. enum AttributorRunOption { NONE = 0, Index: llvm/lib/IR/LLVMContextImpl.h =================================================================== --- llvm/lib/IR/LLVMContextImpl.h +++ llvm/lib/IR/LLVMContextImpl.h @@ -57,27 +57,7 @@ class Value; class ValueHandleBase; -struct DenseMapAPIntKeyInfo { - static inline APInt getEmptyKey() { - APInt V(nullptr, 0); - V.U.VAL = 0; - return V; - } - - static inline APInt getTombstoneKey() { - APInt V(nullptr, 0); - V.U.VAL = 1; - return V; - } - - static unsigned getHashValue(const APInt &Key) { - return static_cast(hash_value(Key)); - } - - static bool isEqual(const APInt &LHS, const APInt &RHS) { - return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS; - } -}; +using DenseMapAPIntKeyInfo = DenseMapInfo; struct DenseMapAPFloatKeyInfo { static inline APFloat getEmptyKey() { return APFloat(APFloat::Bogus(), 1); } Index: llvm/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/lib/Transforms/IPO/Attributor.cpp +++ llvm/lib/Transforms/IPO/Attributor.cpp @@ -2079,6 +2079,19 @@ return OS; } +raw_ostream &llvm::operator<<(raw_ostream &OS, + const PotentialConstantIntValuesState &S) { + OS << "set-state(< {"; + if (!S.isValidState()) + OS << "full-set"; + else + for (auto &it : S.getAssumedSet()) + OS << it << ", "; + OS << "} >)"; + + return OS; +} + void AbstractAttribute::print(raw_ostream &OS) const { OS << "["; OS << getName(); Index: llvm/lib/Transforms/IPO/AttributorAttributes.cpp =================================================================== --- llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -45,6 +45,16 @@ static cl::opt MaxHeapToStackSize("max-heap-to-stack-size", cl::init(128), cl::Hidden); +static cl::opt MaxPotentialValues( + "attributor-max-potential-values", cl::Hidden, + cl::desc("Maximum number of potential values to be " + "tracked for each position."), + cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues), + cl::init(7)); + +template <> +unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0; + STATISTIC(NumAAs, "Number of abstract attributes created"); // Some helper macros to deal with statistics tracking. @@ -120,6 +130,7 @@ PIPE_OPERATOR(AAValueConstantRange) PIPE_OPERATOR(AAPrivatizablePtr) PIPE_OPERATOR(AAUndefinedBehavior) +PIPE_OPERATOR(AAPotentialValues) #undef PIPE_OPERATOR } // namespace llvm @@ -7075,6 +7086,155 @@ STATS_DECLTRACK_CSARG_ATTR(value_range) } }; + +/// ------------------ Potential Values Attribute ------------------------- + +struct AAPotentialValuesImpl : AAPotentialValues { + using StateType = PotentialConstantIntValuesState; + + AAPotentialValuesImpl(const IRPosition &IRP, Attributor &A) + : AAPotentialValues(IRP, A) {} + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + std::string Str; + llvm::raw_string_ostream OS(Str); + OS << getState(); + return OS.str(); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + return indicatePessimisticFixpoint(); + } +}; + +struct AAPotentialValuesArgument final + : AAArgumentFromCallSiteArguments { + using Base = + AAArgumentFromCallSiteArguments; + AAPotentialValuesArgument(const IRPosition &IRP, Attributor &A) + : Base(IRP, A) {} + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + if (!getAnchorScope() || getAnchorScope()->isDeclaration()) { + indicatePessimisticFixpoint(); + } else { + Base::initialize(A); + } + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_ARG_ATTR(potential_values) + } +}; + +struct AAPotentialValuesReturned + : AAReturnedFromReturnedValues { + using Base = + AAReturnedFromReturnedValues; + AAPotentialValuesReturned(const IRPosition &IRP, Attributor &A) + : Base(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FNRET_ATTR(potential_values) + } +}; + +struct AAPotentialValuesFloating : AAPotentialValuesImpl { + AAPotentialValuesFloating(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesImpl(IRP, A) {} + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + Value &V = getAssociatedValue(); + + if (auto *C = dyn_cast(&V)) { + unionAssumed(C->getValue()); + indicateOptimisticFixpoint(); + return; + } + + if (isa(&V)) { + // Collapse the undef state to 0. + unionAssumed( + APInt(/* numBits */ getAssociatedType()->getIntegerBitWidth(), + /* val */ 0)); + indicateOptimisticFixpoint(); + return; + } + + if (isa(&V) || isa(&V) || isa(&V)) + return; + + if (isa(V) || isa(V)) + return; + + indicatePessimisticFixpoint(); + + LLVM_DEBUG(dbgs() << "[AAPotentialValues] We give up: " + << getAssociatedValue() << "\n"); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FLOATING_ATTR(potential_values) + } +}; + +struct AAPotentialValuesFunction : AAPotentialValuesImpl { + AAPotentialValuesFunction(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesImpl(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + ChangeStatus updateImpl(Attributor &A) override { + llvm_unreachable("AAPotentialValues(Function|CallSite)::updateImpl will " + "not be called"); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FN_ATTR(potential_values) + } +}; + +struct AAPotentialValuesCallSite : AAPotentialValuesFunction { + AAPotentialValuesCallSite(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesFunction(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CS_ATTR(potential_values) + } +}; + +struct AAPotentialValuesCallSiteReturned + : AACallSiteReturnedFromReturned { + AAPotentialValuesCallSiteReturned(const IRPosition &IRP, Attributor &A) + : AACallSiteReturnedFromReturned(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CSRET_ATTR(potential_values) + } +}; + +struct AAPotentialValuesCallSiteArgument : AAPotentialValuesFloating { + AAPotentialValuesCallSiteArgument(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesFloating(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CSARG_ATTR(potential_values) + } +}; + } // namespace const char AAReturnedValues::ID = 0; @@ -7098,6 +7258,7 @@ const char AAMemoryBehavior::ID = 0; const char AAMemoryLocation::ID = 0; const char AAValueConstantRange::ID = 0; +const char AAPotentialValues::ID = 0; // Macro magic to create the static generator function for attributes that // follow the naming scheme. @@ -7207,6 +7368,7 @@ CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAlign) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoCapture) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueConstantRange) +CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAPotentialValues) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) Index: llvm/test/Transforms/Attributor/potential.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/Attributor/potential.ll @@ -0,0 +1,394 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes +; RUN: opt -attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=9 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM +; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=7 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM +; RUN: opt -attributor-cgscc -attributor-manifest-internal -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_NPM,IS__CGSCC____,IS________OPM,IS__CGSCC_OPM +; RUN: opt -aa-pipeline=basic-aa -passes=attributor-cgscc -attributor-manifest-internal -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_OPM,IS__CGSCC____,IS________NPM,IS__CGSCC_NPM +; +; Test for multiple potential values +; +; potential-test 1 +; bool iszero(int c) { return c == 0; } +; bool potential_test1(bool c) { return iszero(c ? 1 : -1); } + +define internal i1 @iszero1(i32 %c) { +; CHECK-LABEL: define {{[^@]+}}@iszero1 +; CHECK-SAME: (i32 [[C:%.*]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[C]], 0 +; CHECK-NEXT: ret i1 [[CMP]] +; + %cmp = icmp eq i32 %c, 0 + ret i1 %cmp +} + +define i1 @potential_test1(i1 %c) { +; CHECK-LABEL: define {{[^@]+}}@potential_test1 +; CHECK-SAME: (i1 [[C:%.*]]) +; CHECK-NEXT: [[ARG:%.*]] = select i1 [[C]], i32 -1, i32 1 +; CHECK-NEXT: [[RET:%.*]] = call i1 @iszero1(i32 [[ARG]]) +; CHECK-NEXT: ret i1 [[RET]] +; + %arg = select i1 %c, i32 -1, i32 1 + %ret = call i1 @iszero1(i32 %arg) + ret i1 %ret +} + + +; potential-test 2 +; +; potential values of argument of iszero are {1,-1} +; potential value of returned value of iszero is 0 +; +; int call_with_two_values(int x) { return iszero(x) + iszero(-x); } +; int potential_test2(int x) { return call_with_two_values(1) + call_with_two_values(-1); } + +define internal i32 @iszero2(i32 %c) { +; CHECK-LABEL: define {{[^@]+}}@iszero2 +; CHECK-SAME: (i32 [[C:%.*]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[C]], 0 +; CHECK-NEXT: [[RET:%.*]] = zext i1 [[CMP]] to i32 +; CHECK-NEXT: ret i32 [[RET]] +; + %cmp = icmp eq i32 %c, 0 + %ret = zext i1 %cmp to i32 + ret i32 %ret +} + +define internal i32 @call_with_two_values(i32 %c) { +; IS__TUNIT____-LABEL: define {{[^@]+}}@call_with_two_values +; IS__TUNIT____-SAME: (i32 [[C:%.*]]) +; IS__TUNIT____-NEXT: [[CSRET1:%.*]] = call i32 @iszero2(i32 [[C]]) #0, !range !0 +; IS__TUNIT____-NEXT: [[MINUSC:%.*]] = sub i32 0, [[C]] +; IS__TUNIT____-NEXT: [[CSRET2:%.*]] = call i32 @iszero2(i32 [[MINUSC]]) #0, !range !0 +; IS__TUNIT____-NEXT: [[RET:%.*]] = add i32 [[CSRET1]], [[CSRET2]] +; IS__TUNIT____-NEXT: ret i32 [[RET]] +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@call_with_two_values +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @iszero2(i32 [[C]]) +; IS__CGSCC____-NEXT: [[MINUSC:%.*]] = sub i32 0, [[C]] +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @iszero2(i32 [[MINUSC]]) +; IS__CGSCC____-NEXT: [[RET:%.*]] = add i32 [[CSRET1]], [[CSRET2]] +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %csret1 = call i32 @iszero2(i32 %c) + %minusc = sub i32 0, %c + %csret2 = call i32 @iszero2(i32 %minusc) + %ret = add i32 %csret1, %csret2 + ret i32 %ret +} + +define i32 @potential_test2(i1 %c) { +; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test2 +; IS__TUNIT____-SAME: (i1 [[C:%.*]]) +; IS__TUNIT____-NEXT: [[CSRET1:%.*]] = call i32 @call_with_two_values(i32 1) #0, !range !1 +; IS__TUNIT____-NEXT: [[CSRET2:%.*]] = call i32 @call_with_two_values(i32 -1) #1, !range !1 +; IS__TUNIT____-NEXT: [[RET:%.*]] = add i32 [[CSRET1]], [[CSRET2]] +; IS__TUNIT____-NEXT: ret i32 [[RET]] +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test2 +; IS__CGSCC____-SAME: (i1 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @call_with_two_values(i32 1) +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @call_with_two_values(i32 -1) +; IS__CGSCC____-NEXT: [[RET:%.*]] = add i32 [[CSRET1]], [[CSRET2]] +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %csret1 = call i32 @call_with_two_values(i32 1) + %csret2 = call i32 @call_with_two_values(i32 -1) + %ret = add i32 %csret1, %csret2 + ret i32 %ret +} + + +; potential-test 3 +; +; potential values of returned value of f are {0,1} +; potential values of argument of g are {0,1} +; potential value of returned value of g is 1 +; then returned value of g can be simplified +; +; int zero_or_one(int c) { return c < 2; } +; int potential_test3() { return zero_or_one(iszero(0))+zero_or_one(iszero(1)); } + +define internal i32 @iszero3(i32 %c) { +; CHECK-LABEL: define {{[^@]+}}@iszero3 +; CHECK-SAME: (i32 [[C:%.*]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[C]], 0 +; CHECK-NEXT: [[RET:%.*]] = zext i1 [[CMP]] to i32 +; CHECK-NEXT: ret i32 [[RET]] +; + %cmp = icmp eq i32 %c, 0 + %ret = zext i1 %cmp to i32 + ret i32 %ret +} + +define internal i32 @less_than_two(i32 %c) { +; CHECK-LABEL: define {{[^@]+}}@less_than_two +; CHECK-SAME: (i32 [[C:%.*]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[C]], 2 +; CHECK-NEXT: [[RET:%.*]] = zext i1 [[CMP]] to i32 +; CHECK-NEXT: ret i32 [[RET]] +; + %cmp = icmp slt i32 %c, 2 + %ret = zext i1 %cmp to i32 + ret i32 %ret +} + +define i32 @potential_test3() { +; NOT_TUNIT_NPM-LABEL: define {{[^@]+}}@potential_test3() +; NOT_TUNIT_NPM-NEXT: [[CMP1:%.*]] = call i32 @iszero3(i32 0) +; NOT_TUNIT_NPM-NEXT: [[TRUE1:%.*]] = call i32 @less_than_two(i32 [[CMP1]]) +; NOT_TUNIT_NPM-NEXT: [[CMP2:%.*]] = call i32 @iszero3(i32 1) +; NOT_TUNIT_NPM-NEXT: [[TRUE2:%.*]] = call i32 @less_than_two(i32 [[CMP2]]) +; NOT_TUNIT_NPM-NEXT: [[RET:%.*]] = add i32 [[TRUE1]], [[TRUE2]] +; NOT_TUNIT_NPM-NEXT: ret i32 [[RET]] +; +; IS__TUNIT_NPM-LABEL: define {{[^@]+}}@potential_test3() +; IS__TUNIT_NPM-NEXT: [[CMP1:%.*]] = call i32 @iszero3(i32 0) #0, !range !0 +; IS__TUNIT_NPM-NEXT: [[TRUE1:%.*]] = call i32 @less_than_two(i32 [[CMP1]]) #0, !range !0 +; IS__TUNIT_NPM-NEXT: [[CMP2:%.*]] = call i32 @iszero3(i32 1) #0, !range !0 +; IS__TUNIT_NPM-NEXT: [[TRUE2:%.*]] = call i32 @less_than_two(i32 [[CMP2]]) #0, !range !0 +; IS__TUNIT_NPM-NEXT: [[RET:%.*]] = add i32 [[TRUE1]], [[TRUE2]] +; IS__TUNIT_NPM-NEXT: ret i32 [[RET]] +; + %cmp1 = call i32 @iszero3(i32 0) + %true1 = call i32 @less_than_two(i32 %cmp1) + %cmp2 = call i32 @iszero3(i32 1) + %true2 = call i32 @less_than_two(i32 %cmp2) + %ret = add i32 %true1, %true2 + ret i32 %ret +} + + +; potential-test 4,5 +; +; simplified +; int potential_test4(int c) { return return1or3(c) == 2; } +; int potential_test5(int c) { return return1or3(c) == return2or4(c); } +; +; not simplified +; int potential_test6(int c) { return return1or3(c) == 3; } +; int potential_test7(int c) { return return1or3(c) == return3or4(c); } + +define i32 @potential_test4(i32 %c) { +; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test4 +; IS__TUNIT____-SAME: (i32 [[C:%.*]]) +; IS__TUNIT____-NEXT: [[CSRET:%.*]] = call i32 @return1or3(i32 [[C]]) #0, !range !2 +; IS__TUNIT____-NEXT: [[FALSE:%.*]] = icmp eq i32 [[CSRET]], 2 +; IS__TUNIT____-NEXT: [[RET:%.*]] = zext i1 [[FALSE]] to i32 +; IS__TUNIT____-NEXT: ret i32 [[RET]] +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test4 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET:%.*]] = call i32 @return1or3(i32 [[C]]) +; IS__CGSCC____-NEXT: [[FALSE:%.*]] = icmp eq i32 [[CSRET]], 2 +; IS__CGSCC____-NEXT: [[RET:%.*]] = zext i1 [[FALSE]] to i32 +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %csret = call i32 @return1or3(i32 %c) + %false = icmp eq i32 %csret, 2 + %ret = zext i1 %false to i32 + ret i32 %ret +} + +define i32 @potential_test5(i32 %c) { +; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test5 +; IS__TUNIT____-SAME: (i32 [[C:%.*]]) +; IS__TUNIT____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) #0, !range !2 +; IS__TUNIT____-NEXT: [[CSRET2:%.*]] = call i32 @return2or4(i32 [[C]]) #0, !range !3 +; IS__TUNIT____-NEXT: [[FALSE:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]] +; IS__TUNIT____-NEXT: [[RET:%.*]] = zext i1 [[FALSE]] to i32 +; IS__TUNIT____-NEXT: ret i32 [[RET]] +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test5 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @return2or4(i32 [[C]]) +; IS__CGSCC____-NEXT: [[FALSE:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]] +; IS__CGSCC____-NEXT: [[RET:%.*]] = zext i1 [[FALSE]] to i32 +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %csret1 = call i32 @return1or3(i32 %c) + %csret2 = call i32 @return2or4(i32 %c) + %false = icmp eq i32 %csret1, %csret2 + %ret = zext i1 %false to i32 + ret i32 %ret +} + +define i1 @potential_test6(i32 %c) { +; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test6 +; IS__TUNIT____-SAME: (i32 [[C:%.*]]) +; IS__TUNIT____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) #0, !range !2 +; IS__TUNIT____-NEXT: [[RET:%.*]] = icmp eq i32 [[CSRET1]], 3 +; IS__TUNIT____-NEXT: ret i1 [[RET]] +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test6 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) +; IS__CGSCC____-NEXT: [[RET:%.*]] = icmp eq i32 [[CSRET1]], 3 +; IS__CGSCC____-NEXT: ret i1 [[RET]] +; + %csret1 = call i32 @return1or3(i32 %c) + %ret = icmp eq i32 %csret1, 3 + ret i1 %ret +} + +define i1 @potential_test7(i32 %c) { +; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test7 +; IS__TUNIT____-SAME: (i32 [[C:%.*]]) +; IS__TUNIT____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) #0, !range !2 +; IS__TUNIT____-NEXT: [[CSRET2:%.*]] = call i32 @return3or4(i32 [[C]]) #0, !range !4 +; IS__TUNIT____-NEXT: [[RET:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]] +; IS__TUNIT____-NEXT: ret i1 [[RET]] +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test7 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @return3or4(i32 [[C]]) +; IS__CGSCC____-NEXT: [[RET:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]] +; IS__CGSCC____-NEXT: ret i1 [[RET]] +; + %csret1 = call i32 @return1or3(i32 %c) + %csret2 = call i32 @return3or4(i32 %c) + %ret = icmp eq i32 %csret1, %csret2 + ret i1 %ret +} + +define internal i32 @return1or3(i32 %c) { +; CHECK-LABEL: define {{[^@]+}}@return1or3 +; CHECK-SAME: (i32 [[C:%.*]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[C]], 0 +; CHECK-NEXT: [[RET:%.*]] = select i1 [[CMP]], i32 1, i32 3 +; CHECK-NEXT: ret i32 [[RET]] +; + %cmp = icmp eq i32 %c, 0 + %ret = select i1 %cmp, i32 1, i32 3 + ret i32 %ret +} + +define internal i32 @return2or4(i32 %c) { +; CHECK-LABEL: define {{[^@]+}}@return2or4 +; CHECK-SAME: (i32 [[C:%.*]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[C]], 0 +; CHECK-NEXT: [[RET:%.*]] = select i1 [[CMP]], i32 2, i32 4 +; CHECK-NEXT: ret i32 [[RET]] +; + %cmp = icmp eq i32 %c, 0 + %ret = select i1 %cmp, i32 2, i32 4 + ret i32 %ret +} + +define internal i32 @return3or4(i32 %c) { +; CHECK-LABEL: define {{[^@]+}}@return3or4 +; CHECK-SAME: (i32 [[C:%.*]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[C]], 0 +; CHECK-NEXT: [[RET:%.*]] = select i1 [[CMP]], i32 3, i32 4 +; CHECK-NEXT: ret i32 [[RET]] +; + %cmp = icmp eq i32 %c, 0 + %ret = select i1 %cmp, i32 3, i32 4 + ret i32 %ret +} + +; potential-test 8 +; +; propagate argument to callsite argument + +define internal i1 @cmp_with_four(i32 %c) { +; CHECK-LABEL: define {{[^@]+}}@cmp_with_four +; CHECK-SAME: (i32 [[C:%.*]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[C]], 4 +; CHECK-NEXT: ret i1 [[CMP]] +; + %cmp = icmp eq i32 %c, 4 + ret i1 %cmp +} + +define internal i1 @wrapper(i32 %c) { +; CHECK-LABEL: define {{[^@]+}}@wrapper +; CHECK-SAME: (i32 [[C:%.*]]) +; CHECK-NEXT: [[RET:%.*]] = call i1 @cmp_with_four(i32 [[C]]) +; CHECK-NEXT: ret i1 [[RET]] +; + %ret = call i1 @cmp_with_four(i32 %c) + ret i1 %ret +} + +define i1 @potential_test8() { +; CHECK-LABEL: define {{[^@]+}}@potential_test8() +; CHECK-NEXT: [[RES1:%.*]] = call i1 @wrapper(i32 1) +; CHECK-NEXT: [[RES3:%.*]] = call i1 @wrapper(i32 3) +; CHECK-NEXT: [[RES5:%.*]] = call i1 @wrapper(i32 5) +; CHECK-NEXT: [[RES13:%.*]] = or i1 [[RES1]], [[RES3]] +; CHECK-NEXT: [[RES135:%.*]] = or i1 [[RES13]], [[RES5]] +; CHECK-NEXT: ret i1 [[RES135]] +; + %res1 = call i1 @wrapper(i32 1) + %res3 = call i1 @wrapper(i32 3) + %res5 = call i1 @wrapper(i32 5) + %res13 = or i1 %res1, %res3 + %res135 = or i1 %res13, %res5 + ret i1 %res135 +} + +define i1 @potential_test9() { +; IS________OPM-LABEL: define {{[^@]+}}@potential_test9() +; IS________OPM-NEXT: entry: +; IS________OPM-NEXT: br label [[COND:%.*]] +; IS________OPM: cond: +; IS________OPM-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_1:%.*]], [[INC:%.*]] ] +; IS________OPM-NEXT: [[C_0:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ [[C_1:%.*]], [[INC]] ] +; IS________OPM-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_0]], 10 +; IS________OPM-NEXT: br i1 [[CMP]], label [[BODY:%.*]], label [[END:%.*]] +; IS________OPM: body: +; IS________OPM-NEXT: [[C_1]] = mul i32 [[C_0]], -1 +; IS________OPM-NEXT: br label [[INC]] +; IS________OPM: inc: +; IS________OPM-NEXT: [[I_1]] = add i32 [[I_0]], 1 +; IS________OPM-NEXT: br label [[COND]] +; IS________OPM: end: +; IS________OPM-NEXT: [[RET:%.*]] = icmp eq i32 [[C_0]], 0 +; IS________OPM-NEXT: ret i1 [[RET]] +; +; IS________NPM-LABEL: define {{[^@]+}}@potential_test9() +; IS________NPM-NEXT: entry: +; IS________NPM-NEXT: br label [[COND:%.*]] +; IS________NPM: cond: +; IS________NPM-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_1:%.*]], [[INC:%.*]] ] +; IS________NPM-NEXT: [[C_0:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ [[C_1:%.*]], [[INC]] ] +; IS________NPM-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_0]], 10 +; IS________NPM-NEXT: br i1 [[CMP]], label [[BODY:%.*]], label [[END:%.*]] +; IS________NPM: body: +; IS________NPM-NEXT: [[C_1]] = mul i32 [[C_0]], -1 +; IS________NPM-NEXT: br label [[INC]] +; IS________NPM: inc: +; IS________NPM-NEXT: [[I_1]] = add i32 [[I_0]], 1 +; IS________NPM-NEXT: br label [[COND]] +; IS________NPM: end: +; IS________NPM-NEXT: ret i1 false +; +entry: + br label %cond +cond: + %i.0 = phi i32 [0, %entry], [%i.1, %inc] + %c.0 = phi i32 [1, %entry], [%c.1, %inc] + %cmp = icmp slt i32 %i.0, 10 + br i1 %cmp, label %body, label %end +body: + %c.1 = mul i32 %c.0, -1 + br label %inc +inc: + %i.1 = add i32 %i.0, 1 + br label %cond +end: + %ret = icmp eq i32 %c.0, 0 + ret i1 %ret +} + +; IS__TUNIT____: !0 = !{i32 0, i32 2} +; IS__TUNIT____: !1 = !{i32 0, i32 3} +; IS__TUNIT____: !2 = !{i32 1, i32 4} +; IS__TUNIT____: !3 = !{i32 2, i32 5} +; IS__TUNIT____: !4 = !{i32 3, i32 5} +; IS__TUNIT____-NOT: !5 + +; NOT_TUNIT____-NOT: !0