Attributor.h revision 360784
1//===- Attributor.h --- Module-wide attribute deduction ---------*- C++ -*-===// 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// Attributor: An inter procedural (abstract) "attribute" deduction framework. 10// 11// The Attributor framework is an inter procedural abstract analysis (fixpoint 12// iteration analysis). The goal is to allow easy deduction of new attributes as 13// well as information exchange between abstract attributes in-flight. 14// 15// The Attributor class is the driver and the link between the various abstract 16// attributes. The Attributor will iterate until a fixpoint state is reached by 17// all abstract attributes in-flight, or until it will enforce a pessimistic fix 18// point because an iteration limit is reached. 19// 20// Abstract attributes, derived from the AbstractAttribute class, actually 21// describe properties of the code. They can correspond to actual LLVM-IR 22// attributes, or they can be more general, ultimately unrelated to LLVM-IR 23// attributes. The latter is useful when an abstract attributes provides 24// information to other abstract attributes in-flight but we might not want to 25// manifest the information. The Attributor allows to query in-flight abstract 26// attributes through the `Attributor::getAAFor` method (see the method 27// description for an example). If the method is used by an abstract attribute 28// P, and it results in an abstract attribute Q, the Attributor will 29// automatically capture a potential dependence from Q to P. This dependence 30// will cause P to be reevaluated whenever Q changes in the future. 31// 32// The Attributor will only reevaluated abstract attributes that might have 33// changed since the last iteration. That means that the Attribute will not 34// revisit all instructions/blocks/functions in the module but only query 35// an update from a subset of the abstract attributes. 36// 37// The update method `AbstractAttribute::updateImpl` is implemented by the 38// specific "abstract attribute" subclasses. The method is invoked whenever the 39// currently assumed state (see the AbstractState class) might not be valid 40// anymore. This can, for example, happen if the state was dependent on another 41// abstract attribute that changed. In every invocation, the update method has 42// to adjust the internal state of an abstract attribute to a point that is 43// justifiable by the underlying IR and the current state of abstract attributes 44// in-flight. Since the IR is given and assumed to be valid, the information 45// derived from it can be assumed to hold. However, information derived from 46// other abstract attributes is conditional on various things. If the justifying 47// state changed, the `updateImpl` has to revisit the situation and potentially 48// find another justification or limit the optimistic assumes made. 49// 50// Change is the key in this framework. Until a state of no-change, thus a 51// fixpoint, is reached, the Attributor will query the abstract attributes 52// in-flight to re-evaluate their state. If the (current) state is too 53// optimistic, hence it cannot be justified anymore through other abstract 54// attributes or the state of the IR, the state of the abstract attribute will 55// have to change. Generally, we assume abstract attribute state to be a finite 56// height lattice and the update function to be monotone. However, these 57// conditions are not enforced because the iteration limit will guarantee 58// termination. If an optimistic fixpoint is reached, or a pessimistic fix 59// point is enforced after a timeout, the abstract attributes are tasked to 60// manifest their result in the IR for passes to come. 61// 62// Attribute manifestation is not mandatory. If desired, there is support to 63// generate a single or multiple LLVM-IR attributes already in the helper struct 64// IRAttribute. In the simplest case, a subclass inherits from IRAttribute with 65// a proper Attribute::AttrKind as template parameter. The Attributor 66// manifestation framework will then create and place a new attribute if it is 67// allowed to do so (based on the abstract state). Other use cases can be 68// achieved by overloading AbstractAttribute or IRAttribute methods. 69// 70// 71// The "mechanics" of adding a new "abstract attribute": 72// - Define a class (transitively) inheriting from AbstractAttribute and one 73// (which could be the same) that (transitively) inherits from AbstractState. 74// For the latter, consider the already available BooleanState and 75// {Inc,Dec,Bit}IntegerState if they fit your needs, e.g., you require only a 76// number tracking or bit-encoding. 77// - Implement all pure methods. Also use overloading if the attribute is not 78// conforming with the "default" behavior: A (set of) LLVM-IR attribute(s) for 79// an argument, call site argument, function return value, or function. See 80// the class and method descriptions for more information on the two 81// "Abstract" classes and their respective methods. 82// - Register opportunities for the new abstract attribute in the 83// `Attributor::identifyDefaultAbstractAttributes` method if it should be 84// counted as a 'default' attribute. 85// - Add sufficient tests. 86// - Add a Statistics object for bookkeeping. If it is a simple (set of) 87// attribute(s) manifested through the Attributor manifestation framework, see 88// the bookkeeping function in Attributor.cpp. 89// - If instructions with a certain opcode are interesting to the attribute, add 90// that opcode to the switch in `Attributor::identifyAbstractAttributes`. This 91// will make it possible to query all those instructions through the 92// `InformationCache::getOpcodeInstMapForFunction` interface and eliminate the 93// need to traverse the IR repeatedly. 94// 95//===----------------------------------------------------------------------===// 96 97#ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H 98#define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H 99 100#include "llvm/ADT/MapVector.h" 101#include "llvm/ADT/SCCIterator.h" 102#include "llvm/ADT/SetVector.h" 103#include "llvm/Analysis/AliasAnalysis.h" 104#include "llvm/Analysis/CallGraph.h" 105#include "llvm/Analysis/MustExecute.h" 106#include "llvm/Analysis/TargetLibraryInfo.h" 107#include "llvm/IR/CallSite.h" 108#include "llvm/IR/ConstantRange.h" 109#include "llvm/IR/PassManager.h" 110 111namespace llvm { 112 113struct AbstractAttribute; 114struct InformationCache; 115struct AAIsDead; 116 117class Function; 118 119/// Simple enum classes that forces properties to be spelled out explicitly. 120/// 121///{ 122enum class ChangeStatus { 123 CHANGED, 124 UNCHANGED, 125}; 126 127ChangeStatus operator|(ChangeStatus l, ChangeStatus r); 128ChangeStatus operator&(ChangeStatus l, ChangeStatus r); 129 130enum class DepClassTy { 131 REQUIRED, 132 OPTIONAL, 133}; 134///} 135 136/// Helper to describe and deal with positions in the LLVM-IR. 137/// 138/// A position in the IR is described by an anchor value and an "offset" that 139/// could be the argument number, for call sites and arguments, or an indicator 140/// of the "position kind". The kinds, specified in the Kind enum below, include 141/// the locations in the attribute list, i.a., function scope and return value, 142/// as well as a distinction between call sites and functions. Finally, there 143/// are floating values that do not have a corresponding attribute list 144/// position. 145struct IRPosition { 146 virtual ~IRPosition() {} 147 148 /// The positions we distinguish in the IR. 149 /// 150 /// The values are chosen such that the KindOrArgNo member has a value >= 1 151 /// if it is an argument or call site argument while a value < 1 indicates the 152 /// respective kind of that value. 153 enum Kind : int { 154 IRP_INVALID = -6, ///< An invalid position. 155 IRP_FLOAT = -5, ///< A position that is not associated with a spot suitable 156 ///< for attributes. This could be any value or instruction. 157 IRP_RETURNED = -4, ///< An attribute for the function return value. 158 IRP_CALL_SITE_RETURNED = -3, ///< An attribute for a call site return value. 159 IRP_FUNCTION = -2, ///< An attribute for a function (scope). 160 IRP_CALL_SITE = -1, ///< An attribute for a call site (function scope). 161 IRP_ARGUMENT = 0, ///< An attribute for a function argument. 162 IRP_CALL_SITE_ARGUMENT = 1, ///< An attribute for a call site argument. 163 }; 164 165 /// Default constructor available to create invalid positions implicitly. All 166 /// other positions need to be created explicitly through the appropriate 167 /// static member function. 168 IRPosition() : AnchorVal(nullptr), KindOrArgNo(IRP_INVALID) { verify(); } 169 170 /// Create a position describing the value of \p V. 171 static const IRPosition value(const Value &V) { 172 if (auto *Arg = dyn_cast<Argument>(&V)) 173 return IRPosition::argument(*Arg); 174 if (auto *CB = dyn_cast<CallBase>(&V)) 175 return IRPosition::callsite_returned(*CB); 176 return IRPosition(const_cast<Value &>(V), IRP_FLOAT); 177 } 178 179 /// Create a position describing the function scope of \p F. 180 static const IRPosition function(const Function &F) { 181 return IRPosition(const_cast<Function &>(F), IRP_FUNCTION); 182 } 183 184 /// Create a position describing the returned value of \p F. 185 static const IRPosition returned(const Function &F) { 186 return IRPosition(const_cast<Function &>(F), IRP_RETURNED); 187 } 188 189 /// Create a position describing the argument \p Arg. 190 static const IRPosition argument(const Argument &Arg) { 191 return IRPosition(const_cast<Argument &>(Arg), Kind(Arg.getArgNo())); 192 } 193 194 /// Create a position describing the function scope of \p CB. 195 static const IRPosition callsite_function(const CallBase &CB) { 196 return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE); 197 } 198 199 /// Create a position describing the returned value of \p CB. 200 static const IRPosition callsite_returned(const CallBase &CB) { 201 return IRPosition(const_cast<CallBase &>(CB), IRP_CALL_SITE_RETURNED); 202 } 203 204 /// Create a position describing the argument of \p CB at position \p ArgNo. 205 static const IRPosition callsite_argument(const CallBase &CB, 206 unsigned ArgNo) { 207 return IRPosition(const_cast<CallBase &>(CB), Kind(ArgNo)); 208 } 209 210 /// Create a position describing the function scope of \p ICS. 211 static const IRPosition callsite_function(ImmutableCallSite ICS) { 212 return IRPosition::callsite_function(cast<CallBase>(*ICS.getInstruction())); 213 } 214 215 /// Create a position describing the returned value of \p ICS. 216 static const IRPosition callsite_returned(ImmutableCallSite ICS) { 217 return IRPosition::callsite_returned(cast<CallBase>(*ICS.getInstruction())); 218 } 219 220 /// Create a position describing the argument of \p ICS at position \p ArgNo. 221 static const IRPosition callsite_argument(ImmutableCallSite ICS, 222 unsigned ArgNo) { 223 return IRPosition::callsite_argument(cast<CallBase>(*ICS.getInstruction()), 224 ArgNo); 225 } 226 227 /// Create a position describing the argument of \p ACS at position \p ArgNo. 228 static const IRPosition callsite_argument(AbstractCallSite ACS, 229 unsigned ArgNo) { 230 int CSArgNo = ACS.getCallArgOperandNo(ArgNo); 231 if (CSArgNo >= 0) 232 return IRPosition::callsite_argument( 233 cast<CallBase>(*ACS.getInstruction()), CSArgNo); 234 return IRPosition(); 235 } 236 237 /// Create a position with function scope matching the "context" of \p IRP. 238 /// If \p IRP is a call site (see isAnyCallSitePosition()) then the result 239 /// will be a call site position, otherwise the function position of the 240 /// associated function. 241 static const IRPosition function_scope(const IRPosition &IRP) { 242 if (IRP.isAnyCallSitePosition()) { 243 return IRPosition::callsite_function( 244 cast<CallBase>(IRP.getAnchorValue())); 245 } 246 assert(IRP.getAssociatedFunction()); 247 return IRPosition::function(*IRP.getAssociatedFunction()); 248 } 249 250 bool operator==(const IRPosition &RHS) const { 251 return (AnchorVal == RHS.AnchorVal) && (KindOrArgNo == RHS.KindOrArgNo); 252 } 253 bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); } 254 255 /// Return the value this abstract attribute is anchored with. 256 /// 257 /// The anchor value might not be the associated value if the latter is not 258 /// sufficient to determine where arguments will be manifested. This is, so 259 /// far, only the case for call site arguments as the value is not sufficient 260 /// to pinpoint them. Instead, we can use the call site as an anchor. 261 Value &getAnchorValue() const { 262 assert(KindOrArgNo != IRP_INVALID && 263 "Invalid position does not have an anchor value!"); 264 return *AnchorVal; 265 } 266 267 /// Return the associated function, if any. 268 Function *getAssociatedFunction() const { 269 if (auto *CB = dyn_cast<CallBase>(AnchorVal)) 270 return CB->getCalledFunction(); 271 assert(KindOrArgNo != IRP_INVALID && 272 "Invalid position does not have an anchor scope!"); 273 Value &V = getAnchorValue(); 274 if (isa<Function>(V)) 275 return &cast<Function>(V); 276 if (isa<Argument>(V)) 277 return cast<Argument>(V).getParent(); 278 if (isa<Instruction>(V)) 279 return cast<Instruction>(V).getFunction(); 280 return nullptr; 281 } 282 283 /// Return the associated argument, if any. 284 Argument *getAssociatedArgument() const; 285 286 /// Return true if the position refers to a function interface, that is the 287 /// function scope, the function return, or an argument. 288 bool isFnInterfaceKind() const { 289 switch (getPositionKind()) { 290 case IRPosition::IRP_FUNCTION: 291 case IRPosition::IRP_RETURNED: 292 case IRPosition::IRP_ARGUMENT: 293 return true; 294 default: 295 return false; 296 } 297 } 298 299 /// Return the Function surrounding the anchor value. 300 Function *getAnchorScope() const { 301 Value &V = getAnchorValue(); 302 if (isa<Function>(V)) 303 return &cast<Function>(V); 304 if (isa<Argument>(V)) 305 return cast<Argument>(V).getParent(); 306 if (isa<Instruction>(V)) 307 return cast<Instruction>(V).getFunction(); 308 return nullptr; 309 } 310 311 /// Return the context instruction, if any. 312 Instruction *getCtxI() const { 313 Value &V = getAnchorValue(); 314 if (auto *I = dyn_cast<Instruction>(&V)) 315 return I; 316 if (auto *Arg = dyn_cast<Argument>(&V)) 317 if (!Arg->getParent()->isDeclaration()) 318 return &Arg->getParent()->getEntryBlock().front(); 319 if (auto *F = dyn_cast<Function>(&V)) 320 if (!F->isDeclaration()) 321 return &(F->getEntryBlock().front()); 322 return nullptr; 323 } 324 325 /// Return the value this abstract attribute is associated with. 326 Value &getAssociatedValue() const { 327 assert(KindOrArgNo != IRP_INVALID && 328 "Invalid position does not have an associated value!"); 329 if (getArgNo() < 0 || isa<Argument>(AnchorVal)) 330 return *AnchorVal; 331 assert(isa<CallBase>(AnchorVal) && "Expected a call base!"); 332 return *cast<CallBase>(AnchorVal)->getArgOperand(getArgNo()); 333 } 334 335 /// Return the argument number of the associated value if it is an argument or 336 /// call site argument, otherwise a negative value. 337 int getArgNo() const { return KindOrArgNo; } 338 339 /// Return the index in the attribute list for this position. 340 unsigned getAttrIdx() const { 341 switch (getPositionKind()) { 342 case IRPosition::IRP_INVALID: 343 case IRPosition::IRP_FLOAT: 344 break; 345 case IRPosition::IRP_FUNCTION: 346 case IRPosition::IRP_CALL_SITE: 347 return AttributeList::FunctionIndex; 348 case IRPosition::IRP_RETURNED: 349 case IRPosition::IRP_CALL_SITE_RETURNED: 350 return AttributeList::ReturnIndex; 351 case IRPosition::IRP_ARGUMENT: 352 case IRPosition::IRP_CALL_SITE_ARGUMENT: 353 return KindOrArgNo + AttributeList::FirstArgIndex; 354 } 355 llvm_unreachable( 356 "There is no attribute index for a floating or invalid position!"); 357 } 358 359 /// Return the associated position kind. 360 Kind getPositionKind() const { 361 if (getArgNo() >= 0) { 362 assert(((isa<Argument>(getAnchorValue()) && 363 isa<Argument>(getAssociatedValue())) || 364 isa<CallBase>(getAnchorValue())) && 365 "Expected argument or call base due to argument number!"); 366 if (isa<CallBase>(getAnchorValue())) 367 return IRP_CALL_SITE_ARGUMENT; 368 return IRP_ARGUMENT; 369 } 370 371 assert(KindOrArgNo < 0 && 372 "Expected (call site) arguments to never reach this point!"); 373 return Kind(KindOrArgNo); 374 } 375 376 /// TODO: Figure out if the attribute related helper functions should live 377 /// here or somewhere else. 378 379 /// Return true if any kind in \p AKs existing in the IR at a position that 380 /// will affect this one. See also getAttrs(...). 381 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions, 382 /// e.g., the function position if this is an 383 /// argument position, should be ignored. 384 bool hasAttr(ArrayRef<Attribute::AttrKind> AKs, 385 bool IgnoreSubsumingPositions = false) const; 386 387 /// Return the attributes of any kind in \p AKs existing in the IR at a 388 /// position that will affect this one. While each position can only have a 389 /// single attribute of any kind in \p AKs, there are "subsuming" positions 390 /// that could have an attribute as well. This method returns all attributes 391 /// found in \p Attrs. 392 /// \param IgnoreSubsumingPositions Flag to determine if subsuming positions, 393 /// e.g., the function position if this is an 394 /// argument position, should be ignored. 395 void getAttrs(ArrayRef<Attribute::AttrKind> AKs, 396 SmallVectorImpl<Attribute> &Attrs, 397 bool IgnoreSubsumingPositions = false) const; 398 399 /// Return the attribute of kind \p AK existing in the IR at this position. 400 Attribute getAttr(Attribute::AttrKind AK) const { 401 if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT) 402 return Attribute(); 403 404 AttributeList AttrList; 405 if (ImmutableCallSite ICS = ImmutableCallSite(&getAnchorValue())) 406 AttrList = ICS.getAttributes(); 407 else 408 AttrList = getAssociatedFunction()->getAttributes(); 409 410 if (AttrList.hasAttribute(getAttrIdx(), AK)) 411 return AttrList.getAttribute(getAttrIdx(), AK); 412 return Attribute(); 413 } 414 415 /// Remove the attribute of kind \p AKs existing in the IR at this position. 416 void removeAttrs(ArrayRef<Attribute::AttrKind> AKs) const { 417 if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT) 418 return; 419 420 AttributeList AttrList; 421 CallSite CS = CallSite(&getAnchorValue()); 422 if (CS) 423 AttrList = CS.getAttributes(); 424 else 425 AttrList = getAssociatedFunction()->getAttributes(); 426 427 LLVMContext &Ctx = getAnchorValue().getContext(); 428 for (Attribute::AttrKind AK : AKs) 429 AttrList = AttrList.removeAttribute(Ctx, getAttrIdx(), AK); 430 431 if (CS) 432 CS.setAttributes(AttrList); 433 else 434 getAssociatedFunction()->setAttributes(AttrList); 435 } 436 437 bool isAnyCallSitePosition() const { 438 switch (getPositionKind()) { 439 case IRPosition::IRP_CALL_SITE: 440 case IRPosition::IRP_CALL_SITE_RETURNED: 441 case IRPosition::IRP_CALL_SITE_ARGUMENT: 442 return true; 443 default: 444 return false; 445 } 446 } 447 448 /// Special DenseMap key values. 449 /// 450 ///{ 451 static const IRPosition EmptyKey; 452 static const IRPosition TombstoneKey; 453 ///} 454 455private: 456 /// Private constructor for special values only! 457 explicit IRPosition(int KindOrArgNo) 458 : AnchorVal(0), KindOrArgNo(KindOrArgNo) {} 459 460 /// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK. 461 explicit IRPosition(Value &AnchorVal, Kind PK) 462 : AnchorVal(&AnchorVal), KindOrArgNo(PK) { 463 verify(); 464 } 465 466 /// Verify internal invariants. 467 void verify(); 468 469protected: 470 /// The value this position is anchored at. 471 Value *AnchorVal; 472 473 /// The argument number, if non-negative, or the position "kind". 474 int KindOrArgNo; 475}; 476 477/// Helper that allows IRPosition as a key in a DenseMap. 478template <> struct DenseMapInfo<IRPosition> { 479 static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; } 480 static inline IRPosition getTombstoneKey() { 481 return IRPosition::TombstoneKey; 482 } 483 static unsigned getHashValue(const IRPosition &IRP) { 484 return (DenseMapInfo<Value *>::getHashValue(&IRP.getAnchorValue()) << 4) ^ 485 (unsigned(IRP.getArgNo())); 486 } 487 static bool isEqual(const IRPosition &LHS, const IRPosition &RHS) { 488 return LHS == RHS; 489 } 490}; 491 492/// A visitor class for IR positions. 493/// 494/// Given a position P, the SubsumingPositionIterator allows to visit "subsuming 495/// positions" wrt. attributes/information. Thus, if a piece of information 496/// holds for a subsuming position, it also holds for the position P. 497/// 498/// The subsuming positions always include the initial position and then, 499/// depending on the position kind, additionally the following ones: 500/// - for IRP_RETURNED: 501/// - the function (IRP_FUNCTION) 502/// - for IRP_ARGUMENT: 503/// - the function (IRP_FUNCTION) 504/// - for IRP_CALL_SITE: 505/// - the callee (IRP_FUNCTION), if known 506/// - for IRP_CALL_SITE_RETURNED: 507/// - the callee (IRP_RETURNED), if known 508/// - the call site (IRP_FUNCTION) 509/// - the callee (IRP_FUNCTION), if known 510/// - for IRP_CALL_SITE_ARGUMENT: 511/// - the argument of the callee (IRP_ARGUMENT), if known 512/// - the callee (IRP_FUNCTION), if known 513/// - the position the call site argument is associated with if it is not 514/// anchored to the call site, e.g., if it is an argument then the argument 515/// (IRP_ARGUMENT) 516class SubsumingPositionIterator { 517 SmallVector<IRPosition, 4> IRPositions; 518 using iterator = decltype(IRPositions)::iterator; 519 520public: 521 SubsumingPositionIterator(const IRPosition &IRP); 522 iterator begin() { return IRPositions.begin(); } 523 iterator end() { return IRPositions.end(); } 524}; 525 526/// Wrapper for FunctoinAnalysisManager. 527struct AnalysisGetter { 528 template <typename Analysis> 529 typename Analysis::Result *getAnalysis(const Function &F) { 530 if (!MAM || !F.getParent()) 531 return nullptr; 532 auto &FAM = MAM->getResult<FunctionAnalysisManagerModuleProxy>( 533 const_cast<Module &>(*F.getParent())) 534 .getManager(); 535 return &FAM.getResult<Analysis>(const_cast<Function &>(F)); 536 } 537 538 template <typename Analysis> 539 typename Analysis::Result *getAnalysis(const Module &M) { 540 if (!MAM) 541 return nullptr; 542 return &MAM->getResult<Analysis>(const_cast<Module &>(M)); 543 } 544 AnalysisGetter(ModuleAnalysisManager &MAM) : MAM(&MAM) {} 545 AnalysisGetter() {} 546 547private: 548 ModuleAnalysisManager *MAM = nullptr; 549}; 550 551/// Data structure to hold cached (LLVM-IR) information. 552/// 553/// All attributes are given an InformationCache object at creation time to 554/// avoid inspection of the IR by all of them individually. This default 555/// InformationCache will hold information required by 'default' attributes, 556/// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..) 557/// is called. 558/// 559/// If custom abstract attributes, registered manually through 560/// Attributor::registerAA(...), need more information, especially if it is not 561/// reusable, it is advised to inherit from the InformationCache and cast the 562/// instance down in the abstract attributes. 563struct InformationCache { 564 InformationCache(const Module &M, AnalysisGetter &AG) 565 : DL(M.getDataLayout()), Explorer(/* ExploreInterBlock */ true), AG(AG) { 566 567 CallGraph *CG = AG.getAnalysis<CallGraphAnalysis>(M); 568 if (!CG) 569 return; 570 571 DenseMap<const Function *, unsigned> SccSize; 572 for (scc_iterator<CallGraph *> I = scc_begin(CG); !I.isAtEnd(); ++I) { 573 for (CallGraphNode *Node : *I) 574 SccSize[Node->getFunction()] = I->size(); 575 } 576 SccSizeOpt = std::move(SccSize); 577 } 578 579 /// A map type from opcodes to instructions with this opcode. 580 using OpcodeInstMapTy = DenseMap<unsigned, SmallVector<Instruction *, 32>>; 581 582 /// Return the map that relates "interesting" opcodes with all instructions 583 /// with that opcode in \p F. 584 OpcodeInstMapTy &getOpcodeInstMapForFunction(const Function &F) { 585 return FuncInstOpcodeMap[&F]; 586 } 587 588 /// A vector type to hold instructions. 589 using InstructionVectorTy = std::vector<Instruction *>; 590 591 /// Return the instructions in \p F that may read or write memory. 592 InstructionVectorTy &getReadOrWriteInstsForFunction(const Function &F) { 593 return FuncRWInstsMap[&F]; 594 } 595 596 /// Return MustBeExecutedContextExplorer 597 MustBeExecutedContextExplorer &getMustBeExecutedContextExplorer() { 598 return Explorer; 599 } 600 601 /// Return TargetLibraryInfo for function \p F. 602 TargetLibraryInfo *getTargetLibraryInfoForFunction(const Function &F) { 603 return AG.getAnalysis<TargetLibraryAnalysis>(F); 604 } 605 606 /// Return AliasAnalysis Result for function \p F. 607 AAResults *getAAResultsForFunction(const Function &F) { 608 return AG.getAnalysis<AAManager>(F); 609 } 610 611 /// Return the analysis result from a pass \p AP for function \p F. 612 template <typename AP> 613 typename AP::Result *getAnalysisResultForFunction(const Function &F) { 614 return AG.getAnalysis<AP>(F); 615 } 616 617 /// Return SCC size on call graph for function \p F. 618 unsigned getSccSize(const Function &F) { 619 if (!SccSizeOpt.hasValue()) 620 return 0; 621 return (SccSizeOpt.getValue())[&F]; 622 } 623 624 /// Return datalayout used in the module. 625 const DataLayout &getDL() { return DL; } 626 627private: 628 /// A map type from functions to opcode to instruction maps. 629 using FuncInstOpcodeMapTy = DenseMap<const Function *, OpcodeInstMapTy>; 630 631 /// A map type from functions to their read or write instructions. 632 using FuncRWInstsMapTy = DenseMap<const Function *, InstructionVectorTy>; 633 634 /// A nested map that remembers all instructions in a function with a certain 635 /// instruction opcode (Instruction::getOpcode()). 636 FuncInstOpcodeMapTy FuncInstOpcodeMap; 637 638 /// A map from functions to their instructions that may read or write memory. 639 FuncRWInstsMapTy FuncRWInstsMap; 640 641 /// The datalayout used in the module. 642 const DataLayout &DL; 643 644 /// MustBeExecutedContextExplorer 645 MustBeExecutedContextExplorer Explorer; 646 647 /// Getters for analysis. 648 AnalysisGetter &AG; 649 650 /// Cache result for scc size in the call graph 651 Optional<DenseMap<const Function *, unsigned>> SccSizeOpt; 652 653 /// Give the Attributor access to the members so 654 /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them. 655 friend struct Attributor; 656}; 657 658/// The fixpoint analysis framework that orchestrates the attribute deduction. 659/// 660/// The Attributor provides a general abstract analysis framework (guided 661/// fixpoint iteration) as well as helper functions for the deduction of 662/// (LLVM-IR) attributes. However, also other code properties can be deduced, 663/// propagated, and ultimately manifested through the Attributor framework. This 664/// is particularly useful if these properties interact with attributes and a 665/// co-scheduled deduction allows to improve the solution. Even if not, thus if 666/// attributes/properties are completely isolated, they should use the 667/// Attributor framework to reduce the number of fixpoint iteration frameworks 668/// in the code base. Note that the Attributor design makes sure that isolated 669/// attributes are not impacted, in any way, by others derived at the same time 670/// if there is no cross-reasoning performed. 671/// 672/// The public facing interface of the Attributor is kept simple and basically 673/// allows abstract attributes to one thing, query abstract attributes 674/// in-flight. There are two reasons to do this: 675/// a) The optimistic state of one abstract attribute can justify an 676/// optimistic state of another, allowing to framework to end up with an 677/// optimistic (=best possible) fixpoint instead of one based solely on 678/// information in the IR. 679/// b) This avoids reimplementing various kinds of lookups, e.g., to check 680/// for existing IR attributes, in favor of a single lookups interface 681/// provided by an abstract attribute subclass. 682/// 683/// NOTE: The mechanics of adding a new "concrete" abstract attribute are 684/// described in the file comment. 685struct Attributor { 686 /// Constructor 687 /// 688 /// \param InfoCache Cache to hold various information accessible for 689 /// the abstract attributes. 690 /// \param DepRecomputeInterval Number of iterations until the dependences 691 /// between abstract attributes are recomputed. 692 /// \param Whitelist If not null, a set limiting the attribute opportunities. 693 Attributor(InformationCache &InfoCache, unsigned DepRecomputeInterval, 694 DenseSet<const char *> *Whitelist = nullptr) 695 : InfoCache(InfoCache), DepRecomputeInterval(DepRecomputeInterval), 696 Whitelist(Whitelist) {} 697 698 ~Attributor() { 699 DeleteContainerPointers(AllAbstractAttributes); 700 for (auto &It : ArgumentReplacementMap) 701 DeleteContainerPointers(It.second); 702 } 703 704 /// Run the analyses until a fixpoint is reached or enforced (timeout). 705 /// 706 /// The attributes registered with this Attributor can be used after as long 707 /// as the Attributor is not destroyed (it owns the attributes now). 708 /// 709 /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED. 710 ChangeStatus run(Module &M); 711 712 /// Lookup an abstract attribute of type \p AAType at position \p IRP. While 713 /// no abstract attribute is found equivalent positions are checked, see 714 /// SubsumingPositionIterator. Thus, the returned abstract attribute 715 /// might be anchored at a different position, e.g., the callee if \p IRP is a 716 /// call base. 717 /// 718 /// This method is the only (supported) way an abstract attribute can retrieve 719 /// information from another abstract attribute. As an example, take an 720 /// abstract attribute that determines the memory access behavior for a 721 /// argument (readnone, readonly, ...). It should use `getAAFor` to get the 722 /// most optimistic information for other abstract attributes in-flight, e.g. 723 /// the one reasoning about the "captured" state for the argument or the one 724 /// reasoning on the memory access behavior of the function as a whole. 725 /// 726 /// If the flag \p TrackDependence is set to false the dependence from 727 /// \p QueryingAA to the return abstract attribute is not automatically 728 /// recorded. This should only be used if the caller will record the 729 /// dependence explicitly if necessary, thus if it the returned abstract 730 /// attribute is used for reasoning. To record the dependences explicitly use 731 /// the `Attributor::recordDependence` method. 732 template <typename AAType> 733 const AAType &getAAFor(const AbstractAttribute &QueryingAA, 734 const IRPosition &IRP, bool TrackDependence = true, 735 DepClassTy DepClass = DepClassTy::REQUIRED) { 736 return getOrCreateAAFor<AAType>(IRP, &QueryingAA, TrackDependence, 737 DepClass); 738 } 739 740 /// Explicitly record a dependence from \p FromAA to \p ToAA, that is if 741 /// \p FromAA changes \p ToAA should be updated as well. 742 /// 743 /// This method should be used in conjunction with the `getAAFor` method and 744 /// with the TrackDependence flag passed to the method set to false. This can 745 /// be beneficial to avoid false dependences but it requires the users of 746 /// `getAAFor` to explicitly record true dependences through this method. 747 /// The \p DepClass flag indicates if the dependence is striclty necessary. 748 /// That means for required dependences, if \p FromAA changes to an invalid 749 /// state, \p ToAA can be moved to a pessimistic fixpoint because it required 750 /// information from \p FromAA but none are available anymore. 751 void recordDependence(const AbstractAttribute &FromAA, 752 const AbstractAttribute &ToAA, DepClassTy DepClass); 753 754 /// Introduce a new abstract attribute into the fixpoint analysis. 755 /// 756 /// Note that ownership of the attribute is given to the Attributor. It will 757 /// invoke delete for the Attributor on destruction of the Attributor. 758 /// 759 /// Attributes are identified by their IR position (AAType::getIRPosition()) 760 /// and the address of their static member (see AAType::ID). 761 template <typename AAType> AAType ®isterAA(AAType &AA) { 762 static_assert(std::is_base_of<AbstractAttribute, AAType>::value, 763 "Cannot register an attribute with a type not derived from " 764 "'AbstractAttribute'!"); 765 // Put the attribute in the lookup map structure and the container we use to 766 // keep track of all attributes. 767 const IRPosition &IRP = AA.getIRPosition(); 768 auto &KindToAbstractAttributeMap = AAMap[IRP]; 769 assert(!KindToAbstractAttributeMap.count(&AAType::ID) && 770 "Attribute already in map!"); 771 KindToAbstractAttributeMap[&AAType::ID] = &AA; 772 AllAbstractAttributes.push_back(&AA); 773 return AA; 774 } 775 776 /// Return the internal information cache. 777 InformationCache &getInfoCache() { return InfoCache; } 778 779 /// Determine opportunities to derive 'default' attributes in \p F and create 780 /// abstract attribute objects for them. 781 /// 782 /// \param F The function that is checked for attribute opportunities. 783 /// 784 /// Note that abstract attribute instances are generally created even if the 785 /// IR already contains the information they would deduce. The most important 786 /// reason for this is the single interface, the one of the abstract attribute 787 /// instance, which can be queried without the need to look at the IR in 788 /// various places. 789 void identifyDefaultAbstractAttributes(Function &F); 790 791 /// Initialize the information cache for queries regarding function \p F. 792 /// 793 /// This method needs to be called for all function that might be looked at 794 /// through the information cache interface *prior* to looking at them. 795 void initializeInformationCache(Function &F); 796 797 /// Mark the internal function \p F as live. 798 /// 799 /// This will trigger the identification and initialization of attributes for 800 /// \p F. 801 void markLiveInternalFunction(const Function &F) { 802 assert(F.hasLocalLinkage() && 803 "Only local linkage is assumed dead initially."); 804 805 identifyDefaultAbstractAttributes(const_cast<Function &>(F)); 806 } 807 808 /// Record that \p U is to be replaces with \p NV after information was 809 /// manifested. This also triggers deletion of trivially dead istructions. 810 bool changeUseAfterManifest(Use &U, Value &NV) { 811 Value *&V = ToBeChangedUses[&U]; 812 if (V && (V->stripPointerCasts() == NV.stripPointerCasts() || 813 isa_and_nonnull<UndefValue>(V))) 814 return false; 815 assert((!V || V == &NV || isa<UndefValue>(NV)) && 816 "Use was registered twice for replacement with different values!"); 817 V = &NV; 818 return true; 819 } 820 821 /// Helper function to replace all uses of \p V with \p NV. Return true if 822 /// there is any change. 823 bool changeValueAfterManifest(Value &V, Value &NV) { 824 bool Changed = false; 825 for (auto &U : V.uses()) 826 Changed |= changeUseAfterManifest(U, NV); 827 828 return Changed; 829 } 830 831 /// Get pointer operand of memory accessing instruction. If \p I is 832 /// not a memory accessing instruction, return nullptr. If \p AllowVolatile, 833 /// is set to false and the instruction is volatile, return nullptr. 834 static const Value *getPointerOperand(const Instruction *I, 835 bool AllowVolatile) { 836 if (auto *LI = dyn_cast<LoadInst>(I)) { 837 if (!AllowVolatile && LI->isVolatile()) 838 return nullptr; 839 return LI->getPointerOperand(); 840 } 841 842 if (auto *SI = dyn_cast<StoreInst>(I)) { 843 if (!AllowVolatile && SI->isVolatile()) 844 return nullptr; 845 return SI->getPointerOperand(); 846 } 847 848 if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(I)) { 849 if (!AllowVolatile && CXI->isVolatile()) 850 return nullptr; 851 return CXI->getPointerOperand(); 852 } 853 854 if (auto *RMWI = dyn_cast<AtomicRMWInst>(I)) { 855 if (!AllowVolatile && RMWI->isVolatile()) 856 return nullptr; 857 return RMWI->getPointerOperand(); 858 } 859 860 return nullptr; 861 } 862 863 /// Record that \p I is to be replaced with `unreachable` after information 864 /// was manifested. 865 void changeToUnreachableAfterManifest(Instruction *I) { 866 ToBeChangedToUnreachableInsts.insert(I); 867 } 868 869 /// Record that \p II has at least one dead successor block. This information 870 /// is used, e.g., to replace \p II with a call, after information was 871 /// manifested. 872 void registerInvokeWithDeadSuccessor(InvokeInst &II) { 873 InvokeWithDeadSuccessor.push_back(&II); 874 } 875 876 /// Record that \p I is deleted after information was manifested. This also 877 /// triggers deletion of trivially dead istructions. 878 void deleteAfterManifest(Instruction &I) { ToBeDeletedInsts.insert(&I); } 879 880 /// Record that \p BB is deleted after information was manifested. This also 881 /// triggers deletion of trivially dead istructions. 882 void deleteAfterManifest(BasicBlock &BB) { ToBeDeletedBlocks.insert(&BB); } 883 884 /// Record that \p F is deleted after information was manifested. 885 void deleteAfterManifest(Function &F) { ToBeDeletedFunctions.insert(&F); } 886 887 /// Return true if \p AA (or its context instruction) is assumed dead. 888 /// 889 /// If \p LivenessAA is not provided it is queried. 890 bool isAssumedDead(const AbstractAttribute &AA, const AAIsDead *LivenessAA); 891 892 /// Check \p Pred on all (transitive) uses of \p V. 893 /// 894 /// This method will evaluate \p Pred on all (transitive) uses of the 895 /// associated value and return true if \p Pred holds every time. 896 bool checkForAllUses(const function_ref<bool(const Use &, bool &)> &Pred, 897 const AbstractAttribute &QueryingAA, const Value &V); 898 899 /// Helper struct used in the communication between an abstract attribute (AA) 900 /// that wants to change the signature of a function and the Attributor which 901 /// applies the changes. The struct is partially initialized with the 902 /// information from the AA (see the constructor). All other members are 903 /// provided by the Attributor prior to invoking any callbacks. 904 struct ArgumentReplacementInfo { 905 /// Callee repair callback type 906 /// 907 /// The function repair callback is invoked once to rewire the replacement 908 /// arguments in the body of the new function. The argument replacement info 909 /// is passed, as build from the registerFunctionSignatureRewrite call, as 910 /// well as the replacement function and an iteratore to the first 911 /// replacement argument. 912 using CalleeRepairCBTy = std::function<void( 913 const ArgumentReplacementInfo &, Function &, Function::arg_iterator)>; 914 915 /// Abstract call site (ACS) repair callback type 916 /// 917 /// The abstract call site repair callback is invoked once on every abstract 918 /// call site of the replaced function (\see ReplacedFn). The callback needs 919 /// to provide the operands for the call to the new replacement function. 920 /// The number and type of the operands appended to the provided vector 921 /// (second argument) is defined by the number and types determined through 922 /// the replacement type vector (\see ReplacementTypes). The first argument 923 /// is the ArgumentReplacementInfo object registered with the Attributor 924 /// through the registerFunctionSignatureRewrite call. 925 using ACSRepairCBTy = 926 std::function<void(const ArgumentReplacementInfo &, AbstractCallSite, 927 SmallVectorImpl<Value *> &)>; 928 929 /// Simple getters, see the corresponding members for details. 930 ///{ 931 932 Attributor &getAttributor() const { return A; } 933 const Function &getReplacedFn() const { return ReplacedFn; } 934 const Argument &getReplacedArg() const { return ReplacedArg; } 935 unsigned getNumReplacementArgs() const { return ReplacementTypes.size(); } 936 const SmallVectorImpl<Type *> &getReplacementTypes() const { 937 return ReplacementTypes; 938 } 939 940 ///} 941 942 private: 943 /// Constructor that takes the argument to be replaced, the types of 944 /// the replacement arguments, as well as callbacks to repair the call sites 945 /// and new function after the replacement happened. 946 ArgumentReplacementInfo(Attributor &A, Argument &Arg, 947 ArrayRef<Type *> ReplacementTypes, 948 CalleeRepairCBTy &&CalleeRepairCB, 949 ACSRepairCBTy &&ACSRepairCB) 950 : A(A), ReplacedFn(*Arg.getParent()), ReplacedArg(Arg), 951 ReplacementTypes(ReplacementTypes.begin(), ReplacementTypes.end()), 952 CalleeRepairCB(std::move(CalleeRepairCB)), 953 ACSRepairCB(std::move(ACSRepairCB)) {} 954 955 /// Reference to the attributor to allow access from the callbacks. 956 Attributor &A; 957 958 /// The "old" function replaced by ReplacementFn. 959 const Function &ReplacedFn; 960 961 /// The "old" argument replaced by new ones defined via ReplacementTypes. 962 const Argument &ReplacedArg; 963 964 /// The types of the arguments replacing ReplacedArg. 965 const SmallVector<Type *, 8> ReplacementTypes; 966 967 /// Callee repair callback, see CalleeRepairCBTy. 968 const CalleeRepairCBTy CalleeRepairCB; 969 970 /// Abstract call site (ACS) repair callback, see ACSRepairCBTy. 971 const ACSRepairCBTy ACSRepairCB; 972 973 /// Allow access to the private members from the Attributor. 974 friend struct Attributor; 975 }; 976 977 /// Register a rewrite for a function signature. 978 /// 979 /// The argument \p Arg is replaced with new ones defined by the number, 980 /// order, and types in \p ReplacementTypes. The rewiring at the call sites is 981 /// done through \p ACSRepairCB and at the callee site through 982 /// \p CalleeRepairCB. 983 /// 984 /// \returns True, if the replacement was registered, false otherwise. 985 bool registerFunctionSignatureRewrite( 986 Argument &Arg, ArrayRef<Type *> ReplacementTypes, 987 ArgumentReplacementInfo::CalleeRepairCBTy &&CalleeRepairCB, 988 ArgumentReplacementInfo::ACSRepairCBTy &&ACSRepairCB); 989 990 /// Check \p Pred on all function call sites. 991 /// 992 /// This method will evaluate \p Pred on call sites and return 993 /// true if \p Pred holds in every call sites. However, this is only possible 994 /// all call sites are known, hence the function has internal linkage. 995 bool checkForAllCallSites(const function_ref<bool(AbstractCallSite)> &Pred, 996 const AbstractAttribute &QueryingAA, 997 bool RequireAllCallSites); 998 999 /// Check \p Pred on all values potentially returned by \p F. 1000 /// 1001 /// This method will evaluate \p Pred on all values potentially returned by 1002 /// the function associated with \p QueryingAA. The returned values are 1003 /// matched with their respective return instructions. Returns true if \p Pred 1004 /// holds on all of them. 1005 bool checkForAllReturnedValuesAndReturnInsts( 1006 const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> 1007 &Pred, 1008 const AbstractAttribute &QueryingAA); 1009 1010 /// Check \p Pred on all values potentially returned by the function 1011 /// associated with \p QueryingAA. 1012 /// 1013 /// This is the context insensitive version of the method above. 1014 bool checkForAllReturnedValues(const function_ref<bool(Value &)> &Pred, 1015 const AbstractAttribute &QueryingAA); 1016 1017 /// Check \p Pred on all instructions with an opcode present in \p Opcodes. 1018 /// 1019 /// This method will evaluate \p Pred on all instructions with an opcode 1020 /// present in \p Opcode and return true if \p Pred holds on all of them. 1021 bool checkForAllInstructions(const function_ref<bool(Instruction &)> &Pred, 1022 const AbstractAttribute &QueryingAA, 1023 const ArrayRef<unsigned> &Opcodes); 1024 1025 /// Check \p Pred on all call-like instructions (=CallBased derived). 1026 /// 1027 /// See checkForAllCallLikeInstructions(...) for more information. 1028 bool 1029 checkForAllCallLikeInstructions(const function_ref<bool(Instruction &)> &Pred, 1030 const AbstractAttribute &QueryingAA) { 1031 return checkForAllInstructions(Pred, QueryingAA, 1032 {(unsigned)Instruction::Invoke, 1033 (unsigned)Instruction::CallBr, 1034 (unsigned)Instruction::Call}); 1035 } 1036 1037 /// Check \p Pred on all Read/Write instructions. 1038 /// 1039 /// This method will evaluate \p Pred on all instructions that read or write 1040 /// to memory present in the information cache and return true if \p Pred 1041 /// holds on all of them. 1042 bool checkForAllReadWriteInstructions( 1043 const llvm::function_ref<bool(Instruction &)> &Pred, 1044 AbstractAttribute &QueryingAA); 1045 1046 /// Return the data layout associated with the anchor scope. 1047 const DataLayout &getDataLayout() const { return InfoCache.DL; } 1048 1049private: 1050 /// Check \p Pred on all call sites of \p Fn. 1051 /// 1052 /// This method will evaluate \p Pred on call sites and return 1053 /// true if \p Pred holds in every call sites. However, this is only possible 1054 /// all call sites are known, hence the function has internal linkage. 1055 bool checkForAllCallSites(const function_ref<bool(AbstractCallSite)> &Pred, 1056 const Function &Fn, bool RequireAllCallSites, 1057 const AbstractAttribute *QueryingAA); 1058 1059 /// The private version of getAAFor that allows to omit a querying abstract 1060 /// attribute. See also the public getAAFor method. 1061 template <typename AAType> 1062 const AAType &getOrCreateAAFor(const IRPosition &IRP, 1063 const AbstractAttribute *QueryingAA = nullptr, 1064 bool TrackDependence = false, 1065 DepClassTy DepClass = DepClassTy::OPTIONAL) { 1066 if (const AAType *AAPtr = 1067 lookupAAFor<AAType>(IRP, QueryingAA, TrackDependence)) 1068 return *AAPtr; 1069 1070 // No matching attribute found, create one. 1071 // Use the static create method. 1072 auto &AA = AAType::createForPosition(IRP, *this); 1073 registerAA(AA); 1074 1075 // For now we ignore naked and optnone functions. 1076 bool Invalidate = Whitelist && !Whitelist->count(&AAType::ID); 1077 if (const Function *Fn = IRP.getAnchorScope()) 1078 Invalidate |= Fn->hasFnAttribute(Attribute::Naked) || 1079 Fn->hasFnAttribute(Attribute::OptimizeNone); 1080 1081 // Bootstrap the new attribute with an initial update to propagate 1082 // information, e.g., function -> call site. If it is not on a given 1083 // whitelist we will not perform updates at all. 1084 if (Invalidate) { 1085 AA.getState().indicatePessimisticFixpoint(); 1086 return AA; 1087 } 1088 1089 AA.initialize(*this); 1090 AA.update(*this); 1091 1092 if (TrackDependence && AA.getState().isValidState()) 1093 recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA), 1094 DepClass); 1095 return AA; 1096 } 1097 1098 /// Return the attribute of \p AAType for \p IRP if existing. 1099 template <typename AAType> 1100 const AAType *lookupAAFor(const IRPosition &IRP, 1101 const AbstractAttribute *QueryingAA = nullptr, 1102 bool TrackDependence = false, 1103 DepClassTy DepClass = DepClassTy::OPTIONAL) { 1104 static_assert(std::is_base_of<AbstractAttribute, AAType>::value, 1105 "Cannot query an attribute with a type not derived from " 1106 "'AbstractAttribute'!"); 1107 assert((QueryingAA || !TrackDependence) && 1108 "Cannot track dependences without a QueryingAA!"); 1109 1110 // Lookup the abstract attribute of type AAType. If found, return it after 1111 // registering a dependence of QueryingAA on the one returned attribute. 1112 const auto &KindToAbstractAttributeMap = AAMap.lookup(IRP); 1113 if (AAType *AA = static_cast<AAType *>( 1114 KindToAbstractAttributeMap.lookup(&AAType::ID))) { 1115 // Do not register a dependence on an attribute with an invalid state. 1116 if (TrackDependence && AA->getState().isValidState()) 1117 recordDependence(*AA, const_cast<AbstractAttribute &>(*QueryingAA), 1118 DepClass); 1119 return AA; 1120 } 1121 return nullptr; 1122 } 1123 1124 /// Apply all requested function signature rewrites 1125 /// (\see registerFunctionSignatureRewrite) and return Changed if the module 1126 /// was altered. 1127 ChangeStatus rewriteFunctionSignatures(); 1128 1129 /// The set of all abstract attributes. 1130 ///{ 1131 using AAVector = SmallVector<AbstractAttribute *, 64>; 1132 AAVector AllAbstractAttributes; 1133 ///} 1134 1135 /// A nested map to lookup abstract attributes based on the argument position 1136 /// on the outer level, and the addresses of the static member (AAType::ID) on 1137 /// the inner level. 1138 ///{ 1139 using KindToAbstractAttributeMap = 1140 DenseMap<const char *, AbstractAttribute *>; 1141 DenseMap<IRPosition, KindToAbstractAttributeMap> AAMap; 1142 ///} 1143 1144 /// A map from abstract attributes to the ones that queried them through calls 1145 /// to the getAAFor<...>(...) method. 1146 ///{ 1147 struct QueryMapValueTy { 1148 /// Set of abstract attributes which were used but not necessarily required 1149 /// for a potential optimistic state. 1150 SetVector<AbstractAttribute *> OptionalAAs; 1151 1152 /// Set of abstract attributes which were used and which were necessarily 1153 /// required for any potential optimistic state. 1154 SetVector<AbstractAttribute *> RequiredAAs; 1155 }; 1156 using QueryMapTy = MapVector<const AbstractAttribute *, QueryMapValueTy>; 1157 QueryMapTy QueryMap; 1158 ///} 1159 1160 /// Map to remember all requested signature changes (= argument replacements). 1161 DenseMap<Function *, SmallVector<ArgumentReplacementInfo *, 8>> 1162 ArgumentReplacementMap; 1163 1164 /// The information cache that holds pre-processed (LLVM-IR) information. 1165 InformationCache &InfoCache; 1166 1167 /// Set if the attribute currently updated did query a non-fix attribute. 1168 bool QueriedNonFixAA; 1169 1170 /// Number of iterations until the dependences between abstract attributes are 1171 /// recomputed. 1172 const unsigned DepRecomputeInterval; 1173 1174 /// If not null, a set limiting the attribute opportunities. 1175 const DenseSet<const char *> *Whitelist; 1176 1177 /// A set to remember the functions we already assume to be live and visited. 1178 DenseSet<const Function *> VisitedFunctions; 1179 1180 /// Uses we replace with a new value after manifest is done. We will remove 1181 /// then trivially dead instructions as well. 1182 DenseMap<Use *, Value *> ToBeChangedUses; 1183 1184 /// Instructions we replace with `unreachable` insts after manifest is done. 1185 SmallDenseSet<WeakVH, 16> ToBeChangedToUnreachableInsts; 1186 1187 /// Invoke instructions with at least a single dead successor block. 1188 SmallVector<WeakVH, 16> InvokeWithDeadSuccessor; 1189 1190 /// Functions, blocks, and instructions we delete after manifest is done. 1191 /// 1192 ///{ 1193 SmallPtrSet<Function *, 8> ToBeDeletedFunctions; 1194 SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks; 1195 SmallPtrSet<Instruction *, 8> ToBeDeletedInsts; 1196 ///} 1197}; 1198 1199/// An interface to query the internal state of an abstract attribute. 1200/// 1201/// The abstract state is a minimal interface that allows the Attributor to 1202/// communicate with the abstract attributes about their internal state without 1203/// enforcing or exposing implementation details, e.g., the (existence of an) 1204/// underlying lattice. 1205/// 1206/// It is sufficient to be able to query if a state is (1) valid or invalid, (2) 1207/// at a fixpoint, and to indicate to the state that (3) an optimistic fixpoint 1208/// was reached or (4) a pessimistic fixpoint was enforced. 1209/// 1210/// All methods need to be implemented by the subclass. For the common use case, 1211/// a single boolean state or a bit-encoded state, the BooleanState and 1212/// {Inc,Dec,Bit}IntegerState classes are already provided. An abstract 1213/// attribute can inherit from them to get the abstract state interface and 1214/// additional methods to directly modify the state based if needed. See the 1215/// class comments for help. 1216struct AbstractState { 1217 virtual ~AbstractState() {} 1218 1219 /// Return if this abstract state is in a valid state. If false, no 1220 /// information provided should be used. 1221 virtual bool isValidState() const = 0; 1222 1223 /// Return if this abstract state is fixed, thus does not need to be updated 1224 /// if information changes as it cannot change itself. 1225 virtual bool isAtFixpoint() const = 0; 1226 1227 /// Indicate that the abstract state should converge to the optimistic state. 1228 /// 1229 /// This will usually make the optimistically assumed state the known to be 1230 /// true state. 1231 /// 1232 /// \returns ChangeStatus::UNCHANGED as the assumed value should not change. 1233 virtual ChangeStatus indicateOptimisticFixpoint() = 0; 1234 1235 /// Indicate that the abstract state should converge to the pessimistic state. 1236 /// 1237 /// This will usually revert the optimistically assumed state to the known to 1238 /// be true state. 1239 /// 1240 /// \returns ChangeStatus::CHANGED as the assumed value may change. 1241 virtual ChangeStatus indicatePessimisticFixpoint() = 0; 1242}; 1243 1244/// Simple state with integers encoding. 1245/// 1246/// The interface ensures that the assumed bits are always a subset of the known 1247/// bits. Users can only add known bits and, except through adding known bits, 1248/// they can only remove assumed bits. This should guarantee monotoniticy and 1249/// thereby the existence of a fixpoint (if used corretly). The fixpoint is 1250/// reached when the assumed and known state/bits are equal. Users can 1251/// force/inidicate a fixpoint. If an optimistic one is indicated, the known 1252/// state will catch up with the assumed one, for a pessimistic fixpoint it is 1253/// the other way around. 1254template <typename base_ty, base_ty BestState, base_ty WorstState> 1255struct IntegerStateBase : public AbstractState { 1256 using base_t = base_ty; 1257 1258 /// Return the best possible representable state. 1259 static constexpr base_t getBestState() { return BestState; } 1260 1261 /// Return the worst possible representable state. 1262 static constexpr base_t getWorstState() { return WorstState; } 1263 1264 /// See AbstractState::isValidState() 1265 /// NOTE: For now we simply pretend that the worst possible state is invalid. 1266 bool isValidState() const override { return Assumed != getWorstState(); } 1267 1268 /// See AbstractState::isAtFixpoint() 1269 bool isAtFixpoint() const override { return Assumed == Known; } 1270 1271 /// See AbstractState::indicateOptimisticFixpoint(...) 1272 ChangeStatus indicateOptimisticFixpoint() override { 1273 Known = Assumed; 1274 return ChangeStatus::UNCHANGED; 1275 } 1276 1277 /// See AbstractState::indicatePessimisticFixpoint(...) 1278 ChangeStatus indicatePessimisticFixpoint() override { 1279 Assumed = Known; 1280 return ChangeStatus::CHANGED; 1281 } 1282 1283 /// Return the known state encoding 1284 base_t getKnown() const { return Known; } 1285 1286 /// Return the assumed state encoding. 1287 base_t getAssumed() const { return Assumed; } 1288 1289 /// Equality for IntegerStateBase. 1290 bool 1291 operator==(const IntegerStateBase<base_t, BestState, WorstState> &R) const { 1292 return this->getAssumed() == R.getAssumed() && 1293 this->getKnown() == R.getKnown(); 1294 } 1295 1296 /// Inequality for IntegerStateBase. 1297 bool 1298 operator!=(const IntegerStateBase<base_t, BestState, WorstState> &R) const { 1299 return !(*this == R); 1300 } 1301 1302 /// "Clamp" this state with \p R. The result is subtype dependent but it is 1303 /// intended that only information assumed in both states will be assumed in 1304 /// this one afterwards. 1305 void operator^=(const IntegerStateBase<base_t, BestState, WorstState> &R) { 1306 handleNewAssumedValue(R.getAssumed()); 1307 } 1308 1309 void operator|=(const IntegerStateBase<base_t, BestState, WorstState> &R) { 1310 joinOR(R.getAssumed(), R.getKnown()); 1311 } 1312 1313 void operator&=(const IntegerStateBase<base_t, BestState, WorstState> &R) { 1314 joinAND(R.getAssumed(), R.getKnown()); 1315 } 1316 1317protected: 1318 /// Handle a new assumed value \p Value. Subtype dependent. 1319 virtual void handleNewAssumedValue(base_t Value) = 0; 1320 1321 /// Handle a new known value \p Value. Subtype dependent. 1322 virtual void handleNewKnownValue(base_t Value) = 0; 1323 1324 /// Handle a value \p Value. Subtype dependent. 1325 virtual void joinOR(base_t AssumedValue, base_t KnownValue) = 0; 1326 1327 /// Handle a new assumed value \p Value. Subtype dependent. 1328 virtual void joinAND(base_t AssumedValue, base_t KnownValue) = 0; 1329 1330 /// The known state encoding in an integer of type base_t. 1331 base_t Known = getWorstState(); 1332 1333 /// The assumed state encoding in an integer of type base_t. 1334 base_t Assumed = getBestState(); 1335}; 1336 1337/// Specialization of the integer state for a bit-wise encoding. 1338template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0), 1339 base_ty WorstState = 0> 1340struct BitIntegerState 1341 : public IntegerStateBase<base_ty, BestState, WorstState> { 1342 using base_t = base_ty; 1343 1344 /// Return true if the bits set in \p BitsEncoding are "known bits". 1345 bool isKnown(base_t BitsEncoding) const { 1346 return (this->Known & BitsEncoding) == BitsEncoding; 1347 } 1348 1349 /// Return true if the bits set in \p BitsEncoding are "assumed bits". 1350 bool isAssumed(base_t BitsEncoding) const { 1351 return (this->Assumed & BitsEncoding) == BitsEncoding; 1352 } 1353 1354 /// Add the bits in \p BitsEncoding to the "known bits". 1355 BitIntegerState &addKnownBits(base_t Bits) { 1356 // Make sure we never miss any "known bits". 1357 this->Assumed |= Bits; 1358 this->Known |= Bits; 1359 return *this; 1360 } 1361 1362 /// Remove the bits in \p BitsEncoding from the "assumed bits" if not known. 1363 BitIntegerState &removeAssumedBits(base_t BitsEncoding) { 1364 return intersectAssumedBits(~BitsEncoding); 1365 } 1366 1367 /// Remove the bits in \p BitsEncoding from the "known bits". 1368 BitIntegerState &removeKnownBits(base_t BitsEncoding) { 1369 this->Known = (this->Known & ~BitsEncoding); 1370 return *this; 1371 } 1372 1373 /// Keep only "assumed bits" also set in \p BitsEncoding but all known ones. 1374 BitIntegerState &intersectAssumedBits(base_t BitsEncoding) { 1375 // Make sure we never loose any "known bits". 1376 this->Assumed = (this->Assumed & BitsEncoding) | this->Known; 1377 return *this; 1378 } 1379 1380private: 1381 void handleNewAssumedValue(base_t Value) override { 1382 intersectAssumedBits(Value); 1383 } 1384 void handleNewKnownValue(base_t Value) override { addKnownBits(Value); } 1385 void joinOR(base_t AssumedValue, base_t KnownValue) override { 1386 this->Known |= KnownValue; 1387 this->Assumed |= AssumedValue; 1388 } 1389 void joinAND(base_t AssumedValue, base_t KnownValue) override { 1390 this->Known &= KnownValue; 1391 this->Assumed &= AssumedValue; 1392 } 1393}; 1394 1395/// Specialization of the integer state for an increasing value, hence ~0u is 1396/// the best state and 0 the worst. 1397template <typename base_ty = uint32_t, base_ty BestState = ~base_ty(0), 1398 base_ty WorstState = 0> 1399struct IncIntegerState 1400 : public IntegerStateBase<base_ty, BestState, WorstState> { 1401 using base_t = base_ty; 1402 1403 /// Take minimum of assumed and \p Value. 1404 IncIntegerState &takeAssumedMinimum(base_t Value) { 1405 // Make sure we never loose "known value". 1406 this->Assumed = std::max(std::min(this->Assumed, Value), this->Known); 1407 return *this; 1408 } 1409 1410 /// Take maximum of known and \p Value. 1411 IncIntegerState &takeKnownMaximum(base_t Value) { 1412 // Make sure we never loose "known value". 1413 this->Assumed = std::max(Value, this->Assumed); 1414 this->Known = std::max(Value, this->Known); 1415 return *this; 1416 } 1417 1418private: 1419 void handleNewAssumedValue(base_t Value) override { 1420 takeAssumedMinimum(Value); 1421 } 1422 void handleNewKnownValue(base_t Value) override { takeKnownMaximum(Value); } 1423 void joinOR(base_t AssumedValue, base_t KnownValue) override { 1424 this->Known = std::max(this->Known, KnownValue); 1425 this->Assumed = std::max(this->Assumed, AssumedValue); 1426 } 1427 void joinAND(base_t AssumedValue, base_t KnownValue) override { 1428 this->Known = std::min(this->Known, KnownValue); 1429 this->Assumed = std::min(this->Assumed, AssumedValue); 1430 } 1431}; 1432 1433/// Specialization of the integer state for a decreasing value, hence 0 is the 1434/// best state and ~0u the worst. 1435template <typename base_ty = uint32_t> 1436struct DecIntegerState : public IntegerStateBase<base_ty, 0, ~base_ty(0)> { 1437 using base_t = base_ty; 1438 1439 /// Take maximum of assumed and \p Value. 1440 DecIntegerState &takeAssumedMaximum(base_t Value) { 1441 // Make sure we never loose "known value". 1442 this->Assumed = std::min(std::max(this->Assumed, Value), this->Known); 1443 return *this; 1444 } 1445 1446 /// Take minimum of known and \p Value. 1447 DecIntegerState &takeKnownMinimum(base_t Value) { 1448 // Make sure we never loose "known value". 1449 this->Assumed = std::min(Value, this->Assumed); 1450 this->Known = std::min(Value, this->Known); 1451 return *this; 1452 } 1453 1454private: 1455 void handleNewAssumedValue(base_t Value) override { 1456 takeAssumedMaximum(Value); 1457 } 1458 void handleNewKnownValue(base_t Value) override { takeKnownMinimum(Value); } 1459 void joinOR(base_t AssumedValue, base_t KnownValue) override { 1460 this->Assumed = std::min(this->Assumed, KnownValue); 1461 this->Assumed = std::min(this->Assumed, AssumedValue); 1462 } 1463 void joinAND(base_t AssumedValue, base_t KnownValue) override { 1464 this->Assumed = std::max(this->Assumed, KnownValue); 1465 this->Assumed = std::max(this->Assumed, AssumedValue); 1466 } 1467}; 1468 1469/// Simple wrapper for a single bit (boolean) state. 1470struct BooleanState : public IntegerStateBase<bool, 1, 0> { 1471 using base_t = IntegerStateBase::base_t; 1472 1473 /// Set the assumed value to \p Value but never below the known one. 1474 void setAssumed(bool Value) { Assumed &= (Known | Value); } 1475 1476 /// Set the known and asssumed value to \p Value. 1477 void setKnown(bool Value) { 1478 Known |= Value; 1479 Assumed |= Value; 1480 } 1481 1482 /// Return true if the state is assumed to hold. 1483 bool isAssumed() const { return getAssumed(); } 1484 1485 /// Return true if the state is known to hold. 1486 bool isKnown() const { return getKnown(); } 1487 1488private: 1489 void handleNewAssumedValue(base_t Value) override { 1490 if (!Value) 1491 Assumed = Known; 1492 } 1493 void handleNewKnownValue(base_t Value) override { 1494 if (Value) 1495 Known = (Assumed = Value); 1496 } 1497 void joinOR(base_t AssumedValue, base_t KnownValue) override { 1498 Known |= KnownValue; 1499 Assumed |= AssumedValue; 1500 } 1501 void joinAND(base_t AssumedValue, base_t KnownValue) override { 1502 Known &= KnownValue; 1503 Assumed &= AssumedValue; 1504 } 1505}; 1506 1507/// State for an integer range. 1508struct IntegerRangeState : public AbstractState { 1509 1510 /// Bitwidth of the associated value. 1511 uint32_t BitWidth; 1512 1513 /// State representing assumed range, initially set to empty. 1514 ConstantRange Assumed; 1515 1516 /// State representing known range, initially set to [-inf, inf]. 1517 ConstantRange Known; 1518 1519 IntegerRangeState(uint32_t BitWidth) 1520 : BitWidth(BitWidth), Assumed(ConstantRange::getEmpty(BitWidth)), 1521 Known(ConstantRange::getFull(BitWidth)) {} 1522 1523 /// Return the worst possible representable state. 1524 static ConstantRange getWorstState(uint32_t BitWidth) { 1525 return ConstantRange::getFull(BitWidth); 1526 } 1527 1528 /// Return the best possible representable state. 1529 static ConstantRange getBestState(uint32_t BitWidth) { 1530 return ConstantRange::getEmpty(BitWidth); 1531 } 1532 1533 /// Return associated values' bit width. 1534 uint32_t getBitWidth() const { return BitWidth; } 1535 1536 /// See AbstractState::isValidState() 1537 bool isValidState() const override { 1538 return BitWidth > 0 && !Assumed.isFullSet(); 1539 } 1540 1541 /// See AbstractState::isAtFixpoint() 1542 bool isAtFixpoint() const override { return Assumed == Known; } 1543 1544 /// See AbstractState::indicateOptimisticFixpoint(...) 1545 ChangeStatus indicateOptimisticFixpoint() override { 1546 Known = Assumed; 1547 return ChangeStatus::CHANGED; 1548 } 1549 1550 /// See AbstractState::indicatePessimisticFixpoint(...) 1551 ChangeStatus indicatePessimisticFixpoint() override { 1552 Assumed = Known; 1553 return ChangeStatus::CHANGED; 1554 } 1555 1556 /// Return the known state encoding 1557 ConstantRange getKnown() const { return Known; } 1558 1559 /// Return the assumed state encoding. 1560 ConstantRange getAssumed() const { return Assumed; } 1561 1562 /// Unite assumed range with the passed state. 1563 void unionAssumed(const ConstantRange &R) { 1564 // Don't loose a known range. 1565 Assumed = Assumed.unionWith(R).intersectWith(Known); 1566 } 1567 1568 /// See IntegerRangeState::unionAssumed(..). 1569 void unionAssumed(const IntegerRangeState &R) { 1570 unionAssumed(R.getAssumed()); 1571 } 1572 1573 /// Unite known range with the passed state. 1574 void unionKnown(const ConstantRange &R) { 1575 // Don't loose a known range. 1576 Known = Known.unionWith(R); 1577 Assumed = Assumed.unionWith(Known); 1578 } 1579 1580 /// See IntegerRangeState::unionKnown(..). 1581 void unionKnown(const IntegerRangeState &R) { unionKnown(R.getKnown()); } 1582 1583 /// Intersect known range with the passed state. 1584 void intersectKnown(const ConstantRange &R) { 1585 Assumed = Assumed.intersectWith(R); 1586 Known = Known.intersectWith(R); 1587 } 1588 1589 /// See IntegerRangeState::intersectKnown(..). 1590 void intersectKnown(const IntegerRangeState &R) { 1591 intersectKnown(R.getKnown()); 1592 } 1593 1594 /// Equality for IntegerRangeState. 1595 bool operator==(const IntegerRangeState &R) const { 1596 return getAssumed() == R.getAssumed() && getKnown() == R.getKnown(); 1597 } 1598 1599 /// "Clamp" this state with \p R. The result is subtype dependent but it is 1600 /// intended that only information assumed in both states will be assumed in 1601 /// this one afterwards. 1602 IntegerRangeState operator^=(const IntegerRangeState &R) { 1603 // NOTE: `^=` operator seems like `intersect` but in this case, we need to 1604 // take `union`. 1605 unionAssumed(R); 1606 return *this; 1607 } 1608 1609 IntegerRangeState operator&=(const IntegerRangeState &R) { 1610 // NOTE: `&=` operator seems like `intersect` but in this case, we need to 1611 // take `union`. 1612 unionKnown(R); 1613 unionAssumed(R); 1614 return *this; 1615 } 1616}; 1617/// Helper struct necessary as the modular build fails if the virtual method 1618/// IRAttribute::manifest is defined in the Attributor.cpp. 1619struct IRAttributeManifest { 1620 static ChangeStatus manifestAttrs(Attributor &A, const IRPosition &IRP, 1621 const ArrayRef<Attribute> &DeducedAttrs); 1622}; 1623 1624/// Helper to tie a abstract state implementation to an abstract attribute. 1625template <typename StateTy, typename Base> 1626struct StateWrapper : public StateTy, public Base { 1627 /// Provide static access to the type of the state. 1628 using StateType = StateTy; 1629 1630 /// See AbstractAttribute::getState(...). 1631 StateType &getState() override { return *this; } 1632 1633 /// See AbstractAttribute::getState(...). 1634 const AbstractState &getState() const override { return *this; } 1635}; 1636 1637/// Helper class that provides common functionality to manifest IR attributes. 1638template <Attribute::AttrKind AK, typename Base> 1639struct IRAttribute : public IRPosition, public Base { 1640 IRAttribute(const IRPosition &IRP) : IRPosition(IRP) {} 1641 ~IRAttribute() {} 1642 1643 /// See AbstractAttribute::initialize(...). 1644 virtual void initialize(Attributor &A) override { 1645 const IRPosition &IRP = this->getIRPosition(); 1646 if (isa<UndefValue>(IRP.getAssociatedValue()) || hasAttr(getAttrKind())) { 1647 this->getState().indicateOptimisticFixpoint(); 1648 return; 1649 } 1650 1651 bool IsFnInterface = IRP.isFnInterfaceKind(); 1652 const Function *FnScope = IRP.getAnchorScope(); 1653 // TODO: Not all attributes require an exact definition. Find a way to 1654 // enable deduction for some but not all attributes in case the 1655 // definition might be changed at runtime, see also 1656 // http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html. 1657 // TODO: We could always determine abstract attributes and if sufficient 1658 // information was found we could duplicate the functions that do not 1659 // have an exact definition. 1660 if (IsFnInterface && (!FnScope || !FnScope->hasExactDefinition())) 1661 this->getState().indicatePessimisticFixpoint(); 1662 } 1663 1664 /// See AbstractAttribute::manifest(...). 1665 ChangeStatus manifest(Attributor &A) override { 1666 if (isa<UndefValue>(getIRPosition().getAssociatedValue())) 1667 return ChangeStatus::UNCHANGED; 1668 SmallVector<Attribute, 4> DeducedAttrs; 1669 getDeducedAttributes(getAnchorValue().getContext(), DeducedAttrs); 1670 return IRAttributeManifest::manifestAttrs(A, getIRPosition(), DeducedAttrs); 1671 } 1672 1673 /// Return the kind that identifies the abstract attribute implementation. 1674 Attribute::AttrKind getAttrKind() const { return AK; } 1675 1676 /// Return the deduced attributes in \p Attrs. 1677 virtual void getDeducedAttributes(LLVMContext &Ctx, 1678 SmallVectorImpl<Attribute> &Attrs) const { 1679 Attrs.emplace_back(Attribute::get(Ctx, getAttrKind())); 1680 } 1681 1682 /// Return an IR position, see struct IRPosition. 1683 const IRPosition &getIRPosition() const override { return *this; } 1684}; 1685 1686/// Base struct for all "concrete attribute" deductions. 1687/// 1688/// The abstract attribute is a minimal interface that allows the Attributor to 1689/// orchestrate the abstract/fixpoint analysis. The design allows to hide away 1690/// implementation choices made for the subclasses but also to structure their 1691/// implementation and simplify the use of other abstract attributes in-flight. 1692/// 1693/// To allow easy creation of new attributes, most methods have default 1694/// implementations. The ones that do not are generally straight forward, except 1695/// `AbstractAttribute::updateImpl` which is the location of most reasoning 1696/// associated with the abstract attribute. The update is invoked by the 1697/// Attributor in case the situation used to justify the current optimistic 1698/// state might have changed. The Attributor determines this automatically 1699/// by monitoring the `Attributor::getAAFor` calls made by abstract attributes. 1700/// 1701/// The `updateImpl` method should inspect the IR and other abstract attributes 1702/// in-flight to justify the best possible (=optimistic) state. The actual 1703/// implementation is, similar to the underlying abstract state encoding, not 1704/// exposed. In the most common case, the `updateImpl` will go through a list of 1705/// reasons why its optimistic state is valid given the current information. If 1706/// any combination of them holds and is sufficient to justify the current 1707/// optimistic state, the method shall return UNCHAGED. If not, the optimistic 1708/// state is adjusted to the situation and the method shall return CHANGED. 1709/// 1710/// If the manifestation of the "concrete attribute" deduced by the subclass 1711/// differs from the "default" behavior, which is a (set of) LLVM-IR 1712/// attribute(s) for an argument, call site argument, function return value, or 1713/// function, the `AbstractAttribute::manifest` method should be overloaded. 1714/// 1715/// NOTE: If the state obtained via getState() is INVALID, thus if 1716/// AbstractAttribute::getState().isValidState() returns false, no 1717/// information provided by the methods of this class should be used. 1718/// NOTE: The Attributor currently has certain limitations to what we can do. 1719/// As a general rule of thumb, "concrete" abstract attributes should *for 1720/// now* only perform "backward" information propagation. That means 1721/// optimistic information obtained through abstract attributes should 1722/// only be used at positions that precede the origin of the information 1723/// with regards to the program flow. More practically, information can 1724/// *now* be propagated from instructions to their enclosing function, but 1725/// *not* from call sites to the called function. The mechanisms to allow 1726/// both directions will be added in the future. 1727/// NOTE: The mechanics of adding a new "concrete" abstract attribute are 1728/// described in the file comment. 1729struct AbstractAttribute { 1730 using StateType = AbstractState; 1731 1732 /// Virtual destructor. 1733 virtual ~AbstractAttribute() {} 1734 1735 /// Initialize the state with the information in the Attributor \p A. 1736 /// 1737 /// This function is called by the Attributor once all abstract attributes 1738 /// have been identified. It can and shall be used for task like: 1739 /// - identify existing knowledge in the IR and use it for the "known state" 1740 /// - perform any work that is not going to change over time, e.g., determine 1741 /// a subset of the IR, or attributes in-flight, that have to be looked at 1742 /// in the `updateImpl` method. 1743 virtual void initialize(Attributor &A) {} 1744 1745 /// Return the internal abstract state for inspection. 1746 virtual StateType &getState() = 0; 1747 virtual const StateType &getState() const = 0; 1748 1749 /// Return an IR position, see struct IRPosition. 1750 virtual const IRPosition &getIRPosition() const = 0; 1751 1752 /// Helper functions, for debug purposes only. 1753 ///{ 1754 virtual void print(raw_ostream &OS) const; 1755 void dump() const { print(dbgs()); } 1756 1757 /// This function should return the "summarized" assumed state as string. 1758 virtual const std::string getAsStr() const = 0; 1759 ///} 1760 1761 /// Allow the Attributor access to the protected methods. 1762 friend struct Attributor; 1763 1764protected: 1765 /// Hook for the Attributor to trigger an update of the internal state. 1766 /// 1767 /// If this attribute is already fixed, this method will return UNCHANGED, 1768 /// otherwise it delegates to `AbstractAttribute::updateImpl`. 1769 /// 1770 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED. 1771 ChangeStatus update(Attributor &A); 1772 1773 /// Hook for the Attributor to trigger the manifestation of the information 1774 /// represented by the abstract attribute in the LLVM-IR. 1775 /// 1776 /// \Return CHANGED if the IR was altered, otherwise UNCHANGED. 1777 virtual ChangeStatus manifest(Attributor &A) { 1778 return ChangeStatus::UNCHANGED; 1779 } 1780 1781 /// Hook to enable custom statistic tracking, called after manifest that 1782 /// resulted in a change if statistics are enabled. 1783 /// 1784 /// We require subclasses to provide an implementation so we remember to 1785 /// add statistics for them. 1786 virtual void trackStatistics() const = 0; 1787 1788 /// The actual update/transfer function which has to be implemented by the 1789 /// derived classes. 1790 /// 1791 /// If it is called, the environment has changed and we have to determine if 1792 /// the current information is still valid or adjust it otherwise. 1793 /// 1794 /// \Return CHANGED if the internal state changed, otherwise UNCHANGED. 1795 virtual ChangeStatus updateImpl(Attributor &A) = 0; 1796}; 1797 1798/// Forward declarations of output streams for debug purposes. 1799/// 1800///{ 1801raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA); 1802raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S); 1803raw_ostream &operator<<(raw_ostream &OS, IRPosition::Kind); 1804raw_ostream &operator<<(raw_ostream &OS, const IRPosition &); 1805raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State); 1806template <typename base_ty, base_ty BestState, base_ty WorstState> 1807raw_ostream & 1808operator<<(raw_ostream &OS, 1809 const IntegerStateBase<base_ty, BestState, WorstState> &State); 1810raw_ostream &operator<<(raw_ostream &OS, const IntegerRangeState &State); 1811///} 1812 1813struct AttributorPass : public PassInfoMixin<AttributorPass> { 1814 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 1815}; 1816 1817Pass *createAttributorLegacyPass(); 1818 1819/// ---------------------------------------------------------------------------- 1820/// Abstract Attribute Classes 1821/// ---------------------------------------------------------------------------- 1822 1823/// An abstract attribute for the returned values of a function. 1824struct AAReturnedValues 1825 : public IRAttribute<Attribute::Returned, AbstractAttribute> { 1826 AAReturnedValues(const IRPosition &IRP) : IRAttribute(IRP) {} 1827 1828 /// Return an assumed unique return value if a single candidate is found. If 1829 /// there cannot be one, return a nullptr. If it is not clear yet, return the 1830 /// Optional::NoneType. 1831 Optional<Value *> getAssumedUniqueReturnValue(Attributor &A) const; 1832 1833 /// Check \p Pred on all returned values. 1834 /// 1835 /// This method will evaluate \p Pred on returned values and return 1836 /// true if (1) all returned values are known, and (2) \p Pred returned true 1837 /// for all returned values. 1838 /// 1839 /// Note: Unlike the Attributor::checkForAllReturnedValuesAndReturnInsts 1840 /// method, this one will not filter dead return instructions. 1841 virtual bool checkForAllReturnedValuesAndReturnInsts( 1842 const function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> 1843 &Pred) const = 0; 1844 1845 using iterator = 1846 MapVector<Value *, SmallSetVector<ReturnInst *, 4>>::iterator; 1847 using const_iterator = 1848 MapVector<Value *, SmallSetVector<ReturnInst *, 4>>::const_iterator; 1849 virtual llvm::iterator_range<iterator> returned_values() = 0; 1850 virtual llvm::iterator_range<const_iterator> returned_values() const = 0; 1851 1852 virtual size_t getNumReturnValues() const = 0; 1853 virtual const SmallSetVector<CallBase *, 4> &getUnresolvedCalls() const = 0; 1854 1855 /// Create an abstract attribute view for the position \p IRP. 1856 static AAReturnedValues &createForPosition(const IRPosition &IRP, 1857 Attributor &A); 1858 1859 /// Unique ID (due to the unique address) 1860 static const char ID; 1861}; 1862 1863struct AANoUnwind 1864 : public IRAttribute<Attribute::NoUnwind, 1865 StateWrapper<BooleanState, AbstractAttribute>> { 1866 AANoUnwind(const IRPosition &IRP) : IRAttribute(IRP) {} 1867 1868 /// Returns true if nounwind is assumed. 1869 bool isAssumedNoUnwind() const { return getAssumed(); } 1870 1871 /// Returns true if nounwind is known. 1872 bool isKnownNoUnwind() const { return getKnown(); } 1873 1874 /// Create an abstract attribute view for the position \p IRP. 1875 static AANoUnwind &createForPosition(const IRPosition &IRP, Attributor &A); 1876 1877 /// Unique ID (due to the unique address) 1878 static const char ID; 1879}; 1880 1881struct AANoSync 1882 : public IRAttribute<Attribute::NoSync, 1883 StateWrapper<BooleanState, AbstractAttribute>> { 1884 AANoSync(const IRPosition &IRP) : IRAttribute(IRP) {} 1885 1886 /// Returns true if "nosync" is assumed. 1887 bool isAssumedNoSync() const { return getAssumed(); } 1888 1889 /// Returns true if "nosync" is known. 1890 bool isKnownNoSync() const { return getKnown(); } 1891 1892 /// Create an abstract attribute view for the position \p IRP. 1893 static AANoSync &createForPosition(const IRPosition &IRP, Attributor &A); 1894 1895 /// Unique ID (due to the unique address) 1896 static const char ID; 1897}; 1898 1899/// An abstract interface for all nonnull attributes. 1900struct AANonNull 1901 : public IRAttribute<Attribute::NonNull, 1902 StateWrapper<BooleanState, AbstractAttribute>> { 1903 AANonNull(const IRPosition &IRP) : IRAttribute(IRP) {} 1904 1905 /// Return true if we assume that the underlying value is nonnull. 1906 bool isAssumedNonNull() const { return getAssumed(); } 1907 1908 /// Return true if we know that underlying value is nonnull. 1909 bool isKnownNonNull() const { return getKnown(); } 1910 1911 /// Create an abstract attribute view for the position \p IRP. 1912 static AANonNull &createForPosition(const IRPosition &IRP, Attributor &A); 1913 1914 /// Unique ID (due to the unique address) 1915 static const char ID; 1916}; 1917 1918/// An abstract attribute for norecurse. 1919struct AANoRecurse 1920 : public IRAttribute<Attribute::NoRecurse, 1921 StateWrapper<BooleanState, AbstractAttribute>> { 1922 AANoRecurse(const IRPosition &IRP) : IRAttribute(IRP) {} 1923 1924 /// Return true if "norecurse" is assumed. 1925 bool isAssumedNoRecurse() const { return getAssumed(); } 1926 1927 /// Return true if "norecurse" is known. 1928 bool isKnownNoRecurse() const { return getKnown(); } 1929 1930 /// Create an abstract attribute view for the position \p IRP. 1931 static AANoRecurse &createForPosition(const IRPosition &IRP, Attributor &A); 1932 1933 /// Unique ID (due to the unique address) 1934 static const char ID; 1935}; 1936 1937/// An abstract attribute for willreturn. 1938struct AAWillReturn 1939 : public IRAttribute<Attribute::WillReturn, 1940 StateWrapper<BooleanState, AbstractAttribute>> { 1941 AAWillReturn(const IRPosition &IRP) : IRAttribute(IRP) {} 1942 1943 /// Return true if "willreturn" is assumed. 1944 bool isAssumedWillReturn() const { return getAssumed(); } 1945 1946 /// Return true if "willreturn" is known. 1947 bool isKnownWillReturn() const { return getKnown(); } 1948 1949 /// Create an abstract attribute view for the position \p IRP. 1950 static AAWillReturn &createForPosition(const IRPosition &IRP, Attributor &A); 1951 1952 /// Unique ID (due to the unique address) 1953 static const char ID; 1954}; 1955 1956/// An abstract attribute for undefined behavior. 1957struct AAUndefinedBehavior 1958 : public StateWrapper<BooleanState, AbstractAttribute>, 1959 public IRPosition { 1960 AAUndefinedBehavior(const IRPosition &IRP) : IRPosition(IRP) {} 1961 1962 /// Return true if "undefined behavior" is assumed. 1963 bool isAssumedToCauseUB() const { return getAssumed(); } 1964 1965 /// Return true if "undefined behavior" is assumed for a specific instruction. 1966 virtual bool isAssumedToCauseUB(Instruction *I) const = 0; 1967 1968 /// Return true if "undefined behavior" is known. 1969 bool isKnownToCauseUB() const { return getKnown(); } 1970 1971 /// Return true if "undefined behavior" is known for a specific instruction. 1972 virtual bool isKnownToCauseUB(Instruction *I) const = 0; 1973 1974 /// Return an IR position, see struct IRPosition. 1975 const IRPosition &getIRPosition() const override { return *this; } 1976 1977 /// Create an abstract attribute view for the position \p IRP. 1978 static AAUndefinedBehavior &createForPosition(const IRPosition &IRP, 1979 Attributor &A); 1980 1981 /// Unique ID (due to the unique address) 1982 static const char ID; 1983}; 1984 1985/// An abstract interface to determine reachability of point A to B. 1986struct AAReachability : public StateWrapper<BooleanState, AbstractAttribute>, 1987 public IRPosition { 1988 AAReachability(const IRPosition &IRP) : IRPosition(IRP) {} 1989 1990 /// Returns true if 'From' instruction is assumed to reach, 'To' instruction. 1991 /// Users should provide two positions they are interested in, and the class 1992 /// determines (and caches) reachability. 1993 bool isAssumedReachable(const Instruction *From, 1994 const Instruction *To) const { 1995 return true; 1996 } 1997 1998 /// Returns true if 'From' instruction is known to reach, 'To' instruction. 1999 /// Users should provide two positions they are interested in, and the class 2000 /// determines (and caches) reachability. 2001 bool isKnownReachable(const Instruction *From, const Instruction *To) const { 2002 return true; 2003 } 2004 2005 /// Return an IR position, see struct IRPosition. 2006 const IRPosition &getIRPosition() const override { return *this; } 2007 2008 /// Create an abstract attribute view for the position \p IRP. 2009 static AAReachability &createForPosition(const IRPosition &IRP, 2010 Attributor &A); 2011 2012 /// Unique ID (due to the unique address) 2013 static const char ID; 2014}; 2015 2016/// An abstract interface for all noalias attributes. 2017struct AANoAlias 2018 : public IRAttribute<Attribute::NoAlias, 2019 StateWrapper<BooleanState, AbstractAttribute>> { 2020 AANoAlias(const IRPosition &IRP) : IRAttribute(IRP) {} 2021 2022 /// Return true if we assume that the underlying value is alias. 2023 bool isAssumedNoAlias() const { return getAssumed(); } 2024 2025 /// Return true if we know that underlying value is noalias. 2026 bool isKnownNoAlias() const { return getKnown(); } 2027 2028 /// Create an abstract attribute view for the position \p IRP. 2029 static AANoAlias &createForPosition(const IRPosition &IRP, Attributor &A); 2030 2031 /// Unique ID (due to the unique address) 2032 static const char ID; 2033}; 2034 2035/// An AbstractAttribute for nofree. 2036struct AANoFree 2037 : public IRAttribute<Attribute::NoFree, 2038 StateWrapper<BooleanState, AbstractAttribute>> { 2039 AANoFree(const IRPosition &IRP) : IRAttribute(IRP) {} 2040 2041 /// Return true if "nofree" is assumed. 2042 bool isAssumedNoFree() const { return getAssumed(); } 2043 2044 /// Return true if "nofree" is known. 2045 bool isKnownNoFree() const { return getKnown(); } 2046 2047 /// Create an abstract attribute view for the position \p IRP. 2048 static AANoFree &createForPosition(const IRPosition &IRP, Attributor &A); 2049 2050 /// Unique ID (due to the unique address) 2051 static const char ID; 2052}; 2053 2054/// An AbstractAttribute for noreturn. 2055struct AANoReturn 2056 : public IRAttribute<Attribute::NoReturn, 2057 StateWrapper<BooleanState, AbstractAttribute>> { 2058 AANoReturn(const IRPosition &IRP) : IRAttribute(IRP) {} 2059 2060 /// Return true if the underlying object is assumed to never return. 2061 bool isAssumedNoReturn() const { return getAssumed(); } 2062 2063 /// Return true if the underlying object is known to never return. 2064 bool isKnownNoReturn() const { return getKnown(); } 2065 2066 /// Create an abstract attribute view for the position \p IRP. 2067 static AANoReturn &createForPosition(const IRPosition &IRP, Attributor &A); 2068 2069 /// Unique ID (due to the unique address) 2070 static const char ID; 2071}; 2072 2073/// An abstract interface for liveness abstract attribute. 2074struct AAIsDead : public StateWrapper<BooleanState, AbstractAttribute>, 2075 public IRPosition { 2076 AAIsDead(const IRPosition &IRP) : IRPosition(IRP) {} 2077 2078 /// Returns true if the underlying value is assumed dead. 2079 virtual bool isAssumedDead() const = 0; 2080 2081 /// Returns true if \p BB is assumed dead. 2082 virtual bool isAssumedDead(const BasicBlock *BB) const = 0; 2083 2084 /// Returns true if \p BB is known dead. 2085 virtual bool isKnownDead(const BasicBlock *BB) const = 0; 2086 2087 /// Returns true if \p I is assumed dead. 2088 virtual bool isAssumedDead(const Instruction *I) const = 0; 2089 2090 /// Returns true if \p I is known dead. 2091 virtual bool isKnownDead(const Instruction *I) const = 0; 2092 2093 /// This method is used to check if at least one instruction in a collection 2094 /// of instructions is live. 2095 template <typename T> bool isLiveInstSet(T begin, T end) const { 2096 for (const auto &I : llvm::make_range(begin, end)) { 2097 assert(I->getFunction() == getIRPosition().getAssociatedFunction() && 2098 "Instruction must be in the same anchor scope function."); 2099 2100 if (!isAssumedDead(I)) 2101 return true; 2102 } 2103 2104 return false; 2105 } 2106 2107 /// Return an IR position, see struct IRPosition. 2108 const IRPosition &getIRPosition() const override { return *this; } 2109 2110 /// Create an abstract attribute view for the position \p IRP. 2111 static AAIsDead &createForPosition(const IRPosition &IRP, Attributor &A); 2112 2113 /// Unique ID (due to the unique address) 2114 static const char ID; 2115}; 2116 2117/// State for dereferenceable attribute 2118struct DerefState : AbstractState { 2119 2120 /// State representing for dereferenceable bytes. 2121 IncIntegerState<> DerefBytesState; 2122 2123 /// Map representing for accessed memory offsets and sizes. 2124 /// A key is Offset and a value is size. 2125 /// If there is a load/store instruction something like, 2126 /// p[offset] = v; 2127 /// (offset, sizeof(v)) will be inserted to this map. 2128 /// std::map is used because we want to iterate keys in ascending order. 2129 std::map<int64_t, uint64_t> AccessedBytesMap; 2130 2131 /// Helper function to calculate dereferenceable bytes from current known 2132 /// bytes and accessed bytes. 2133 /// 2134 /// int f(int *A){ 2135 /// *A = 0; 2136 /// *(A+2) = 2; 2137 /// *(A+1) = 1; 2138 /// *(A+10) = 10; 2139 /// } 2140 /// ``` 2141 /// In that case, AccessedBytesMap is `{0:4, 4:4, 8:4, 40:4}`. 2142 /// AccessedBytesMap is std::map so it is iterated in accending order on 2143 /// key(Offset). So KnownBytes will be updated like this: 2144 /// 2145 /// |Access | KnownBytes 2146 /// |(0, 4)| 0 -> 4 2147 /// |(4, 4)| 4 -> 8 2148 /// |(8, 4)| 8 -> 12 2149 /// |(40, 4) | 12 (break) 2150 void computeKnownDerefBytesFromAccessedMap() { 2151 int64_t KnownBytes = DerefBytesState.getKnown(); 2152 for (auto &Access : AccessedBytesMap) { 2153 if (KnownBytes < Access.first) 2154 break; 2155 KnownBytes = std::max(KnownBytes, Access.first + (int64_t)Access.second); 2156 } 2157 2158 DerefBytesState.takeKnownMaximum(KnownBytes); 2159 } 2160 2161 /// State representing that whether the value is globaly dereferenceable. 2162 BooleanState GlobalState; 2163 2164 /// See AbstractState::isValidState() 2165 bool isValidState() const override { return DerefBytesState.isValidState(); } 2166 2167 /// See AbstractState::isAtFixpoint() 2168 bool isAtFixpoint() const override { 2169 return !isValidState() || 2170 (DerefBytesState.isAtFixpoint() && GlobalState.isAtFixpoint()); 2171 } 2172 2173 /// See AbstractState::indicateOptimisticFixpoint(...) 2174 ChangeStatus indicateOptimisticFixpoint() override { 2175 DerefBytesState.indicateOptimisticFixpoint(); 2176 GlobalState.indicateOptimisticFixpoint(); 2177 return ChangeStatus::UNCHANGED; 2178 } 2179 2180 /// See AbstractState::indicatePessimisticFixpoint(...) 2181 ChangeStatus indicatePessimisticFixpoint() override { 2182 DerefBytesState.indicatePessimisticFixpoint(); 2183 GlobalState.indicatePessimisticFixpoint(); 2184 return ChangeStatus::CHANGED; 2185 } 2186 2187 /// Update known dereferenceable bytes. 2188 void takeKnownDerefBytesMaximum(uint64_t Bytes) { 2189 DerefBytesState.takeKnownMaximum(Bytes); 2190 2191 // Known bytes might increase. 2192 computeKnownDerefBytesFromAccessedMap(); 2193 } 2194 2195 /// Update assumed dereferenceable bytes. 2196 void takeAssumedDerefBytesMinimum(uint64_t Bytes) { 2197 DerefBytesState.takeAssumedMinimum(Bytes); 2198 } 2199 2200 /// Add accessed bytes to the map. 2201 void addAccessedBytes(int64_t Offset, uint64_t Size) { 2202 AccessedBytesMap[Offset] = std::max(AccessedBytesMap[Offset], Size); 2203 2204 // Known bytes might increase. 2205 computeKnownDerefBytesFromAccessedMap(); 2206 } 2207 2208 /// Equality for DerefState. 2209 bool operator==(const DerefState &R) { 2210 return this->DerefBytesState == R.DerefBytesState && 2211 this->GlobalState == R.GlobalState; 2212 } 2213 2214 /// Inequality for DerefState. 2215 bool operator!=(const DerefState &R) { return !(*this == R); } 2216 2217 /// See IntegerStateBase::operator^= 2218 DerefState operator^=(const DerefState &R) { 2219 DerefBytesState ^= R.DerefBytesState; 2220 GlobalState ^= R.GlobalState; 2221 return *this; 2222 } 2223 2224 /// See IntegerStateBase::operator&= 2225 DerefState operator&=(const DerefState &R) { 2226 DerefBytesState &= R.DerefBytesState; 2227 GlobalState &= R.GlobalState; 2228 return *this; 2229 } 2230 2231 /// See IntegerStateBase::operator|= 2232 DerefState operator|=(const DerefState &R) { 2233 DerefBytesState |= R.DerefBytesState; 2234 GlobalState |= R.GlobalState; 2235 return *this; 2236 } 2237 2238protected: 2239 const AANonNull *NonNullAA = nullptr; 2240}; 2241 2242/// An abstract interface for all dereferenceable attribute. 2243struct AADereferenceable 2244 : public IRAttribute<Attribute::Dereferenceable, 2245 StateWrapper<DerefState, AbstractAttribute>> { 2246 AADereferenceable(const IRPosition &IRP) : IRAttribute(IRP) {} 2247 2248 /// Return true if we assume that the underlying value is nonnull. 2249 bool isAssumedNonNull() const { 2250 return NonNullAA && NonNullAA->isAssumedNonNull(); 2251 } 2252 2253 /// Return true if we know that the underlying value is nonnull. 2254 bool isKnownNonNull() const { 2255 return NonNullAA && NonNullAA->isKnownNonNull(); 2256 } 2257 2258 /// Return true if we assume that underlying value is 2259 /// dereferenceable(_or_null) globally. 2260 bool isAssumedGlobal() const { return GlobalState.getAssumed(); } 2261 2262 /// Return true if we know that underlying value is 2263 /// dereferenceable(_or_null) globally. 2264 bool isKnownGlobal() const { return GlobalState.getKnown(); } 2265 2266 /// Return assumed dereferenceable bytes. 2267 uint32_t getAssumedDereferenceableBytes() const { 2268 return DerefBytesState.getAssumed(); 2269 } 2270 2271 /// Return known dereferenceable bytes. 2272 uint32_t getKnownDereferenceableBytes() const { 2273 return DerefBytesState.getKnown(); 2274 } 2275 2276 /// Create an abstract attribute view for the position \p IRP. 2277 static AADereferenceable &createForPosition(const IRPosition &IRP, 2278 Attributor &A); 2279 2280 /// Unique ID (due to the unique address) 2281 static const char ID; 2282}; 2283 2284using AAAlignmentStateType = 2285 IncIntegerState<uint32_t, /* maximal alignment */ 1U << 29, 0>; 2286/// An abstract interface for all align attributes. 2287struct AAAlign : public IRAttribute< 2288 Attribute::Alignment, 2289 StateWrapper<AAAlignmentStateType, AbstractAttribute>> { 2290 AAAlign(const IRPosition &IRP) : IRAttribute(IRP) {} 2291 2292 /// Return assumed alignment. 2293 unsigned getAssumedAlign() const { return getAssumed(); } 2294 2295 /// Return known alignment. 2296 unsigned getKnownAlign() const { return getKnown(); } 2297 2298 /// Create an abstract attribute view for the position \p IRP. 2299 static AAAlign &createForPosition(const IRPosition &IRP, Attributor &A); 2300 2301 /// Unique ID (due to the unique address) 2302 static const char ID; 2303}; 2304 2305/// An abstract interface for all nocapture attributes. 2306struct AANoCapture 2307 : public IRAttribute< 2308 Attribute::NoCapture, 2309 StateWrapper<BitIntegerState<uint16_t, 7, 0>, AbstractAttribute>> { 2310 AANoCapture(const IRPosition &IRP) : IRAttribute(IRP) {} 2311 2312 /// State encoding bits. A set bit in the state means the property holds. 2313 /// NO_CAPTURE is the best possible state, 0 the worst possible state. 2314 enum { 2315 NOT_CAPTURED_IN_MEM = 1 << 0, 2316 NOT_CAPTURED_IN_INT = 1 << 1, 2317 NOT_CAPTURED_IN_RET = 1 << 2, 2318 2319 /// If we do not capture the value in memory or through integers we can only 2320 /// communicate it back as a derived pointer. 2321 NO_CAPTURE_MAYBE_RETURNED = NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT, 2322 2323 /// If we do not capture the value in memory, through integers, or as a 2324 /// derived pointer we know it is not captured. 2325 NO_CAPTURE = 2326 NOT_CAPTURED_IN_MEM | NOT_CAPTURED_IN_INT | NOT_CAPTURED_IN_RET, 2327 }; 2328 2329 /// Return true if we know that the underlying value is not captured in its 2330 /// respective scope. 2331 bool isKnownNoCapture() const { return isKnown(NO_CAPTURE); } 2332 2333 /// Return true if we assume that the underlying value is not captured in its 2334 /// respective scope. 2335 bool isAssumedNoCapture() const { return isAssumed(NO_CAPTURE); } 2336 2337 /// Return true if we know that the underlying value is not captured in its 2338 /// respective scope but we allow it to escape through a "return". 2339 bool isKnownNoCaptureMaybeReturned() const { 2340 return isKnown(NO_CAPTURE_MAYBE_RETURNED); 2341 } 2342 2343 /// Return true if we assume that the underlying value is not captured in its 2344 /// respective scope but we allow it to escape through a "return". 2345 bool isAssumedNoCaptureMaybeReturned() const { 2346 return isAssumed(NO_CAPTURE_MAYBE_RETURNED); 2347 } 2348 2349 /// Create an abstract attribute view for the position \p IRP. 2350 static AANoCapture &createForPosition(const IRPosition &IRP, Attributor &A); 2351 2352 /// Unique ID (due to the unique address) 2353 static const char ID; 2354}; 2355 2356/// An abstract interface for value simplify abstract attribute. 2357struct AAValueSimplify : public StateWrapper<BooleanState, AbstractAttribute>, 2358 public IRPosition { 2359 AAValueSimplify(const IRPosition &IRP) : IRPosition(IRP) {} 2360 2361 /// Return an IR position, see struct IRPosition. 2362 const IRPosition &getIRPosition() const { return *this; } 2363 2364 /// Return an assumed simplified value if a single candidate is found. If 2365 /// there cannot be one, return original value. If it is not clear yet, return 2366 /// the Optional::NoneType. 2367 virtual Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const = 0; 2368 2369 /// Create an abstract attribute view for the position \p IRP. 2370 static AAValueSimplify &createForPosition(const IRPosition &IRP, 2371 Attributor &A); 2372 2373 /// Unique ID (due to the unique address) 2374 static const char ID; 2375}; 2376 2377struct AAHeapToStack : public StateWrapper<BooleanState, AbstractAttribute>, 2378 public IRPosition { 2379 AAHeapToStack(const IRPosition &IRP) : IRPosition(IRP) {} 2380 2381 /// Returns true if HeapToStack conversion is assumed to be possible. 2382 bool isAssumedHeapToStack() const { return getAssumed(); } 2383 2384 /// Returns true if HeapToStack conversion is known to be possible. 2385 bool isKnownHeapToStack() const { return getKnown(); } 2386 2387 /// Return an IR position, see struct IRPosition. 2388 const IRPosition &getIRPosition() const { return *this; } 2389 2390 /// Create an abstract attribute view for the position \p IRP. 2391 static AAHeapToStack &createForPosition(const IRPosition &IRP, Attributor &A); 2392 2393 /// Unique ID (due to the unique address) 2394 static const char ID; 2395}; 2396 2397/// An abstract interface for all memory related attributes. 2398struct AAMemoryBehavior 2399 : public IRAttribute< 2400 Attribute::ReadNone, 2401 StateWrapper<BitIntegerState<uint8_t, 3>, AbstractAttribute>> { 2402 AAMemoryBehavior(const IRPosition &IRP) : IRAttribute(IRP) {} 2403 2404 /// State encoding bits. A set bit in the state means the property holds. 2405 /// BEST_STATE is the best possible state, 0 the worst possible state. 2406 enum { 2407 NO_READS = 1 << 0, 2408 NO_WRITES = 1 << 1, 2409 NO_ACCESSES = NO_READS | NO_WRITES, 2410 2411 BEST_STATE = NO_ACCESSES, 2412 }; 2413 2414 /// Return true if we know that the underlying value is not read or accessed 2415 /// in its respective scope. 2416 bool isKnownReadNone() const { return isKnown(NO_ACCESSES); } 2417 2418 /// Return true if we assume that the underlying value is not read or accessed 2419 /// in its respective scope. 2420 bool isAssumedReadNone() const { return isAssumed(NO_ACCESSES); } 2421 2422 /// Return true if we know that the underlying value is not accessed 2423 /// (=written) in its respective scope. 2424 bool isKnownReadOnly() const { return isKnown(NO_WRITES); } 2425 2426 /// Return true if we assume that the underlying value is not accessed 2427 /// (=written) in its respective scope. 2428 bool isAssumedReadOnly() const { return isAssumed(NO_WRITES); } 2429 2430 /// Return true if we know that the underlying value is not read in its 2431 /// respective scope. 2432 bool isKnownWriteOnly() const { return isKnown(NO_READS); } 2433 2434 /// Return true if we assume that the underlying value is not read in its 2435 /// respective scope. 2436 bool isAssumedWriteOnly() const { return isAssumed(NO_READS); } 2437 2438 /// Create an abstract attribute view for the position \p IRP. 2439 static AAMemoryBehavior &createForPosition(const IRPosition &IRP, 2440 Attributor &A); 2441 2442 /// Unique ID (due to the unique address) 2443 static const char ID; 2444}; 2445 2446/// An abstract interface for range value analysis. 2447struct AAValueConstantRange : public IntegerRangeState, 2448 public AbstractAttribute, 2449 public IRPosition { 2450 AAValueConstantRange(const IRPosition &IRP) 2451 : IntegerRangeState( 2452 IRP.getAssociatedValue().getType()->getIntegerBitWidth()), 2453 IRPosition(IRP) {} 2454 2455 /// Return an IR position, see struct IRPosition. 2456 const IRPosition &getIRPosition() const override { return *this; } 2457 2458 /// See AbstractAttribute::getState(...). 2459 IntegerRangeState &getState() override { return *this; } 2460 const AbstractState &getState() const override { return *this; } 2461 2462 /// Create an abstract attribute view for the position \p IRP. 2463 static AAValueConstantRange &createForPosition(const IRPosition &IRP, 2464 Attributor &A); 2465 2466 /// Return an assumed range for the assocaited value a program point \p CtxI. 2467 /// If \p I is nullptr, simply return an assumed range. 2468 virtual ConstantRange 2469 getAssumedConstantRange(Attributor &A, 2470 const Instruction *CtxI = nullptr) const = 0; 2471 2472 /// Return a known range for the assocaited value at a program point \p CtxI. 2473 /// If \p I is nullptr, simply return a known range. 2474 virtual ConstantRange 2475 getKnownConstantRange(Attributor &A, 2476 const Instruction *CtxI = nullptr) const = 0; 2477 2478 /// Return an assumed constant for the assocaited value a program point \p 2479 /// CtxI. 2480 Optional<ConstantInt *> 2481 getAssumedConstantInt(Attributor &A, const Instruction *CtxI = nullptr) const { 2482 ConstantRange RangeV = getAssumedConstantRange(A, CtxI); 2483 if (auto *C = RangeV.getSingleElement()) 2484 return cast<ConstantInt>( 2485 ConstantInt::get(getAssociatedValue().getType(), *C)); 2486 if (RangeV.isEmptySet()) 2487 return llvm::None; 2488 return nullptr; 2489 } 2490 2491 /// Unique ID (due to the unique address) 2492 static const char ID; 2493}; 2494 2495} // end namespace llvm 2496 2497#endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H 2498