diff options
Diffstat (limited to 'llvm/lib/Transforms/IPO/Attributor.cpp')
| -rw-r--r-- | llvm/lib/Transforms/IPO/Attributor.cpp | 739 |
1 files changed, 609 insertions, 130 deletions
diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp index 03ad45135001..762317425026 100644 --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -17,6 +17,7 @@ #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/TinyPtrVector.h" #include "llvm/Analysis/InlineCost.h" @@ -24,9 +25,16 @@ #include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/Attributes.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/Constants.h" #include "llvm/IR/GlobalValue.h" +#include "llvm/IR/GlobalVariable.h" #include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/NoFolder.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/IR/Verifier.h" #include "llvm/InitializePasses.h" #include "llvm/Support/Casting.h" @@ -62,8 +70,6 @@ STATISTIC(NumAttributesValidFixpoint, "Number of abstract attributes in a valid fixpoint state"); STATISTIC(NumAttributesManifested, "Number of abstract attributes manifested in IR"); -STATISTIC(NumAttributesFixedDueToRequiredDependences, - "Number of abstract attributes fixed due to required dependences"); // TODO: Determine a good default value. // @@ -74,7 +80,7 @@ STATISTIC(NumAttributesFixedDueToRequiredDependences, // This will become more evolved once we perform two interleaved fixpoint // iterations: bottom-up and top-down. static cl::opt<unsigned> - MaxFixpointIterations("attributor-max-iterations", cl::Hidden, + SetFixpointIterations("attributor-max-iterations", cl::Hidden, cl::desc("Maximal number of fixpoint iterations."), cl::init(32)); @@ -141,17 +147,221 @@ static cl::opt<bool> PrintDependencies("attributor-print-dep", cl::Hidden, cl::desc("Print attribute dependencies"), cl::init(false)); +static cl::opt<bool> EnableCallSiteSpecific( + "attributor-enable-call-site-specific-deduction", cl::Hidden, + cl::desc("Allow the Attributor to do call site specific analysis"), + cl::init(false)); + +static cl::opt<bool> + PrintCallGraph("attributor-print-call-graph", cl::Hidden, + cl::desc("Print Attributor's internal call graph"), + cl::init(false)); + +static cl::opt<bool> SimplifyAllLoads("attributor-simplify-all-loads", + cl::Hidden, + cl::desc("Try to simplify all loads."), + cl::init(true)); + /// Logic operators for the change status enum class. /// ///{ ChangeStatus llvm::operator|(ChangeStatus L, ChangeStatus R) { return L == ChangeStatus::CHANGED ? L : R; } +ChangeStatus &llvm::operator|=(ChangeStatus &L, ChangeStatus R) { + L = L | R; + return L; +} ChangeStatus llvm::operator&(ChangeStatus L, ChangeStatus R) { return L == ChangeStatus::UNCHANGED ? L : R; } +ChangeStatus &llvm::operator&=(ChangeStatus &L, ChangeStatus R) { + L = L & R; + return L; +} ///} +bool AA::isDynamicallyUnique(Attributor &A, const AbstractAttribute &QueryingAA, + const Value &V) { + if (auto *C = dyn_cast<Constant>(&V)) + return !C->isThreadDependent(); + // TODO: Inspect and cache more complex instructions. + if (auto *CB = dyn_cast<CallBase>(&V)) + return CB->getNumOperands() == 0 && !CB->mayHaveSideEffects() && + !CB->mayReadFromMemory(); + const Function *Scope = nullptr; + if (auto *I = dyn_cast<Instruction>(&V)) + Scope = I->getFunction(); + if (auto *A = dyn_cast<Argument>(&V)) + Scope = A->getParent(); + if (!Scope) + return false; + auto &NoRecurseAA = A.getAAFor<AANoRecurse>( + QueryingAA, IRPosition::function(*Scope), DepClassTy::OPTIONAL); + return NoRecurseAA.isAssumedNoRecurse(); +} + +Constant *AA::getInitialValueForObj(Value &Obj, Type &Ty) { + if (isa<AllocaInst>(Obj)) + return UndefValue::get(&Ty); + auto *GV = dyn_cast<GlobalVariable>(&Obj); + if (!GV || !GV->hasLocalLinkage()) + return nullptr; + if (!GV->hasInitializer()) + return UndefValue::get(&Ty); + return dyn_cast_or_null<Constant>(getWithType(*GV->getInitializer(), Ty)); +} + +bool AA::isValidInScope(const Value &V, const Function *Scope) { + if (isa<Constant>(V)) + return true; + if (auto *I = dyn_cast<Instruction>(&V)) + return I->getFunction() == Scope; + if (auto *A = dyn_cast<Argument>(&V)) + return A->getParent() == Scope; + return false; +} + +bool AA::isValidAtPosition(const Value &V, const Instruction &CtxI, + InformationCache &InfoCache) { + if (isa<Constant>(V)) + return true; + const Function *Scope = CtxI.getFunction(); + if (auto *A = dyn_cast<Argument>(&V)) + return A->getParent() == Scope; + if (auto *I = dyn_cast<Instruction>(&V)) + if (I->getFunction() == Scope) { + const DominatorTree *DT = + InfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(*Scope); + return DT && DT->dominates(I, &CtxI); + } + return false; +} + +Value *AA::getWithType(Value &V, Type &Ty) { + if (V.getType() == &Ty) + return &V; + if (isa<PoisonValue>(V)) + return PoisonValue::get(&Ty); + if (isa<UndefValue>(V)) + return UndefValue::get(&Ty); + if (auto *C = dyn_cast<Constant>(&V)) { + if (C->isNullValue()) + return Constant::getNullValue(&Ty); + if (C->getType()->isPointerTy() && Ty.isPointerTy()) + return ConstantExpr::getPointerCast(C, &Ty); + if (C->getType()->isIntegerTy() && Ty.isIntegerTy()) + return ConstantExpr::getTrunc(C, &Ty, /* OnlyIfReduced */ true); + if (C->getType()->isFloatingPointTy() && Ty.isFloatingPointTy()) + return ConstantExpr::getFPTrunc(C, &Ty, /* OnlyIfReduced */ true); + } + return nullptr; +} + +Optional<Value *> +AA::combineOptionalValuesInAAValueLatice(const Optional<Value *> &A, + const Optional<Value *> &B, Type *Ty) { + if (A == B) + return A; + if (!B.hasValue()) + return A; + if (*B == nullptr) + return nullptr; + if (!A.hasValue()) + return Ty ? getWithType(**B, *Ty) : nullptr; + if (*A == nullptr) + return nullptr; + if (!Ty) + Ty = (*A)->getType(); + if (isa_and_nonnull<UndefValue>(*A)) + return getWithType(**B, *Ty); + if (isa<UndefValue>(*B)) + return A; + if (*A && *B && *A == getWithType(**B, *Ty)) + return A; + return nullptr; +} + +bool AA::getPotentialCopiesOfStoredValue( + Attributor &A, StoreInst &SI, SmallSetVector<Value *, 4> &PotentialCopies, + const AbstractAttribute &QueryingAA, bool &UsedAssumedInformation) { + + Value &Ptr = *SI.getPointerOperand(); + SmallVector<Value *, 8> Objects; + if (!AA::getAssumedUnderlyingObjects(A, Ptr, Objects, QueryingAA, &SI)) { + LLVM_DEBUG( + dbgs() << "Underlying objects stored into could not be determined\n";); + return false; + } + + SmallVector<const AAPointerInfo *> PIs; + SmallVector<Value *> NewCopies; + + for (Value *Obj : Objects) { + LLVM_DEBUG(dbgs() << "Visit underlying object " << *Obj << "\n"); + if (isa<UndefValue>(Obj)) + continue; + if (isa<ConstantPointerNull>(Obj)) { + // A null pointer access can be undefined but any offset from null may + // be OK. We do not try to optimize the latter. + if (!NullPointerIsDefined(SI.getFunction(), + Ptr.getType()->getPointerAddressSpace()) && + A.getAssumedSimplified(Ptr, QueryingAA, UsedAssumedInformation) == + Obj) + continue; + LLVM_DEBUG( + dbgs() << "Underlying object is a valid nullptr, giving up.\n";); + return false; + } + if (!isa<AllocaInst>(Obj) && !isa<GlobalVariable>(Obj)) { + LLVM_DEBUG(dbgs() << "Underlying object is not supported yet: " << *Obj + << "\n";); + return false; + } + if (auto *GV = dyn_cast<GlobalVariable>(Obj)) + if (!GV->hasLocalLinkage()) { + LLVM_DEBUG(dbgs() << "Underlying object is global with external " + "linkage, not supported yet: " + << *Obj << "\n";); + return false; + } + + auto CheckAccess = [&](const AAPointerInfo::Access &Acc, bool IsExact) { + if (!Acc.isRead()) + return true; + auto *LI = dyn_cast<LoadInst>(Acc.getRemoteInst()); + if (!LI) { + LLVM_DEBUG(dbgs() << "Underlying object read through a non-load " + "instruction not supported yet: " + << *Acc.getRemoteInst() << "\n";); + return false; + } + NewCopies.push_back(LI); + return true; + }; + + auto &PI = A.getAAFor<AAPointerInfo>(QueryingAA, IRPosition::value(*Obj), + DepClassTy::NONE); + if (!PI.forallInterferingAccesses(SI, CheckAccess)) { + LLVM_DEBUG( + dbgs() + << "Failed to verify all interfering accesses for underlying object: " + << *Obj << "\n"); + return false; + } + PIs.push_back(&PI); + } + + for (auto *PI : PIs) { + if (!PI->getState().isAtFixpoint()) + UsedAssumedInformation = true; + A.recordDependence(*PI, QueryingAA, DepClassTy::OPTIONAL); + } + PotentialCopies.insert(NewCopies.begin(), NewCopies.end()); + + return true; +} + /// Return true if \p New is equal or worse than \p Old. static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) { if (!Old.isIntAttribute()) @@ -164,12 +374,14 @@ static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) { /// attribute list \p Attrs. This is only the case if it was not already present /// in \p Attrs at the position describe by \p PK and \p AttrIdx. static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, - AttributeList &Attrs, int AttrIdx) { + AttributeList &Attrs, int AttrIdx, + bool ForceReplace = false) { if (Attr.isEnumAttribute()) { Attribute::AttrKind Kind = Attr.getKindAsEnum(); if (Attrs.hasAttribute(AttrIdx, Kind)) - if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) + if (!ForceReplace && + isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) return false; Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr); return true; @@ -177,7 +389,8 @@ static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, if (Attr.isStringAttribute()) { StringRef Kind = Attr.getKindAsString(); if (Attrs.hasAttribute(AttrIdx, Kind)) - if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) + if (!ForceReplace && + isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) return false; Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr); return true; @@ -185,7 +398,8 @@ static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, if (Attr.isIntAttribute()) { Attribute::AttrKind Kind = Attr.getKindAsEnum(); if (Attrs.hasAttribute(AttrIdx, Kind)) - if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) + if (!ForceReplace && + isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) return false; Attrs = Attrs.removeAttribute(Ctx, AttrIdx, Kind); Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr); @@ -266,7 +480,8 @@ ChangeStatus AbstractAttribute::update(Attributor &A) { ChangeStatus IRAttributeManifest::manifestAttrs(Attributor &A, const IRPosition &IRP, - const ArrayRef<Attribute> &DeducedAttrs) { + const ArrayRef<Attribute> &DeducedAttrs, + bool ForceReplace) { Function *ScopeFn = IRP.getAnchorScope(); IRPosition::Kind PK = IRP.getPositionKind(); @@ -294,7 +509,7 @@ IRAttributeManifest::manifestAttrs(Attributor &A, const IRPosition &IRP, ChangeStatus HasChanged = ChangeStatus::UNCHANGED; LLVMContext &Ctx = IRP.getAnchorValue().getContext(); for (const Attribute &Attr : DeducedAttrs) { - if (!addIfNotExistent(Ctx, Attr, Attrs, IRP.getAttrIdx())) + if (!addIfNotExistent(Ctx, Attr, Attrs, IRP.getAttrIdx(), ForceReplace)) continue; HasChanged = ChangeStatus::CHANGED; @@ -475,6 +690,8 @@ void IRPosition::verify() { #ifdef EXPENSIVE_CHECKS switch (getPositionKind()) { case IRP_INVALID: + assert((CBContext == nullptr) && + "Invalid position must not have CallBaseContext!"); assert(!Enc.getOpaqueValue() && "Expected a nullptr for an invalid position!"); return; @@ -490,12 +707,16 @@ void IRPosition::verify() { "Associated value mismatch!"); return; case IRP_CALL_SITE_RETURNED: + assert((CBContext == nullptr) && + "'call site returned' position must not have CallBaseContext!"); assert((isa<CallBase>(getAsValuePtr())) && "Expected call base for 'call site returned' position!"); assert(getAsValuePtr() == &getAssociatedValue() && "Associated value mismatch!"); return; case IRP_CALL_SITE: + assert((CBContext == nullptr) && + "'call site function' position must not have CallBaseContext!"); assert((isa<CallBase>(getAsValuePtr())) && "Expected call base for 'call site function' position!"); assert(getAsValuePtr() == &getAssociatedValue() && @@ -514,6 +735,8 @@ void IRPosition::verify() { "Associated value mismatch!"); return; case IRP_CALL_SITE_ARGUMENT: { + assert((CBContext == nullptr) && + "'call site argument' position must not have CallBaseContext!"); Use *U = getAsUsePtr(); assert(U && "Expected use for a 'call site argument' position!"); assert(isa<CallBase>(U->getUser()) && @@ -532,13 +755,25 @@ void IRPosition::verify() { } Optional<Constant *> -Attributor::getAssumedConstant(const Value &V, const AbstractAttribute &AA, +Attributor::getAssumedConstant(const IRPosition &IRP, + const AbstractAttribute &AA, bool &UsedAssumedInformation) { - const auto &ValueSimplifyAA = getAAFor<AAValueSimplify>( - AA, IRPosition::value(V), /* TrackDependence */ false); + // First check all callbacks provided by outside AAs. If any of them returns + // a non-null value that is different from the associated value, or None, we + // assume it's simpliied. + for (auto &CB : SimplificationCallbacks.lookup(IRP)) { + Optional<Value *> SimplifiedV = CB(IRP, &AA, UsedAssumedInformation); + if (!SimplifiedV.hasValue()) + return llvm::None; + if (isa_and_nonnull<Constant>(*SimplifiedV)) + return cast<Constant>(*SimplifiedV); + return nullptr; + } + const auto &ValueSimplifyAA = + getAAFor<AAValueSimplify>(AA, IRP, DepClassTy::NONE); Optional<Value *> SimplifiedV = ValueSimplifyAA.getAssumedSimplifiedValue(*this); - bool IsKnown = ValueSimplifyAA.isKnown(); + bool IsKnown = ValueSimplifyAA.isAtFixpoint(); UsedAssumedInformation |= !IsKnown; if (!SimplifiedV.hasValue()) { recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL); @@ -546,18 +781,66 @@ Attributor::getAssumedConstant(const Value &V, const AbstractAttribute &AA, } if (isa_and_nonnull<UndefValue>(SimplifiedV.getValue())) { recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL); - return llvm::None; + return UndefValue::get(IRP.getAssociatedType()); } Constant *CI = dyn_cast_or_null<Constant>(SimplifiedV.getValue()); - if (CI && CI->getType() != V.getType()) { - // TODO: Check for a save conversion. - return nullptr; - } + if (CI) + CI = dyn_cast_or_null<Constant>( + AA::getWithType(*CI, *IRP.getAssociatedType())); if (CI) recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL); return CI; } +Optional<Value *> +Attributor::getAssumedSimplified(const IRPosition &IRP, + const AbstractAttribute *AA, + bool &UsedAssumedInformation) { + // First check all callbacks provided by outside AAs. If any of them returns + // a non-null value that is different from the associated value, or None, we + // assume it's simpliied. + for (auto &CB : SimplificationCallbacks.lookup(IRP)) + return CB(IRP, AA, UsedAssumedInformation); + + // If no high-level/outside simplification occured, use AAValueSimplify. + const auto &ValueSimplifyAA = + getOrCreateAAFor<AAValueSimplify>(IRP, AA, DepClassTy::NONE); + Optional<Value *> SimplifiedV = + ValueSimplifyAA.getAssumedSimplifiedValue(*this); + bool IsKnown = ValueSimplifyAA.isAtFixpoint(); + UsedAssumedInformation |= !IsKnown; + if (!SimplifiedV.hasValue()) { + if (AA) + recordDependence(ValueSimplifyAA, *AA, DepClassTy::OPTIONAL); + return llvm::None; + } + if (*SimplifiedV == nullptr) + return const_cast<Value *>(&IRP.getAssociatedValue()); + if (Value *SimpleV = + AA::getWithType(**SimplifiedV, *IRP.getAssociatedType())) { + if (AA) + recordDependence(ValueSimplifyAA, *AA, DepClassTy::OPTIONAL); + return SimpleV; + } + return const_cast<Value *>(&IRP.getAssociatedValue()); +} + +Optional<Value *> Attributor::translateArgumentToCallSiteContent( + Optional<Value *> V, CallBase &CB, const AbstractAttribute &AA, + bool &UsedAssumedInformation) { + if (!V.hasValue()) + return V; + if (*V == nullptr || isa<Constant>(*V)) + return V; + if (auto *Arg = dyn_cast<Argument>(*V)) + if (CB.getCalledFunction() == Arg->getParent()) + if (!Arg->hasPointeeInMemoryValueAttr()) + return getAssumedSimplified( + IRPosition::callsite_argument(CB, Arg->getArgNo()), AA, + UsedAssumedInformation); + return nullptr; +} + Attributor::~Attributor() { // The abstract attributes are allocated via the BumpPtrAllocator Allocator, // thus we cannot delete them. We can, and want to, destruct them though. @@ -569,21 +852,24 @@ Attributor::~Attributor() { bool Attributor::isAssumedDead(const AbstractAttribute &AA, const AAIsDead *FnLivenessAA, + bool &UsedAssumedInformation, bool CheckBBLivenessOnly, DepClassTy DepClass) { const IRPosition &IRP = AA.getIRPosition(); if (!Functions.count(IRP.getAnchorScope())) return false; - return isAssumedDead(IRP, &AA, FnLivenessAA, CheckBBLivenessOnly, DepClass); + return isAssumedDead(IRP, &AA, FnLivenessAA, UsedAssumedInformation, + CheckBBLivenessOnly, DepClass); } bool Attributor::isAssumedDead(const Use &U, const AbstractAttribute *QueryingAA, const AAIsDead *FnLivenessAA, + bool &UsedAssumedInformation, bool CheckBBLivenessOnly, DepClassTy DepClass) { Instruction *UserI = dyn_cast<Instruction>(U.getUser()); if (!UserI) return isAssumedDead(IRPosition::value(*U.get()), QueryingAA, FnLivenessAA, - CheckBBLivenessOnly, DepClass); + UsedAssumedInformation, CheckBBLivenessOnly, DepClass); if (auto *CB = dyn_cast<CallBase>(UserI)) { // For call site argument uses we can check if the argument is @@ -592,30 +878,38 @@ bool Attributor::isAssumedDead(const Use &U, const IRPosition &CSArgPos = IRPosition::callsite_argument(*CB, CB->getArgOperandNo(&U)); return isAssumedDead(CSArgPos, QueryingAA, FnLivenessAA, - CheckBBLivenessOnly, DepClass); + UsedAssumedInformation, CheckBBLivenessOnly, + DepClass); } } else if (ReturnInst *RI = dyn_cast<ReturnInst>(UserI)) { const IRPosition &RetPos = IRPosition::returned(*RI->getFunction()); - return isAssumedDead(RetPos, QueryingAA, FnLivenessAA, CheckBBLivenessOnly, - DepClass); + return isAssumedDead(RetPos, QueryingAA, FnLivenessAA, + UsedAssumedInformation, CheckBBLivenessOnly, DepClass); } else if (PHINode *PHI = dyn_cast<PHINode>(UserI)) { BasicBlock *IncomingBB = PHI->getIncomingBlock(U); return isAssumedDead(*IncomingBB->getTerminator(), QueryingAA, FnLivenessAA, - CheckBBLivenessOnly, DepClass); + UsedAssumedInformation, CheckBBLivenessOnly, DepClass); } return isAssumedDead(IRPosition::value(*UserI), QueryingAA, FnLivenessAA, - CheckBBLivenessOnly, DepClass); + UsedAssumedInformation, CheckBBLivenessOnly, DepClass); } bool Attributor::isAssumedDead(const Instruction &I, const AbstractAttribute *QueryingAA, const AAIsDead *FnLivenessAA, + bool &UsedAssumedInformation, bool CheckBBLivenessOnly, DepClassTy DepClass) { + const IRPosition::CallBaseContext *CBCtx = + QueryingAA ? QueryingAA->getCallBaseContext() : nullptr; + + if (ManifestAddedBlocks.contains(I.getParent())) + return false; + if (!FnLivenessAA) - FnLivenessAA = lookupAAFor<AAIsDead>(IRPosition::function(*I.getFunction()), - QueryingAA, - /* TrackDependence */ false); + FnLivenessAA = + lookupAAFor<AAIsDead>(IRPosition::function(*I.getFunction(), CBCtx), + QueryingAA, DepClassTy::NONE); // If we have a context instruction and a liveness AA we use it. if (FnLivenessAA && @@ -623,6 +917,8 @@ bool Attributor::isAssumedDead(const Instruction &I, FnLivenessAA->isAssumedDead(&I)) { if (QueryingAA) recordDependence(*FnLivenessAA, *QueryingAA, DepClass); + if (!FnLivenessAA->isKnownDead(&I)) + UsedAssumedInformation = true; return true; } @@ -630,7 +926,7 @@ bool Attributor::isAssumedDead(const Instruction &I, return false; const AAIsDead &IsDeadAA = getOrCreateAAFor<AAIsDead>( - IRPosition::value(I), QueryingAA, /* TrackDependence */ false); + IRPosition::value(I, CBCtx), QueryingAA, DepClassTy::NONE); // Don't check liveness for AAIsDead. if (QueryingAA == &IsDeadAA) return false; @@ -638,6 +934,8 @@ bool Attributor::isAssumedDead(const Instruction &I, if (IsDeadAA.isAssumedDead()) { if (QueryingAA) recordDependence(IsDeadAA, *QueryingAA, DepClass); + if (!IsDeadAA.isKnownDead()) + UsedAssumedInformation = true; return true; } @@ -647,10 +945,11 @@ bool Attributor::isAssumedDead(const Instruction &I, bool Attributor::isAssumedDead(const IRPosition &IRP, const AbstractAttribute *QueryingAA, const AAIsDead *FnLivenessAA, + bool &UsedAssumedInformation, bool CheckBBLivenessOnly, DepClassTy DepClass) { Instruction *CtxI = IRP.getCtxI(); if (CtxI && - isAssumedDead(*CtxI, QueryingAA, FnLivenessAA, + isAssumedDead(*CtxI, QueryingAA, FnLivenessAA, UsedAssumedInformation, /* CheckBBLivenessOnly */ true, CheckBBLivenessOnly ? DepClass : DepClassTy::OPTIONAL)) return true; @@ -663,10 +962,9 @@ bool Attributor::isAssumedDead(const IRPosition &IRP, if (IRP.getPositionKind() == IRPosition::IRP_CALL_SITE) IsDeadAA = &getOrCreateAAFor<AAIsDead>( IRPosition::callsite_returned(cast<CallBase>(IRP.getAssociatedValue())), - QueryingAA, /* TrackDependence */ false); + QueryingAA, DepClassTy::NONE); else - IsDeadAA = &getOrCreateAAFor<AAIsDead>(IRP, QueryingAA, - /* TrackDependence */ false); + IsDeadAA = &getOrCreateAAFor<AAIsDead>(IRP, QueryingAA, DepClassTy::NONE); // Don't check liveness for AAIsDead. if (QueryingAA == IsDeadAA) return false; @@ -674,6 +972,24 @@ bool Attributor::isAssumedDead(const IRPosition &IRP, if (IsDeadAA->isAssumedDead()) { if (QueryingAA) recordDependence(*IsDeadAA, *QueryingAA, DepClass); + if (!IsDeadAA->isKnownDead()) + UsedAssumedInformation = true; + return true; + } + + return false; +} + +bool Attributor::isAssumedDead(const BasicBlock &BB, + const AbstractAttribute *QueryingAA, + const AAIsDead *FnLivenessAA, + DepClassTy DepClass) { + if (!FnLivenessAA) + FnLivenessAA = lookupAAFor<AAIsDead>(IRPosition::function(*BB.getParent()), + QueryingAA, DepClassTy::NONE); + if (FnLivenessAA->isAssumedDead(&BB)) { + if (QueryingAA) + recordDependence(*FnLivenessAA, *QueryingAA, DepClass); return true; } @@ -682,25 +998,13 @@ bool Attributor::isAssumedDead(const IRPosition &IRP, bool Attributor::checkForAllUses(function_ref<bool(const Use &, bool &)> Pred, const AbstractAttribute &QueryingAA, - const Value &V, DepClassTy LivenessDepClass) { + const Value &V, bool CheckBBLivenessOnly, + DepClassTy LivenessDepClass) { // Check the trivial case first as it catches void values. if (V.use_empty()) return true; - // If the value is replaced by another one, for now a constant, we do not have - // uses. Note that this requires users of `checkForAllUses` to not recurse but - // instead use the `follow` callback argument to look at transitive users, - // however, that should be clear from the presence of the argument. - bool UsedAssumedInformation = false; - Optional<Constant *> C = - getAssumedConstant(V, QueryingAA, UsedAssumedInformation); - if (C.hasValue() && C.getValue()) { - LLVM_DEBUG(dbgs() << "[Attributor] Value is simplified, uses skipped: " << V - << " -> " << *C.getValue() << "\n"); - return true; - } - const IRPosition &IRP = QueryingAA.getIRPosition(); SmallVector<const Use *, 16> Worklist; SmallPtrSet<const Use *, 16> Visited; @@ -714,7 +1018,7 @@ bool Attributor::checkForAllUses(function_ref<bool(const Use &, bool &)> Pred, const Function *ScopeFn = IRP.getAnchorScope(); const auto *LivenessAA = ScopeFn ? &getAAFor<AAIsDead>(QueryingAA, IRPosition::function(*ScopeFn), - /* TrackDependence */ false) + DepClassTy::NONE) : nullptr; while (!Worklist.empty()) { @@ -723,8 +1027,9 @@ bool Attributor::checkForAllUses(function_ref<bool(const Use &, bool &)> Pred, continue; LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << " in " << *U->getUser() << "\n"); - if (isAssumedDead(*U, &QueryingAA, LivenessAA, - /* CheckBBLivenessOnly */ false, LivenessDepClass)) { + bool UsedAssumedInformation = false; + if (isAssumedDead(*U, &QueryingAA, LivenessAA, UsedAssumedInformation, + CheckBBLivenessOnly, LivenessDepClass)) { LLVM_DEBUG(dbgs() << "[Attributor] Dead use, skip!\n"); continue; } @@ -733,6 +1038,23 @@ bool Attributor::checkForAllUses(function_ref<bool(const Use &, bool &)> Pred, continue; } + if (auto *SI = dyn_cast<StoreInst>(U->getUser())) { + if (&SI->getOperandUse(0) == U) { + SmallSetVector<Value *, 4> PotentialCopies; + if (AA::getPotentialCopiesOfStoredValue(*this, *SI, PotentialCopies, + QueryingAA, + UsedAssumedInformation)) { + LLVM_DEBUG(dbgs() << "[Attributor] Value is stored, continue with " + << PotentialCopies.size() + << " potential copies instead!\n"); + for (Value *PotentialCopy : PotentialCopies) + for (const Use &U : PotentialCopy->uses()) + Worklist.push_back(&U); + continue; + } + } + } + bool Follow = false; if (!Pred(*U, Follow)) return false; @@ -787,7 +1109,9 @@ bool Attributor::checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred, const Use &U = *Uses[u]; LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << *U << " in " << *U.getUser() << "\n"); - if (isAssumedDead(U, QueryingAA, nullptr, /* CheckBBLivenessOnly */ true)) { + bool UsedAssumedInformation = false; + if (isAssumedDead(U, QueryingAA, nullptr, UsedAssumedInformation, + /* CheckBBLivenessOnly */ true)) { LLVM_DEBUG(dbgs() << "[Attributor] Dead use, skip!\n"); continue; } @@ -850,6 +1174,13 @@ bool Attributor::checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred, return true; } +bool Attributor::shouldPropagateCallBaseContext(const IRPosition &IRP) { + // TODO: Maintain a cache of Values that are + // on the pathway from a Argument to a Instruction that would effect the + // liveness/return state etc. + return EnableCallSiteSpecific; +} + bool Attributor::checkForAllReturnedValuesAndReturnInsts( function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred, const AbstractAttribute &QueryingAA) { @@ -865,7 +1196,8 @@ bool Attributor::checkForAllReturnedValuesAndReturnInsts( // and liveness information. // TODO: use the function scope once we have call site AAReturnedValues. const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction); - const auto &AARetVal = getAAFor<AAReturnedValues>(QueryingAA, QueryIRP); + const auto &AARetVal = + getAAFor<AAReturnedValues>(QueryingAA, QueryIRP, DepClassTy::REQUIRED); if (!AARetVal.getState().isValidState()) return false; @@ -881,8 +1213,10 @@ bool Attributor::checkForAllReturnedValues( return false; // TODO: use the function scope once we have call site AAReturnedValues. - const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction); - const auto &AARetVal = getAAFor<AAReturnedValues>(QueryingAA, QueryIRP); + const IRPosition &QueryIRP = IRPosition::function( + *AssociatedFunction, QueryingAA.getCallBaseContext()); + const auto &AARetVal = + getAAFor<AAReturnedValues>(QueryingAA, QueryIRP, DepClassTy::REQUIRED); if (!AARetVal.getState().isValidState()) return false; @@ -896,7 +1230,8 @@ static bool checkForAllInstructionsImpl( Attributor *A, InformationCache::OpcodeInstMapTy &OpcodeInstMap, function_ref<bool(Instruction &)> Pred, const AbstractAttribute *QueryingAA, const AAIsDead *LivenessAA, const ArrayRef<unsigned> &Opcodes, - bool CheckBBLivenessOnly = false) { + bool &UsedAssumedInformation, bool CheckBBLivenessOnly = false, + bool CheckPotentiallyDead = false) { for (unsigned Opcode : Opcodes) { // Check if we have instructions with this opcode at all first. auto *Insts = OpcodeInstMap.lookup(Opcode); @@ -905,8 +1240,9 @@ static bool checkForAllInstructionsImpl( for (Instruction *I : *Insts) { // Skip dead instructions. - if (A && A->isAssumedDead(IRPosition::value(*I), QueryingAA, LivenessAA, - CheckBBLivenessOnly)) + if (A && !CheckPotentiallyDead && + A->isAssumedDead(IRPosition::value(*I), QueryingAA, LivenessAA, + UsedAssumedInformation, CheckBBLivenessOnly)) continue; if (!Pred(*I)) @@ -919,7 +1255,9 @@ static bool checkForAllInstructionsImpl( bool Attributor::checkForAllInstructions(function_ref<bool(Instruction &)> Pred, const AbstractAttribute &QueryingAA, const ArrayRef<unsigned> &Opcodes, - bool CheckBBLivenessOnly) { + bool &UsedAssumedInformation, + bool CheckBBLivenessOnly, + bool CheckPotentiallyDead) { const IRPosition &IRP = QueryingAA.getIRPosition(); // Since we need to provide instructions we have to have an exact definition. @@ -927,24 +1265,29 @@ bool Attributor::checkForAllInstructions(function_ref<bool(Instruction &)> Pred, if (!AssociatedFunction) return false; + if (AssociatedFunction->isDeclaration()) + return false; + // TODO: use the function scope once we have call site AAReturnedValues. const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction); const auto *LivenessAA = - CheckBBLivenessOnly ? nullptr - : &(getAAFor<AAIsDead>(QueryingAA, QueryIRP, - /* TrackDependence */ false)); + (CheckBBLivenessOnly || CheckPotentiallyDead) + ? nullptr + : &(getAAFor<AAIsDead>(QueryingAA, QueryIRP, DepClassTy::NONE)); auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(*AssociatedFunction); if (!checkForAllInstructionsImpl(this, OpcodeInstMap, Pred, &QueryingAA, - LivenessAA, Opcodes, CheckBBLivenessOnly)) + LivenessAA, Opcodes, UsedAssumedInformation, + CheckBBLivenessOnly, CheckPotentiallyDead)) return false; return true; } bool Attributor::checkForAllReadWriteInstructions( - function_ref<bool(Instruction &)> Pred, AbstractAttribute &QueryingAA) { + function_ref<bool(Instruction &)> Pred, AbstractAttribute &QueryingAA, + bool &UsedAssumedInformation) { const Function *AssociatedFunction = QueryingAA.getIRPosition().getAssociatedFunction(); @@ -954,12 +1297,13 @@ bool Attributor::checkForAllReadWriteInstructions( // TODO: use the function scope once we have call site AAReturnedValues. const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction); const auto &LivenessAA = - getAAFor<AAIsDead>(QueryingAA, QueryIRP, /* TrackDependence */ false); + getAAFor<AAIsDead>(QueryingAA, QueryIRP, DepClassTy::NONE); for (Instruction *I : InfoCache.getReadOrWriteInstsForFunction(*AssociatedFunction)) { // Skip dead instructions. - if (isAssumedDead(IRPosition::value(*I), &QueryingAA, &LivenessAA)) + if (isAssumedDead(IRPosition::value(*I), &QueryingAA, &LivenessAA, + UsedAssumedInformation)) continue; if (!Pred(*I)) @@ -979,6 +1323,11 @@ void Attributor::runTillFixpoint() { // the abstract analysis. unsigned IterationCounter = 1; + unsigned MaxFixedPointIterations; + if (MaxFixpointIterations) + MaxFixedPointIterations = MaxFixpointIterations.getValue(); + else + MaxFixedPointIterations = SetFixpointIterations; SmallVector<AbstractAttribute *, 32> ChangedAAs; SetVector<AbstractAttribute *> Worklist, InvalidAAs; @@ -1058,7 +1407,7 @@ void Attributor::runTillFixpoint() { Worklist.clear(); Worklist.insert(ChangedAAs.begin(), ChangedAAs.end()); - } while (!Worklist.empty() && (IterationCounter++ < MaxFixpointIterations || + } while (!Worklist.empty() && (IterationCounter++ < MaxFixedPointIterations || VerifyMaxFixpointIterations)); LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: " @@ -1097,9 +1446,9 @@ void Attributor::runTillFixpoint() { }); if (VerifyMaxFixpointIterations && - IterationCounter != MaxFixpointIterations) { + IterationCounter != MaxFixedPointIterations) { errs() << "\n[Attributor] Fixpoint iteration done after: " - << IterationCounter << "/" << MaxFixpointIterations + << IterationCounter << "/" << MaxFixedPointIterations << " iterations\n"; llvm_unreachable("The fixpoint was not reached with exactly the number of " "specified iterations!"); @@ -1124,12 +1473,17 @@ ChangeStatus Attributor::manifestAttributes() { if (!State.isAtFixpoint()) State.indicateOptimisticFixpoint(); + // We must not manifest Attributes that use Callbase info. + if (AA->hasCallBaseContext()) + continue; // If the state is invalid, we do not try to manifest it. if (!State.isValidState()) continue; // Skip dead code. - if (isAssumedDead(*AA, nullptr, /* CheckBBLivenessOnly */ true)) + bool UsedAssumedInformation = false; + if (isAssumedDead(*AA, nullptr, UsedAssumedInformation, + /* CheckBBLivenessOnly */ true)) continue; // Check if the manifest debug counter that allows skipping manifestation of // AAs @@ -1174,6 +1528,10 @@ ChangeStatus Attributor::manifestAttributes() { } void Attributor::identifyDeadInternalFunctions() { + // Early exit if we don't intend to delete functions. + if (!DeleteFns) + return; + // Identify dead internal functions and delete them. This happens outside // the other fixpoint analysis as we might treat potentially dead functions // as live to lower the number of iterations. If they happen to be dead, the @@ -1218,40 +1576,68 @@ void Attributor::identifyDeadInternalFunctions() { ChangeStatus Attributor::cleanupIR() { TimeTraceScope TimeScope("Attributor::cleanupIR"); // Delete stuff at the end to avoid invalid references and a nice order. - LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least " + LLVM_DEBUG(dbgs() << "\n[Attributor] Delete/replace at least " << ToBeDeletedFunctions.size() << " functions and " << ToBeDeletedBlocks.size() << " blocks and " << ToBeDeletedInsts.size() << " instructions and " - << ToBeChangedUses.size() << " uses\n"); + << ToBeChangedValues.size() << " values and " + << ToBeChangedUses.size() << " uses. " + << "Preserve manifest added " << ManifestAddedBlocks.size() + << " blocks\n"); SmallVector<WeakTrackingVH, 32> DeadInsts; SmallVector<Instruction *, 32> TerminatorsToFold; - for (auto &It : ToBeChangedUses) { - Use *U = It.first; - Value *NewV = It.second; + auto ReplaceUse = [&](Use *U, Value *NewV) { Value *OldV = U->get(); + // If we plan to replace NewV we need to update it at this point. + do { + const auto &Entry = ToBeChangedValues.lookup(NewV); + if (!Entry.first) + break; + NewV = Entry.first; + } while (true); + // Do not replace uses in returns if the value is a must-tail call we will // not delete. - if (isa<ReturnInst>(U->getUser())) + if (auto *RI = dyn_cast<ReturnInst>(U->getUser())) { if (auto *CI = dyn_cast<CallInst>(OldV->stripPointerCasts())) - if (CI->isMustTailCall() && !ToBeDeletedInsts.count(CI)) - continue; + if (CI->isMustTailCall() && + (!ToBeDeletedInsts.count(CI) || !isRunOn(*CI->getCaller()))) + return; + // If we rewrite a return and the new value is not an argument, strip the + // `returned` attribute as it is wrong now. + if (!isa<Argument>(NewV)) + for (auto &Arg : RI->getFunction()->args()) + Arg.removeAttr(Attribute::Returned); + } + + // Do not perform call graph altering changes outside the SCC. + if (auto *CB = dyn_cast<CallBase>(U->getUser())) + if (CB->isCallee(U) && !isRunOn(*CB->getCaller())) + return; LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser() << " instead of " << *OldV << "\n"); U->set(NewV); - // Do not modify call instructions outside the SCC. - if (auto *CB = dyn_cast<CallBase>(OldV)) - if (!Functions.count(CB->getCaller())) - continue; + if (Instruction *I = dyn_cast<Instruction>(OldV)) { CGModifiedFunctions.insert(I->getFunction()); if (!isa<PHINode>(I) && !ToBeDeletedInsts.count(I) && isInstructionTriviallyDead(I)) DeadInsts.push_back(I); } + if (isa<UndefValue>(NewV) && isa<CallBase>(U->getUser())) { + auto *CB = cast<CallBase>(U->getUser()); + if (CB->isArgOperand(U)) { + unsigned Idx = CB->getArgOperandNo(U); + CB->removeParamAttr(Idx, Attribute::NoUndef); + Function *Fn = CB->getCalledFunction(); + if (Fn && Fn->arg_size() > Idx) + Fn->removeParamAttr(Idx, Attribute::NoUndef); + } + } if (isa<Constant>(NewV) && isa<BranchInst>(U->getUser())) { Instruction *UserI = cast<Instruction>(U->getUser()); if (isa<UndefValue>(NewV)) { @@ -1260,9 +1646,31 @@ ChangeStatus Attributor::cleanupIR() { TerminatorsToFold.push_back(UserI); } } + }; + + for (auto &It : ToBeChangedUses) { + Use *U = It.first; + Value *NewV = It.second; + ReplaceUse(U, NewV); + } + + SmallVector<Use *, 4> Uses; + for (auto &It : ToBeChangedValues) { + Value *OldV = It.first; + auto &Entry = It.second; + Value *NewV = Entry.first; + Uses.clear(); + for (auto &U : OldV->uses()) + if (Entry.second || !U.getUser()->isDroppable()) + Uses.push_back(&U); + for (Use *U : Uses) + ReplaceUse(U, NewV); } + for (auto &V : InvokeWithDeadSuccessor) if (InvokeInst *II = dyn_cast_or_null<InvokeInst>(V)) { + assert(isRunOn(*II->getFunction()) && + "Cannot replace an invoke outside the current SCC!"); bool UnwindBBIsDead = II->hasFnAttr(Attribute::NoUnwind); bool NormalBBIsDead = II->hasFnAttr(Attribute::NoReturn); bool Invoke2CallAllowed = @@ -1287,17 +1695,27 @@ ChangeStatus Attributor::cleanupIR() { } } for (Instruction *I : TerminatorsToFold) { + if (!isRunOn(*I->getFunction())) + continue; CGModifiedFunctions.insert(I->getFunction()); ConstantFoldTerminator(I->getParent()); } for (auto &V : ToBeChangedToUnreachableInsts) if (Instruction *I = dyn_cast_or_null<Instruction>(V)) { + if (!isRunOn(*I->getFunction())) + continue; CGModifiedFunctions.insert(I->getFunction()); - changeToUnreachable(I, /* UseLLVMTrap */ false); + changeToUnreachable(I); } for (auto &V : ToBeDeletedInsts) { if (Instruction *I = dyn_cast_or_null<Instruction>(V)) { + if (auto *CB = dyn_cast<CallBase>(I)) { + if (!isRunOn(*I->getFunction())) + continue; + if (!isa<IntrinsicInst>(CB)) + CGUpdater.removeCallSite(*CB); + } I->dropDroppableUses(); CGModifiedFunctions.insert(I->getFunction()); if (!I->getType()->isVoidTy()) @@ -1309,8 +1727,16 @@ ChangeStatus Attributor::cleanupIR() { } } - LLVM_DEBUG(dbgs() << "[Attributor] DeadInsts size: " << DeadInsts.size() - << "\n"); + llvm::erase_if(DeadInsts, [&](WeakTrackingVH I) { + return !I || !isRunOn(*cast<Instruction>(I)->getFunction()); + }); + + LLVM_DEBUG({ + dbgs() << "[Attributor] DeadInsts size: " << DeadInsts.size() << "\n"; + for (auto &I : DeadInsts) + if (I) + dbgs() << " - " << *I << "\n"; + }); RecursivelyDeleteTriviallyDeadInstructions(DeadInsts); @@ -1318,7 +1744,12 @@ ChangeStatus Attributor::cleanupIR() { SmallVector<BasicBlock *, 8> ToBeDeletedBBs; ToBeDeletedBBs.reserve(NumDeadBlocks); for (BasicBlock *BB : ToBeDeletedBlocks) { + assert(isRunOn(*BB->getParent()) && + "Cannot delete a block outside the current SCC!"); CGModifiedFunctions.insert(BB->getParent()); + // Do not delete BBs added during manifests of AAs. + if (ManifestAddedBlocks.contains(BB)) + continue; ToBeDeletedBBs.push_back(BB); } // Actually we do not delete the blocks but squash them into a single @@ -1333,7 +1764,7 @@ ChangeStatus Attributor::cleanupIR() { ChangeStatus ManifestChange = rewriteFunctionSignatures(CGModifiedFunctions); for (Function *Fn : CGModifiedFunctions) - if (!ToBeDeletedFunctions.count(Fn)) + if (!ToBeDeletedFunctions.count(Fn) && Functions.count(Fn)) CGUpdater.reanalyzeFunction(*Fn); for (Function *Fn : ToBeDeletedFunctions) { @@ -1381,6 +1812,10 @@ ChangeStatus Attributor::cleanupIR() { ChangeStatus Attributor::run() { TimeTraceScope TimeScope("Attributor::run"); + AttributorCallGraph ACallGraph(*this); + + if (PrintCallGraph) + ACallGraph.populateAll(); Phase = AttributorPhase::UPDATE; runTillFixpoint(); @@ -1401,6 +1836,9 @@ ChangeStatus Attributor::run() { Phase = AttributorPhase::CLEANUP; ChangeStatus CleanupChange = cleanupIR(); + if (PrintCallGraph) + ACallGraph.print(); + return ManifestChange | CleanupChange; } @@ -1417,7 +1855,9 @@ ChangeStatus Attributor::updateAA(AbstractAttribute &AA) { auto &AAState = AA.getState(); ChangeStatus CS = ChangeStatus::UNCHANGED; - if (!isAssumedDead(AA, nullptr, /* CheckBBLivenessOnly */ true)) + bool UsedAssumedInformation = false; + if (!isAssumedDead(AA, nullptr, UsedAssumedInformation, + /* CheckBBLivenessOnly */ true)) CS = AA.update(*this); if (DV.empty()) { @@ -1485,19 +1925,12 @@ void Attributor::createShallowWrapper(Function &F) { NumFnShallowWrappersCreated++; } -/// Make another copy of the function \p F such that the copied version has -/// internal linkage afterwards and can be analysed. Then we replace all uses -/// of the original function to the copied one -/// -/// Only non-exactly defined functions that have `linkonce_odr` or `weak_odr` -/// linkage can be internalized because these linkages guarantee that other -/// definitions with the same name have the same semantics as this one -/// -static Function *internalizeFunction(Function &F) { - assert(AllowDeepWrapper && "Cannot create a copy if not allowed."); - assert(!F.isDeclaration() && !F.hasExactDefinition() && - !GlobalValue::isInterposableLinkage(F.getLinkage()) && - "Trying to internalize function which cannot be internalized."); +Function *Attributor::internalizeFunction(Function &F, bool Force) { + if (!AllowDeepWrapper && !Force) + return nullptr; + if (F.isDeclaration() || F.hasLocalLinkage() || + GlobalValue::isInterposableLinkage(F.getLinkage())) + return nullptr; Module &M = *F.getParent(); FunctionType *FnTy = F.getFunctionType(); @@ -1515,7 +1948,8 @@ static Function *internalizeFunction(Function &F) { SmallVector<ReturnInst *, 8> Returns; // Copy the body of the original function to the new one - CloneFunctionInto(Copied, &F, VMap, /* ModuleLevelChanges */ false, Returns); + CloneFunctionInto(Copied, &F, VMap, CloneFunctionChangeType::LocalChangesOnly, + Returns); // Set the linakage and visibility late as CloneFunctionInto has some implicit // requirements. @@ -1526,7 +1960,8 @@ static Function *internalizeFunction(Function &F) { SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; F.getAllMetadata(MDs); for (auto MDIt : MDs) - Copied->addMetadata(MDIt.first, *MDIt.second); + if (!Copied->hasMetadata()) + Copied->addMetadata(MDIt.first, *MDIt.second); M.getFunctionList().insert(F.getIterator(), Copied); F.replaceAllUsesWith(Copied); @@ -1538,6 +1973,9 @@ static Function *internalizeFunction(Function &F) { bool Attributor::isValidFunctionSignatureRewrite( Argument &Arg, ArrayRef<Type *> ReplacementTypes) { + if (!RewriteSignatures) + return false; + auto CallSiteCanBeChanged = [](AbstractCallSite ACS) { // Forbid the call site to cast the function return type. If we need to // rewrite these functions we need to re-create a cast for the new call site @@ -1584,9 +2022,11 @@ bool Attributor::isValidFunctionSignatureRewrite( // Forbid must-tail calls for now. // TODO: + bool UsedAssumedInformation = false; auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(*Fn); if (!checkForAllInstructionsImpl(nullptr, OpcodeInstMap, InstPred, nullptr, - nullptr, {Instruction::Call})) { + nullptr, {Instruction::Call}, + UsedAssumedInformation)) { LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite due to instructions\n"); return false; } @@ -1696,6 +2136,7 @@ ChangeStatus Attributor::rewriteFunctionSignatures( // Create the new function body and insert it into the module. Function *NewFn = Function::Create(NewFnTy, OldFn->getLinkage(), OldFn->getAddressSpace(), ""); + Functions.insert(NewFn); OldFn->getParent()->getFunctionList().insert(OldFn->getIterator(), NewFn); NewFn->takeName(OldFn); NewFn->copyAttributesFrom(OldFn); @@ -1870,9 +2311,8 @@ void InformationCache::initializeInformationCache(const Function &CF, // Calls are interesting on their own, additionally: // For `llvm.assume` calls we also fill the KnowledgeMap as we find them. // For `must-tail` calls we remember the caller and callee. - if (IntrinsicInst *Assume = dyn_cast<IntrinsicInst>(&I)) { - if (Assume->getIntrinsicID() == Intrinsic::assume) - fillMapFromAssume(*Assume, KnowledgeMap); + if (auto *Assume = dyn_cast<AssumeInst>(&I)) { + fillMapFromAssume(*Assume, KnowledgeMap); } else if (cast<CallInst>(I).isMustTailCall()) { FI.ContainsMustTailCall = true; if (const Function *Callee = cast<CallInst>(I).getCalledFunction()) @@ -1892,6 +2332,8 @@ void InformationCache::initializeInformationCache(const Function &CF, // The alignment of a pointer is interesting for loads. case Instruction::Store: // The alignment of a pointer is interesting for stores. + case Instruction::Alloca: + case Instruction::AddrSpaceCast: IsInterestingOpcode = true; } if (IsInterestingOpcode) { @@ -1923,6 +2365,8 @@ InformationCache::FunctionInfo::~FunctionInfo() { void Attributor::recordDependence(const AbstractAttribute &FromAA, const AbstractAttribute &ToAA, DepClassTy DepClass) { + if (DepClass == DepClassTy::NONE) + return; // If we are outside of an update, thus before the actual fixpoint iteration // started (= when we create AAs), we do not track dependences because we will // put all AAs into the initial worklist anyway. @@ -1937,6 +2381,9 @@ void Attributor::rememberDependences() { assert(!DependenceStack.empty() && "No dependences to remember!"); for (DepInfo &DI : *DependenceStack.back()) { + assert((DI.DepClass == DepClassTy::REQUIRED || + DI.DepClass == DepClassTy::OPTIONAL) && + "Expected required or optional dependence (1 bit)!"); auto &DepAAs = const_cast<AbstractAttribute &>(*DI.FromAA).Deps; DepAAs.push_back(AbstractAttribute::DepTy( const_cast<AbstractAttribute *>(DI.ToAA), unsigned(DI.DepClass))); @@ -2036,8 +2483,11 @@ void Attributor::identifyDefaultAbstractAttributes(Function &F) { for (Argument &Arg : F.args()) { IRPosition ArgPos = IRPosition::argument(Arg); - // Every argument might be simplified. - getOrCreateAAFor<AAValueSimplify>(ArgPos); + // Every argument might be simplified. We have to go through the Attributor + // interface though as outside AAs can register custom simplification + // callbacks. + bool UsedAssumedInformation = false; + getAssumedSimplified(ArgPos, /* AA */ nullptr, UsedAssumedInformation); // Every argument might be dead. getOrCreateAAFor<AAIsDead>(ArgPos); @@ -2096,10 +2546,7 @@ void Attributor::identifyDefaultAbstractAttributes(Function &F) { if (!Callee->getReturnType()->isVoidTy() && !CB.use_empty()) { IRPosition CBRetPos = IRPosition::callsite_returned(CB); - - // Call site return integer values might be limited by a constant range. - if (Callee->getReturnType()->isIntegerTy()) - getOrCreateAAFor<AAValueConstantRange>(CBRetPos); + getOrCreateAAFor<AAValueSimplify>(CBRetPos); } for (int I = 0, E = CB.getNumArgOperands(); I < E; ++I) { @@ -2109,8 +2556,11 @@ void Attributor::identifyDefaultAbstractAttributes(Function &F) { // Every call site argument might be dead. getOrCreateAAFor<AAIsDead>(CBArgPos); - // Call site argument might be simplified. - getOrCreateAAFor<AAValueSimplify>(CBArgPos); + // Call site argument might be simplified. We have to go through the + // Attributor interface though as outside AAs can register custom + // simplification callbacks. + bool UsedAssumedInformation = false; + getAssumedSimplified(CBArgPos, /* AA */ nullptr, UsedAssumedInformation); // Every call site argument might be marked "noundef". getOrCreateAAFor<AANoUndef>(CBArgPos); @@ -2145,25 +2595,30 @@ void Attributor::identifyDefaultAbstractAttributes(Function &F) { auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); bool Success; + bool UsedAssumedInformation = false; Success = checkForAllInstructionsImpl( nullptr, OpcodeInstMap, CallSitePred, nullptr, nullptr, {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, - (unsigned)Instruction::Call}); + (unsigned)Instruction::Call}, + UsedAssumedInformation); (void)Success; assert(Success && "Expected the check call to be successful!"); auto LoadStorePred = [&](Instruction &I) -> bool { - if (isa<LoadInst>(I)) + if (isa<LoadInst>(I)) { getOrCreateAAFor<AAAlign>( IRPosition::value(*cast<LoadInst>(I).getPointerOperand())); - else + if (SimplifyAllLoads) + getOrCreateAAFor<AAValueSimplify>(IRPosition::value(I)); + } else getOrCreateAAFor<AAAlign>( IRPosition::value(*cast<StoreInst>(I).getPointerOperand())); return true; }; Success = checkForAllInstructionsImpl( nullptr, OpcodeInstMap, LoadStorePred, nullptr, nullptr, - {(unsigned)Instruction::Load, (unsigned)Instruction::Store}); + {(unsigned)Instruction::Load, (unsigned)Instruction::Store}, + UsedAssumedInformation); (void)Success; assert(Success && "Expected the check call to be successful!"); } @@ -2199,9 +2654,12 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, IRPosition::Kind AP) { raw_ostream &llvm::operator<<(raw_ostream &OS, const IRPosition &Pos) { const Value &AV = Pos.getAssociatedValue(); - return OS << "{" << Pos.getPositionKind() << ":" << AV.getName() << " [" - << Pos.getAnchorValue().getName() << "@" << Pos.getCallSiteArgNo() - << "]}"; + OS << "{" << Pos.getPositionKind() << ":" << AV.getName() << " [" + << Pos.getAnchorValue().getName() << "@" << Pos.getCallSiteArgNo() << "]"; + + if (Pos.hasCallBaseContext()) + OS << "[cb_context:" << *Pos.getCallBaseContext() << "]"; + return OS << "}"; } raw_ostream &llvm::operator<<(raw_ostream &OS, const IntegerRangeState &S) { @@ -2266,6 +2724,16 @@ void AbstractAttribute::printWithDeps(raw_ostream &OS) const { OS << '\n'; } + +raw_ostream &llvm::operator<<(raw_ostream &OS, + const AAPointerInfo::Access &Acc) { + OS << " [" << Acc.getKind() << "] " << *Acc.getRemoteInst(); + if (Acc.getLocalInst() != Acc.getRemoteInst()) + OS << " via " << *Acc.getLocalInst(); + if (Acc.getContent().hasValue()) + OS << " [" << *Acc.getContent() << "]"; + return OS; +} ///} /// ---------------------------------------------------------------------------- @@ -2275,16 +2743,22 @@ void AbstractAttribute::printWithDeps(raw_ostream &OS) const { static bool runAttributorOnFunctions(InformationCache &InfoCache, SetVector<Function *> &Functions, AnalysisGetter &AG, - CallGraphUpdater &CGUpdater) { + CallGraphUpdater &CGUpdater, + bool DeleteFns) { if (Functions.empty()) return false; - LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << Functions.size() - << " functions.\n"); + LLVM_DEBUG({ + dbgs() << "[Attributor] Run on module with " << Functions.size() + << " functions:\n"; + for (Function *Fn : Functions) + dbgs() << " - " << Fn->getName() << "\n"; + }); // Create an Attributor and initially empty information cache that is filled // while we identify default attribute opportunities. - Attributor A(Functions, InfoCache, CGUpdater); + Attributor A(Functions, InfoCache, CGUpdater, /* Allowed */ nullptr, + DeleteFns); // Create shallow wrappers for all functions that are not IPO amendable if (AllowShallowWrappers) @@ -2302,7 +2776,8 @@ static bool runAttributorOnFunctions(InformationCache &InfoCache, Function *F = Functions[u]; if (!F->isDeclaration() && !F->isDefinitionExact() && F->getNumUses() && !GlobalValue::isInterposableLinkage(F->getLinkage())) { - Function *NewF = internalizeFunction(*F); + Function *NewF = Attributor::internalizeFunction(*F); + assert(NewF && "Could not internalize function."); Functions.insert(NewF); // Update call graph @@ -2363,7 +2838,7 @@ void AADepGraph::dumpGraph() { std::error_code EC; - raw_fd_ostream File(Filename, EC, sys::fs::OF_Text); + raw_fd_ostream File(Filename, EC, sys::fs::OF_TextWithCRLF); if (!EC) llvm::WriteGraph(File, this); @@ -2387,7 +2862,8 @@ PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) { CallGraphUpdater CGUpdater; BumpPtrAllocator Allocator; InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr); - if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater)) { + if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater, + /* DeleteFns */ true)) { // FIXME: Think about passes we will preserve and add them here. return PreservedAnalyses::none(); } @@ -2414,7 +2890,8 @@ PreservedAnalyses AttributorCGSCCPass::run(LazyCallGraph::SCC &C, CGUpdater.initialize(CG, C, AM, UR); BumpPtrAllocator Allocator; InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions); - if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater)) { + if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater, + /* DeleteFns */ false)) { // FIXME: Think about passes we will preserve and add them here. PreservedAnalyses PA; PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); @@ -2489,7 +2966,8 @@ struct AttributorLegacyPass : public ModulePass { CallGraphUpdater CGUpdater; BumpPtrAllocator Allocator; InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr); - return runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater); + return runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater, + /* DeleteFns*/ true); } void getAnalysisUsage(AnalysisUsage &AU) const override { @@ -2525,7 +3003,8 @@ struct AttributorCGSCCLegacyPass : public CallGraphSCCPass { Module &M = *Functions.back()->getParent(); BumpPtrAllocator Allocator; InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions); - return runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater); + return runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater, + /* DeleteFns */ false); } void getAnalysisUsage(AnalysisUsage &AU) const override { |