Page MenuHomePhabricator
Differential D62687 Diff 202386 llvm/lib/Transforms/IPO/Attributor.cpp

Changeset View

Standalone View

View Options

llvm/lib/Transforms/IPO/Attributor.cpp

Show First 20 Lines • Show All 44 Lines • ▼ Show 20 Line(s)
45STATISTIC(NumAttributesManifested, 45​STATISTIC(NumAttributesManifested,
46 "Number of abstract attributes manifested in IR"); 46​ "Number of abstract attributes manifested in IR");
47 47​
48STATISTIC(NumFnUniqueReturned, "Number of function with unique return"); 48​STATISTIC(NumFnUniqueReturned, "Number of function with unique return");
49STATISTIC(NumFnKnownReturns, "Number of function with known return values"); 49​STATISTIC(NumFnKnownReturns, "Number of function with known return values");
50STATISTIC(NumFnArgumentReturned, 50​STATISTIC(NumFnArgumentReturned,
51 "Number of function arguments marked returned"); 51​ "Number of function arguments marked returned");
52 52​
53​STATISTIC(NumFnNoFree, "Number of function marked nofree");
54​
53// TODO: Determine a good default value. 55​// TODO: Determine a good default value.
54// 56​//
55// In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads 57​// In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
56// (when run with the first 5 abstract attributes). The results also indicate 58​// (when run with the first 5 abstract attributes). The results also indicate
57// that we never reach 32 iterations but always find a fixpoint sooner. 59​// that we never reach 32 iterations but always find a fixpoint sooner.
58// 60​//
59// This will become more evolved once we perform two interleaved fixpoint 61​// This will become more evolved once we perform two interleaved fixpoint
60// iterations: bottom-up and top-down. 62​// iterations: bottom-up and top-down.
▲ Show 20 Lines • Show All 113 Lines • ▼ Show 20 Line(s)
174}; 176​};
175 177​
176/// Helper to adjust the statistics. 178​/// Helper to adjust the statistics.
177static void bookkeeping(AbstractAttribute::ManifestPosition MP, 179​static void bookkeeping(AbstractAttribute::ManifestPosition MP,
178 const Attribute &Attr) { 180​ const Attribute &Attr) {
179 if (!AreStatisticsEnabled()) 181​ if (!AreStatisticsEnabled())
180 return; 182​ return;
181 183​
184​ if (Attr.isStringAttribute()) {
185​ StringRef StringAttr = Attr.getKindAsString();
lebedev.riUnsubmitted
Not Done
Reply

StringRef

lebedev.ri: StringRef
186​ if (StringAttr == "nofree") {
jdoerfertUnsubmitted
Not Done
Reply

We want an llvm::StringSwitch here.

We could also move the whole bookkeeping into the AbstractAttributes. That might actually be nicer.

jdoerfert: We want an llvm::StringSwitch here. We could also move the whole bookkeeping into the…
187​ NumFnNoFree++;
188​ }
189​ return;
190​ }
191​
182 if (!Attr.isEnumAttribute()) 192​ if (!Attr.isEnumAttribute())
183 return; 193​ return;
184 switch (Attr.getKindAsEnum()) { 194​ switch (Attr.getKindAsEnum()) {
185 case Attribute::Returned: 195​ case Attribute::Returned:
186 NumFnArgumentReturned++; 196​ NumFnArgumentReturned++;
187 return; 197​ return;
188 default: 198​ default:
189 return; 199​ return;
▲ Show 20 Lines • Show All 246 Lines • ▼ Show 20 Line(s)433 static void collectValuesRecursively(
436 gernericValueTraversal(V, UnusedBool, FollowValueCB, VisitValueCB); 446​ gernericValueTraversal(V, UnusedBool, FollowValueCB, VisitValueCB);
437 } 447​ }
438 448​
439public: 449​public:
440 /// See AbstractAttribute::AbstractAttribute(...). 450​ /// See AbstractAttribute::AbstractAttribute(...).
441 AAReturnedValuesImpl(Function &F, InformationCache &InfoCache) 451​ AAReturnedValuesImpl(Function &F, InformationCache &InfoCache)
442 : AAReturnedValues(F, InfoCache) { 452​ : AAReturnedValues(F, InfoCache) {
443 // We do not have an associated argument yet. 453​ // We do not have an associated argument yet.
444 AssociatedVal = nullptr; 454​ AssociatedVal = nullptr;
jdoerfertUnsubmitted
Not Done
Reply

Leftover comment.

jdoerfert: Leftover comment.
445 } 455​ }
446 456​
447 /// See AbstractAttribute::initialize(...). 457​ /// See AbstractAttribute::initialize(...).
448 void initialize(Attributor &A) override { 458​ void initialize(Attributor &A) override {
449 Function &F = cast<Function>(getAnchoredValue()); 459​ Function &F = cast<Function>(getAnchoredValue());
450 460​
451 // The map from instruction opcodes to those instructions in the function. 461​ // The map from instruction opcodes to those instructions in the function.
452 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); 462​ auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
▲ Show 20 Lines • Show All 242 Lines • ▼ Show 20 Line(s)605ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
695 if (!HasCallSite) { 705​ if (!HasCallSite) {
696 indicateOptimisticFixpoint(); 706​ indicateOptimisticFixpoint();
697 return ChangeStatus::CHANGED; 707​ return ChangeStatus::CHANGED;
698 } 708​ }
699 709​
700 return Changed; 710​ return Changed;
701} 711​}
702 712​
713​/// ------------------------ No-Free Attributes ----------------------------
714​
715​struct AANoFreeFunction : AbstractAttribute, BooleanState {
716​
jdoerfertUnsubmitted
Done
Reply

If you make it a struct you don't need the public anymore.

jdoerfert: If you make it a struct you don't need the `public` anymore.
717​ /// See AbstractAttribute::AbstractAttribute(...).
718​ AANoFreeFunction(Function &F, InformationCache &InfoCache)
719​ : AbstractAttribute(F, InfoCache) {}
720​
721​ /// See AbstractAttribute::getState()
722​ ///{
723​ AbstractState &getState() override { return *this; }
jdoerfertUnsubmitted
Done
Reply

Please add bool isAssumedNoFree() and bool isKnownNoFree().

jdoerfert: Please add `bool isAssumedNoFree()` and `bool isKnownNoFree()`.
724​ const AbstractState &getState() const override { return *this; }
725​ ///}
726​
727​ /// See AbstractAttribute::getManifestPosition().
728​ virtual ManifestPosition getManifestPosition() const override {
729​ return MP_FUNCTION;
730​ }
731​
jdoerfertUnsubmitted
Done
Reply

Comment and new line pls.

jdoerfert: Comment and new line pls.
732​ /// See AbstractAttribute::getAsStr().
733​ virtual const std::string getAsStr() const override {
734​ return getAssumed() ? "nofree" : "may-free";
735​ }
736​
737​ /// See AbstractAttribute::updateImpl(...).
738​ virtual ChangeStatus updateImpl(Attributor &A) override;
739​
740​ /// Return the deduced attributes in \p Attrs.
741​ virtual void
742​ getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const override {
743​ LLVMContext &Ctx = AnchoredVal.getContext();
744​ Attrs.emplace_back(Attribute::get(Ctx, "nofree"));
745​ }
746​
747​ /// See AbstractAttribute::getAttrKind().
748​ virtual Attribute::AttrKind getAttrKind() const override {
749​ return Attribute::None;
750​ }
751​
jdoerfertUnsubmitted
Done
Reply

Comments please.

jdoerfert: Comments please.
752​ /// Return true if "nofree" is assumed.
753​ bool isAssumedNoFree() const { return getAssumed(); }
754​
755​ /// Return true if "nofree" is known.
756​ bool isKnownNoFree() const { return getKnown(); }
757​
758​ /// FIXME: I tried ((AttrKind) - 2) for ID but I got exception so I use
jdoerfertUnsubmitted
Done
Reply

You can directly get the AnchorScope

jdoerfert: You can directly get the AnchorScope
759​ /// Attribute::None + 1 for now.
760​ static constexpr Attribute::AttrKind ID =
761​ Attribute::AttrKind(Attribute::None + 1);
762​};
763​
764​ChangeStatus AANoFreeFunction::updateImpl(Attributor &A) {
765​ Function &F = getAnchorScope();
766​
767​ // The map from instruction opcodes to those instructions in the function.
768​ auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
769​
jdoerfertUnsubmitted
Not Done
Reply

Do we have any intrinsic that might free memory? I would need to double check but I don't think we have one.

jdoerfert: Do we have any intrinsic that might free memory? I would need to double check but I don't think…
uenokuAuthorUnsubmitted
Done
Reply

I think so too. However, I have one concern. There are some intrinsic related to GC and I can not be sure whether these intrinsic wouldn't free memory.

uenoku: I think so too. However, I have one concern. There are some intrinsic related to GC and I can…
jdoerfertUnsubmitted
Not Done
Reply

That is a good point. Let's do the following:

  • Do not look at intrinsic here as at all so we are sound for sure (we should have a test for that!)
  • Annotate intrinsics in their ".td" file definition (different patch later on)
jdoerfert: That is a good point. Let's do the following: - Do not look at intrinsic here as at all so we…
770​ for (unsigned Opcode :
jdoerfertUnsubmitted
Done
Reply

I don't see why we'd need this conditional (and the Realloc check).

jdoerfert: I don't see why we'd need this conditional (and the Realloc check).
771​ {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
772​ (unsigned)Instruction::Call}) {
773​ for (Instruction *I : OpcodeInstMap[Opcode]) {
774​ // Assume that all intrinsic function wouldn't free memory.
775​ if (isa<IntrinsicInst>(I)) {
776​ continue;
777​ }
778​ auto *NoFreeAA = A.getAAFor<AANoFreeFunction>(*this, *I);
779​ if (!NoFreeAA || !NoFreeAA->isValidState() ||
780​ !NoFreeAA->isAssumedNoFree()) {
781​ indicatePessimisticFixpoint();
782​ return ChangeStatus::CHANGED;
783​ }
784​ }
785​ }
786​ return ChangeStatus::UNCHANGED;
787​}
788​
703/// ---------------------------------------------------------------------------- 789​/// ----------------------------------------------------------------------------
704/// Attributor 790​/// Attributor
705/// ---------------------------------------------------------------------------- 791​/// ----------------------------------------------------------------------------
706 792​
707ChangeStatus Attributor::run() { 793​ChangeStatus Attributor::run() {
708 // Initialize all abstract attributes. 794​ // Initialize all abstract attributes.
709 for (AbstractAttribute *AA : AllAbstractAttributes) 795​ for (AbstractAttribute *AA : AllAbstractAttributes)
710 AA->initialize(*this); 796​ AA->initialize(*this);
711 797​
712 LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized " 798​ LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
713 << AllAbstractAttributes.size() 799​ << AllAbstractAttributes.size()
jdoerfertUnsubmitted
Done
Reply

No need for the assert, and if you want one, add a message.

jdoerfert: No need for the assert, and if you want one, add a message.
714 << " abstract attributes.\n"); 800​ << " abstract attributes.\n");
jdoerfertUnsubmitted
Done
Reply

You can make safe indention if you continue for nofree call sites. Though, I don't see why we should check the attribute in the first place. The following check is what we want.

jdoerfert: You can make safe indention if you continue for `nofree` call sites. Though, I don't see why we…
jdoerfertUnsubmitted
Not Done
Reply

My other two comments were confusing and I should have explained this better.

The idea (I have) is:
Information should be determined through other attributes if possible. That way we do not need to look at the IR in different places and also ask if an attribute exist and what the status is. That would mean do not look at the IR attributes (through the CallSite). I also confused you with the isAssumedNoFree as it seems. I did want that in addition to the two checks you had, so !NoFreeAA, !NoFreeAA->getState().hasValidState(), and !NoFreeAA->isAssumedNoFree(), even though the last two are equivalent it makes it easier to read and consistent with more complex attributes.

jdoerfert: My other two comments were confusing and I should have explained this better. The idea (I…
uenokuAuthorUnsubmitted
Done
Reply

I have a question about this.
As you said I changed not to look IR attributes. Then I don't know how to deal with a function declaration like this:

declare void @nofree_function() "nofree" 

define void @call_nofree_function() {
    tail call void @nofree_function()
    ret void
}
uenoku: I have a question about this. As you said I changed not to look IR attributes. Then I don't…
jdoerfertUnsubmitted
Not Done
Reply

Good point, very good point. Let's agree that I was wrong for now and you add back the ImmutableCallSite attribute check.

jdoerfert: Good point, very good point. Let's agree that I was wrong for now and you add back the…
715 801​
716 // Now that all abstract attributes are collected and initialized we start the 802​ // Now that all abstract attributes are collected and initialized we start the
jdoerfertUnsubmitted
Done
Reply

Please add || !NoFreeAA->isAssumedNoFree() for concistency.

Revert the condition for less indented code.

jdoerfert: Please add `|| !NoFreeAA->isAssumedNoFree()` for concistency. Revert the condition for less…
717 // abstract analysis. 803​ // abstract analysis.
718 804​
719 unsigned IterationCounter = 1; 805​ unsigned IterationCounter = 1;
720 806​
721 SmallVector<AbstractAttribute *, 64> ChangedAAs; 807​ SmallVector<AbstractAttribute *, 64> ChangedAAs;
722 SetVector<AbstractAttribute *> Worklist; 808​ SetVector<AbstractAttribute *> Worklist;
723 Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end()); 809​ Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
jdoerfertUnsubmitted
Done
Reply

There is no fixpoint reached here, at least not if getAAFor was called at least once! Just remove the line and let the framework determine this for you.

jdoerfert: There is no fixpoint reached here, at least not if `getAAFor` was called at least once! Just…
724 810​
725 do { 811​ do {
726 LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter 812​ LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
727 << ", Worklist size: " << Worklist.size() << "\n"); 813​ << ", Worklist size: " << Worklist.size() << "\n");
728 814​
729 // Add all abstract attributes that are potentially dependent on one that 815​ // Add all abstract attributes that are potentially dependent on one that
730 // changed to the work list. 816​ // changed to the work list.
731 for (AbstractAttribute *ChangedAA : ChangedAAs) { 817​ for (AbstractAttribute *ChangedAA : ChangedAAs) {
▲ Show 20 Lines • Show All 112 Lines • ▼ Show 20 Line(s)925void Attributor::identifyDefaultAbstractAttributes(
844 Type *ReturnType = F.getReturnType(); 930​ Type *ReturnType = F.getReturnType();
845 if (!ReturnType->isVoidTy()) { 931​ if (!ReturnType->isVoidTy()) {
846 // Argument attribute "returned" --- Create only one per function even 932​ // Argument attribute "returned" --- Create only one per function even
847 // though it is an argument attribute. 933​ // though it is an argument attribute.
848 if (!Whitelist || Whitelist->count(AAReturnedValues::ID)) 934​ if (!Whitelist || Whitelist->count(AAReturnedValues::ID))
849 registerAA(*new AAReturnedValuesImpl(F, InfoCache)); 935​ registerAA(*new AAReturnedValuesImpl(F, InfoCache));
850 } 936​ }
851 937​
938​ // Every function might be "no-free".
939​ registerAA(*new AANoFreeFunction(F, InfoCache));
940​
852 // Walk all instructions to find more attribute opportunities and also 941​ // Walk all instructions to find more attribute opportunities and also
853 // interesting instructions that might be queried by abstract attributes 942​ // interesting instructions that might be queried by abstract attributes
854 // during their initialization or update. 943​ // during their initialization or update.
855 auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F]; 944​ auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
856 auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F]; 945​ auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
857 946​
858 for (Instruction &I : instructions(&F)) { 947​ for (Instruction &I : instructions(&F)) {
859 bool IsInterestingOpcode = false; 948​ bool IsInterestingOpcode = false;
860 949​
861 switch (I.getOpcode()) { 950​ switch (I.getOpcode()) {
862 default: 951​ default:
952​ assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
953​ "New call site/base instruction type needs to be known in the "
954​ "attributor!");
jdoerfertUnsubmitted
Done
Reply

Please add an assert here to make sure we did not miss any CallBase instruction opcode.

jdoerfert: Please add an `assert` here to make sure we did not miss any CallBase instruction opcode.
863 break; 955​ break;
956​ case Instruction::Call:
957​ case Instruction::CallBr:
958​ case Instruction::Invoke:
959​ // Call-like instructions are interesting for AANoFreeFunction.
864 case Instruction::Ret: // ReturnInst are interesting for AAReturnedValues. 960​ case Instruction::Ret: // ReturnInst are interesting for AAReturnedValues.
865 IsInterestingOpcode = true; 961​ IsInterestingOpcode = true;
866 } 962​ }
867 if (IsInterestingOpcode) 963​ if (IsInterestingOpcode)
868 InstOpcodeMap[I.getOpcode()].push_back(&I); 964​ InstOpcodeMap[I.getOpcode()].push_back(&I);
869 if (I.mayReadOrWriteMemory()) 965​ if (I.mayReadOrWriteMemory())
870 ReadOrWriteInsts.push_back(&I); 966​ ReadOrWriteInsts.push_back(&I);
871 } 967​ }
▲ Show 20 Lines • Show All 91 Lines • ▼ Show 20 Line(s)1054PreservedAnalyses AttributorPass::run(LazyCallGraph::SCC &C,
963 for (LazyCallGraph::Node &N : C) { 1059​ for (LazyCallGraph::Node &N : C) {
964 Function &Fn = N.getFunction(); 1060​ Function &Fn = N.getFunction();
965 if (!Fn.isDeclaration()) 1061​ if (!Fn.isDeclaration())
966 SCCFunctions.push_back(&Fn); 1062​ SCCFunctions.push_back(&Fn);
967 } 1063​ }
968 1064​
969 if (runAttributorOnSCC(SCCFunctions)) 1065​ if (runAttributorOnSCC(SCCFunctions))
970 return PreservedAnalyses::none(); 1066​ return PreservedAnalyses::none();
971 return PreservedAnalyses::all(); 1067​ return PreservedAnalyses::all();
lebedev.riUnsubmitted
Done
Reply

Hm, there is no .empty() ?

lebedev.ri: Hm, there is no .empty() ?
972} 1068​}
973 1069​
974namespace { 1070​namespace {
975 1071​
976struct AttributorLegacyPass : public CallGraphSCCPass { 1072​struct AttributorLegacyPass : public CallGraphSCCPass {
977 static char ID; 1073​ static char ID;
978 1074​
979 AttributorLegacyPass() : CallGraphSCCPass(ID) { 1075​ AttributorLegacyPass() : CallGraphSCCPass(ID) {
Show All 33 Lines