lib/Transforms/IPO/Attributor.cpp

   1 //===- Attributor.cpp - Module-wide attribute deduction -------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements an inter procedural pass that deduces and/or propagating
  10 // attributes. This is done in an abstract interpretation style fixpoint
  11 // iteration. See the Attributor.h file comment and the class descriptions in
  12 // that file for more information.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/IPO/Attributor.h"
  17
  18 #include "llvm/ADT/SetVector.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/Analysis/GlobalsModRef.h"
  23 #include "llvm/IR/Argument.h"
  24 #include "llvm/IR/Attributes.h"
  25 #include "llvm/IR/InstIterator.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include <cassert>
  30
  31 using namespace llvm;
  32
  33 #define DEBUG_TYPE "attributor"
  34
  35 STATISTIC(NumFnWithExactDefinition,
  36           "Number of function with exact definitions");
  37 STATISTIC(NumFnWithoutExactDefinition,
  38           "Number of function without exact definitions");
  39 STATISTIC(NumAttributesTimedOut,
  40           "Number of abstract attributes timed out before fixpoint");
  41 STATISTIC(NumAttributesValidFixpoint,
  42           "Number of abstract attributes in a valid fixpoint state");
  43 STATISTIC(NumAttributesManifested,
  44           "Number of abstract attributes manifested in IR");
  45
  46 // TODO: Determine a good default value.
  47 //
  48 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
  49 // (when run with the first 5 abstract attributes). The results also indicate
  50 // that we never reach 32 iterations but always find a fixpoint sooner.
  51 //
  52 // This will become more evolved once we perform two interleaved fixpoint
  53 // iterations: bottom-up and top-down.
  54 static cl::opt<unsigned>
  55     MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
  56                           cl::desc("Maximal number of fixpoint iterations."),
  57                           cl::init(32));
  58
  59 static cl::opt<bool> DisableAttributor(
  60     "attributor-disable", cl::Hidden,
  61     cl::desc("Disable the attributor inter-procedural deduction pass."),
  62     cl::init(true));
  63
  64 static cl::opt<bool> VerifyAttributor(
  65     "attributor-verify", cl::Hidden,
  66     cl::desc("Verify the Attributor deduction and "
  67              "manifestation of attributes -- may issue false-positive errors"),
  68     cl::init(false));
  69
  70 /// Logic operators for the change status enum class.
  71 ///
  72 ///{
  73 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
  74   return l == ChangeStatus::CHANGED ? l : r;
  75 }
  76 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
  77   return l == ChangeStatus::UNCHANGED ? l : r;
  78 }
  79 ///}
  80
  81 /// Helper to adjust the statistics.
  82 static void bookkeeping(AbstractAttribute::ManifestPosition MP,
  83                         const Attribute &Attr) {
  84   if (!AreStatisticsEnabled())
  85     return;
  86
  87   if (!Attr.isEnumAttribute())
  88     return;
  89   //switch (Attr.getKindAsEnum()) {
  90   //default:
  91   //  return;
  92   //}
  93 }
  94
  95 /// Helper to identify the correct offset into an attribute list.
  96 static unsigned getAttrIndex(AbstractAttribute::ManifestPosition MP,
  97                              unsigned ArgNo = 0) {
  98   switch (MP) {
  99   case AbstractAttribute::MP_ARGUMENT:
 100   case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
 101     return ArgNo + AttributeList::FirstArgIndex;
 102   case AbstractAttribute::MP_FUNCTION:
 103     return AttributeList::FunctionIndex;
 104   case AbstractAttribute::MP_RETURNED:
 105     return AttributeList::ReturnIndex;
 106   }
 107   llvm_unreachable("Unknown manifest position!");
 108 }
 109
 110 /// Return true if \p New is equal or worse than \p Old.
 111 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
 112   if (!Old.isIntAttribute())
 113     return true;
 114
 115   return Old.getValueAsInt() >= New.getValueAsInt();
 116 }
 117
 118 /// Return true if the information provided by \p Attr was added to the
 119 /// attribute list \p Attrs. This is only the case if it was not already present
 120 /// in \p Attrs at the position describe by \p MP and \p ArgNo.
 121 static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
 122                              AttributeList &Attrs,
 123                              AbstractAttribute::ManifestPosition MP,
 124                              unsigned ArgNo = 0) {
 125   unsigned AttrIdx = getAttrIndex(MP, ArgNo);
 126
 127   if (Attr.isEnumAttribute()) {
 128     Attribute::AttrKind Kind = Attr.getKindAsEnum();
 129     if (Attrs.hasAttribute(AttrIdx, Kind))
 130       if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
 131         return false;
 132     Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
 133     return true;
 134   }
 135   if (Attr.isStringAttribute()) {
 136     StringRef Kind = Attr.getKindAsString();
 137     if (Attrs.hasAttribute(AttrIdx, Kind))
 138       if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
 139         return false;
 140     Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
 141     return true;
 142   }
 143
 144   llvm_unreachable("Expected enum or string attribute!");
 145 }
 146
 147 ChangeStatus AbstractAttribute::update(Attributor &A) {
 148   ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
 149   if (getState().isAtFixpoint())
 150     return HasChanged;
 151
 152   LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
 153
 154   HasChanged = updateImpl(A);
 155
 156   LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
 157                     << "\n");
 158
 159   return HasChanged;
 160 }
 161
 162 ChangeStatus AbstractAttribute::manifest(Attributor &A) {
 163   assert(getState().isValidState() &&
 164          "Attempted to manifest an invalid state!");
 165   assert(getAssociatedValue() &&
 166          "Attempted to manifest an attribute without associated value!");
 167
 168   ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
 169   SmallVector<Attribute, 4> DeducedAttrs;
 170   getDeducedAttributes(DeducedAttrs);
 171
 172   Function &ScopeFn = getAnchorScope();
 173   LLVMContext &Ctx = ScopeFn.getContext();
 174   ManifestPosition MP = getManifestPosition();
 175
 176   AttributeList Attrs;
 177   SmallVector<unsigned, 4> ArgNos;
 178
 179   // In the following some generic code that will manifest attributes in
 180   // DeducedAttrs if they improve the current IR. Due to the different
 181   // annotation positions we use the underlying AttributeList interface.
 182   // Note that MP_CALL_SITE_ARGUMENT can annotate multiple locations.
 183
 184   switch (MP) {
 185   case MP_ARGUMENT:
 186     ArgNos.push_back(cast<Argument>(getAssociatedValue())->getArgNo());
 187     Attrs = ScopeFn.getAttributes();
 188     break;
 189   case MP_FUNCTION:
 190   case MP_RETURNED:
 191     ArgNos.push_back(0);
 192     Attrs = ScopeFn.getAttributes();
 193     break;
 194   case MP_CALL_SITE_ARGUMENT: {
 195     CallSite CS(&getAnchoredValue());
 196     for (unsigned u = 0, e = CS.getNumArgOperands(); u != e; u++)
 197       if (CS.getArgOperand(u) == getAssociatedValue())
 198         ArgNos.push_back(u);
 199     Attrs = CS.getAttributes();
 200   }
 201   }
 202
 203   for (const Attribute &Attr : DeducedAttrs) {
 204     for (unsigned ArgNo : ArgNos) {
 205       if (!addIfNotExistent(Ctx, Attr, Attrs, MP, ArgNo))
 206         continue;
 207
 208       HasChanged = ChangeStatus::CHANGED;
 209       bookkeeping(MP, Attr);
 210     }
 211   }
 212
 213   if (HasChanged == ChangeStatus::UNCHANGED)
 214     return HasChanged;
 215
 216   switch (MP) {
 217   case MP_ARGUMENT:
 218   case MP_FUNCTION:
 219   case MP_RETURNED:
 220     ScopeFn.setAttributes(Attrs);
 221     break;
 222   case MP_CALL_SITE_ARGUMENT:
 223     CallSite(&getAnchoredValue()).setAttributes(Attrs);
 224   }
 225
 226   return HasChanged;
 227 }
 228
 229 Function &AbstractAttribute::getAnchorScope() {
 230   Value &V = getAnchoredValue();
 231   if (isa<Function>(V))
 232     return cast<Function>(V);
 233   if (isa<Argument>(V))
 234     return *cast<Argument>(V).getParent();
 235   if (isa<Instruction>(V))
 236     return *cast<Instruction>(V).getFunction();
 237   llvm_unreachable("No scope for anchored value found!");
 238 }
 239
 240 const Function &AbstractAttribute::getAnchorScope() const {
 241   return const_cast<AbstractAttribute *>(this)->getAnchorScope();
 242 }
 243
 244 /// ----------------------------------------------------------------------------
 245 ///                               Attributor
 246 /// ----------------------------------------------------------------------------
 247
 248 ChangeStatus Attributor::run() {
 249   // Initialize all abstract attributes.
 250   for (AbstractAttribute *AA : AllAbstractAttributes)
 251     AA->initialize(*this);
 252
 253   LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
 254                     << AllAbstractAttributes.size()
 255                     << " abstract attributes.\n");
 256
 257   // Now that all abstract attributes are collected and initialized we start the
 258   // abstract analysis.
 259
 260   unsigned IterationCounter = 1;
 261
 262   SmallVector<AbstractAttribute *, 64> ChangedAAs;
 263   SetVector<AbstractAttribute *> Worklist;
 264   Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
 265
 266   do {
 267     LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
 268                       << ", Worklist size: " << Worklist.size() << "\n");
 269
 270     // Add all abstract attributes that are potentially dependent on one that
 271     // changed to the work list.
 272     for (AbstractAttribute *ChangedAA : ChangedAAs) {
 273       auto &QuerriedAAs = QueryMap[ChangedAA];
 274       Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
 275     }
 276
 277     // Reset the changed set.
 278     ChangedAAs.clear();
 279
 280     // Update all abstract attribute in the work list and record the ones that
 281     // changed.
 282     for (AbstractAttribute *AA : Worklist)
 283       if (AA->update(*this) == ChangeStatus::CHANGED)
 284         ChangedAAs.push_back(AA);
 285
 286     // Reset the work list and repopulate with the changed abstract attributes.
 287     // Note that dependent ones are added above.
 288     Worklist.clear();
 289     Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
 290
 291   } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
 292
 293   LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
 294                     << IterationCounter << "/" << MaxFixpointIterations
 295                     << " iterations\n");
 296
 297   bool FinishedAtFixpoint = Worklist.empty();
 298
 299   // Reset abstract arguments not settled in a sound fixpoint by now. This
 300   // happens when we stopped the fixpoint iteration early. Note that only the
 301   // ones marked as "changed" *and* the ones transitively depending on them
 302   // need to be reverted to a pessimistic state. Others might not be in a
 303   // fixpoint state but we can use the optimistic results for them anyway.
 304   SmallPtrSet<AbstractAttribute *, 32> Visited;
 305   for (unsigned u = 0; u < ChangedAAs.size(); u++) {
 306     AbstractAttribute *ChangedAA = ChangedAAs[u];
 307     if (!Visited.insert(ChangedAA).second)
 308       continue;
 309
 310     AbstractState &State = ChangedAA->getState();
 311     if (!State.isAtFixpoint()) {
 312       State.indicatePessimisticFixpoint();
 313
 314       NumAttributesTimedOut++;
 315     }
 316
 317     auto &QuerriedAAs = QueryMap[ChangedAA];
 318     ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end());
 319   }
 320
 321   LLVM_DEBUG({
 322     if (!Visited.empty())
 323       dbgs() << "\n[Attributor] Finalized " << Visited.size()
 324              << " abstract attributes.\n";
 325   });
 326
 327   unsigned NumManifested = 0;
 328   unsigned NumAtFixpoint = 0;
 329   ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
 330   for (AbstractAttribute *AA : AllAbstractAttributes) {
 331     AbstractState &State = AA->getState();
 332
 333     // If there is not already a fixpoint reached, we can now take the
 334     // optimistic state. This is correct because we enforced a pessimistic one
 335     // on abstract attributes that were transitively dependent on a changed one
 336     // already above.
 337     if (!State.isAtFixpoint())
 338       State.indicateOptimisticFixpoint();
 339
 340     // If the state is invalid, we do not try to manifest it.
 341     if (!State.isValidState())
 342       continue;
 343
 344     // Manifest the state and record if we changed the IR.
 345     ChangeStatus LocalChange = AA->manifest(*this);
 346     ManifestChange = ManifestChange | LocalChange;
 347
 348     NumAtFixpoint++;
 349     NumManifested += (LocalChange == ChangeStatus::CHANGED);
 350   }
 351
 352   (void)NumManifested;
 353   (void)NumAtFixpoint;
 354   LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
 355                     << " arguments while " << NumAtFixpoint
 356                     << " were in a valid fixpoint state\n");
 357
 358   // If verification is requested, we finished this run at a fixpoint, and the
 359   // IR was changed, we re-run the whole fixpoint analysis, starting at
 360   // re-initialization of the arguments. This re-run should not result in an IR
 361   // change. Though, the (virtual) state of attributes at the end of the re-run
 362   // might be more optimistic than the known state or the IR state if the better
 363   // state cannot be manifested.
 364   if (VerifyAttributor && FinishedAtFixpoint &&
 365       ManifestChange == ChangeStatus::CHANGED) {
 366     VerifyAttributor = false;
 367     ChangeStatus VerifyStatus = run();
 368     if (VerifyStatus != ChangeStatus::UNCHANGED)
 369       llvm_unreachable(
 370           "Attributor verification failed, re-run did result in an IR change "
 371           "even after a fixpoint was reached in the original run. (False "
 372           "positives possible!)");
 373     VerifyAttributor = true;
 374   }
 375
 376   NumAttributesManifested += NumManifested;
 377   NumAttributesValidFixpoint += NumAtFixpoint;
 378
 379   return ManifestChange;
 380 }
 381
 382 void Attributor::identifyDefaultAbstractAttributes(
 383     Function &F, InformationCache &InfoCache,
 384     DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
 385
 386   // Walk all instructions to find more attribute opportunities and also
 387   // interesting instructions that might be queried by abstract attributes
 388   // during their initialization or update.
 389   auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
 390   auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
 391
 392   for (Instruction &I : instructions(&F)) {
 393     bool IsInterestingOpcode = false;
 394
 395     // To allow easy access to all instructions in a function with a given
 396     // opcode we store them in the InfoCache. As not all opcodes are interesting
 397     // to concrete attributes we only cache the ones that are as identified in
 398     // the following switch.
 399     // Note: There are no concrete attributes now so this is initially empty.
 400     //switch (I.getOpcode()) {
 401     //default:
 402     //  break;
 403     //}
 404     if (IsInterestingOpcode)
 405       InstOpcodeMap[I.getOpcode()].push_back(&I);
 406     if (I.mayReadOrWriteMemory())
 407       ReadOrWriteInsts.push_back(&I);
 408   }
 409 }
 410
 411 /// Helpers to ease debugging through output streams and print calls.
 412 ///
 413 ///{
 414 raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
 415   return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
 416 }
 417
 418 raw_ostream &llvm::operator<<(raw_ostream &OS,
 419                               AbstractAttribute::ManifestPosition AP) {
 420   switch (AP) {
 421   case AbstractAttribute::MP_ARGUMENT:
 422     return OS << "arg";
 423   case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
 424     return OS << "cs_arg";
 425   case AbstractAttribute::MP_FUNCTION:
 426     return OS << "fn";
 427   case AbstractAttribute::MP_RETURNED:
 428     return OS << "fn_ret";
 429   }
 430   llvm_unreachable("Unknown attribute position!");
 431 }
 432
 433 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
 434   return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
 435 }
 436
 437 raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
 438   AA.print(OS);
 439   return OS;
 440 }
 441
 442 void AbstractAttribute::print(raw_ostream &OS) const {
 443   OS << "[" << getManifestPosition() << "][" << getAsStr() << "]["
 444      << AnchoredVal.getName() << "]";
 445 }
 446 ///}
 447
 448 /// ----------------------------------------------------------------------------
 449 ///                       Pass (Manager) Boilerplate
 450 /// ----------------------------------------------------------------------------
 451
 452 static bool runAttributorOnModule(Module &M) {
 453   if (DisableAttributor)
 454     return false;
 455
 456   LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
 457                     << " functions.\n");
 458
 459   // Create an Attributor and initially empty information cache that is filled
 460   // while we identify default attribute opportunities.
 461   Attributor A;
 462   InformationCache InfoCache;
 463
 464   for (Function &F : M) {
 465     // TODO: Not all attributes require an exact definition. Find a way to
 466     //       enable deduction for some but not all attributes in case the
 467     //       definition might be changed at runtime, see also
 468     //       http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
 469     // TODO: We could always determine abstract attributes and if sufficient
 470     //       information was found we could duplicate the functions that do not
 471     //       have an exact definition.
 472     if (!F.hasExactDefinition()) {
 473       NumFnWithoutExactDefinition++;
 474       continue;
 475     }
 476
 477     // For now we ignore naked and optnone functions.
 478     if (F.hasFnAttribute(Attribute::Naked) ||
 479         F.hasFnAttribute(Attribute::OptimizeNone))
 480       continue;
 481
 482     NumFnWithExactDefinition++;
 483
 484     // Populate the Attributor with abstract attribute opportunities in the
 485     // function and the information cache with IR information.
 486     A.identifyDefaultAbstractAttributes(F, InfoCache);
 487   }
 488
 489   return A.run() == ChangeStatus::CHANGED;
 490 }
 491
 492 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
 493   if (runAttributorOnModule(M)) {
 494     // FIXME: Think about passes we will preserve and add them here.
 495     return PreservedAnalyses::none();
 496   }
 497   return PreservedAnalyses::all();
 498 }
 499
 500 namespace {
 501
 502 struct AttributorLegacyPass : public ModulePass {
 503   static char ID;
 504
 505   AttributorLegacyPass() : ModulePass(ID) {
 506     initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry());
 507   }
 508
 509   bool runOnModule(Module &M) override {
 510     if (skipModule(M))
 511       return false;
 512     return runAttributorOnModule(M);
 513   }
 514
 515   void getAnalysisUsage(AnalysisUsage &AU) const override {
 516     // FIXME: Think about passes we will preserve and add them here.
 517     AU.setPreservesCFG();
 518   }
 519 };
 520
 521 } // end anonymous namespace
 522
 523 Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
 524
 525 char AttributorLegacyPass::ID = 0;
 526 INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
 527                       "Deduce and propagate attributes", false, false)
 528 INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
 529                     "Deduce and propagate attributes", false, false)