diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -1974,10 +1974,12 @@ const IRPosition &getIRPosition() const { return *this; } ///} - /// Return an assumed simplified value if a single candidate is found. If - /// there cannot be one, return original value. If it is not clear yet, return - /// the Optional::NoneType. - virtual Optional getAssumedSimplifiedValue(Attributor &A) const = 0; + /// Return the values assumed to be equivalent. + virtual const SmallSetVector & + getAssumedEquivalentValues() const = 0; + + /// Return the constant assumed to be equivalent, if any. + virtual Constant *getAssumedEquivalentConstant() const = 0; /// Create an abstract attribute view for the position \p IRP. static AAValueSimplify &createForPosition(const IRPosition &IRP, diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -17,6 +17,7 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetOperations.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" @@ -1139,39 +1140,10 @@ STATS_DECLTRACK(UniqueReturnValue, FunctionReturn, "Number of function with unique return"); - // Callback to replace the uses of CB with the constant C. - auto ReplaceCallSiteUsersWith = [](CallBase &CB, Constant &C) { - if (CB.getNumUses() == 0 || CB.isMustTailCall()) - return ChangeStatus::UNCHANGED; - CB.replaceAllUsesWith(&C); - return ChangeStatus::CHANGED; - }; - // If the assumed unique return value is an argument, annotate it. if (auto *UniqueRVArg = dyn_cast(UniqueRV.getValue())) { getIRPosition() = IRPosition::argument(*UniqueRVArg); Changed = IRAttribute::manifest(A); - } else if (auto *RVC = dyn_cast(UniqueRV.getValue())) { - // We can replace the returned value with the unique returned constant. - Value &AnchorValue = getAnchorValue(); - if (Function *F = dyn_cast(&AnchorValue)) { - for (const Use &U : F->uses()) - if (CallBase *CB = dyn_cast(U.getUser())) - if (CB->isCallee(&U)) { - Constant *RVCCast = - ConstantExpr::getTruncOrBitCast(RVC, CB->getType()); - Changed = ReplaceCallSiteUsersWith(*CB, *RVCCast) | Changed; - } - } else { - assert(isa(AnchorValue) && - "Expcected a function or call base anchor!"); - Constant *RVCCast = - ConstantExpr::getTruncOrBitCast(RVC, AnchorValue.getType()); - Changed = ReplaceCallSiteUsersWith(cast(AnchorValue), *RVCCast); - } - if (Changed == ChangeStatus::CHANGED) - STATS_DECLTRACK(UniqueConstantReturnValue, FunctionReturn, - "Number of function returns replaced by constant return"); } return Changed; @@ -3694,114 +3666,282 @@ struct AAValueSimplifyImpl : AAValueSimplify { AAValueSimplifyImpl(const IRPosition &IRP) : AAValueSimplify(IRP) {} + void initialize(Attributor &A) override { + EquivalentValues.insert(&getAssociatedValue()); + if (isa(getAssociatedValue())) + indicateOptimisticFixpoint(); + } + /// See AbstractAttribute::getAsStr(). const std::string getAsStr() const override { - return getAssumed() ? (getKnown() ? "simplified" : "maybe-simple") - : "not-simple"; + return getAssumed() + ? "simplify(" + std::to_string(EquivalentValues.size()) + ")" + : "not-simplifiable"; } - /// See AbstractAttribute::trackStatistics() - void trackStatistics() const override {} + /// See AAValueSimplify::getAssumedEquivalentValues() + const SmallSetVector & + getAssumedEquivalentValues() const override { + return EquivalentValues; + } - /// See AAValueSimplify::getAssumedSimplifiedValue() - Optional getAssumedSimplifiedValue(Attributor &A) const override { - if (!getAssumed()) - return const_cast(&getAssociatedValue()); - return SimplifiedAssociatedValue; + /// See AAValueSimplify::getAssumedEquivalentConstant() + Constant *getAssumedEquivalentConstant() const override { + return getAssumedEquivalentConstant(&getAssociatedValue()); } - void initialize(Attributor &A) override {} - /// Helper function for querying AAValueSimplify and updating candicate. - /// \param QueryingValue Value trying to unify with SimplifiedValue - /// \param AccumulatedSimplifiedValue Current simplification result. - static bool checkAndUpdate(Attributor &A, const AbstractAttribute &QueryingAA, - Value &QueryingValue, - Optional &AccumulatedSimplifiedValue) { - // FIXME: Add a typecast support. + /// Combine the equivalent value set with the equivalent values for \p V. + bool recurseAndCombined(Attributor &A, Value &V, + const AAValueSimplify *VAA = nullptr) { + if (isa(V)) { + EquivalentValues.insert(&V); + return true; + } + + if (!VAA) + VAA = &A.getAAFor(*this, IRPosition::value(V)); + if (!VAA->isValidState()) + return false; + EquivalentValues.set_union(VAA->getAssumedEquivalentValues()); + return true; + } - auto &ValueSimpifyAA = A.getAAFor( - QueryingAA, IRPosition::value(QueryingValue)); + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + // Limit the equivalent values to compatible ones. + if (!checkConsistency(A, /* IgnoreFixpoint */ true)) + return ChangeStatus::UNCHANGED; - Optional QueryingValueSimplified = - ValueSimpifyAA.getAssumedSimplifiedValue(A); + Value &OldValue = getAssociatedValue(); + if (ImmutableCallSite ICS = ImmutableCallSite(OldValue.stripPointerCasts())) + if (ICS.isMustTailCall()) + return ChangeStatus::UNCHANGED; - if (!QueryingValueSimplified.hasValue()) - return true; + Value *NewValue = getNewValue(&OldValue, getCtxI()); + if (!NewValue) + return ChangeStatus::UNCHANGED; - if (!QueryingValueSimplified.getValue()) - return false; + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] Replace '" << OldValue + << "' with '" << *NewValue << "'\n"); + OldValue.replaceAllUsesWith(NewValue); + return ChangeStatus::CHANGED; + } - Value &QueryingValueSimplifiedUnwrapped = - *QueryingValueSimplified.getValue(); + ChangeStatus indicatePessimisticFixpoint() override { + // We only know "optimistic" fixpoints for most AAValueSimplify + // instanciations. However, we revert to a known state if a pessimistic one + // is requested. + EquivalentValues.clear(); + EquivalentValues.insert(&getAssociatedValue()); + indicateOptimisticFixpoint(); + return ChangeStatus::CHANGED; + } - if (isa(QueryingValueSimplifiedUnwrapped)) - return true; +protected: - if (AccumulatedSimplifiedValue.hasValue()) - return AccumulatedSimplifiedValue == QueryingValueSimplified; + Constant *getAssumedEquivalentConstant(const Value *OldValue) const { + bool IsPtr = OldValue->getType()->isPointerTy(); - LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << QueryingValue - << " is assumed to be " - << QueryingValueSimplifiedUnwrapped << "\n"); + bool HasUndef = false; + // Constants are valid everywhere so we can deal with them first. + for (Value *EquivV : EquivalentValues) + if (auto *C = dyn_cast(EquivV)) { + if (isa(C)) { + HasUndef = true; + continue; + } + if (C->getType() == OldValue->getType()) + return C; + if (IsPtr) + return ConstantExpr::getPointerCast(C, OldValue->getType()); + // TODO: Deal with other casts + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] Equivalent constant '" + << *C << "' needs complex cast.\n"); + } - AccumulatedSimplifiedValue = QueryingValueSimplified; - return true; + // If we only have undefs, we can use them. + if (HasUndef && EquivalentValues.size() == 1) + return UndefValue::get(OldValue->getType()); + return nullptr; } - /// See AbstractAttribute::manifest(...). - ChangeStatus manifest(Attributor &A) override { - ChangeStatus Changed = ChangeStatus::UNCHANGED; + Value *getNewValue(Value *OldValue, Instruction *IP) { + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] Find new value for '" + << *OldValue << "' @ " + << (IP ? IP->getName() : "") << "!\n"); + // TODO IsDead query + if (OldValue->getNumUses() == 0) + return nullptr; - if (!SimplifiedAssociatedValue.hasValue() || - !SimplifiedAssociatedValue.getValue()) - return Changed; - Value &V = getAssociatedValue(); - if (isa(V)) - return Changed; + if (isa(OldValue)) { + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] No new value necessary, '" + << *OldValue << "' is a constant!\n"); + return nullptr; + } - if (auto *C = dyn_cast(SimplifiedAssociatedValue.getValue())) { - // We can replace the AssociatedValue with the constant. - if (!V.user_empty() && &V != C && V.getType() == C->getType()) { - LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << V << " -> " << *C - << "\n"); - V.replaceAllUsesWith(C); - Changed = ChangeStatus::CHANGED; + if (Constant *C = getAssumedEquivalentConstant(OldValue)) + return C; + + bool IsPtr = OldValue->getType()->isPointerTy(); + for (Value *EquivV : EquivalentValues) { + // Do not replace a value "with itself". + if (OldValue == EquivV) + continue; + // Or with undef if we have other values. + // TODO: This is not necessarily an optimization but we go with it for + // now and see if it helps or causes problems. + if (isa(EquivV)) + continue; + + // Check if the simplified value is an instruction or argument in the same + // scope as the anchor. + if (canBeUsedInstead(*EquivV)) { + if (EquivV->getType() == OldValue->getType()) + return EquivV; + if (!IP) { + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] EquivV '" << *EquivV + << "' needs cast but no position provided.\n"); + continue; + } + if (IsPtr) + return new BitCastInst(EquivV, OldValue->getType(), ".cast", IP); + // TODO Deal with other casts + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] EquivV '" << *EquivV + << "' needs complex cast.\n"); + } else { + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] EquivV '" << *EquivV + << "' not usable in scope.\n"); } } - return Changed | AAValueSimplify::manifest(A); + DEBUG_WITH_TYPE( + "attributor-value-simplify", + dbgs() << "[AAValueSimplify] No suitable new value found, looked at " + << EquivalentValues.size() << " candidates\n"); + return nullptr; } -protected: - // An assumed simplified value. Initially, it is set to Optional::None, which - // means that the value is not clear under current assumption. If in the - // pessimistic state, getAssumedSimplifiedValue doesn't return this value but - // returns orignal associated value. - Optional SimplifiedAssociatedValue; + /// Verify the equivalent values are in a consistent state, that is there + /// might be an equivalence relation between all of them. + bool checkConsistency(Attributor &A, bool IgnoreFixpoint) { + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] Check consistency of " + << static_cast(*this) + << "\n"); + + if (EquivalentValues.size() < 2) + return true; + + SmallPtrSet Copy; + Copy.insert(EquivalentValues.begin(), EquivalentValues.end()); + + for (Value *V : EquivalentValues) { + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] - " << *V + << " | #EV : " << Copy.size() << "\n"); + if (V == &getAssociatedValue()) + continue; + + if (isa(V)) { + if (isa(V)) + continue; + + if (!Copy.count(V)) { + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] Constant EquivVal " << *V + << " not present anymore!\n"); + return false; + } + Copy.clear(); + Copy.insert(V); + continue; + } + + auto &VAA = A.getAAFor(*this, IRPosition::value(*V)); + if (!VAA.isValidState()) + return false; + if (!IgnoreFixpoint && !VAA.isAtFixpoint()) + continue; + + const auto &VEquivVals = VAA.getAssumedEquivalentValues(); + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] - " << *V + << " is equivalent to " << VEquivVals.size() + << " values -> intersection\n"); + set_intersect(Copy, VEquivVals); + } + + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] Consistency result: " + << Copy.size() << " of " << EquivalentValues.size() + << "\n";); + return !Copy.empty(); + } + + /// Returns true if \p NewValue can be used in the scope of this AA. + bool canBeUsedInstead(Value &NewValue) const { + if (isa(NewValue)) + return true; + + // Check if the simplified value is an instruction or argument in the same + // scope as the anchor. + const IRPosition &IRP = getIRPosition(); + if (auto *NewI = dyn_cast(&NewValue)) + if (NewI->getFunction() == IRP.getAnchorScope()) + return /* TODO: Dominacne test! */ false; + + if (auto *NewArg = dyn_cast(&NewValue)) + return NewArg->getParent() == IRP.getAnchorScope(); + + return false; + } + + /// Values equivalent to the one represented by the AA. + SmallSetVector EquivalentValues; }; struct AAValueSimplifyArgument final : AAValueSimplifyImpl { AAValueSimplifyArgument(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {} + void initialize(Attributor &A) override { + AAValueSimplifyImpl::initialize(A); + if (!getAssociatedFunction() || getAssociatedFunction()->isDeclaration()) + indicatePessimisticFixpoint(); + } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { - bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); + decltype(EquivalentValues) OldEquivalentValues = EquivalentValues; + EquivalentValues.clear(); auto PredForCallSite = [&](AbstractCallSite ACS) { // Check if we have an associated argument or not (which can happen for // callback calls). - if (Value *ArgOp = ACS.getCallArgOperand(getArgNo())) - return checkAndUpdate(A, *this, *ArgOp, SimplifiedAssociatedValue); - return false; + Value *ArgOp = ACS.getCallArgOperand(getArgNo()); + if (!ArgOp) + return false; + return recurseAndCombined(A, *ArgOp); }; if (!A.checkForAllCallSites(PredForCallSite, *this, true)) return indicatePessimisticFixpoint(); - // If a candicate was found in this update, return CHANGED. - return HasValueBefore == SimplifiedAssociatedValue.hasValue() - ? ChangeStatus::UNCHANGED - : ChangeStatus ::CHANGED; + // If no new candicates were found in this update, return UNCHANGED. + if (OldEquivalentValues == EquivalentValues) + return ChangeStatus::UNCHANGED; + + // Limit the equivalent values to compatible ones. + if (!checkConsistency(A, /* IgnoreFixpoint */ false)) + return indicatePessimisticFixpoint(); + + return ChangeStatus ::CHANGED; } /// See AbstractAttribute::trackStatistics() @@ -3813,22 +3953,70 @@ struct AAValueSimplifyReturned : AAValueSimplifyImpl { AAValueSimplifyReturned(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {} + void initialize(Attributor &A) override {} + + ChangeStatus indicatePessimisticFixpoint() override { + // Because there is no "return value" we cannot fall back to anything known + // and need to indicate an invalid state instead. + EquivalentValues.clear(); + return AAValueSimplify::indicatePessimisticFixpoint(); + } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { - bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); - - auto PredForReturned = [&](Value &V) { - return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue); - }; + decltype(EquivalentValues) OldEquivalentValues = EquivalentValues; + EquivalentValues.clear(); + auto PredForReturned = [&](Value &V) { return recurseAndCombined(A, V); }; if (!A.checkForAllReturnedValues(PredForReturned, *this)) return indicatePessimisticFixpoint(); - // If a candicate was found in this update, return CHANGED. - return HasValueBefore == SimplifiedAssociatedValue.hasValue() - ? ChangeStatus::UNCHANGED - : ChangeStatus ::CHANGED; + // If no new candicates were found in this update, return UNCHANGED. + if (OldEquivalentValues == EquivalentValues) + return ChangeStatus::UNCHANGED; + + // Limit the equivalent values to compatible ones. + if (!checkConsistency(A, /* IgnoreFixpoint */ false)) + return indicatePessimisticFixpoint(); + + return ChangeStatus ::CHANGED; } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + // Limit the equivalent values to compatible ones. + if (!checkConsistency(A, /* IgnoreFixpoint */ true)) + return ChangeStatus::UNCHANGED; + + Function *AssociatedFunction = getAssociatedFunction(); + ChangeStatus Changed = ChangeStatus::UNCHANGED; + auto RetValRepl = [&](Value &V, + const SmallSetVector &ReturnInsts) { + for (ReturnInst *RI : ReturnInsts) { + if (RI->getFunction() != AssociatedFunction) + continue; + Value *OldValue = RI->getOperand(0); + if (ImmutableCallSite ICS = ImmutableCallSite(OldValue->stripPointerCasts())) + if (ICS.isMustTailCall()) + continue; + Value *NewValue = getNewValue(OldValue, RI); + if (!NewValue) + continue; + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] Replace '" << OldValue + << "' with '" << *NewValue << "' in " << *RI + << "\n"); + RI->setOperand(0, NewValue); + Changed = ChangeStatus::CHANGED; + } + return true; + }; + + A.checkForAllReturnedValuesAndReturnInsts(RetValRepl, *this); + + return Changed; + } + /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(value_simplify) @@ -3838,30 +4026,72 @@ struct AAValueSimplifyFloating : AAValueSimplifyImpl { AAValueSimplifyFloating(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {} - /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { - Value &V = getAnchorValue(); - - // TODO: add other stuffs - if (isa(V) || isa(V)) - indicatePessimisticFixpoint(); + if (isa(getAssociatedValue())) + indicateOptimisticFixpoint(); } /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { - bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); + decltype(EquivalentValues) OldEquivalentValues = EquivalentValues; + EquivalentValues.clear(); + + auto GetConstantForValue = [&](Value *V, bool &AllConst) -> Constant *{ + if (Constant *COp = dyn_cast(V)) + return COp; + auto &VAA = A.getAAFor(*this, IRPosition::value(*V)); + if (VAA.isValidState()) + if (Constant *COp = VAA.getAssumedEquivalentConstant()) + return COp; + AllConst = false; + return nullptr; + }; auto VisitValueCB = [&](Value &V, BooleanState, bool Stripped) -> bool { - auto &AA = A.getAAFor(*this, IRPosition::value(V)); - if (!Stripped && this == &AA) { - // TODO: Look the instruction and check recursively. - LLVM_DEBUG( - dbgs() << "[Attributor][ValueSimplify] Can't be stripped more : " - << V << "\n"); - indicatePessimisticFixpoint(); + auto &VAA = A.getAAFor(*this, IRPosition::value(V)); + if (!VAA.isValidState()) return false; + if (Stripped || this != &VAA) + return recurseAndCombined(A, V, &VAA); + + EquivalentValues.insert(&V); + + Instruction *I = dyn_cast(&V); + if (!I) + return true; + + DEBUG_WITH_TYPE("attributor-value-simplify", + dbgs() << "[AAValueSimplify] Leaf reached (" << V + << "), try folding\n"); + + bool AllConst = true; + SmallVector COps; + for (Value *Op : I->operands()) + COps.push_back(GetConstantForValue(Op, AllConst)); + + Value *Repl = nullptr; + if (AllConst) + Repl = ConstantFoldInstOperands(I, COps, A.getDataLayout()); + else { + switch (I->getOpcode()) { + case Instruction::Select: + if (COps[0]) + Repl = COps[0]->isNullValue() ? I->getOperand(1) : I->getOperand(0); + break; + default: + // TODO: Check if we can reuse some logic or have to write our own + // for partially constant values. + break; + }; } - return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue); + DEBUG_WITH_TYPE("attributor-value-simplify", { + if (Repl) + dbgs() << "[AAValueSimplify] Folding successful: " << *Repl << "\n"; + }); + + if (Repl) + EquivalentValues.insert(Repl); + return true; }; if (!genericValueTraversal( @@ -3869,14 +4099,18 @@ VisitValueCB)) return indicatePessimisticFixpoint(); - // If a candicate was found in this update, return CHANGED. + // If no new candicates were found in this update, return UNCHANGED. + if (OldEquivalentValues == EquivalentValues) + return ChangeStatus::UNCHANGED; + + // Limit the equivalent values to compatible ones. + if (!checkConsistency(A, /* IgnoreFixpoint */ false)) + return indicatePessimisticFixpoint(); - return HasValueBefore == SimplifiedAssociatedValue.hasValue() - ? ChangeStatus::UNCHANGED - : ChangeStatus ::CHANGED; + return ChangeStatus ::CHANGED; } - /// See AbstractAttribute::trackStatistics() + /// See AbstractAttribute::trackStatistics(). void trackStatistics() const override { STATS_DECLTRACK_FLOATING_ATTR(value_simplify) } @@ -3885,43 +4119,90 @@ struct AAValueSimplifyFunction : AAValueSimplifyImpl { AAValueSimplifyFunction(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {} - /// See AbstractAttribute::initialize(...). - void initialize(Attributor &A) override { - SimplifiedAssociatedValue = &getAnchorValue(); - indicateOptimisticFixpoint(); - } - /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { indicateOptimisticFixpoint(); } + + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { llvm_unreachable( "AAValueSimplify(Function|CallSite)::updateImpl will not be called"); } - /// See AbstractAttribute::trackStatistics() + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + return ChangeStatus::UNCHANGED; + } + + /// See AbstractAttribute::trackStatistics(). void trackStatistics() const override { - STATS_DECLTRACK_FN_ATTR(value_simplify) + llvm_unreachable("AAValueSimplify(Function|CallSite)::trackStatistics will " + "not be called"); } }; +// TODO: Remove this as it can never be instantiated. This Will require a new +// createForPosition template. struct AAValueSimplifyCallSite : AAValueSimplifyFunction { AAValueSimplifyCallSite(const IRPosition &IRP) : AAValueSimplifyFunction(IRP) {} - /// See AbstractAttribute::trackStatistics() - void trackStatistics() const override { - STATS_DECLTRACK_CS_ATTR(value_simplify) - } }; -struct AAValueSimplifyCallSiteReturned : AAValueSimplifyReturned { +struct AAValueSimplifyCallSiteReturned : AAValueSimplifyImpl { AAValueSimplifyCallSiteReturned(const IRPosition &IRP) - : AAValueSimplifyReturned(IRP) {} + : AAValueSimplifyImpl(IRP) {} + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + decltype(EquivalentValues) OldEquivalentValues = EquivalentValues; + EquivalentValues.clear(); + + // TODO: Once we have call site specific value information we can provide + // call site specific liveness information and then it makes + // sense to specialize attributes for call sites instead of + // redirecting requests to the callee return value. + Function *F = getAssociatedFunction(); + if (!F) + return indicatePessimisticFixpoint(); + const IRPosition &RetPos = IRPosition::returned(*F); + auto &FnRetAA = A.getAAFor(*this, RetPos); + if (!FnRetAA.isValidState()) + return indicatePessimisticFixpoint(); + + // Copy equivalent values over but translate arguments of the callee to call + // site operands instead. + auto *CB = cast(getCtxI()); + for (Value *EquivV : FnRetAA.getAssumedEquivalentValues()) { + if (auto *Arg = dyn_cast(EquivV)) { + if (Arg->getParent() == CB->getCalledFunction()) { + if (!recurseAndCombined(A, *CB->getArgOperand(Arg->getArgNo()))) + return indicatePessimisticFixpoint(); + continue; + } + } + EquivalentValues.insert(EquivV); + } + + // If no new candicates were found in this update, return UNCHANGED. + if (OldEquivalentValues == EquivalentValues) + return ChangeStatus::UNCHANGED; + + // Limit the equivalent values to compatible ones. + if (!checkConsistency(A, /* IgnoreFixpoint */ false)) + return indicatePessimisticFixpoint(); + + return ChangeStatus ::CHANGED; + } + + /// See AbstractAttribute::trackStatistics(). void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(value_simplify) } }; + struct AAValueSimplifyCallSiteArgument : AAValueSimplifyFloating { AAValueSimplifyCallSiteArgument(const IRPosition &IRP) : AAValueSimplifyFloating(IRP) {} + /// See AbstractAttribute::trackStatistics(). void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(value_simplify) } @@ -5908,7 +6189,7 @@ // Every returned value might be dead. getOrCreateAAFor(RetPos); - // Every function might be simplified. + // Return instructions/values might be simplified. getOrCreateAAFor(RetPos); if (ReturnType->isPointerTy()) { @@ -5967,6 +6248,9 @@ // Call site return values might be dead. getOrCreateAAFor(CSRetPos); + + // Call site return values might be simplified. + getOrCreateAAFor(CSRetPos); } for (int i = 0, e = Callee->arg_size(); i < e; i++) { diff --git a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll --- a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll +++ b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll @@ -1,4 +1,4 @@ -; RUN: opt -functionattrs -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=10 -S < %s | FileCheck %s +; RUN: opt -functionattrs -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=11 -S < %s | FileCheck %s ; ; Test cases specifically designed for the "no-capture" argument attribute. ; We use FIXME's to indicate problems and missing attributes. diff --git a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll --- a/llvm/test/Transforms/FunctionAttrs/arg_returned.ll +++ b/llvm/test/Transforms/FunctionAttrs/arg_returned.ll @@ -1,5 +1,5 @@ ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR -; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR +; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=7 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR ; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -functionattrs -S < %s | FileCheck %s --check-prefix=BOTH ; ; Test cases specifically designed for the "returned" argument attribute. @@ -808,11 +808,11 @@ %c3 = call i32* @non_exact_3(i32* %a) ; We can use the information of the weak function non_exact_3 because it was ; given to us and not derived (the alignment of the returned argument). -; ATTRIBUTOR: %c4 = load i32, i32* %c3, align 32 +; ATTRIBUTOR: %c4 = load i32, i32* %a %c4 = load i32, i32* %c3 ; FIXME: %c2 and %c3 should be replaced but not %c0 or %c1! ; ATTRIBUTOR: %add1 = add i32 %c0, %c1 -; ATTRIBUTOR: %add2 = add i32 %add1, %c2 +; ATTRIBUTOR: %add2 = add i32 %add1, 2 ; ATTRIBUTOR: %add3 = add i32 %add2, %c4 %add1 = add i32 %c0, %c1 %add2 = add i32 %add1, %c2 diff --git a/llvm/test/Transforms/FunctionAttrs/value-simplify.ll b/llvm/test/Transforms/FunctionAttrs/value-simplify.ll --- a/llvm/test/Transforms/FunctionAttrs/value-simplify.ll +++ b/llvm/test/Transforms/FunctionAttrs/value-simplify.ll @@ -1,39 +1,63 @@ -; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s -; TODO: Add max-iteration check -; ModuleID = 'value-simplify.ll' -source_filename = "value-simplify.ll" +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=15 < %s | FileCheck %s target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" + declare void @f(i32) ; Test1: Replace argument with constant define internal void @test1(i32 %a) { -; CHECK: tail call void @f(i32 1) +; CHECK-LABEL: define {{[^@]+}}@test1 +; CHECK-SAME: (i32 [[A:%.*]]) +; CHECK-NEXT: tail call void @f(i32 1) +; CHECK-NEXT: ret void +; tail call void @f(i32 %a) ret void } define void @test1_helper() { +; CHECK-LABEL: define {{[^@]+}}@test1_helper() +; CHECK-NEXT: tail call void @test1(i32 1) +; CHECK-NEXT: ret void +; tail call void @test1(i32 1) ret void } ; TEST 2 : Simplify return value define i32 @return0() { +; CHECK-LABEL: define {{[^@]+}}@return0() +; CHECK-NEXT: ret i32 0 +; ret i32 0 } define i32 @return1() { +; CHECK-LABEL: define {{[^@]+}}@return1() +; CHECK-NEXT: ret i32 1 +; ret i32 1 } -; CHECK: define i32 @test2_1(i1 %c) define i32 @test2_1(i1 %c) { +; CHECK-LABEL: define {{[^@]+}}@test2_1 +; CHECK-SAME: (i1 [[C:%.*]]) +; CHECK-NEXT: br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] +; CHECK: if.true: +; CHECK-NEXT: [[CALL:%.*]] = tail call i32 @return0() +; CHECK-NEXT: [[RET0:%.*]] = add i32 0, 1 +; CHECK-NEXT: br label [[END:%.*]] +; CHECK: if.false: +; CHECK-NEXT: [[RET1:%.*]] = tail call i32 @return1() +; CHECK-NEXT: br label [[END]] +; CHECK: end: +; CHECK-NEXT: [[RET:%.*]] = phi i32 [ 1, [[IF_TRUE]] ], [ 1, [[IF_FALSE]] ] +; CHECK-NEXT: ret i32 1 +; br i1 %c, label %if.true, label %if.false if.true: %call = tail call i32 @return0() -; FIXME: %ret0 should be replaced with i32 1. -; CHECK: %ret0 = add i32 0, 1 %ret0 = add i32 %call, 1 br label %end if.false: @@ -42,28 +66,41 @@ end: ; FIXME: %ret should be replaced with i32 1. -; CHECK: %ret = phi i32 [ %ret0, %if.true ], [ 1, %if.false ] %ret = phi i32 [ %ret0, %if.true ], [ %ret1, %if.false ] ; FIXME: ret i32 1 -; CHECK: ret i32 %ret ret i32 %ret } -; CHECK: define i32 @test2_2(i1 %c) define i32 @test2_2(i1 %c) { ; FIXME: %ret should be replaced with i32 1. +; CHECK-LABEL: define {{[^@]+}}@test2_2 +; CHECK-SAME: (i1 [[C:%.*]]) +; CHECK-NEXT: [[RET:%.*]] = tail call i32 @test2_1(i1 [[C]]) +; CHECK-NEXT: ret i32 1 +; %ret = tail call i32 @test2_1(i1 %c) ; FIXME: ret i32 1 -; CHECK: ret i32 %ret ret i32 %ret } declare void @use(i32) -; CHECK: define void @test3(i1 %c) define void @test3(i1 %c) { +; CHECK-LABEL: define {{[^@]+}}@test3 +; CHECK-SAME: (i1 [[C:%.*]]) +; CHECK-NEXT: br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] +; CHECK: if.true: +; CHECK-NEXT: br label [[END:%.*]] +; CHECK: if.false: +; CHECK-NEXT: [[RET1:%.*]] = tail call i32 @return1() +; CHECK-NEXT: br label [[END]] +; CHECK: end: +; CHECK-NEXT: [[R:%.*]] = phi i32 [ 1, [[IF_TRUE]] ], [ 1, [[IF_FALSE]] ] +; CHECK-NEXT: tail call void @use(i32 1) +; CHECK-NEXT: ret void +; br i1 %c, label %if.true, label %if.false if.true: br label %end @@ -72,21 +109,41 @@ br label %end end: -; CHECK: %r = phi i32 [ 1, %if.true ], [ 1, %if.false ] %r = phi i32 [ 1, %if.true ], [ %ret1, %if.false ] -; CHECK: tail call void @use(i32 1) tail call void @use(i32 %r) ret void } define void @test-select-phi(i1 %c) { +; CHECK-LABEL: define {{[^@]+}}@test-select-phi +; CHECK-SAME: (i1 [[C:%.*]]) +; CHECK-NEXT: [[SELECT_SAME:%.*]] = select i1 [[C]], i32 1, i32 1 +; CHECK-NEXT: tail call void @use(i32 1) +; CHECK-NEXT: [[SELECT_NOT_SAME:%.*]] = select i1 [[C]], i32 1, i32 0 +; CHECK-NEXT: tail call void @use(i32 [[SELECT_NOT_SAME]]) +; CHECK-NEXT: br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] +; CHECK: if-true: +; CHECK-NEXT: br label [[END:%.*]] +; CHECK: if-false: +; CHECK-NEXT: br label [[END]] +; CHECK: end: +; CHECK-NEXT: [[PHI_SAME:%.*]] = phi i32 [ 1, [[IF_TRUE]] ], [ 1, [[IF_FALSE]] ] +; CHECK-NEXT: [[PHI_NOT_SAME:%.*]] = phi i32 [ 0, [[IF_TRUE]] ], [ 1, [[IF_FALSE]] ] +; CHECK-NEXT: [[PHI_SAME_PROP:%.*]] = phi i32 [ 1, [[IF_TRUE]] ], [ 1, [[IF_FALSE]] ] +; CHECK-NEXT: [[PHI_SAME_UNDEF:%.*]] = phi i32 [ 1, [[IF_TRUE]] ], [ undef, [[IF_FALSE]] ] +; CHECK-NEXT: [[SELECT_NOT_SAME_UNDEF:%.*]] = select i1 [[C]], i32 [[PHI_NOT_SAME]], i32 undef +; CHECK-NEXT: tail call void @use(i32 1) +; CHECK-NEXT: tail call void @use(i32 [[PHI_NOT_SAME]]) +; CHECK-NEXT: tail call void @use(i32 1) +; CHECK-NEXT: tail call void @use(i32 1) +; CHECK-NEXT: tail call void @use(i32 [[SELECT_NOT_SAME_UNDEF]]) +; CHECK-NEXT: ret void +; %select-same = select i1 %c, i32 1, i32 1 - ; CHECK: tail call void @use(i32 1) tail call void @use(i32 %select-same) %select-not-same = select i1 %c, i32 1, i32 0 - ; CHECK: tail call void @use(i32 %select-not-same) tail call void @use(i32 %select-not-same) br i1 %c, label %if-true, label %if-false if-true: @@ -101,21 +158,324 @@ %select-not-same-undef = select i1 %c, i32 %phi-not-same, i32 undef - ; CHECK: tail call void @use(i32 1) tail call void @use(i32 %phi-same) - ; CHECK: tail call void @use(i32 %phi-not-same) tail call void @use(i32 %phi-not-same) - ; CHECK: tail call void @use(i32 1) tail call void @use(i32 %phi-same-prop) - ; CHECK: tail call void @use(i32 1) tail call void @use(i32 %phi-same-undef) - ; CHECK: tail call void @use(i32 %select-not-same-undef) tail call void @use(i32 %select-not-same-undef) ret void } + +define internal i32 @rec0(i32 %a0) { +; CHECK-LABEL: define {{[^@]+}}@rec0 +; CHECK-SAME: (i32 returned [[A0:%.*]]) +; CHECK-NEXT: ret i32 [[A0]] +; + ret i32 %a0 +} + +define internal i32 @rec1(i1 %c, i32 %a1) { +; CHECK-LABEL: define {{[^@]+}}@rec1 +; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A1:%.*]]) +; CHECK-NEXT: br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] +; CHECK: if-true: +; CHECK-NEXT: [[REC0:%.*]] = call i32 @rec0(i32 [[A1]]) +; CHECK-NEXT: br label [[END:%.*]] +; CHECK: if-false: +; CHECK-NEXT: [[REC1:%.*]] = call i32 @rec1(i1 true, i32 [[A1]]) +; CHECK-NEXT: br label [[END]] +; CHECK: end: +; CHECK-NEXT: [[PHI_SAME:%.*]] = phi i32 [ [[REC0]], [[IF_TRUE]] ], [ [[REC1]], [[IF_FALSE]] ] +; CHECK-NEXT: ret i32 [[PHI_SAME]] +; + br i1 %c, label %if-true, label %if-false +if-true: + %rec0 = call i32 @rec0(i32 %a1) + br label %end +if-false: + %rec1 = call i32 @rec1(i1 true, i32 %a1) + br label %end +end: + %phi-same = phi i32 [ %rec0, %if-true ], [ %rec1, %if-false ] + ret i32 %phi-same +} + +define internal i32 @rec2(i1 %c, i32 %a2) { +; CHECK-LABEL: define {{[^@]+}}@rec2 +; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A2:%.*]]) +; CHECK-NEXT: br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] +; CHECK: if-true: +; CHECK-NEXT: [[REC1:%.*]] = call i32 @rec1(i1 [[C]], i32 [[A2]]) +; CHECK-NEXT: br label [[END:%.*]] +; CHECK: if-false: +; CHECK-NEXT: [[REC2:%.*]] = call i32 @rec2(i1 true, i32 [[A2]]) +; CHECK-NEXT: br label [[END]] +; CHECK: end: +; CHECK-NEXT: [[PHI_SAME:%.*]] = phi i32 [ [[REC1]], [[IF_TRUE]] ], [ [[REC2]], [[IF_FALSE]] ] +; CHECK-NEXT: ret i32 [[PHI_SAME]] +; + br i1 %c, label %if-true, label %if-false +if-true: + %rec1 = call i32 @rec1(i1 %c, i32 %a2) + br label %end +if-false: + %rec2 = call i32 @rec2(i1 true, i32 %a2) + br label %end +end: + %phi-same = phi i32 [ %rec1, %if-true ], [ %rec2, %if-false ] + ret i32 %phi-same +} + +define internal i32 @rec3(i1 %c, i32 %a3) { +; CHECK-LABEL: define {{[^@]+}}@rec3 +; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A3:%.*]]) +; CHECK-NEXT: br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] +; CHECK: if-true: +; CHECK-NEXT: [[REC2:%.*]] = call i32 @rec2(i1 [[C]], i32 [[A3]]) +; CHECK-NEXT: br label [[END:%.*]] +; CHECK: if-false: +; CHECK-NEXT: [[REC3:%.*]] = call i32 @rec3(i1 true, i32 [[A3]]) +; CHECK-NEXT: br label [[END]] +; CHECK: end: +; CHECK-NEXT: [[PHI_SAME:%.*]] = phi i32 [ [[REC2]], [[IF_TRUE]] ], [ [[REC3]], [[IF_FALSE]] ] +; CHECK-NEXT: ret i32 [[PHI_SAME]] +; + br i1 %c, label %if-true, label %if-false +if-true: + %rec2 = call i32 @rec2(i1 %c, i32 %a3) + br label %end +if-false: + %rec3 = call i32 @rec3(i1 true, i32 %a3) + br label %end +end: + %phi-same = phi i32 [ %rec2, %if-true ], [ %rec3, %if-false ] + ret i32 %phi-same +} + +define internal i32 @rec4(i1 %c, i32 %a4) { +; CHECK-LABEL: define {{[^@]+}}@rec4 +; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A4:%.*]]) +; CHECK-NEXT: br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] +; CHECK: if-true: +; CHECK-NEXT: [[REC3:%.*]] = call i32 @rec3(i1 [[C]], i32 [[A4]]) +; CHECK-NEXT: br label [[END:%.*]] +; CHECK: if-false: +; CHECK-NEXT: [[REC4:%.*]] = call i32 @rec4(i1 true, i32 [[A4]]) +; CHECK-NEXT: br label [[END]] +; CHECK: end: +; CHECK-NEXT: [[PHI_SAME:%.*]] = phi i32 [ [[REC3]], [[IF_TRUE]] ], [ [[REC4]], [[IF_FALSE]] ] +; CHECK-NEXT: ret i32 [[PHI_SAME]] +; + br i1 %c, label %if-true, label %if-false +if-true: + %rec3 = call i32 @rec3(i1 %c, i32 %a4) + br label %end +if-false: + %rec4 = call i32 @rec4(i1 true, i32 %a4) + br label %end +end: + %phi-same = phi i32 [ %rec3, %if-true ], [ %rec4, %if-false ] + ret i32 %phi-same +} + +define internal i32 @rec5(i1 %c, i32 %a5) { +; CHECK-LABEL: define {{[^@]+}}@rec5 +; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A5:%.*]]) +; CHECK-NEXT: br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] +; CHECK: if-true: +; CHECK-NEXT: [[REC4:%.*]] = call i32 @rec4(i1 [[C]], i32 [[A5]]) +; CHECK-NEXT: br label [[END:%.*]] +; CHECK: if-false: +; CHECK-NEXT: [[REC5:%.*]] = call i32 @rec5(i1 true, i32 [[A5]]) +; CHECK-NEXT: br label [[END]] +; CHECK: end: +; CHECK-NEXT: [[PHI_SAME:%.*]] = phi i32 [ [[REC4]], [[IF_TRUE]] ], [ [[REC5]], [[IF_FALSE]] ] +; CHECK-NEXT: ret i32 [[PHI_SAME]] +; + br i1 %c, label %if-true, label %if-false +if-true: + %rec4 = call i32 @rec4(i1 %c, i32 %a5) + br label %end +if-false: + %rec5 = call i32 @rec5(i1 true, i32 %a5) + br label %end +end: + %phi-same = phi i32 [ %rec4, %if-true ], [ %rec5, %if-false ] + ret i32 %phi-same +} + +define i32 @rec_caller(i1 %c, i32 %a_init) { +; CHECK-LABEL: define {{[^@]+}}@rec_caller +; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A_INIT:%.*]]) +; CHECK-NEXT: [[CALL:%.*]] = call i32 @rec5(i1 [[C]], i32 [[A_INIT]]) +; CHECK-NEXT: ret i32 [[A_INIT]] +; + %call = call i32 @rec5(i1 %c, i32 %a_init) + ret i32 %call +} + +define i32 @loop_no_const(i32 %N) { +; CHECK-LABEL: define {{[^@]+}}@loop_no_const +; CHECK-SAME: (i32 [[N:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_COND:%.*]] +; CHECK: for.cond: +; CHECK-NEXT: [[A_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD:%.*]], [[FOR_INC:%.*]] ] +; CHECK-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_INC]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_0]], [[N]] +; CHECK-NEXT: br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[ADD]] = add nsw i32 [[A_0]], [[I_0]] +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[INC]] = add nsw i32 [[I_0]], 1 +; CHECK-NEXT: br label [[FOR_COND]] +; CHECK: for.end: +; CHECK-NEXT: ret i32 [[A_0]] +; +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %a.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ] + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, %N + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %add = add nsw i32 %a.0, %i.0 + br label %for.inc + +for.inc: ; preds = %for.body + %inc = add nsw i32 %i.0, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret i32 %a.0 +} + +define i32 @alternating_in_loop(i32 %N) { +; CHECK-LABEL: define {{[^@]+}}@alternating_in_loop +; CHECK-SAME: (i32 [[N:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_COND:%.*]] +; CHECK: for.cond: +; CHECK-NEXT: [[A_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[FOR_INC:%.*]] ] +; CHECK-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_INC]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_0]], [[N]] +; CHECK-NEXT: br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[SUB]] = sub nsw i32 1, [[A_0]] +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[INC]] = add nsw i32 [[I_0]], 1 +; CHECK-NEXT: br label [[FOR_COND]] +; CHECK: for.end: +; CHECK-NEXT: ret i32 [[A_0]] +; +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %a.0 = phi i32 [ 0, %entry ], [ %sub, %for.inc ] + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, %N + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %sub = sub nsw i32 1, %a.0 + br label %for.inc + +for.inc: ; preds = %for.body + %inc = add nsw i32 %i.0, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret i32 %a.0 +} + +define i32 @const_in_loop1(i32 %N) { +; CHECK-LABEL: define {{[^@]+}}@const_in_loop1 +; CHECK-SAME: (i32 [[N:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_COND:%.*]] +; CHECK: for.cond: +; CHECK-NEXT: [[A_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 0, [[FOR_INC:%.*]] ] +; CHECK-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_INC]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_0]], [[N]] +; CHECK-NEXT: br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[MUL:%.*]] = mul nsw i32 0, 0 +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[INC]] = add nsw i32 [[I_0]], 1 +; CHECK-NEXT: br label [[FOR_COND]] +; CHECK: for.end: +; CHECK-NEXT: ret i32 0 +; +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %a.0 = phi i32 [ 0, %entry ], [ %mul, %for.inc ] + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, %N + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %mul = mul nsw i32 %a.0, %a.0 + br label %for.inc + +for.inc: ; preds = %for.body + %inc = add nsw i32 %i.0, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret i32 %a.0 +} + +define i32 @const_in_loop2(i32 %N) { +; CHECK-LABEL: define {{[^@]+}}@const_in_loop2 +; CHECK-SAME: (i32 [[N:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_COND:%.*]] +; CHECK: for.cond: +; CHECK-NEXT: [[A_0:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 1, [[FOR_INC:%.*]] ] +; CHECK-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_INC]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_0]], [[N]] +; CHECK-NEXT: br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[MUL:%.*]] = mul nsw i32 1, 1 +; CHECK-NEXT: br label [[FOR_INC]] +; CHECK: for.inc: +; CHECK-NEXT: [[INC]] = add nsw i32 [[I_0]], 1 +; CHECK-NEXT: br label [[FOR_COND]] +; CHECK: for.end: +; CHECK-NEXT: ret i32 1 +; +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %a.0 = phi i32 [ 1, %entry ], [ %mul, %for.inc ] + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, %N + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %mul = mul nsw i32 %a.0, %a.0 + br label %for.inc + +for.inc: ; preds = %for.body + %inc = add nsw i32 %i.0, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret i32 %a.0 +} diff --git a/llvm/test/Transforms/FunctionAttrs/willreturn.ll b/llvm/test/Transforms/FunctionAttrs/willreturn.ll --- a/llvm/test/Transforms/FunctionAttrs/willreturn.ll +++ b/llvm/test/Transforms/FunctionAttrs/willreturn.ll @@ -1,5 +1,5 @@ ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR -; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR +; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=4 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"