1 //===- Attributor.cpp - Module-wide attribute deduction -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements an interprocedural pass that deduces and/or propagates
10 // attributes. This is done in an abstract interpretation style fixpoint
11 // iteration. See the Attributor.h file comment and the class descriptions in
12 // that file for more information.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "llvm/Transforms/IPO/Attributor.h"
17
18 #include "llvm/ADT/GraphTraits.h"
19 #include "llvm/ADT/PointerIntPair.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/ADT/TinyPtrVector.h"
22 #include "llvm/Analysis/InlineCost.h"
23 #include "llvm/Analysis/LazyValueInfo.h"
24 #include "llvm/Analysis/MemorySSAUpdater.h"
25 #include "llvm/Analysis/MustExecute.h"
26 #include "llvm/Analysis/ValueTracking.h"
27 #include "llvm/IR/Attributes.h"
28 #include "llvm/IR/GlobalValue.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/NoFolder.h"
31 #include "llvm/IR/Verifier.h"
32 #include "llvm/InitializePasses.h"
33 #include "llvm/Support/Casting.h"
34 #include "llvm/Support/CommandLine.h"
35 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/DebugCounter.h"
37 #include "llvm/Support/FileSystem.h"
38 #include "llvm/Support/GraphWriter.h"
39 #include "llvm/Support/raw_ostream.h"
40 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
41 #include "llvm/Transforms/Utils/Cloning.h"
42 #include "llvm/Transforms/Utils/Local.h"
43
44 #include <cassert>
45 #include <string>
46
47 using namespace llvm;
48
49 #define DEBUG_TYPE "attributor"
50
51 DEBUG_COUNTER(ManifestDBGCounter, "attributor-manifest",
52 "Determine what attributes are manifested in the IR");
53
54 STATISTIC(NumFnDeleted, "Number of function deleted");
55 STATISTIC(NumFnWithExactDefinition,
56 "Number of functions with exact definitions");
57 STATISTIC(NumFnWithoutExactDefinition,
58 "Number of functions without exact definitions");
59 STATISTIC(NumFnShallowWrappersCreated, "Number of shallow wrappers created");
60 STATISTIC(NumAttributesTimedOut,
61 "Number of abstract attributes timed out before fixpoint");
62 STATISTIC(NumAttributesValidFixpoint,
63 "Number of abstract attributes in a valid fixpoint state");
64 STATISTIC(NumAttributesManifested,
65 "Number of abstract attributes manifested in IR");
66
67 // TODO: Determine a good default value.
68 //
69 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
70 // (when run with the first 5 abstract attributes). The results also indicate
71 // that we never reach 32 iterations but always find a fixpoint sooner.
72 //
73 // This will become more evolved once we perform two interleaved fixpoint
74 // iterations: bottom-up and top-down.
75 static cl::opt<unsigned>
76 MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
77 cl::desc("Maximal number of fixpoint iterations."),
78 cl::init(32));
79
80 static cl::opt<unsigned, true> MaxInitializationChainLengthX(
81 "attributor-max-initialization-chain-length", cl::Hidden,
82 cl::desc(
83 "Maximal number of chained initializations (to avoid stack overflows)"),
84 cl::location(MaxInitializationChainLength), cl::init(1024));
85 unsigned llvm::MaxInitializationChainLength;
86
87 static cl::opt<bool> VerifyMaxFixpointIterations(
88 "attributor-max-iterations-verify", cl::Hidden,
89 cl::desc("Verify that max-iterations is a tight bound for a fixpoint"),
90 cl::init(false));
91
92 static cl::opt<bool> AnnotateDeclarationCallSites(
93 "attributor-annotate-decl-cs", cl::Hidden,
94 cl::desc("Annotate call sites of function declarations."), cl::init(false));
95
96 static cl::opt<bool> EnableHeapToStack("enable-heap-to-stack-conversion",
97 cl::init(true), cl::Hidden);
98
99 static cl::opt<bool>
100 AllowShallowWrappers("attributor-allow-shallow-wrappers", cl::Hidden,
101 cl::desc("Allow the Attributor to create shallow "
102 "wrappers for non-exact definitions."),
103 cl::init(false));
104
105 static cl::opt<bool>
106 AllowDeepWrapper("attributor-allow-deep-wrappers", cl::Hidden,
107 cl::desc("Allow the Attributor to use IP information "
108 "derived from non-exact functions via cloning"),
109 cl::init(false));
110
111 // These options can only used for debug builds.
112 #ifndef NDEBUG
113 static cl::list<std::string>
114 SeedAllowList("attributor-seed-allow-list", cl::Hidden,
115 cl::desc("Comma seperated list of attribute names that are "
116 "allowed to be seeded."),
117 cl::ZeroOrMore, cl::CommaSeparated);
118
119 static cl::list<std::string> FunctionSeedAllowList(
120 "attributor-function-seed-allow-list", cl::Hidden,
121 cl::desc("Comma seperated list of function names that are "
122 "allowed to be seeded."),
123 cl::ZeroOrMore, cl::CommaSeparated);
124 #endif
125
126 static cl::opt<bool>
127 DumpDepGraph("attributor-dump-dep-graph", cl::Hidden,
128 cl::desc("Dump the dependency graph to dot files."),
129 cl::init(false));
130
131 static cl::opt<std::string> DepGraphDotFileNamePrefix(
132 "attributor-depgraph-dot-filename-prefix", cl::Hidden,
133 cl::desc("The prefix used for the CallGraph dot file names."));
134
135 static cl::opt<bool> ViewDepGraph("attributor-view-dep-graph", cl::Hidden,
136 cl::desc("View the dependency graph."),
137 cl::init(false));
138
139 static cl::opt<bool> PrintDependencies("attributor-print-dep", cl::Hidden,
140 cl::desc("Print attribute dependencies"),
141 cl::init(false));
142
143 static cl::opt<bool> EnableCallSiteSpecific(
144 "attributor-enable-call-site-specific-deduction", cl::Hidden,
145 cl::desc("Allow the Attributor to do call site specific analysis"),
146 cl::init(false));
147
148 /// Logic operators for the change status enum class.
149 ///
150 ///{
operator |(ChangeStatus L,ChangeStatus R)151 ChangeStatus llvm::operator|(ChangeStatus L, ChangeStatus R) {
152 return L == ChangeStatus::CHANGED ? L : R;
153 }
operator &(ChangeStatus L,ChangeStatus R)154 ChangeStatus llvm::operator&(ChangeStatus L, ChangeStatus R) {
155 return L == ChangeStatus::UNCHANGED ? L : R;
156 }
157 ///}
158
159 /// Return true if \p New is equal or worse than \p Old.
isEqualOrWorse(const Attribute & New,const Attribute & Old)160 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
161 if (!Old.isIntAttribute())
162 return true;
163
164 return Old.getValueAsInt() >= New.getValueAsInt();
165 }
166
167 /// Return true if the information provided by \p Attr was added to the
168 /// attribute list \p Attrs. This is only the case if it was not already present
169 /// in \p Attrs at the position describe by \p PK and \p AttrIdx.
addIfNotExistent(LLVMContext & Ctx,const Attribute & Attr,AttributeList & Attrs,int AttrIdx)170 static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
171 AttributeList &Attrs, int AttrIdx) {
172
173 if (Attr.isEnumAttribute()) {
174 Attribute::AttrKind Kind = Attr.getKindAsEnum();
175 if (Attrs.hasAttribute(AttrIdx, Kind))
176 if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
177 return false;
178 Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
179 return true;
180 }
181 if (Attr.isStringAttribute()) {
182 StringRef Kind = Attr.getKindAsString();
183 if (Attrs.hasAttribute(AttrIdx, Kind))
184 if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
185 return false;
186 Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
187 return true;
188 }
189 if (Attr.isIntAttribute()) {
190 Attribute::AttrKind Kind = Attr.getKindAsEnum();
191 if (Attrs.hasAttribute(AttrIdx, Kind))
192 if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
193 return false;
194 Attrs = Attrs.removeAttribute(Ctx, AttrIdx, Kind);
195 Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
196 return true;
197 }
198
199 llvm_unreachable("Expected enum or string attribute!");
200 }
201
getAssociatedArgument() const202 Argument *IRPosition::getAssociatedArgument() const {
203 if (getPositionKind() == IRP_ARGUMENT)
204 return cast<Argument>(&getAnchorValue());
205
206 // Not an Argument and no argument number means this is not a call site
207 // argument, thus we cannot find a callback argument to return.
208 int ArgNo = getCallSiteArgNo();
209 if (ArgNo < 0)
210 return nullptr;
211
212 // Use abstract call sites to make the connection between the call site
213 // values and the ones in callbacks. If a callback was found that makes use
214 // of the underlying call site operand, we want the corresponding callback
215 // callee argument and not the direct callee argument.
216 Optional<Argument *> CBCandidateArg;
217 SmallVector<const Use *, 4> CallbackUses;
218 const auto &CB = cast<CallBase>(getAnchorValue());
219 AbstractCallSite::getCallbackUses(CB, CallbackUses);
220 for (const Use *U : CallbackUses) {
221 AbstractCallSite ACS(U);
222 assert(ACS && ACS.isCallbackCall());
223 if (!ACS.getCalledFunction())
224 continue;
225
226 for (unsigned u = 0, e = ACS.getNumArgOperands(); u < e; u++) {
227
228 // Test if the underlying call site operand is argument number u of the
229 // callback callee.
230 if (ACS.getCallArgOperandNo(u) != ArgNo)
231 continue;
232
233 assert(ACS.getCalledFunction()->arg_size() > u &&
234 "ACS mapped into var-args arguments!");
235 if (CBCandidateArg.hasValue()) {
236 CBCandidateArg = nullptr;
237 break;
238 }
239 CBCandidateArg = ACS.getCalledFunction()->getArg(u);
240 }
241 }
242
243 // If we found a unique callback candidate argument, return it.
244 if (CBCandidateArg.hasValue() && CBCandidateArg.getValue())
245 return CBCandidateArg.getValue();
246
247 // If no callbacks were found, or none used the underlying call site operand
248 // exclusively, use the direct callee argument if available.
249 const Function *Callee = CB.getCalledFunction();
250 if (Callee && Callee->arg_size() > unsigned(ArgNo))
251 return Callee->getArg(ArgNo);
252
253 return nullptr;
254 }
255
update(Attributor & A)256 ChangeStatus AbstractAttribute::update(Attributor &A) {
257 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
258 if (getState().isAtFixpoint())
259 return HasChanged;
260
261 LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
262
263 HasChanged = updateImpl(A);
264
265 LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
266 << "\n");
267
268 return HasChanged;
269 }
270
271 ChangeStatus
manifestAttrs(Attributor & A,const IRPosition & IRP,const ArrayRef<Attribute> & DeducedAttrs)272 IRAttributeManifest::manifestAttrs(Attributor &A, const IRPosition &IRP,
273 const ArrayRef<Attribute> &DeducedAttrs) {
274 Function *ScopeFn = IRP.getAnchorScope();
275 IRPosition::Kind PK = IRP.getPositionKind();
276
277 // In the following some generic code that will manifest attributes in
278 // DeducedAttrs if they improve the current IR. Due to the different
279 // annotation positions we use the underlying AttributeList interface.
280
281 AttributeList Attrs;
282 switch (PK) {
283 case IRPosition::IRP_INVALID:
284 case IRPosition::IRP_FLOAT:
285 return ChangeStatus::UNCHANGED;
286 case IRPosition::IRP_ARGUMENT:
287 case IRPosition::IRP_FUNCTION:
288 case IRPosition::IRP_RETURNED:
289 Attrs = ScopeFn->getAttributes();
290 break;
291 case IRPosition::IRP_CALL_SITE:
292 case IRPosition::IRP_CALL_SITE_RETURNED:
293 case IRPosition::IRP_CALL_SITE_ARGUMENT:
294 Attrs = cast<CallBase>(IRP.getAnchorValue()).getAttributes();
295 break;
296 }
297
298 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
299 LLVMContext &Ctx = IRP.getAnchorValue().getContext();
300 for (const Attribute &Attr : DeducedAttrs) {
301 if (!addIfNotExistent(Ctx, Attr, Attrs, IRP.getAttrIdx()))
302 continue;
303
304 HasChanged = ChangeStatus::CHANGED;
305 }
306
307 if (HasChanged == ChangeStatus::UNCHANGED)
308 return HasChanged;
309
310 switch (PK) {
311 case IRPosition::IRP_ARGUMENT:
312 case IRPosition::IRP_FUNCTION:
313 case IRPosition::IRP_RETURNED:
314 ScopeFn->setAttributes(Attrs);
315 break;
316 case IRPosition::IRP_CALL_SITE:
317 case IRPosition::IRP_CALL_SITE_RETURNED:
318 case IRPosition::IRP_CALL_SITE_ARGUMENT:
319 cast<CallBase>(IRP.getAnchorValue()).setAttributes(Attrs);
320 break;
321 case IRPosition::IRP_INVALID:
322 case IRPosition::IRP_FLOAT:
323 break;
324 }
325
326 return HasChanged;
327 }
328
329 const IRPosition IRPosition::EmptyKey(DenseMapInfo<void *>::getEmptyKey());
330 const IRPosition
331 IRPosition::TombstoneKey(DenseMapInfo<void *>::getTombstoneKey());
332
SubsumingPositionIterator(const IRPosition & IRP)333 SubsumingPositionIterator::SubsumingPositionIterator(const IRPosition &IRP) {
334 IRPositions.emplace_back(IRP);
335
336 // Helper to determine if operand bundles on a call site are benin or
337 // potentially problematic. We handle only llvm.assume for now.
338 auto CanIgnoreOperandBundles = [](const CallBase &CB) {
339 return (isa<IntrinsicInst>(CB) &&
340 cast<IntrinsicInst>(CB).getIntrinsicID() == Intrinsic ::assume);
341 };
342
343 const auto *CB = dyn_cast<CallBase>(&IRP.getAnchorValue());
344 switch (IRP.getPositionKind()) {
345 case IRPosition::IRP_INVALID:
346 case IRPosition::IRP_FLOAT:
347 case IRPosition::IRP_FUNCTION:
348 return;
349 case IRPosition::IRP_ARGUMENT:
350 case IRPosition::IRP_RETURNED:
351 IRPositions.emplace_back(IRPosition::function(*IRP.getAnchorScope()));
352 return;
353 case IRPosition::IRP_CALL_SITE:
354 assert(CB && "Expected call site!");
355 // TODO: We need to look at the operand bundles similar to the redirection
356 // in CallBase.
357 if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB))
358 if (const Function *Callee = CB->getCalledFunction())
359 IRPositions.emplace_back(IRPosition::function(*Callee));
360 return;
361 case IRPosition::IRP_CALL_SITE_RETURNED:
362 assert(CB && "Expected call site!");
363 // TODO: We need to look at the operand bundles similar to the redirection
364 // in CallBase.
365 if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB)) {
366 if (const Function *Callee = CB->getCalledFunction()) {
367 IRPositions.emplace_back(IRPosition::returned(*Callee));
368 IRPositions.emplace_back(IRPosition::function(*Callee));
369 for (const Argument &Arg : Callee->args())
370 if (Arg.hasReturnedAttr()) {
371 IRPositions.emplace_back(
372 IRPosition::callsite_argument(*CB, Arg.getArgNo()));
373 IRPositions.emplace_back(
374 IRPosition::value(*CB->getArgOperand(Arg.getArgNo())));
375 IRPositions.emplace_back(IRPosition::argument(Arg));
376 }
377 }
378 }
379 IRPositions.emplace_back(IRPosition::callsite_function(*CB));
380 return;
381 case IRPosition::IRP_CALL_SITE_ARGUMENT: {
382 assert(CB && "Expected call site!");
383 // TODO: We need to look at the operand bundles similar to the redirection
384 // in CallBase.
385 if (!CB->hasOperandBundles() || CanIgnoreOperandBundles(*CB)) {
386 const Function *Callee = CB->getCalledFunction();
387 if (Callee) {
388 if (Argument *Arg = IRP.getAssociatedArgument())
389 IRPositions.emplace_back(IRPosition::argument(*Arg));
390 IRPositions.emplace_back(IRPosition::function(*Callee));
391 }
392 }
393 IRPositions.emplace_back(IRPosition::value(IRP.getAssociatedValue()));
394 return;
395 }
396 }
397 }
398
hasAttr(ArrayRef<Attribute::AttrKind> AKs,bool IgnoreSubsumingPositions,Attributor * A) const399 bool IRPosition::hasAttr(ArrayRef<Attribute::AttrKind> AKs,
400 bool IgnoreSubsumingPositions, Attributor *A) const {
401 SmallVector<Attribute, 4> Attrs;
402 for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) {
403 for (Attribute::AttrKind AK : AKs)
404 if (EquivIRP.getAttrsFromIRAttr(AK, Attrs))
405 return true;
406 // The first position returned by the SubsumingPositionIterator is
407 // always the position itself. If we ignore subsuming positions we
408 // are done after the first iteration.
409 if (IgnoreSubsumingPositions)
410 break;
411 }
412 if (A)
413 for (Attribute::AttrKind AK : AKs)
414 if (getAttrsFromAssumes(AK, Attrs, *A))
415 return true;
416 return false;
417 }
418
getAttrs(ArrayRef<Attribute::AttrKind> AKs,SmallVectorImpl<Attribute> & Attrs,bool IgnoreSubsumingPositions,Attributor * A) const419 void IRPosition::getAttrs(ArrayRef<Attribute::AttrKind> AKs,
420 SmallVectorImpl<Attribute> &Attrs,
421 bool IgnoreSubsumingPositions, Attributor *A) const {
422 for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) {
423 for (Attribute::AttrKind AK : AKs)
424 EquivIRP.getAttrsFromIRAttr(AK, Attrs);
425 // The first position returned by the SubsumingPositionIterator is
426 // always the position itself. If we ignore subsuming positions we
427 // are done after the first iteration.
428 if (IgnoreSubsumingPositions)
429 break;
430 }
431 if (A)
432 for (Attribute::AttrKind AK : AKs)
433 getAttrsFromAssumes(AK, Attrs, *A);
434 }
435
getAttrsFromIRAttr(Attribute::AttrKind AK,SmallVectorImpl<Attribute> & Attrs) const436 bool IRPosition::getAttrsFromIRAttr(Attribute::AttrKind AK,
437 SmallVectorImpl<Attribute> &Attrs) const {
438 if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT)
439 return false;
440
441 AttributeList AttrList;
442 if (const auto *CB = dyn_cast<CallBase>(&getAnchorValue()))
443 AttrList = CB->getAttributes();
444 else
445 AttrList = getAssociatedFunction()->getAttributes();
446
447 bool HasAttr = AttrList.hasAttribute(getAttrIdx(), AK);
448 if (HasAttr)
449 Attrs.push_back(AttrList.getAttribute(getAttrIdx(), AK));
450 return HasAttr;
451 }
452
getAttrsFromAssumes(Attribute::AttrKind AK,SmallVectorImpl<Attribute> & Attrs,Attributor & A) const453 bool IRPosition::getAttrsFromAssumes(Attribute::AttrKind AK,
454 SmallVectorImpl<Attribute> &Attrs,
455 Attributor &A) const {
456 assert(getPositionKind() != IRP_INVALID && "Did expect a valid position!");
457 Value &AssociatedValue = getAssociatedValue();
458
459 const Assume2KnowledgeMap &A2K =
460 A.getInfoCache().getKnowledgeMap().lookup({&AssociatedValue, AK});
461
462 // Check if we found any potential assume use, if not we don't need to create
463 // explorer iterators.
464 if (A2K.empty())
465 return false;
466
467 LLVMContext &Ctx = AssociatedValue.getContext();
468 unsigned AttrsSize = Attrs.size();
469 MustBeExecutedContextExplorer &Explorer =
470 A.getInfoCache().getMustBeExecutedContextExplorer();
471 auto EIt = Explorer.begin(getCtxI()), EEnd = Explorer.end(getCtxI());
472 for (auto &It : A2K)
473 if (Explorer.findInContextOf(It.first, EIt, EEnd))
474 Attrs.push_back(Attribute::get(Ctx, AK, It.second.Max));
475 return AttrsSize != Attrs.size();
476 }
477
verify()478 void IRPosition::verify() {
479 #ifdef EXPENSIVE_CHECKS
480 switch (getPositionKind()) {
481 case IRP_INVALID:
482 assert((CBContext == nullptr) &&
483 "Invalid position must not have CallBaseContext!");
484 assert(!Enc.getOpaqueValue() &&
485 "Expected a nullptr for an invalid position!");
486 return;
487 case IRP_FLOAT:
488 assert((!isa<CallBase>(&getAssociatedValue()) &&
489 !isa<Argument>(&getAssociatedValue())) &&
490 "Expected specialized kind for call base and argument values!");
491 return;
492 case IRP_RETURNED:
493 assert(isa<Function>(getAsValuePtr()) &&
494 "Expected function for a 'returned' position!");
495 assert(getAsValuePtr() == &getAssociatedValue() &&
496 "Associated value mismatch!");
497 return;
498 case IRP_CALL_SITE_RETURNED:
499 assert((CBContext == nullptr) &&
500 "'call site returned' position must not have CallBaseContext!");
501 assert((isa<CallBase>(getAsValuePtr())) &&
502 "Expected call base for 'call site returned' position!");
503 assert(getAsValuePtr() == &getAssociatedValue() &&
504 "Associated value mismatch!");
505 return;
506 case IRP_CALL_SITE:
507 assert((CBContext == nullptr) &&
508 "'call site function' position must not have CallBaseContext!");
509 assert((isa<CallBase>(getAsValuePtr())) &&
510 "Expected call base for 'call site function' position!");
511 assert(getAsValuePtr() == &getAssociatedValue() &&
512 "Associated value mismatch!");
513 return;
514 case IRP_FUNCTION:
515 assert(isa<Function>(getAsValuePtr()) &&
516 "Expected function for a 'function' position!");
517 assert(getAsValuePtr() == &getAssociatedValue() &&
518 "Associated value mismatch!");
519 return;
520 case IRP_ARGUMENT:
521 assert(isa<Argument>(getAsValuePtr()) &&
522 "Expected argument for a 'argument' position!");
523 assert(getAsValuePtr() == &getAssociatedValue() &&
524 "Associated value mismatch!");
525 return;
526 case IRP_CALL_SITE_ARGUMENT: {
527 assert((CBContext == nullptr) &&
528 "'call site argument' position must not have CallBaseContext!");
529 Use *U = getAsUsePtr();
530 assert(U && "Expected use for a 'call site argument' position!");
531 assert(isa<CallBase>(U->getUser()) &&
532 "Expected call base user for a 'call site argument' position!");
533 assert(cast<CallBase>(U->getUser())->isArgOperand(U) &&
534 "Expected call base argument operand for a 'call site argument' "
535 "position");
536 assert(cast<CallBase>(U->getUser())->getArgOperandNo(U) ==
537 unsigned(getCallSiteArgNo()) &&
538 "Argument number mismatch!");
539 assert(U->get() == &getAssociatedValue() && "Associated value mismatch!");
540 return;
541 }
542 }
543 #endif
544 }
545
546 Optional<Constant *>
getAssumedConstant(const Value & V,const AbstractAttribute & AA,bool & UsedAssumedInformation)547 Attributor::getAssumedConstant(const Value &V, const AbstractAttribute &AA,
548 bool &UsedAssumedInformation) {
549 const auto &ValueSimplifyAA = getAAFor<AAValueSimplify>(
550 AA, IRPosition::value(V, AA.getCallBaseContext()), DepClassTy::NONE);
551 Optional<Value *> SimplifiedV =
552 ValueSimplifyAA.getAssumedSimplifiedValue(*this);
553 bool IsKnown = ValueSimplifyAA.isKnown();
554 UsedAssumedInformation |= !IsKnown;
555 if (!SimplifiedV.hasValue()) {
556 recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
557 return llvm::None;
558 }
559 if (isa_and_nonnull<UndefValue>(SimplifiedV.getValue())) {
560 recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
561 return llvm::None;
562 }
563 Constant *CI = dyn_cast_or_null<Constant>(SimplifiedV.getValue());
564 if (CI && CI->getType() != V.getType()) {
565 // TODO: Check for a save conversion.
566 return nullptr;
567 }
568 if (CI)
569 recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
570 return CI;
571 }
572
~Attributor()573 Attributor::~Attributor() {
574 // The abstract attributes are allocated via the BumpPtrAllocator Allocator,
575 // thus we cannot delete them. We can, and want to, destruct them though.
576 for (auto &DepAA : DG.SyntheticRoot.Deps) {
577 AbstractAttribute *AA = cast<AbstractAttribute>(DepAA.getPointer());
578 AA->~AbstractAttribute();
579 }
580 }
581
isAssumedDead(const AbstractAttribute & AA,const AAIsDead * FnLivenessAA,bool CheckBBLivenessOnly,DepClassTy DepClass)582 bool Attributor::isAssumedDead(const AbstractAttribute &AA,
583 const AAIsDead *FnLivenessAA,
584 bool CheckBBLivenessOnly, DepClassTy DepClass) {
585 const IRPosition &IRP = AA.getIRPosition();
586 if (!Functions.count(IRP.getAnchorScope()))
587 return false;
588 return isAssumedDead(IRP, &AA, FnLivenessAA, CheckBBLivenessOnly, DepClass);
589 }
590
isAssumedDead(const Use & U,const AbstractAttribute * QueryingAA,const AAIsDead * FnLivenessAA,bool CheckBBLivenessOnly,DepClassTy DepClass)591 bool Attributor::isAssumedDead(const Use &U,
592 const AbstractAttribute *QueryingAA,
593 const AAIsDead *FnLivenessAA,
594 bool CheckBBLivenessOnly, DepClassTy DepClass) {
595 Instruction *UserI = dyn_cast<Instruction>(U.getUser());
596 if (!UserI)
597 return isAssumedDead(IRPosition::value(*U.get()), QueryingAA, FnLivenessAA,
598 CheckBBLivenessOnly, DepClass);
599
600 if (auto *CB = dyn_cast<CallBase>(UserI)) {
601 // For call site argument uses we can check if the argument is
602 // unused/dead.
603 if (CB->isArgOperand(&U)) {
604 const IRPosition &CSArgPos =
605 IRPosition::callsite_argument(*CB, CB->getArgOperandNo(&U));
606 return isAssumedDead(CSArgPos, QueryingAA, FnLivenessAA,
607 CheckBBLivenessOnly, DepClass);
608 }
609 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(UserI)) {
610 const IRPosition &RetPos = IRPosition::returned(*RI->getFunction());
611 return isAssumedDead(RetPos, QueryingAA, FnLivenessAA, CheckBBLivenessOnly,
612 DepClass);
613 } else if (PHINode *PHI = dyn_cast<PHINode>(UserI)) {
614 BasicBlock *IncomingBB = PHI->getIncomingBlock(U);
615 return isAssumedDead(*IncomingBB->getTerminator(), QueryingAA, FnLivenessAA,
616 CheckBBLivenessOnly, DepClass);
617 }
618
619 return isAssumedDead(IRPosition::value(*UserI), QueryingAA, FnLivenessAA,
620 CheckBBLivenessOnly, DepClass);
621 }
622
isAssumedDead(const Instruction & I,const AbstractAttribute * QueryingAA,const AAIsDead * FnLivenessAA,bool CheckBBLivenessOnly,DepClassTy DepClass)623 bool Attributor::isAssumedDead(const Instruction &I,
624 const AbstractAttribute *QueryingAA,
625 const AAIsDead *FnLivenessAA,
626 bool CheckBBLivenessOnly, DepClassTy DepClass) {
627 const IRPosition::CallBaseContext *CBCtx =
628 QueryingAA ? QueryingAA->getCallBaseContext() : nullptr;
629
630 if (!FnLivenessAA)
631 FnLivenessAA =
632 lookupAAFor<AAIsDead>(IRPosition::function(*I.getFunction(), CBCtx),
633 QueryingAA, DepClassTy::NONE);
634
635 // If we have a context instruction and a liveness AA we use it.
636 if (FnLivenessAA &&
637 FnLivenessAA->getIRPosition().getAnchorScope() == I.getFunction() &&
638 FnLivenessAA->isAssumedDead(&I)) {
639 if (QueryingAA)
640 recordDependence(*FnLivenessAA, *QueryingAA, DepClass);
641 return true;
642 }
643
644 if (CheckBBLivenessOnly)
645 return false;
646
647 const AAIsDead &IsDeadAA = getOrCreateAAFor<AAIsDead>(
648 IRPosition::value(I, CBCtx), QueryingAA, DepClassTy::NONE);
649 // Don't check liveness for AAIsDead.
650 if (QueryingAA == &IsDeadAA)
651 return false;
652
653 if (IsDeadAA.isAssumedDead()) {
654 if (QueryingAA)
655 recordDependence(IsDeadAA, *QueryingAA, DepClass);
656 return true;
657 }
658
659 return false;
660 }
661
isAssumedDead(const IRPosition & IRP,const AbstractAttribute * QueryingAA,const AAIsDead * FnLivenessAA,bool CheckBBLivenessOnly,DepClassTy DepClass)662 bool Attributor::isAssumedDead(const IRPosition &IRP,
663 const AbstractAttribute *QueryingAA,
664 const AAIsDead *FnLivenessAA,
665 bool CheckBBLivenessOnly, DepClassTy DepClass) {
666 Instruction *CtxI = IRP.getCtxI();
667 if (CtxI &&
668 isAssumedDead(*CtxI, QueryingAA, FnLivenessAA,
669 /* CheckBBLivenessOnly */ true,
670 CheckBBLivenessOnly ? DepClass : DepClassTy::OPTIONAL))
671 return true;
672
673 if (CheckBBLivenessOnly)
674 return false;
675
676 // If we haven't succeeded we query the specific liveness info for the IRP.
677 const AAIsDead *IsDeadAA;
678 if (IRP.getPositionKind() == IRPosition::IRP_CALL_SITE)
679 IsDeadAA = &getOrCreateAAFor<AAIsDead>(
680 IRPosition::callsite_returned(cast<CallBase>(IRP.getAssociatedValue())),
681 QueryingAA, DepClassTy::NONE);
682 else
683 IsDeadAA = &getOrCreateAAFor<AAIsDead>(IRP, QueryingAA, DepClassTy::NONE);
684 // Don't check liveness for AAIsDead.
685 if (QueryingAA == IsDeadAA)
686 return false;
687
688 if (IsDeadAA->isAssumedDead()) {
689 if (QueryingAA)
690 recordDependence(*IsDeadAA, *QueryingAA, DepClass);
691 return true;
692 }
693
694 return false;
695 }
696
checkForAllUses(function_ref<bool (const Use &,bool &)> Pred,const AbstractAttribute & QueryingAA,const Value & V,DepClassTy LivenessDepClass)697 bool Attributor::checkForAllUses(function_ref<bool(const Use &, bool &)> Pred,
698 const AbstractAttribute &QueryingAA,
699 const Value &V, DepClassTy LivenessDepClass) {
700
701 // Check the trivial case first as it catches void values.
702 if (V.use_empty())
703 return true;
704
705 // If the value is replaced by another one, for now a constant, we do not have
706 // uses. Note that this requires users of `checkForAllUses` to not recurse but
707 // instead use the `follow` callback argument to look at transitive users,
708 // however, that should be clear from the presence of the argument.
709 bool UsedAssumedInformation = false;
710 Optional<Constant *> C =
711 getAssumedConstant(V, QueryingAA, UsedAssumedInformation);
712 if (C.hasValue() && C.getValue()) {
713 LLVM_DEBUG(dbgs() << "[Attributor] Value is simplified, uses skipped: " << V
714 << " -> " << *C.getValue() << "\n");
715 return true;
716 }
717
718 const IRPosition &IRP = QueryingAA.getIRPosition();
719 SmallVector<const Use *, 16> Worklist;
720 SmallPtrSet<const Use *, 16> Visited;
721
722 for (const Use &U : V.uses())
723 Worklist.push_back(&U);
724
725 LLVM_DEBUG(dbgs() << "[Attributor] Got " << Worklist.size()
726 << " initial uses to check\n");
727
728 const Function *ScopeFn = IRP.getAnchorScope();
729 const auto *LivenessAA =
730 ScopeFn ? &getAAFor<AAIsDead>(QueryingAA, IRPosition::function(*ScopeFn),
731 DepClassTy::NONE)
732 : nullptr;
733
734 while (!Worklist.empty()) {
735 const Use *U = Worklist.pop_back_val();
736 if (!Visited.insert(U).second)
737 continue;
738 LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << " in "
739 << *U->getUser() << "\n");
740 if (isAssumedDead(*U, &QueryingAA, LivenessAA,
741 /* CheckBBLivenessOnly */ false, LivenessDepClass)) {
742 LLVM_DEBUG(dbgs() << "[Attributor] Dead use, skip!\n");
743 continue;
744 }
745 if (U->getUser()->isDroppable()) {
746 LLVM_DEBUG(dbgs() << "[Attributor] Droppable user, skip!\n");
747 continue;
748 }
749
750 bool Follow = false;
751 if (!Pred(*U, Follow))
752 return false;
753 if (!Follow)
754 continue;
755 for (const Use &UU : U->getUser()->uses())
756 Worklist.push_back(&UU);
757 }
758
759 return true;
760 }
761
checkForAllCallSites(function_ref<bool (AbstractCallSite)> Pred,const AbstractAttribute & QueryingAA,bool RequireAllCallSites,bool & AllCallSitesKnown)762 bool Attributor::checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
763 const AbstractAttribute &QueryingAA,
764 bool RequireAllCallSites,
765 bool &AllCallSitesKnown) {
766 // We can try to determine information from
767 // the call sites. However, this is only possible all call sites are known,
768 // hence the function has internal linkage.
769 const IRPosition &IRP = QueryingAA.getIRPosition();
770 const Function *AssociatedFunction = IRP.getAssociatedFunction();
771 if (!AssociatedFunction) {
772 LLVM_DEBUG(dbgs() << "[Attributor] No function associated with " << IRP
773 << "\n");
774 AllCallSitesKnown = false;
775 return false;
776 }
777
778 return checkForAllCallSites(Pred, *AssociatedFunction, RequireAllCallSites,
779 &QueryingAA, AllCallSitesKnown);
780 }
781
checkForAllCallSites(function_ref<bool (AbstractCallSite)> Pred,const Function & Fn,bool RequireAllCallSites,const AbstractAttribute * QueryingAA,bool & AllCallSitesKnown)782 bool Attributor::checkForAllCallSites(function_ref<bool(AbstractCallSite)> Pred,
783 const Function &Fn,
784 bool RequireAllCallSites,
785 const AbstractAttribute *QueryingAA,
786 bool &AllCallSitesKnown) {
787 if (RequireAllCallSites && !Fn.hasLocalLinkage()) {
788 LLVM_DEBUG(
789 dbgs()
790 << "[Attributor] Function " << Fn.getName()
791 << " has no internal linkage, hence not all call sites are known\n");
792 AllCallSitesKnown = false;
793 return false;
794 }
795
796 // If we do not require all call sites we might not see all.
797 AllCallSitesKnown = RequireAllCallSites;
798
799 SmallVector<const Use *, 8> Uses(make_pointer_range(Fn.uses()));
800 for (unsigned u = 0; u < Uses.size(); ++u) {
801 const Use &U = *Uses[u];
802 LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << *U << " in "
803 << *U.getUser() << "\n");
804 if (isAssumedDead(U, QueryingAA, nullptr, /* CheckBBLivenessOnly */ true)) {
805 LLVM_DEBUG(dbgs() << "[Attributor] Dead use, skip!\n");
806 continue;
807 }
808 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U.getUser())) {
809 if (CE->isCast() && CE->getType()->isPointerTy() &&
810 CE->getType()->getPointerElementType()->isFunctionTy()) {
811 for (const Use &CEU : CE->uses())
812 Uses.push_back(&CEU);
813 continue;
814 }
815 }
816
817 AbstractCallSite ACS(&U);
818 if (!ACS) {
819 LLVM_DEBUG(dbgs() << "[Attributor] Function " << Fn.getName()
820 << " has non call site use " << *U.get() << " in "
821 << *U.getUser() << "\n");
822 // BlockAddress users are allowed.
823 if (isa<BlockAddress>(U.getUser()))
824 continue;
825 return false;
826 }
827
828 const Use *EffectiveUse =
829 ACS.isCallbackCall() ? &ACS.getCalleeUseForCallback() : &U;
830 if (!ACS.isCallee(EffectiveUse)) {
831 if (!RequireAllCallSites)
832 continue;
833 LLVM_DEBUG(dbgs() << "[Attributor] User " << EffectiveUse->getUser()
834 << " is an invalid use of " << Fn.getName() << "\n");
835 return false;
836 }
837
838 // Make sure the arguments that can be matched between the call site and the
839 // callee argee on their type. It is unlikely they do not and it doesn't
840 // make sense for all attributes to know/care about this.
841 assert(&Fn == ACS.getCalledFunction() && "Expected known callee");
842 unsigned MinArgsParams =
843 std::min(size_t(ACS.getNumArgOperands()), Fn.arg_size());
844 for (unsigned u = 0; u < MinArgsParams; ++u) {
845 Value *CSArgOp = ACS.getCallArgOperand(u);
846 if (CSArgOp && Fn.getArg(u)->getType() != CSArgOp->getType()) {
847 LLVM_DEBUG(
848 dbgs() << "[Attributor] Call site / callee argument type mismatch ["
849 << u << "@" << Fn.getName() << ": "
850 << *Fn.getArg(u)->getType() << " vs. "
851 << *ACS.getCallArgOperand(u)->getType() << "\n");
852 return false;
853 }
854 }
855
856 if (Pred(ACS))
857 continue;
858
859 LLVM_DEBUG(dbgs() << "[Attributor] Call site callback failed for "
860 << *ACS.getInstruction() << "\n");
861 return false;
862 }
863
864 return true;
865 }
866
shouldPropagateCallBaseContext(const IRPosition & IRP)867 bool Attributor::shouldPropagateCallBaseContext(const IRPosition &IRP) {
868 // TODO: Maintain a cache of Values that are
869 // on the pathway from a Argument to a Instruction that would effect the
870 // liveness/return state etc.
871 return EnableCallSiteSpecific;
872 }
873
checkForAllReturnedValuesAndReturnInsts(function_ref<bool (Value &,const SmallSetVector<ReturnInst *,4> &)> Pred,const AbstractAttribute & QueryingAA)874 bool Attributor::checkForAllReturnedValuesAndReturnInsts(
875 function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred,
876 const AbstractAttribute &QueryingAA) {
877
878 const IRPosition &IRP = QueryingAA.getIRPosition();
879 // Since we need to provide return instructions we have to have an exact
880 // definition.
881 const Function *AssociatedFunction = IRP.getAssociatedFunction();
882 if (!AssociatedFunction)
883 return false;
884
885 // If this is a call site query we use the call site specific return values
886 // and liveness information.
887 // TODO: use the function scope once we have call site AAReturnedValues.
888 const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
889 const auto &AARetVal =
890 getAAFor<AAReturnedValues>(QueryingAA, QueryIRP, DepClassTy::REQUIRED);
891 if (!AARetVal.getState().isValidState())
892 return false;
893
894 return AARetVal.checkForAllReturnedValuesAndReturnInsts(Pred);
895 }
896
checkForAllReturnedValues(function_ref<bool (Value &)> Pred,const AbstractAttribute & QueryingAA)897 bool Attributor::checkForAllReturnedValues(
898 function_ref<bool(Value &)> Pred, const AbstractAttribute &QueryingAA) {
899
900 const IRPosition &IRP = QueryingAA.getIRPosition();
901 const Function *AssociatedFunction = IRP.getAssociatedFunction();
902 if (!AssociatedFunction)
903 return false;
904
905 // TODO: use the function scope once we have call site AAReturnedValues.
906 const IRPosition &QueryIRP = IRPosition::function(
907 *AssociatedFunction, QueryingAA.getCallBaseContext());
908 const auto &AARetVal =
909 getAAFor<AAReturnedValues>(QueryingAA, QueryIRP, DepClassTy::REQUIRED);
910 if (!AARetVal.getState().isValidState())
911 return false;
912
913 return AARetVal.checkForAllReturnedValuesAndReturnInsts(
914 [&](Value &RV, const SmallSetVector<ReturnInst *, 4> &) {
915 return Pred(RV);
916 });
917 }
918
checkForAllInstructionsImpl(Attributor * A,InformationCache::OpcodeInstMapTy & OpcodeInstMap,function_ref<bool (Instruction &)> Pred,const AbstractAttribute * QueryingAA,const AAIsDead * LivenessAA,const ArrayRef<unsigned> & Opcodes,bool CheckBBLivenessOnly=false)919 static bool checkForAllInstructionsImpl(
920 Attributor *A, InformationCache::OpcodeInstMapTy &OpcodeInstMap,
921 function_ref<bool(Instruction &)> Pred, const AbstractAttribute *QueryingAA,
922 const AAIsDead *LivenessAA, const ArrayRef<unsigned> &Opcodes,
923 bool CheckBBLivenessOnly = false) {
924 for (unsigned Opcode : Opcodes) {
925 // Check if we have instructions with this opcode at all first.
926 auto *Insts = OpcodeInstMap.lookup(Opcode);
927 if (!Insts)
928 continue;
929
930 for (Instruction *I : *Insts) {
931 // Skip dead instructions.
932 if (A && A->isAssumedDead(IRPosition::value(*I), QueryingAA, LivenessAA,
933 CheckBBLivenessOnly))
934 continue;
935
936 if (!Pred(*I))
937 return false;
938 }
939 }
940 return true;
941 }
942
checkForAllInstructions(function_ref<bool (Instruction &)> Pred,const AbstractAttribute & QueryingAA,const ArrayRef<unsigned> & Opcodes,bool CheckBBLivenessOnly)943 bool Attributor::checkForAllInstructions(function_ref<bool(Instruction &)> Pred,
944 const AbstractAttribute &QueryingAA,
945 const ArrayRef<unsigned> &Opcodes,
946 bool CheckBBLivenessOnly) {
947
948 const IRPosition &IRP = QueryingAA.getIRPosition();
949 // Since we need to provide instructions we have to have an exact definition.
950 const Function *AssociatedFunction = IRP.getAssociatedFunction();
951 if (!AssociatedFunction)
952 return false;
953
954 // TODO: use the function scope once we have call site AAReturnedValues.
955 const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
956 const auto *LivenessAA =
957 CheckBBLivenessOnly
958 ? nullptr
959 : &(getAAFor<AAIsDead>(QueryingAA, QueryIRP, DepClassTy::NONE));
960
961 auto &OpcodeInstMap =
962 InfoCache.getOpcodeInstMapForFunction(*AssociatedFunction);
963 if (!checkForAllInstructionsImpl(this, OpcodeInstMap, Pred, &QueryingAA,
964 LivenessAA, Opcodes, CheckBBLivenessOnly))
965 return false;
966
967 return true;
968 }
969
checkForAllReadWriteInstructions(function_ref<bool (Instruction &)> Pred,AbstractAttribute & QueryingAA)970 bool Attributor::checkForAllReadWriteInstructions(
971 function_ref<bool(Instruction &)> Pred, AbstractAttribute &QueryingAA) {
972
973 const Function *AssociatedFunction =
974 QueryingAA.getIRPosition().getAssociatedFunction();
975 if (!AssociatedFunction)
976 return false;
977
978 // TODO: use the function scope once we have call site AAReturnedValues.
979 const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction);
980 const auto &LivenessAA =
981 getAAFor<AAIsDead>(QueryingAA, QueryIRP, DepClassTy::NONE);
982
983 for (Instruction *I :
984 InfoCache.getReadOrWriteInstsForFunction(*AssociatedFunction)) {
985 // Skip dead instructions.
986 if (isAssumedDead(IRPosition::value(*I), &QueryingAA, &LivenessAA))
987 continue;
988
989 if (!Pred(*I))
990 return false;
991 }
992
993 return true;
994 }
995
runTillFixpoint()996 void Attributor::runTillFixpoint() {
997 TimeTraceScope TimeScope("Attributor::runTillFixpoint");
998 LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
999 << DG.SyntheticRoot.Deps.size()
1000 << " abstract attributes.\n");
1001
1002 // Now that all abstract attributes are collected and initialized we start
1003 // the abstract analysis.
1004
1005 unsigned IterationCounter = 1;
1006
1007 SmallVector<AbstractAttribute *, 32> ChangedAAs;
1008 SetVector<AbstractAttribute *> Worklist, InvalidAAs;
1009 Worklist.insert(DG.SyntheticRoot.begin(), DG.SyntheticRoot.end());
1010
1011 do {
1012 // Remember the size to determine new attributes.
1013 size_t NumAAs = DG.SyntheticRoot.Deps.size();
1014 LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
1015 << ", Worklist size: " << Worklist.size() << "\n");
1016
1017 // For invalid AAs we can fix dependent AAs that have a required dependence,
1018 // thereby folding long dependence chains in a single step without the need
1019 // to run updates.
1020 for (unsigned u = 0; u < InvalidAAs.size(); ++u) {
1021 AbstractAttribute *InvalidAA = InvalidAAs[u];
1022
1023 // Check the dependences to fast track invalidation.
1024 LLVM_DEBUG(dbgs() << "[Attributor] InvalidAA: " << *InvalidAA << " has "
1025 << InvalidAA->Deps.size()
1026 << " required & optional dependences\n");
1027 while (!InvalidAA->Deps.empty()) {
1028 const auto &Dep = InvalidAA->Deps.back();
1029 InvalidAA->Deps.pop_back();
1030 AbstractAttribute *DepAA = cast<AbstractAttribute>(Dep.getPointer());
1031 if (Dep.getInt() == unsigned(DepClassTy::OPTIONAL)) {
1032 Worklist.insert(DepAA);
1033 continue;
1034 }
1035 DepAA->getState().indicatePessimisticFixpoint();
1036 assert(DepAA->getState().isAtFixpoint() && "Expected fixpoint state!");
1037 if (!DepAA->getState().isValidState())
1038 InvalidAAs.insert(DepAA);
1039 else
1040 ChangedAAs.push_back(DepAA);
1041 }
1042 }
1043
1044 // Add all abstract attributes that are potentially dependent on one that
1045 // changed to the work list.
1046 for (AbstractAttribute *ChangedAA : ChangedAAs)
1047 while (!ChangedAA->Deps.empty()) {
1048 Worklist.insert(
1049 cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
1050 ChangedAA->Deps.pop_back();
1051 }
1052
1053 LLVM_DEBUG(dbgs() << "[Attributor] #Iteration: " << IterationCounter
1054 << ", Worklist+Dependent size: " << Worklist.size()
1055 << "\n");
1056
1057 // Reset the changed and invalid set.
1058 ChangedAAs.clear();
1059 InvalidAAs.clear();
1060
1061 // Update all abstract attribute in the work list and record the ones that
1062 // changed.
1063 for (AbstractAttribute *AA : Worklist) {
1064 const auto &AAState = AA->getState();
1065 if (!AAState.isAtFixpoint())
1066 if (updateAA(*AA) == ChangeStatus::CHANGED)
1067 ChangedAAs.push_back(AA);
1068
1069 // Use the InvalidAAs vector to propagate invalid states fast transitively
1070 // without requiring updates.
1071 if (!AAState.isValidState())
1072 InvalidAAs.insert(AA);
1073 }
1074
1075 // Add attributes to the changed set if they have been created in the last
1076 // iteration.
1077 ChangedAAs.append(DG.SyntheticRoot.begin() + NumAAs,
1078 DG.SyntheticRoot.end());
1079
1080 // Reset the work list and repopulate with the changed abstract attributes.
1081 // Note that dependent ones are added above.
1082 Worklist.clear();
1083 Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
1084
1085 } while (!Worklist.empty() && (IterationCounter++ < MaxFixpointIterations ||
1086 VerifyMaxFixpointIterations));
1087
1088 LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
1089 << IterationCounter << "/" << MaxFixpointIterations
1090 << " iterations\n");
1091
1092 // Reset abstract arguments not settled in a sound fixpoint by now. This
1093 // happens when we stopped the fixpoint iteration early. Note that only the
1094 // ones marked as "changed" *and* the ones transitively depending on them
1095 // need to be reverted to a pessimistic state. Others might not be in a
1096 // fixpoint state but we can use the optimistic results for them anyway.
1097 SmallPtrSet<AbstractAttribute *, 32> Visited;
1098 for (unsigned u = 0; u < ChangedAAs.size(); u++) {
1099 AbstractAttribute *ChangedAA = ChangedAAs[u];
1100 if (!Visited.insert(ChangedAA).second)
1101 continue;
1102
1103 AbstractState &State = ChangedAA->getState();
1104 if (!State.isAtFixpoint()) {
1105 State.indicatePessimisticFixpoint();
1106
1107 NumAttributesTimedOut++;
1108 }
1109
1110 while (!ChangedAA->Deps.empty()) {
1111 ChangedAAs.push_back(
1112 cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
1113 ChangedAA->Deps.pop_back();
1114 }
1115 }
1116
1117 LLVM_DEBUG({
1118 if (!Visited.empty())
1119 dbgs() << "\n[Attributor] Finalized " << Visited.size()
1120 << " abstract attributes.\n";
1121 });
1122
1123 if (VerifyMaxFixpointIterations &&
1124 IterationCounter != MaxFixpointIterations) {
1125 errs() << "\n[Attributor] Fixpoint iteration done after: "
1126 << IterationCounter << "/" << MaxFixpointIterations
1127 << " iterations\n";
1128 llvm_unreachable("The fixpoint was not reached with exactly the number of "
1129 "specified iterations!");
1130 }
1131 }
1132
manifestAttributes()1133 ChangeStatus Attributor::manifestAttributes() {
1134 TimeTraceScope TimeScope("Attributor::manifestAttributes");
1135 size_t NumFinalAAs = DG.SyntheticRoot.Deps.size();
1136
1137 unsigned NumManifested = 0;
1138 unsigned NumAtFixpoint = 0;
1139 ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
1140 for (auto &DepAA : DG.SyntheticRoot.Deps) {
1141 AbstractAttribute *AA = cast<AbstractAttribute>(DepAA.getPointer());
1142 AbstractState &State = AA->getState();
1143
1144 // If there is not already a fixpoint reached, we can now take the
1145 // optimistic state. This is correct because we enforced a pessimistic one
1146 // on abstract attributes that were transitively dependent on a changed one
1147 // already above.
1148 if (!State.isAtFixpoint())
1149 State.indicateOptimisticFixpoint();
1150
1151 // We must not manifest Attributes that use Callbase info.
1152 if (AA->hasCallBaseContext())
1153 continue;
1154 // If the state is invalid, we do not try to manifest it.
1155 if (!State.isValidState())
1156 continue;
1157
1158 // Skip dead code.
1159 if (isAssumedDead(*AA, nullptr, /* CheckBBLivenessOnly */ true))
1160 continue;
1161 // Check if the manifest debug counter that allows skipping manifestation of
1162 // AAs
1163 if (!DebugCounter::shouldExecute(ManifestDBGCounter))
1164 continue;
1165 // Manifest the state and record if we changed the IR.
1166 ChangeStatus LocalChange = AA->manifest(*this);
1167 if (LocalChange == ChangeStatus::CHANGED && AreStatisticsEnabled())
1168 AA->trackStatistics();
1169 LLVM_DEBUG(dbgs() << "[Attributor] Manifest " << LocalChange << " : " << *AA
1170 << "\n");
1171
1172 ManifestChange = ManifestChange | LocalChange;
1173
1174 NumAtFixpoint++;
1175 NumManifested += (LocalChange == ChangeStatus::CHANGED);
1176 }
1177
1178 (void)NumManifested;
1179 (void)NumAtFixpoint;
1180 LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
1181 << " arguments while " << NumAtFixpoint
1182 << " were in a valid fixpoint state\n");
1183
1184 NumAttributesManifested += NumManifested;
1185 NumAttributesValidFixpoint += NumAtFixpoint;
1186
1187 (void)NumFinalAAs;
1188 if (NumFinalAAs != DG.SyntheticRoot.Deps.size()) {
1189 for (unsigned u = NumFinalAAs; u < DG.SyntheticRoot.Deps.size(); ++u)
1190 errs() << "Unexpected abstract attribute: "
1191 << cast<AbstractAttribute>(DG.SyntheticRoot.Deps[u].getPointer())
1192 << " :: "
1193 << cast<AbstractAttribute>(DG.SyntheticRoot.Deps[u].getPointer())
1194 ->getIRPosition()
1195 .getAssociatedValue()
1196 << "\n";
1197 llvm_unreachable("Expected the final number of abstract attributes to "
1198 "remain unchanged!");
1199 }
1200 return ManifestChange;
1201 }
1202
identifyDeadInternalFunctions()1203 void Attributor::identifyDeadInternalFunctions() {
1204 // Early exit if we don't intend to delete functions.
1205 if (!DeleteFns)
1206 return;
1207
1208 // Identify dead internal functions and delete them. This happens outside
1209 // the other fixpoint analysis as we might treat potentially dead functions
1210 // as live to lower the number of iterations. If they happen to be dead, the
1211 // below fixpoint loop will identify and eliminate them.
1212 SmallVector<Function *, 8> InternalFns;
1213 for (Function *F : Functions)
1214 if (F->hasLocalLinkage())
1215 InternalFns.push_back(F);
1216
1217 SmallPtrSet<Function *, 8> LiveInternalFns;
1218 bool FoundLiveInternal = true;
1219 while (FoundLiveInternal) {
1220 FoundLiveInternal = false;
1221 for (unsigned u = 0, e = InternalFns.size(); u < e; ++u) {
1222 Function *F = InternalFns[u];
1223 if (!F)
1224 continue;
1225
1226 bool AllCallSitesKnown;
1227 if (checkForAllCallSites(
1228 [&](AbstractCallSite ACS) {
1229 Function *Callee = ACS.getInstruction()->getFunction();
1230 return ToBeDeletedFunctions.count(Callee) ||
1231 (Functions.count(Callee) && Callee->hasLocalLinkage() &&
1232 !LiveInternalFns.count(Callee));
1233 },
1234 *F, true, nullptr, AllCallSitesKnown)) {
1235 continue;
1236 }
1237
1238 LiveInternalFns.insert(F);
1239 InternalFns[u] = nullptr;
1240 FoundLiveInternal = true;
1241 }
1242 }
1243
1244 for (unsigned u = 0, e = InternalFns.size(); u < e; ++u)
1245 if (Function *F = InternalFns[u])
1246 ToBeDeletedFunctions.insert(F);
1247 }
1248
cleanupIR()1249 ChangeStatus Attributor::cleanupIR() {
1250 TimeTraceScope TimeScope("Attributor::cleanupIR");
1251 // Delete stuff at the end to avoid invalid references and a nice order.
1252 LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least "
1253 << ToBeDeletedFunctions.size() << " functions and "
1254 << ToBeDeletedBlocks.size() << " blocks and "
1255 << ToBeDeletedInsts.size() << " instructions and "
1256 << ToBeChangedUses.size() << " uses\n");
1257
1258 SmallVector<WeakTrackingVH, 32> DeadInsts;
1259 SmallVector<Instruction *, 32> TerminatorsToFold;
1260
1261 for (auto &It : ToBeChangedUses) {
1262 Use *U = It.first;
1263 Value *NewV = It.second;
1264 Value *OldV = U->get();
1265
1266 // Do not replace uses in returns if the value is a must-tail call we will
1267 // not delete.
1268 if (isa<ReturnInst>(U->getUser()))
1269 if (auto *CI = dyn_cast<CallInst>(OldV->stripPointerCasts()))
1270 if (CI->isMustTailCall() && !ToBeDeletedInsts.count(CI))
1271 continue;
1272
1273 LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser()
1274 << " instead of " << *OldV << "\n");
1275 U->set(NewV);
1276 // Do not modify call instructions outside the SCC.
1277 if (auto *CB = dyn_cast<CallBase>(OldV))
1278 if (!Functions.count(CB->getCaller()))
1279 continue;
1280 if (Instruction *I = dyn_cast<Instruction>(OldV)) {
1281 CGModifiedFunctions.insert(I->getFunction());
1282 if (!isa<PHINode>(I) && !ToBeDeletedInsts.count(I) &&
1283 isInstructionTriviallyDead(I))
1284 DeadInsts.push_back(I);
1285 }
1286 if (isa<UndefValue>(NewV) && isa<CallBase>(U->getUser())) {
1287 auto *CB = cast<CallBase>(U->getUser());
1288 if (CB->isArgOperand(U)) {
1289 unsigned Idx = CB->getArgOperandNo(U);
1290 CB->removeParamAttr(Idx, Attribute::NoUndef);
1291 Function *Fn = CB->getCalledFunction();
1292 assert(Fn && "Expected callee when call argument is replaced!");
1293 if (Fn->arg_size() > Idx)
1294 Fn->removeParamAttr(Idx, Attribute::NoUndef);
1295 }
1296 }
1297 if (isa<Constant>(NewV) && isa<BranchInst>(U->getUser())) {
1298 Instruction *UserI = cast<Instruction>(U->getUser());
1299 if (isa<UndefValue>(NewV)) {
1300 ToBeChangedToUnreachableInsts.insert(UserI);
1301 } else {
1302 TerminatorsToFold.push_back(UserI);
1303 }
1304 }
1305 }
1306 for (auto &V : InvokeWithDeadSuccessor)
1307 if (InvokeInst *II = dyn_cast_or_null<InvokeInst>(V)) {
1308 bool UnwindBBIsDead = II->hasFnAttr(Attribute::NoUnwind);
1309 bool NormalBBIsDead = II->hasFnAttr(Attribute::NoReturn);
1310 bool Invoke2CallAllowed =
1311 !AAIsDead::mayCatchAsynchronousExceptions(*II->getFunction());
1312 assert((UnwindBBIsDead || NormalBBIsDead) &&
1313 "Invoke does not have dead successors!");
1314 BasicBlock *BB = II->getParent();
1315 BasicBlock *NormalDestBB = II->getNormalDest();
1316 if (UnwindBBIsDead) {
1317 Instruction *NormalNextIP = &NormalDestBB->front();
1318 if (Invoke2CallAllowed) {
1319 changeToCall(II);
1320 NormalNextIP = BB->getTerminator();
1321 }
1322 if (NormalBBIsDead)
1323 ToBeChangedToUnreachableInsts.insert(NormalNextIP);
1324 } else {
1325 assert(NormalBBIsDead && "Broken invariant!");
1326 if (!NormalDestBB->getUniquePredecessor())
1327 NormalDestBB = SplitBlockPredecessors(NormalDestBB, {BB}, ".dead");
1328 ToBeChangedToUnreachableInsts.insert(&NormalDestBB->front());
1329 }
1330 }
1331 for (Instruction *I : TerminatorsToFold) {
1332 CGModifiedFunctions.insert(I->getFunction());
1333 ConstantFoldTerminator(I->getParent());
1334 }
1335 for (auto &V : ToBeChangedToUnreachableInsts)
1336 if (Instruction *I = dyn_cast_or_null<Instruction>(V)) {
1337 CGModifiedFunctions.insert(I->getFunction());
1338 changeToUnreachable(I, /* UseLLVMTrap */ false);
1339 }
1340
1341 for (auto &V : ToBeDeletedInsts) {
1342 if (Instruction *I = dyn_cast_or_null<Instruction>(V)) {
1343 I->dropDroppableUses();
1344 CGModifiedFunctions.insert(I->getFunction());
1345 if (!I->getType()->isVoidTy())
1346 I->replaceAllUsesWith(UndefValue::get(I->getType()));
1347 if (!isa<PHINode>(I) && isInstructionTriviallyDead(I))
1348 DeadInsts.push_back(I);
1349 else
1350 I->eraseFromParent();
1351 }
1352 }
1353
1354 LLVM_DEBUG(dbgs() << "[Attributor] DeadInsts size: " << DeadInsts.size()
1355 << "\n");
1356
1357 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);
1358
1359 if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) {
1360 SmallVector<BasicBlock *, 8> ToBeDeletedBBs;
1361 ToBeDeletedBBs.reserve(NumDeadBlocks);
1362 for (BasicBlock *BB : ToBeDeletedBlocks) {
1363 CGModifiedFunctions.insert(BB->getParent());
1364 ToBeDeletedBBs.push_back(BB);
1365 }
1366 // Actually we do not delete the blocks but squash them into a single
1367 // unreachable but untangling branches that jump here is something we need
1368 // to do in a more generic way.
1369 DetatchDeadBlocks(ToBeDeletedBBs, nullptr);
1370 }
1371
1372 identifyDeadInternalFunctions();
1373
1374 // Rewrite the functions as requested during manifest.
1375 ChangeStatus ManifestChange = rewriteFunctionSignatures(CGModifiedFunctions);
1376
1377 for (Function *Fn : CGModifiedFunctions)
1378 if (!ToBeDeletedFunctions.count(Fn))
1379 CGUpdater.reanalyzeFunction(*Fn);
1380
1381 for (Function *Fn : ToBeDeletedFunctions) {
1382 if (!Functions.count(Fn))
1383 continue;
1384 CGUpdater.removeFunction(*Fn);
1385 }
1386
1387 if (!ToBeChangedUses.empty())
1388 ManifestChange = ChangeStatus::CHANGED;
1389
1390 if (!ToBeChangedToUnreachableInsts.empty())
1391 ManifestChange = ChangeStatus::CHANGED;
1392
1393 if (!ToBeDeletedFunctions.empty())
1394 ManifestChange = ChangeStatus::CHANGED;
1395
1396 if (!ToBeDeletedBlocks.empty())
1397 ManifestChange = ChangeStatus::CHANGED;
1398
1399 if (!ToBeDeletedInsts.empty())
1400 ManifestChange = ChangeStatus::CHANGED;
1401
1402 if (!InvokeWithDeadSuccessor.empty())
1403 ManifestChange = ChangeStatus::CHANGED;
1404
1405 if (!DeadInsts.empty())
1406 ManifestChange = ChangeStatus::CHANGED;
1407
1408 NumFnDeleted += ToBeDeletedFunctions.size();
1409
1410 LLVM_DEBUG(dbgs() << "[Attributor] Deleted " << ToBeDeletedFunctions.size()
1411 << " functions after manifest.\n");
1412
1413 #ifdef EXPENSIVE_CHECKS
1414 for (Function *F : Functions) {
1415 if (ToBeDeletedFunctions.count(F))
1416 continue;
1417 assert(!verifyFunction(*F, &errs()) && "Module verification failed!");
1418 }
1419 #endif
1420
1421 return ManifestChange;
1422 }
1423
run()1424 ChangeStatus Attributor::run() {
1425 TimeTraceScope TimeScope("Attributor::run");
1426
1427 Phase = AttributorPhase::UPDATE;
1428 runTillFixpoint();
1429
1430 // dump graphs on demand
1431 if (DumpDepGraph)
1432 DG.dumpGraph();
1433
1434 if (ViewDepGraph)
1435 DG.viewGraph();
1436
1437 if (PrintDependencies)
1438 DG.print();
1439
1440 Phase = AttributorPhase::MANIFEST;
1441 ChangeStatus ManifestChange = manifestAttributes();
1442
1443 Phase = AttributorPhase::CLEANUP;
1444 ChangeStatus CleanupChange = cleanupIR();
1445
1446 return ManifestChange | CleanupChange;
1447 }
1448
updateAA(AbstractAttribute & AA)1449 ChangeStatus Attributor::updateAA(AbstractAttribute &AA) {
1450 TimeTraceScope TimeScope(
1451 AA.getName() + std::to_string(AA.getIRPosition().getPositionKind()) +
1452 "::updateAA");
1453 assert(Phase == AttributorPhase::UPDATE &&
1454 "We can update AA only in the update stage!");
1455
1456 // Use a new dependence vector for this update.
1457 DependenceVector DV;
1458 DependenceStack.push_back(&DV);
1459
1460 auto &AAState = AA.getState();
1461 ChangeStatus CS = ChangeStatus::UNCHANGED;
1462 if (!isAssumedDead(AA, nullptr, /* CheckBBLivenessOnly */ true))
1463 CS = AA.update(*this);
1464
1465 if (DV.empty()) {
1466 // If the attribute did not query any non-fix information, the state
1467 // will not change and we can indicate that right away.
1468 AAState.indicateOptimisticFixpoint();
1469 }
1470
1471 if (!AAState.isAtFixpoint())
1472 rememberDependences();
1473
1474 // Verify the stack was used properly, that is we pop the dependence vector we
1475 // put there earlier.
1476 DependenceVector *PoppedDV = DependenceStack.pop_back_val();
1477 (void)PoppedDV;
1478 assert(PoppedDV == &DV && "Inconsistent usage of the dependence stack!");
1479
1480 return CS;
1481 }
1482
createShallowWrapper(Function & F)1483 void Attributor::createShallowWrapper(Function &F) {
1484 assert(!F.isDeclaration() && "Cannot create a wrapper around a declaration!");
1485
1486 Module &M = *F.getParent();
1487 LLVMContext &Ctx = M.getContext();
1488 FunctionType *FnTy = F.getFunctionType();
1489
1490 Function *Wrapper =
1491 Function::Create(FnTy, F.getLinkage(), F.getAddressSpace(), F.getName());
1492 F.setName(""); // set the inside function anonymous
1493 M.getFunctionList().insert(F.getIterator(), Wrapper);
1494
1495 F.setLinkage(GlobalValue::InternalLinkage);
1496
1497 F.replaceAllUsesWith(Wrapper);
1498 assert(F.use_empty() && "Uses remained after wrapper was created!");
1499
1500 // Move the COMDAT section to the wrapper.
1501 // TODO: Check if we need to keep it for F as well.
1502 Wrapper->setComdat(F.getComdat());
1503 F.setComdat(nullptr);
1504
1505 // Copy all metadata and attributes but keep them on F as well.
1506 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
1507 F.getAllMetadata(MDs);
1508 for (auto MDIt : MDs)
1509 Wrapper->addMetadata(MDIt.first, *MDIt.second);
1510 Wrapper->setAttributes(F.getAttributes());
1511
1512 // Create the call in the wrapper.
1513 BasicBlock *EntryBB = BasicBlock::Create(Ctx, "entry", Wrapper);
1514
1515 SmallVector<Value *, 8> Args;
1516 Argument *FArgIt = F.arg_begin();
1517 for (Argument &Arg : Wrapper->args()) {
1518 Args.push_back(&Arg);
1519 Arg.setName((FArgIt++)->getName());
1520 }
1521
1522 CallInst *CI = CallInst::Create(&F, Args, "", EntryBB);
1523 CI->setTailCall(true);
1524 CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoInline);
1525 ReturnInst::Create(Ctx, CI->getType()->isVoidTy() ? nullptr : CI, EntryBB);
1526
1527 NumFnShallowWrappersCreated++;
1528 }
1529
1530 /// Make another copy of the function \p F such that the copied version has
1531 /// internal linkage afterwards and can be analysed. Then we replace all uses
1532 /// of the original function to the copied one
1533 ///
1534 /// Only non-exactly defined functions that have `linkonce_odr` or `weak_odr`
1535 /// linkage can be internalized because these linkages guarantee that other
1536 /// definitions with the same name have the same semantics as this one
1537 ///
internalizeFunction(Function & F)1538 static Function *internalizeFunction(Function &F) {
1539 assert(AllowDeepWrapper && "Cannot create a copy if not allowed.");
1540 assert(!F.isDeclaration() && !F.hasExactDefinition() &&
1541 !GlobalValue::isInterposableLinkage(F.getLinkage()) &&
1542 "Trying to internalize function which cannot be internalized.");
1543
1544 Module &M = *F.getParent();
1545 FunctionType *FnTy = F.getFunctionType();
1546
1547 // create a copy of the current function
1548 Function *Copied = Function::Create(FnTy, F.getLinkage(), F.getAddressSpace(),
1549 F.getName() + ".internalized");
1550 ValueToValueMapTy VMap;
1551 auto *NewFArgIt = Copied->arg_begin();
1552 for (auto &Arg : F.args()) {
1553 auto ArgName = Arg.getName();
1554 NewFArgIt->setName(ArgName);
1555 VMap[&Arg] = &(*NewFArgIt++);
1556 }
1557 SmallVector<ReturnInst *, 8> Returns;
1558
1559 // Copy the body of the original function to the new one
1560 CloneFunctionInto(Copied, &F, VMap, CloneFunctionChangeType::LocalChangesOnly,
1561 Returns);
1562
1563 // Set the linakage and visibility late as CloneFunctionInto has some implicit
1564 // requirements.
1565 Copied->setVisibility(GlobalValue::DefaultVisibility);
1566 Copied->setLinkage(GlobalValue::PrivateLinkage);
1567
1568 // Copy metadata
1569 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
1570 F.getAllMetadata(MDs);
1571 for (auto MDIt : MDs)
1572 Copied->addMetadata(MDIt.first, *MDIt.second);
1573
1574 M.getFunctionList().insert(F.getIterator(), Copied);
1575 F.replaceAllUsesWith(Copied);
1576 Copied->setDSOLocal(true);
1577
1578 return Copied;
1579 }
1580
isValidFunctionSignatureRewrite(Argument & Arg,ArrayRef<Type * > ReplacementTypes)1581 bool Attributor::isValidFunctionSignatureRewrite(
1582 Argument &Arg, ArrayRef<Type *> ReplacementTypes) {
1583
1584 auto CallSiteCanBeChanged = [](AbstractCallSite ACS) {
1585 // Forbid the call site to cast the function return type. If we need to
1586 // rewrite these functions we need to re-create a cast for the new call site
1587 // (if the old had uses).
1588 if (!ACS.getCalledFunction() ||
1589 ACS.getInstruction()->getType() !=
1590 ACS.getCalledFunction()->getReturnType())
1591 return false;
1592 // Forbid must-tail calls for now.
1593 return !ACS.isCallbackCall() && !ACS.getInstruction()->isMustTailCall();
1594 };
1595
1596 Function *Fn = Arg.getParent();
1597 // Avoid var-arg functions for now.
1598 if (Fn->isVarArg()) {
1599 LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite var-args functions\n");
1600 return false;
1601 }
1602
1603 // Avoid functions with complicated argument passing semantics.
1604 AttributeList FnAttributeList = Fn->getAttributes();
1605 if (FnAttributeList.hasAttrSomewhere(Attribute::Nest) ||
1606 FnAttributeList.hasAttrSomewhere(Attribute::StructRet) ||
1607 FnAttributeList.hasAttrSomewhere(Attribute::InAlloca) ||
1608 FnAttributeList.hasAttrSomewhere(Attribute::Preallocated)) {
1609 LLVM_DEBUG(
1610 dbgs() << "[Attributor] Cannot rewrite due to complex attribute\n");
1611 return false;
1612 }
1613
1614 // Avoid callbacks for now.
1615 bool AllCallSitesKnown;
1616 if (!checkForAllCallSites(CallSiteCanBeChanged, *Fn, true, nullptr,
1617 AllCallSitesKnown)) {
1618 LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite all call sites\n");
1619 return false;
1620 }
1621
1622 auto InstPred = [](Instruction &I) {
1623 if (auto *CI = dyn_cast<CallInst>(&I))
1624 return !CI->isMustTailCall();
1625 return true;
1626 };
1627
1628 // Forbid must-tail calls for now.
1629 // TODO:
1630 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(*Fn);
1631 if (!checkForAllInstructionsImpl(nullptr, OpcodeInstMap, InstPred, nullptr,
1632 nullptr, {Instruction::Call})) {
1633 LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite due to instructions\n");
1634 return false;
1635 }
1636
1637 return true;
1638 }
1639
registerFunctionSignatureRewrite(Argument & Arg,ArrayRef<Type * > ReplacementTypes,ArgumentReplacementInfo::CalleeRepairCBTy && CalleeRepairCB,ArgumentReplacementInfo::ACSRepairCBTy && ACSRepairCB)1640 bool Attributor::registerFunctionSignatureRewrite(
1641 Argument &Arg, ArrayRef<Type *> ReplacementTypes,
1642 ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB,
1643 ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB) {
1644 LLVM_DEBUG(dbgs() << "[Attributor] Register new rewrite of " << Arg << " in "
1645 << Arg.getParent()->getName() << " with "
1646 << ReplacementTypes.size() << " replacements\n");
1647 assert(isValidFunctionSignatureRewrite(Arg, ReplacementTypes) &&
1648 "Cannot register an invalid rewrite");
1649
1650 Function *Fn = Arg.getParent();
1651 SmallVectorImpl<std::unique_ptr<ArgumentReplacementInfo>> &ARIs =
1652 ArgumentReplacementMap[Fn];
1653 if (ARIs.empty())
1654 ARIs.resize(Fn->arg_size());
1655
1656 // If we have a replacement already with less than or equal new arguments,
1657 // ignore this request.
1658 std::unique_ptr<ArgumentReplacementInfo> &ARI = ARIs[Arg.getArgNo()];
1659 if (ARI && ARI->getNumReplacementArgs() <= ReplacementTypes.size()) {
1660 LLVM_DEBUG(dbgs() << "[Attributor] Existing rewrite is preferred\n");
1661 return false;
1662 }
1663
1664 // If we have a replacement already but we like the new one better, delete
1665 // the old.
1666 ARI.reset();
1667
1668 LLVM_DEBUG(dbgs() << "[Attributor] Register new rewrite of " << Arg << " in "
1669 << Arg.getParent()->getName() << " with "
1670 << ReplacementTypes.size() << " replacements\n");
1671
1672 // Remember the replacement.
1673 ARI.reset(new ArgumentReplacementInfo(*this, Arg, ReplacementTypes,
1674 std::move(CalleeRepairCB),
1675 std::move(ACSRepairCB)));
1676
1677 return true;
1678 }
1679
shouldSeedAttribute(AbstractAttribute & AA)1680 bool Attributor::shouldSeedAttribute(AbstractAttribute &AA) {
1681 bool Result = true;
1682 #ifndef NDEBUG
1683 if (SeedAllowList.size() != 0)
1684 Result =
1685 std::count(SeedAllowList.begin(), SeedAllowList.end(), AA.getName());
1686 Function *Fn = AA.getAnchorScope();
1687 if (FunctionSeedAllowList.size() != 0 && Fn)
1688 Result &= std::count(FunctionSeedAllowList.begin(),
1689 FunctionSeedAllowList.end(), Fn->getName());
1690 #endif
1691 return Result;
1692 }
1693
rewriteFunctionSignatures(SmallPtrSetImpl<Function * > & ModifiedFns)1694 ChangeStatus Attributor::rewriteFunctionSignatures(
1695 SmallPtrSetImpl<Function *> &ModifiedFns) {
1696 ChangeStatus Changed = ChangeStatus::UNCHANGED;
1697
1698 for (auto &It : ArgumentReplacementMap) {
1699 Function *OldFn = It.getFirst();
1700
1701 // Deleted functions do not require rewrites.
1702 if (!Functions.count(OldFn) || ToBeDeletedFunctions.count(OldFn))
1703 continue;
1704
1705 const SmallVectorImpl<std::unique_ptr<ArgumentReplacementInfo>> &ARIs =
1706 It.getSecond();
1707 assert(ARIs.size() == OldFn->arg_size() && "Inconsistent state!");
1708
1709 SmallVector<Type *, 16> NewArgumentTypes;
1710 SmallVector<AttributeSet, 16> NewArgumentAttributes;
1711
1712 // Collect replacement argument types and copy over existing attributes.
1713 AttributeList OldFnAttributeList = OldFn->getAttributes();
1714 for (Argument &Arg : OldFn->args()) {
1715 if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
1716 ARIs[Arg.getArgNo()]) {
1717 NewArgumentTypes.append(ARI->ReplacementTypes.begin(),
1718 ARI->ReplacementTypes.end());
1719 NewArgumentAttributes.append(ARI->getNumReplacementArgs(),
1720 AttributeSet());
1721 } else {
1722 NewArgumentTypes.push_back(Arg.getType());
1723 NewArgumentAttributes.push_back(
1724 OldFnAttributeList.getParamAttributes(Arg.getArgNo()));
1725 }
1726 }
1727
1728 FunctionType *OldFnTy = OldFn->getFunctionType();
1729 Type *RetTy = OldFnTy->getReturnType();
1730
1731 // Construct the new function type using the new arguments types.
1732 FunctionType *NewFnTy =
1733 FunctionType::get(RetTy, NewArgumentTypes, OldFnTy->isVarArg());
1734
1735 LLVM_DEBUG(dbgs() << "[Attributor] Function rewrite '" << OldFn->getName()
1736 << "' from " << *OldFn->getFunctionType() << " to "
1737 << *NewFnTy << "\n");
1738
1739 // Create the new function body and insert it into the module.
1740 Function *NewFn = Function::Create(NewFnTy, OldFn->getLinkage(),
1741 OldFn->getAddressSpace(), "");
1742 OldFn->getParent()->getFunctionList().insert(OldFn->getIterator(), NewFn);
1743 NewFn->takeName(OldFn);
1744 NewFn->copyAttributesFrom(OldFn);
1745
1746 // Patch the pointer to LLVM function in debug info descriptor.
1747 NewFn->setSubprogram(OldFn->getSubprogram());
1748 OldFn->setSubprogram(nullptr);
1749
1750 // Recompute the parameter attributes list based on the new arguments for
1751 // the function.
1752 LLVMContext &Ctx = OldFn->getContext();
1753 NewFn->setAttributes(AttributeList::get(
1754 Ctx, OldFnAttributeList.getFnAttributes(),
1755 OldFnAttributeList.getRetAttributes(), NewArgumentAttributes));
1756
1757 // Since we have now created the new function, splice the body of the old
1758 // function right into the new function, leaving the old rotting hulk of the
1759 // function empty.
1760 NewFn->getBasicBlockList().splice(NewFn->begin(),
1761 OldFn->getBasicBlockList());
1762
1763 // Fixup block addresses to reference new function.
1764 SmallVector<BlockAddress *, 8u> BlockAddresses;
1765 for (User *U : OldFn->users())
1766 if (auto *BA = dyn_cast<BlockAddress>(U))
1767 BlockAddresses.push_back(BA);
1768 for (auto *BA : BlockAddresses)
1769 BA->replaceAllUsesWith(BlockAddress::get(NewFn, BA->getBasicBlock()));
1770
1771 // Set of all "call-like" instructions that invoke the old function mapped
1772 // to their new replacements.
1773 SmallVector<std::pair<CallBase *, CallBase *>, 8> CallSitePairs;
1774
1775 // Callback to create a new "call-like" instruction for a given one.
1776 auto CallSiteReplacementCreator = [&](AbstractCallSite ACS) {
1777 CallBase *OldCB = cast<CallBase>(ACS.getInstruction());
1778 const AttributeList &OldCallAttributeList = OldCB->getAttributes();
1779
1780 // Collect the new argument operands for the replacement call site.
1781 SmallVector<Value *, 16> NewArgOperands;
1782 SmallVector<AttributeSet, 16> NewArgOperandAttributes;
1783 for (unsigned OldArgNum = 0; OldArgNum < ARIs.size(); ++OldArgNum) {
1784 unsigned NewFirstArgNum = NewArgOperands.size();
1785 (void)NewFirstArgNum; // only used inside assert.
1786 if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
1787 ARIs[OldArgNum]) {
1788 if (ARI->ACSRepairCB)
1789 ARI->ACSRepairCB(*ARI, ACS, NewArgOperands);
1790 assert(ARI->getNumReplacementArgs() + NewFirstArgNum ==
1791 NewArgOperands.size() &&
1792 "ACS repair callback did not provide as many operand as new "
1793 "types were registered!");
1794 // TODO: Exose the attribute set to the ACS repair callback
1795 NewArgOperandAttributes.append(ARI->ReplacementTypes.size(),
1796 AttributeSet());
1797 } else {
1798 NewArgOperands.push_back(ACS.getCallArgOperand(OldArgNum));
1799 NewArgOperandAttributes.push_back(
1800 OldCallAttributeList.getParamAttributes(OldArgNum));
1801 }
1802 }
1803
1804 assert(NewArgOperands.size() == NewArgOperandAttributes.size() &&
1805 "Mismatch # argument operands vs. # argument operand attributes!");
1806 assert(NewArgOperands.size() == NewFn->arg_size() &&
1807 "Mismatch # argument operands vs. # function arguments!");
1808
1809 SmallVector<OperandBundleDef, 4> OperandBundleDefs;
1810 OldCB->getOperandBundlesAsDefs(OperandBundleDefs);
1811
1812 // Create a new call or invoke instruction to replace the old one.
1813 CallBase *NewCB;
1814 if (InvokeInst *II = dyn_cast<InvokeInst>(OldCB)) {
1815 NewCB =
1816 InvokeInst::Create(NewFn, II->getNormalDest(), II->getUnwindDest(),
1817 NewArgOperands, OperandBundleDefs, "", OldCB);
1818 } else {
1819 auto *NewCI = CallInst::Create(NewFn, NewArgOperands, OperandBundleDefs,
1820 "", OldCB);
1821 NewCI->setTailCallKind(cast<CallInst>(OldCB)->getTailCallKind());
1822 NewCB = NewCI;
1823 }
1824
1825 // Copy over various properties and the new attributes.
1826 NewCB->copyMetadata(*OldCB, {LLVMContext::MD_prof, LLVMContext::MD_dbg});
1827 NewCB->setCallingConv(OldCB->getCallingConv());
1828 NewCB->takeName(OldCB);
1829 NewCB->setAttributes(AttributeList::get(
1830 Ctx, OldCallAttributeList.getFnAttributes(),
1831 OldCallAttributeList.getRetAttributes(), NewArgOperandAttributes));
1832
1833 CallSitePairs.push_back({OldCB, NewCB});
1834 return true;
1835 };
1836
1837 // Use the CallSiteReplacementCreator to create replacement call sites.
1838 bool AllCallSitesKnown;
1839 bool Success = checkForAllCallSites(CallSiteReplacementCreator, *OldFn,
1840 true, nullptr, AllCallSitesKnown);
1841 (void)Success;
1842 assert(Success && "Assumed call site replacement to succeed!");
1843
1844 // Rewire the arguments.
1845 Argument *OldFnArgIt = OldFn->arg_begin();
1846 Argument *NewFnArgIt = NewFn->arg_begin();
1847 for (unsigned OldArgNum = 0; OldArgNum < ARIs.size();
1848 ++OldArgNum, ++OldFnArgIt) {
1849 if (const std::unique_ptr<ArgumentReplacementInfo> &ARI =
1850 ARIs[OldArgNum]) {
1851 if (ARI->CalleeRepairCB)
1852 ARI->CalleeRepairCB(*ARI, *NewFn, NewFnArgIt);
1853 NewFnArgIt += ARI->ReplacementTypes.size();
1854 } else {
1855 NewFnArgIt->takeName(&*OldFnArgIt);
1856 OldFnArgIt->replaceAllUsesWith(&*NewFnArgIt);
1857 ++NewFnArgIt;
1858 }
1859 }
1860
1861 // Eliminate the instructions *after* we visited all of them.
1862 for (auto &CallSitePair : CallSitePairs) {
1863 CallBase &OldCB = *CallSitePair.first;
1864 CallBase &NewCB = *CallSitePair.second;
1865 assert(OldCB.getType() == NewCB.getType() &&
1866 "Cannot handle call sites with different types!");
1867 ModifiedFns.insert(OldCB.getFunction());
1868 CGUpdater.replaceCallSite(OldCB, NewCB);
1869 OldCB.replaceAllUsesWith(&NewCB);
1870 OldCB.eraseFromParent();
1871 }
1872
1873 // Replace the function in the call graph (if any).
1874 CGUpdater.replaceFunctionWith(*OldFn, *NewFn);
1875
1876 // If the old function was modified and needed to be reanalyzed, the new one
1877 // does now.
1878 if (ModifiedFns.erase(OldFn))
1879 ModifiedFns.insert(NewFn);
1880
1881 Changed = ChangeStatus::CHANGED;
1882 }
1883
1884 return Changed;
1885 }
1886
initializeInformationCache(const Function & CF,FunctionInfo & FI)1887 void InformationCache::initializeInformationCache(const Function &CF,
1888 FunctionInfo &FI) {
1889 // As we do not modify the function here we can remove the const
1890 // withouth breaking implicit assumptions. At the end of the day, we could
1891 // initialize the cache eagerly which would look the same to the users.
1892 Function &F = const_cast<Function &>(CF);
1893
1894 // Walk all instructions to find interesting instructions that might be
1895 // queried by abstract attributes during their initialization or update.
1896 // This has to happen before we create attributes.
1897
1898 for (Instruction &I : instructions(&F)) {
1899 bool IsInterestingOpcode = false;
1900
1901 // To allow easy access to all instructions in a function with a given
1902 // opcode we store them in the InfoCache. As not all opcodes are interesting
1903 // to concrete attributes we only cache the ones that are as identified in
1904 // the following switch.
1905 // Note: There are no concrete attributes now so this is initially empty.
1906 switch (I.getOpcode()) {
1907 default:
1908 assert(!isa<CallBase>(&I) &&
1909 "New call base instruction type needs to be known in the "
1910 "Attributor.");
1911 break;
1912 case Instruction::Call:
1913 // Calls are interesting on their own, additionally:
1914 // For `llvm.assume` calls we also fill the KnowledgeMap as we find them.
1915 // For `must-tail` calls we remember the caller and callee.
1916 if (auto *Assume = dyn_cast<AssumeInst>(&I)) {
1917 fillMapFromAssume(*Assume, KnowledgeMap);
1918 } else if (cast<CallInst>(I).isMustTailCall()) {
1919 FI.ContainsMustTailCall = true;
1920 if (const Function *Callee = cast<CallInst>(I).getCalledFunction())
1921 getFunctionInfo(*Callee).CalledViaMustTail = true;
1922 }
1923 LLVM_FALLTHROUGH;
1924 case Instruction::CallBr:
1925 case Instruction::Invoke:
1926 case Instruction::CleanupRet:
1927 case Instruction::CatchSwitch:
1928 case Instruction::AtomicRMW:
1929 case Instruction::AtomicCmpXchg:
1930 case Instruction::Br:
1931 case Instruction::Resume:
1932 case Instruction::Ret:
1933 case Instruction::Load:
1934 // The alignment of a pointer is interesting for loads.
1935 case Instruction::Store:
1936 // The alignment of a pointer is interesting for stores.
1937 IsInterestingOpcode = true;
1938 }
1939 if (IsInterestingOpcode) {
1940 auto *&Insts = FI.OpcodeInstMap[I.getOpcode()];
1941 if (!Insts)
1942 Insts = new (Allocator) InstructionVectorTy();
1943 Insts->push_back(&I);
1944 }
1945 if (I.mayReadOrWriteMemory())
1946 FI.RWInsts.push_back(&I);
1947 }
1948
1949 if (F.hasFnAttribute(Attribute::AlwaysInline) &&
1950 isInlineViable(F).isSuccess())
1951 InlineableFunctions.insert(&F);
1952 }
1953
getAAResultsForFunction(const Function & F)1954 AAResults *InformationCache::getAAResultsForFunction(const Function &F) {
1955 return AG.getAnalysis<AAManager>(F);
1956 }
1957
~FunctionInfo()1958 InformationCache::FunctionInfo::~FunctionInfo() {
1959 // The instruction vectors are allocated using a BumpPtrAllocator, we need to
1960 // manually destroy them.
1961 for (auto &It : OpcodeInstMap)
1962 It.getSecond()->~InstructionVectorTy();
1963 }
1964
recordDependence(const AbstractAttribute & FromAA,const AbstractAttribute & ToAA,DepClassTy DepClass)1965 void Attributor::recordDependence(const AbstractAttribute &FromAA,
1966 const AbstractAttribute &ToAA,
1967 DepClassTy DepClass) {
1968 if (DepClass == DepClassTy::NONE)
1969 return;
1970 // If we are outside of an update, thus before the actual fixpoint iteration
1971 // started (= when we create AAs), we do not track dependences because we will
1972 // put all AAs into the initial worklist anyway.
1973 if (DependenceStack.empty())
1974 return;
1975 if (FromAA.getState().isAtFixpoint())
1976 return;
1977 DependenceStack.back()->push_back({&FromAA, &ToAA, DepClass});
1978 }
1979
rememberDependences()1980 void Attributor::rememberDependences() {
1981 assert(!DependenceStack.empty() && "No dependences to remember!");
1982
1983 for (DepInfo &DI : *DependenceStack.back()) {
1984 assert((DI.DepClass == DepClassTy::REQUIRED ||
1985 DI.DepClass == DepClassTy::OPTIONAL) &&
1986 "Expected required or optional dependence (1 bit)!");
1987 auto &DepAAs = const_cast<AbstractAttribute &>(*DI.FromAA).Deps;
1988 DepAAs.push_back(AbstractAttribute::DepTy(
1989 const_cast<AbstractAttribute *>(DI.ToAA), unsigned(DI.DepClass)));
1990 }
1991 }
1992
identifyDefaultAbstractAttributes(Function & F)1993 void Attributor::identifyDefaultAbstractAttributes(Function &F) {
1994 if (!VisitedFunctions.insert(&F).second)
1995 return;
1996 if (F.isDeclaration())
1997 return;
1998
1999 // In non-module runs we need to look at the call sites of a function to
2000 // determine if it is part of a must-tail call edge. This will influence what
2001 // attributes we can derive.
2002 InformationCache::FunctionInfo &FI = InfoCache.getFunctionInfo(F);
2003 if (!isModulePass() && !FI.CalledViaMustTail) {
2004 for (const Use &U : F.uses())
2005 if (const auto *CB = dyn_cast<CallBase>(U.getUser()))
2006 if (CB->isCallee(&U) && CB->isMustTailCall())
2007 FI.CalledViaMustTail = true;
2008 }
2009
2010 IRPosition FPos = IRPosition::function(F);
2011
2012 // Check for dead BasicBlocks in every function.
2013 // We need dead instruction detection because we do not want to deal with
2014 // broken IR in which SSA rules do not apply.
2015 getOrCreateAAFor<AAIsDead>(FPos);
2016
2017 // Every function might be "will-return".
2018 getOrCreateAAFor<AAWillReturn>(FPos);
2019
2020 // Every function might contain instructions that cause "undefined behavior".
2021 getOrCreateAAFor<AAUndefinedBehavior>(FPos);
2022
2023 // Every function can be nounwind.
2024 getOrCreateAAFor<AANoUnwind>(FPos);
2025
2026 // Every function might be marked "nosync"
2027 getOrCreateAAFor<AANoSync>(FPos);
2028
2029 // Every function might be "no-free".
2030 getOrCreateAAFor<AANoFree>(FPos);
2031
2032 // Every function might be "no-return".
2033 getOrCreateAAFor<AANoReturn>(FPos);
2034
2035 // Every function might be "no-recurse".
2036 getOrCreateAAFor<AANoRecurse>(FPos);
2037
2038 // Every function might be "readnone/readonly/writeonly/...".
2039 getOrCreateAAFor<AAMemoryBehavior>(FPos);
2040
2041 // Every function can be "readnone/argmemonly/inaccessiblememonly/...".
2042 getOrCreateAAFor<AAMemoryLocation>(FPos);
2043
2044 // Every function might be applicable for Heap-To-Stack conversion.
2045 if (EnableHeapToStack)
2046 getOrCreateAAFor<AAHeapToStack>(FPos);
2047
2048 // Return attributes are only appropriate if the return type is non void.
2049 Type *ReturnType = F.getReturnType();
2050 if (!ReturnType->isVoidTy()) {
2051 // Argument attribute "returned" --- Create only one per function even
2052 // though it is an argument attribute.
2053 getOrCreateAAFor<AAReturnedValues>(FPos);
2054
2055 IRPosition RetPos = IRPosition::returned(F);
2056
2057 // Every returned value might be dead.
2058 getOrCreateAAFor<AAIsDead>(RetPos);
2059
2060 // Every function might be simplified.
2061 getOrCreateAAFor<AAValueSimplify>(RetPos);
2062
2063 // Every returned value might be marked noundef.
2064 getOrCreateAAFor<AANoUndef>(RetPos);
2065
2066 if (ReturnType->isPointerTy()) {
2067
2068 // Every function with pointer return type might be marked align.
2069 getOrCreateAAFor<AAAlign>(RetPos);
2070
2071 // Every function with pointer return type might be marked nonnull.
2072 getOrCreateAAFor<AANonNull>(RetPos);
2073
2074 // Every function with pointer return type might be marked noalias.
2075 getOrCreateAAFor<AANoAlias>(RetPos);
2076
2077 // Every function with pointer return type might be marked
2078 // dereferenceable.
2079 getOrCreateAAFor<AADereferenceable>(RetPos);
2080 }
2081 }
2082
2083 for (Argument &Arg : F.args()) {
2084 IRPosition ArgPos = IRPosition::argument(Arg);
2085
2086 // Every argument might be simplified.
2087 getOrCreateAAFor<AAValueSimplify>(ArgPos);
2088
2089 // Every argument might be dead.
2090 getOrCreateAAFor<AAIsDead>(ArgPos);
2091
2092 // Every argument might be marked noundef.
2093 getOrCreateAAFor<AANoUndef>(ArgPos);
2094
2095 if (Arg.getType()->isPointerTy()) {
2096 // Every argument with pointer type might be marked nonnull.
2097 getOrCreateAAFor<AANonNull>(ArgPos);
2098
2099 // Every argument with pointer type might be marked noalias.
2100 getOrCreateAAFor<AANoAlias>(ArgPos);
2101
2102 // Every argument with pointer type might be marked dereferenceable.
2103 getOrCreateAAFor<AADereferenceable>(ArgPos);
2104
2105 // Every argument with pointer type might be marked align.
2106 getOrCreateAAFor<AAAlign>(ArgPos);
2107
2108 // Every argument with pointer type might be marked nocapture.
2109 getOrCreateAAFor<AANoCapture>(ArgPos);
2110
2111 // Every argument with pointer type might be marked
2112 // "readnone/readonly/writeonly/..."
2113 getOrCreateAAFor<AAMemoryBehavior>(ArgPos);
2114
2115 // Every argument with pointer type might be marked nofree.
2116 getOrCreateAAFor<AANoFree>(ArgPos);
2117
2118 // Every argument with pointer type might be privatizable (or promotable)
2119 getOrCreateAAFor<AAPrivatizablePtr>(ArgPos);
2120 }
2121 }
2122
2123 auto CallSitePred = [&](Instruction &I) -> bool {
2124 auto &CB = cast<CallBase>(I);
2125 IRPosition CBRetPos = IRPosition::callsite_returned(CB);
2126
2127 // Call sites might be dead if they do not have side effects and no live
2128 // users. The return value might be dead if there are no live users.
2129 getOrCreateAAFor<AAIsDead>(CBRetPos);
2130
2131 Function *Callee = CB.getCalledFunction();
2132 // TODO: Even if the callee is not known now we might be able to simplify
2133 // the call/callee.
2134 if (!Callee)
2135 return true;
2136
2137 // Skip declarations except if annotations on their call sites were
2138 // explicitly requested.
2139 if (!AnnotateDeclarationCallSites && Callee->isDeclaration() &&
2140 !Callee->hasMetadata(LLVMContext::MD_callback))
2141 return true;
2142
2143 if (!Callee->getReturnType()->isVoidTy() && !CB.use_empty()) {
2144
2145 IRPosition CBRetPos = IRPosition::callsite_returned(CB);
2146
2147 // Call site return integer values might be limited by a constant range.
2148 if (Callee->getReturnType()->isIntegerTy())
2149 getOrCreateAAFor<AAValueConstantRange>(CBRetPos);
2150 }
2151
2152 for (int I = 0, E = CB.getNumArgOperands(); I < E; ++I) {
2153
2154 IRPosition CBArgPos = IRPosition::callsite_argument(CB, I);
2155
2156 // Every call site argument might be dead.
2157 getOrCreateAAFor<AAIsDead>(CBArgPos);
2158
2159 // Call site argument might be simplified.
2160 getOrCreateAAFor<AAValueSimplify>(CBArgPos);
2161
2162 // Every call site argument might be marked "noundef".
2163 getOrCreateAAFor<AANoUndef>(CBArgPos);
2164
2165 if (!CB.getArgOperand(I)->getType()->isPointerTy())
2166 continue;
2167
2168 // Call site argument attribute "non-null".
2169 getOrCreateAAFor<AANonNull>(CBArgPos);
2170
2171 // Call site argument attribute "nocapture".
2172 getOrCreateAAFor<AANoCapture>(CBArgPos);
2173
2174 // Call site argument attribute "no-alias".
2175 getOrCreateAAFor<AANoAlias>(CBArgPos);
2176
2177 // Call site argument attribute "dereferenceable".
2178 getOrCreateAAFor<AADereferenceable>(CBArgPos);
2179
2180 // Call site argument attribute "align".
2181 getOrCreateAAFor<AAAlign>(CBArgPos);
2182
2183 // Call site argument attribute
2184 // "readnone/readonly/writeonly/..."
2185 getOrCreateAAFor<AAMemoryBehavior>(CBArgPos);
2186
2187 // Call site argument attribute "nofree".
2188 getOrCreateAAFor<AANoFree>(CBArgPos);
2189 }
2190 return true;
2191 };
2192
2193 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
2194 bool Success;
2195 Success = checkForAllInstructionsImpl(
2196 nullptr, OpcodeInstMap, CallSitePred, nullptr, nullptr,
2197 {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
2198 (unsigned)Instruction::Call});
2199 (void)Success;
2200 assert(Success && "Expected the check call to be successful!");
2201
2202 auto LoadStorePred = [&](Instruction &I) -> bool {
2203 if (isa<LoadInst>(I))
2204 getOrCreateAAFor<AAAlign>(
2205 IRPosition::value(*cast<LoadInst>(I).getPointerOperand()));
2206 else
2207 getOrCreateAAFor<AAAlign>(
2208 IRPosition::value(*cast<StoreInst>(I).getPointerOperand()));
2209 return true;
2210 };
2211 Success = checkForAllInstructionsImpl(
2212 nullptr, OpcodeInstMap, LoadStorePred, nullptr, nullptr,
2213 {(unsigned)Instruction::Load, (unsigned)Instruction::Store});
2214 (void)Success;
2215 assert(Success && "Expected the check call to be successful!");
2216 }
2217
2218 /// Helpers to ease debugging through output streams and print calls.
2219 ///
2220 ///{
operator <<(raw_ostream & OS,ChangeStatus S)2221 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
2222 return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
2223 }
2224
operator <<(raw_ostream & OS,IRPosition::Kind AP)2225 raw_ostream &llvm::operator<<(raw_ostream &OS, IRPosition::Kind AP) {
2226 switch (AP) {
2227 case IRPosition::IRP_INVALID:
2228 return OS << "inv";
2229 case IRPosition::IRP_FLOAT:
2230 return OS << "flt";
2231 case IRPosition::IRP_RETURNED:
2232 return OS << "fn_ret";
2233 case IRPosition::IRP_CALL_SITE_RETURNED:
2234 return OS << "cs_ret";
2235 case IRPosition::IRP_FUNCTION:
2236 return OS << "fn";
2237 case IRPosition::IRP_CALL_SITE:
2238 return OS << "cs";
2239 case IRPosition::IRP_ARGUMENT:
2240 return OS << "arg";
2241 case IRPosition::IRP_CALL_SITE_ARGUMENT:
2242 return OS << "cs_arg";
2243 }
2244 llvm_unreachable("Unknown attribute position!");
2245 }
2246
operator <<(raw_ostream & OS,const IRPosition & Pos)2247 raw_ostream &llvm::operator<<(raw_ostream &OS, const IRPosition &Pos) {
2248 const Value &AV = Pos.getAssociatedValue();
2249 OS << "{" << Pos.getPositionKind() << ":" << AV.getName() << " ["
2250 << Pos.getAnchorValue().getName() << "@" << Pos.getCallSiteArgNo() << "]";
2251
2252 if (Pos.hasCallBaseContext())
2253 OS << "[cb_context:" << *Pos.getCallBaseContext() << "]";
2254 return OS << "}";
2255 }
2256
operator <<(raw_ostream & OS,const IntegerRangeState & S)2257 raw_ostream &llvm::operator<<(raw_ostream &OS, const IntegerRangeState &S) {
2258 OS << "range-state(" << S.getBitWidth() << ")<";
2259 S.getKnown().print(OS);
2260 OS << " / ";
2261 S.getAssumed().print(OS);
2262 OS << ">";
2263
2264 return OS << static_cast<const AbstractState &>(S);
2265 }
2266
operator <<(raw_ostream & OS,const AbstractState & S)2267 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
2268 return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
2269 }
2270
operator <<(raw_ostream & OS,const AbstractAttribute & AA)2271 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
2272 AA.print(OS);
2273 return OS;
2274 }
2275
operator <<(raw_ostream & OS,const PotentialConstantIntValuesState & S)2276 raw_ostream &llvm::operator<<(raw_ostream &OS,
2277 const PotentialConstantIntValuesState &S) {
2278 OS << "set-state(< {";
2279 if (!S.isValidState())
2280 OS << "full-set";
2281 else {
2282 for (auto &it : S.getAssumedSet())
2283 OS << it << ", ";
2284 if (S.undefIsContained())
2285 OS << "undef ";
2286 }
2287 OS << "} >)";
2288
2289 return OS;
2290 }
2291
print(raw_ostream & OS) const2292 void AbstractAttribute::print(raw_ostream &OS) const {
2293 OS << "[";
2294 OS << getName();
2295 OS << "] for CtxI ";
2296
2297 if (auto *I = getCtxI()) {
2298 OS << "'";
2299 I->print(OS);
2300 OS << "'";
2301 } else
2302 OS << "<<null inst>>";
2303
2304 OS << " at position " << getIRPosition() << " with state " << getAsStr()
2305 << '\n';
2306 }
2307
printWithDeps(raw_ostream & OS) const2308 void AbstractAttribute::printWithDeps(raw_ostream &OS) const {
2309 print(OS);
2310
2311 for (const auto &DepAA : Deps) {
2312 auto *AA = DepAA.getPointer();
2313 OS << " updates ";
2314 AA->print(OS);
2315 }
2316
2317 OS << '\n';
2318 }
2319 ///}
2320
2321 /// ----------------------------------------------------------------------------
2322 /// Pass (Manager) Boilerplate
2323 /// ----------------------------------------------------------------------------
2324
runAttributorOnFunctions(InformationCache & InfoCache,SetVector<Function * > & Functions,AnalysisGetter & AG,CallGraphUpdater & CGUpdater,bool DeleteFns)2325 static bool runAttributorOnFunctions(InformationCache &InfoCache,
2326 SetVector<Function *> &Functions,
2327 AnalysisGetter &AG,
2328 CallGraphUpdater &CGUpdater,
2329 bool DeleteFns) {
2330 if (Functions.empty())
2331 return false;
2332
2333 LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << Functions.size()
2334 << " functions.\n");
2335
2336 // Create an Attributor and initially empty information cache that is filled
2337 // while we identify default attribute opportunities.
2338 Attributor A(Functions, InfoCache, CGUpdater, /* Allowed */ nullptr,
2339 DeleteFns);
2340
2341 // Create shallow wrappers for all functions that are not IPO amendable
2342 if (AllowShallowWrappers)
2343 for (Function *F : Functions)
2344 if (!A.isFunctionIPOAmendable(*F))
2345 Attributor::createShallowWrapper(*F);
2346
2347 // Internalize non-exact functions
2348 // TODO: for now we eagerly internalize functions without calculating the
2349 // cost, we need a cost interface to determine whether internalizing
2350 // a function is "benefitial"
2351 if (AllowDeepWrapper) {
2352 unsigned FunSize = Functions.size();
2353 for (unsigned u = 0; u < FunSize; u++) {
2354 Function *F = Functions[u];
2355 if (!F->isDeclaration() && !F->isDefinitionExact() && F->getNumUses() &&
2356 !GlobalValue::isInterposableLinkage(F->getLinkage())) {
2357 Function *NewF = internalizeFunction(*F);
2358 Functions.insert(NewF);
2359
2360 // Update call graph
2361 CGUpdater.replaceFunctionWith(*F, *NewF);
2362 for (const Use &U : NewF->uses())
2363 if (CallBase *CB = dyn_cast<CallBase>(U.getUser())) {
2364 auto *CallerF = CB->getCaller();
2365 CGUpdater.reanalyzeFunction(*CallerF);
2366 }
2367 }
2368 }
2369 }
2370
2371 for (Function *F : Functions) {
2372 if (F->hasExactDefinition())
2373 NumFnWithExactDefinition++;
2374 else
2375 NumFnWithoutExactDefinition++;
2376
2377 // We look at internal functions only on-demand but if any use is not a
2378 // direct call or outside the current set of analyzed functions, we have
2379 // to do it eagerly.
2380 if (F->hasLocalLinkage()) {
2381 if (llvm::all_of(F->uses(), [&Functions](const Use &U) {
2382 const auto *CB = dyn_cast<CallBase>(U.getUser());
2383 return CB && CB->isCallee(&U) &&
2384 Functions.count(const_cast<Function *>(CB->getCaller()));
2385 }))
2386 continue;
2387 }
2388
2389 // Populate the Attributor with abstract attribute opportunities in the
2390 // function and the information cache with IR information.
2391 A.identifyDefaultAbstractAttributes(*F);
2392 }
2393
2394 ChangeStatus Changed = A.run();
2395
2396 LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size()
2397 << " functions, result: " << Changed << ".\n");
2398 return Changed == ChangeStatus::CHANGED;
2399 }
2400
viewGraph()2401 void AADepGraph::viewGraph() { llvm::ViewGraph(this, "Dependency Graph"); }
2402
dumpGraph()2403 void AADepGraph::dumpGraph() {
2404 static std::atomic<int> CallTimes;
2405 std::string Prefix;
2406
2407 if (!DepGraphDotFileNamePrefix.empty())
2408 Prefix = DepGraphDotFileNamePrefix;
2409 else
2410 Prefix = "dep_graph";
2411 std::string Filename =
2412 Prefix + "_" + std::to_string(CallTimes.load()) + ".dot";
2413
2414 outs() << "Dependency graph dump to " << Filename << ".\n";
2415
2416 std::error_code EC;
2417
2418 raw_fd_ostream File(Filename, EC, sys::fs::OF_TextWithCRLF);
2419 if (!EC)
2420 llvm::WriteGraph(File, this);
2421
2422 CallTimes++;
2423 }
2424
print()2425 void AADepGraph::print() {
2426 for (auto DepAA : SyntheticRoot.Deps)
2427 cast<AbstractAttribute>(DepAA.getPointer())->printWithDeps(outs());
2428 }
2429
run(Module & M,ModuleAnalysisManager & AM)2430 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
2431 FunctionAnalysisManager &FAM =
2432 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
2433 AnalysisGetter AG(FAM);
2434
2435 SetVector<Function *> Functions;
2436 for (Function &F : M)
2437 Functions.insert(&F);
2438
2439 CallGraphUpdater CGUpdater;
2440 BumpPtrAllocator Allocator;
2441 InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr);
2442 if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
2443 /* DeleteFns */ true)) {
2444 // FIXME: Think about passes we will preserve and add them here.
2445 return PreservedAnalyses::none();
2446 }
2447 return PreservedAnalyses::all();
2448 }
2449
run(LazyCallGraph::SCC & C,CGSCCAnalysisManager & AM,LazyCallGraph & CG,CGSCCUpdateResult & UR)2450 PreservedAnalyses AttributorCGSCCPass::run(LazyCallGraph::SCC &C,
2451 CGSCCAnalysisManager &AM,
2452 LazyCallGraph &CG,
2453 CGSCCUpdateResult &UR) {
2454 FunctionAnalysisManager &FAM =
2455 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
2456 AnalysisGetter AG(FAM);
2457
2458 SetVector<Function *> Functions;
2459 for (LazyCallGraph::Node &N : C)
2460 Functions.insert(&N.getFunction());
2461
2462 if (Functions.empty())
2463 return PreservedAnalyses::all();
2464
2465 Module &M = *Functions.back()->getParent();
2466 CallGraphUpdater CGUpdater;
2467 CGUpdater.initialize(CG, C, AM, UR);
2468 BumpPtrAllocator Allocator;
2469 InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions);
2470 if (runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
2471 /* DeleteFns */ false)) {
2472 // FIXME: Think about passes we will preserve and add them here.
2473 PreservedAnalyses PA;
2474 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
2475 return PA;
2476 }
2477 return PreservedAnalyses::all();
2478 }
2479
2480 namespace llvm {
2481
2482 template <> struct GraphTraits<AADepGraphNode *> {
2483 using NodeRef = AADepGraphNode *;
2484 using DepTy = PointerIntPair<AADepGraphNode *, 1>;
2485 using EdgeRef = PointerIntPair<AADepGraphNode *, 1>;
2486
getEntryNodellvm::GraphTraits2487 static NodeRef getEntryNode(AADepGraphNode *DGN) { return DGN; }
DepGetValllvm::GraphTraits2488 static NodeRef DepGetVal(DepTy &DT) { return DT.getPointer(); }
2489
2490 using ChildIteratorType =
2491 mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
2492 using ChildEdgeIteratorType = TinyPtrVector<DepTy>::iterator;
2493
child_beginllvm::GraphTraits2494 static ChildIteratorType child_begin(NodeRef N) { return N->child_begin(); }
2495
child_endllvm::GraphTraits2496 static ChildIteratorType child_end(NodeRef N) { return N->child_end(); }
2497 };
2498
2499 template <>
2500 struct GraphTraits<AADepGraph *> : public GraphTraits<AADepGraphNode *> {
getEntryNodellvm::GraphTraits2501 static NodeRef getEntryNode(AADepGraph *DG) { return DG->GetEntryNode(); }
2502
2503 using nodes_iterator =
2504 mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
2505
nodes_beginllvm::GraphTraits2506 static nodes_iterator nodes_begin(AADepGraph *DG) { return DG->begin(); }
2507
nodes_endllvm::GraphTraits2508 static nodes_iterator nodes_end(AADepGraph *DG) { return DG->end(); }
2509 };
2510
2511 template <> struct DOTGraphTraits<AADepGraph *> : public DefaultDOTGraphTraits {
DOTGraphTraitsllvm::DOTGraphTraits2512 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
2513
getNodeLabelllvm::DOTGraphTraits2514 static std::string getNodeLabel(const AADepGraphNode *Node,
2515 const AADepGraph *DG) {
2516 std::string AAString;
2517 raw_string_ostream O(AAString);
2518 Node->print(O);
2519 return AAString;
2520 }
2521 };
2522
2523 } // end namespace llvm
2524
2525 namespace {
2526
2527 struct AttributorLegacyPass : public ModulePass {
2528 static char ID;
2529
AttributorLegacyPass__anonfe0f36560a11::AttributorLegacyPass2530 AttributorLegacyPass() : ModulePass(ID) {
2531 initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry());
2532 }
2533
runOnModule__anonfe0f36560a11::AttributorLegacyPass2534 bool runOnModule(Module &M) override {
2535 if (skipModule(M))
2536 return false;
2537
2538 AnalysisGetter AG;
2539 SetVector<Function *> Functions;
2540 for (Function &F : M)
2541 Functions.insert(&F);
2542
2543 CallGraphUpdater CGUpdater;
2544 BumpPtrAllocator Allocator;
2545 InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ nullptr);
2546 return runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
2547 /* DeleteFns*/ true);
2548 }
2549
getAnalysisUsage__anonfe0f36560a11::AttributorLegacyPass2550 void getAnalysisUsage(AnalysisUsage &AU) const override {
2551 // FIXME: Think about passes we will preserve and add them here.
2552 AU.addRequired<TargetLibraryInfoWrapperPass>();
2553 }
2554 };
2555
2556 struct AttributorCGSCCLegacyPass : public CallGraphSCCPass {
2557 static char ID;
2558
AttributorCGSCCLegacyPass__anonfe0f36560a11::AttributorCGSCCLegacyPass2559 AttributorCGSCCLegacyPass() : CallGraphSCCPass(ID) {
2560 initializeAttributorCGSCCLegacyPassPass(*PassRegistry::getPassRegistry());
2561 }
2562
runOnSCC__anonfe0f36560a11::AttributorCGSCCLegacyPass2563 bool runOnSCC(CallGraphSCC &SCC) override {
2564 if (skipSCC(SCC))
2565 return false;
2566
2567 SetVector<Function *> Functions;
2568 for (CallGraphNode *CGN : SCC)
2569 if (Function *Fn = CGN->getFunction())
2570 if (!Fn->isDeclaration())
2571 Functions.insert(Fn);
2572
2573 if (Functions.empty())
2574 return false;
2575
2576 AnalysisGetter AG;
2577 CallGraph &CG = const_cast<CallGraph &>(SCC.getCallGraph());
2578 CallGraphUpdater CGUpdater;
2579 CGUpdater.initialize(CG, SCC);
2580 Module &M = *Functions.back()->getParent();
2581 BumpPtrAllocator Allocator;
2582 InformationCache InfoCache(M, AG, Allocator, /* CGSCC */ &Functions);
2583 return runAttributorOnFunctions(InfoCache, Functions, AG, CGUpdater,
2584 /* DeleteFns */ false);
2585 }
2586
getAnalysisUsage__anonfe0f36560a11::AttributorCGSCCLegacyPass2587 void getAnalysisUsage(AnalysisUsage &AU) const override {
2588 // FIXME: Think about passes we will preserve and add them here.
2589 AU.addRequired<TargetLibraryInfoWrapperPass>();
2590 CallGraphSCCPass::getAnalysisUsage(AU);
2591 }
2592 };
2593
2594 } // end anonymous namespace
2595
createAttributorLegacyPass()2596 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
createAttributorCGSCCLegacyPass()2597 Pass *llvm::createAttributorCGSCCLegacyPass() {
2598 return new AttributorCGSCCLegacyPass();
2599 }
2600
2601 char AttributorLegacyPass::ID = 0;
2602 char AttributorCGSCCLegacyPass::ID = 0;
2603
2604 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
2605 "Deduce and propagate attributes", false, false)
2606 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
2607 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
2608 "Deduce and propagate attributes", false, false)
2609 INITIALIZE_PASS_BEGIN(AttributorCGSCCLegacyPass, "attributor-cgscc",
2610 "Deduce and propagate attributes (CGSCC pass)", false,
2611 false)
2612 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
2613 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
2614 INITIALIZE_PASS_END(AttributorCGSCCLegacyPass, "attributor-cgscc",
2615 "Deduce and propagate attributes (CGSCC pass)", false,
2616 false)
2617