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 inter procedural pass that deduces and/or propagating 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/DepthFirstIterator.h" 19 #include "llvm/ADT/STLExtras.h" 20 #include "llvm/ADT/SmallPtrSet.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/ADT/Statistic.h" 23 #include "llvm/Analysis/CaptureTracking.h" 24 #include "llvm/Analysis/EHPersonalities.h" 25 #include "llvm/Analysis/GlobalsModRef.h" 26 #include "llvm/Analysis/LazyValueInfo.h" 27 #include "llvm/Analysis/Loads.h" 28 #include "llvm/Analysis/MemoryBuiltins.h" 29 #include "llvm/Analysis/ScalarEvolution.h" 30 #include "llvm/Analysis/ValueTracking.h" 31 #include "llvm/IR/Argument.h" 32 #include "llvm/IR/Attributes.h" 33 #include "llvm/IR/CFG.h" 34 #include "llvm/IR/InstIterator.h" 35 #include "llvm/IR/IntrinsicInst.h" 36 #include "llvm/IR/Verifier.h" 37 #include "llvm/InitializePasses.h" 38 #include "llvm/Support/CommandLine.h" 39 #include "llvm/Support/Debug.h" 40 #include "llvm/Support/raw_ostream.h" 41 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 42 #include "llvm/Transforms/Utils/Local.h" 43 44 #include <cassert> 45 46 using namespace llvm; 47 48 #define DEBUG_TYPE "attributor" 49 50 STATISTIC(NumFnWithExactDefinition, 51 "Number of function with exact definitions"); 52 STATISTIC(NumFnWithoutExactDefinition, 53 "Number of function without exact definitions"); 54 STATISTIC(NumAttributesTimedOut, 55 "Number of abstract attributes timed out before fixpoint"); 56 STATISTIC(NumAttributesValidFixpoint, 57 "Number of abstract attributes in a valid fixpoint state"); 58 STATISTIC(NumAttributesManifested, 59 "Number of abstract attributes manifested in IR"); 60 STATISTIC(NumAttributesFixedDueToRequiredDependences, 61 "Number of abstract attributes fixed due to required dependences"); 62 63 // Some helper macros to deal with statistics tracking. 64 // 65 // Usage: 66 // For simple IR attribute tracking overload trackStatistics in the abstract 67 // attribute and choose the right STATS_DECLTRACK_********* macro, 68 // e.g.,: 69 // void trackStatistics() const override { 70 // STATS_DECLTRACK_ARG_ATTR(returned) 71 // } 72 // If there is a single "increment" side one can use the macro 73 // STATS_DECLTRACK with a custom message. If there are multiple increment 74 // sides, STATS_DECL and STATS_TRACK can also be used separatly. 75 // 76 #define BUILD_STAT_MSG_IR_ATTR(TYPE, NAME) \ 77 ("Number of " #TYPE " marked '" #NAME "'") 78 #define BUILD_STAT_NAME(NAME, TYPE) NumIR##TYPE##_##NAME 79 #define STATS_DECL_(NAME, MSG) STATISTIC(NAME, MSG); 80 #define STATS_DECL(NAME, TYPE, MSG) \ 81 STATS_DECL_(BUILD_STAT_NAME(NAME, TYPE), MSG); 82 #define STATS_TRACK(NAME, TYPE) ++(BUILD_STAT_NAME(NAME, TYPE)); 83 #define STATS_DECLTRACK(NAME, TYPE, MSG) \ 84 { \ 85 STATS_DECL(NAME, TYPE, MSG) \ 86 STATS_TRACK(NAME, TYPE) \ 87 } 88 #define STATS_DECLTRACK_ARG_ATTR(NAME) \ 89 STATS_DECLTRACK(NAME, Arguments, BUILD_STAT_MSG_IR_ATTR(arguments, NAME)) 90 #define STATS_DECLTRACK_CSARG_ATTR(NAME) \ 91 STATS_DECLTRACK(NAME, CSArguments, \ 92 BUILD_STAT_MSG_IR_ATTR(call site arguments, NAME)) 93 #define STATS_DECLTRACK_FN_ATTR(NAME) \ 94 STATS_DECLTRACK(NAME, Function, BUILD_STAT_MSG_IR_ATTR(functions, NAME)) 95 #define STATS_DECLTRACK_CS_ATTR(NAME) \ 96 STATS_DECLTRACK(NAME, CS, BUILD_STAT_MSG_IR_ATTR(call site, NAME)) 97 #define STATS_DECLTRACK_FNRET_ATTR(NAME) \ 98 STATS_DECLTRACK(NAME, FunctionReturn, \ 99 BUILD_STAT_MSG_IR_ATTR(function returns, NAME)) 100 #define STATS_DECLTRACK_CSRET_ATTR(NAME) \ 101 STATS_DECLTRACK(NAME, CSReturn, \ 102 BUILD_STAT_MSG_IR_ATTR(call site returns, NAME)) 103 #define STATS_DECLTRACK_FLOATING_ATTR(NAME) \ 104 STATS_DECLTRACK(NAME, Floating, \ 105 ("Number of floating values known to be '" #NAME "'")) 106 107 // Specialization of the operator<< for abstract attributes subclasses. This 108 // disambiguates situations where multiple operators are applicable. 109 namespace llvm { 110 #define PIPE_OPERATOR(CLASS) \ 111 raw_ostream &operator<<(raw_ostream &OS, const CLASS &AA) { \ 112 return OS << static_cast<const AbstractAttribute &>(AA); \ 113 } 114 115 PIPE_OPERATOR(AAIsDead) 116 PIPE_OPERATOR(AANoUnwind) 117 PIPE_OPERATOR(AANoSync) 118 PIPE_OPERATOR(AANoRecurse) 119 PIPE_OPERATOR(AAWillReturn) 120 PIPE_OPERATOR(AANoReturn) 121 PIPE_OPERATOR(AAReturnedValues) 122 PIPE_OPERATOR(AANonNull) 123 PIPE_OPERATOR(AANoAlias) 124 PIPE_OPERATOR(AADereferenceable) 125 PIPE_OPERATOR(AAAlign) 126 PIPE_OPERATOR(AANoCapture) 127 PIPE_OPERATOR(AAValueSimplify) 128 PIPE_OPERATOR(AANoFree) 129 PIPE_OPERATOR(AAHeapToStack) 130 PIPE_OPERATOR(AAReachability) 131 PIPE_OPERATOR(AAMemoryBehavior) 132 PIPE_OPERATOR(AAValueConstantRange) 133 134 #undef PIPE_OPERATOR 135 } // namespace llvm 136 137 // TODO: Determine a good default value. 138 // 139 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads 140 // (when run with the first 5 abstract attributes). The results also indicate 141 // that we never reach 32 iterations but always find a fixpoint sooner. 142 // 143 // This will become more evolved once we perform two interleaved fixpoint 144 // iterations: bottom-up and top-down. 145 static cl::opt<unsigned> 146 MaxFixpointIterations("attributor-max-iterations", cl::Hidden, 147 cl::desc("Maximal number of fixpoint iterations."), 148 cl::init(32)); 149 static cl::opt<bool> VerifyMaxFixpointIterations( 150 "attributor-max-iterations-verify", cl::Hidden, 151 cl::desc("Verify that max-iterations is a tight bound for a fixpoint"), 152 cl::init(false)); 153 154 static cl::opt<bool> DisableAttributor( 155 "attributor-disable", cl::Hidden, 156 cl::desc("Disable the attributor inter-procedural deduction pass."), 157 cl::init(true)); 158 159 static cl::opt<bool> AnnotateDeclarationCallSites( 160 "attributor-annotate-decl-cs", cl::Hidden, 161 cl::desc("Annotate call sites of function declarations."), cl::init(false)); 162 163 static cl::opt<bool> ManifestInternal( 164 "attributor-manifest-internal", cl::Hidden, 165 cl::desc("Manifest Attributor internal string attributes."), 166 cl::init(false)); 167 168 static cl::opt<unsigned> DepRecInterval( 169 "attributor-dependence-recompute-interval", cl::Hidden, 170 cl::desc("Number of iterations until dependences are recomputed."), 171 cl::init(4)); 172 173 static cl::opt<bool> EnableHeapToStack("enable-heap-to-stack-conversion", 174 cl::init(true), cl::Hidden); 175 176 static cl::opt<int> MaxHeapToStackSize("max-heap-to-stack-size", cl::init(128), 177 cl::Hidden); 178 179 /// Logic operators for the change status enum class. 180 /// 181 ///{ 182 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) { 183 return l == ChangeStatus::CHANGED ? l : r; 184 } 185 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) { 186 return l == ChangeStatus::UNCHANGED ? l : r; 187 } 188 ///} 189 190 Argument *IRPosition::getAssociatedArgument() const { 191 if (getPositionKind() == IRP_ARGUMENT) 192 return cast<Argument>(&getAnchorValue()); 193 194 // Not an Argument and no argument number means this is not a call site 195 // argument, thus we cannot find a callback argument to return. 196 int ArgNo = getArgNo(); 197 if (ArgNo < 0) 198 return nullptr; 199 200 // Use abstract call sites to make the connection between the call site 201 // values and the ones in callbacks. If a callback was found that makes use 202 // of the underlying call site operand, we want the corresponding callback 203 // callee argument and not the direct callee argument. 204 Optional<Argument *> CBCandidateArg; 205 SmallVector<const Use *, 4> CBUses; 206 ImmutableCallSite ICS(&getAnchorValue()); 207 AbstractCallSite::getCallbackUses(ICS, CBUses); 208 for (const Use *U : CBUses) { 209 AbstractCallSite ACS(U); 210 assert(ACS && ACS.isCallbackCall()); 211 if (!ACS.getCalledFunction()) 212 continue; 213 214 for (unsigned u = 0, e = ACS.getNumArgOperands(); u < e; u++) { 215 216 // Test if the underlying call site operand is argument number u of the 217 // callback callee. 218 if (ACS.getCallArgOperandNo(u) != ArgNo) 219 continue; 220 221 assert(ACS.getCalledFunction()->arg_size() > u && 222 "ACS mapped into var-args arguments!"); 223 if (CBCandidateArg.hasValue()) { 224 CBCandidateArg = nullptr; 225 break; 226 } 227 CBCandidateArg = ACS.getCalledFunction()->getArg(u); 228 } 229 } 230 231 // If we found a unique callback candidate argument, return it. 232 if (CBCandidateArg.hasValue() && CBCandidateArg.getValue()) 233 return CBCandidateArg.getValue(); 234 235 // If no callbacks were found, or none used the underlying call site operand 236 // exclusively, use the direct callee argument if available. 237 const Function *Callee = ICS.getCalledFunction(); 238 if (Callee && Callee->arg_size() > unsigned(ArgNo)) 239 return Callee->getArg(ArgNo); 240 241 return nullptr; 242 } 243 244 /// For calls (and invokes) we will only replace instruction uses to not disturb 245 /// the old style call graph. 246 /// TODO: Remove this once we get rid of the old PM. 247 static void replaceAllInstructionUsesWith(Value &Old, Value &New) { 248 if (!isa<CallBase>(Old)) 249 return Old.replaceAllUsesWith(&New); 250 SmallVector<Use *, 8> Uses; 251 for (Use &U : Old.uses()) 252 if (isa<Instruction>(U.getUser())) 253 Uses.push_back(&U); 254 for (Use *U : Uses) 255 U->set(&New); 256 } 257 258 /// Recursively visit all values that might become \p IRP at some point. This 259 /// will be done by looking through cast instructions, selects, phis, and calls 260 /// with the "returned" attribute. Once we cannot look through the value any 261 /// further, the callback \p VisitValueCB is invoked and passed the current 262 /// value, the \p State, and a flag to indicate if we stripped anything. To 263 /// limit how much effort is invested, we will never visit more values than 264 /// specified by \p MaxValues. 265 template <typename AAType, typename StateTy> 266 static bool genericValueTraversal( 267 Attributor &A, IRPosition IRP, const AAType &QueryingAA, StateTy &State, 268 const function_ref<bool(Value &, StateTy &, bool)> &VisitValueCB, 269 int MaxValues = 8) { 270 271 const AAIsDead *LivenessAA = nullptr; 272 if (IRP.getAnchorScope()) 273 LivenessAA = &A.getAAFor<AAIsDead>( 274 QueryingAA, IRPosition::function(*IRP.getAnchorScope()), 275 /* TrackDependence */ false); 276 bool AnyDead = false; 277 278 // TODO: Use Positions here to allow context sensitivity in VisitValueCB 279 SmallPtrSet<Value *, 16> Visited; 280 SmallVector<Value *, 16> Worklist; 281 Worklist.push_back(&IRP.getAssociatedValue()); 282 283 int Iteration = 0; 284 do { 285 Value *V = Worklist.pop_back_val(); 286 287 // Check if we should process the current value. To prevent endless 288 // recursion keep a record of the values we followed! 289 if (!Visited.insert(V).second) 290 continue; 291 292 // Make sure we limit the compile time for complex expressions. 293 if (Iteration++ >= MaxValues) 294 return false; 295 296 // Explicitly look through calls with a "returned" attribute if we do 297 // not have a pointer as stripPointerCasts only works on them. 298 Value *NewV = nullptr; 299 if (V->getType()->isPointerTy()) { 300 NewV = V->stripPointerCasts(); 301 } else { 302 CallSite CS(V); 303 if (CS && CS.getCalledFunction()) { 304 for (Argument &Arg : CS.getCalledFunction()->args()) 305 if (Arg.hasReturnedAttr()) { 306 NewV = CS.getArgOperand(Arg.getArgNo()); 307 break; 308 } 309 } 310 } 311 if (NewV && NewV != V) { 312 Worklist.push_back(NewV); 313 continue; 314 } 315 316 // Look through select instructions, visit both potential values. 317 if (auto *SI = dyn_cast<SelectInst>(V)) { 318 Worklist.push_back(SI->getTrueValue()); 319 Worklist.push_back(SI->getFalseValue()); 320 continue; 321 } 322 323 // Look through phi nodes, visit all live operands. 324 if (auto *PHI = dyn_cast<PHINode>(V)) { 325 assert(LivenessAA && 326 "Expected liveness in the presence of instructions!"); 327 for (unsigned u = 0, e = PHI->getNumIncomingValues(); u < e; u++) { 328 const BasicBlock *IncomingBB = PHI->getIncomingBlock(u); 329 if (LivenessAA->isAssumedDead(IncomingBB->getTerminator())) { 330 AnyDead = true; 331 continue; 332 } 333 Worklist.push_back(PHI->getIncomingValue(u)); 334 } 335 continue; 336 } 337 338 // Once a leaf is reached we inform the user through the callback. 339 if (!VisitValueCB(*V, State, Iteration > 1)) 340 return false; 341 } while (!Worklist.empty()); 342 343 // If we actually used liveness information so we have to record a dependence. 344 if (AnyDead) 345 A.recordDependence(*LivenessAA, QueryingAA, DepClassTy::OPTIONAL); 346 347 // All values have been visited. 348 return true; 349 } 350 351 /// Return true if \p New is equal or worse than \p Old. 352 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) { 353 if (!Old.isIntAttribute()) 354 return true; 355 356 return Old.getValueAsInt() >= New.getValueAsInt(); 357 } 358 359 /// Return true if the information provided by \p Attr was added to the 360 /// attribute list \p Attrs. This is only the case if it was not already present 361 /// in \p Attrs at the position describe by \p PK and \p AttrIdx. 362 static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr, 363 AttributeList &Attrs, int AttrIdx) { 364 365 if (Attr.isEnumAttribute()) { 366 Attribute::AttrKind Kind = Attr.getKindAsEnum(); 367 if (Attrs.hasAttribute(AttrIdx, Kind)) 368 if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) 369 return false; 370 Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr); 371 return true; 372 } 373 if (Attr.isStringAttribute()) { 374 StringRef Kind = Attr.getKindAsString(); 375 if (Attrs.hasAttribute(AttrIdx, Kind)) 376 if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) 377 return false; 378 Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr); 379 return true; 380 } 381 if (Attr.isIntAttribute()) { 382 Attribute::AttrKind Kind = Attr.getKindAsEnum(); 383 if (Attrs.hasAttribute(AttrIdx, Kind)) 384 if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind))) 385 return false; 386 Attrs = Attrs.removeAttribute(Ctx, AttrIdx, Kind); 387 Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr); 388 return true; 389 } 390 391 llvm_unreachable("Expected enum or string attribute!"); 392 } 393 394 static const Value * 395 getBasePointerOfAccessPointerOperand(const Instruction *I, int64_t &BytesOffset, 396 const DataLayout &DL, 397 bool AllowNonInbounds = false) { 398 const Value *Ptr = 399 Attributor::getPointerOperand(I, /* AllowVolatile */ false); 400 if (!Ptr) 401 return nullptr; 402 403 return GetPointerBaseWithConstantOffset(Ptr, BytesOffset, DL, 404 AllowNonInbounds); 405 } 406 407 ChangeStatus AbstractAttribute::update(Attributor &A) { 408 ChangeStatus HasChanged = ChangeStatus::UNCHANGED; 409 if (getState().isAtFixpoint()) 410 return HasChanged; 411 412 LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n"); 413 414 HasChanged = updateImpl(A); 415 416 LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this 417 << "\n"); 418 419 return HasChanged; 420 } 421 422 ChangeStatus 423 IRAttributeManifest::manifestAttrs(Attributor &A, const IRPosition &IRP, 424 const ArrayRef<Attribute> &DeducedAttrs) { 425 Function *ScopeFn = IRP.getAssociatedFunction(); 426 IRPosition::Kind PK = IRP.getPositionKind(); 427 428 // In the following some generic code that will manifest attributes in 429 // DeducedAttrs if they improve the current IR. Due to the different 430 // annotation positions we use the underlying AttributeList interface. 431 432 AttributeList Attrs; 433 switch (PK) { 434 case IRPosition::IRP_INVALID: 435 case IRPosition::IRP_FLOAT: 436 return ChangeStatus::UNCHANGED; 437 case IRPosition::IRP_ARGUMENT: 438 case IRPosition::IRP_FUNCTION: 439 case IRPosition::IRP_RETURNED: 440 Attrs = ScopeFn->getAttributes(); 441 break; 442 case IRPosition::IRP_CALL_SITE: 443 case IRPosition::IRP_CALL_SITE_RETURNED: 444 case IRPosition::IRP_CALL_SITE_ARGUMENT: 445 Attrs = ImmutableCallSite(&IRP.getAnchorValue()).getAttributes(); 446 break; 447 } 448 449 ChangeStatus HasChanged = ChangeStatus::UNCHANGED; 450 LLVMContext &Ctx = IRP.getAnchorValue().getContext(); 451 for (const Attribute &Attr : DeducedAttrs) { 452 if (!addIfNotExistent(Ctx, Attr, Attrs, IRP.getAttrIdx())) 453 continue; 454 455 HasChanged = ChangeStatus::CHANGED; 456 } 457 458 if (HasChanged == ChangeStatus::UNCHANGED) 459 return HasChanged; 460 461 switch (PK) { 462 case IRPosition::IRP_ARGUMENT: 463 case IRPosition::IRP_FUNCTION: 464 case IRPosition::IRP_RETURNED: 465 ScopeFn->setAttributes(Attrs); 466 break; 467 case IRPosition::IRP_CALL_SITE: 468 case IRPosition::IRP_CALL_SITE_RETURNED: 469 case IRPosition::IRP_CALL_SITE_ARGUMENT: 470 CallSite(&IRP.getAnchorValue()).setAttributes(Attrs); 471 break; 472 case IRPosition::IRP_INVALID: 473 case IRPosition::IRP_FLOAT: 474 break; 475 } 476 477 return HasChanged; 478 } 479 480 const IRPosition IRPosition::EmptyKey(255); 481 const IRPosition IRPosition::TombstoneKey(256); 482 483 SubsumingPositionIterator::SubsumingPositionIterator(const IRPosition &IRP) { 484 IRPositions.emplace_back(IRP); 485 486 ImmutableCallSite ICS(&IRP.getAnchorValue()); 487 switch (IRP.getPositionKind()) { 488 case IRPosition::IRP_INVALID: 489 case IRPosition::IRP_FLOAT: 490 case IRPosition::IRP_FUNCTION: 491 return; 492 case IRPosition::IRP_ARGUMENT: 493 case IRPosition::IRP_RETURNED: 494 IRPositions.emplace_back( 495 IRPosition::function(*IRP.getAssociatedFunction())); 496 return; 497 case IRPosition::IRP_CALL_SITE: 498 assert(ICS && "Expected call site!"); 499 // TODO: We need to look at the operand bundles similar to the redirection 500 // in CallBase. 501 if (!ICS.hasOperandBundles()) 502 if (const Function *Callee = ICS.getCalledFunction()) 503 IRPositions.emplace_back(IRPosition::function(*Callee)); 504 return; 505 case IRPosition::IRP_CALL_SITE_RETURNED: 506 assert(ICS && "Expected call site!"); 507 // TODO: We need to look at the operand bundles similar to the redirection 508 // in CallBase. 509 if (!ICS.hasOperandBundles()) { 510 if (const Function *Callee = ICS.getCalledFunction()) { 511 IRPositions.emplace_back(IRPosition::returned(*Callee)); 512 IRPositions.emplace_back(IRPosition::function(*Callee)); 513 } 514 } 515 IRPositions.emplace_back( 516 IRPosition::callsite_function(cast<CallBase>(*ICS.getInstruction()))); 517 return; 518 case IRPosition::IRP_CALL_SITE_ARGUMENT: { 519 int ArgNo = IRP.getArgNo(); 520 assert(ICS && ArgNo >= 0 && "Expected call site!"); 521 // TODO: We need to look at the operand bundles similar to the redirection 522 // in CallBase. 523 if (!ICS.hasOperandBundles()) { 524 const Function *Callee = ICS.getCalledFunction(); 525 if (Callee && Callee->arg_size() > unsigned(ArgNo)) 526 IRPositions.emplace_back(IRPosition::argument(*Callee->getArg(ArgNo))); 527 if (Callee) 528 IRPositions.emplace_back(IRPosition::function(*Callee)); 529 } 530 IRPositions.emplace_back(IRPosition::value(IRP.getAssociatedValue())); 531 return; 532 } 533 } 534 } 535 536 bool IRPosition::hasAttr(ArrayRef<Attribute::AttrKind> AKs, 537 bool IgnoreSubsumingPositions) const { 538 for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) { 539 for (Attribute::AttrKind AK : AKs) 540 if (EquivIRP.getAttr(AK).getKindAsEnum() == AK) 541 return true; 542 // The first position returned by the SubsumingPositionIterator is 543 // always the position itself. If we ignore subsuming positions we 544 // are done after the first iteration. 545 if (IgnoreSubsumingPositions) 546 break; 547 } 548 return false; 549 } 550 551 void IRPosition::getAttrs(ArrayRef<Attribute::AttrKind> AKs, 552 SmallVectorImpl<Attribute> &Attrs, 553 bool IgnoreSubsumingPositions) const { 554 for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) { 555 for (Attribute::AttrKind AK : AKs) { 556 const Attribute &Attr = EquivIRP.getAttr(AK); 557 if (Attr.getKindAsEnum() == AK) 558 Attrs.push_back(Attr); 559 } 560 // The first position returned by the SubsumingPositionIterator is 561 // always the position itself. If we ignore subsuming positions we 562 // are done after the first iteration. 563 if (IgnoreSubsumingPositions) 564 break; 565 } 566 } 567 568 void IRPosition::verify() { 569 switch (KindOrArgNo) { 570 default: 571 assert(KindOrArgNo >= 0 && "Expected argument or call site argument!"); 572 assert((isa<CallBase>(AnchorVal) || isa<Argument>(AnchorVal)) && 573 "Expected call base or argument for positive attribute index!"); 574 if (isa<Argument>(AnchorVal)) { 575 assert(cast<Argument>(AnchorVal)->getArgNo() == unsigned(getArgNo()) && 576 "Argument number mismatch!"); 577 assert(cast<Argument>(AnchorVal) == &getAssociatedValue() && 578 "Associated value mismatch!"); 579 } else { 580 assert(cast<CallBase>(*AnchorVal).arg_size() > unsigned(getArgNo()) && 581 "Call site argument number mismatch!"); 582 assert(cast<CallBase>(*AnchorVal).getArgOperand(getArgNo()) == 583 &getAssociatedValue() && 584 "Associated value mismatch!"); 585 } 586 break; 587 case IRP_INVALID: 588 assert(!AnchorVal && "Expected no value for an invalid position!"); 589 break; 590 case IRP_FLOAT: 591 assert((!isa<CallBase>(&getAssociatedValue()) && 592 !isa<Argument>(&getAssociatedValue())) && 593 "Expected specialized kind for call base and argument values!"); 594 break; 595 case IRP_RETURNED: 596 assert(isa<Function>(AnchorVal) && 597 "Expected function for a 'returned' position!"); 598 assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!"); 599 break; 600 case IRP_CALL_SITE_RETURNED: 601 assert((isa<CallBase>(AnchorVal)) && 602 "Expected call base for 'call site returned' position!"); 603 assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!"); 604 break; 605 case IRP_CALL_SITE: 606 assert((isa<CallBase>(AnchorVal)) && 607 "Expected call base for 'call site function' position!"); 608 assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!"); 609 break; 610 case IRP_FUNCTION: 611 assert(isa<Function>(AnchorVal) && 612 "Expected function for a 'function' position!"); 613 assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!"); 614 break; 615 } 616 } 617 618 namespace { 619 /// Helper function to clamp a state \p S of type \p StateType with the 620 /// information in \p R and indicate/return if \p S did change (as-in update is 621 /// required to be run again). 622 template <typename StateType> 623 ChangeStatus clampStateAndIndicateChange(StateType &S, const StateType &R) { 624 auto Assumed = S.getAssumed(); 625 S ^= R; 626 return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED 627 : ChangeStatus::CHANGED; 628 } 629 630 /// Clamp the information known for all returned values of a function 631 /// (identified by \p QueryingAA) into \p S. 632 template <typename AAType, typename StateType = typename AAType::StateType> 633 static void clampReturnedValueStates(Attributor &A, const AAType &QueryingAA, 634 StateType &S) { 635 LLVM_DEBUG(dbgs() << "[Attributor] Clamp return value states for " 636 << QueryingAA << " into " << S << "\n"); 637 638 assert((QueryingAA.getIRPosition().getPositionKind() == 639 IRPosition::IRP_RETURNED || 640 QueryingAA.getIRPosition().getPositionKind() == 641 IRPosition::IRP_CALL_SITE_RETURNED) && 642 "Can only clamp returned value states for a function returned or call " 643 "site returned position!"); 644 645 // Use an optional state as there might not be any return values and we want 646 // to join (IntegerState::operator&) the state of all there are. 647 Optional<StateType> T; 648 649 // Callback for each possibly returned value. 650 auto CheckReturnValue = [&](Value &RV) -> bool { 651 const IRPosition &RVPos = IRPosition::value(RV); 652 const AAType &AA = A.getAAFor<AAType>(QueryingAA, RVPos); 653 LLVM_DEBUG(dbgs() << "[Attributor] RV: " << RV << " AA: " << AA.getAsStr() 654 << " @ " << RVPos << "\n"); 655 const StateType &AAS = static_cast<const StateType &>(AA.getState()); 656 if (T.hasValue()) 657 *T &= AAS; 658 else 659 T = AAS; 660 LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " RV State: " << T 661 << "\n"); 662 return T->isValidState(); 663 }; 664 665 if (!A.checkForAllReturnedValues(CheckReturnValue, QueryingAA)) 666 S.indicatePessimisticFixpoint(); 667 else if (T.hasValue()) 668 S ^= *T; 669 } 670 671 /// Helper class to compose two generic deduction 672 template <typename AAType, typename Base, typename StateType, 673 template <typename...> class F, template <typename...> class G> 674 struct AAComposeTwoGenericDeduction 675 : public F<AAType, G<AAType, Base, StateType>, StateType> { 676 AAComposeTwoGenericDeduction(const IRPosition &IRP) 677 : F<AAType, G<AAType, Base, StateType>, StateType>(IRP) {} 678 679 /// See AbstractAttribute::updateImpl(...). 680 ChangeStatus updateImpl(Attributor &A) override { 681 ChangeStatus ChangedF = 682 F<AAType, G<AAType, Base, StateType>, StateType>::updateImpl(A); 683 ChangeStatus ChangedG = G<AAType, Base, StateType>::updateImpl(A); 684 return ChangedF | ChangedG; 685 } 686 }; 687 688 /// Helper class for generic deduction: return value -> returned position. 689 template <typename AAType, typename Base, 690 typename StateType = typename AAType::StateType> 691 struct AAReturnedFromReturnedValues : public Base { 692 AAReturnedFromReturnedValues(const IRPosition &IRP) : Base(IRP) {} 693 694 /// See AbstractAttribute::updateImpl(...). 695 ChangeStatus updateImpl(Attributor &A) override { 696 StateType S; 697 clampReturnedValueStates<AAType, StateType>(A, *this, S); 698 // TODO: If we know we visited all returned values, thus no are assumed 699 // dead, we can take the known information from the state T. 700 return clampStateAndIndicateChange<StateType>(this->getState(), S); 701 } 702 }; 703 704 /// Clamp the information known at all call sites for a given argument 705 /// (identified by \p QueryingAA) into \p S. 706 template <typename AAType, typename StateType = typename AAType::StateType> 707 static void clampCallSiteArgumentStates(Attributor &A, const AAType &QueryingAA, 708 StateType &S) { 709 LLVM_DEBUG(dbgs() << "[Attributor] Clamp call site argument states for " 710 << QueryingAA << " into " << S << "\n"); 711 712 assert(QueryingAA.getIRPosition().getPositionKind() == 713 IRPosition::IRP_ARGUMENT && 714 "Can only clamp call site argument states for an argument position!"); 715 716 // Use an optional state as there might not be any return values and we want 717 // to join (IntegerState::operator&) the state of all there are. 718 Optional<StateType> T; 719 720 // The argument number which is also the call site argument number. 721 unsigned ArgNo = QueryingAA.getIRPosition().getArgNo(); 722 723 auto CallSiteCheck = [&](AbstractCallSite ACS) { 724 const IRPosition &ACSArgPos = IRPosition::callsite_argument(ACS, ArgNo); 725 // Check if a coresponding argument was found or if it is on not associated 726 // (which can happen for callback calls). 727 if (ACSArgPos.getPositionKind() == IRPosition::IRP_INVALID) 728 return false; 729 730 const AAType &AA = A.getAAFor<AAType>(QueryingAA, ACSArgPos); 731 LLVM_DEBUG(dbgs() << "[Attributor] ACS: " << *ACS.getInstruction() 732 << " AA: " << AA.getAsStr() << " @" << ACSArgPos << "\n"); 733 const StateType &AAS = static_cast<const StateType &>(AA.getState()); 734 if (T.hasValue()) 735 *T &= AAS; 736 else 737 T = AAS; 738 LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " CSA State: " << T 739 << "\n"); 740 return T->isValidState(); 741 }; 742 743 if (!A.checkForAllCallSites(CallSiteCheck, QueryingAA, true)) 744 S.indicatePessimisticFixpoint(); 745 else if (T.hasValue()) 746 S ^= *T; 747 } 748 749 /// Helper class for generic deduction: call site argument -> argument position. 750 template <typename AAType, typename Base, 751 typename StateType = typename AAType::StateType> 752 struct AAArgumentFromCallSiteArguments : public Base { 753 AAArgumentFromCallSiteArguments(const IRPosition &IRP) : Base(IRP) {} 754 755 /// See AbstractAttribute::updateImpl(...). 756 ChangeStatus updateImpl(Attributor &A) override { 757 StateType S; 758 clampCallSiteArgumentStates<AAType, StateType>(A, *this, S); 759 // TODO: If we know we visited all incoming values, thus no are assumed 760 // dead, we can take the known information from the state T. 761 return clampStateAndIndicateChange<StateType>(this->getState(), S); 762 } 763 }; 764 765 /// Helper class for generic replication: function returned -> cs returned. 766 template <typename AAType, typename Base, 767 typename StateType = typename AAType::StateType> 768 struct AACallSiteReturnedFromReturned : public Base { 769 AACallSiteReturnedFromReturned(const IRPosition &IRP) : Base(IRP) {} 770 771 /// See AbstractAttribute::updateImpl(...). 772 ChangeStatus updateImpl(Attributor &A) override { 773 assert(this->getIRPosition().getPositionKind() == 774 IRPosition::IRP_CALL_SITE_RETURNED && 775 "Can only wrap function returned positions for call site returned " 776 "positions!"); 777 auto &S = this->getState(); 778 779 const Function *AssociatedFunction = 780 this->getIRPosition().getAssociatedFunction(); 781 if (!AssociatedFunction) 782 return S.indicatePessimisticFixpoint(); 783 784 IRPosition FnPos = IRPosition::returned(*AssociatedFunction); 785 const AAType &AA = A.getAAFor<AAType>(*this, FnPos); 786 return clampStateAndIndicateChange( 787 S, static_cast<const typename AAType::StateType &>(AA.getState())); 788 } 789 }; 790 791 /// Helper class for generic deduction using must-be-executed-context 792 /// Base class is required to have `followUse` method. 793 794 /// bool followUse(Attributor &A, const Use *U, const Instruction *I) 795 /// U - Underlying use. 796 /// I - The user of the \p U. 797 /// `followUse` returns true if the value should be tracked transitively. 798 799 template <typename AAType, typename Base, 800 typename StateType = typename AAType::StateType> 801 struct AAFromMustBeExecutedContext : public Base { 802 AAFromMustBeExecutedContext(const IRPosition &IRP) : Base(IRP) {} 803 804 void initialize(Attributor &A) override { 805 Base::initialize(A); 806 const IRPosition &IRP = this->getIRPosition(); 807 Instruction *CtxI = IRP.getCtxI(); 808 809 if (!CtxI) 810 return; 811 812 for (const Use &U : IRP.getAssociatedValue().uses()) 813 Uses.insert(&U); 814 } 815 816 /// See AbstractAttribute::updateImpl(...). 817 ChangeStatus updateImpl(Attributor &A) override { 818 auto BeforeState = this->getState(); 819 auto &S = this->getState(); 820 Instruction *CtxI = this->getIRPosition().getCtxI(); 821 if (!CtxI) 822 return ChangeStatus::UNCHANGED; 823 824 MustBeExecutedContextExplorer &Explorer = 825 A.getInfoCache().getMustBeExecutedContextExplorer(); 826 827 auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI); 828 for (unsigned u = 0; u < Uses.size(); ++u) { 829 const Use *U = Uses[u]; 830 if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) { 831 bool Found = Explorer.findInContextOf(UserI, EIt, EEnd); 832 if (Found && Base::followUse(A, U, UserI)) 833 for (const Use &Us : UserI->uses()) 834 Uses.insert(&Us); 835 } 836 } 837 838 return BeforeState == S ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED; 839 } 840 841 private: 842 /// Container for (transitive) uses of the associated value. 843 SetVector<const Use *> Uses; 844 }; 845 846 template <typename AAType, typename Base, 847 typename StateType = typename AAType::StateType> 848 using AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext = 849 AAComposeTwoGenericDeduction<AAType, Base, StateType, 850 AAFromMustBeExecutedContext, 851 AAArgumentFromCallSiteArguments>; 852 853 template <typename AAType, typename Base, 854 typename StateType = typename AAType::StateType> 855 using AACallSiteReturnedFromReturnedAndMustBeExecutedContext = 856 AAComposeTwoGenericDeduction<AAType, Base, StateType, 857 AAFromMustBeExecutedContext, 858 AACallSiteReturnedFromReturned>; 859 860 /// -----------------------NoUnwind Function Attribute-------------------------- 861 862 struct AANoUnwindImpl : AANoUnwind { 863 AANoUnwindImpl(const IRPosition &IRP) : AANoUnwind(IRP) {} 864 865 const std::string getAsStr() const override { 866 return getAssumed() ? "nounwind" : "may-unwind"; 867 } 868 869 /// See AbstractAttribute::updateImpl(...). 870 ChangeStatus updateImpl(Attributor &A) override { 871 auto Opcodes = { 872 (unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, 873 (unsigned)Instruction::Call, (unsigned)Instruction::CleanupRet, 874 (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume}; 875 876 auto CheckForNoUnwind = [&](Instruction &I) { 877 if (!I.mayThrow()) 878 return true; 879 880 if (ImmutableCallSite ICS = ImmutableCallSite(&I)) { 881 const auto &NoUnwindAA = 882 A.getAAFor<AANoUnwind>(*this, IRPosition::callsite_function(ICS)); 883 return NoUnwindAA.isAssumedNoUnwind(); 884 } 885 return false; 886 }; 887 888 if (!A.checkForAllInstructions(CheckForNoUnwind, *this, Opcodes)) 889 return indicatePessimisticFixpoint(); 890 891 return ChangeStatus::UNCHANGED; 892 } 893 }; 894 895 struct AANoUnwindFunction final : public AANoUnwindImpl { 896 AANoUnwindFunction(const IRPosition &IRP) : AANoUnwindImpl(IRP) {} 897 898 /// See AbstractAttribute::trackStatistics() 899 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nounwind) } 900 }; 901 902 /// NoUnwind attribute deduction for a call sites. 903 struct AANoUnwindCallSite final : AANoUnwindImpl { 904 AANoUnwindCallSite(const IRPosition &IRP) : AANoUnwindImpl(IRP) {} 905 906 /// See AbstractAttribute::initialize(...). 907 void initialize(Attributor &A) override { 908 AANoUnwindImpl::initialize(A); 909 Function *F = getAssociatedFunction(); 910 if (!F) 911 indicatePessimisticFixpoint(); 912 } 913 914 /// See AbstractAttribute::updateImpl(...). 915 ChangeStatus updateImpl(Attributor &A) override { 916 // TODO: Once we have call site specific value information we can provide 917 // call site specific liveness information and then it makes 918 // sense to specialize attributes for call sites arguments instead of 919 // redirecting requests to the callee argument. 920 Function *F = getAssociatedFunction(); 921 const IRPosition &FnPos = IRPosition::function(*F); 922 auto &FnAA = A.getAAFor<AANoUnwind>(*this, FnPos); 923 return clampStateAndIndicateChange( 924 getState(), 925 static_cast<const AANoUnwind::StateType &>(FnAA.getState())); 926 } 927 928 /// See AbstractAttribute::trackStatistics() 929 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nounwind); } 930 }; 931 932 /// --------------------- Function Return Values ------------------------------- 933 934 /// "Attribute" that collects all potential returned values and the return 935 /// instructions that they arise from. 936 /// 937 /// If there is a unique returned value R, the manifest method will: 938 /// - mark R with the "returned" attribute, if R is an argument. 939 class AAReturnedValuesImpl : public AAReturnedValues, public AbstractState { 940 941 /// Mapping of values potentially returned by the associated function to the 942 /// return instructions that might return them. 943 MapVector<Value *, SmallSetVector<ReturnInst *, 4>> ReturnedValues; 944 945 /// Mapping to remember the number of returned values for a call site such 946 /// that we can avoid updates if nothing changed. 947 DenseMap<const CallBase *, unsigned> NumReturnedValuesPerKnownAA; 948 949 /// Set of unresolved calls returned by the associated function. 950 SmallSetVector<CallBase *, 4> UnresolvedCalls; 951 952 /// State flags 953 /// 954 ///{ 955 bool IsFixed = false; 956 bool IsValidState = true; 957 ///} 958 959 public: 960 AAReturnedValuesImpl(const IRPosition &IRP) : AAReturnedValues(IRP) {} 961 962 /// See AbstractAttribute::initialize(...). 963 void initialize(Attributor &A) override { 964 // Reset the state. 965 IsFixed = false; 966 IsValidState = true; 967 ReturnedValues.clear(); 968 969 Function *F = getAssociatedFunction(); 970 if (!F) { 971 indicatePessimisticFixpoint(); 972 return; 973 } 974 975 // The map from instruction opcodes to those instructions in the function. 976 auto &OpcodeInstMap = A.getInfoCache().getOpcodeInstMapForFunction(*F); 977 978 // Look through all arguments, if one is marked as returned we are done. 979 for (Argument &Arg : F->args()) { 980 if (Arg.hasReturnedAttr()) { 981 auto &ReturnInstSet = ReturnedValues[&Arg]; 982 for (Instruction *RI : OpcodeInstMap[Instruction::Ret]) 983 ReturnInstSet.insert(cast<ReturnInst>(RI)); 984 985 indicateOptimisticFixpoint(); 986 return; 987 } 988 } 989 990 if (!F->hasExactDefinition()) 991 indicatePessimisticFixpoint(); 992 } 993 994 /// See AbstractAttribute::manifest(...). 995 ChangeStatus manifest(Attributor &A) override; 996 997 /// See AbstractAttribute::getState(...). 998 AbstractState &getState() override { return *this; } 999 1000 /// See AbstractAttribute::getState(...). 1001 const AbstractState &getState() const override { return *this; } 1002 1003 /// See AbstractAttribute::updateImpl(Attributor &A). 1004 ChangeStatus updateImpl(Attributor &A) override; 1005 1006 llvm::iterator_range<iterator> returned_values() override { 1007 return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end()); 1008 } 1009 1010 llvm::iterator_range<const_iterator> returned_values() const override { 1011 return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end()); 1012 } 1013 1014 const SmallSetVector<CallBase *, 4> &getUnresolvedCalls() const override { 1015 return UnresolvedCalls; 1016 } 1017 1018 /// Return the number of potential return values, -1 if unknown. 1019 size_t getNumReturnValues() const override { 1020 return isValidState() ? ReturnedValues.size() : -1; 1021 } 1022 1023 /// Return an assumed unique return value if a single candidate is found. If 1024 /// there cannot be one, return a nullptr. If it is not clear yet, return the 1025 /// Optional::NoneType. 1026 Optional<Value *> getAssumedUniqueReturnValue(Attributor &A) const; 1027 1028 /// See AbstractState::checkForAllReturnedValues(...). 1029 bool checkForAllReturnedValuesAndReturnInsts( 1030 const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> 1031 &Pred) const override; 1032 1033 /// Pretty print the attribute similar to the IR representation. 1034 const std::string getAsStr() const override; 1035 1036 /// See AbstractState::isAtFixpoint(). 1037 bool isAtFixpoint() const override { return IsFixed; } 1038 1039 /// See AbstractState::isValidState(). 1040 bool isValidState() const override { return IsValidState; } 1041 1042 /// See AbstractState::indicateOptimisticFixpoint(...). 1043 ChangeStatus indicateOptimisticFixpoint() override { 1044 IsFixed = true; 1045 return ChangeStatus::UNCHANGED; 1046 } 1047 1048 ChangeStatus indicatePessimisticFixpoint() override { 1049 IsFixed = true; 1050 IsValidState = false; 1051 return ChangeStatus::CHANGED; 1052 } 1053 }; 1054 1055 ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) { 1056 ChangeStatus Changed = ChangeStatus::UNCHANGED; 1057 1058 // Bookkeeping. 1059 assert(isValidState()); 1060 STATS_DECLTRACK(KnownReturnValues, FunctionReturn, 1061 "Number of function with known return values"); 1062 1063 // Check if we have an assumed unique return value that we could manifest. 1064 Optional<Value *> UniqueRV = getAssumedUniqueReturnValue(A); 1065 1066 if (!UniqueRV.hasValue() || !UniqueRV.getValue()) 1067 return Changed; 1068 1069 // Bookkeeping. 1070 STATS_DECLTRACK(UniqueReturnValue, FunctionReturn, 1071 "Number of function with unique return"); 1072 1073 // Callback to replace the uses of CB with the constant C. 1074 auto ReplaceCallSiteUsersWith = [](CallBase &CB, Constant &C) { 1075 if (CB.getNumUses() == 0 || CB.isMustTailCall()) 1076 return ChangeStatus::UNCHANGED; 1077 replaceAllInstructionUsesWith(CB, C); 1078 return ChangeStatus::CHANGED; 1079 }; 1080 1081 // If the assumed unique return value is an argument, annotate it. 1082 if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) { 1083 // TODO: This should be handled differently! 1084 this->AnchorVal = UniqueRVArg; 1085 this->KindOrArgNo = UniqueRVArg->getArgNo(); 1086 Changed = IRAttribute::manifest(A); 1087 } else if (auto *RVC = dyn_cast<Constant>(UniqueRV.getValue())) { 1088 // We can replace the returned value with the unique returned constant. 1089 Value &AnchorValue = getAnchorValue(); 1090 if (Function *F = dyn_cast<Function>(&AnchorValue)) { 1091 for (const Use &U : F->uses()) 1092 if (CallBase *CB = dyn_cast<CallBase>(U.getUser())) 1093 if (CB->isCallee(&U)) { 1094 Constant *RVCCast = 1095 CB->getType() == RVC->getType() 1096 ? RVC 1097 : ConstantExpr::getTruncOrBitCast(RVC, CB->getType()); 1098 Changed = ReplaceCallSiteUsersWith(*CB, *RVCCast) | Changed; 1099 } 1100 } else { 1101 assert(isa<CallBase>(AnchorValue) && 1102 "Expcected a function or call base anchor!"); 1103 Constant *RVCCast = 1104 AnchorValue.getType() == RVC->getType() 1105 ? RVC 1106 : ConstantExpr::getTruncOrBitCast(RVC, AnchorValue.getType()); 1107 Changed = ReplaceCallSiteUsersWith(cast<CallBase>(AnchorValue), *RVCCast); 1108 } 1109 if (Changed == ChangeStatus::CHANGED) 1110 STATS_DECLTRACK(UniqueConstantReturnValue, FunctionReturn, 1111 "Number of function returns replaced by constant return"); 1112 } 1113 1114 return Changed; 1115 } 1116 1117 const std::string AAReturnedValuesImpl::getAsStr() const { 1118 return (isAtFixpoint() ? "returns(#" : "may-return(#") + 1119 (isValidState() ? std::to_string(getNumReturnValues()) : "?") + 1120 ")[#UC: " + std::to_string(UnresolvedCalls.size()) + "]"; 1121 } 1122 1123 Optional<Value *> 1124 AAReturnedValuesImpl::getAssumedUniqueReturnValue(Attributor &A) const { 1125 // If checkForAllReturnedValues provides a unique value, ignoring potential 1126 // undef values that can also be present, it is assumed to be the actual 1127 // return value and forwarded to the caller of this method. If there are 1128 // multiple, a nullptr is returned indicating there cannot be a unique 1129 // returned value. 1130 Optional<Value *> UniqueRV; 1131 1132 auto Pred = [&](Value &RV) -> bool { 1133 // If we found a second returned value and neither the current nor the saved 1134 // one is an undef, there is no unique returned value. Undefs are special 1135 // since we can pretend they have any value. 1136 if (UniqueRV.hasValue() && UniqueRV != &RV && 1137 !(isa<UndefValue>(RV) || isa<UndefValue>(UniqueRV.getValue()))) { 1138 UniqueRV = nullptr; 1139 return false; 1140 } 1141 1142 // Do not overwrite a value with an undef. 1143 if (!UniqueRV.hasValue() || !isa<UndefValue>(RV)) 1144 UniqueRV = &RV; 1145 1146 return true; 1147 }; 1148 1149 if (!A.checkForAllReturnedValues(Pred, *this)) 1150 UniqueRV = nullptr; 1151 1152 return UniqueRV; 1153 } 1154 1155 bool AAReturnedValuesImpl::checkForAllReturnedValuesAndReturnInsts( 1156 const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> 1157 &Pred) const { 1158 if (!isValidState()) 1159 return false; 1160 1161 // Check all returned values but ignore call sites as long as we have not 1162 // encountered an overdefined one during an update. 1163 for (auto &It : ReturnedValues) { 1164 Value *RV = It.first; 1165 1166 CallBase *CB = dyn_cast<CallBase>(RV); 1167 if (CB && !UnresolvedCalls.count(CB)) 1168 continue; 1169 1170 if (!Pred(*RV, It.second)) 1171 return false; 1172 } 1173 1174 return true; 1175 } 1176 1177 ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) { 1178 size_t NumUnresolvedCalls = UnresolvedCalls.size(); 1179 bool Changed = false; 1180 1181 // State used in the value traversals starting in returned values. 1182 struct RVState { 1183 // The map in which we collect return values -> return instrs. 1184 decltype(ReturnedValues) &RetValsMap; 1185 // The flag to indicate a change. 1186 bool &Changed; 1187 // The return instrs we come from. 1188 SmallSetVector<ReturnInst *, 4> RetInsts; 1189 }; 1190 1191 // Callback for a leaf value returned by the associated function. 1192 auto VisitValueCB = [](Value &Val, RVState &RVS, bool) -> bool { 1193 auto Size = RVS.RetValsMap[&Val].size(); 1194 RVS.RetValsMap[&Val].insert(RVS.RetInsts.begin(), RVS.RetInsts.end()); 1195 bool Inserted = RVS.RetValsMap[&Val].size() != Size; 1196 RVS.Changed |= Inserted; 1197 LLVM_DEBUG({ 1198 if (Inserted) 1199 dbgs() << "[AAReturnedValues] 1 Add new returned value " << Val 1200 << " => " << RVS.RetInsts.size() << "\n"; 1201 }); 1202 return true; 1203 }; 1204 1205 // Helper method to invoke the generic value traversal. 1206 auto VisitReturnedValue = [&](Value &RV, RVState &RVS) { 1207 IRPosition RetValPos = IRPosition::value(RV); 1208 return genericValueTraversal<AAReturnedValues, RVState>(A, RetValPos, *this, 1209 RVS, VisitValueCB); 1210 }; 1211 1212 // Callback for all "return intructions" live in the associated function. 1213 auto CheckReturnInst = [this, &VisitReturnedValue, &Changed](Instruction &I) { 1214 ReturnInst &Ret = cast<ReturnInst>(I); 1215 RVState RVS({ReturnedValues, Changed, {}}); 1216 RVS.RetInsts.insert(&Ret); 1217 return VisitReturnedValue(*Ret.getReturnValue(), RVS); 1218 }; 1219 1220 // Start by discovering returned values from all live returned instructions in 1221 // the associated function. 1222 if (!A.checkForAllInstructions(CheckReturnInst, *this, {Instruction::Ret})) 1223 return indicatePessimisticFixpoint(); 1224 1225 // Once returned values "directly" present in the code are handled we try to 1226 // resolve returned calls. 1227 decltype(ReturnedValues) NewRVsMap; 1228 for (auto &It : ReturnedValues) { 1229 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *It.first 1230 << " by #" << It.second.size() << " RIs\n"); 1231 CallBase *CB = dyn_cast<CallBase>(It.first); 1232 if (!CB || UnresolvedCalls.count(CB)) 1233 continue; 1234 1235 if (!CB->getCalledFunction()) { 1236 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Unresolved call: " << *CB 1237 << "\n"); 1238 UnresolvedCalls.insert(CB); 1239 continue; 1240 } 1241 1242 // TODO: use the function scope once we have call site AAReturnedValues. 1243 const auto &RetValAA = A.getAAFor<AAReturnedValues>( 1244 *this, IRPosition::function(*CB->getCalledFunction())); 1245 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Found another AAReturnedValues: " 1246 << RetValAA << "\n"); 1247 1248 // Skip dead ends, thus if we do not know anything about the returned 1249 // call we mark it as unresolved and it will stay that way. 1250 if (!RetValAA.getState().isValidState()) { 1251 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Unresolved call: " << *CB 1252 << "\n"); 1253 UnresolvedCalls.insert(CB); 1254 continue; 1255 } 1256 1257 // Do not try to learn partial information. If the callee has unresolved 1258 // return values we will treat the call as unresolved/opaque. 1259 auto &RetValAAUnresolvedCalls = RetValAA.getUnresolvedCalls(); 1260 if (!RetValAAUnresolvedCalls.empty()) { 1261 UnresolvedCalls.insert(CB); 1262 continue; 1263 } 1264 1265 // Now check if we can track transitively returned values. If possible, thus 1266 // if all return value can be represented in the current scope, do so. 1267 bool Unresolved = false; 1268 for (auto &RetValAAIt : RetValAA.returned_values()) { 1269 Value *RetVal = RetValAAIt.first; 1270 if (isa<Argument>(RetVal) || isa<CallBase>(RetVal) || 1271 isa<Constant>(RetVal)) 1272 continue; 1273 // Anything that did not fit in the above categories cannot be resolved, 1274 // mark the call as unresolved. 1275 LLVM_DEBUG(dbgs() << "[AAReturnedValues] transitively returned value " 1276 "cannot be translated: " 1277 << *RetVal << "\n"); 1278 UnresolvedCalls.insert(CB); 1279 Unresolved = true; 1280 break; 1281 } 1282 1283 if (Unresolved) 1284 continue; 1285 1286 // Now track transitively returned values. 1287 unsigned &NumRetAA = NumReturnedValuesPerKnownAA[CB]; 1288 if (NumRetAA == RetValAA.getNumReturnValues()) { 1289 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Skip call as it has not " 1290 "changed since it was seen last\n"); 1291 continue; 1292 } 1293 NumRetAA = RetValAA.getNumReturnValues(); 1294 1295 for (auto &RetValAAIt : RetValAA.returned_values()) { 1296 Value *RetVal = RetValAAIt.first; 1297 if (Argument *Arg = dyn_cast<Argument>(RetVal)) { 1298 // Arguments are mapped to call site operands and we begin the traversal 1299 // again. 1300 bool Unused = false; 1301 RVState RVS({NewRVsMap, Unused, RetValAAIt.second}); 1302 VisitReturnedValue(*CB->getArgOperand(Arg->getArgNo()), RVS); 1303 continue; 1304 } else if (isa<CallBase>(RetVal)) { 1305 // Call sites are resolved by the callee attribute over time, no need to 1306 // do anything for us. 1307 continue; 1308 } else if (isa<Constant>(RetVal)) { 1309 // Constants are valid everywhere, we can simply take them. 1310 NewRVsMap[RetVal].insert(It.second.begin(), It.second.end()); 1311 continue; 1312 } 1313 } 1314 } 1315 1316 // To avoid modifications to the ReturnedValues map while we iterate over it 1317 // we kept record of potential new entries in a copy map, NewRVsMap. 1318 for (auto &It : NewRVsMap) { 1319 assert(!It.second.empty() && "Entry does not add anything."); 1320 auto &ReturnInsts = ReturnedValues[It.first]; 1321 for (ReturnInst *RI : It.second) 1322 if (ReturnInsts.insert(RI)) { 1323 LLVM_DEBUG(dbgs() << "[AAReturnedValues] Add new returned value " 1324 << *It.first << " => " << *RI << "\n"); 1325 Changed = true; 1326 } 1327 } 1328 1329 Changed |= (NumUnresolvedCalls != UnresolvedCalls.size()); 1330 return Changed ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; 1331 } 1332 1333 struct AAReturnedValuesFunction final : public AAReturnedValuesImpl { 1334 AAReturnedValuesFunction(const IRPosition &IRP) : AAReturnedValuesImpl(IRP) {} 1335 1336 /// See AbstractAttribute::trackStatistics() 1337 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(returned) } 1338 }; 1339 1340 /// Returned values information for a call sites. 1341 struct AAReturnedValuesCallSite final : AAReturnedValuesImpl { 1342 AAReturnedValuesCallSite(const IRPosition &IRP) : AAReturnedValuesImpl(IRP) {} 1343 1344 /// See AbstractAttribute::initialize(...). 1345 void initialize(Attributor &A) override { 1346 // TODO: Once we have call site specific value information we can provide 1347 // call site specific liveness information and then it makes 1348 // sense to specialize attributes for call sites instead of 1349 // redirecting requests to the callee. 1350 llvm_unreachable("Abstract attributes for returned values are not " 1351 "supported for call sites yet!"); 1352 } 1353 1354 /// See AbstractAttribute::updateImpl(...). 1355 ChangeStatus updateImpl(Attributor &A) override { 1356 return indicatePessimisticFixpoint(); 1357 } 1358 1359 /// See AbstractAttribute::trackStatistics() 1360 void trackStatistics() const override {} 1361 }; 1362 1363 /// ------------------------ NoSync Function Attribute ------------------------- 1364 1365 struct AANoSyncImpl : AANoSync { 1366 AANoSyncImpl(const IRPosition &IRP) : AANoSync(IRP) {} 1367 1368 const std::string getAsStr() const override { 1369 return getAssumed() ? "nosync" : "may-sync"; 1370 } 1371 1372 /// See AbstractAttribute::updateImpl(...). 1373 ChangeStatus updateImpl(Attributor &A) override; 1374 1375 /// Helper function used to determine whether an instruction is non-relaxed 1376 /// atomic. In other words, if an atomic instruction does not have unordered 1377 /// or monotonic ordering 1378 static bool isNonRelaxedAtomic(Instruction *I); 1379 1380 /// Helper function used to determine whether an instruction is volatile. 1381 static bool isVolatile(Instruction *I); 1382 1383 /// Helper function uset to check if intrinsic is volatile (memcpy, memmove, 1384 /// memset). 1385 static bool isNoSyncIntrinsic(Instruction *I); 1386 }; 1387 1388 bool AANoSyncImpl::isNonRelaxedAtomic(Instruction *I) { 1389 if (!I->isAtomic()) 1390 return false; 1391 1392 AtomicOrdering Ordering; 1393 switch (I->getOpcode()) { 1394 case Instruction::AtomicRMW: 1395 Ordering = cast<AtomicRMWInst>(I)->getOrdering(); 1396 break; 1397 case Instruction::Store: 1398 Ordering = cast<StoreInst>(I)->getOrdering(); 1399 break; 1400 case Instruction::Load: 1401 Ordering = cast<LoadInst>(I)->getOrdering(); 1402 break; 1403 case Instruction::Fence: { 1404 auto *FI = cast<FenceInst>(I); 1405 if (FI->getSyncScopeID() == SyncScope::SingleThread) 1406 return false; 1407 Ordering = FI->getOrdering(); 1408 break; 1409 } 1410 case Instruction::AtomicCmpXchg: { 1411 AtomicOrdering Success = cast<AtomicCmpXchgInst>(I)->getSuccessOrdering(); 1412 AtomicOrdering Failure = cast<AtomicCmpXchgInst>(I)->getFailureOrdering(); 1413 // Only if both are relaxed, than it can be treated as relaxed. 1414 // Otherwise it is non-relaxed. 1415 if (Success != AtomicOrdering::Unordered && 1416 Success != AtomicOrdering::Monotonic) 1417 return true; 1418 if (Failure != AtomicOrdering::Unordered && 1419 Failure != AtomicOrdering::Monotonic) 1420 return true; 1421 return false; 1422 } 1423 default: 1424 llvm_unreachable( 1425 "New atomic operations need to be known in the attributor."); 1426 } 1427 1428 // Relaxed. 1429 if (Ordering == AtomicOrdering::Unordered || 1430 Ordering == AtomicOrdering::Monotonic) 1431 return false; 1432 return true; 1433 } 1434 1435 /// Checks if an intrinsic is nosync. Currently only checks mem* intrinsics. 1436 /// FIXME: We should ipmrove the handling of intrinsics. 1437 bool AANoSyncImpl::isNoSyncIntrinsic(Instruction *I) { 1438 if (auto *II = dyn_cast<IntrinsicInst>(I)) { 1439 switch (II->getIntrinsicID()) { 1440 /// Element wise atomic memory intrinsics are can only be unordered, 1441 /// therefore nosync. 1442 case Intrinsic::memset_element_unordered_atomic: 1443 case Intrinsic::memmove_element_unordered_atomic: 1444 case Intrinsic::memcpy_element_unordered_atomic: 1445 return true; 1446 case Intrinsic::memset: 1447 case Intrinsic::memmove: 1448 case Intrinsic::memcpy: 1449 if (!cast<MemIntrinsic>(II)->isVolatile()) 1450 return true; 1451 return false; 1452 default: 1453 return false; 1454 } 1455 } 1456 return false; 1457 } 1458 1459 bool AANoSyncImpl::isVolatile(Instruction *I) { 1460 assert(!ImmutableCallSite(I) && !isa<CallBase>(I) && 1461 "Calls should not be checked here"); 1462 1463 switch (I->getOpcode()) { 1464 case Instruction::AtomicRMW: 1465 return cast<AtomicRMWInst>(I)->isVolatile(); 1466 case Instruction::Store: 1467 return cast<StoreInst>(I)->isVolatile(); 1468 case Instruction::Load: 1469 return cast<LoadInst>(I)->isVolatile(); 1470 case Instruction::AtomicCmpXchg: 1471 return cast<AtomicCmpXchgInst>(I)->isVolatile(); 1472 default: 1473 return false; 1474 } 1475 } 1476 1477 ChangeStatus AANoSyncImpl::updateImpl(Attributor &A) { 1478 1479 auto CheckRWInstForNoSync = [&](Instruction &I) { 1480 /// We are looking for volatile instructions or Non-Relaxed atomics. 1481 /// FIXME: We should improve the handling of intrinsics. 1482 1483 if (isa<IntrinsicInst>(&I) && isNoSyncIntrinsic(&I)) 1484 return true; 1485 1486 if (ImmutableCallSite ICS = ImmutableCallSite(&I)) { 1487 if (ICS.hasFnAttr(Attribute::NoSync)) 1488 return true; 1489 1490 const auto &NoSyncAA = 1491 A.getAAFor<AANoSync>(*this, IRPosition::callsite_function(ICS)); 1492 if (NoSyncAA.isAssumedNoSync()) 1493 return true; 1494 return false; 1495 } 1496 1497 if (!isVolatile(&I) && !isNonRelaxedAtomic(&I)) 1498 return true; 1499 1500 return false; 1501 }; 1502 1503 auto CheckForNoSync = [&](Instruction &I) { 1504 // At this point we handled all read/write effects and they are all 1505 // nosync, so they can be skipped. 1506 if (I.mayReadOrWriteMemory()) 1507 return true; 1508 1509 // non-convergent and readnone imply nosync. 1510 return !ImmutableCallSite(&I).isConvergent(); 1511 }; 1512 1513 if (!A.checkForAllReadWriteInstructions(CheckRWInstForNoSync, *this) || 1514 !A.checkForAllCallLikeInstructions(CheckForNoSync, *this)) 1515 return indicatePessimisticFixpoint(); 1516 1517 return ChangeStatus::UNCHANGED; 1518 } 1519 1520 struct AANoSyncFunction final : public AANoSyncImpl { 1521 AANoSyncFunction(const IRPosition &IRP) : AANoSyncImpl(IRP) {} 1522 1523 /// See AbstractAttribute::trackStatistics() 1524 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nosync) } 1525 }; 1526 1527 /// NoSync attribute deduction for a call sites. 1528 struct AANoSyncCallSite final : AANoSyncImpl { 1529 AANoSyncCallSite(const IRPosition &IRP) : AANoSyncImpl(IRP) {} 1530 1531 /// See AbstractAttribute::initialize(...). 1532 void initialize(Attributor &A) override { 1533 AANoSyncImpl::initialize(A); 1534 Function *F = getAssociatedFunction(); 1535 if (!F) 1536 indicatePessimisticFixpoint(); 1537 } 1538 1539 /// See AbstractAttribute::updateImpl(...). 1540 ChangeStatus updateImpl(Attributor &A) override { 1541 // TODO: Once we have call site specific value information we can provide 1542 // call site specific liveness information and then it makes 1543 // sense to specialize attributes for call sites arguments instead of 1544 // redirecting requests to the callee argument. 1545 Function *F = getAssociatedFunction(); 1546 const IRPosition &FnPos = IRPosition::function(*F); 1547 auto &FnAA = A.getAAFor<AANoSync>(*this, FnPos); 1548 return clampStateAndIndicateChange( 1549 getState(), static_cast<const AANoSync::StateType &>(FnAA.getState())); 1550 } 1551 1552 /// See AbstractAttribute::trackStatistics() 1553 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nosync); } 1554 }; 1555 1556 /// ------------------------ No-Free Attributes ---------------------------- 1557 1558 struct AANoFreeImpl : public AANoFree { 1559 AANoFreeImpl(const IRPosition &IRP) : AANoFree(IRP) {} 1560 1561 /// See AbstractAttribute::updateImpl(...). 1562 ChangeStatus updateImpl(Attributor &A) override { 1563 auto CheckForNoFree = [&](Instruction &I) { 1564 ImmutableCallSite ICS(&I); 1565 if (ICS.hasFnAttr(Attribute::NoFree)) 1566 return true; 1567 1568 const auto &NoFreeAA = 1569 A.getAAFor<AANoFree>(*this, IRPosition::callsite_function(ICS)); 1570 return NoFreeAA.isAssumedNoFree(); 1571 }; 1572 1573 if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this)) 1574 return indicatePessimisticFixpoint(); 1575 return ChangeStatus::UNCHANGED; 1576 } 1577 1578 /// See AbstractAttribute::getAsStr(). 1579 const std::string getAsStr() const override { 1580 return getAssumed() ? "nofree" : "may-free"; 1581 } 1582 }; 1583 1584 struct AANoFreeFunction final : public AANoFreeImpl { 1585 AANoFreeFunction(const IRPosition &IRP) : AANoFreeImpl(IRP) {} 1586 1587 /// See AbstractAttribute::trackStatistics() 1588 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nofree) } 1589 }; 1590 1591 /// NoFree attribute deduction for a call sites. 1592 struct AANoFreeCallSite final : AANoFreeImpl { 1593 AANoFreeCallSite(const IRPosition &IRP) : AANoFreeImpl(IRP) {} 1594 1595 /// See AbstractAttribute::initialize(...). 1596 void initialize(Attributor &A) override { 1597 AANoFreeImpl::initialize(A); 1598 Function *F = getAssociatedFunction(); 1599 if (!F) 1600 indicatePessimisticFixpoint(); 1601 } 1602 1603 /// See AbstractAttribute::updateImpl(...). 1604 ChangeStatus updateImpl(Attributor &A) override { 1605 // TODO: Once we have call site specific value information we can provide 1606 // call site specific liveness information and then it makes 1607 // sense to specialize attributes for call sites arguments instead of 1608 // redirecting requests to the callee argument. 1609 Function *F = getAssociatedFunction(); 1610 const IRPosition &FnPos = IRPosition::function(*F); 1611 auto &FnAA = A.getAAFor<AANoFree>(*this, FnPos); 1612 return clampStateAndIndicateChange( 1613 getState(), static_cast<const AANoFree::StateType &>(FnAA.getState())); 1614 } 1615 1616 /// See AbstractAttribute::trackStatistics() 1617 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nofree); } 1618 }; 1619 1620 /// NoFree attribute for floating values. 1621 struct AANoFreeFloating : AANoFreeImpl { 1622 AANoFreeFloating(const IRPosition &IRP) : AANoFreeImpl(IRP) {} 1623 1624 /// See AbstractAttribute::trackStatistics() 1625 void trackStatistics() const override{STATS_DECLTRACK_FLOATING_ATTR(nofree)} 1626 1627 /// See Abstract Attribute::updateImpl(...). 1628 ChangeStatus updateImpl(Attributor &A) override { 1629 const IRPosition &IRP = getIRPosition(); 1630 1631 const auto &NoFreeAA = 1632 A.getAAFor<AANoFree>(*this, IRPosition::function_scope(IRP)); 1633 if (NoFreeAA.isAssumedNoFree()) 1634 return ChangeStatus::UNCHANGED; 1635 1636 Value &AssociatedValue = getIRPosition().getAssociatedValue(); 1637 auto Pred = [&](const Use &U, bool &Follow) -> bool { 1638 Instruction *UserI = cast<Instruction>(U.getUser()); 1639 if (auto *CB = dyn_cast<CallBase>(UserI)) { 1640 if (CB->isBundleOperand(&U)) 1641 return false; 1642 if (!CB->isArgOperand(&U)) 1643 return true; 1644 unsigned ArgNo = CB->getArgOperandNo(&U); 1645 1646 const auto &NoFreeArg = A.getAAFor<AANoFree>( 1647 *this, IRPosition::callsite_argument(*CB, ArgNo)); 1648 return NoFreeArg.isAssumedNoFree(); 1649 } 1650 1651 if (isa<GetElementPtrInst>(UserI) || isa<BitCastInst>(UserI) || 1652 isa<PHINode>(UserI) || isa<SelectInst>(UserI)) { 1653 Follow = true; 1654 return true; 1655 } 1656 1657 // Unknown user. 1658 return false; 1659 }; 1660 if (!A.checkForAllUses(Pred, *this, AssociatedValue)) 1661 return indicatePessimisticFixpoint(); 1662 1663 return ChangeStatus::UNCHANGED; 1664 } 1665 }; 1666 1667 /// NoFree attribute for a call site argument. 1668 struct AANoFreeArgument final : AANoFreeFloating { 1669 AANoFreeArgument(const IRPosition &IRP) : AANoFreeFloating(IRP) {} 1670 1671 /// See AbstractAttribute::trackStatistics() 1672 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nofree) } 1673 }; 1674 1675 /// NoFree attribute for call site arguments. 1676 struct AANoFreeCallSiteArgument final : AANoFreeFloating { 1677 AANoFreeCallSiteArgument(const IRPosition &IRP) : AANoFreeFloating(IRP) {} 1678 1679 /// See AbstractAttribute::updateImpl(...). 1680 ChangeStatus updateImpl(Attributor &A) override { 1681 // TODO: Once we have call site specific value information we can provide 1682 // call site specific liveness information and then it makes 1683 // sense to specialize attributes for call sites arguments instead of 1684 // redirecting requests to the callee argument. 1685 Argument *Arg = getAssociatedArgument(); 1686 if (!Arg) 1687 return indicatePessimisticFixpoint(); 1688 const IRPosition &ArgPos = IRPosition::argument(*Arg); 1689 auto &ArgAA = A.getAAFor<AANoFree>(*this, ArgPos); 1690 return clampStateAndIndicateChange( 1691 getState(), static_cast<const AANoFree::StateType &>(ArgAA.getState())); 1692 } 1693 1694 /// See AbstractAttribute::trackStatistics() 1695 void trackStatistics() const override{STATS_DECLTRACK_CSARG_ATTR(nofree)}; 1696 }; 1697 1698 /// NoFree attribute for function return value. 1699 struct AANoFreeReturned final : AANoFreeFloating { 1700 AANoFreeReturned(const IRPosition &IRP) : AANoFreeFloating(IRP) { 1701 llvm_unreachable("NoFree is not applicable to function returns!"); 1702 } 1703 1704 /// See AbstractAttribute::initialize(...). 1705 void initialize(Attributor &A) override { 1706 llvm_unreachable("NoFree is not applicable to function returns!"); 1707 } 1708 1709 /// See AbstractAttribute::updateImpl(...). 1710 ChangeStatus updateImpl(Attributor &A) override { 1711 llvm_unreachable("NoFree is not applicable to function returns!"); 1712 } 1713 1714 /// See AbstractAttribute::trackStatistics() 1715 void trackStatistics() const override {} 1716 }; 1717 1718 /// NoFree attribute deduction for a call site return value. 1719 struct AANoFreeCallSiteReturned final : AANoFreeFloating { 1720 AANoFreeCallSiteReturned(const IRPosition &IRP) : AANoFreeFloating(IRP) {} 1721 1722 ChangeStatus manifest(Attributor &A) override { 1723 return ChangeStatus::UNCHANGED; 1724 } 1725 /// See AbstractAttribute::trackStatistics() 1726 void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nofree) } 1727 }; 1728 1729 /// ------------------------ NonNull Argument Attribute ------------------------ 1730 static int64_t getKnownNonNullAndDerefBytesForUse( 1731 Attributor &A, AbstractAttribute &QueryingAA, Value &AssociatedValue, 1732 const Use *U, const Instruction *I, bool &IsNonNull, bool &TrackUse) { 1733 TrackUse = false; 1734 1735 const Value *UseV = U->get(); 1736 if (!UseV->getType()->isPointerTy()) 1737 return 0; 1738 1739 Type *PtrTy = UseV->getType(); 1740 const Function *F = I->getFunction(); 1741 bool NullPointerIsDefined = 1742 F ? llvm::NullPointerIsDefined(F, PtrTy->getPointerAddressSpace()) : true; 1743 const DataLayout &DL = A.getInfoCache().getDL(); 1744 if (ImmutableCallSite ICS = ImmutableCallSite(I)) { 1745 if (ICS.isBundleOperand(U)) 1746 return 0; 1747 1748 if (ICS.isCallee(U)) { 1749 IsNonNull |= !NullPointerIsDefined; 1750 return 0; 1751 } 1752 1753 unsigned ArgNo = ICS.getArgumentNo(U); 1754 IRPosition IRP = IRPosition::callsite_argument(ICS, ArgNo); 1755 // As long as we only use known information there is no need to track 1756 // dependences here. 1757 auto &DerefAA = A.getAAFor<AADereferenceable>(QueryingAA, IRP, 1758 /* TrackDependence */ false); 1759 IsNonNull |= DerefAA.isKnownNonNull(); 1760 return DerefAA.getKnownDereferenceableBytes(); 1761 } 1762 1763 // We need to follow common pointer manipulation uses to the accesses they 1764 // feed into. We can try to be smart to avoid looking through things we do not 1765 // like for now, e.g., non-inbounds GEPs. 1766 if (isa<CastInst>(I)) { 1767 TrackUse = true; 1768 return 0; 1769 } 1770 if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) 1771 if (GEP->hasAllConstantIndices()) { 1772 TrackUse = true; 1773 return 0; 1774 } 1775 1776 int64_t Offset; 1777 if (const Value *Base = getBasePointerOfAccessPointerOperand(I, Offset, DL)) { 1778 if (Base == &AssociatedValue && 1779 Attributor::getPointerOperand(I, /* AllowVolatile */ false) == UseV) { 1780 int64_t DerefBytes = 1781 (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType()) + Offset; 1782 1783 IsNonNull |= !NullPointerIsDefined; 1784 return std::max(int64_t(0), DerefBytes); 1785 } 1786 } 1787 1788 /// Corner case when an offset is 0. 1789 if (const Value *Base = getBasePointerOfAccessPointerOperand( 1790 I, Offset, DL, /*AllowNonInbounds*/ true)) { 1791 if (Offset == 0 && Base == &AssociatedValue && 1792 Attributor::getPointerOperand(I, /* AllowVolatile */ false) == UseV) { 1793 int64_t DerefBytes = 1794 (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType()); 1795 IsNonNull |= !NullPointerIsDefined; 1796 return std::max(int64_t(0), DerefBytes); 1797 } 1798 } 1799 1800 return 0; 1801 } 1802 1803 struct AANonNullImpl : AANonNull { 1804 AANonNullImpl(const IRPosition &IRP) 1805 : AANonNull(IRP), 1806 NullIsDefined(NullPointerIsDefined( 1807 getAnchorScope(), 1808 getAssociatedValue().getType()->getPointerAddressSpace())) {} 1809 1810 /// See AbstractAttribute::initialize(...). 1811 void initialize(Attributor &A) override { 1812 if (!NullIsDefined && 1813 hasAttr({Attribute::NonNull, Attribute::Dereferenceable})) 1814 indicateOptimisticFixpoint(); 1815 else if (isa<ConstantPointerNull>(getAssociatedValue())) 1816 indicatePessimisticFixpoint(); 1817 else 1818 AANonNull::initialize(A); 1819 } 1820 1821 /// See AAFromMustBeExecutedContext 1822 bool followUse(Attributor &A, const Use *U, const Instruction *I) { 1823 bool IsNonNull = false; 1824 bool TrackUse = false; 1825 getKnownNonNullAndDerefBytesForUse(A, *this, getAssociatedValue(), U, I, 1826 IsNonNull, TrackUse); 1827 setKnown(IsNonNull); 1828 return TrackUse; 1829 } 1830 1831 /// See AbstractAttribute::getAsStr(). 1832 const std::string getAsStr() const override { 1833 return getAssumed() ? "nonnull" : "may-null"; 1834 } 1835 1836 /// Flag to determine if the underlying value can be null and still allow 1837 /// valid accesses. 1838 const bool NullIsDefined; 1839 }; 1840 1841 /// NonNull attribute for a floating value. 1842 struct AANonNullFloating 1843 : AAFromMustBeExecutedContext<AANonNull, AANonNullImpl> { 1844 using Base = AAFromMustBeExecutedContext<AANonNull, AANonNullImpl>; 1845 AANonNullFloating(const IRPosition &IRP) : Base(IRP) {} 1846 1847 /// See AbstractAttribute::updateImpl(...). 1848 ChangeStatus updateImpl(Attributor &A) override { 1849 ChangeStatus Change = Base::updateImpl(A); 1850 if (isKnownNonNull()) 1851 return Change; 1852 1853 if (!NullIsDefined) { 1854 const auto &DerefAA = 1855 A.getAAFor<AADereferenceable>(*this, getIRPosition()); 1856 if (DerefAA.getAssumedDereferenceableBytes()) 1857 return Change; 1858 } 1859 1860 const DataLayout &DL = A.getDataLayout(); 1861 1862 DominatorTree *DT = nullptr; 1863 InformationCache &InfoCache = A.getInfoCache(); 1864 if (const Function *Fn = getAnchorScope()) 1865 DT = InfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(*Fn); 1866 1867 auto VisitValueCB = [&](Value &V, AANonNull::StateType &T, 1868 bool Stripped) -> bool { 1869 const auto &AA = A.getAAFor<AANonNull>(*this, IRPosition::value(V)); 1870 if (!Stripped && this == &AA) { 1871 if (!isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr, getCtxI(), DT)) 1872 T.indicatePessimisticFixpoint(); 1873 } else { 1874 // Use abstract attribute information. 1875 const AANonNull::StateType &NS = 1876 static_cast<const AANonNull::StateType &>(AA.getState()); 1877 T ^= NS; 1878 } 1879 return T.isValidState(); 1880 }; 1881 1882 StateType T; 1883 if (!genericValueTraversal<AANonNull, StateType>(A, getIRPosition(), *this, 1884 T, VisitValueCB)) 1885 return indicatePessimisticFixpoint(); 1886 1887 return clampStateAndIndicateChange(getState(), T); 1888 } 1889 1890 /// See AbstractAttribute::trackStatistics() 1891 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) } 1892 }; 1893 1894 /// NonNull attribute for function return value. 1895 struct AANonNullReturned final 1896 : AAReturnedFromReturnedValues<AANonNull, AANonNullImpl> { 1897 AANonNullReturned(const IRPosition &IRP) 1898 : AAReturnedFromReturnedValues<AANonNull, AANonNullImpl>(IRP) {} 1899 1900 /// See AbstractAttribute::trackStatistics() 1901 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) } 1902 }; 1903 1904 /// NonNull attribute for function argument. 1905 struct AANonNullArgument final 1906 : AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext<AANonNull, 1907 AANonNullImpl> { 1908 AANonNullArgument(const IRPosition &IRP) 1909 : AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext<AANonNull, 1910 AANonNullImpl>( 1911 IRP) {} 1912 1913 /// See AbstractAttribute::trackStatistics() 1914 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nonnull) } 1915 }; 1916 1917 struct AANonNullCallSiteArgument final : AANonNullFloating { 1918 AANonNullCallSiteArgument(const IRPosition &IRP) : AANonNullFloating(IRP) {} 1919 1920 /// See AbstractAttribute::trackStatistics() 1921 void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(nonnull) } 1922 }; 1923 1924 /// NonNull attribute for a call site return position. 1925 struct AANonNullCallSiteReturned final 1926 : AACallSiteReturnedFromReturnedAndMustBeExecutedContext<AANonNull, 1927 AANonNullImpl> { 1928 AANonNullCallSiteReturned(const IRPosition &IRP) 1929 : AACallSiteReturnedFromReturnedAndMustBeExecutedContext<AANonNull, 1930 AANonNullImpl>( 1931 IRP) {} 1932 1933 /// See AbstractAttribute::trackStatistics() 1934 void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nonnull) } 1935 }; 1936 1937 /// ------------------------ No-Recurse Attributes ---------------------------- 1938 1939 struct AANoRecurseImpl : public AANoRecurse { 1940 AANoRecurseImpl(const IRPosition &IRP) : AANoRecurse(IRP) {} 1941 1942 /// See AbstractAttribute::getAsStr() 1943 const std::string getAsStr() const override { 1944 return getAssumed() ? "norecurse" : "may-recurse"; 1945 } 1946 }; 1947 1948 struct AANoRecurseFunction final : AANoRecurseImpl { 1949 AANoRecurseFunction(const IRPosition &IRP) : AANoRecurseImpl(IRP) {} 1950 1951 /// See AbstractAttribute::initialize(...). 1952 void initialize(Attributor &A) override { 1953 AANoRecurseImpl::initialize(A); 1954 if (const Function *F = getAnchorScope()) 1955 if (A.getInfoCache().getSccSize(*F) == 1) 1956 return; 1957 indicatePessimisticFixpoint(); 1958 } 1959 1960 /// See AbstractAttribute::updateImpl(...). 1961 ChangeStatus updateImpl(Attributor &A) override { 1962 1963 auto CheckForNoRecurse = [&](Instruction &I) { 1964 ImmutableCallSite ICS(&I); 1965 if (ICS.hasFnAttr(Attribute::NoRecurse)) 1966 return true; 1967 1968 const auto &NoRecurseAA = 1969 A.getAAFor<AANoRecurse>(*this, IRPosition::callsite_function(ICS)); 1970 if (!NoRecurseAA.isAssumedNoRecurse()) 1971 return false; 1972 1973 // Recursion to the same function 1974 if (ICS.getCalledFunction() == getAnchorScope()) 1975 return false; 1976 1977 return true; 1978 }; 1979 1980 if (!A.checkForAllCallLikeInstructions(CheckForNoRecurse, *this)) 1981 return indicatePessimisticFixpoint(); 1982 return ChangeStatus::UNCHANGED; 1983 } 1984 1985 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(norecurse) } 1986 }; 1987 1988 /// NoRecurse attribute deduction for a call sites. 1989 struct AANoRecurseCallSite final : AANoRecurseImpl { 1990 AANoRecurseCallSite(const IRPosition &IRP) : AANoRecurseImpl(IRP) {} 1991 1992 /// See AbstractAttribute::initialize(...). 1993 void initialize(Attributor &A) override { 1994 AANoRecurseImpl::initialize(A); 1995 Function *F = getAssociatedFunction(); 1996 if (!F) 1997 indicatePessimisticFixpoint(); 1998 } 1999 2000 /// See AbstractAttribute::updateImpl(...). 2001 ChangeStatus updateImpl(Attributor &A) override { 2002 // TODO: Once we have call site specific value information we can provide 2003 // call site specific liveness information and then it makes 2004 // sense to specialize attributes for call sites arguments instead of 2005 // redirecting requests to the callee argument. 2006 Function *F = getAssociatedFunction(); 2007 const IRPosition &FnPos = IRPosition::function(*F); 2008 auto &FnAA = A.getAAFor<AANoRecurse>(*this, FnPos); 2009 return clampStateAndIndicateChange( 2010 getState(), 2011 static_cast<const AANoRecurse::StateType &>(FnAA.getState())); 2012 } 2013 2014 /// See AbstractAttribute::trackStatistics() 2015 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(norecurse); } 2016 }; 2017 2018 /// -------------------- Undefined-Behavior Attributes ------------------------ 2019 2020 struct AAUndefinedBehaviorImpl : public AAUndefinedBehavior { 2021 AAUndefinedBehaviorImpl(const IRPosition &IRP) : AAUndefinedBehavior(IRP) {} 2022 2023 /// See AbstractAttribute::updateImpl(...). 2024 // through a pointer (i.e. also branches etc.) 2025 ChangeStatus updateImpl(Attributor &A) override { 2026 const size_t UBPrevSize = KnownUBInsts.size(); 2027 const size_t NoUBPrevSize = AssumedNoUBInsts.size(); 2028 2029 auto InspectMemAccessInstForUB = [&](Instruction &I) { 2030 // Skip instructions that are already saved. 2031 if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I)) 2032 return true; 2033 2034 // If we reach here, we know we have an instruction 2035 // that accesses memory through a pointer operand, 2036 // for which getPointerOperand() should give it to us. 2037 const Value *PtrOp = 2038 Attributor::getPointerOperand(&I, /* AllowVolatile */ true); 2039 assert(PtrOp && 2040 "Expected pointer operand of memory accessing instruction"); 2041 2042 // A memory access through a pointer is considered UB 2043 // only if the pointer has constant null value. 2044 // TODO: Expand it to not only check constant values. 2045 if (!isa<ConstantPointerNull>(PtrOp)) { 2046 AssumedNoUBInsts.insert(&I); 2047 return true; 2048 } 2049 const Type *PtrTy = PtrOp->getType(); 2050 2051 // Because we only consider instructions inside functions, 2052 // assume that a parent function exists. 2053 const Function *F = I.getFunction(); 2054 2055 // A memory access using constant null pointer is only considered UB 2056 // if null pointer is _not_ defined for the target platform. 2057 if (llvm::NullPointerIsDefined(F, PtrTy->getPointerAddressSpace())) 2058 AssumedNoUBInsts.insert(&I); 2059 else 2060 KnownUBInsts.insert(&I); 2061 return true; 2062 }; 2063 2064 auto InspectBrInstForUB = [&](Instruction &I) { 2065 // A conditional branch instruction is considered UB if it has `undef` 2066 // condition. 2067 2068 // Skip instructions that are already saved. 2069 if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I)) 2070 return true; 2071 2072 // We know we have a branch instruction. 2073 auto BrInst = cast<BranchInst>(&I); 2074 2075 // Unconditional branches are never considered UB. 2076 if (BrInst->isUnconditional()) 2077 return true; 2078 2079 // Either we stopped and the appropriate action was taken, 2080 // or we got back a simplified value to continue. 2081 Optional<Value *> SimplifiedCond = 2082 stopOnUndefOrAssumed(A, BrInst->getCondition(), BrInst); 2083 if (!SimplifiedCond.hasValue()) 2084 return true; 2085 AssumedNoUBInsts.insert(&I); 2086 return true; 2087 }; 2088 2089 A.checkForAllInstructions(InspectMemAccessInstForUB, *this, 2090 {Instruction::Load, Instruction::Store, 2091 Instruction::AtomicCmpXchg, 2092 Instruction::AtomicRMW}); 2093 A.checkForAllInstructions(InspectBrInstForUB, *this, {Instruction::Br}); 2094 if (NoUBPrevSize != AssumedNoUBInsts.size() || 2095 UBPrevSize != KnownUBInsts.size()) 2096 return ChangeStatus::CHANGED; 2097 return ChangeStatus::UNCHANGED; 2098 } 2099 2100 bool isKnownToCauseUB(Instruction *I) const override { 2101 return KnownUBInsts.count(I); 2102 } 2103 2104 bool isAssumedToCauseUB(Instruction *I) const override { 2105 // In simple words, if an instruction is not in the assumed to _not_ 2106 // cause UB, then it is assumed UB (that includes those 2107 // in the KnownUBInsts set). The rest is boilerplate 2108 // is to ensure that it is one of the instructions we test 2109 // for UB. 2110 2111 switch (I->getOpcode()) { 2112 case Instruction::Load: 2113 case Instruction::Store: 2114 case Instruction::AtomicCmpXchg: 2115 case Instruction::AtomicRMW: 2116 return !AssumedNoUBInsts.count(I); 2117 case Instruction::Br: { 2118 auto BrInst = cast<BranchInst>(I); 2119 if (BrInst->isUnconditional()) 2120 return false; 2121 return !AssumedNoUBInsts.count(I); 2122 } break; 2123 default: 2124 return false; 2125 } 2126 return false; 2127 } 2128 2129 ChangeStatus manifest(Attributor &A) override { 2130 if (KnownUBInsts.empty()) 2131 return ChangeStatus::UNCHANGED; 2132 for (Instruction *I : KnownUBInsts) 2133 A.changeToUnreachableAfterManifest(I); 2134 return ChangeStatus::CHANGED; 2135 } 2136 2137 /// See AbstractAttribute::getAsStr() 2138 const std::string getAsStr() const override { 2139 return getAssumed() ? "undefined-behavior" : "no-ub"; 2140 } 2141 2142 /// Note: The correctness of this analysis depends on the fact that the 2143 /// following 2 sets will stop changing after some point. 2144 /// "Change" here means that their size changes. 2145 /// The size of each set is monotonically increasing 2146 /// (we only add items to them) and it is upper bounded by the number of 2147 /// instructions in the processed function (we can never save more 2148 /// elements in either set than this number). Hence, at some point, 2149 /// they will stop increasing. 2150 /// Consequently, at some point, both sets will have stopped 2151 /// changing, effectively making the analysis reach a fixpoint. 2152 2153 /// Note: These 2 sets are disjoint and an instruction can be considered 2154 /// one of 3 things: 2155 /// 1) Known to cause UB (AAUndefinedBehavior could prove it) and put it in 2156 /// the KnownUBInsts set. 2157 /// 2) Assumed to cause UB (in every updateImpl, AAUndefinedBehavior 2158 /// has a reason to assume it). 2159 /// 3) Assumed to not cause UB. very other instruction - AAUndefinedBehavior 2160 /// could not find a reason to assume or prove that it can cause UB, 2161 /// hence it assumes it doesn't. We have a set for these instructions 2162 /// so that we don't reprocess them in every update. 2163 /// Note however that instructions in this set may cause UB. 2164 2165 protected: 2166 /// A set of all live instructions _known_ to cause UB. 2167 SmallPtrSet<Instruction *, 8> KnownUBInsts; 2168 2169 private: 2170 /// A set of all the (live) instructions that are assumed to _not_ cause UB. 2171 SmallPtrSet<Instruction *, 8> AssumedNoUBInsts; 2172 2173 // Should be called on updates in which if we're processing an instruction 2174 // \p I that depends on a value \p V, one of the following has to happen: 2175 // - If the value is assumed, then stop. 2176 // - If the value is known but undef, then consider it UB. 2177 // - Otherwise, do specific processing with the simplified value. 2178 // We return None in the first 2 cases to signify that an appropriate 2179 // action was taken and the caller should stop. 2180 // Otherwise, we return the simplified value that the caller should 2181 // use for specific processing. 2182 Optional<Value *> stopOnUndefOrAssumed(Attributor &A, const Value *V, 2183 Instruction *I) { 2184 const auto &ValueSimplifyAA = 2185 A.getAAFor<AAValueSimplify>(*this, IRPosition::value(*V)); 2186 Optional<Value *> SimplifiedV = 2187 ValueSimplifyAA.getAssumedSimplifiedValue(A); 2188 if (!ValueSimplifyAA.isKnown()) { 2189 // Don't depend on assumed values. 2190 return llvm::None; 2191 } 2192 if (!SimplifiedV.hasValue()) { 2193 // If it is known (which we tested above) but it doesn't have a value, 2194 // then we can assume `undef` and hence the instruction is UB. 2195 KnownUBInsts.insert(I); 2196 return llvm::None; 2197 } 2198 Value *Val = SimplifiedV.getValue(); 2199 if (isa<UndefValue>(Val)) { 2200 KnownUBInsts.insert(I); 2201 return llvm::None; 2202 } 2203 return Val; 2204 } 2205 }; 2206 2207 struct AAUndefinedBehaviorFunction final : AAUndefinedBehaviorImpl { 2208 AAUndefinedBehaviorFunction(const IRPosition &IRP) 2209 : AAUndefinedBehaviorImpl(IRP) {} 2210 2211 /// See AbstractAttribute::trackStatistics() 2212 void trackStatistics() const override { 2213 STATS_DECL(UndefinedBehaviorInstruction, Instruction, 2214 "Number of instructions known to have UB"); 2215 BUILD_STAT_NAME(UndefinedBehaviorInstruction, Instruction) += 2216 KnownUBInsts.size(); 2217 } 2218 }; 2219 2220 /// ------------------------ Will-Return Attributes ---------------------------- 2221 2222 // Helper function that checks whether a function has any cycle. 2223 // TODO: Replace with more efficent code 2224 static bool containsCycle(Function &F) { 2225 SmallPtrSet<BasicBlock *, 32> Visited; 2226 2227 // Traverse BB by dfs and check whether successor is already visited. 2228 for (BasicBlock *BB : depth_first(&F)) { 2229 Visited.insert(BB); 2230 for (auto *SuccBB : successors(BB)) { 2231 if (Visited.count(SuccBB)) 2232 return true; 2233 } 2234 } 2235 return false; 2236 } 2237 2238 // Helper function that checks the function have a loop which might become an 2239 // endless loop 2240 // FIXME: Any cycle is regarded as endless loop for now. 2241 // We have to allow some patterns. 2242 static bool containsPossiblyEndlessLoop(Function *F) { 2243 return !F || !F->hasExactDefinition() || containsCycle(*F); 2244 } 2245 2246 struct AAWillReturnImpl : public AAWillReturn { 2247 AAWillReturnImpl(const IRPosition &IRP) : AAWillReturn(IRP) {} 2248 2249 /// See AbstractAttribute::initialize(...). 2250 void initialize(Attributor &A) override { 2251 AAWillReturn::initialize(A); 2252 2253 Function *F = getAssociatedFunction(); 2254 if (containsPossiblyEndlessLoop(F)) 2255 indicatePessimisticFixpoint(); 2256 } 2257 2258 /// See AbstractAttribute::updateImpl(...). 2259 ChangeStatus updateImpl(Attributor &A) override { 2260 auto CheckForWillReturn = [&](Instruction &I) { 2261 IRPosition IPos = IRPosition::callsite_function(ImmutableCallSite(&I)); 2262 const auto &WillReturnAA = A.getAAFor<AAWillReturn>(*this, IPos); 2263 if (WillReturnAA.isKnownWillReturn()) 2264 return true; 2265 if (!WillReturnAA.isAssumedWillReturn()) 2266 return false; 2267 const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(*this, IPos); 2268 return NoRecurseAA.isAssumedNoRecurse(); 2269 }; 2270 2271 if (!A.checkForAllCallLikeInstructions(CheckForWillReturn, *this)) 2272 return indicatePessimisticFixpoint(); 2273 2274 return ChangeStatus::UNCHANGED; 2275 } 2276 2277 /// See AbstractAttribute::getAsStr() 2278 const std::string getAsStr() const override { 2279 return getAssumed() ? "willreturn" : "may-noreturn"; 2280 } 2281 }; 2282 2283 struct AAWillReturnFunction final : AAWillReturnImpl { 2284 AAWillReturnFunction(const IRPosition &IRP) : AAWillReturnImpl(IRP) {} 2285 2286 /// See AbstractAttribute::trackStatistics() 2287 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(willreturn) } 2288 }; 2289 2290 /// WillReturn attribute deduction for a call sites. 2291 struct AAWillReturnCallSite final : AAWillReturnImpl { 2292 AAWillReturnCallSite(const IRPosition &IRP) : AAWillReturnImpl(IRP) {} 2293 2294 /// See AbstractAttribute::initialize(...). 2295 void initialize(Attributor &A) override { 2296 AAWillReturnImpl::initialize(A); 2297 Function *F = getAssociatedFunction(); 2298 if (!F) 2299 indicatePessimisticFixpoint(); 2300 } 2301 2302 /// See AbstractAttribute::updateImpl(...). 2303 ChangeStatus updateImpl(Attributor &A) override { 2304 // TODO: Once we have call site specific value information we can provide 2305 // call site specific liveness information and then it makes 2306 // sense to specialize attributes for call sites arguments instead of 2307 // redirecting requests to the callee argument. 2308 Function *F = getAssociatedFunction(); 2309 const IRPosition &FnPos = IRPosition::function(*F); 2310 auto &FnAA = A.getAAFor<AAWillReturn>(*this, FnPos); 2311 return clampStateAndIndicateChange( 2312 getState(), 2313 static_cast<const AAWillReturn::StateType &>(FnAA.getState())); 2314 } 2315 2316 /// See AbstractAttribute::trackStatistics() 2317 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(willreturn); } 2318 }; 2319 2320 /// -------------------AAReachability Attribute-------------------------- 2321 2322 struct AAReachabilityImpl : AAReachability { 2323 AAReachabilityImpl(const IRPosition &IRP) : AAReachability(IRP) {} 2324 2325 const std::string getAsStr() const override { 2326 // TODO: Return the number of reachable queries. 2327 return "reachable"; 2328 } 2329 2330 /// See AbstractAttribute::initialize(...). 2331 void initialize(Attributor &A) override { indicatePessimisticFixpoint(); } 2332 2333 /// See AbstractAttribute::updateImpl(...). 2334 ChangeStatus updateImpl(Attributor &A) override { 2335 return indicatePessimisticFixpoint(); 2336 } 2337 }; 2338 2339 struct AAReachabilityFunction final : public AAReachabilityImpl { 2340 AAReachabilityFunction(const IRPosition &IRP) : AAReachabilityImpl(IRP) {} 2341 2342 /// See AbstractAttribute::trackStatistics() 2343 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(reachable); } 2344 }; 2345 2346 /// ------------------------ NoAlias Argument Attribute ------------------------ 2347 2348 struct AANoAliasImpl : AANoAlias { 2349 AANoAliasImpl(const IRPosition &IRP) : AANoAlias(IRP) {} 2350 2351 const std::string getAsStr() const override { 2352 return getAssumed() ? "noalias" : "may-alias"; 2353 } 2354 }; 2355 2356 /// NoAlias attribute for a floating value. 2357 struct AANoAliasFloating final : AANoAliasImpl { 2358 AANoAliasFloating(const IRPosition &IRP) : AANoAliasImpl(IRP) {} 2359 2360 /// See AbstractAttribute::initialize(...). 2361 void initialize(Attributor &A) override { 2362 AANoAliasImpl::initialize(A); 2363 Value &Val = getAssociatedValue(); 2364 if (isa<AllocaInst>(Val)) 2365 indicateOptimisticFixpoint(); 2366 if (isa<ConstantPointerNull>(Val) && 2367 Val.getType()->getPointerAddressSpace() == 0) 2368 indicateOptimisticFixpoint(); 2369 } 2370 2371 /// See AbstractAttribute::updateImpl(...). 2372 ChangeStatus updateImpl(Attributor &A) override { 2373 // TODO: Implement this. 2374 return indicatePessimisticFixpoint(); 2375 } 2376 2377 /// See AbstractAttribute::trackStatistics() 2378 void trackStatistics() const override { 2379 STATS_DECLTRACK_FLOATING_ATTR(noalias) 2380 } 2381 }; 2382 2383 /// NoAlias attribute for an argument. 2384 struct AANoAliasArgument final 2385 : AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl> { 2386 using Base = AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl>; 2387 AANoAliasArgument(const IRPosition &IRP) : Base(IRP) {} 2388 2389 /// See AbstractAttribute::update(...). 2390 ChangeStatus updateImpl(Attributor &A) override { 2391 // We have to make sure no-alias on the argument does not break 2392 // synchronization when this is a callback argument, see also [1] below. 2393 // If synchronization cannot be affected, we delegate to the base updateImpl 2394 // function, otherwise we give up for now. 2395 2396 // If the function is no-sync, no-alias cannot break synchronization. 2397 const auto &NoSyncAA = A.getAAFor<AANoSync>( 2398 *this, IRPosition::function_scope(getIRPosition())); 2399 if (NoSyncAA.isAssumedNoSync()) 2400 return Base::updateImpl(A); 2401 2402 // If the argument is read-only, no-alias cannot break synchronization. 2403 const auto &MemBehaviorAA = 2404 A.getAAFor<AAMemoryBehavior>(*this, getIRPosition()); 2405 if (MemBehaviorAA.isAssumedReadOnly()) 2406 return Base::updateImpl(A); 2407 2408 // If the argument is never passed through callbacks, no-alias cannot break 2409 // synchronization. 2410 if (A.checkForAllCallSites( 2411 [](AbstractCallSite ACS) { return !ACS.isCallbackCall(); }, *this, 2412 true)) 2413 return Base::updateImpl(A); 2414 2415 // TODO: add no-alias but make sure it doesn't break synchronization by 2416 // introducing fake uses. See: 2417 // [1] Compiler Optimizations for OpenMP, J. Doerfert and H. Finkel, 2418 // International Workshop on OpenMP 2018, 2419 // http://compilers.cs.uni-saarland.de/people/doerfert/par_opt18.pdf 2420 2421 return indicatePessimisticFixpoint(); 2422 } 2423 2424 /// See AbstractAttribute::trackStatistics() 2425 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(noalias) } 2426 }; 2427 2428 struct AANoAliasCallSiteArgument final : AANoAliasImpl { 2429 AANoAliasCallSiteArgument(const IRPosition &IRP) : AANoAliasImpl(IRP) {} 2430 2431 /// See AbstractAttribute::initialize(...). 2432 void initialize(Attributor &A) override { 2433 // See callsite argument attribute and callee argument attribute. 2434 ImmutableCallSite ICS(&getAnchorValue()); 2435 if (ICS.paramHasAttr(getArgNo(), Attribute::NoAlias)) 2436 indicateOptimisticFixpoint(); 2437 } 2438 2439 /// See AbstractAttribute::updateImpl(...). 2440 ChangeStatus updateImpl(Attributor &A) override { 2441 // We can deduce "noalias" if the following conditions hold. 2442 // (i) Associated value is assumed to be noalias in the definition. 2443 // (ii) Associated value is assumed to be no-capture in all the uses 2444 // possibly executed before this callsite. 2445 // (iii) There is no other pointer argument which could alias with the 2446 // value. 2447 2448 const Value &V = getAssociatedValue(); 2449 const IRPosition IRP = IRPosition::value(V); 2450 2451 // (i) Check whether noalias holds in the definition. 2452 2453 auto &NoAliasAA = A.getAAFor<AANoAlias>(*this, IRP); 2454 LLVM_DEBUG(dbgs() << "[Attributor][AANoAliasCSArg] check definition: " << V 2455 << " :: " << NoAliasAA << "\n"); 2456 2457 if (!NoAliasAA.isAssumedNoAlias()) 2458 return indicatePessimisticFixpoint(); 2459 2460 LLVM_DEBUG(dbgs() << "[Attributor][AANoAliasCSArg] " << V 2461 << " is assumed NoAlias in the definition\n"); 2462 2463 // (ii) Check whether the value is captured in the scope using AANoCapture. 2464 // FIXME: This is conservative though, it is better to look at CFG and 2465 // check only uses possibly executed before this callsite. 2466 2467 auto &NoCaptureAA = A.getAAFor<AANoCapture>(*this, IRP); 2468 if (!NoCaptureAA.isAssumedNoCaptureMaybeReturned()) { 2469 LLVM_DEBUG( 2470 dbgs() << "[Attributor][AANoAliasCSArg] " << V 2471 << " cannot be noalias as it is potentially captured\n"); 2472 return indicatePessimisticFixpoint(); 2473 } 2474 2475 // (iii) Check there is no other pointer argument which could alias with the 2476 // value. 2477 // TODO: AbstractCallSite 2478 ImmutableCallSite ICS(&getAnchorValue()); 2479 for (unsigned i = 0; i < ICS.getNumArgOperands(); i++) { 2480 if (getArgNo() == (int)i) 2481 continue; 2482 const Value *ArgOp = ICS.getArgOperand(i); 2483 if (!ArgOp->getType()->isPointerTy()) 2484 continue; 2485 2486 if (const Function *F = getAnchorScope()) { 2487 if (AAResults *AAR = A.getInfoCache().getAAResultsForFunction(*F)) { 2488 bool IsAliasing = !AAR->isNoAlias(&getAssociatedValue(), ArgOp); 2489 LLVM_DEBUG(dbgs() 2490 << "[Attributor][NoAliasCSArg] Check alias between " 2491 "callsite arguments " 2492 << AAR->isNoAlias(&getAssociatedValue(), ArgOp) << " " 2493 << getAssociatedValue() << " " << *ArgOp << " => " 2494 << (IsAliasing ? "" : "no-") << "alias \n"); 2495 2496 if (!IsAliasing) 2497 continue; 2498 } 2499 } 2500 return indicatePessimisticFixpoint(); 2501 } 2502 2503 return ChangeStatus::UNCHANGED; 2504 } 2505 2506 /// See AbstractAttribute::trackStatistics() 2507 void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(noalias) } 2508 }; 2509 2510 /// NoAlias attribute for function return value. 2511 struct AANoAliasReturned final : AANoAliasImpl { 2512 AANoAliasReturned(const IRPosition &IRP) : AANoAliasImpl(IRP) {} 2513 2514 /// See AbstractAttribute::updateImpl(...). 2515 virtual ChangeStatus updateImpl(Attributor &A) override { 2516 2517 auto CheckReturnValue = [&](Value &RV) -> bool { 2518 if (Constant *C = dyn_cast<Constant>(&RV)) 2519 if (C->isNullValue() || isa<UndefValue>(C)) 2520 return true; 2521 2522 /// For now, we can only deduce noalias if we have call sites. 2523 /// FIXME: add more support. 2524 ImmutableCallSite ICS(&RV); 2525 if (!ICS) 2526 return false; 2527 2528 const IRPosition &RVPos = IRPosition::value(RV); 2529 const auto &NoAliasAA = A.getAAFor<AANoAlias>(*this, RVPos); 2530 if (!NoAliasAA.isAssumedNoAlias()) 2531 return false; 2532 2533 const auto &NoCaptureAA = A.getAAFor<AANoCapture>(*this, RVPos); 2534 return NoCaptureAA.isAssumedNoCaptureMaybeReturned(); 2535 }; 2536 2537 if (!A.checkForAllReturnedValues(CheckReturnValue, *this)) 2538 return indicatePessimisticFixpoint(); 2539 2540 return ChangeStatus::UNCHANGED; 2541 } 2542 2543 /// See AbstractAttribute::trackStatistics() 2544 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(noalias) } 2545 }; 2546 2547 /// NoAlias attribute deduction for a call site return value. 2548 struct AANoAliasCallSiteReturned final : AANoAliasImpl { 2549 AANoAliasCallSiteReturned(const IRPosition &IRP) : AANoAliasImpl(IRP) {} 2550 2551 /// See AbstractAttribute::initialize(...). 2552 void initialize(Attributor &A) override { 2553 AANoAliasImpl::initialize(A); 2554 Function *F = getAssociatedFunction(); 2555 if (!F) 2556 indicatePessimisticFixpoint(); 2557 } 2558 2559 /// See AbstractAttribute::updateImpl(...). 2560 ChangeStatus updateImpl(Attributor &A) override { 2561 // TODO: Once we have call site specific value information we can provide 2562 // call site specific liveness information and then it makes 2563 // sense to specialize attributes for call sites arguments instead of 2564 // redirecting requests to the callee argument. 2565 Function *F = getAssociatedFunction(); 2566 const IRPosition &FnPos = IRPosition::returned(*F); 2567 auto &FnAA = A.getAAFor<AANoAlias>(*this, FnPos); 2568 return clampStateAndIndicateChange( 2569 getState(), static_cast<const AANoAlias::StateType &>(FnAA.getState())); 2570 } 2571 2572 /// See AbstractAttribute::trackStatistics() 2573 void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noalias); } 2574 }; 2575 2576 /// -------------------AAIsDead Function Attribute----------------------- 2577 2578 struct AAIsDeadValueImpl : public AAIsDead { 2579 AAIsDeadValueImpl(const IRPosition &IRP) : AAIsDead(IRP) {} 2580 2581 /// See AAIsDead::isAssumedDead(). 2582 bool isAssumedDead() const override { return getAssumed(); } 2583 2584 /// See AAIsDead::isAssumedDead(BasicBlock *). 2585 bool isAssumedDead(const BasicBlock *BB) const override { return false; } 2586 2587 /// See AAIsDead::isKnownDead(BasicBlock *). 2588 bool isKnownDead(const BasicBlock *BB) const override { return false; } 2589 2590 /// See AAIsDead::isAssumedDead(Instruction *I). 2591 bool isAssumedDead(const Instruction *I) const override { 2592 return I == getCtxI() && isAssumedDead(); 2593 } 2594 2595 /// See AAIsDead::isKnownDead(Instruction *I). 2596 bool isKnownDead(const Instruction *I) const override { 2597 return I == getCtxI() && getKnown(); 2598 } 2599 2600 /// See AbstractAttribute::getAsStr(). 2601 const std::string getAsStr() const override { 2602 return isAssumedDead() ? "assumed-dead" : "assumed-live"; 2603 } 2604 }; 2605 2606 struct AAIsDeadFloating : public AAIsDeadValueImpl { 2607 AAIsDeadFloating(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {} 2608 2609 /// See AbstractAttribute::initialize(...). 2610 void initialize(Attributor &A) override { 2611 if (Instruction *I = dyn_cast<Instruction>(&getAssociatedValue())) 2612 if (!wouldInstructionBeTriviallyDead(I)) 2613 indicatePessimisticFixpoint(); 2614 if (isa<UndefValue>(getAssociatedValue())) 2615 indicatePessimisticFixpoint(); 2616 } 2617 2618 /// See AbstractAttribute::updateImpl(...). 2619 ChangeStatus updateImpl(Attributor &A) override { 2620 auto UsePred = [&](const Use &U, bool &Follow) { 2621 Instruction *UserI = cast<Instruction>(U.getUser()); 2622 if (CallSite CS = CallSite(UserI)) { 2623 if (!CS.isArgOperand(&U)) 2624 return false; 2625 const IRPosition &CSArgPos = 2626 IRPosition::callsite_argument(CS, CS.getArgumentNo(&U)); 2627 const auto &CSArgIsDead = A.getAAFor<AAIsDead>(*this, CSArgPos); 2628 return CSArgIsDead.isAssumedDead(); 2629 } 2630 if (ReturnInst *RI = dyn_cast<ReturnInst>(UserI)) { 2631 const IRPosition &RetPos = IRPosition::returned(*RI->getFunction()); 2632 const auto &RetIsDeadAA = A.getAAFor<AAIsDead>(*this, RetPos); 2633 return RetIsDeadAA.isAssumedDead(); 2634 } 2635 Follow = true; 2636 return wouldInstructionBeTriviallyDead(UserI); 2637 }; 2638 2639 if (!A.checkForAllUses(UsePred, *this, getAssociatedValue())) 2640 return indicatePessimisticFixpoint(); 2641 return ChangeStatus::UNCHANGED; 2642 } 2643 2644 /// See AbstractAttribute::manifest(...). 2645 ChangeStatus manifest(Attributor &A) override { 2646 Value &V = getAssociatedValue(); 2647 if (auto *I = dyn_cast<Instruction>(&V)) 2648 if (wouldInstructionBeTriviallyDead(I)) { 2649 A.deleteAfterManifest(*I); 2650 return ChangeStatus::CHANGED; 2651 } 2652 2653 if (V.use_empty()) 2654 return ChangeStatus::UNCHANGED; 2655 2656 UndefValue &UV = *UndefValue::get(V.getType()); 2657 bool AnyChange = A.changeValueAfterManifest(V, UV); 2658 return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; 2659 } 2660 2661 /// See AbstractAttribute::trackStatistics() 2662 void trackStatistics() const override { 2663 STATS_DECLTRACK_FLOATING_ATTR(IsDead) 2664 } 2665 }; 2666 2667 struct AAIsDeadArgument : public AAIsDeadFloating { 2668 AAIsDeadArgument(const IRPosition &IRP) : AAIsDeadFloating(IRP) {} 2669 2670 /// See AbstractAttribute::initialize(...). 2671 void initialize(Attributor &A) override { 2672 if (!getAssociatedFunction()->hasExactDefinition()) 2673 indicatePessimisticFixpoint(); 2674 } 2675 2676 /// See AbstractAttribute::manifest(...). 2677 ChangeStatus manifest(Attributor &A) override { 2678 ChangeStatus Changed = AAIsDeadFloating::manifest(A); 2679 Argument &Arg = *getAssociatedArgument(); 2680 if (Arg.getParent()->hasLocalLinkage()) 2681 if (A.registerFunctionSignatureRewrite( 2682 Arg, /* ReplacementTypes */ {}, 2683 Attributor::ArgumentReplacementInfo::CalleeRepairCBTy{}, 2684 Attributor::ArgumentReplacementInfo::ACSRepairCBTy{})) 2685 return ChangeStatus::CHANGED; 2686 return Changed; 2687 } 2688 2689 /// See AbstractAttribute::trackStatistics() 2690 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(IsDead) } 2691 }; 2692 2693 struct AAIsDeadCallSiteArgument : public AAIsDeadValueImpl { 2694 AAIsDeadCallSiteArgument(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {} 2695 2696 /// See AbstractAttribute::initialize(...). 2697 void initialize(Attributor &A) override { 2698 if (isa<UndefValue>(getAssociatedValue())) 2699 indicatePessimisticFixpoint(); 2700 } 2701 2702 /// See AbstractAttribute::updateImpl(...). 2703 ChangeStatus updateImpl(Attributor &A) override { 2704 // TODO: Once we have call site specific value information we can provide 2705 // call site specific liveness information and then it makes 2706 // sense to specialize attributes for call sites arguments instead of 2707 // redirecting requests to the callee argument. 2708 Argument *Arg = getAssociatedArgument(); 2709 if (!Arg) 2710 return indicatePessimisticFixpoint(); 2711 const IRPosition &ArgPos = IRPosition::argument(*Arg); 2712 auto &ArgAA = A.getAAFor<AAIsDead>(*this, ArgPos); 2713 return clampStateAndIndicateChange( 2714 getState(), static_cast<const AAIsDead::StateType &>(ArgAA.getState())); 2715 } 2716 2717 /// See AbstractAttribute::manifest(...). 2718 ChangeStatus manifest(Attributor &A) override { 2719 CallBase &CB = cast<CallBase>(getAnchorValue()); 2720 Use &U = CB.getArgOperandUse(getArgNo()); 2721 assert(!isa<UndefValue>(U.get()) && 2722 "Expected undef values to be filtered out!"); 2723 UndefValue &UV = *UndefValue::get(U->getType()); 2724 if (A.changeUseAfterManifest(U, UV)) 2725 return ChangeStatus::CHANGED; 2726 return ChangeStatus::UNCHANGED; 2727 } 2728 2729 /// See AbstractAttribute::trackStatistics() 2730 void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(IsDead) } 2731 }; 2732 2733 struct AAIsDeadReturned : public AAIsDeadValueImpl { 2734 AAIsDeadReturned(const IRPosition &IRP) : AAIsDeadValueImpl(IRP) {} 2735 2736 /// See AbstractAttribute::updateImpl(...). 2737 ChangeStatus updateImpl(Attributor &A) override { 2738 2739 auto PredForCallSite = [&](AbstractCallSite ACS) { 2740 if (ACS.isCallbackCall()) 2741 return false; 2742 const IRPosition &CSRetPos = 2743 IRPosition::callsite_returned(ACS.getCallSite()); 2744 const auto &RetIsDeadAA = A.getAAFor<AAIsDead>(*this, CSRetPos); 2745 return RetIsDeadAA.isAssumedDead(); 2746 }; 2747 2748 if (!A.checkForAllCallSites(PredForCallSite, *this, true)) 2749 return indicatePessimisticFixpoint(); 2750 2751 return ChangeStatus::UNCHANGED; 2752 } 2753 2754 /// See AbstractAttribute::manifest(...). 2755 ChangeStatus manifest(Attributor &A) override { 2756 // TODO: Rewrite the signature to return void? 2757 bool AnyChange = false; 2758 UndefValue &UV = *UndefValue::get(getAssociatedFunction()->getReturnType()); 2759 auto RetInstPred = [&](Instruction &I) { 2760 ReturnInst &RI = cast<ReturnInst>(I); 2761 if (!isa<UndefValue>(RI.getReturnValue())) 2762 AnyChange |= A.changeUseAfterManifest(RI.getOperandUse(0), UV); 2763 return true; 2764 }; 2765 A.checkForAllInstructions(RetInstPred, *this, {Instruction::Ret}); 2766 return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED; 2767 } 2768 2769 /// See AbstractAttribute::trackStatistics() 2770 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(IsDead) } 2771 }; 2772 2773 struct AAIsDeadCallSiteReturned : public AAIsDeadFloating { 2774 AAIsDeadCallSiteReturned(const IRPosition &IRP) : AAIsDeadFloating(IRP) {} 2775 2776 /// See AbstractAttribute::initialize(...). 2777 void initialize(Attributor &A) override {} 2778 2779 /// See AbstractAttribute::trackStatistics() 2780 void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(IsDead) } 2781 }; 2782 2783 struct AAIsDeadFunction : public AAIsDead { 2784 AAIsDeadFunction(const IRPosition &IRP) : AAIsDead(IRP) {} 2785 2786 /// See AbstractAttribute::initialize(...). 2787 void initialize(Attributor &A) override { 2788 const Function *F = getAssociatedFunction(); 2789 if (F && !F->isDeclaration()) { 2790 ToBeExploredFrom.insert(&F->getEntryBlock().front()); 2791 assumeLive(A, F->getEntryBlock()); 2792 } 2793 } 2794 2795 /// See AbstractAttribute::getAsStr(). 2796 const std::string getAsStr() const override { 2797 return "Live[#BB " + std::to_string(AssumedLiveBlocks.size()) + "/" + 2798 std::to_string(getAssociatedFunction()->size()) + "][#TBEP " + 2799 std::to_string(ToBeExploredFrom.size()) + "][#KDE " + 2800 std::to_string(KnownDeadEnds.size()) + "]"; 2801 } 2802 2803 /// See AbstractAttribute::manifest(...). 2804 ChangeStatus manifest(Attributor &A) override { 2805 assert(getState().isValidState() && 2806 "Attempted to manifest an invalid state!"); 2807 2808 ChangeStatus HasChanged = ChangeStatus::UNCHANGED; 2809 Function &F = *getAssociatedFunction(); 2810 2811 if (AssumedLiveBlocks.empty()) { 2812 A.deleteAfterManifest(F); 2813 return ChangeStatus::CHANGED; 2814 } 2815 2816 // Flag to determine if we can change an invoke to a call assuming the 2817 // callee is nounwind. This is not possible if the personality of the 2818 // function allows to catch asynchronous exceptions. 2819 bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F); 2820 2821 KnownDeadEnds.set_union(ToBeExploredFrom); 2822 for (const Instruction *DeadEndI : KnownDeadEnds) { 2823 auto *CB = dyn_cast<CallBase>(DeadEndI); 2824 if (!CB) 2825 continue; 2826 const auto &NoReturnAA = 2827 A.getAAFor<AANoReturn>(*this, IRPosition::callsite_function(*CB)); 2828 bool MayReturn = !NoReturnAA.isAssumedNoReturn(); 2829 if (MayReturn && (!Invoke2CallAllowed || !isa<InvokeInst>(CB))) 2830 continue; 2831 2832 if (auto *II = dyn_cast<InvokeInst>(DeadEndI)) 2833 A.registerInvokeWithDeadSuccessor(const_cast<InvokeInst &>(*II)); 2834 else 2835 A.changeToUnreachableAfterManifest( 2836 const_cast<Instruction *>(DeadEndI->getNextNode())); 2837 HasChanged = ChangeStatus::CHANGED; 2838 } 2839 2840 for (BasicBlock &BB : F) 2841 if (!AssumedLiveBlocks.count(&BB)) 2842 A.deleteAfterManifest(BB); 2843 2844 return HasChanged; 2845 } 2846 2847 /// See AbstractAttribute::updateImpl(...). 2848 ChangeStatus updateImpl(Attributor &A) override; 2849 2850 /// See AbstractAttribute::trackStatistics() 2851 void trackStatistics() const override {} 2852 2853 /// Returns true if the function is assumed dead. 2854 bool isAssumedDead() const override { return false; } 2855 2856 /// See AAIsDead::isAssumedDead(BasicBlock *). 2857 bool isAssumedDead(const BasicBlock *BB) const override { 2858 assert(BB->getParent() == getAssociatedFunction() && 2859 "BB must be in the same anchor scope function."); 2860 2861 if (!getAssumed()) 2862 return false; 2863 return !AssumedLiveBlocks.count(BB); 2864 } 2865 2866 /// See AAIsDead::isKnownDead(BasicBlock *). 2867 bool isKnownDead(const BasicBlock *BB) const override { 2868 return getKnown() && isAssumedDead(BB); 2869 } 2870 2871 /// See AAIsDead::isAssumed(Instruction *I). 2872 bool isAssumedDead(const Instruction *I) const override { 2873 assert(I->getParent()->getParent() == getAssociatedFunction() && 2874 "Instruction must be in the same anchor scope function."); 2875 2876 if (!getAssumed()) 2877 return false; 2878 2879 // If it is not in AssumedLiveBlocks then it for sure dead. 2880 // Otherwise, it can still be after noreturn call in a live block. 2881 if (!AssumedLiveBlocks.count(I->getParent())) 2882 return true; 2883 2884 // If it is not after a liveness barrier it is live. 2885 const Instruction *PrevI = I->getPrevNode(); 2886 while (PrevI) { 2887 if (KnownDeadEnds.count(PrevI) || ToBeExploredFrom.count(PrevI)) 2888 return true; 2889 PrevI = PrevI->getPrevNode(); 2890 } 2891 return false; 2892 } 2893 2894 /// See AAIsDead::isKnownDead(Instruction *I). 2895 bool isKnownDead(const Instruction *I) const override { 2896 return getKnown() && isAssumedDead(I); 2897 } 2898 2899 /// Determine if \p F might catch asynchronous exceptions. 2900 static bool mayCatchAsynchronousExceptions(const Function &F) { 2901 return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(&F); 2902 } 2903 2904 /// Assume \p BB is (partially) live now and indicate to the Attributor \p A 2905 /// that internal function called from \p BB should now be looked at. 2906 bool assumeLive(Attributor &A, const BasicBlock &BB) { 2907 if (!AssumedLiveBlocks.insert(&BB).second) 2908 return false; 2909 2910 // We assume that all of BB is (probably) live now and if there are calls to 2911 // internal functions we will assume that those are now live as well. This 2912 // is a performance optimization for blocks with calls to a lot of internal 2913 // functions. It can however cause dead functions to be treated as live. 2914 for (const Instruction &I : BB) 2915 if (ImmutableCallSite ICS = ImmutableCallSite(&I)) 2916 if (const Function *F = ICS.getCalledFunction()) 2917 if (F->hasLocalLinkage()) 2918 A.markLiveInternalFunction(*F); 2919 return true; 2920 } 2921 2922 /// Collection of instructions that need to be explored again, e.g., we 2923 /// did assume they do not transfer control to (one of their) successors. 2924 SmallSetVector<const Instruction *, 8> ToBeExploredFrom; 2925 2926 /// Collection of instructions that are known to not transfer control. 2927 SmallSetVector<const Instruction *, 8> KnownDeadEnds; 2928 2929 /// Collection of all assumed live BasicBlocks. 2930 DenseSet<const BasicBlock *> AssumedLiveBlocks; 2931 }; 2932 2933 static bool 2934 identifyAliveSuccessors(Attributor &A, const CallBase &CB, 2935 AbstractAttribute &AA, 2936 SmallVectorImpl<const Instruction *> &AliveSuccessors) { 2937 const IRPosition &IPos = IRPosition::callsite_function(CB); 2938 2939 const auto &NoReturnAA = A.getAAFor<AANoReturn>(AA, IPos); 2940 if (NoReturnAA.isAssumedNoReturn()) 2941 return !NoReturnAA.isKnownNoReturn(); 2942 if (CB.isTerminator()) 2943 AliveSuccessors.push_back(&CB.getSuccessor(0)->front()); 2944 else 2945 AliveSuccessors.push_back(CB.getNextNode()); 2946 return false; 2947 } 2948 2949 static bool 2950 identifyAliveSuccessors(Attributor &A, const InvokeInst &II, 2951 AbstractAttribute &AA, 2952 SmallVectorImpl<const Instruction *> &AliveSuccessors) { 2953 bool UsedAssumedInformation = 2954 identifyAliveSuccessors(A, cast<CallBase>(II), AA, AliveSuccessors); 2955 2956 // First, determine if we can change an invoke to a call assuming the 2957 // callee is nounwind. This is not possible if the personality of the 2958 // function allows to catch asynchronous exceptions. 2959 if (AAIsDeadFunction::mayCatchAsynchronousExceptions(*II.getFunction())) { 2960 AliveSuccessors.push_back(&II.getUnwindDest()->front()); 2961 } else { 2962 const IRPosition &IPos = IRPosition::callsite_function(II); 2963 const auto &AANoUnw = A.getAAFor<AANoUnwind>(AA, IPos); 2964 if (AANoUnw.isAssumedNoUnwind()) { 2965 UsedAssumedInformation |= !AANoUnw.isKnownNoUnwind(); 2966 } else { 2967 AliveSuccessors.push_back(&II.getUnwindDest()->front()); 2968 } 2969 } 2970 return UsedAssumedInformation; 2971 } 2972 2973 static Optional<ConstantInt *> 2974 getAssumedConstant(Attributor &A, const Value &V, AbstractAttribute &AA, 2975 bool &UsedAssumedInformation) { 2976 const auto &ValueSimplifyAA = 2977 A.getAAFor<AAValueSimplify>(AA, IRPosition::value(V)); 2978 Optional<Value *> SimplifiedV = ValueSimplifyAA.getAssumedSimplifiedValue(A); 2979 UsedAssumedInformation |= !ValueSimplifyAA.isKnown(); 2980 if (!SimplifiedV.hasValue()) 2981 return llvm::None; 2982 if (isa_and_nonnull<UndefValue>(SimplifiedV.getValue())) 2983 return llvm::None; 2984 return dyn_cast_or_null<ConstantInt>(SimplifiedV.getValue()); 2985 } 2986 2987 static bool 2988 identifyAliveSuccessors(Attributor &A, const BranchInst &BI, 2989 AbstractAttribute &AA, 2990 SmallVectorImpl<const Instruction *> &AliveSuccessors) { 2991 bool UsedAssumedInformation = false; 2992 if (BI.getNumSuccessors() == 1) { 2993 AliveSuccessors.push_back(&BI.getSuccessor(0)->front()); 2994 } else { 2995 Optional<ConstantInt *> CI = 2996 getAssumedConstant(A, *BI.getCondition(), AA, UsedAssumedInformation); 2997 if (!CI.hasValue()) { 2998 // No value yet, assume both edges are dead. 2999 } else if (CI.getValue()) { 3000 const BasicBlock *SuccBB = 3001 BI.getSuccessor(1 - CI.getValue()->getZExtValue()); 3002 AliveSuccessors.push_back(&SuccBB->front()); 3003 } else { 3004 AliveSuccessors.push_back(&BI.getSuccessor(0)->front()); 3005 AliveSuccessors.push_back(&BI.getSuccessor(1)->front()); 3006 UsedAssumedInformation = false; 3007 } 3008 } 3009 return UsedAssumedInformation; 3010 } 3011 3012 static bool 3013 identifyAliveSuccessors(Attributor &A, const SwitchInst &SI, 3014 AbstractAttribute &AA, 3015 SmallVectorImpl<const Instruction *> &AliveSuccessors) { 3016 bool UsedAssumedInformation = false; 3017 Optional<ConstantInt *> CI = 3018 getAssumedConstant(A, *SI.getCondition(), AA, UsedAssumedInformation); 3019 if (!CI.hasValue()) { 3020 // No value yet, assume all edges are dead. 3021 } else if (CI.getValue()) { 3022 for (auto &CaseIt : SI.cases()) { 3023 if (CaseIt.getCaseValue() == CI.getValue()) { 3024 AliveSuccessors.push_back(&CaseIt.getCaseSuccessor()->front()); 3025 return UsedAssumedInformation; 3026 } 3027 } 3028 AliveSuccessors.push_back(&SI.getDefaultDest()->front()); 3029 return UsedAssumedInformation; 3030 } else { 3031 for (const BasicBlock *SuccBB : successors(SI.getParent())) 3032 AliveSuccessors.push_back(&SuccBB->front()); 3033 } 3034 return UsedAssumedInformation; 3035 } 3036 3037 ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) { 3038 ChangeStatus Change = ChangeStatus::UNCHANGED; 3039 3040 LLVM_DEBUG(dbgs() << "[AAIsDead] Live [" << AssumedLiveBlocks.size() << "/" 3041 << getAssociatedFunction()->size() << "] BBs and " 3042 << ToBeExploredFrom.size() << " exploration points and " 3043 << KnownDeadEnds.size() << " known dead ends\n"); 3044 3045 // Copy and clear the list of instructions we need to explore from. It is 3046 // refilled with instructions the next update has to look at. 3047 SmallVector<const Instruction *, 8> Worklist(ToBeExploredFrom.begin(), 3048 ToBeExploredFrom.end()); 3049 decltype(ToBeExploredFrom) NewToBeExploredFrom; 3050 3051 SmallVector<const Instruction *, 8> AliveSuccessors; 3052 while (!Worklist.empty()) { 3053 const Instruction *I = Worklist.pop_back_val(); 3054 LLVM_DEBUG(dbgs() << "[AAIsDead] Exploration inst: " << *I << "\n"); 3055 3056 AliveSuccessors.clear(); 3057 3058 bool UsedAssumedInformation = false; 3059 switch (I->getOpcode()) { 3060 // TODO: look for (assumed) UB to backwards propagate "deadness". 3061 default: 3062 if (I->isTerminator()) { 3063 for (const BasicBlock *SuccBB : successors(I->getParent())) 3064 AliveSuccessors.push_back(&SuccBB->front()); 3065 } else { 3066 AliveSuccessors.push_back(I->getNextNode()); 3067 } 3068 break; 3069 case Instruction::Call: 3070 UsedAssumedInformation = identifyAliveSuccessors(A, cast<CallInst>(*I), 3071 *this, AliveSuccessors); 3072 break; 3073 case Instruction::Invoke: 3074 UsedAssumedInformation = identifyAliveSuccessors(A, cast<InvokeInst>(*I), 3075 *this, AliveSuccessors); 3076 break; 3077 case Instruction::Br: 3078 UsedAssumedInformation = identifyAliveSuccessors(A, cast<BranchInst>(*I), 3079 *this, AliveSuccessors); 3080 break; 3081 case Instruction::Switch: 3082 UsedAssumedInformation = identifyAliveSuccessors(A, cast<SwitchInst>(*I), 3083 *this, AliveSuccessors); 3084 break; 3085 } 3086 3087 if (UsedAssumedInformation) { 3088 NewToBeExploredFrom.insert(I); 3089 } else { 3090 Change = ChangeStatus::CHANGED; 3091 if (AliveSuccessors.empty() || 3092 (I->isTerminator() && AliveSuccessors.size() < I->getNumSuccessors())) 3093 KnownDeadEnds.insert(I); 3094 } 3095 3096 LLVM_DEBUG(dbgs() << "[AAIsDead] #AliveSuccessors: " 3097 << AliveSuccessors.size() << " UsedAssumedInformation: " 3098 << UsedAssumedInformation << "\n"); 3099 3100 for (const Instruction *AliveSuccessor : AliveSuccessors) { 3101 if (!I->isTerminator()) { 3102 assert(AliveSuccessors.size() == 1 && 3103 "Non-terminator expected to have a single successor!"); 3104 Worklist.push_back(AliveSuccessor); 3105 } else { 3106 if (assumeLive(A, *AliveSuccessor->getParent())) 3107 Worklist.push_back(AliveSuccessor); 3108 } 3109 } 3110 } 3111 3112 ToBeExploredFrom = std::move(NewToBeExploredFrom); 3113 3114 // If we know everything is live there is no need to query for liveness. 3115 // Instead, indicating a pessimistic fixpoint will cause the state to be 3116 // "invalid" and all queries to be answered conservatively without lookups. 3117 // To be in this state we have to (1) finished the exploration and (3) not 3118 // discovered any non-trivial dead end and (2) not ruled unreachable code 3119 // dead. 3120 if (ToBeExploredFrom.empty() && 3121 getAssociatedFunction()->size() == AssumedLiveBlocks.size() && 3122 llvm::all_of(KnownDeadEnds, [](const Instruction *DeadEndI) { 3123 return DeadEndI->isTerminator() && DeadEndI->getNumSuccessors() == 0; 3124 })) 3125 return indicatePessimisticFixpoint(); 3126 return Change; 3127 } 3128 3129 /// Liveness information for a call sites. 3130 struct AAIsDeadCallSite final : AAIsDeadFunction { 3131 AAIsDeadCallSite(const IRPosition &IRP) : AAIsDeadFunction(IRP) {} 3132 3133 /// See AbstractAttribute::initialize(...). 3134 void initialize(Attributor &A) override { 3135 // TODO: Once we have call site specific value information we can provide 3136 // call site specific liveness information and then it makes 3137 // sense to specialize attributes for call sites instead of 3138 // redirecting requests to the callee. 3139 llvm_unreachable("Abstract attributes for liveness are not " 3140 "supported for call sites yet!"); 3141 } 3142 3143 /// See AbstractAttribute::updateImpl(...). 3144 ChangeStatus updateImpl(Attributor &A) override { 3145 return indicatePessimisticFixpoint(); 3146 } 3147 3148 /// See AbstractAttribute::trackStatistics() 3149 void trackStatistics() const override {} 3150 }; 3151 3152 /// -------------------- Dereferenceable Argument Attribute -------------------- 3153 3154 template <> 3155 ChangeStatus clampStateAndIndicateChange<DerefState>(DerefState &S, 3156 const DerefState &R) { 3157 ChangeStatus CS0 = 3158 clampStateAndIndicateChange(S.DerefBytesState, R.DerefBytesState); 3159 ChangeStatus CS1 = clampStateAndIndicateChange(S.GlobalState, R.GlobalState); 3160 return CS0 | CS1; 3161 } 3162 3163 struct AADereferenceableImpl : AADereferenceable { 3164 AADereferenceableImpl(const IRPosition &IRP) : AADereferenceable(IRP) {} 3165 using StateType = DerefState; 3166 3167 void initialize(Attributor &A) override { 3168 SmallVector<Attribute, 4> Attrs; 3169 getAttrs({Attribute::Dereferenceable, Attribute::DereferenceableOrNull}, 3170 Attrs); 3171 for (const Attribute &Attr : Attrs) 3172 takeKnownDerefBytesMaximum(Attr.getValueAsInt()); 3173 3174 NonNullAA = &A.getAAFor<AANonNull>(*this, getIRPosition()); 3175 3176 const IRPosition &IRP = this->getIRPosition(); 3177 bool IsFnInterface = IRP.isFnInterfaceKind(); 3178 const Function *FnScope = IRP.getAnchorScope(); 3179 if (IsFnInterface && (!FnScope || !FnScope->hasExactDefinition())) 3180 indicatePessimisticFixpoint(); 3181 } 3182 3183 /// See AbstractAttribute::getState() 3184 /// { 3185 StateType &getState() override { return *this; } 3186 const StateType &getState() const override { return *this; } 3187 /// } 3188 3189 /// Helper function for collecting accessed bytes in must-be-executed-context 3190 void addAccessedBytesForUse(Attributor &A, const Use *U, 3191 const Instruction *I) { 3192 const Value *UseV = U->get(); 3193 if (!UseV->getType()->isPointerTy()) 3194 return; 3195 3196 Type *PtrTy = UseV->getType(); 3197 const DataLayout &DL = A.getDataLayout(); 3198 int64_t Offset; 3199 if (const Value *Base = getBasePointerOfAccessPointerOperand( 3200 I, Offset, DL, /*AllowNonInbounds*/ true)) { 3201 if (Base == &getAssociatedValue() && 3202 Attributor::getPointerOperand(I, /* AllowVolatile */ false) == UseV) { 3203 uint64_t Size = DL.getTypeStoreSize(PtrTy->getPointerElementType()); 3204 addAccessedBytes(Offset, Size); 3205 } 3206 } 3207 return; 3208 } 3209 3210 /// See AAFromMustBeExecutedContext 3211 bool followUse(Attributor &A, const Use *U, const Instruction *I) { 3212 bool IsNonNull = false; 3213 bool TrackUse = false; 3214 int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse( 3215 A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse); 3216 3217 addAccessedBytesForUse(A, U, I); 3218 takeKnownDerefBytesMaximum(DerefBytes); 3219 return TrackUse; 3220 } 3221 3222 /// See AbstractAttribute::manifest(...). 3223 ChangeStatus manifest(Attributor &A) override { 3224 ChangeStatus Change = AADereferenceable::manifest(A); 3225 if (isAssumedNonNull() && hasAttr(Attribute::DereferenceableOrNull)) { 3226 removeAttrs({Attribute::DereferenceableOrNull}); 3227 return ChangeStatus::CHANGED; 3228 } 3229 return Change; 3230 } 3231 3232 void getDeducedAttributes(LLVMContext &Ctx, 3233 SmallVectorImpl<Attribute> &Attrs) const override { 3234 // TODO: Add *_globally support 3235 if (isAssumedNonNull()) 3236 Attrs.emplace_back(Attribute::getWithDereferenceableBytes( 3237 Ctx, getAssumedDereferenceableBytes())); 3238 else 3239 Attrs.emplace_back(Attribute::getWithDereferenceableOrNullBytes( 3240 Ctx, getAssumedDereferenceableBytes())); 3241 } 3242 3243 /// See AbstractAttribute::getAsStr(). 3244 const std::string getAsStr() const override { 3245 if (!getAssumedDereferenceableBytes()) 3246 return "unknown-dereferenceable"; 3247 return std::string("dereferenceable") + 3248 (isAssumedNonNull() ? "" : "_or_null") + 3249 (isAssumedGlobal() ? "_globally" : "") + "<" + 3250 std::to_string(getKnownDereferenceableBytes()) + "-" + 3251 std::to_string(getAssumedDereferenceableBytes()) + ">"; 3252 } 3253 }; 3254 3255 /// Dereferenceable attribute for a floating value. 3256 struct AADereferenceableFloating 3257 : AAFromMustBeExecutedContext<AADereferenceable, AADereferenceableImpl> { 3258 using Base = 3259 AAFromMustBeExecutedContext<AADereferenceable, AADereferenceableImpl>; 3260 AADereferenceableFloating(const IRPosition &IRP) : Base(IRP) {} 3261 3262 /// See AbstractAttribute::updateImpl(...). 3263 ChangeStatus updateImpl(Attributor &A) override { 3264 ChangeStatus Change = Base::updateImpl(A); 3265 3266 const DataLayout &DL = A.getDataLayout(); 3267 3268 auto VisitValueCB = [&](Value &V, DerefState &T, bool Stripped) -> bool { 3269 unsigned IdxWidth = 3270 DL.getIndexSizeInBits(V.getType()->getPointerAddressSpace()); 3271 APInt Offset(IdxWidth, 0); 3272 const Value *Base = 3273 V.stripAndAccumulateInBoundsConstantOffsets(DL, Offset); 3274 3275 const auto &AA = 3276 A.getAAFor<AADereferenceable>(*this, IRPosition::value(*Base)); 3277 int64_t DerefBytes = 0; 3278 if (!Stripped && this == &AA) { 3279 // Use IR information if we did not strip anything. 3280 // TODO: track globally. 3281 bool CanBeNull; 3282 DerefBytes = Base->getPointerDereferenceableBytes(DL, CanBeNull); 3283 T.GlobalState.indicatePessimisticFixpoint(); 3284 } else { 3285 const DerefState &DS = static_cast<const DerefState &>(AA.getState()); 3286 DerefBytes = DS.DerefBytesState.getAssumed(); 3287 T.GlobalState &= DS.GlobalState; 3288 } 3289 3290 // TODO: Use `AAConstantRange` to infer dereferenceable bytes. 3291 3292 // For now we do not try to "increase" dereferenceability due to negative 3293 // indices as we first have to come up with code to deal with loops and 3294 // for overflows of the dereferenceable bytes. 3295 int64_t OffsetSExt = Offset.getSExtValue(); 3296 if (OffsetSExt < 0) 3297 OffsetSExt = 0; 3298 3299 T.takeAssumedDerefBytesMinimum( 3300 std::max(int64_t(0), DerefBytes - OffsetSExt)); 3301 3302 if (this == &AA) { 3303 if (!Stripped) { 3304 // If nothing was stripped IR information is all we got. 3305 T.takeKnownDerefBytesMaximum( 3306 std::max(int64_t(0), DerefBytes - OffsetSExt)); 3307 T.indicatePessimisticFixpoint(); 3308 } else if (OffsetSExt > 0) { 3309 // If something was stripped but there is circular reasoning we look 3310 // for the offset. If it is positive we basically decrease the 3311 // dereferenceable bytes in a circluar loop now, which will simply 3312 // drive them down to the known value in a very slow way which we 3313 // can accelerate. 3314 T.indicatePessimisticFixpoint(); 3315 } 3316 } 3317 3318 return T.isValidState(); 3319 }; 3320 3321 DerefState T; 3322 if (!genericValueTraversal<AADereferenceable, DerefState>( 3323 A, getIRPosition(), *this, T, VisitValueCB)) 3324 return indicatePessimisticFixpoint(); 3325 3326 return Change | clampStateAndIndicateChange(getState(), T); 3327 } 3328 3329 /// See AbstractAttribute::trackStatistics() 3330 void trackStatistics() const override { 3331 STATS_DECLTRACK_FLOATING_ATTR(dereferenceable) 3332 } 3333 }; 3334 3335 /// Dereferenceable attribute for a return value. 3336 struct AADereferenceableReturned final 3337 : AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl, 3338 DerefState> { 3339 AADereferenceableReturned(const IRPosition &IRP) 3340 : AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl, 3341 DerefState>(IRP) {} 3342 3343 /// See AbstractAttribute::trackStatistics() 3344 void trackStatistics() const override { 3345 STATS_DECLTRACK_FNRET_ATTR(dereferenceable) 3346 } 3347 }; 3348 3349 /// Dereferenceable attribute for an argument 3350 struct AADereferenceableArgument final 3351 : AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext< 3352 AADereferenceable, AADereferenceableImpl, DerefState> { 3353 using Base = AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext< 3354 AADereferenceable, AADereferenceableImpl, DerefState>; 3355 AADereferenceableArgument(const IRPosition &IRP) : Base(IRP) {} 3356 3357 /// See AbstractAttribute::trackStatistics() 3358 void trackStatistics() const override { 3359 STATS_DECLTRACK_ARG_ATTR(dereferenceable) 3360 } 3361 }; 3362 3363 /// Dereferenceable attribute for a call site argument. 3364 struct AADereferenceableCallSiteArgument final : AADereferenceableFloating { 3365 AADereferenceableCallSiteArgument(const IRPosition &IRP) 3366 : AADereferenceableFloating(IRP) {} 3367 3368 /// See AbstractAttribute::trackStatistics() 3369 void trackStatistics() const override { 3370 STATS_DECLTRACK_CSARG_ATTR(dereferenceable) 3371 } 3372 }; 3373 3374 /// Dereferenceable attribute deduction for a call site return value. 3375 struct AADereferenceableCallSiteReturned final 3376 : AACallSiteReturnedFromReturnedAndMustBeExecutedContext< 3377 AADereferenceable, AADereferenceableImpl> { 3378 using Base = AACallSiteReturnedFromReturnedAndMustBeExecutedContext< 3379 AADereferenceable, AADereferenceableImpl>; 3380 AADereferenceableCallSiteReturned(const IRPosition &IRP) : Base(IRP) {} 3381 3382 /// See AbstractAttribute::trackStatistics() 3383 void trackStatistics() const override { 3384 STATS_DECLTRACK_CS_ATTR(dereferenceable); 3385 } 3386 }; 3387 3388 // ------------------------ Align Argument Attribute ------------------------ 3389 3390 static unsigned int getKnownAlignForUse(Attributor &A, 3391 AbstractAttribute &QueryingAA, 3392 Value &AssociatedValue, const Use *U, 3393 const Instruction *I, bool &TrackUse) { 3394 // We need to follow common pointer manipulation uses to the accesses they 3395 // feed into. 3396 if (isa<CastInst>(I)) { 3397 // Follow all but ptr2int casts. 3398 TrackUse = !isa<PtrToIntInst>(I); 3399 return 0; 3400 } 3401 if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) { 3402 if (GEP->hasAllConstantIndices()) { 3403 TrackUse = true; 3404 return 0; 3405 } 3406 } 3407 3408 unsigned Alignment = 0; 3409 if (ImmutableCallSite ICS = ImmutableCallSite(I)) { 3410 if (ICS.isBundleOperand(U) || ICS.isCallee(U)) 3411 return 0; 3412 3413 unsigned ArgNo = ICS.getArgumentNo(U); 3414 IRPosition IRP = IRPosition::callsite_argument(ICS, ArgNo); 3415 // As long as we only use known information there is no need to track 3416 // dependences here. 3417 auto &AlignAA = A.getAAFor<AAAlign>(QueryingAA, IRP, 3418 /* TrackDependence */ false); 3419 Alignment = AlignAA.getKnownAlign(); 3420 } 3421 3422 const Value *UseV = U->get(); 3423 if (auto *SI = dyn_cast<StoreInst>(I)) 3424 Alignment = SI->getAlignment(); 3425 else if (auto *LI = dyn_cast<LoadInst>(I)) 3426 Alignment = LI->getAlignment(); 3427 3428 if (Alignment <= 1) 3429 return 0; 3430 3431 auto &DL = A.getDataLayout(); 3432 int64_t Offset; 3433 3434 if (const Value *Base = GetPointerBaseWithConstantOffset(UseV, Offset, DL)) { 3435 if (Base == &AssociatedValue) { 3436 // BasePointerAddr + Offset = Alignment * Q for some integer Q. 3437 // So we can say that the maximum power of two which is a divisor of 3438 // gcd(Offset, Alignment) is an alignment. 3439 3440 uint32_t gcd = 3441 greatestCommonDivisor(uint32_t(abs((int32_t)Offset)), Alignment); 3442 Alignment = llvm::PowerOf2Floor(gcd); 3443 } 3444 } 3445 3446 return Alignment; 3447 } 3448 struct AAAlignImpl : AAAlign { 3449 AAAlignImpl(const IRPosition &IRP) : AAAlign(IRP) {} 3450 3451 /// See AbstractAttribute::initialize(...). 3452 void initialize(Attributor &A) override { 3453 SmallVector<Attribute, 4> Attrs; 3454 getAttrs({Attribute::Alignment}, Attrs); 3455 for (const Attribute &Attr : Attrs) 3456 takeKnownMaximum(Attr.getValueAsInt()); 3457 3458 if (getIRPosition().isFnInterfaceKind() && 3459 (!getAssociatedFunction() || 3460 !getAssociatedFunction()->hasExactDefinition())) 3461 indicatePessimisticFixpoint(); 3462 } 3463 3464 /// See AbstractAttribute::manifest(...). 3465 ChangeStatus manifest(Attributor &A) override { 3466 ChangeStatus Changed = ChangeStatus::UNCHANGED; 3467 3468 // Check for users that allow alignment annotations. 3469 Value &AnchorVal = getIRPosition().getAnchorValue(); 3470 for (const Use &U : AnchorVal.uses()) { 3471 if (auto *SI = dyn_cast<StoreInst>(U.getUser())) { 3472 if (SI->getPointerOperand() == &AnchorVal) 3473 if (SI->getAlignment() < getAssumedAlign()) { 3474 STATS_DECLTRACK(AAAlign, Store, 3475 "Number of times alignment added to a store"); 3476 SI->setAlignment(Align(getAssumedAlign())); 3477 Changed = ChangeStatus::CHANGED; 3478 } 3479 } else if (auto *LI = dyn_cast<LoadInst>(U.getUser())) { 3480 if (LI->getPointerOperand() == &AnchorVal) 3481 if (LI->getAlignment() < getAssumedAlign()) { 3482 LI->setAlignment(Align(getAssumedAlign())); 3483 STATS_DECLTRACK(AAAlign, Load, 3484 "Number of times alignment added to a load"); 3485 Changed = ChangeStatus::CHANGED; 3486 } 3487 } 3488 } 3489 3490 return AAAlign::manifest(A) | Changed; 3491 } 3492 3493 // TODO: Provide a helper to determine the implied ABI alignment and check in 3494 // the existing manifest method and a new one for AAAlignImpl that value 3495 // to avoid making the alignment explicit if it did not improve. 3496 3497 /// See AbstractAttribute::getDeducedAttributes 3498 virtual void 3499 getDeducedAttributes(LLVMContext &Ctx, 3500 SmallVectorImpl<Attribute> &Attrs) const override { 3501 if (getAssumedAlign() > 1) 3502 Attrs.emplace_back( 3503 Attribute::getWithAlignment(Ctx, Align(getAssumedAlign()))); 3504 } 3505 /// See AAFromMustBeExecutedContext 3506 bool followUse(Attributor &A, const Use *U, const Instruction *I) { 3507 bool TrackUse = false; 3508 3509 unsigned int KnownAlign = 3510 getKnownAlignForUse(A, *this, getAssociatedValue(), U, I, TrackUse); 3511 takeKnownMaximum(KnownAlign); 3512 3513 return TrackUse; 3514 } 3515 3516 /// See AbstractAttribute::getAsStr(). 3517 const std::string getAsStr() const override { 3518 return getAssumedAlign() ? ("align<" + std::to_string(getKnownAlign()) + 3519 "-" + std::to_string(getAssumedAlign()) + ">") 3520 : "unknown-align"; 3521 } 3522 }; 3523 3524 /// Align attribute for a floating value. 3525 struct AAAlignFloating : AAFromMustBeExecutedContext<AAAlign, AAAlignImpl> { 3526 using Base = AAFromMustBeExecutedContext<AAAlign, AAAlignImpl>; 3527 AAAlignFloating(const IRPosition &IRP) : Base(IRP) {} 3528 3529 /// See AbstractAttribute::updateImpl(...). 3530 ChangeStatus updateImpl(Attributor &A) override { 3531 Base::updateImpl(A); 3532 3533 const DataLayout &DL = A.getDataLayout(); 3534 3535 auto VisitValueCB = [&](Value &V, AAAlign::StateType &T, 3536 bool Stripped) -> bool { 3537 const auto &AA = A.getAAFor<AAAlign>(*this, IRPosition::value(V)); 3538 if (!Stripped && this == &AA) { 3539 // Use only IR information if we did not strip anything. 3540 const MaybeAlign PA = V.getPointerAlignment(DL); 3541 T.takeKnownMaximum(PA ? PA->value() : 0); 3542 T.indicatePessimisticFixpoint(); 3543 } else { 3544 // Use abstract attribute information. 3545 const AAAlign::StateType &DS = 3546 static_cast<const AAAlign::StateType &>(AA.getState()); 3547 T ^= DS; 3548 } 3549 return T.isValidState(); 3550 }; 3551 3552 StateType T; 3553 if (!genericValueTraversal<AAAlign, StateType>(A, getIRPosition(), *this, T, 3554 VisitValueCB)) 3555 return indicatePessimisticFixpoint(); 3556 3557 // TODO: If we know we visited all incoming values, thus no are assumed 3558 // dead, we can take the known information from the state T. 3559 return clampStateAndIndicateChange(getState(), T); 3560 } 3561 3562 /// See AbstractAttribute::trackStatistics() 3563 void trackStatistics() const override { STATS_DECLTRACK_FLOATING_ATTR(align) } 3564 }; 3565 3566 /// Align attribute for function return value. 3567 struct AAAlignReturned final 3568 : AAReturnedFromReturnedValues<AAAlign, AAAlignImpl> { 3569 AAAlignReturned(const IRPosition &IRP) 3570 : AAReturnedFromReturnedValues<AAAlign, AAAlignImpl>(IRP) {} 3571 3572 /// See AbstractAttribute::trackStatistics() 3573 void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(aligned) } 3574 }; 3575 3576 /// Align attribute for function argument. 3577 struct AAAlignArgument final 3578 : AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext<AAAlign, 3579 AAAlignImpl> { 3580 AAAlignArgument(const IRPosition &IRP) 3581 : AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext<AAAlign, 3582 AAAlignImpl>( 3583 IRP) {} 3584 3585 /// See AbstractAttribute::trackStatistics() 3586 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(aligned) } 3587 }; 3588 3589 struct AAAlignCallSiteArgument final : AAAlignFloating { 3590 AAAlignCallSiteArgument(const IRPosition &IRP) : AAAlignFloating(IRP) {} 3591 3592 /// See AbstractAttribute::manifest(...). 3593 ChangeStatus manifest(Attributor &A) override { 3594 return AAAlignImpl::manifest(A); 3595 } 3596 3597 /// See AbstractAttribute::updateImpl(Attributor &A). 3598 ChangeStatus updateImpl(Attributor &A) override { 3599 ChangeStatus Changed = AAAlignFloating::updateImpl(A); 3600 if (Argument *Arg = getAssociatedArgument()) { 3601 const auto &ArgAlignAA = A.getAAFor<AAAlign>( 3602 *this, IRPosition::argument(*Arg), /* TrackDependence */ false, 3603 DepClassTy::OPTIONAL); 3604 takeKnownMaximum(ArgAlignAA.getKnownAlign()); 3605 } 3606 return Changed; 3607 } 3608 3609 /// See AbstractAttribute::trackStatistics() 3610 void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(aligned) } 3611 }; 3612 3613 /// Align attribute deduction for a call site return value. 3614 struct AAAlignCallSiteReturned final 3615 : AACallSiteReturnedFromReturnedAndMustBeExecutedContext<AAAlign, 3616 AAAlignImpl> { 3617 using Base = 3618 AACallSiteReturnedFromReturnedAndMustBeExecutedContext<AAAlign, 3619 AAAlignImpl>; 3620 AAAlignCallSiteReturned(const IRPosition &IRP) : Base(IRP) {} 3621 3622 /// See AbstractAttribute::initialize(...). 3623 void initialize(Attributor &A) override { 3624 Base::initialize(A); 3625 Function *F = getAssociatedFunction(); 3626 if (!F) 3627 indicatePessimisticFixpoint(); 3628 } 3629 3630 /// See AbstractAttribute::trackStatistics() 3631 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(align); } 3632 }; 3633 3634 /// ------------------ Function No-Return Attribute ---------------------------- 3635 struct AANoReturnImpl : public AANoReturn { 3636 AANoReturnImpl(const IRPosition &IRP) : AANoReturn(IRP) {} 3637 3638 /// See AbstractAttribute::initialize(...). 3639 void initialize(Attributor &A) override { 3640 AANoReturn::initialize(A); 3641 Function *F = getAssociatedFunction(); 3642 if (!F) 3643 indicatePessimisticFixpoint(); 3644 } 3645 3646 /// See AbstractAttribute::getAsStr(). 3647 const std::string getAsStr() const override { 3648 return getAssumed() ? "noreturn" : "may-return"; 3649 } 3650 3651 /// See AbstractAttribute::updateImpl(Attributor &A). 3652 virtual ChangeStatus updateImpl(Attributor &A) override { 3653 auto CheckForNoReturn = [](Instruction &) { return false; }; 3654 if (!A.checkForAllInstructions(CheckForNoReturn, *this, 3655 {(unsigned)Instruction::Ret})) 3656 return indicatePessimisticFixpoint(); 3657 return ChangeStatus::UNCHANGED; 3658 } 3659 }; 3660 3661 struct AANoReturnFunction final : AANoReturnImpl { 3662 AANoReturnFunction(const IRPosition &IRP) : AANoReturnImpl(IRP) {} 3663 3664 /// See AbstractAttribute::trackStatistics() 3665 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(noreturn) } 3666 }; 3667 3668 /// NoReturn attribute deduction for a call sites. 3669 struct AANoReturnCallSite final : AANoReturnImpl { 3670 AANoReturnCallSite(const IRPosition &IRP) : AANoReturnImpl(IRP) {} 3671 3672 /// See AbstractAttribute::updateImpl(...). 3673 ChangeStatus updateImpl(Attributor &A) override { 3674 // TODO: Once we have call site specific value information we can provide 3675 // call site specific liveness information and then it makes 3676 // sense to specialize attributes for call sites arguments instead of 3677 // redirecting requests to the callee argument. 3678 Function *F = getAssociatedFunction(); 3679 const IRPosition &FnPos = IRPosition::function(*F); 3680 auto &FnAA = A.getAAFor<AANoReturn>(*this, FnPos); 3681 return clampStateAndIndicateChange( 3682 getState(), 3683 static_cast<const AANoReturn::StateType &>(FnAA.getState())); 3684 } 3685 3686 /// See AbstractAttribute::trackStatistics() 3687 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(noreturn); } 3688 }; 3689 3690 /// ----------------------- Variable Capturing --------------------------------- 3691 3692 /// A class to hold the state of for no-capture attributes. 3693 struct AANoCaptureImpl : public AANoCapture { 3694 AANoCaptureImpl(const IRPosition &IRP) : AANoCapture(IRP) {} 3695 3696 /// See AbstractAttribute::initialize(...). 3697 void initialize(Attributor &A) override { 3698 if (hasAttr(getAttrKind(), /* IgnoreSubsumingPositions */ true)) { 3699 indicateOptimisticFixpoint(); 3700 return; 3701 } 3702 Function *AnchorScope = getAnchorScope(); 3703 if (isFnInterfaceKind() && 3704 (!AnchorScope || !AnchorScope->hasExactDefinition())) { 3705 indicatePessimisticFixpoint(); 3706 return; 3707 } 3708 3709 // You cannot "capture" null in the default address space. 3710 if (isa<ConstantPointerNull>(getAssociatedValue()) && 3711 getAssociatedValue().getType()->getPointerAddressSpace() == 0) { 3712 indicateOptimisticFixpoint(); 3713 return; 3714 } 3715 3716 const Function *F = getArgNo() >= 0 ? getAssociatedFunction() : AnchorScope; 3717 3718 // Check what state the associated function can actually capture. 3719 if (F) 3720 determineFunctionCaptureCapabilities(getIRPosition(), *F, *this); 3721 else 3722 indicatePessimisticFixpoint(); 3723 } 3724 3725 /// See AbstractAttribute::updateImpl(...). 3726 ChangeStatus updateImpl(Attributor &A) override; 3727 3728 /// see AbstractAttribute::isAssumedNoCaptureMaybeReturned(...). 3729 virtual void 3730 getDeducedAttributes(LLVMContext &Ctx, 3731 SmallVectorImpl<Attribute> &Attrs) const override { 3732 if (!isAssumedNoCaptureMaybeReturned()) 3733 return; 3734 3735 if (getArgNo() >= 0) { 3736 if (isAssumedNoCapture()) 3737 Attrs.emplace_back(Attribute::get(Ctx, Attribute::NoCapture)); 3738 else if (ManifestInternal) 3739 Attrs.emplace_back(Attribute::get(Ctx, "no-capture-maybe-returned")); 3740 } 3741 } 3742 3743 /// Set the NOT_CAPTURED_IN_MEM and NOT_CAPTURED_IN_RET bits in \p Known 3744 /// depending on the ability of the function associated with \p IRP to capture 3745 /// state in memory and through "returning/throwing", respectively. 3746 static void determineFunctionCaptureCapabilities(const IRPosition &IRP, 3747 const Function &F, 3748 BitIntegerState &State) { 3749 // TODO: Once we have memory behavior attributes we should use them here. 3750 3751 // If we know we cannot communicate or write to memory, we do not care about 3752 // ptr2int anymore. 3753 if (F.onlyReadsMemory() && F.doesNotThrow() && 3754 F.getReturnType()->isVoidTy()) { 3755 State.addKnownBits(NO_CAPTURE); 3756 return; 3757 } 3758 3759 // A function cannot capture state in memory if it only reads memory, it can 3760 // however return/throw state and the state might be influenced by the 3761 // pointer value, e.g., loading from a returned pointer might reveal a bit. 3762 if (F.onlyReadsMemory()) 3763 State.addKnownBits(NOT_CAPTURED_IN_MEM); 3764 3765 // A function cannot communicate state back if it does not through 3766 // exceptions and doesn not return values. 3767 if (F.doesNotThrow() && F.getReturnType()->isVoidTy()) 3768 State.addKnownBits(NOT_CAPTURED_IN_RET); 3769 3770 // Check existing "returned" attributes. 3771 int ArgNo = IRP.getArgNo(); 3772 if (F.doesNotThrow() && ArgNo >= 0) { 3773 for (unsigned u = 0, e = F.arg_size(); u < e; ++u) 3774 if (F.hasParamAttribute(u, Attribute::Returned)) { 3775 if (u == unsigned(ArgNo)) 3776 State.removeAssumedBits(NOT_CAPTURED_IN_RET); 3777 else if (F.onlyReadsMemory()) 3778 State.addKnownBits(NO_CAPTURE); 3779 else 3780 State.addKnownBits(NOT_CAPTURED_IN_RET); 3781 break; 3782 } 3783 } 3784 } 3785 3786 /// See AbstractState::getAsStr(). 3787 const std::string getAsStr() const override { 3788 if (isKnownNoCapture()) 3789 return "known not-captured"; 3790 if (isAssumedNoCapture()) 3791 return "assumed not-captured"; 3792 if (isKnownNoCaptureMaybeReturned()) 3793 return "known not-captured-maybe-returned"; 3794 if (isAssumedNoCaptureMaybeReturned()) 3795 return "assumed not-captured-maybe-returned"; 3796 return "assumed-captured"; 3797 } 3798 }; 3799 3800 /// Attributor-aware capture tracker. 3801 struct AACaptureUseTracker final : public CaptureTracker { 3802 3803 /// Create a capture tracker that can lookup in-flight abstract attributes 3804 /// through the Attributor \p A. 3805 /// 3806 /// If a use leads to a potential capture, \p CapturedInMemory is set and the 3807 /// search is stopped. If a use leads to a return instruction, 3808 /// \p CommunicatedBack is set to true and \p CapturedInMemory is not changed. 3809 /// If a use leads to a ptr2int which may capture the value, 3810 /// \p CapturedInInteger is set. If a use is found that is currently assumed 3811 /// "no-capture-maybe-returned", the user is added to the \p PotentialCopies 3812 /// set. All values in \p PotentialCopies are later tracked as well. For every 3813 /// explored use we decrement \p RemainingUsesToExplore. Once it reaches 0, 3814 /// the search is stopped with \p CapturedInMemory and \p CapturedInInteger 3815 /// conservatively set to true. 3816 AACaptureUseTracker(Attributor &A, AANoCapture &NoCaptureAA, 3817 const AAIsDead &IsDeadAA, AANoCapture::StateType &State, 3818 SmallVectorImpl<const Value *> &PotentialCopies, 3819 unsigned &RemainingUsesToExplore) 3820 : A(A), NoCaptureAA(NoCaptureAA), IsDeadAA(IsDeadAA), State(State), 3821 PotentialCopies(PotentialCopies), 3822 RemainingUsesToExplore(RemainingUsesToExplore) {} 3823 3824 /// Determine if \p V maybe captured. *Also updates the state!* 3825 bool valueMayBeCaptured(const Value *V) { 3826 if (V->getType()->isPointerTy()) { 3827 PointerMayBeCaptured(V, this); 3828 } else { 3829 State.indicatePessimisticFixpoint(); 3830 } 3831 return State.isAssumed(AANoCapture::NO_CAPTURE_MAYBE_RETURNED); 3832 } 3833 3834 /// See CaptureTracker::tooManyUses(). 3835 void tooManyUses() override { 3836 State.removeAssumedBits(AANoCapture::NO_CAPTURE); 3837 } 3838 3839 bool isDereferenceableOrNull(Value *O, const DataLayout &DL) override { 3840 if (CaptureTracker::isDereferenceableOrNull(O, DL)) 3841 return true; 3842 const auto &DerefAA = 3843 A.getAAFor<AADereferenceable>(NoCaptureAA, IRPosition::value(*O)); 3844 return DerefAA.getAssumedDereferenceableBytes(); 3845 } 3846 3847 /// See CaptureTracker::captured(...). 3848 bool captured(const Use *U) override { 3849 Instruction *UInst = cast<Instruction>(U->getUser()); 3850 LLVM_DEBUG(dbgs() << "Check use: " << *U->get() << " in " << *UInst 3851 << "\n"); 3852 3853 // Because we may reuse the tracker multiple times we keep track of the 3854 // number of explored uses ourselves as well. 3855 if (RemainingUsesToExplore-- == 0) { 3856 LLVM_DEBUG(dbgs() << " - too many uses to explore!\n"); 3857 return isCapturedIn(/* Memory */ true, /* Integer */ true, 3858 /* Return */ true); 3859 } 3860 3861 // Deal with ptr2int by following uses. 3862 if (isa<PtrToIntInst>(UInst)) { 3863 LLVM_DEBUG(dbgs() << " - ptr2int assume the worst!\n"); 3864 return valueMayBeCaptured(UInst); 3865 } 3866 3867 // Explicitly catch return instructions. 3868 if (isa<ReturnInst>(UInst)) 3869 return isCapturedIn(/* Memory */ false, /* Integer */ false, 3870 /* Return */ true); 3871 3872 // For now we only use special logic for call sites. However, the tracker 3873 // itself knows about a lot of other non-capturing cases already. 3874 CallSite CS(UInst); 3875 if (!CS || !CS.isArgOperand(U)) 3876 return isCapturedIn(/* Memory */ true, /* Integer */ true, 3877 /* Return */ true); 3878 3879 unsigned ArgNo = CS.getArgumentNo(U); 3880 const IRPosition &CSArgPos = IRPosition::callsite_argument(CS, ArgNo); 3881 // If we have a abstract no-capture attribute for the argument we can use 3882 // it to justify a non-capture attribute here. This allows recursion! 3883 auto &ArgNoCaptureAA = A.getAAFor<AANoCapture>(NoCaptureAA, CSArgPos); 3884 if (ArgNoCaptureAA.isAssumedNoCapture()) 3885 return isCapturedIn(/* Memory */ false, /* Integer */ false, 3886 /* Return */ false); 3887 if (ArgNoCaptureAA.isAssumedNoCaptureMaybeReturned()) { 3888 addPotentialCopy(CS); 3889 return isCapturedIn(/* Memory */ false, /* Integer */ false, 3890 /* Return */ false); 3891 } 3892 3893 // Lastly, we could not find a reason no-capture can be assumed so we don't. 3894 return isCapturedIn(/* Memory */ true, /* Integer */ true, 3895 /* Return */ true); 3896 } 3897 3898 /// Register \p CS as potential copy of the value we are checking. 3899 void addPotentialCopy(CallSite CS) { 3900 PotentialCopies.push_back(CS.getInstruction()); 3901 } 3902 3903 /// See CaptureTracker::shouldExplore(...). 3904 bool shouldExplore(const Use *U) override { 3905 // Check liveness. 3906 return !IsDeadAA.isAssumedDead(cast<Instruction>(U->getUser())); 3907 } 3908 3909 /// Update the state according to \p CapturedInMem, \p CapturedInInt, and 3910 /// \p CapturedInRet, then return the appropriate value for use in the 3911 /// CaptureTracker::captured() interface. 3912 bool isCapturedIn(bool CapturedInMem, bool CapturedInInt, 3913 bool CapturedInRet) { 3914 LLVM_DEBUG(dbgs() << " - captures [Mem " << CapturedInMem << "|Int " 3915 << CapturedInInt << "|Ret " << CapturedInRet << "]\n"); 3916 if (CapturedInMem) 3917 State.removeAssumedBits(AANoCapture::NOT_CAPTURED_IN_MEM); 3918 if (CapturedInInt) 3919 State.removeAssumedBits(AANoCapture::NOT_CAPTURED_IN_INT); 3920 if (CapturedInRet) 3921 State.removeAssumedBits(AANoCapture::NOT_CAPTURED_IN_RET); 3922 return !State.isAssumed(AANoCapture::NO_CAPTURE_MAYBE_RETURNED); 3923 } 3924 3925 private: 3926 /// The attributor providing in-flight abstract attributes. 3927 Attributor &A; 3928 3929 /// The abstract attribute currently updated. 3930 AANoCapture &NoCaptureAA; 3931 3932 /// The abstract liveness state. 3933 const AAIsDead &IsDeadAA; 3934 3935 /// The state currently updated. 3936 AANoCapture::StateType &State; 3937 3938 /// Set of potential copies of the tracked value. 3939 SmallVectorImpl<const Value *> &PotentialCopies; 3940 3941 /// Global counter to limit the number of explored uses. 3942 unsigned &RemainingUsesToExplore; 3943 }; 3944 3945 ChangeStatus AANoCaptureImpl::updateImpl(Attributor &A) { 3946 const IRPosition &IRP = getIRPosition(); 3947 const Value *V = 3948 getArgNo() >= 0 ? IRP.getAssociatedArgument() : &IRP.getAssociatedValue(); 3949 if (!V) 3950 return indicatePessimisticFixpoint(); 3951 3952 const Function *F = 3953 getArgNo() >= 0 ? IRP.getAssociatedFunction() : IRP.getAnchorScope(); 3954 assert(F && "Expected a function!"); 3955 const IRPosition &FnPos = IRPosition::function(*F); 3956 const auto &IsDeadAA = A.getAAFor<AAIsDead>(*this, FnPos); 3957 3958 AANoCapture::StateType T; 3959 3960 // Readonly means we cannot capture through memory. 3961 const auto &FnMemAA = A.getAAFor<AAMemoryBehavior>(*this, FnPos); 3962 if (FnMemAA.isAssumedReadOnly()) { 3963 T.addKnownBits(NOT_CAPTURED_IN_MEM); 3964 if (FnMemAA.isKnownReadOnly()) 3965 addKnownBits(NOT_CAPTURED_IN_MEM); 3966 } 3967 3968 // Make sure all returned values are different than the underlying value. 3969 // TODO: we could do this in a more sophisticated way inside 3970 // AAReturnedValues, e.g., track all values that escape through returns 3971 // directly somehow. 3972 auto CheckReturnedArgs = [&](const AAReturnedValues &RVAA) { 3973 bool SeenConstant = false; 3974 for (auto &It : RVAA.returned_values()) { 3975 if (isa<Constant>(It.first)) { 3976 if (SeenConstant) 3977 return false; 3978 SeenConstant = true; 3979 } else if (!isa<Argument>(It.first) || 3980 It.first == getAssociatedArgument()) 3981 return false; 3982 } 3983 return true; 3984 }; 3985 3986 const auto &NoUnwindAA = A.getAAFor<AANoUnwind>(*this, FnPos); 3987 if (NoUnwindAA.isAssumedNoUnwind()) { 3988 bool IsVoidTy = F->getReturnType()->isVoidTy(); 3989 const AAReturnedValues *RVAA = 3990 IsVoidTy ? nullptr : &A.getAAFor<AAReturnedValues>(*this, FnPos); 3991 if (IsVoidTy || CheckReturnedArgs(*RVAA)) { 3992 T.addKnownBits(NOT_CAPTURED_IN_RET); 3993 if (T.isKnown(NOT_CAPTURED_IN_MEM)) 3994 return ChangeStatus::UNCHANGED; 3995 if (NoUnwindAA.isKnownNoUnwind() && 3996 (IsVoidTy || RVAA->getState().isAtFixpoint())) { 3997 addKnownBits(NOT_CAPTURED_IN_RET); 3998 if (isKnown(NOT_CAPTURED_IN_MEM)) 3999 return indicateOptimisticFixpoint(); 4000 } 4001 } 4002 } 4003 4004 // Use the CaptureTracker interface and logic with the specialized tracker, 4005 // defined in AACaptureUseTracker, that can look at in-flight abstract 4006 // attributes and directly updates the assumed state. 4007 SmallVector<const Value *, 4> PotentialCopies; 4008 unsigned RemainingUsesToExplore = DefaultMaxUsesToExplore; 4009 AACaptureUseTracker Tracker(A, *this, IsDeadAA, T, PotentialCopies, 4010 RemainingUsesToExplore); 4011 4012 // Check all potential copies of the associated value until we can assume 4013 // none will be captured or we have to assume at least one might be. 4014 unsigned Idx = 0; 4015 PotentialCopies.push_back(V); 4016 while (T.isAssumed(NO_CAPTURE_MAYBE_RETURNED) && Idx < PotentialCopies.size()) 4017 Tracker.valueMayBeCaptured(PotentialCopies[Idx++]); 4018 4019 AANoCapture::StateType &S = getState(); 4020 auto Assumed = S.getAssumed(); 4021 S.intersectAssumedBits(T.getAssumed()); 4022 if (!isAssumedNoCaptureMaybeReturned()) 4023 return indicatePessimisticFixpoint(); 4024 return Assumed == S.getAssumed() ? ChangeStatus::UNCHANGED 4025 : ChangeStatus::CHANGED; 4026 } 4027 4028 /// NoCapture attribute for function arguments. 4029 struct AANoCaptureArgument final : AANoCaptureImpl { 4030 AANoCaptureArgument(const IRPosition &IRP) : AANoCaptureImpl(IRP) {} 4031 4032 /// See AbstractAttribute::trackStatistics() 4033 void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nocapture) } 4034 }; 4035 4036 /// NoCapture attribute for call site arguments. 4037 struct AANoCaptureCallSiteArgument final : AANoCaptureImpl { 4038 AANoCaptureCallSiteArgument(const IRPosition &IRP) : AANoCaptureImpl(IRP) {} 4039 4040 /// See AbstractAttribute::initialize(...). 4041 void initialize(Attributor &A) override { 4042 if (Argument *Arg = getAssociatedArgument()) 4043 if (Arg->hasByValAttr()) 4044 indicateOptimisticFixpoint(); 4045 AANoCaptureImpl::initialize(A); 4046 } 4047 4048 /// See AbstractAttribute::updateImpl(...). 4049 ChangeStatus updateImpl(Attributor &A) override { 4050 // TODO: Once we have call site specific value information we can provide 4051 // call site specific liveness information and then it makes 4052 // sense to specialize attributes for call sites arguments instead of 4053 // redirecting requests to the callee argument. 4054 Argument *Arg = getAssociatedArgument(); 4055 if (!Arg) 4056 return indicatePessimisticFixpoint(); 4057 const IRPosition &ArgPos = IRPosition::argument(*Arg); 4058 auto &ArgAA = A.getAAFor<AANoCapture>(*this, ArgPos); 4059 return clampStateAndIndicateChange( 4060 getState(), 4061 static_cast<const AANoCapture::StateType &>(ArgAA.getState())); 4062 } 4063 4064 /// See AbstractAttribute::trackStatistics() 4065 void trackStatistics() const override{STATS_DECLTRACK_CSARG_ATTR(nocapture)}; 4066 }; 4067 4068 /// NoCapture attribute for floating values. 4069 struct AANoCaptureFloating final : AANoCaptureImpl { 4070 AANoCaptureFloating(const IRPosition &IRP) : AANoCaptureImpl(IRP) {} 4071 4072 /// See AbstractAttribute::trackStatistics() 4073 void trackStatistics() const override { 4074 STATS_DECLTRACK_FLOATING_ATTR(nocapture) 4075 } 4076 }; 4077 4078 /// NoCapture attribute for function return value. 4079 struct AANoCaptureReturned final : AANoCaptureImpl { 4080 AANoCaptureReturned(const IRPosition &IRP) : AANoCaptureImpl(IRP) { 4081 llvm_unreachable("NoCapture is not applicable to function returns!"); 4082 } 4083 4084 /// See AbstractAttribute::initialize(...). 4085 void initialize(Attributor &A) override { 4086 llvm_unreachable("NoCapture is not applicable to function returns!"); 4087 } 4088 4089 /// See AbstractAttribute::updateImpl(...). 4090 ChangeStatus updateImpl(Attributor &A) override { 4091 llvm_unreachable("NoCapture is not applicable to function returns!"); 4092 } 4093 4094 /// See AbstractAttribute::trackStatistics() 4095 void trackStatistics() const override {} 4096 }; 4097 4098 /// NoCapture attribute deduction for a call site return value. 4099 struct AANoCaptureCallSiteReturned final : AANoCaptureImpl { 4100 AANoCaptureCallSiteReturned(const IRPosition &IRP) : AANoCaptureImpl(IRP) {} 4101 4102 /// See AbstractAttribute::trackStatistics() 4103 void trackStatistics() const override { 4104 STATS_DECLTRACK_CSRET_ATTR(nocapture) 4105 } 4106 }; 4107 4108 /// ------------------ Value Simplify Attribute ---------------------------- 4109 struct AAValueSimplifyImpl : AAValueSimplify { 4110 AAValueSimplifyImpl(const IRPosition &IRP) : AAValueSimplify(IRP) {} 4111 4112 /// See AbstractAttribute::getAsStr(). 4113 const std::string getAsStr() const override { 4114 return getAssumed() ? (getKnown() ? "simplified" : "maybe-simple") 4115 : "not-simple"; 4116 } 4117 4118 /// See AbstractAttribute::trackStatistics() 4119 void trackStatistics() const override {} 4120 4121 /// See AAValueSimplify::getAssumedSimplifiedValue() 4122 Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const override { 4123 if (!getAssumed()) 4124 return const_cast<Value *>(&getAssociatedValue()); 4125 return SimplifiedAssociatedValue; 4126 } 4127 void initialize(Attributor &A) override {} 4128 4129 /// Helper function for querying AAValueSimplify and updating candicate. 4130 /// \param QueryingValue Value trying to unify with SimplifiedValue 4131 /// \param AccumulatedSimplifiedValue Current simplification result. 4132 static bool checkAndUpdate(Attributor &A, const AbstractAttribute &QueryingAA, 4133 Value &QueryingValue, 4134 Optional<Value *> &AccumulatedSimplifiedValue) { 4135 // FIXME: Add a typecast support. 4136 4137 auto &ValueSimpifyAA = A.getAAFor<AAValueSimplify>( 4138 QueryingAA, IRPosition::value(QueryingValue)); 4139 4140 Optional<Value *> QueryingValueSimplified = 4141 ValueSimpifyAA.getAssumedSimplifiedValue(A); 4142 4143 if (!QueryingValueSimplified.hasValue()) 4144 return true; 4145 4146 if (!QueryingValueSimplified.getValue()) 4147 return false; 4148 4149 Value &QueryingValueSimplifiedUnwrapped = 4150 *QueryingValueSimplified.getValue(); 4151 4152 if (isa<UndefValue>(QueryingValueSimplifiedUnwrapped)) 4153 return true; 4154 4155 if (AccumulatedSimplifiedValue.hasValue()) 4156 return AccumulatedSimplifiedValue == QueryingValueSimplified; 4157 4158 LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << QueryingValue 4159 << " is assumed to be " 4160 << QueryingValueSimplifiedUnwrapped << "\n"); 4161 4162 AccumulatedSimplifiedValue = QueryingValueSimplified; 4163 return true; 4164 } 4165 4166 bool askSimplifiedValueForAAValueConstantRange(Attributor &A) { 4167 if (!getAssociatedValue().getType()->isIntegerTy()) 4168 return false; 4169 4170 const auto &ValueConstantRangeAA = 4171 A.getAAFor<AAValueConstantRange>(*this, getIRPosition()); 4172 4173 Optional<ConstantInt *> COpt = 4174 ValueConstantRangeAA.getAssumedConstantInt(A); 4175 if (COpt.hasValue()) { 4176 if (auto *C = COpt.getValue()) 4177 SimplifiedAssociatedValue = C; 4178 else 4179 return false; 4180 } else { 4181 // FIXME: It should be llvm::None but if you set llvm::None, 4182 // values are mistakenly infered as `undef` now. 4183 SimplifiedAssociatedValue = &getAssociatedValue(); 4184 } 4185 return true; 4186 } 4187 4188 /// See AbstractAttribute::manifest(...). 4189 ChangeStatus manifest(Attributor &A) override { 4190 ChangeStatus Changed = ChangeStatus::UNCHANGED; 4191 4192 if (!SimplifiedAssociatedValue.hasValue() || 4193 !SimplifiedAssociatedValue.getValue()) 4194 return Changed; 4195 4196 if (auto *C = dyn_cast<Constant>(SimplifiedAssociatedValue.getValue())) { 4197 // We can replace the AssociatedValue with the constant. 4198 Value &V = getAssociatedValue(); 4199 if (!V.user_empty() && &V != C && V.getType() == C->getType()) { 4200 LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << V << " -> " << *C 4201 << "\n"); 4202 A.changeValueAfterManifest(V, *C); 4203 Changed = ChangeStatus::CHANGED; 4204 } 4205 } 4206 4207 return Changed | AAValueSimplify::manifest(A); 4208 } 4209 4210 /// See AbstractState::indicatePessimisticFixpoint(...). 4211 ChangeStatus indicatePessimisticFixpoint() override { 4212 // NOTE: Associated value will be returned in a pessimistic fixpoint and is 4213 // regarded as known. That's why`indicateOptimisticFixpoint` is called. 4214 SimplifiedAssociatedValue = &getAssociatedValue(); 4215 indicateOptimisticFixpoint(); 4216 return ChangeStatus::CHANGED; 4217 } 4218 4219 protected: 4220 // An assumed simplified value. Initially, it is set to Optional::None, which 4221 // means that the value is not clear under current assumption. If in the 4222 // pessimistic state, getAssumedSimplifiedValue doesn't return this value but 4223 // returns orignal associated value. 4224 Optional<Value *> SimplifiedAssociatedValue; 4225 }; 4226 4227 struct AAValueSimplifyArgument final : AAValueSimplifyImpl { 4228 AAValueSimplifyArgument(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {} 4229 4230 void initialize(Attributor &A) override { 4231 AAValueSimplifyImpl::initialize(A); 4232 if (!getAssociatedFunction() || getAssociatedFunction()->isDeclaration()) 4233 indicatePessimisticFixpoint(); 4234 if (hasAttr({Attribute::InAlloca, Attribute::StructRet, Attribute::Nest}, 4235 /* IgnoreSubsumingPositions */ true)) 4236 indicatePessimisticFixpoint(); 4237 } 4238 4239 /// See AbstractAttribute::updateImpl(...). 4240 ChangeStatus updateImpl(Attributor &A) override { 4241 // Byval is only replacable if it is readonly otherwise we would write into 4242 // the replaced value and not the copy that byval creates implicitly. 4243 Argument *Arg = getAssociatedArgument(); 4244 if (Arg->hasByValAttr()) { 4245 const auto &MemAA = A.getAAFor<AAMemoryBehavior>(*this, getIRPosition()); 4246 if (!MemAA.isAssumedReadOnly()) 4247 return indicatePessimisticFixpoint(); 4248 } 4249 4250 bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); 4251 4252 auto PredForCallSite = [&](AbstractCallSite ACS) { 4253 // Check if we have an associated argument or not (which can happen for 4254 // callback calls). 4255 Value *ArgOp = ACS.getCallArgOperand(getArgNo()); 4256 if (!ArgOp) 4257 return false; 4258 // We can only propagate thread independent values through callbacks. 4259 // This is different to direct/indirect call sites because for them we 4260 // know the thread executing the caller and callee is the same. For 4261 // callbacks this is not guaranteed, thus a thread dependent value could 4262 // be different for the caller and callee, making it invalid to propagate. 4263 if (ACS.isCallbackCall()) 4264 if (auto *C = dyn_cast<Constant>(ArgOp)) 4265 if (C->isThreadDependent()) 4266 return false; 4267 return checkAndUpdate(A, *this, *ArgOp, SimplifiedAssociatedValue); 4268 }; 4269 4270 if (!A.checkForAllCallSites(PredForCallSite, *this, true)) 4271 if (!askSimplifiedValueForAAValueConstantRange(A)) 4272 return indicatePessimisticFixpoint(); 4273 4274 // If a candicate was found in this update, return CHANGED. 4275 return HasValueBefore == SimplifiedAssociatedValue.hasValue() 4276 ? ChangeStatus::UNCHANGED 4277 : ChangeStatus ::CHANGED; 4278 } 4279 4280 /// See AbstractAttribute::trackStatistics() 4281 void trackStatistics() const override { 4282 STATS_DECLTRACK_ARG_ATTR(value_simplify) 4283 } 4284 }; 4285 4286 struct AAValueSimplifyReturned : AAValueSimplifyImpl { 4287 AAValueSimplifyReturned(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {} 4288 4289 /// See AbstractAttribute::updateImpl(...). 4290 ChangeStatus updateImpl(Attributor &A) override { 4291 bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); 4292 4293 auto PredForReturned = [&](Value &V) { 4294 return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue); 4295 }; 4296 4297 if (!A.checkForAllReturnedValues(PredForReturned, *this)) 4298 if (!askSimplifiedValueForAAValueConstantRange(A)) 4299 return indicatePessimisticFixpoint(); 4300 4301 // If a candicate was found in this update, return CHANGED. 4302 return HasValueBefore == SimplifiedAssociatedValue.hasValue() 4303 ? ChangeStatus::UNCHANGED 4304 : ChangeStatus ::CHANGED; 4305 } 4306 /// See AbstractAttribute::trackStatistics() 4307 void trackStatistics() const override { 4308 STATS_DECLTRACK_FNRET_ATTR(value_simplify) 4309 } 4310 }; 4311 4312 struct AAValueSimplifyFloating : AAValueSimplifyImpl { 4313 AAValueSimplifyFloating(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {} 4314 4315 /// See AbstractAttribute::initialize(...). 4316 void initialize(Attributor &A) override { 4317 Value &V = getAnchorValue(); 4318 4319 // TODO: add other stuffs 4320 if (isa<Constant>(V)) 4321 indicatePessimisticFixpoint(); 4322 } 4323 4324 /// See AbstractAttribute::updateImpl(...). 4325 ChangeStatus updateImpl(Attributor &A) override { 4326 bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); 4327 4328 auto VisitValueCB = [&](Value &V, BooleanState, bool Stripped) -> bool { 4329 auto &AA = A.getAAFor<AAValueSimplify>(*this, IRPosition::value(V)); 4330 if (!Stripped && this == &AA) { 4331 // TODO: Look the instruction and check recursively. 4332 4333 LLVM_DEBUG( 4334 dbgs() << "[Attributor][ValueSimplify] Can't be stripped more : " 4335 << V << "\n"); 4336 return false; 4337 } 4338 return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue); 4339 }; 4340 4341 if (!genericValueTraversal<AAValueSimplify, BooleanState>( 4342 A, getIRPosition(), *this, static_cast<BooleanState &>(*this), 4343 VisitValueCB)) 4344 if (!askSimplifiedValueForAAValueConstantRange(A)) 4345 return indicatePessimisticFixpoint(); 4346 4347 // If a candicate was found in this update, return CHANGED. 4348 4349 return HasValueBefore == SimplifiedAssociatedValue.hasValue() 4350 ? ChangeStatus::UNCHANGED 4351 : ChangeStatus ::CHANGED; 4352 } 4353 4354 /// See AbstractAttribute::trackStatistics() 4355 void trackStatistics() const override { 4356 STATS_DECLTRACK_FLOATING_ATTR(value_simplify) 4357 } 4358 }; 4359 4360 struct AAValueSimplifyFunction : AAValueSimplifyImpl { 4361 AAValueSimplifyFunction(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {} 4362 4363 /// See AbstractAttribute::initialize(...). 4364 void initialize(Attributor &A) override { 4365 SimplifiedAssociatedValue = &getAnchorValue(); 4366 indicateOptimisticFixpoint(); 4367 } 4368 /// See AbstractAttribute::initialize(...). 4369 ChangeStatus updateImpl(Attributor &A) override { 4370 llvm_unreachable( 4371 "AAValueSimplify(Function|CallSite)::updateImpl will not be called"); 4372 } 4373 /// See AbstractAttribute::trackStatistics() 4374 void trackStatistics() const override { 4375 STATS_DECLTRACK_FN_ATTR(value_simplify) 4376 } 4377 }; 4378 4379 struct AAValueSimplifyCallSite : AAValueSimplifyFunction { 4380 AAValueSimplifyCallSite(const IRPosition &IRP) 4381 : AAValueSimplifyFunction(IRP) {} 4382 /// See AbstractAttribute::trackStatistics() 4383 void trackStatistics() const override { 4384 STATS_DECLTRACK_CS_ATTR(value_simplify) 4385 } 4386 }; 4387 4388 struct AAValueSimplifyCallSiteReturned : AAValueSimplifyReturned { 4389 AAValueSimplifyCallSiteReturned(const IRPosition &IRP) 4390 : AAValueSimplifyReturned(IRP) {} 4391 4392 void trackStatistics() const override { 4393 STATS_DECLTRACK_CSRET_ATTR(value_simplify) 4394 } 4395 }; 4396 struct AAValueSimplifyCallSiteArgument : AAValueSimplifyFloating { 4397 AAValueSimplifyCallSiteArgument(const IRPosition &IRP) 4398 : AAValueSimplifyFloating(IRP) {} 4399 4400 void trackStatistics() const override { 4401 STATS_DECLTRACK_CSARG_ATTR(value_simplify) 4402 } 4403 }; 4404 4405 /// ----------------------- Heap-To-Stack Conversion --------------------------- 4406 struct AAHeapToStackImpl : public AAHeapToStack { 4407 AAHeapToStackImpl(const IRPosition &IRP) : AAHeapToStack(IRP) {} 4408 4409 const std::string getAsStr() const override { 4410 return "[H2S] Mallocs: " + std::to_string(MallocCalls.size()); 4411 } 4412 4413 ChangeStatus manifest(Attributor &A) override { 4414 assert(getState().isValidState() && 4415 "Attempted to manifest an invalid state!"); 4416 4417 ChangeStatus HasChanged = ChangeStatus::UNCHANGED; 4418 Function *F = getAssociatedFunction(); 4419 const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(*F); 4420 4421 for (Instruction *MallocCall : MallocCalls) { 4422 // This malloc cannot be replaced. 4423 if (BadMallocCalls.count(MallocCall)) 4424 continue; 4425 4426 for (Instruction *FreeCall : FreesForMalloc[MallocCall]) { 4427 LLVM_DEBUG(dbgs() << "H2S: Removing free call: " << *FreeCall << "\n"); 4428 A.deleteAfterManifest(*FreeCall); 4429 HasChanged = ChangeStatus::CHANGED; 4430 } 4431 4432 LLVM_DEBUG(dbgs() << "H2S: Removing malloc call: " << *MallocCall 4433 << "\n"); 4434 4435 Constant *Size; 4436 if (isCallocLikeFn(MallocCall, TLI)) { 4437 auto *Num = cast<ConstantInt>(MallocCall->getOperand(0)); 4438 auto *SizeT = dyn_cast<ConstantInt>(MallocCall->getOperand(1)); 4439 APInt TotalSize = SizeT->getValue() * Num->getValue(); 4440 Size = 4441 ConstantInt::get(MallocCall->getOperand(0)->getType(), TotalSize); 4442 } else { 4443 Size = cast<ConstantInt>(MallocCall->getOperand(0)); 4444 } 4445 4446 unsigned AS = cast<PointerType>(MallocCall->getType())->getAddressSpace(); 4447 Instruction *AI = new AllocaInst(Type::getInt8Ty(F->getContext()), AS, 4448 Size, "", MallocCall->getNextNode()); 4449 4450 if (AI->getType() != MallocCall->getType()) 4451 AI = new BitCastInst(AI, MallocCall->getType(), "malloc_bc", 4452 AI->getNextNode()); 4453 4454 replaceAllInstructionUsesWith(*MallocCall, *AI); 4455 4456 if (auto *II = dyn_cast<InvokeInst>(MallocCall)) { 4457 auto *NBB = II->getNormalDest(); 4458 BranchInst::Create(NBB, MallocCall->getParent()); 4459 A.deleteAfterManifest(*MallocCall); 4460 } else { 4461 A.deleteAfterManifest(*MallocCall); 4462 } 4463 4464 if (isCallocLikeFn(MallocCall, TLI)) { 4465 auto *BI = new BitCastInst(AI, MallocCall->getType(), "calloc_bc", 4466 AI->getNextNode()); 4467 Value *Ops[] = { 4468 BI, ConstantInt::get(F->getContext(), APInt(8, 0, false)), Size, 4469 ConstantInt::get(Type::getInt1Ty(F->getContext()), false)}; 4470 4471 Type *Tys[] = {BI->getType(), MallocCall->getOperand(0)->getType()}; 4472 Module *M = F->getParent(); 4473 Function *Fn = Intrinsic::getDeclaration(M, Intrinsic::memset, Tys); 4474 CallInst::Create(Fn, Ops, "", BI->getNextNode()); 4475 } 4476 HasChanged = ChangeStatus::CHANGED; 4477 } 4478 4479 return HasChanged; 4480 } 4481 4482 /// Collection of all malloc calls in a function. 4483 SmallSetVector<Instruction *, 4> MallocCalls; 4484 4485 /// Collection of malloc calls that cannot be converted. 4486 DenseSet<const Instruction *> BadMallocCalls; 4487 4488 /// A map for each malloc call to the set of associated free calls. 4489 DenseMap<Instruction *, SmallPtrSet<Instruction *, 4>> FreesForMalloc; 4490 4491 ChangeStatus updateImpl(Attributor &A) override; 4492 }; 4493 4494 ChangeStatus AAHeapToStackImpl::updateImpl(Attributor &A) { 4495 const Function *F = getAssociatedFunction(); 4496 const auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(*F); 4497 4498 MustBeExecutedContextExplorer &Explorer = 4499 A.getInfoCache().getMustBeExecutedContextExplorer(); 4500 4501 auto FreeCheck = [&](Instruction &I) { 4502 const auto &Frees = FreesForMalloc.lookup(&I); 4503 if (Frees.size() != 1) 4504 return false; 4505 Instruction *UniqueFree = *Frees.begin(); 4506 return Explorer.findInContextOf(UniqueFree, I.getNextNode()); 4507 }; 4508 4509 auto UsesCheck = [&](Instruction &I) { 4510 bool ValidUsesOnly = true; 4511 bool MustUse = true; 4512 auto Pred = [&](const Use &U, bool &Follow) -> bool { 4513 Instruction *UserI = cast<Instruction>(U.getUser()); 4514 if (isa<LoadInst>(UserI)) 4515 return true; 4516 if (auto *SI = dyn_cast<StoreInst>(UserI)) { 4517 if (SI->getValueOperand() == U.get()) { 4518 LLVM_DEBUG(dbgs() 4519 << "[H2S] escaping store to memory: " << *UserI << "\n"); 4520 ValidUsesOnly = false; 4521 } else { 4522 // A store into the malloc'ed memory is fine. 4523 } 4524 return true; 4525 } 4526 if (auto *CB = dyn_cast<CallBase>(UserI)) { 4527 if (!CB->isArgOperand(&U) || CB->isLifetimeStartOrEnd()) 4528 return true; 4529 // Record malloc. 4530 if (isFreeCall(UserI, TLI)) { 4531 if (MustUse) { 4532 FreesForMalloc[&I].insert(UserI); 4533 } else { 4534 LLVM_DEBUG(dbgs() << "[H2S] free potentially on different mallocs: " 4535 << *UserI << "\n"); 4536 ValidUsesOnly = false; 4537 } 4538 return true; 4539 } 4540 4541 unsigned ArgNo = CB->getArgOperandNo(&U); 4542 4543 const auto &NoCaptureAA = A.getAAFor<AANoCapture>( 4544 *this, IRPosition::callsite_argument(*CB, ArgNo)); 4545 4546 // If a callsite argument use is nofree, we are fine. 4547 const auto &ArgNoFreeAA = A.getAAFor<AANoFree>( 4548 *this, IRPosition::callsite_argument(*CB, ArgNo)); 4549 4550 if (!NoCaptureAA.isAssumedNoCapture() || 4551 !ArgNoFreeAA.isAssumedNoFree()) { 4552 LLVM_DEBUG(dbgs() << "[H2S] Bad user: " << *UserI << "\n"); 4553 ValidUsesOnly = false; 4554 } 4555 return true; 4556 } 4557 4558 if (isa<GetElementPtrInst>(UserI) || isa<BitCastInst>(UserI) || 4559 isa<PHINode>(UserI) || isa<SelectInst>(UserI)) { 4560 MustUse &= !(isa<PHINode>(UserI) || isa<SelectInst>(UserI)); 4561 Follow = true; 4562 return true; 4563 } 4564 // Unknown user for which we can not track uses further (in a way that 4565 // makes sense). 4566 LLVM_DEBUG(dbgs() << "[H2S] Unknown user: " << *UserI << "\n"); 4567 ValidUsesOnly = false; 4568 return true; 4569 }; 4570 A.checkForAllUses(Pred, *this, I); 4571 return ValidUsesOnly; 4572 }; 4573 4574 auto MallocCallocCheck = [&](Instruction &I) { 4575 if (BadMallocCalls.count(&I)) 4576 return true; 4577 4578 bool IsMalloc = isMallocLikeFn(&I, TLI); 4579 bool IsCalloc = !IsMalloc && isCallocLikeFn(&I, TLI); 4580 if (!IsMalloc && !IsCalloc) { 4581 BadMallocCalls.insert(&I); 4582 return true; 4583 } 4584 4585 if (IsMalloc) { 4586 if (auto *Size = dyn_cast<ConstantInt>(I.getOperand(0))) 4587 if (Size->getValue().ule(MaxHeapToStackSize)) 4588 if (UsesCheck(I) || FreeCheck(I)) { 4589 MallocCalls.insert(&I); 4590 return true; 4591 } 4592 } else if (IsCalloc) { 4593 bool Overflow = false; 4594 if (auto *Num = dyn_cast<ConstantInt>(I.getOperand(0))) 4595 if (auto *Size = dyn_cast<ConstantInt>(I.getOperand(1))) 4596 if ((Size->getValue().umul_ov(Num->getValue(), Overflow)) 4597 .ule(MaxHeapToStackSize)) 4598 if (!Overflow && (UsesCheck(I) || FreeCheck(I))) { 4599 MallocCalls.insert(&I); 4600 return true; 4601 } 4602 } 4603 4604 BadMallocCalls.insert(&I); 4605 return true; 4606 }; 4607 4608 size_t NumBadMallocs = BadMallocCalls.size(); 4609 4610 A.checkForAllCallLikeInstructions(MallocCallocCheck, *this); 4611 4612 if (NumBadMallocs != BadMallocCalls.size()) 4613 return ChangeStatus::CHANGED; 4614 4615 return ChangeStatus::UNCHANGED; 4616 } 4617 4618 struct AAHeapToStackFunction final : public AAHeapToStackImpl { 4619 AAHeapToStackFunction(const IRPosition &IRP) : AAHeapToStackImpl(IRP) {} 4620 4621 /// See AbstractAttribute::trackStatistics() 4622 void trackStatistics() const override { 4623 STATS_DECL(MallocCalls, Function, 4624 "Number of malloc calls converted to allocas"); 4625 for (auto *C : MallocCalls) 4626 if (!BadMallocCalls.count(C)) 4627 ++BUILD_STAT_NAME(MallocCalls, Function); 4628 } 4629 }; 4630 4631 /// -------------------- Memory Behavior Attributes ---------------------------- 4632 /// Includes read-none, read-only, and write-only. 4633 /// ---------------------------------------------------------------------------- 4634 struct AAMemoryBehaviorImpl : public AAMemoryBehavior { 4635 AAMemoryBehaviorImpl(const IRPosition &IRP) : AAMemoryBehavior(IRP) {} 4636 4637 /// See AbstractAttribute::initialize(...). 4638 void initialize(Attributor &A) override { 4639 intersectAssumedBits(BEST_STATE); 4640 getKnownStateFromValue(getIRPosition(), getState()); 4641 IRAttribute::initialize(A); 4642 } 4643 4644 /// Return the memory behavior information encoded in the IR for \p IRP. 4645 static void getKnownStateFromValue(const IRPosition &IRP, 4646 BitIntegerState &State, 4647 bool IgnoreSubsumingPositions = false) { 4648 SmallVector<Attribute, 2> Attrs; 4649 IRP.getAttrs(AttrKinds, Attrs, IgnoreSubsumingPositions); 4650 for (const Attribute &Attr : Attrs) { 4651 switch (Attr.getKindAsEnum()) { 4652 case Attribute::ReadNone: 4653 State.addKnownBits(NO_ACCESSES); 4654 break; 4655 case Attribute::ReadOnly: 4656 State.addKnownBits(NO_WRITES); 4657 break; 4658 case Attribute::WriteOnly: 4659 State.addKnownBits(NO_READS); 4660 break; 4661 default: 4662 llvm_unreachable("Unexpcted attribute!"); 4663 } 4664 } 4665 4666 if (auto *I = dyn_cast<Instruction>(&IRP.getAnchorValue())) { 4667 if (!I->mayReadFromMemory()) 4668 State.addKnownBits(NO_READS); 4669 if (!I->mayWriteToMemory()) 4670 State.addKnownBits(NO_WRITES); 4671 } 4672 } 4673 4674 /// See AbstractAttribute::getDeducedAttributes(...). 4675 void getDeducedAttributes(LLVMContext &Ctx, 4676 SmallVectorImpl<Attribute> &Attrs) const override { 4677 assert(Attrs.size() == 0); 4678 if (isAssumedReadNone()) 4679 Attrs.push_back(Attribute::get(Ctx, Attribute::ReadNone)); 4680 else if (isAssumedReadOnly()) 4681 Attrs.push_back(Attribute::get(Ctx, Attribute::ReadOnly)); 4682 else if (isAssumedWriteOnly()) 4683 Attrs.push_back(Attribute::get(Ctx, Attribute::WriteOnly)); 4684 assert(Attrs.size() <= 1); 4685 } 4686 4687 /// See AbstractAttribute::manifest(...). 4688 ChangeStatus manifest(Attributor &A) override { 4689 const IRPosition &IRP = getIRPosition(); 4690 4691 // Check if we would improve the existing attributes first. 4692 SmallVector<Attribute, 4> DeducedAttrs; 4693 getDeducedAttributes(IRP.getAnchorValue().getContext(), DeducedAttrs); 4694 if (llvm::all_of(DeducedAttrs, [&](const Attribute &Attr) { 4695 return IRP.hasAttr(Attr.getKindAsEnum(), 4696 /* IgnoreSubsumingPositions */ true); 4697 })) 4698 return ChangeStatus::UNCHANGED; 4699 4700 // Clear existing attributes. 4701 IRP.removeAttrs(AttrKinds); 4702 4703 // Use the generic manifest method. 4704 return IRAttribute::manifest(A); 4705 } 4706 4707 /// See AbstractState::getAsStr(). 4708 const std::string getAsStr() const override { 4709 if (isAssumedReadNone()) 4710 return "readnone"; 4711 if (isAssumedReadOnly()) 4712 return "readonly"; 4713 if (isAssumedWriteOnly()) 4714 return "writeonly"; 4715 return "may-read/write"; 4716 } 4717 4718 /// The set of IR attributes AAMemoryBehavior deals with. 4719 static const Attribute::AttrKind AttrKinds[3]; 4720 }; 4721 4722 const Attribute::AttrKind AAMemoryBehaviorImpl::AttrKinds[] = { 4723 Attribute::ReadNone, Attribute::ReadOnly, Attribute::WriteOnly}; 4724 4725 /// Memory behavior attribute for a floating value. 4726 struct AAMemoryBehaviorFloating : AAMemoryBehaviorImpl { 4727 AAMemoryBehaviorFloating(const IRPosition &IRP) : AAMemoryBehaviorImpl(IRP) {} 4728 4729 /// See AbstractAttribute::initialize(...). 4730 void initialize(Attributor &A) override { 4731 AAMemoryBehaviorImpl::initialize(A); 4732 // Initialize the use vector with all direct uses of the associated value. 4733 for (const Use &U : getAssociatedValue().uses()) 4734 Uses.insert(&U); 4735 } 4736 4737 /// See AbstractAttribute::updateImpl(...). 4738 ChangeStatus updateImpl(Attributor &A) override; 4739 4740 /// See AbstractAttribute::trackStatistics() 4741 void trackStatistics() const override { 4742 if (isAssumedReadNone()) 4743 STATS_DECLTRACK_FLOATING_ATTR(readnone) 4744 else if (isAssumedReadOnly()) 4745 STATS_DECLTRACK_FLOATING_ATTR(readonly) 4746 else if (isAssumedWriteOnly()) 4747 STATS_DECLTRACK_FLOATING_ATTR(writeonly) 4748 } 4749 4750 private: 4751 /// Return true if users of \p UserI might access the underlying 4752 /// variable/location described by \p U and should therefore be analyzed. 4753 bool followUsersOfUseIn(Attributor &A, const Use *U, 4754 const Instruction *UserI); 4755 4756 /// Update the state according to the effect of use \p U in \p UserI. 4757 void analyzeUseIn(Attributor &A, const Use *U, const Instruction *UserI); 4758 4759 protected: 4760 /// Container for (transitive) uses of the associated argument. 4761 SetVector<const Use *> Uses; 4762 }; 4763 4764 /// Memory behavior attribute for function argument. 4765 struct AAMemoryBehaviorArgument : AAMemoryBehaviorFloating { 4766 AAMemoryBehaviorArgument(const IRPosition &IRP) 4767 : AAMemoryBehaviorFloating(IRP) {} 4768 4769 /// See AbstractAttribute::initialize(...). 4770 void initialize(Attributor &A) override { 4771 intersectAssumedBits(BEST_STATE); 4772 const IRPosition &IRP = getIRPosition(); 4773 // TODO: Make IgnoreSubsumingPositions a property of an IRAttribute so we 4774 // can query it when we use has/getAttr. That would allow us to reuse the 4775 // initialize of the base class here. 4776 bool HasByVal = 4777 IRP.hasAttr({Attribute::ByVal}, /* IgnoreSubsumingPositions */ true); 4778 getKnownStateFromValue(IRP, getState(), 4779 /* IgnoreSubsumingPositions */ HasByVal); 4780 4781 // Initialize the use vector with all direct uses of the associated value. 4782 Argument *Arg = getAssociatedArgument(); 4783 if (!Arg || !Arg->getParent()->hasExactDefinition()) { 4784 indicatePessimisticFixpoint(); 4785 } else { 4786 // Initialize the use vector with all direct uses of the associated value. 4787 for (const Use &U : Arg->uses()) 4788 Uses.insert(&U); 4789 } 4790 } 4791 4792 ChangeStatus manifest(Attributor &A) override { 4793 // TODO: From readattrs.ll: "inalloca parameters are always 4794 // considered written" 4795 if (hasAttr({Attribute::InAlloca})) { 4796 removeKnownBits(NO_WRITES); 4797 removeAssumedBits(NO_WRITES); 4798 } 4799 return AAMemoryBehaviorFloating::manifest(A); 4800 } 4801 4802 /// See AbstractAttribute::trackStatistics() 4803 void trackStatistics() const override { 4804 if (isAssumedReadNone()) 4805 STATS_DECLTRACK_ARG_ATTR(readnone) 4806 else if (isAssumedReadOnly()) 4807 STATS_DECLTRACK_ARG_ATTR(readonly) 4808 else if (isAssumedWriteOnly()) 4809 STATS_DECLTRACK_ARG_ATTR(writeonly) 4810 } 4811 }; 4812 4813 struct AAMemoryBehaviorCallSiteArgument final : AAMemoryBehaviorArgument { 4814 AAMemoryBehaviorCallSiteArgument(const IRPosition &IRP) 4815 : AAMemoryBehaviorArgument(IRP) {} 4816 4817 /// See AbstractAttribute::initialize(...). 4818 void initialize(Attributor &A) override { 4819 if (Argument *Arg = getAssociatedArgument()) { 4820 if (Arg->hasByValAttr()) { 4821 addKnownBits(NO_WRITES); 4822 removeKnownBits(NO_READS); 4823 removeAssumedBits(NO_READS); 4824 } 4825 } else { 4826 } 4827 AAMemoryBehaviorArgument::initialize(A); 4828 } 4829 4830 /// See AbstractAttribute::updateImpl(...). 4831 ChangeStatus updateImpl(Attributor &A) override { 4832 // TODO: Once we have call site specific value information we can provide 4833 // call site specific liveness liveness information and then it makes 4834 // sense to specialize attributes for call sites arguments instead of 4835 // redirecting requests to the callee argument. 4836 Argument *Arg = getAssociatedArgument(); 4837 const IRPosition &ArgPos = IRPosition::argument(*Arg); 4838 auto &ArgAA = A.getAAFor<AAMemoryBehavior>(*this, ArgPos); 4839 return clampStateAndIndicateChange( 4840 getState(), 4841 static_cast<const AAMemoryBehavior::StateType &>(ArgAA.getState())); 4842 } 4843 4844 /// See AbstractAttribute::trackStatistics() 4845 void trackStatistics() const override { 4846 if (isAssumedReadNone()) 4847 STATS_DECLTRACK_CSARG_ATTR(readnone) 4848 else if (isAssumedReadOnly()) 4849 STATS_DECLTRACK_CSARG_ATTR(readonly) 4850 else if (isAssumedWriteOnly()) 4851 STATS_DECLTRACK_CSARG_ATTR(writeonly) 4852 } 4853 }; 4854 4855 /// Memory behavior attribute for a call site return position. 4856 struct AAMemoryBehaviorCallSiteReturned final : AAMemoryBehaviorFloating { 4857 AAMemoryBehaviorCallSiteReturned(const IRPosition &IRP) 4858 : AAMemoryBehaviorFloating(IRP) {} 4859 4860 /// See AbstractAttribute::manifest(...). 4861 ChangeStatus manifest(Attributor &A) override { 4862 // We do not annotate returned values. 4863 return ChangeStatus::UNCHANGED; 4864 } 4865 4866 /// See AbstractAttribute::trackStatistics() 4867 void trackStatistics() const override {} 4868 }; 4869 4870 /// An AA to represent the memory behavior function attributes. 4871 struct AAMemoryBehaviorFunction final : public AAMemoryBehaviorImpl { 4872 AAMemoryBehaviorFunction(const IRPosition &IRP) : AAMemoryBehaviorImpl(IRP) {} 4873 4874 /// See AbstractAttribute::updateImpl(Attributor &A). 4875 virtual ChangeStatus updateImpl(Attributor &A) override; 4876 4877 /// See AbstractAttribute::manifest(...). 4878 ChangeStatus manifest(Attributor &A) override { 4879 Function &F = cast<Function>(getAnchorValue()); 4880 if (isAssumedReadNone()) { 4881 F.removeFnAttr(Attribute::ArgMemOnly); 4882 F.removeFnAttr(Attribute::InaccessibleMemOnly); 4883 F.removeFnAttr(Attribute::InaccessibleMemOrArgMemOnly); 4884 } 4885 return AAMemoryBehaviorImpl::manifest(A); 4886 } 4887 4888 /// See AbstractAttribute::trackStatistics() 4889 void trackStatistics() const override { 4890 if (isAssumedReadNone()) 4891 STATS_DECLTRACK_FN_ATTR(readnone) 4892 else if (isAssumedReadOnly()) 4893 STATS_DECLTRACK_FN_ATTR(readonly) 4894 else if (isAssumedWriteOnly()) 4895 STATS_DECLTRACK_FN_ATTR(writeonly) 4896 } 4897 }; 4898 4899 /// AAMemoryBehavior attribute for call sites. 4900 struct AAMemoryBehaviorCallSite final : AAMemoryBehaviorImpl { 4901 AAMemoryBehaviorCallSite(const IRPosition &IRP) : AAMemoryBehaviorImpl(IRP) {} 4902 4903 /// See AbstractAttribute::initialize(...). 4904 void initialize(Attributor &A) override { 4905 AAMemoryBehaviorImpl::initialize(A); 4906 Function *F = getAssociatedFunction(); 4907 if (!F || !F->hasExactDefinition()) 4908 indicatePessimisticFixpoint(); 4909 } 4910 4911 /// See AbstractAttribute::updateImpl(...). 4912 ChangeStatus updateImpl(Attributor &A) override { 4913 // TODO: Once we have call site specific value information we can provide 4914 // call site specific liveness liveness information and then it makes 4915 // sense to specialize attributes for call sites arguments instead of 4916 // redirecting requests to the callee argument. 4917 Function *F = getAssociatedFunction(); 4918 const IRPosition &FnPos = IRPosition::function(*F); 4919 auto &FnAA = A.getAAFor<AAMemoryBehavior>(*this, FnPos); 4920 return clampStateAndIndicateChange( 4921 getState(), 4922 static_cast<const AAMemoryBehavior::StateType &>(FnAA.getState())); 4923 } 4924 4925 /// See AbstractAttribute::trackStatistics() 4926 void trackStatistics() const override { 4927 if (isAssumedReadNone()) 4928 STATS_DECLTRACK_CS_ATTR(readnone) 4929 else if (isAssumedReadOnly()) 4930 STATS_DECLTRACK_CS_ATTR(readonly) 4931 else if (isAssumedWriteOnly()) 4932 STATS_DECLTRACK_CS_ATTR(writeonly) 4933 } 4934 }; 4935 } // namespace 4936 4937 ChangeStatus AAMemoryBehaviorFunction::updateImpl(Attributor &A) { 4938 4939 // The current assumed state used to determine a change. 4940 auto AssumedState = getAssumed(); 4941 4942 auto CheckRWInst = [&](Instruction &I) { 4943 // If the instruction has an own memory behavior state, use it to restrict 4944 // the local state. No further analysis is required as the other memory 4945 // state is as optimistic as it gets. 4946 if (ImmutableCallSite ICS = ImmutableCallSite(&I)) { 4947 const auto &MemBehaviorAA = A.getAAFor<AAMemoryBehavior>( 4948 *this, IRPosition::callsite_function(ICS)); 4949 intersectAssumedBits(MemBehaviorAA.getAssumed()); 4950 return !isAtFixpoint(); 4951 } 4952 4953 // Remove access kind modifiers if necessary. 4954 if (I.mayReadFromMemory()) 4955 removeAssumedBits(NO_READS); 4956 if (I.mayWriteToMemory()) 4957 removeAssumedBits(NO_WRITES); 4958 return !isAtFixpoint(); 4959 }; 4960 4961 if (!A.checkForAllReadWriteInstructions(CheckRWInst, *this)) 4962 return indicatePessimisticFixpoint(); 4963 4964 return (AssumedState != getAssumed()) ? ChangeStatus::CHANGED 4965 : ChangeStatus::UNCHANGED; 4966 } 4967 4968 ChangeStatus AAMemoryBehaviorFloating::updateImpl(Attributor &A) { 4969 4970 const IRPosition &IRP = getIRPosition(); 4971 const IRPosition &FnPos = IRPosition::function_scope(IRP); 4972 AAMemoryBehavior::StateType &S = getState(); 4973 4974 // First, check the function scope. We take the known information and we avoid 4975 // work if the assumed information implies the current assumed information for 4976 // this attribute. This is a valid for all but byval arguments. 4977 Argument *Arg = IRP.getAssociatedArgument(); 4978 AAMemoryBehavior::base_t FnMemAssumedState = 4979 AAMemoryBehavior::StateType::getWorstState(); 4980 if (!Arg || !Arg->hasByValAttr()) { 4981 const auto &FnMemAA = A.getAAFor<AAMemoryBehavior>(*this, FnPos); 4982 FnMemAssumedState = FnMemAA.getAssumed(); 4983 S.addKnownBits(FnMemAA.getKnown()); 4984 if ((S.getAssumed() & FnMemAA.getAssumed()) == S.getAssumed()) 4985 return ChangeStatus::UNCHANGED; 4986 } 4987 4988 // Make sure the value is not captured (except through "return"), if 4989 // it is, any information derived would be irrelevant anyway as we cannot 4990 // check the potential aliases introduced by the capture. However, no need 4991 // to fall back to anythign less optimistic than the function state. 4992 const auto &ArgNoCaptureAA = A.getAAFor<AANoCapture>( 4993 *this, IRP, /* TrackDependence */ true, DepClassTy::OPTIONAL); 4994 if (!ArgNoCaptureAA.isAssumedNoCaptureMaybeReturned()) { 4995 S.intersectAssumedBits(FnMemAssumedState); 4996 return ChangeStatus::CHANGED; 4997 } 4998 4999 // The current assumed state used to determine a change. 5000 auto AssumedState = S.getAssumed(); 5001 5002 // Liveness information to exclude dead users. 5003 // TODO: Take the FnPos once we have call site specific liveness information. 5004 const auto &LivenessAA = A.getAAFor<AAIsDead>( 5005 *this, IRPosition::function(*IRP.getAssociatedFunction())); 5006 5007 // Visit and expand uses until all are analyzed or a fixpoint is reached. 5008 for (unsigned i = 0; i < Uses.size() && !isAtFixpoint(); i++) { 5009 const Use *U = Uses[i]; 5010 Instruction *UserI = cast<Instruction>(U->getUser()); 5011 LLVM_DEBUG(dbgs() << "[AAMemoryBehavior] Use: " << **U << " in " << *UserI 5012 << " [Dead: " << (LivenessAA.isAssumedDead(UserI)) 5013 << "]\n"); 5014 if (LivenessAA.isAssumedDead(UserI)) 5015 continue; 5016 5017 // Check if the users of UserI should also be visited. 5018 if (followUsersOfUseIn(A, U, UserI)) 5019 for (const Use &UserIUse : UserI->uses()) 5020 Uses.insert(&UserIUse); 5021 5022 // If UserI might touch memory we analyze the use in detail. 5023 if (UserI->mayReadOrWriteMemory()) 5024 analyzeUseIn(A, U, UserI); 5025 } 5026 5027 return (AssumedState != getAssumed()) ? ChangeStatus::CHANGED 5028 : ChangeStatus::UNCHANGED; 5029 } 5030 5031 bool AAMemoryBehaviorFloating::followUsersOfUseIn(Attributor &A, const Use *U, 5032 const Instruction *UserI) { 5033 // The loaded value is unrelated to the pointer argument, no need to 5034 // follow the users of the load. 5035 if (isa<LoadInst>(UserI)) 5036 return false; 5037 5038 // By default we follow all uses assuming UserI might leak information on U, 5039 // we have special handling for call sites operands though. 5040 ImmutableCallSite ICS(UserI); 5041 if (!ICS || !ICS.isArgOperand(U)) 5042 return true; 5043 5044 // If the use is a call argument known not to be captured, the users of 5045 // the call do not need to be visited because they have to be unrelated to 5046 // the input. Note that this check is not trivial even though we disallow 5047 // general capturing of the underlying argument. The reason is that the 5048 // call might the argument "through return", which we allow and for which we 5049 // need to check call users. 5050 unsigned ArgNo = ICS.getArgumentNo(U); 5051 const auto &ArgNoCaptureAA = 5052 A.getAAFor<AANoCapture>(*this, IRPosition::callsite_argument(ICS, ArgNo)); 5053 return !ArgNoCaptureAA.isAssumedNoCapture(); 5054 } 5055 5056 void AAMemoryBehaviorFloating::analyzeUseIn(Attributor &A, const Use *U, 5057 const Instruction *UserI) { 5058 assert(UserI->mayReadOrWriteMemory()); 5059 5060 switch (UserI->getOpcode()) { 5061 default: 5062 // TODO: Handle all atomics and other side-effect operations we know of. 5063 break; 5064 case Instruction::Load: 5065 // Loads cause the NO_READS property to disappear. 5066 removeAssumedBits(NO_READS); 5067 return; 5068 5069 case Instruction::Store: 5070 // Stores cause the NO_WRITES property to disappear if the use is the 5071 // pointer operand. Note that we do assume that capturing was taken care of 5072 // somewhere else. 5073 if (cast<StoreInst>(UserI)->getPointerOperand() == U->get()) 5074 removeAssumedBits(NO_WRITES); 5075 return; 5076 5077 case Instruction::Call: 5078 case Instruction::CallBr: 5079 case Instruction::Invoke: { 5080 // For call sites we look at the argument memory behavior attribute (this 5081 // could be recursive!) in order to restrict our own state. 5082 ImmutableCallSite ICS(UserI); 5083 5084 // Give up on operand bundles. 5085 if (ICS.isBundleOperand(U)) { 5086 indicatePessimisticFixpoint(); 5087 return; 5088 } 5089 5090 // Calling a function does read the function pointer, maybe write it if the 5091 // function is self-modifying. 5092 if (ICS.isCallee(U)) { 5093 removeAssumedBits(NO_READS); 5094 break; 5095 } 5096 5097 // Adjust the possible access behavior based on the information on the 5098 // argument. 5099 unsigned ArgNo = ICS.getArgumentNo(U); 5100 const IRPosition &ArgPos = IRPosition::callsite_argument(ICS, ArgNo); 5101 const auto &MemBehaviorAA = A.getAAFor<AAMemoryBehavior>(*this, ArgPos); 5102 // "assumed" has at most the same bits as the MemBehaviorAA assumed 5103 // and at least "known". 5104 intersectAssumedBits(MemBehaviorAA.getAssumed()); 5105 return; 5106 } 5107 }; 5108 5109 // Generally, look at the "may-properties" and adjust the assumed state if we 5110 // did not trigger special handling before. 5111 if (UserI->mayReadFromMemory()) 5112 removeAssumedBits(NO_READS); 5113 if (UserI->mayWriteToMemory()) 5114 removeAssumedBits(NO_WRITES); 5115 } 5116 /// ------------------ Value Constant Range Attribute ------------------------- 5117 5118 struct AAValueConstantRangeImpl : AAValueConstantRange { 5119 using StateType = IntegerRangeState; 5120 AAValueConstantRangeImpl(const IRPosition &IRP) : AAValueConstantRange(IRP) {} 5121 5122 /// See AbstractAttribute::getAsStr(). 5123 const std::string getAsStr() const override { 5124 std::string Str; 5125 llvm::raw_string_ostream OS(Str); 5126 OS << "range(" << getBitWidth() << ")<"; 5127 getKnown().print(OS); 5128 OS << " / "; 5129 getAssumed().print(OS); 5130 OS << ">"; 5131 return OS.str(); 5132 } 5133 5134 /// Helper function to get a SCEV expr for the associated value at program 5135 /// point \p I. 5136 const SCEV *getSCEV(Attributor &A, const Instruction *I = nullptr) const { 5137 if (!getAnchorScope()) 5138 return nullptr; 5139 5140 ScalarEvolution *SE = 5141 A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>( 5142 *getAnchorScope()); 5143 5144 LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>( 5145 *getAnchorScope()); 5146 5147 if (!SE || !LI) 5148 return nullptr; 5149 5150 const SCEV *S = SE->getSCEV(&getAssociatedValue()); 5151 if (!I) 5152 return S; 5153 5154 return SE->getSCEVAtScope(S, LI->getLoopFor(I->getParent())); 5155 } 5156 5157 /// Helper function to get a range from SCEV for the associated value at 5158 /// program point \p I. 5159 ConstantRange getConstantRangeFromSCEV(Attributor &A, 5160 const Instruction *I = nullptr) const { 5161 if (!getAnchorScope()) 5162 return getWorstState(getBitWidth()); 5163 5164 ScalarEvolution *SE = 5165 A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>( 5166 *getAnchorScope()); 5167 5168 const SCEV *S = getSCEV(A, I); 5169 if (!SE || !S) 5170 return getWorstState(getBitWidth()); 5171 5172 return SE->getUnsignedRange(S); 5173 } 5174 5175 /// Helper function to get a range from LVI for the associated value at 5176 /// program point \p I. 5177 ConstantRange 5178 getConstantRangeFromLVI(Attributor &A, 5179 const Instruction *CtxI = nullptr) const { 5180 if (!getAnchorScope()) 5181 return getWorstState(getBitWidth()); 5182 5183 LazyValueInfo *LVI = 5184 A.getInfoCache().getAnalysisResultForFunction<LazyValueAnalysis>( 5185 *getAnchorScope()); 5186 5187 if (!LVI || !CtxI) 5188 return getWorstState(getBitWidth()); 5189 return LVI->getConstantRange(&getAssociatedValue(), 5190 const_cast<BasicBlock *>(CtxI->getParent()), 5191 const_cast<Instruction *>(CtxI)); 5192 } 5193 5194 /// See AAValueConstantRange::getKnownConstantRange(..). 5195 ConstantRange 5196 getKnownConstantRange(Attributor &A, 5197 const Instruction *CtxI = nullptr) const override { 5198 if (!CtxI || CtxI == getCtxI()) 5199 return getKnown(); 5200 5201 ConstantRange LVIR = getConstantRangeFromLVI(A, CtxI); 5202 ConstantRange SCEVR = getConstantRangeFromSCEV(A, CtxI); 5203 return getKnown().intersectWith(SCEVR).intersectWith(LVIR); 5204 } 5205 5206 /// See AAValueConstantRange::getAssumedConstantRange(..). 5207 ConstantRange 5208 getAssumedConstantRange(Attributor &A, 5209 const Instruction *CtxI = nullptr) const override { 5210 // TODO: Make SCEV use Attributor assumption. 5211 // We may be able to bound a variable range via assumptions in 5212 // Attributor. ex.) If x is assumed to be in [1, 3] and y is known to 5213 // evolve to x^2 + x, then we can say that y is in [2, 12]. 5214 5215 if (!CtxI || CtxI == getCtxI()) 5216 return getAssumed(); 5217 5218 ConstantRange LVIR = getConstantRangeFromLVI(A, CtxI); 5219 ConstantRange SCEVR = getConstantRangeFromSCEV(A, CtxI); 5220 return getAssumed().intersectWith(SCEVR).intersectWith(LVIR); 5221 } 5222 5223 /// See AbstractAttribute::initialize(..). 5224 void initialize(Attributor &A) override { 5225 // Intersect a range given by SCEV. 5226 intersectKnown(getConstantRangeFromSCEV(A, getCtxI())); 5227 5228 // Intersect a range given by LVI. 5229 intersectKnown(getConstantRangeFromLVI(A, getCtxI())); 5230 } 5231 5232 /// Helper function to create MDNode for range metadata. 5233 static MDNode * 5234 getMDNodeForConstantRange(Type *Ty, LLVMContext &Ctx, 5235 const ConstantRange &AssumedConstantRange) { 5236 Metadata *LowAndHigh[] = {ConstantAsMetadata::get(ConstantInt::get( 5237 Ty, AssumedConstantRange.getLower())), 5238 ConstantAsMetadata::get(ConstantInt::get( 5239 Ty, AssumedConstantRange.getUpper()))}; 5240 return MDNode::get(Ctx, LowAndHigh); 5241 } 5242 5243 /// Return true if \p Assumed is included in \p KnownRanges. 5244 static bool isBetterRange(const ConstantRange &Assumed, MDNode *KnownRanges) { 5245 5246 if (Assumed.isFullSet()) 5247 return false; 5248 5249 if (!KnownRanges) 5250 return true; 5251 5252 // If multiple ranges are annotated in IR, we give up to annotate assumed 5253 // range for now. 5254 5255 // TODO: If there exists a known range which containts assumed range, we 5256 // can say assumed range is better. 5257 if (KnownRanges->getNumOperands() > 2) 5258 return false; 5259 5260 ConstantInt *Lower = 5261 mdconst::extract<ConstantInt>(KnownRanges->getOperand(0)); 5262 ConstantInt *Upper = 5263 mdconst::extract<ConstantInt>(KnownRanges->getOperand(1)); 5264 5265 ConstantRange Known(Lower->getValue(), Upper->getValue()); 5266 return Known.contains(Assumed) && Known != Assumed; 5267 } 5268 5269 /// Helper function to set range metadata. 5270 static bool 5271 setRangeMetadataIfisBetterRange(Instruction *I, 5272 const ConstantRange &AssumedConstantRange) { 5273 auto *OldRangeMD = I->getMetadata(LLVMContext::MD_range); 5274 if (isBetterRange(AssumedConstantRange, OldRangeMD)) { 5275 if (!AssumedConstantRange.isEmptySet()) { 5276 I->setMetadata(LLVMContext::MD_range, 5277 getMDNodeForConstantRange(I->getType(), I->getContext(), 5278 AssumedConstantRange)); 5279 return true; 5280 } 5281 } 5282 return false; 5283 } 5284 5285 /// See AbstractAttribute::manifest() 5286 ChangeStatus manifest(Attributor &A) override { 5287 ChangeStatus Changed = ChangeStatus::UNCHANGED; 5288 ConstantRange AssumedConstantRange = getAssumedConstantRange(A); 5289 assert(!AssumedConstantRange.isFullSet() && "Invalid state"); 5290 5291 auto &V = getAssociatedValue(); 5292 if (!AssumedConstantRange.isEmptySet() && 5293 !AssumedConstantRange.isSingleElement()) { 5294 if (Instruction *I = dyn_cast<Instruction>(&V)) 5295 if (isa<CallInst>(I) || isa<LoadInst>(I)) 5296 if (setRangeMetadataIfisBetterRange(I, AssumedConstantRange)) 5297 Changed = ChangeStatus::CHANGED; 5298 } 5299 5300 return Changed; 5301 } 5302 }; 5303 5304 struct AAValueConstantRangeArgument final : public AAValueConstantRangeImpl { 5305 5306 AAValueConstantRangeArgument(const IRPosition &IRP) 5307 : AAValueConstantRangeImpl(IRP) {} 5308 5309 /// See AbstractAttribute::updateImpl(...). 5310 ChangeStatus updateImpl(Attributor &A) override { 5311 // TODO: Use AAArgumentFromCallSiteArguments 5312 5313 IntegerRangeState S(getBitWidth()); 5314 clampCallSiteArgumentStates<AAValueConstantRange, IntegerRangeState>( 5315 A, *this, S); 5316 5317 // TODO: If we know we visited all incoming values, thus no are assumed 5318 // dead, we can take the known information from the state T. 5319 return clampStateAndIndicateChange<IntegerRangeState>(this->getState(), S); 5320 } 5321 5322 /// See AbstractAttribute::trackStatistics() 5323 void trackStatistics() const override { 5324 STATS_DECLTRACK_ARG_ATTR(value_range) 5325 } 5326 }; 5327 5328 struct AAValueConstantRangeReturned : AAValueConstantRangeImpl { 5329 AAValueConstantRangeReturned(const IRPosition &IRP) 5330 : AAValueConstantRangeImpl(IRP) {} 5331 5332 /// See AbstractAttribute::updateImpl(...). 5333 ChangeStatus updateImpl(Attributor &A) override { 5334 // TODO: Use AAReturnedFromReturnedValues 5335 5336 // TODO: If we know we visited all returned values, thus no are assumed 5337 // dead, we can take the known information from the state T. 5338 5339 IntegerRangeState S(getBitWidth()); 5340 5341 clampReturnedValueStates<AAValueConstantRange, IntegerRangeState>(A, *this, 5342 S); 5343 return clampStateAndIndicateChange<StateType>(this->getState(), S); 5344 } 5345 5346 /// See AbstractAttribute::trackStatistics() 5347 void trackStatistics() const override { 5348 STATS_DECLTRACK_FNRET_ATTR(value_range) 5349 } 5350 }; 5351 5352 struct AAValueConstantRangeFloating : AAValueConstantRangeImpl { 5353 AAValueConstantRangeFloating(const IRPosition &IRP) 5354 : AAValueConstantRangeImpl(IRP) {} 5355 5356 /// See AbstractAttribute::initialize(...). 5357 void initialize(Attributor &A) override { 5358 AAValueConstantRange::initialize(A); 5359 Value &V = getAssociatedValue(); 5360 5361 if (auto *C = dyn_cast<ConstantInt>(&V)) { 5362 unionAssumed(ConstantRange(C->getValue())); 5363 indicateOptimisticFixpoint(); 5364 return; 5365 } 5366 5367 if (isa<UndefValue>(&V)) { 5368 indicateOptimisticFixpoint(); 5369 return; 5370 } 5371 5372 if (auto *I = dyn_cast<Instruction>(&V)) 5373 if (isa<BinaryOperator>(I) || isa<CmpInst>(I)) { 5374 Value *LHS = I->getOperand(0); 5375 Value *RHS = I->getOperand(1); 5376 5377 if (LHS->getType()->isIntegerTy() && RHS->getType()->isIntegerTy()) 5378 return; 5379 } 5380 5381 // If it is a load instruction with range metadata, use it. 5382 if (LoadInst *LI = dyn_cast<LoadInst>(&V)) 5383 if (auto *RangeMD = LI->getMetadata(LLVMContext::MD_range)) { 5384 intersectKnown(getConstantRangeFromMetadata(*RangeMD)); 5385 return; 5386 } 5387 5388 // Otherwise we give up. 5389 indicatePessimisticFixpoint(); 5390 5391 LLVM_DEBUG(dbgs() << "[Attributor][AAValueConstantRange] We give up: " 5392 << getAssociatedValue()); 5393 } 5394 5395 bool calculateBinaryOperator(Attributor &A, BinaryOperator *BinOp, 5396 IntegerRangeState &T, Instruction *CtxI) { 5397 Value *LHS = BinOp->getOperand(0); 5398 Value *RHS = BinOp->getOperand(1); 5399 5400 auto &LHSAA = 5401 A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*LHS)); 5402 auto LHSAARange = LHSAA.getAssumedConstantRange(A, CtxI); 5403 5404 auto &RHSAA = 5405 A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*RHS)); 5406 auto RHSAARange = RHSAA.getAssumedConstantRange(A, CtxI); 5407 5408 auto AssumedRange = LHSAARange.binaryOp(BinOp->getOpcode(), RHSAARange); 5409 5410 T.unionAssumed(AssumedRange); 5411 5412 // TODO: Track a known state too. 5413 5414 return T.isValidState(); 5415 } 5416 5417 bool calculateCmpInst(Attributor &A, CmpInst *CmpI, IntegerRangeState &T, 5418 Instruction *CtxI) { 5419 Value *LHS = CmpI->getOperand(0); 5420 Value *RHS = CmpI->getOperand(1); 5421 5422 auto &LHSAA = 5423 A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*LHS)); 5424 auto &RHSAA = 5425 A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(*RHS)); 5426 5427 auto LHSAARange = LHSAA.getAssumedConstantRange(A, CtxI); 5428 auto RHSAARange = RHSAA.getAssumedConstantRange(A, CtxI); 5429 5430 // If one of them is empty set, we can't decide. 5431 if (LHSAARange.isEmptySet() || RHSAARange.isEmptySet()) 5432 return true; 5433 5434 bool MustTrue = false, MustFalse = false; 5435 5436 auto AllowedRegion = 5437 ConstantRange::makeAllowedICmpRegion(CmpI->getPredicate(), RHSAARange); 5438 5439 auto SatisfyingRegion = ConstantRange::makeSatisfyingICmpRegion( 5440 CmpI->getPredicate(), RHSAARange); 5441 5442 if (AllowedRegion.intersectWith(LHSAARange).isEmptySet()) 5443 MustFalse = true; 5444 5445 if (SatisfyingRegion.contains(LHSAARange)) 5446 MustTrue = true; 5447 5448 assert((!MustTrue || !MustFalse) && 5449 "Either MustTrue or MustFalse should be false!"); 5450 5451 if (MustTrue) 5452 T.unionAssumed(ConstantRange(APInt(/* numBits */ 1, /* val */ 1))); 5453 else if (MustFalse) 5454 T.unionAssumed(ConstantRange(APInt(/* numBits */ 1, /* val */ 0))); 5455 else 5456 T.unionAssumed(ConstantRange(/* BitWidth */ 1, /* isFullSet */ true)); 5457 5458 LLVM_DEBUG(dbgs() << "[AAValueConstantRange] " << *CmpI << " " << LHSAA 5459 << " " << RHSAA << "\n"); 5460 5461 // TODO: Track a known state too. 5462 return T.isValidState(); 5463 } 5464 5465 /// See AbstractAttribute::updateImpl(...). 5466 ChangeStatus updateImpl(Attributor &A) override { 5467 Instruction *CtxI = getCtxI(); 5468 auto VisitValueCB = [&](Value &V, IntegerRangeState &T, 5469 bool Stripped) -> bool { 5470 Instruction *I = dyn_cast<Instruction>(&V); 5471 if (!I) { 5472 5473 // If the value is not instruction, we query AA to Attributor. 5474 const auto &AA = 5475 A.getAAFor<AAValueConstantRange>(*this, IRPosition::value(V)); 5476 5477 // Clamp operator is not used to utilize a program point CtxI. 5478 T.unionAssumed(AA.getAssumedConstantRange(A, CtxI)); 5479 5480 return T.isValidState(); 5481 } 5482 5483 if (auto *BinOp = dyn_cast<BinaryOperator>(I)) 5484 return calculateBinaryOperator(A, BinOp, T, CtxI); 5485 else if (auto *CmpI = dyn_cast<CmpInst>(I)) 5486 return calculateCmpInst(A, CmpI, T, CtxI); 5487 else { 5488 // Give up with other instructions. 5489 // TODO: Add other instructions 5490 5491 T.indicatePessimisticFixpoint(); 5492 return false; 5493 } 5494 }; 5495 5496 IntegerRangeState T(getBitWidth()); 5497 5498 if (!genericValueTraversal<AAValueConstantRange, IntegerRangeState>( 5499 A, getIRPosition(), *this, T, VisitValueCB)) 5500 return indicatePessimisticFixpoint(); 5501 5502 return clampStateAndIndicateChange(getState(), T); 5503 } 5504 5505 /// See AbstractAttribute::trackStatistics() 5506 void trackStatistics() const override { 5507 STATS_DECLTRACK_FLOATING_ATTR(value_range) 5508 } 5509 }; 5510 5511 struct AAValueConstantRangeFunction : AAValueConstantRangeImpl { 5512 AAValueConstantRangeFunction(const IRPosition &IRP) 5513 : AAValueConstantRangeImpl(IRP) {} 5514 5515 /// See AbstractAttribute::initialize(...). 5516 ChangeStatus updateImpl(Attributor &A) override { 5517 llvm_unreachable("AAValueConstantRange(Function|CallSite)::updateImpl will " 5518 "not be called"); 5519 } 5520 5521 /// See AbstractAttribute::trackStatistics() 5522 void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(value_range) } 5523 }; 5524 5525 struct AAValueConstantRangeCallSite : AAValueConstantRangeFunction { 5526 AAValueConstantRangeCallSite(const IRPosition &IRP) 5527 : AAValueConstantRangeFunction(IRP) {} 5528 5529 /// See AbstractAttribute::trackStatistics() 5530 void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(value_range) } 5531 }; 5532 5533 struct AAValueConstantRangeCallSiteReturned : AAValueConstantRangeReturned { 5534 AAValueConstantRangeCallSiteReturned(const IRPosition &IRP) 5535 : AAValueConstantRangeReturned(IRP) {} 5536 5537 /// See AbstractAttribute::initialize(...). 5538 void initialize(Attributor &A) override { 5539 // If it is a load instruction with range metadata, use the metadata. 5540 if (CallInst *CI = dyn_cast<CallInst>(&getAssociatedValue())) 5541 if (auto *RangeMD = CI->getMetadata(LLVMContext::MD_range)) 5542 intersectKnown(getConstantRangeFromMetadata(*RangeMD)); 5543 5544 AAValueConstantRangeReturned::initialize(A); 5545 } 5546 5547 /// See AbstractAttribute::trackStatistics() 5548 void trackStatistics() const override { 5549 STATS_DECLTRACK_CSRET_ATTR(value_range) 5550 } 5551 }; 5552 struct AAValueConstantRangeCallSiteArgument : AAValueConstantRangeFloating { 5553 AAValueConstantRangeCallSiteArgument(const IRPosition &IRP) 5554 : AAValueConstantRangeFloating(IRP) {} 5555 5556 /// See AbstractAttribute::trackStatistics() 5557 void trackStatistics() const override { 5558 STATS_DECLTRACK_CSARG_ATTR(value_range) 5559 } 5560 }; 5561 /// ---------------------------------------------------------------------------- 5562 /// Attributor 5563 /// ---------------------------------------------------------------------------- 5564 5565 bool Attributor::isAssumedDead(const AbstractAttribute &AA, 5566 const AAIsDead *LivenessAA) { 5567 const Instruction *CtxI = AA.getIRPosition().getCtxI(); 5568 if (!CtxI) 5569 return false; 5570 5571 // TODO: Find a good way to utilize fine and coarse grained liveness 5572 // information. 5573 if (!LivenessAA) 5574 LivenessAA = 5575 &getAAFor<AAIsDead>(AA, IRPosition::function(*CtxI->getFunction()), 5576 /* TrackDependence */ false); 5577 5578 // Don't check liveness for AAIsDead. 5579 if (&AA == LivenessAA) 5580 return false; 5581 5582 if (!LivenessAA->isAssumedDead(CtxI)) 5583 return false; 5584 5585 // We actually used liveness information so we have to record a dependence. 5586 recordDependence(*LivenessAA, AA, DepClassTy::OPTIONAL); 5587 5588 return true; 5589 } 5590 5591 bool Attributor::checkForAllUses( 5592 const function_ref<bool(const Use &, bool &)> &Pred, 5593 const AbstractAttribute &QueryingAA, const Value &V) { 5594 const IRPosition &IRP = QueryingAA.getIRPosition(); 5595 SmallVector<const Use *, 16> Worklist; 5596 SmallPtrSet<const Use *, 16> Visited; 5597 5598 for (const Use &U : V.uses()) 5599 Worklist.push_back(&U); 5600 5601 LLVM_DEBUG(dbgs() << "[Attributor] Got " << Worklist.size() 5602 << " initial uses to check\n"); 5603 5604 if (Worklist.empty()) 5605 return true; 5606 5607 bool AnyDead = false; 5608 const Function *ScopeFn = IRP.getAnchorScope(); 5609 const auto *LivenessAA = 5610 ScopeFn ? &getAAFor<AAIsDead>(QueryingAA, IRPosition::function(*ScopeFn), 5611 /* TrackDependence */ false) 5612 : nullptr; 5613 5614 while (!Worklist.empty()) { 5615 const Use *U = Worklist.pop_back_val(); 5616 if (!Visited.insert(U).second) 5617 continue; 5618 LLVM_DEBUG(dbgs() << "[Attributor] Check use: " << **U << "\n"); 5619 if (Instruction *UserI = dyn_cast<Instruction>(U->getUser())) 5620 if (LivenessAA && LivenessAA->isAssumedDead(UserI)) { 5621 LLVM_DEBUG(dbgs() << "[Attributor] Dead user: " << *UserI << ": " 5622 << *LivenessAA << "\n"); 5623 AnyDead = true; 5624 continue; 5625 } 5626 5627 bool Follow = false; 5628 if (!Pred(*U, Follow)) 5629 return false; 5630 if (!Follow) 5631 continue; 5632 for (const Use &UU : U->getUser()->uses()) 5633 Worklist.push_back(&UU); 5634 } 5635 5636 if (AnyDead) 5637 recordDependence(*LivenessAA, QueryingAA, DepClassTy::OPTIONAL); 5638 5639 return true; 5640 } 5641 5642 bool Attributor::checkForAllCallSites( 5643 const function_ref<bool(AbstractCallSite)> &Pred, 5644 const AbstractAttribute &QueryingAA, bool RequireAllCallSites) { 5645 // We can try to determine information from 5646 // the call sites. However, this is only possible all call sites are known, 5647 // hence the function has internal linkage. 5648 const IRPosition &IRP = QueryingAA.getIRPosition(); 5649 const Function *AssociatedFunction = IRP.getAssociatedFunction(); 5650 if (!AssociatedFunction) { 5651 LLVM_DEBUG(dbgs() << "[Attributor] No function associated with " << IRP 5652 << "\n"); 5653 return false; 5654 } 5655 5656 return checkForAllCallSites(Pred, *AssociatedFunction, RequireAllCallSites, 5657 &QueryingAA); 5658 } 5659 5660 bool Attributor::checkForAllCallSites( 5661 const function_ref<bool(AbstractCallSite)> &Pred, const Function &Fn, 5662 bool RequireAllCallSites, const AbstractAttribute *QueryingAA) { 5663 if (RequireAllCallSites && !Fn.hasLocalLinkage()) { 5664 LLVM_DEBUG( 5665 dbgs() 5666 << "[Attributor] Function " << Fn.getName() 5667 << " has no internal linkage, hence not all call sites are known\n"); 5668 return false; 5669 } 5670 5671 for (const Use &U : Fn.uses()) { 5672 AbstractCallSite ACS(&U); 5673 if (!ACS) { 5674 LLVM_DEBUG(dbgs() << "[Attributor] Function " << Fn.getName() 5675 << " has non call site use " << *U.get() << " in " 5676 << *U.getUser() << "\n"); 5677 // BlockAddress users are allowed. 5678 if (isa<BlockAddress>(U.getUser())) 5679 continue; 5680 return false; 5681 } 5682 5683 Instruction *I = ACS.getInstruction(); 5684 Function *Caller = I->getFunction(); 5685 5686 const auto *LivenessAA = 5687 lookupAAFor<AAIsDead>(IRPosition::function(*Caller), QueryingAA, 5688 /* TrackDependence */ false); 5689 5690 // Skip dead calls. 5691 if (LivenessAA && LivenessAA->isAssumedDead(I)) { 5692 // We actually used liveness information so we have to record a 5693 // dependence. 5694 if (QueryingAA) 5695 recordDependence(*LivenessAA, *QueryingAA, DepClassTy::OPTIONAL); 5696 continue; 5697 } 5698 5699 const Use *EffectiveUse = 5700 ACS.isCallbackCall() ? &ACS.getCalleeUseForCallback() : &U; 5701 if (!ACS.isCallee(EffectiveUse)) { 5702 if (!RequireAllCallSites) 5703 continue; 5704 LLVM_DEBUG(dbgs() << "[Attributor] User " << EffectiveUse->getUser() 5705 << " is an invalid use of " << Fn.getName() << "\n"); 5706 return false; 5707 } 5708 5709 if (Pred(ACS)) 5710 continue; 5711 5712 LLVM_DEBUG(dbgs() << "[Attributor] Call site callback failed for " 5713 << *ACS.getInstruction() << "\n"); 5714 return false; 5715 } 5716 5717 return true; 5718 } 5719 5720 bool Attributor::checkForAllReturnedValuesAndReturnInsts( 5721 const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> 5722 &Pred, 5723 const AbstractAttribute &QueryingAA) { 5724 5725 const IRPosition &IRP = QueryingAA.getIRPosition(); 5726 // Since we need to provide return instructions we have to have an exact 5727 // definition. 5728 const Function *AssociatedFunction = IRP.getAssociatedFunction(); 5729 if (!AssociatedFunction) 5730 return false; 5731 5732 // If this is a call site query we use the call site specific return values 5733 // and liveness information. 5734 // TODO: use the function scope once we have call site AAReturnedValues. 5735 const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction); 5736 const auto &AARetVal = getAAFor<AAReturnedValues>(QueryingAA, QueryIRP); 5737 if (!AARetVal.getState().isValidState()) 5738 return false; 5739 5740 return AARetVal.checkForAllReturnedValuesAndReturnInsts(Pred); 5741 } 5742 5743 bool Attributor::checkForAllReturnedValues( 5744 const function_ref<bool(Value &)> &Pred, 5745 const AbstractAttribute &QueryingAA) { 5746 5747 const IRPosition &IRP = QueryingAA.getIRPosition(); 5748 const Function *AssociatedFunction = IRP.getAssociatedFunction(); 5749 if (!AssociatedFunction) 5750 return false; 5751 5752 // TODO: use the function scope once we have call site AAReturnedValues. 5753 const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction); 5754 const auto &AARetVal = getAAFor<AAReturnedValues>(QueryingAA, QueryIRP); 5755 if (!AARetVal.getState().isValidState()) 5756 return false; 5757 5758 return AARetVal.checkForAllReturnedValuesAndReturnInsts( 5759 [&](Value &RV, const SmallSetVector<ReturnInst *, 4> &) { 5760 return Pred(RV); 5761 }); 5762 } 5763 5764 static bool 5765 checkForAllInstructionsImpl(InformationCache::OpcodeInstMapTy &OpcodeInstMap, 5766 const function_ref<bool(Instruction &)> &Pred, 5767 const AAIsDead *LivenessAA, bool &AnyDead, 5768 const ArrayRef<unsigned> &Opcodes) { 5769 for (unsigned Opcode : Opcodes) { 5770 for (Instruction *I : OpcodeInstMap[Opcode]) { 5771 // Skip dead instructions. 5772 if (LivenessAA && LivenessAA->isAssumedDead(I)) { 5773 AnyDead = true; 5774 continue; 5775 } 5776 5777 if (!Pred(*I)) 5778 return false; 5779 } 5780 } 5781 return true; 5782 } 5783 5784 bool Attributor::checkForAllInstructions( 5785 const llvm::function_ref<bool(Instruction &)> &Pred, 5786 const AbstractAttribute &QueryingAA, const ArrayRef<unsigned> &Opcodes) { 5787 5788 const IRPosition &IRP = QueryingAA.getIRPosition(); 5789 // Since we need to provide instructions we have to have an exact definition. 5790 const Function *AssociatedFunction = IRP.getAssociatedFunction(); 5791 if (!AssociatedFunction) 5792 return false; 5793 5794 // TODO: use the function scope once we have call site AAReturnedValues. 5795 const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction); 5796 const auto &LivenessAA = 5797 getAAFor<AAIsDead>(QueryingAA, QueryIRP, /* TrackDependence */ false); 5798 bool AnyDead = false; 5799 5800 auto &OpcodeInstMap = 5801 InfoCache.getOpcodeInstMapForFunction(*AssociatedFunction); 5802 if (!checkForAllInstructionsImpl(OpcodeInstMap, Pred, &LivenessAA, AnyDead, 5803 Opcodes)) 5804 return false; 5805 5806 // If we actually used liveness information so we have to record a dependence. 5807 if (AnyDead) 5808 recordDependence(LivenessAA, QueryingAA, DepClassTy::OPTIONAL); 5809 5810 return true; 5811 } 5812 5813 bool Attributor::checkForAllReadWriteInstructions( 5814 const llvm::function_ref<bool(Instruction &)> &Pred, 5815 AbstractAttribute &QueryingAA) { 5816 5817 const Function *AssociatedFunction = 5818 QueryingAA.getIRPosition().getAssociatedFunction(); 5819 if (!AssociatedFunction) 5820 return false; 5821 5822 // TODO: use the function scope once we have call site AAReturnedValues. 5823 const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction); 5824 const auto &LivenessAA = 5825 getAAFor<AAIsDead>(QueryingAA, QueryIRP, /* TrackDependence */ false); 5826 bool AnyDead = false; 5827 5828 for (Instruction *I : 5829 InfoCache.getReadOrWriteInstsForFunction(*AssociatedFunction)) { 5830 // Skip dead instructions. 5831 if (LivenessAA.isAssumedDead(I)) { 5832 AnyDead = true; 5833 continue; 5834 } 5835 5836 if (!Pred(*I)) 5837 return false; 5838 } 5839 5840 // If we actually used liveness information so we have to record a dependence. 5841 if (AnyDead) 5842 recordDependence(LivenessAA, QueryingAA, DepClassTy::OPTIONAL); 5843 5844 return true; 5845 } 5846 5847 ChangeStatus Attributor::run(Module &M) { 5848 LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized " 5849 << AllAbstractAttributes.size() 5850 << " abstract attributes.\n"); 5851 5852 // Now that all abstract attributes are collected and initialized we start 5853 // the abstract analysis. 5854 5855 unsigned IterationCounter = 1; 5856 5857 SmallVector<AbstractAttribute *, 64> ChangedAAs; 5858 SetVector<AbstractAttribute *> Worklist, InvalidAAs; 5859 Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end()); 5860 5861 bool RecomputeDependences = false; 5862 5863 do { 5864 // Remember the size to determine new attributes. 5865 size_t NumAAs = AllAbstractAttributes.size(); 5866 LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter 5867 << ", Worklist size: " << Worklist.size() << "\n"); 5868 5869 // For invalid AAs we can fix dependent AAs that have a required dependence, 5870 // thereby folding long dependence chains in a single step without the need 5871 // to run updates. 5872 for (unsigned u = 0; u < InvalidAAs.size(); ++u) { 5873 AbstractAttribute *InvalidAA = InvalidAAs[u]; 5874 auto &QuerriedAAs = QueryMap[InvalidAA]; 5875 LLVM_DEBUG(dbgs() << "[Attributor] InvalidAA: " << *InvalidAA << " has " 5876 << QuerriedAAs.RequiredAAs.size() << "/" 5877 << QuerriedAAs.OptionalAAs.size() 5878 << " required/optional dependences\n"); 5879 for (AbstractAttribute *DepOnInvalidAA : QuerriedAAs.RequiredAAs) { 5880 AbstractState &DOIAAState = DepOnInvalidAA->getState(); 5881 DOIAAState.indicatePessimisticFixpoint(); 5882 ++NumAttributesFixedDueToRequiredDependences; 5883 assert(DOIAAState.isAtFixpoint() && "Expected fixpoint state!"); 5884 if (!DOIAAState.isValidState()) 5885 InvalidAAs.insert(DepOnInvalidAA); 5886 } 5887 if (!RecomputeDependences) 5888 Worklist.insert(QuerriedAAs.OptionalAAs.begin(), 5889 QuerriedAAs.OptionalAAs.end()); 5890 } 5891 5892 // If dependences (=QueryMap) are recomputed we have to look at all abstract 5893 // attributes again, regardless of what changed in the last iteration. 5894 if (RecomputeDependences) { 5895 LLVM_DEBUG( 5896 dbgs() << "[Attributor] Run all AAs to recompute dependences\n"); 5897 QueryMap.clear(); 5898 ChangedAAs.clear(); 5899 Worklist.insert(AllAbstractAttributes.begin(), 5900 AllAbstractAttributes.end()); 5901 } 5902 5903 // Add all abstract attributes that are potentially dependent on one that 5904 // changed to the work list. 5905 for (AbstractAttribute *ChangedAA : ChangedAAs) { 5906 auto &QuerriedAAs = QueryMap[ChangedAA]; 5907 Worklist.insert(QuerriedAAs.OptionalAAs.begin(), 5908 QuerriedAAs.OptionalAAs.end()); 5909 Worklist.insert(QuerriedAAs.RequiredAAs.begin(), 5910 QuerriedAAs.RequiredAAs.end()); 5911 } 5912 5913 LLVM_DEBUG(dbgs() << "[Attributor] #Iteration: " << IterationCounter 5914 << ", Worklist+Dependent size: " << Worklist.size() 5915 << "\n"); 5916 5917 // Reset the changed and invalid set. 5918 ChangedAAs.clear(); 5919 InvalidAAs.clear(); 5920 5921 // Update all abstract attribute in the work list and record the ones that 5922 // changed. 5923 for (AbstractAttribute *AA : Worklist) 5924 if (!AA->getState().isAtFixpoint() && !isAssumedDead(*AA, nullptr)) { 5925 QueriedNonFixAA = false; 5926 if (AA->update(*this) == ChangeStatus::CHANGED) { 5927 ChangedAAs.push_back(AA); 5928 if (!AA->getState().isValidState()) 5929 InvalidAAs.insert(AA); 5930 } else if (!QueriedNonFixAA) { 5931 // If the attribute did not query any non-fix information, the state 5932 // will not change and we can indicate that right away. 5933 AA->getState().indicateOptimisticFixpoint(); 5934 } 5935 } 5936 5937 // Check if we recompute the dependences in the next iteration. 5938 RecomputeDependences = (DepRecomputeInterval > 0 && 5939 IterationCounter % DepRecomputeInterval == 0); 5940 5941 // Add attributes to the changed set if they have been created in the last 5942 // iteration. 5943 ChangedAAs.append(AllAbstractAttributes.begin() + NumAAs, 5944 AllAbstractAttributes.end()); 5945 5946 // Reset the work list and repopulate with the changed abstract attributes. 5947 // Note that dependent ones are added above. 5948 Worklist.clear(); 5949 Worklist.insert(ChangedAAs.begin(), ChangedAAs.end()); 5950 5951 } while (!Worklist.empty() && (IterationCounter++ < MaxFixpointIterations || 5952 VerifyMaxFixpointIterations)); 5953 5954 LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: " 5955 << IterationCounter << "/" << MaxFixpointIterations 5956 << " iterations\n"); 5957 5958 size_t NumFinalAAs = AllAbstractAttributes.size(); 5959 5960 // Reset abstract arguments not settled in a sound fixpoint by now. This 5961 // happens when we stopped the fixpoint iteration early. Note that only the 5962 // ones marked as "changed" *and* the ones transitively depending on them 5963 // need to be reverted to a pessimistic state. Others might not be in a 5964 // fixpoint state but we can use the optimistic results for them anyway. 5965 SmallPtrSet<AbstractAttribute *, 32> Visited; 5966 for (unsigned u = 0; u < ChangedAAs.size(); u++) { 5967 AbstractAttribute *ChangedAA = ChangedAAs[u]; 5968 if (!Visited.insert(ChangedAA).second) 5969 continue; 5970 5971 AbstractState &State = ChangedAA->getState(); 5972 if (!State.isAtFixpoint()) { 5973 State.indicatePessimisticFixpoint(); 5974 5975 NumAttributesTimedOut++; 5976 } 5977 5978 auto &QuerriedAAs = QueryMap[ChangedAA]; 5979 ChangedAAs.append(QuerriedAAs.OptionalAAs.begin(), 5980 QuerriedAAs.OptionalAAs.end()); 5981 ChangedAAs.append(QuerriedAAs.RequiredAAs.begin(), 5982 QuerriedAAs.RequiredAAs.end()); 5983 } 5984 5985 LLVM_DEBUG({ 5986 if (!Visited.empty()) 5987 dbgs() << "\n[Attributor] Finalized " << Visited.size() 5988 << " abstract attributes.\n"; 5989 }); 5990 5991 unsigned NumManifested = 0; 5992 unsigned NumAtFixpoint = 0; 5993 ChangeStatus ManifestChange = ChangeStatus::UNCHANGED; 5994 for (AbstractAttribute *AA : AllAbstractAttributes) { 5995 AbstractState &State = AA->getState(); 5996 5997 // If there is not already a fixpoint reached, we can now take the 5998 // optimistic state. This is correct because we enforced a pessimistic one 5999 // on abstract attributes that were transitively dependent on a changed one 6000 // already above. 6001 if (!State.isAtFixpoint()) 6002 State.indicateOptimisticFixpoint(); 6003 6004 // If the state is invalid, we do not try to manifest it. 6005 if (!State.isValidState()) 6006 continue; 6007 6008 // Skip dead code. 6009 if (isAssumedDead(*AA, nullptr)) 6010 continue; 6011 // Manifest the state and record if we changed the IR. 6012 ChangeStatus LocalChange = AA->manifest(*this); 6013 if (LocalChange == ChangeStatus::CHANGED && AreStatisticsEnabled()) 6014 AA->trackStatistics(); 6015 6016 ManifestChange = ManifestChange | LocalChange; 6017 6018 NumAtFixpoint++; 6019 NumManifested += (LocalChange == ChangeStatus::CHANGED); 6020 } 6021 6022 (void)NumManifested; 6023 (void)NumAtFixpoint; 6024 LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested 6025 << " arguments while " << NumAtFixpoint 6026 << " were in a valid fixpoint state\n"); 6027 6028 NumAttributesManifested += NumManifested; 6029 NumAttributesValidFixpoint += NumAtFixpoint; 6030 6031 (void)NumFinalAAs; 6032 assert( 6033 NumFinalAAs == AllAbstractAttributes.size() && 6034 "Expected the final number of abstract attributes to remain unchanged!"); 6035 6036 // Delete stuff at the end to avoid invalid references and a nice order. 6037 { 6038 LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least " 6039 << ToBeDeletedFunctions.size() << " functions and " 6040 << ToBeDeletedBlocks.size() << " blocks and " 6041 << ToBeDeletedInsts.size() << " instructions and " 6042 << ToBeChangedUses.size() << " uses\n"); 6043 6044 SmallVector<Instruction *, 32> DeadInsts; 6045 SmallVector<Instruction *, 32> TerminatorsToFold; 6046 6047 for (auto &It : ToBeChangedUses) { 6048 Use *U = It.first; 6049 Value *NewV = It.second; 6050 Value *OldV = U->get(); 6051 LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser() 6052 << " instead of " << *OldV << "\n"); 6053 U->set(NewV); 6054 if (Instruction *I = dyn_cast<Instruction>(OldV)) 6055 if (!isa<PHINode>(I) && !ToBeDeletedInsts.count(I) && 6056 isInstructionTriviallyDead(I)) { 6057 DeadInsts.push_back(I); 6058 } 6059 if (isa<Constant>(NewV) && isa<BranchInst>(U->getUser())) { 6060 Instruction *UserI = cast<Instruction>(U->getUser()); 6061 if (isa<UndefValue>(NewV)) { 6062 ToBeChangedToUnreachableInsts.insert(UserI); 6063 } else { 6064 TerminatorsToFold.push_back(UserI); 6065 } 6066 } 6067 } 6068 for (auto &V : InvokeWithDeadSuccessor) 6069 if (InvokeInst *II = dyn_cast_or_null<InvokeInst>(V)) { 6070 bool UnwindBBIsDead = II->hasFnAttr(Attribute::NoUnwind); 6071 bool NormalBBIsDead = II->hasFnAttr(Attribute::NoReturn); 6072 bool Invoke2CallAllowed = 6073 !AAIsDeadFunction::mayCatchAsynchronousExceptions( 6074 *II->getFunction()); 6075 assert((UnwindBBIsDead || NormalBBIsDead) && 6076 "Invoke does not have dead successors!"); 6077 BasicBlock *BB = II->getParent(); 6078 BasicBlock *NormalDestBB = II->getNormalDest(); 6079 if (UnwindBBIsDead) { 6080 Instruction *NormalNextIP = &NormalDestBB->front(); 6081 if (Invoke2CallAllowed) { 6082 changeToCall(II); 6083 NormalNextIP = BB->getTerminator(); 6084 } 6085 if (NormalBBIsDead) 6086 ToBeChangedToUnreachableInsts.insert(NormalNextIP); 6087 } else { 6088 assert(NormalBBIsDead && "Broken invariant!"); 6089 if (!NormalDestBB->getUniquePredecessor()) 6090 NormalDestBB = SplitBlockPredecessors(NormalDestBB, {BB}, ".dead"); 6091 ToBeChangedToUnreachableInsts.insert(&NormalDestBB->front()); 6092 } 6093 } 6094 for (auto &V : ToBeChangedToUnreachableInsts) 6095 if (Instruction *I = dyn_cast_or_null<Instruction>(V)) 6096 changeToUnreachable(I, /* UseLLVMTrap */ false); 6097 for (Instruction *I : TerminatorsToFold) 6098 ConstantFoldTerminator(I->getParent()); 6099 6100 for (Instruction *I : ToBeDeletedInsts) { 6101 I->replaceAllUsesWith(UndefValue::get(I->getType())); 6102 if (!isa<PHINode>(I) && isInstructionTriviallyDead(I)) 6103 DeadInsts.push_back(I); 6104 else 6105 I->eraseFromParent(); 6106 } 6107 6108 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts); 6109 6110 if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) { 6111 SmallVector<BasicBlock *, 8> ToBeDeletedBBs; 6112 ToBeDeletedBBs.reserve(NumDeadBlocks); 6113 ToBeDeletedBBs.append(ToBeDeletedBlocks.begin(), ToBeDeletedBlocks.end()); 6114 // Actually we do not delete the blocks but squash them into a single 6115 // unreachable but untangling branches that jump here is something we need 6116 // to do in a more generic way. 6117 DetatchDeadBlocks(ToBeDeletedBBs, nullptr); 6118 STATS_DECL(AAIsDead, BasicBlock, "Number of dead basic blocks deleted."); 6119 BUILD_STAT_NAME(AAIsDead, BasicBlock) += ToBeDeletedBlocks.size(); 6120 } 6121 6122 // Identify dead internal functions and delete them. This happens outside 6123 // the other fixpoint analysis as we might treat potentially dead functions 6124 // as live to lower the number of iterations. If they happen to be dead, the 6125 // below fixpoint loop will identify and eliminate them. 6126 SmallVector<Function *, 8> InternalFns; 6127 for (Function &F : M) 6128 if (F.hasLocalLinkage()) 6129 InternalFns.push_back(&F); 6130 6131 bool FoundDeadFn = true; 6132 while (FoundDeadFn) { 6133 FoundDeadFn = false; 6134 for (unsigned u = 0, e = InternalFns.size(); u < e; ++u) { 6135 Function *F = InternalFns[u]; 6136 if (!F) 6137 continue; 6138 6139 if (!checkForAllCallSites( 6140 [this](AbstractCallSite ACS) { 6141 return ToBeDeletedFunctions.count( 6142 ACS.getInstruction()->getFunction()); 6143 }, 6144 *F, true, nullptr)) 6145 continue; 6146 6147 ToBeDeletedFunctions.insert(F); 6148 InternalFns[u] = nullptr; 6149 FoundDeadFn = true; 6150 } 6151 } 6152 } 6153 6154 STATS_DECL(AAIsDead, Function, "Number of dead functions deleted."); 6155 BUILD_STAT_NAME(AAIsDead, Function) += ToBeDeletedFunctions.size(); 6156 6157 // Rewrite the functions as requested during manifest. 6158 ManifestChange = ManifestChange | rewriteFunctionSignatures(); 6159 6160 for (Function *Fn : ToBeDeletedFunctions) { 6161 Fn->deleteBody(); 6162 Fn->replaceAllUsesWith(UndefValue::get(Fn->getType())); 6163 Fn->eraseFromParent(); 6164 } 6165 6166 if (VerifyMaxFixpointIterations && 6167 IterationCounter != MaxFixpointIterations) { 6168 errs() << "\n[Attributor] Fixpoint iteration done after: " 6169 << IterationCounter << "/" << MaxFixpointIterations 6170 << " iterations\n"; 6171 llvm_unreachable("The fixpoint was not reached with exactly the number of " 6172 "specified iterations!"); 6173 } 6174 6175 return ManifestChange; 6176 } 6177 6178 bool Attributor::registerFunctionSignatureRewrite( 6179 Argument &Arg, ArrayRef<Type *> ReplacementTypes, 6180 ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB, 6181 ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB) { 6182 6183 auto CallSiteCanBeChanged = [](AbstractCallSite ACS) { 6184 // Forbid must-tail calls for now. 6185 return !ACS.isCallbackCall() && !ACS.getCallSite().isMustTailCall(); 6186 }; 6187 6188 Function *Fn = Arg.getParent(); 6189 // Avoid var-arg functions for now. 6190 if (Fn->isVarArg()) { 6191 LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite var-args functions\n"); 6192 return false; 6193 } 6194 6195 // Avoid functions with complicated argument passing semantics. 6196 AttributeList FnAttributeList = Fn->getAttributes(); 6197 if (FnAttributeList.hasAttrSomewhere(Attribute::Nest) || 6198 FnAttributeList.hasAttrSomewhere(Attribute::StructRet) || 6199 FnAttributeList.hasAttrSomewhere(Attribute::InAlloca)) { 6200 LLVM_DEBUG( 6201 dbgs() << "[Attributor] Cannot rewrite due to complex attribute\n"); 6202 return false; 6203 } 6204 6205 // Avoid callbacks for now. 6206 if (!checkForAllCallSites(CallSiteCanBeChanged, *Fn, true, nullptr)) { 6207 LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite all call sites\n"); 6208 return false; 6209 } 6210 6211 auto InstPred = [](Instruction &I) { 6212 if (auto *CI = dyn_cast<CallInst>(&I)) 6213 return !CI->isMustTailCall(); 6214 return true; 6215 }; 6216 6217 // Forbid must-tail calls for now. 6218 // TODO: 6219 bool AnyDead; 6220 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(*Fn); 6221 if (!checkForAllInstructionsImpl(OpcodeInstMap, InstPred, nullptr, AnyDead, 6222 {Instruction::Call})) { 6223 LLVM_DEBUG(dbgs() << "[Attributor] Cannot rewrite due to instructions\n"); 6224 return false; 6225 } 6226 6227 SmallVectorImpl<ArgumentReplacementInfo *> &ARIs = ArgumentReplacementMap[Fn]; 6228 if (ARIs.size() == 0) 6229 ARIs.resize(Fn->arg_size()); 6230 6231 // If we have a replacement already with less than or equal new arguments, 6232 // ignore this request. 6233 ArgumentReplacementInfo *&ARI = ARIs[Arg.getArgNo()]; 6234 if (ARI && ARI->getNumReplacementArgs() <= ReplacementTypes.size()) { 6235 LLVM_DEBUG(dbgs() << "[Attributor] Existing rewrite is preferred\n"); 6236 return false; 6237 } 6238 6239 // If we have a replacement already but we like the new one better, delete 6240 // the old. 6241 if (ARI) 6242 delete ARI; 6243 6244 // Remember the replacement. 6245 ARI = new ArgumentReplacementInfo(*this, Arg, ReplacementTypes, 6246 std::move(CalleeRepairCB), 6247 std::move(ACSRepairCB)); 6248 6249 return true; 6250 } 6251 6252 ChangeStatus Attributor::rewriteFunctionSignatures() { 6253 ChangeStatus Changed = ChangeStatus::UNCHANGED; 6254 6255 for (auto &It : ArgumentReplacementMap) { 6256 Function *OldFn = It.getFirst(); 6257 6258 // Deleted functions do not require rewrites. 6259 if (ToBeDeletedFunctions.count(OldFn)) 6260 continue; 6261 6262 const SmallVectorImpl<ArgumentReplacementInfo *> &ARIs = It.getSecond(); 6263 assert(ARIs.size() == OldFn->arg_size() && "Inconsistent state!"); 6264 6265 SmallVector<Type *, 16> NewArgumentTypes; 6266 SmallVector<AttributeSet, 16> NewArgumentAttributes; 6267 6268 // Collect replacement argument types and copy over existing attributes. 6269 AttributeList OldFnAttributeList = OldFn->getAttributes(); 6270 for (Argument &Arg : OldFn->args()) { 6271 if (ArgumentReplacementInfo *ARI = ARIs[Arg.getArgNo()]) { 6272 NewArgumentTypes.append(ARI->ReplacementTypes.begin(), 6273 ARI->ReplacementTypes.end()); 6274 NewArgumentAttributes.append(ARI->getNumReplacementArgs(), 6275 AttributeSet()); 6276 } else { 6277 NewArgumentTypes.push_back(Arg.getType()); 6278 NewArgumentAttributes.push_back( 6279 OldFnAttributeList.getParamAttributes(Arg.getArgNo())); 6280 } 6281 } 6282 6283 FunctionType *OldFnTy = OldFn->getFunctionType(); 6284 Type *RetTy = OldFnTy->getReturnType(); 6285 6286 // Construct the new function type using the new arguments types. 6287 FunctionType *NewFnTy = 6288 FunctionType::get(RetTy, NewArgumentTypes, OldFnTy->isVarArg()); 6289 6290 LLVM_DEBUG(dbgs() << "[Attributor] Function rewrite '" << OldFn->getName() 6291 << "' from " << *OldFn->getFunctionType() << " to " 6292 << *NewFnTy << "\n"); 6293 6294 // Create the new function body and insert it into the module. 6295 Function *NewFn = Function::Create(NewFnTy, OldFn->getLinkage(), 6296 OldFn->getAddressSpace(), ""); 6297 OldFn->getParent()->getFunctionList().insert(OldFn->getIterator(), NewFn); 6298 NewFn->takeName(OldFn); 6299 NewFn->copyAttributesFrom(OldFn); 6300 6301 // Patch the pointer to LLVM function in debug info descriptor. 6302 NewFn->setSubprogram(OldFn->getSubprogram()); 6303 OldFn->setSubprogram(nullptr); 6304 6305 // Recompute the parameter attributes list based on the new arguments for 6306 // the function. 6307 LLVMContext &Ctx = OldFn->getContext(); 6308 NewFn->setAttributes(AttributeList::get( 6309 Ctx, OldFnAttributeList.getFnAttributes(), 6310 OldFnAttributeList.getRetAttributes(), NewArgumentAttributes)); 6311 6312 // Since we have now created the new function, splice the body of the old 6313 // function right into the new function, leaving the old rotting hulk of the 6314 // function empty. 6315 NewFn->getBasicBlockList().splice(NewFn->begin(), 6316 OldFn->getBasicBlockList()); 6317 6318 // Set of all "call-like" instructions that invoke the old function mapped 6319 // to their new replacements. 6320 SmallVector<std::pair<CallBase *, CallBase *>, 8> CallSitePairs; 6321 6322 // Callback to create a new "call-like" instruction for a given one. 6323 auto CallSiteReplacementCreator = [&](AbstractCallSite ACS) { 6324 CallBase *OldCB = cast<CallBase>(ACS.getInstruction()); 6325 const AttributeList &OldCallAttributeList = OldCB->getAttributes(); 6326 6327 // Collect the new argument operands for the replacement call site. 6328 SmallVector<Value *, 16> NewArgOperands; 6329 SmallVector<AttributeSet, 16> NewArgOperandAttributes; 6330 for (unsigned OldArgNum = 0; OldArgNum < ARIs.size(); ++OldArgNum) { 6331 unsigned NewFirstArgNum = NewArgOperands.size(); 6332 (void)NewFirstArgNum; // only used inside assert. 6333 if (ArgumentReplacementInfo *ARI = ARIs[OldArgNum]) { 6334 if (ARI->ACSRepairCB) 6335 ARI->ACSRepairCB(*ARI, ACS, NewArgOperands); 6336 assert(ARI->getNumReplacementArgs() + NewFirstArgNum == 6337 NewArgOperands.size() && 6338 "ACS repair callback did not provide as many operand as new " 6339 "types were registered!"); 6340 // TODO: Exose the attribute set to the ACS repair callback 6341 NewArgOperandAttributes.append(ARI->ReplacementTypes.size(), 6342 AttributeSet()); 6343 } else { 6344 NewArgOperands.push_back(ACS.getCallArgOperand(OldArgNum)); 6345 NewArgOperandAttributes.push_back( 6346 OldCallAttributeList.getParamAttributes(OldArgNum)); 6347 } 6348 } 6349 6350 assert(NewArgOperands.size() == NewArgOperandAttributes.size() && 6351 "Mismatch # argument operands vs. # argument operand attributes!"); 6352 assert(NewArgOperands.size() == NewFn->arg_size() && 6353 "Mismatch # argument operands vs. # function arguments!"); 6354 6355 SmallVector<OperandBundleDef, 4> OperandBundleDefs; 6356 OldCB->getOperandBundlesAsDefs(OperandBundleDefs); 6357 6358 // Create a new call or invoke instruction to replace the old one. 6359 CallBase *NewCB; 6360 if (InvokeInst *II = dyn_cast<InvokeInst>(OldCB)) { 6361 NewCB = 6362 InvokeInst::Create(NewFn, II->getNormalDest(), II->getUnwindDest(), 6363 NewArgOperands, OperandBundleDefs, "", OldCB); 6364 } else { 6365 auto *NewCI = CallInst::Create(NewFn, NewArgOperands, OperandBundleDefs, 6366 "", OldCB); 6367 NewCI->setTailCallKind(cast<CallInst>(OldCB)->getTailCallKind()); 6368 NewCB = NewCI; 6369 } 6370 6371 // Copy over various properties and the new attributes. 6372 uint64_t W; 6373 if (OldCB->extractProfTotalWeight(W)) 6374 NewCB->setProfWeight(W); 6375 NewCB->setCallingConv(OldCB->getCallingConv()); 6376 NewCB->setDebugLoc(OldCB->getDebugLoc()); 6377 NewCB->takeName(OldCB); 6378 NewCB->setAttributes(AttributeList::get( 6379 Ctx, OldCallAttributeList.getFnAttributes(), 6380 OldCallAttributeList.getRetAttributes(), NewArgOperandAttributes)); 6381 6382 CallSitePairs.push_back({OldCB, NewCB}); 6383 return true; 6384 }; 6385 6386 // Use the CallSiteReplacementCreator to create replacement call sites. 6387 bool Success = 6388 checkForAllCallSites(CallSiteReplacementCreator, *OldFn, true, nullptr); 6389 (void)Success; 6390 assert(Success && "Assumed call site replacement to succeed!"); 6391 6392 // Rewire the arguments. 6393 auto OldFnArgIt = OldFn->arg_begin(); 6394 auto NewFnArgIt = NewFn->arg_begin(); 6395 for (unsigned OldArgNum = 0; OldArgNum < ARIs.size(); 6396 ++OldArgNum, ++OldFnArgIt) { 6397 if (ArgumentReplacementInfo *ARI = ARIs[OldArgNum]) { 6398 if (ARI->CalleeRepairCB) 6399 ARI->CalleeRepairCB(*ARI, *NewFn, NewFnArgIt); 6400 NewFnArgIt += ARI->ReplacementTypes.size(); 6401 } else { 6402 NewFnArgIt->takeName(&*OldFnArgIt); 6403 OldFnArgIt->replaceAllUsesWith(&*NewFnArgIt); 6404 ++NewFnArgIt; 6405 } 6406 } 6407 6408 // Eliminate the instructions *after* we visited all of them. 6409 for (auto &CallSitePair : CallSitePairs) { 6410 CallBase &OldCB = *CallSitePair.first; 6411 CallBase &NewCB = *CallSitePair.second; 6412 OldCB.replaceAllUsesWith(&NewCB); 6413 OldCB.eraseFromParent(); 6414 } 6415 6416 ToBeDeletedFunctions.insert(OldFn); 6417 6418 Changed = ChangeStatus::CHANGED; 6419 } 6420 6421 return Changed; 6422 } 6423 6424 void Attributor::initializeInformationCache(Function &F) { 6425 6426 // Walk all instructions to find interesting instructions that might be 6427 // queried by abstract attributes during their initialization or update. 6428 // This has to happen before we create attributes. 6429 auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F]; 6430 auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F]; 6431 6432 for (Instruction &I : instructions(&F)) { 6433 bool IsInterestingOpcode = false; 6434 6435 // To allow easy access to all instructions in a function with a given 6436 // opcode we store them in the InfoCache. As not all opcodes are interesting 6437 // to concrete attributes we only cache the ones that are as identified in 6438 // the following switch. 6439 // Note: There are no concrete attributes now so this is initially empty. 6440 switch (I.getOpcode()) { 6441 default: 6442 assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) && 6443 "New call site/base instruction type needs to be known int the " 6444 "Attributor."); 6445 break; 6446 case Instruction::Load: 6447 // The alignment of a pointer is interesting for loads. 6448 case Instruction::Store: 6449 // The alignment of a pointer is interesting for stores. 6450 case Instruction::Call: 6451 case Instruction::CallBr: 6452 case Instruction::Invoke: 6453 case Instruction::CleanupRet: 6454 case Instruction::CatchSwitch: 6455 case Instruction::AtomicRMW: 6456 case Instruction::AtomicCmpXchg: 6457 case Instruction::Br: 6458 case Instruction::Resume: 6459 case Instruction::Ret: 6460 IsInterestingOpcode = true; 6461 } 6462 if (IsInterestingOpcode) 6463 InstOpcodeMap[I.getOpcode()].push_back(&I); 6464 if (I.mayReadOrWriteMemory()) 6465 ReadOrWriteInsts.push_back(&I); 6466 } 6467 } 6468 6469 void Attributor::recordDependence(const AbstractAttribute &FromAA, 6470 const AbstractAttribute &ToAA, 6471 DepClassTy DepClass) { 6472 if (FromAA.getState().isAtFixpoint()) 6473 return; 6474 6475 if (DepClass == DepClassTy::REQUIRED) 6476 QueryMap[&FromAA].RequiredAAs.insert( 6477 const_cast<AbstractAttribute *>(&ToAA)); 6478 else 6479 QueryMap[&FromAA].OptionalAAs.insert( 6480 const_cast<AbstractAttribute *>(&ToAA)); 6481 QueriedNonFixAA = true; 6482 } 6483 6484 void Attributor::identifyDefaultAbstractAttributes(Function &F) { 6485 if (!VisitedFunctions.insert(&F).second) 6486 return; 6487 if (F.isDeclaration()) 6488 return; 6489 6490 IRPosition FPos = IRPosition::function(F); 6491 6492 // Check for dead BasicBlocks in every function. 6493 // We need dead instruction detection because we do not want to deal with 6494 // broken IR in which SSA rules do not apply. 6495 getOrCreateAAFor<AAIsDead>(FPos); 6496 6497 // Every function might be "will-return". 6498 getOrCreateAAFor<AAWillReturn>(FPos); 6499 6500 // Every function might contain instructions that cause "undefined behavior". 6501 getOrCreateAAFor<AAUndefinedBehavior>(FPos); 6502 6503 // Every function can be nounwind. 6504 getOrCreateAAFor<AANoUnwind>(FPos); 6505 6506 // Every function might be marked "nosync" 6507 getOrCreateAAFor<AANoSync>(FPos); 6508 6509 // Every function might be "no-free". 6510 getOrCreateAAFor<AANoFree>(FPos); 6511 6512 // Every function might be "no-return". 6513 getOrCreateAAFor<AANoReturn>(FPos); 6514 6515 // Every function might be "no-recurse". 6516 getOrCreateAAFor<AANoRecurse>(FPos); 6517 6518 // Every function might be "readnone/readonly/writeonly/...". 6519 getOrCreateAAFor<AAMemoryBehavior>(FPos); 6520 6521 // Every function might be applicable for Heap-To-Stack conversion. 6522 if (EnableHeapToStack) 6523 getOrCreateAAFor<AAHeapToStack>(FPos); 6524 6525 // Return attributes are only appropriate if the return type is non void. 6526 Type *ReturnType = F.getReturnType(); 6527 if (!ReturnType->isVoidTy()) { 6528 // Argument attribute "returned" --- Create only one per function even 6529 // though it is an argument attribute. 6530 getOrCreateAAFor<AAReturnedValues>(FPos); 6531 6532 IRPosition RetPos = IRPosition::returned(F); 6533 6534 // Every returned value might be dead. 6535 getOrCreateAAFor<AAIsDead>(RetPos); 6536 6537 // Every function might be simplified. 6538 getOrCreateAAFor<AAValueSimplify>(RetPos); 6539 6540 if (ReturnType->isPointerTy()) { 6541 6542 // Every function with pointer return type might be marked align. 6543 getOrCreateAAFor<AAAlign>(RetPos); 6544 6545 // Every function with pointer return type might be marked nonnull. 6546 getOrCreateAAFor<AANonNull>(RetPos); 6547 6548 // Every function with pointer return type might be marked noalias. 6549 getOrCreateAAFor<AANoAlias>(RetPos); 6550 6551 // Every function with pointer return type might be marked 6552 // dereferenceable. 6553 getOrCreateAAFor<AADereferenceable>(RetPos); 6554 } 6555 } 6556 6557 for (Argument &Arg : F.args()) { 6558 IRPosition ArgPos = IRPosition::argument(Arg); 6559 6560 // Every argument might be simplified. 6561 getOrCreateAAFor<AAValueSimplify>(ArgPos); 6562 6563 if (Arg.getType()->isPointerTy()) { 6564 // Every argument with pointer type might be marked nonnull. 6565 getOrCreateAAFor<AANonNull>(ArgPos); 6566 6567 // Every argument with pointer type might be marked noalias. 6568 getOrCreateAAFor<AANoAlias>(ArgPos); 6569 6570 // Every argument with pointer type might be marked dereferenceable. 6571 getOrCreateAAFor<AADereferenceable>(ArgPos); 6572 6573 // Every argument with pointer type might be marked align. 6574 getOrCreateAAFor<AAAlign>(ArgPos); 6575 6576 // Every argument with pointer type might be marked nocapture. 6577 getOrCreateAAFor<AANoCapture>(ArgPos); 6578 6579 // Every argument with pointer type might be marked 6580 // "readnone/readonly/writeonly/..." 6581 getOrCreateAAFor<AAMemoryBehavior>(ArgPos); 6582 6583 // Every argument with pointer type might be marked nofree. 6584 getOrCreateAAFor<AANoFree>(ArgPos); 6585 } 6586 } 6587 6588 auto CallSitePred = [&](Instruction &I) -> bool { 6589 CallSite CS(&I); 6590 if (Function *Callee = CS.getCalledFunction()) { 6591 // Skip declerations except if annotations on their call sites were 6592 // explicitly requested. 6593 if (!AnnotateDeclarationCallSites && Callee->isDeclaration() && 6594 !Callee->hasMetadata(LLVMContext::MD_callback)) 6595 return true; 6596 6597 if (!Callee->getReturnType()->isVoidTy() && !CS->use_empty()) { 6598 6599 IRPosition CSRetPos = IRPosition::callsite_returned(CS); 6600 6601 // Call site return values might be dead. 6602 getOrCreateAAFor<AAIsDead>(CSRetPos); 6603 6604 // Call site return integer values might be limited by a constant range. 6605 if (Callee->getReturnType()->isIntegerTy()) { 6606 getOrCreateAAFor<AAValueConstantRange>(CSRetPos); 6607 } 6608 } 6609 6610 for (int i = 0, e = CS.getNumArgOperands(); i < e; i++) { 6611 6612 IRPosition CSArgPos = IRPosition::callsite_argument(CS, i); 6613 6614 // Every call site argument might be dead. 6615 getOrCreateAAFor<AAIsDead>(CSArgPos); 6616 6617 // Call site argument might be simplified. 6618 getOrCreateAAFor<AAValueSimplify>(CSArgPos); 6619 6620 if (!CS.getArgument(i)->getType()->isPointerTy()) 6621 continue; 6622 6623 // Call site argument attribute "non-null". 6624 getOrCreateAAFor<AANonNull>(CSArgPos); 6625 6626 // Call site argument attribute "no-alias". 6627 getOrCreateAAFor<AANoAlias>(CSArgPos); 6628 6629 // Call site argument attribute "dereferenceable". 6630 getOrCreateAAFor<AADereferenceable>(CSArgPos); 6631 6632 // Call site argument attribute "align". 6633 getOrCreateAAFor<AAAlign>(CSArgPos); 6634 6635 // Call site argument attribute 6636 // "readnone/readonly/writeonly/..." 6637 getOrCreateAAFor<AAMemoryBehavior>(CSArgPos); 6638 6639 // Call site argument attribute "nofree". 6640 getOrCreateAAFor<AANoFree>(CSArgPos); 6641 } 6642 } 6643 return true; 6644 }; 6645 6646 auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); 6647 bool Success, AnyDead = false; 6648 Success = checkForAllInstructionsImpl( 6649 OpcodeInstMap, CallSitePred, nullptr, AnyDead, 6650 {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, 6651 (unsigned)Instruction::Call}); 6652 (void)Success; 6653 assert(Success && !AnyDead && "Expected the check call to be successful!"); 6654 6655 auto LoadStorePred = [&](Instruction &I) -> bool { 6656 if (isa<LoadInst>(I)) 6657 getOrCreateAAFor<AAAlign>( 6658 IRPosition::value(*cast<LoadInst>(I).getPointerOperand())); 6659 else 6660 getOrCreateAAFor<AAAlign>( 6661 IRPosition::value(*cast<StoreInst>(I).getPointerOperand())); 6662 return true; 6663 }; 6664 Success = checkForAllInstructionsImpl( 6665 OpcodeInstMap, LoadStorePred, nullptr, AnyDead, 6666 {(unsigned)Instruction::Load, (unsigned)Instruction::Store}); 6667 (void)Success; 6668 assert(Success && !AnyDead && "Expected the check call to be successful!"); 6669 } 6670 6671 /// Helpers to ease debugging through output streams and print calls. 6672 /// 6673 ///{ 6674 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) { 6675 return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged"); 6676 } 6677 6678 raw_ostream &llvm::operator<<(raw_ostream &OS, IRPosition::Kind AP) { 6679 switch (AP) { 6680 case IRPosition::IRP_INVALID: 6681 return OS << "inv"; 6682 case IRPosition::IRP_FLOAT: 6683 return OS << "flt"; 6684 case IRPosition::IRP_RETURNED: 6685 return OS << "fn_ret"; 6686 case IRPosition::IRP_CALL_SITE_RETURNED: 6687 return OS << "cs_ret"; 6688 case IRPosition::IRP_FUNCTION: 6689 return OS << "fn"; 6690 case IRPosition::IRP_CALL_SITE: 6691 return OS << "cs"; 6692 case IRPosition::IRP_ARGUMENT: 6693 return OS << "arg"; 6694 case IRPosition::IRP_CALL_SITE_ARGUMENT: 6695 return OS << "cs_arg"; 6696 } 6697 llvm_unreachable("Unknown attribute position!"); 6698 } 6699 6700 raw_ostream &llvm::operator<<(raw_ostream &OS, const IRPosition &Pos) { 6701 const Value &AV = Pos.getAssociatedValue(); 6702 return OS << "{" << Pos.getPositionKind() << ":" << AV.getName() << " [" 6703 << Pos.getAnchorValue().getName() << "@" << Pos.getArgNo() << "]}"; 6704 } 6705 6706 template <typename base_ty, base_ty BestState, base_ty WorstState> 6707 raw_ostream & 6708 llvm::operator<<(raw_ostream &OS, 6709 const IntegerStateBase<base_ty, BestState, WorstState> &S) { 6710 return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")" 6711 << static_cast<const AbstractState &>(S); 6712 } 6713 6714 raw_ostream &llvm::operator<<(raw_ostream &OS, const IntegerRangeState &S) { 6715 OS << "range-state(" << S.getBitWidth() << ")<"; 6716 S.getKnown().print(OS); 6717 OS << " / "; 6718 S.getAssumed().print(OS); 6719 OS << ">"; 6720 6721 return OS << static_cast<const AbstractState &>(S); 6722 } 6723 6724 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) { 6725 return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : "")); 6726 } 6727 6728 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) { 6729 AA.print(OS); 6730 return OS; 6731 } 6732 6733 void AbstractAttribute::print(raw_ostream &OS) const { 6734 OS << "[P: " << getIRPosition() << "][" << getAsStr() << "][S: " << getState() 6735 << "]"; 6736 } 6737 ///} 6738 6739 /// ---------------------------------------------------------------------------- 6740 /// Pass (Manager) Boilerplate 6741 /// ---------------------------------------------------------------------------- 6742 6743 static bool runAttributorOnModule(Module &M, AnalysisGetter &AG) { 6744 if (DisableAttributor) 6745 return false; 6746 6747 LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size() 6748 << " functions.\n"); 6749 6750 // Create an Attributor and initially empty information cache that is filled 6751 // while we identify default attribute opportunities. 6752 InformationCache InfoCache(M, AG); 6753 Attributor A(InfoCache, DepRecInterval); 6754 6755 for (Function &F : M) 6756 A.initializeInformationCache(F); 6757 6758 for (Function &F : M) { 6759 if (F.hasExactDefinition()) 6760 NumFnWithExactDefinition++; 6761 else 6762 NumFnWithoutExactDefinition++; 6763 6764 // We look at internal functions only on-demand but if any use is not a 6765 // direct call, we have to do it eagerly. 6766 if (F.hasLocalLinkage()) { 6767 if (llvm::all_of(F.uses(), [](const Use &U) { 6768 return ImmutableCallSite(U.getUser()) && 6769 ImmutableCallSite(U.getUser()).isCallee(&U); 6770 })) 6771 continue; 6772 } 6773 6774 // Populate the Attributor with abstract attribute opportunities in the 6775 // function and the information cache with IR information. 6776 A.identifyDefaultAbstractAttributes(F); 6777 } 6778 6779 bool Changed = A.run(M) == ChangeStatus::CHANGED; 6780 assert(!verifyModule(M, &errs()) && "Module verification failed!"); 6781 return Changed; 6782 } 6783 6784 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) { 6785 AnalysisGetter AG(AM); 6786 if (runAttributorOnModule(M, AG)) { 6787 // FIXME: Think about passes we will preserve and add them here. 6788 return PreservedAnalyses::none(); 6789 } 6790 return PreservedAnalyses::all(); 6791 } 6792 6793 namespace { 6794 6795 struct AttributorLegacyPass : public ModulePass { 6796 static char ID; 6797 6798 AttributorLegacyPass() : ModulePass(ID) { 6799 initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry()); 6800 } 6801 6802 bool runOnModule(Module &M) override { 6803 if (skipModule(M)) 6804 return false; 6805 6806 AnalysisGetter AG; 6807 return runAttributorOnModule(M, AG); 6808 } 6809 6810 void getAnalysisUsage(AnalysisUsage &AU) const override { 6811 // FIXME: Think about passes we will preserve and add them here. 6812 AU.addRequired<TargetLibraryInfoWrapperPass>(); 6813 } 6814 }; 6815 6816 } // end anonymous namespace 6817 6818 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); } 6819 6820 char AttributorLegacyPass::ID = 0; 6821 6822 const char AAReturnedValues::ID = 0; 6823 const char AANoUnwind::ID = 0; 6824 const char AANoSync::ID = 0; 6825 const char AANoFree::ID = 0; 6826 const char AANonNull::ID = 0; 6827 const char AANoRecurse::ID = 0; 6828 const char AAWillReturn::ID = 0; 6829 const char AAUndefinedBehavior::ID = 0; 6830 const char AANoAlias::ID = 0; 6831 const char AAReachability::ID = 0; 6832 const char AANoReturn::ID = 0; 6833 const char AAIsDead::ID = 0; 6834 const char AADereferenceable::ID = 0; 6835 const char AAAlign::ID = 0; 6836 const char AANoCapture::ID = 0; 6837 const char AAValueSimplify::ID = 0; 6838 const char AAHeapToStack::ID = 0; 6839 const char AAMemoryBehavior::ID = 0; 6840 const char AAValueConstantRange::ID = 0; 6841 6842 // Macro magic to create the static generator function for attributes that 6843 // follow the naming scheme. 6844 6845 #define SWITCH_PK_INV(CLASS, PK, POS_NAME) \ 6846 case IRPosition::PK: \ 6847 llvm_unreachable("Cannot create " #CLASS " for a " POS_NAME " position!"); 6848 6849 #define SWITCH_PK_CREATE(CLASS, IRP, PK, SUFFIX) \ 6850 case IRPosition::PK: \ 6851 AA = new CLASS##SUFFIX(IRP); \ 6852 break; 6853 6854 #define CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS) \ 6855 CLASS &CLASS::createForPosition(const IRPosition &IRP, Attributor &A) { \ 6856 CLASS *AA = nullptr; \ 6857 switch (IRP.getPositionKind()) { \ 6858 SWITCH_PK_INV(CLASS, IRP_INVALID, "invalid") \ 6859 SWITCH_PK_INV(CLASS, IRP_FLOAT, "floating") \ 6860 SWITCH_PK_INV(CLASS, IRP_ARGUMENT, "argument") \ 6861 SWITCH_PK_INV(CLASS, IRP_RETURNED, "returned") \ 6862 SWITCH_PK_INV(CLASS, IRP_CALL_SITE_RETURNED, "call site returned") \ 6863 SWITCH_PK_INV(CLASS, IRP_CALL_SITE_ARGUMENT, "call site argument") \ 6864 SWITCH_PK_CREATE(CLASS, IRP, IRP_FUNCTION, Function) \ 6865 SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE, CallSite) \ 6866 } \ 6867 return *AA; \ 6868 } 6869 6870 #define CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS) \ 6871 CLASS &CLASS::createForPosition(const IRPosition &IRP, Attributor &A) { \ 6872 CLASS *AA = nullptr; \ 6873 switch (IRP.getPositionKind()) { \ 6874 SWITCH_PK_INV(CLASS, IRP_INVALID, "invalid") \ 6875 SWITCH_PK_INV(CLASS, IRP_FUNCTION, "function") \ 6876 SWITCH_PK_INV(CLASS, IRP_CALL_SITE, "call site") \ 6877 SWITCH_PK_CREATE(CLASS, IRP, IRP_FLOAT, Floating) \ 6878 SWITCH_PK_CREATE(CLASS, IRP, IRP_ARGUMENT, Argument) \ 6879 SWITCH_PK_CREATE(CLASS, IRP, IRP_RETURNED, Returned) \ 6880 SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_RETURNED, CallSiteReturned) \ 6881 SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_ARGUMENT, CallSiteArgument) \ 6882 } \ 6883 return *AA; \ 6884 } 6885 6886 #define CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS) \ 6887 CLASS &CLASS::createForPosition(const IRPosition &IRP, Attributor &A) { \ 6888 CLASS *AA = nullptr; \ 6889 switch (IRP.getPositionKind()) { \ 6890 SWITCH_PK_INV(CLASS, IRP_INVALID, "invalid") \ 6891 SWITCH_PK_CREATE(CLASS, IRP, IRP_FUNCTION, Function) \ 6892 SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE, CallSite) \ 6893 SWITCH_PK_CREATE(CLASS, IRP, IRP_FLOAT, Floating) \ 6894 SWITCH_PK_CREATE(CLASS, IRP, IRP_ARGUMENT, Argument) \ 6895 SWITCH_PK_CREATE(CLASS, IRP, IRP_RETURNED, Returned) \ 6896 SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_RETURNED, CallSiteReturned) \ 6897 SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_ARGUMENT, CallSiteArgument) \ 6898 } \ 6899 return *AA; \ 6900 } 6901 6902 #define CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS) \ 6903 CLASS &CLASS::createForPosition(const IRPosition &IRP, Attributor &A) { \ 6904 CLASS *AA = nullptr; \ 6905 switch (IRP.getPositionKind()) { \ 6906 SWITCH_PK_INV(CLASS, IRP_INVALID, "invalid") \ 6907 SWITCH_PK_INV(CLASS, IRP_ARGUMENT, "argument") \ 6908 SWITCH_PK_INV(CLASS, IRP_FLOAT, "floating") \ 6909 SWITCH_PK_INV(CLASS, IRP_RETURNED, "returned") \ 6910 SWITCH_PK_INV(CLASS, IRP_CALL_SITE_RETURNED, "call site returned") \ 6911 SWITCH_PK_INV(CLASS, IRP_CALL_SITE_ARGUMENT, "call site argument") \ 6912 SWITCH_PK_INV(CLASS, IRP_CALL_SITE, "call site") \ 6913 SWITCH_PK_CREATE(CLASS, IRP, IRP_FUNCTION, Function) \ 6914 } \ 6915 return *AA; \ 6916 } 6917 6918 #define CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS) \ 6919 CLASS &CLASS::createForPosition(const IRPosition &IRP, Attributor &A) { \ 6920 CLASS *AA = nullptr; \ 6921 switch (IRP.getPositionKind()) { \ 6922 SWITCH_PK_INV(CLASS, IRP_INVALID, "invalid") \ 6923 SWITCH_PK_INV(CLASS, IRP_RETURNED, "returned") \ 6924 SWITCH_PK_CREATE(CLASS, IRP, IRP_FUNCTION, Function) \ 6925 SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE, CallSite) \ 6926 SWITCH_PK_CREATE(CLASS, IRP, IRP_FLOAT, Floating) \ 6927 SWITCH_PK_CREATE(CLASS, IRP, IRP_ARGUMENT, Argument) \ 6928 SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_RETURNED, CallSiteReturned) \ 6929 SWITCH_PK_CREATE(CLASS, IRP, IRP_CALL_SITE_ARGUMENT, CallSiteArgument) \ 6930 } \ 6931 return *AA; \ 6932 } 6933 6934 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoUnwind) 6935 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoSync) 6936 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoRecurse) 6937 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAWillReturn) 6938 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoReturn) 6939 CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReturnedValues) 6940 6941 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANonNull) 6942 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoAlias) 6943 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AADereferenceable) 6944 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAlign) 6945 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoCapture) 6946 CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueConstantRange) 6947 6948 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify) 6949 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) 6950 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoFree) 6951 6952 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAHeapToStack) 6953 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReachability) 6954 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAUndefinedBehavior) 6955 6956 CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAMemoryBehavior) 6957 6958 #undef CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION 6959 #undef CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION 6960 #undef CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION 6961 #undef CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION 6962 #undef CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION 6963 #undef SWITCH_PK_CREATE 6964 #undef SWITCH_PK_INV 6965 6966 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor", 6967 "Deduce and propagate attributes", false, false) 6968 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 6969 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor", 6970 "Deduce and propagate attributes", false, false) 6971