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 @@ -642,6 +642,23 @@ /// Abstract Attribute Classes /// ---------------------------------------------------------------------------- +struct AANoUnwind : public AbstractAttribute { + /// An abstract interface for all nosync attributes. + AANoUnwind(Value &V, InformationCache &InfoCache) + : AbstractAttribute(V, InfoCache) {} + + /// See AbstractAttribute::getAttrKind()/ + virtual Attribute::AttrKind getAttrKind() const override { return ID; } + + static constexpr Attribute::AttrKind ID = Attribute::NoUnwind; + + /// Returns true if nounwind is assumed. + virtual bool isAssumedNoUnwind() const = 0; + + /// Returns true if nounwind is known. + virtual bool isKnownNoUnwind() const = 0; +}; + } // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H 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 @@ -42,6 +42,7 @@ "Number of abstract attributes in a valid fixpoint state"); STATISTIC(NumAttributesManifested, "Number of abstract attributes manifested in IR"); +STATISTIC(NumFnNoUnwind, "Number of functions marked nounwind"); // TODO: Determine a good default value. // @@ -86,10 +87,13 @@ if (!Attr.isEnumAttribute()) return; - //switch (Attr.getKindAsEnum()) { - //default: - // return; - //} + switch (Attr.getKindAsEnum()) { + case Attribute::NoUnwind: + NumFnNoUnwind++; + return; + default: + return; + } } /// Helper to identify the correct offset into an attribute list. @@ -241,148 +245,211 @@ return const_cast(this)->getAnchorScope(); } -/// ---------------------------------------------------------------------------- -/// Attributor -/// ---------------------------------------------------------------------------- - -ChangeStatus Attributor::run() { - // Initialize all abstract attributes. - for (AbstractAttribute *AA : AllAbstractAttributes) - AA->initialize(*this); - - LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized " - << AllAbstractAttributes.size() - << " abstract attributes.\n"); - - // Now that all abstract attributes are collected and initialized we start the - // abstract analysis. - - unsigned IterationCounter = 1; - - SmallVector ChangedAAs; - SetVector Worklist; - Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end()); - - do { - LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter - << ", Worklist size: " << Worklist.size() << "\n"); - - // Add all abstract attributes that are potentially dependent on one that - // changed to the work list. - for (AbstractAttribute *ChangedAA : ChangedAAs) { - auto &QuerriedAAs = QueryMap[ChangedAA]; - Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end()); - } +/// -----------------------NoUnwind Function Attribute-------------------------- - // Reset the changed set. - ChangedAAs.clear(); - - // Update all abstract attribute in the work list and record the ones that - // changed. - for (AbstractAttribute *AA : Worklist) - if (AA->update(*this) == ChangeStatus::CHANGED) - ChangedAAs.push_back(AA); - - // Reset the work list and repopulate with the changed abstract attributes. - // Note that dependent ones are added above. - Worklist.clear(); - Worklist.insert(ChangedAAs.begin(), ChangedAAs.end()); - - } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations); - - LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: " - << IterationCounter << "/" << MaxFixpointIterations - << " iterations\n"); - - bool FinishedAtFixpoint = Worklist.empty(); - - // Reset abstract arguments not settled in a sound fixpoint by now. This - // happens when we stopped the fixpoint iteration early. Note that only the - // ones marked as "changed" *and* the ones transitively depending on them - // need to be reverted to a pessimistic state. Others might not be in a - // fixpoint state but we can use the optimistic results for them anyway. - SmallPtrSet Visited; - for (unsigned u = 0; u < ChangedAAs.size(); u++) { - AbstractAttribute *ChangedAA = ChangedAAs[u]; - if (!Visited.insert(ChangedAA).second) - continue; +struct AANoUnwindFunction : AANoUnwind, BooleanState { - AbstractState &State = ChangedAA->getState(); - if (!State.isAtFixpoint()) { - State.indicatePessimisticFixpoint(); + AANoUnwindFunction(Function &F, InformationCache &InfoCache) + : AANoUnwind(F, InfoCache) {} - NumAttributesTimedOut++; - } + /// See AbstractAttribute::getState() + /// { + AbstractState &getState() override { return *this; } + const AbstractState &getState() const override { return *this; } + /// } - auto &QuerriedAAs = QueryMap[ChangedAA]; - ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end()); + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_FUNCTION; } - LLVM_DEBUG({ - if (!Visited.empty()) - dbgs() << "\n[Attributor] Finalized " << Visited.size() - << " abstract attributes.\n"; - }); - - unsigned NumManifested = 0; - unsigned NumAtFixpoint = 0; - ChangeStatus ManifestChange = ChangeStatus::UNCHANGED; - for (AbstractAttribute *AA : AllAbstractAttributes) { - AbstractState &State = AA->getState(); - - // If there is not already a fixpoint reached, we can now take the - // optimistic state. This is correct because we enforced a pessimistic one - // on abstract attributes that were transitively dependent on a changed one - // already above. - if (!State.isAtFixpoint()) - State.indicateOptimisticFixpoint(); - - // If the state is invalid, we do not try to manifest it. - if (!State.isValidState()) - continue; + virtual const std::string getAsStr() const override { + return getAssumed() ? "nounwind" : "may-unwind"; + } - // Manifest the state and record if we changed the IR. - ChangeStatus LocalChange = AA->manifest(*this); - ManifestChange = ManifestChange | LocalChange; + /// See AbstractAttribute::updateImpl(...). + virtual ChangeStatus updateImpl(Attributor &A) override; - NumAtFixpoint++; - NumManifested += (LocalChange == ChangeStatus::CHANGED); - } + /// See AANoUnwind::isAssumedNoUnwind(). + virtual bool isAssumedNoUnwind() const override { return getAssumed(); } - (void)NumManifested; - (void)NumAtFixpoint; - LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested - << " arguments while " << NumAtFixpoint - << " were in a valid fixpoint state\n"); - - // If verification is requested, we finished this run at a fixpoint, and the - // IR was changed, we re-run the whole fixpoint analysis, starting at - // re-initialization of the arguments. This re-run should not result in an IR - // change. Though, the (virtual) state of attributes at the end of the re-run - // might be more optimistic than the known state or the IR state if the better - // state cannot be manifested. - if (VerifyAttributor && FinishedAtFixpoint && - ManifestChange == ChangeStatus::CHANGED) { - VerifyAttributor = false; - ChangeStatus VerifyStatus = run(); - if (VerifyStatus != ChangeStatus::UNCHANGED) - llvm_unreachable( - "Attributor verification failed, re-run did result in an IR change " - "even after a fixpoint was reached in the original run. (False " - "positives possible!)"); - VerifyAttributor = true; - } + /// See AANoUnwind::isKnownNoUnwind(). + virtual bool isKnownNoUnwind() const override { return getKnown(); } +}; - NumAttributesManifested += NumManifested; - NumAttributesValidFixpoint += NumAtFixpoint; +ChangeStatus AANoUnwindFunction::updateImpl(Attributor &A){ + Function &F = getAnchorScope(); + + // The map from instruction opcodes to those instructions in the function. + auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); + auto Opcodes = { + (unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, + (unsigned)Instruction::Call, (unsigned)Instruction::CleanupRet, + (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume}; + + for (unsigned Opcode : Opcodes) { + for (Instruction *I : OpcodeInstMap[Opcode]) { + if(!I->mayThrow()) + continue; + + auto *NoUnwindAA = A.getAAFor(*this, *I); + + if (!NoUnwindAA || !NoUnwindAA->isAssumedNoUnwind()) { + indicatePessimisticFixpoint(); + return ChangeStatus::CHANGED; + } + } + } + return ChangeStatus::UNCHANGED; +} - return ManifestChange; + /// ---------------------------------------------------------------------------- + /// Attributor + /// ---------------------------------------------------------------------------- + + ChangeStatus Attributor::run() { + // Initialize all abstract attributes. + for (AbstractAttribute *AA : AllAbstractAttributes) + AA->initialize(*this); + + LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized " + << AllAbstractAttributes.size() + << " abstract attributes.\n"); + + // Now that all abstract attributes are collected and initialized we start + // the abstract analysis. + + unsigned IterationCounter = 1; + + SmallVector ChangedAAs; + SetVector Worklist; + Worklist.insert(AllAbstractAttributes.begin(), + AllAbstractAttributes.end()); + + do { + LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter + << ", Worklist size: " << Worklist.size() << "\n"); + + // Add all abstract attributes that are potentially dependent on one that + // changed to the work list. + for (AbstractAttribute *ChangedAA : ChangedAAs) { + auto &QuerriedAAs = QueryMap[ChangedAA]; + Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end()); + } + + // Reset the changed set. + ChangedAAs.clear(); + + // Update all abstract attribute in the work list and record the ones + // that changed. + for (AbstractAttribute *AA : Worklist) + if (AA->update(*this) == ChangeStatus::CHANGED) + ChangedAAs.push_back(AA); + + // Reset the work list and repopulate with the changed abstract + // attributes. Note that dependent ones are added above. + Worklist.clear(); + Worklist.insert(ChangedAAs.begin(), ChangedAAs.end()); + + } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations); + + LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: " + << IterationCounter << "/" << MaxFixpointIterations + << " iterations\n"); + + bool FinishedAtFixpoint = Worklist.empty(); + + // Reset abstract arguments not settled in a sound fixpoint by now. This + // happens when we stopped the fixpoint iteration early. Note that only the + // ones marked as "changed" *and* the ones transitively depending on them + // need to be reverted to a pessimistic state. Others might not be in a + // fixpoint state but we can use the optimistic results for them anyway. + SmallPtrSet Visited; + for (unsigned u = 0; u < ChangedAAs.size(); u++) { + AbstractAttribute *ChangedAA = ChangedAAs[u]; + if (!Visited.insert(ChangedAA).second) + continue; + + AbstractState &State = ChangedAA->getState(); + if (!State.isAtFixpoint()) { + State.indicatePessimisticFixpoint(); + + NumAttributesTimedOut++; + } + + auto &QuerriedAAs = QueryMap[ChangedAA]; + ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end()); + } + + LLVM_DEBUG({ + if (!Visited.empty()) + dbgs() << "\n[Attributor] Finalized " << Visited.size() + << " abstract attributes.\n"; + }); + + unsigned NumManifested = 0; + unsigned NumAtFixpoint = 0; + ChangeStatus ManifestChange = ChangeStatus::UNCHANGED; + for (AbstractAttribute *AA : AllAbstractAttributes) { + AbstractState &State = AA->getState(); + + // If there is not already a fixpoint reached, we can now take the + // optimistic state. This is correct because we enforced a pessimistic + // one on abstract attributes that were transitively dependent on a + // changed one already above. + if (!State.isAtFixpoint()) + State.indicateOptimisticFixpoint(); + + // If the state is invalid, we do not try to manifest it. + if (!State.isValidState()) + continue; + + // Manifest the state and record if we changed the IR. + ChangeStatus LocalChange = AA->manifest(*this); + ManifestChange = ManifestChange | LocalChange; + + NumAtFixpoint++; + NumManifested += (LocalChange == ChangeStatus::CHANGED); + } + + (void)NumManifested; + (void)NumAtFixpoint; + LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested + << " arguments while " << NumAtFixpoint + << " were in a valid fixpoint state\n"); + + // If verification is requested, we finished this run at a fixpoint, and + // the IR was changed, we re-run the whole fixpoint analysis, starting at + // re-initialization of the arguments. This re-run should not result in an + // IR change. Though, the (virtual) state of attributes at the end of the + // re-run might be more optimistic than the known state or the IR state if + // the better state cannot be manifested. + if (VerifyAttributor && FinishedAtFixpoint && + ManifestChange == ChangeStatus::CHANGED) { + VerifyAttributor = false; + ChangeStatus VerifyStatus = run(); + if (VerifyStatus != ChangeStatus::UNCHANGED) + llvm_unreachable( + "Attributor verification failed, re-run did result in an IR " + "change " + "even after a fixpoint was reached in the original run. (False " + "positives possible!)"); + VerifyAttributor = true; + } + + NumAttributesManifested += NumManifested; + NumAttributesValidFixpoint += NumAtFixpoint; + + return ManifestChange; } void Attributor::identifyDefaultAbstractAttributes( Function &F, InformationCache &InfoCache, DenseSet *Whitelist) { + // Every function can be nounwind. + registerAA(*new AANoUnwindFunction(F, InfoCache)); + // Walk all instructions to find more attribute opportunities and also // interesting instructions that might be queried by abstract attributes // during their initialization or update. @@ -397,10 +464,20 @@ // to concrete attributes we only cache the ones that are as identified in // the following switch. // Note: There are no concrete attributes now so this is initially empty. - //switch (I.getOpcode()) { - //default: - // break; - //} + switch (I.getOpcode()) { + default: + assert((!ImmutableCallSite(&I)) && (!isa(&I)) && + "New call site/base instruction type needs to be known int the " + "attributor."); + break; + case Instruction::Call: + case Instruction::CallBr: + case Instruction::Invoke: + case Instruction::CleanupRet: + case Instruction::CatchSwitch: + case Instruction::Resume: + IsInterestingOpcode = true; + } if (IsInterestingOpcode) InstOpcodeMap[I.getOpcode()].push_back(&I); if (I.mayReadOrWriteMemory()) diff --git a/llvm/test/Transforms/FunctionAttrs/nounwind.ll b/llvm/test/Transforms/FunctionAttrs/nounwind.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/FunctionAttrs/nounwind.ll @@ -0,0 +1,101 @@ +; RUN: opt < %s -functionattrs -S | FileCheck %s +; RUN: opt < %S -attributor -S | FileCheck %s --check-prefix=ATTRIBUTOR + +; TEST 1 +; CHECK: Function Attrs: norecurse, nounwind readnone +; CHECK-NEXT: define i32 @leaf() +; ATTRIBUTOR: Function Attrs: nounwind +; ATTRIBUTOR-NEXT: define i32 @leaf() +define i32 @foo1() { + ret i32 1 +} + +; TEST 2 +; CHECK: Function Attrs: nounwind readnone +; CHECK-NEXT: define i32 @scc1_foo() +; ATTRIBUTOR: Function Attrs: nounwind +; ATTRIBUTOR-NEXT: define i32 @scc1_foo() +define i32 @scc1_foo() { + %1 = call i32 @scc1_bar() + ret i32 1 +} + + +; TEST 3 +; CHECK: Function Attrs: nounwind readnone +; CHECK-NEXT: define i32 @scc1_bar() +; ATTRIBUTOR: Function Attrs: nounwind +; ATTRIBUTOR-NEXT: define i32 @scc1_bar() +define i32 @scc1_bar() { + %1 = call i32 @scc1_foo() + ret i32 1 +} + +; CHECK-NOT: nounwind +; CHECK-NEXT: declare i32 @non_nounwind() +declare i32 @non_nounwind() + +; TEST 4 +; CHECK-NOT: nounwind +; CHECK-NEXT: define void @call_non_nounwind() +; ATTRIBUTOR: define void @call_non_nounwind() +define void @call_non_nounwind(){ + tail call i32 @non_nounwind() + ret void +} + +; TEST 5 - throw +; int maybe_throw(bool canThrow) { +; if (canThrow) +; throw; +; else +; return -1; +; } + +; CHECK: define i32 @maybe_throw(i1 zeroext) +; ATTRIBUTOR: define i32 @maybe_throw(i1 zeroext) +define i32 @maybe_throw(i1 zeroext) { + br i1 %0, label %2, label %3 + +2: ; preds = %1 + tail call void @__cxa_rethrow() #1 + unreachable + +3: ; preds = %1 + ret i32 -1 +} + +declare void @__cxa_rethrow() + +; TEST 6 - catch +; int catch_thing() { +; try { +; int a = doThing(true); +; } +; catch(...) { return -1; } +; return 1; +; } + +; CHECK: define i32 @catch_thing() +; ATTRIBUTOR: define i32 @catch_thing() +define i32 @catch_thing() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) { + invoke void @__cxa_rethrow() #1 + to label %1 unwind label %2 + +1: ; preds = %0 + unreachable + +2: ; preds = %0 + %3 = landingpad { i8*, i32 } + catch i8* null + %4 = extractvalue { i8*, i32 } %3, 0 + %5 = tail call i8* @__cxa_begin_catch(i8* %4) #2 + tail call void @__cxa_end_catch() + ret i32 -1 +} + +declare i32 @__gxx_personality_v0(...) + +declare i8* @__cxa_begin_catch(i8*) + +declare void @__cxa_end_catch()