polly/lib/Support/VirtualInstruction.cpp

   1 //===------ VirtualInstruction.cpp ------------------------------*- 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 // Tools for determining which instructions are within a statement and the
  10 // nature of their operands.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "polly/Support/VirtualInstruction.h"
  15
  16 using namespace polly;
  17 using namespace llvm;
  18
  19 VirtualUse VirtualUse::create(Scop *S, const Use &U, LoopInfo *LI,
  20                               bool Virtual) {
  21   auto *UserBB = getUseBlock(U);
  22   Loop *UserScope = LI->getLoopFor(UserBB);
  23   Instruction *UI = dyn_cast<Instruction>(U.getUser());
  24   ScopStmt *UserStmt = S->getStmtFor(UI);
  25
  26   // Uses by PHI nodes are always reading values written by other statements,
  27   // except it is within a region statement.
  28   if (PHINode *PHI = dyn_cast<PHINode>(UI)) {
  29     // Handle PHI in exit block.
  30     if (S->getRegion().getExit() == PHI->getParent())
  31       return VirtualUse(UserStmt, U.get(), Inter, nullptr, nullptr);
  32
  33     if (UserStmt->getEntryBlock() != PHI->getParent())
  34       return VirtualUse(UserStmt, U.get(), Intra, nullptr, nullptr);
  35
  36     // The MemoryAccess is expected to be set if @p Virtual is true.
  37     MemoryAccess *IncomingMA = nullptr;
  38     if (Virtual) {
  39       if (const ScopArrayInfo *SAI =
  40               S->getScopArrayInfoOrNull(PHI, MemoryKind::PHI)) {
  41         IncomingMA = S->getPHIRead(SAI);
  42         assert(IncomingMA->getStatement() == UserStmt);
  43       }
  44     }
  45
  46     return VirtualUse(UserStmt, U.get(), Inter, nullptr, IncomingMA);
  47   }
  48
  49   return create(S, UserStmt, UserScope, U.get(), Virtual);
  50 }
  51
  52 VirtualUse VirtualUse::create(Scop *S, ScopStmt *UserStmt, Loop *UserScope,
  53                               Value *Val, bool Virtual) {
  54   assert(!isa<StoreInst>(Val) && "a StoreInst cannot be used");
  55
  56   if (isa<BasicBlock>(Val))
  57     return VirtualUse(UserStmt, Val, Block, nullptr, nullptr);
  58
  59   if (isa<llvm::Constant>(Val) || isa<MetadataAsValue>(Val) ||
  60       isa<InlineAsm>(Val))
  61     return VirtualUse(UserStmt, Val, Constant, nullptr, nullptr);
  62
  63   // Is the value synthesizable? If the user has been pruned
  64   // (UserStmt == nullptr), it is either not used anywhere or is synthesizable.
  65   // We assume synthesizable which practically should have the same effect.
  66   auto *SE = S->getSE();
  67   if (SE->isSCEVable(Val->getType())) {
  68     auto *ScevExpr = SE->getSCEVAtScope(Val, UserScope);
  69     if (!UserStmt || canSynthesize(Val, *UserStmt->getParent(), SE, UserScope))
  70       return VirtualUse(UserStmt, Val, Synthesizable, ScevExpr, nullptr);
  71   }
  72
  73   // FIXME: Inconsistency between lookupInvariantEquivClass and
  74   // getRequiredInvariantLoads. Querying one of them should be enough.
  75   auto &RIL = S->getRequiredInvariantLoads();
  76   if (S->lookupInvariantEquivClass(Val) || RIL.count(dyn_cast<LoadInst>(Val)))
  77     return VirtualUse(UserStmt, Val, Hoisted, nullptr, nullptr);
  78
  79   // ReadOnly uses may have MemoryAccesses that we want to associate with the
  80   // use. This is why we look for a MemoryAccess here already.
  81   MemoryAccess *InputMA = nullptr;
  82   if (UserStmt && Virtual)
  83     InputMA = UserStmt->lookupValueReadOf(Val);
  84
  85   // Uses are read-only if they have been defined before the SCoP, i.e., they
  86   // cannot be written to inside the SCoP. Arguments are defined before any
  87   // instructions, hence also before the SCoP. If the user has been pruned
  88   // (UserStmt == nullptr) and is not SCEVable, assume it is read-only as it is
  89   // neither an intra- nor an inter-use.
  90   if (!UserStmt || isa<Argument>(Val))
  91     return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
  92
  93   auto Inst = cast<Instruction>(Val);
  94   if (!S->contains(Inst))
  95     return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
  96
  97   // A use is inter-statement if either it is defined in another statement, or
  98   // there is a MemoryAccess that reads its value that has been written by
  99   // another statement.
 100   if (InputMA || (!Virtual && UserStmt != S->getStmtFor(Inst)))
 101     return VirtualUse(UserStmt, Val, Inter, nullptr, InputMA);
 102
 103   return VirtualUse(UserStmt, Val, Intra, nullptr, nullptr);
 104 }
 105
 106 void VirtualUse::print(raw_ostream &OS, bool Reproducible) const {
 107   OS << "User: [" << User->getBaseName() << "] ";
 108   switch (Kind) {
 109   case VirtualUse::Constant:
 110     OS << "Constant Op:";
 111     break;
 112   case VirtualUse::Block:
 113     OS << "BasicBlock Op:";
 114     break;
 115   case VirtualUse::Synthesizable:
 116     OS << "Synthesizable Op:";
 117     break;
 118   case VirtualUse::Hoisted:
 119     OS << "Hoisted load Op:";
 120     break;
 121   case VirtualUse::ReadOnly:
 122     OS << "Read-Only Op:";
 123     break;
 124   case VirtualUse::Intra:
 125     OS << "Intra Op:";
 126     break;
 127   case VirtualUse::Inter:
 128     OS << "Inter Op:";
 129     break;
 130   }
 131
 132   if (Val) {
 133     OS << ' ';
 134     if (Reproducible)
 135       OS << '"' << Val->getName() << '"';
 136     else
 137       Val->print(OS, true);
 138   }
 139   if (ScevExpr) {
 140     OS << ' ';
 141     ScevExpr->print(OS);
 142   }
 143   if (InputMA && !Reproducible)
 144     OS << ' ' << InputMA;
 145 }
 146
 147 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 148 LLVM_DUMP_METHOD void VirtualUse::dump() const {
 149   print(errs(), false);
 150   errs() << '\n';
 151 }
 152 #endif
 153
 154 void VirtualInstruction::print(raw_ostream &OS, bool Reproducible) const {
 155   if (!Stmt || !Inst) {
 156     OS << "[null VirtualInstruction]";
 157     return;
 158   }
 159
 160   OS << "[" << Stmt->getBaseName() << "]";
 161   Inst->print(OS, !Reproducible);
 162 }
 163
 164 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 165 LLVM_DUMP_METHOD void VirtualInstruction::dump() const {
 166   print(errs(), false);
 167   errs() << '\n';
 168 }
 169 #endif
 170
 171 /// Return true if @p Inst cannot be removed, even if it is nowhere referenced.
 172 static bool isRoot(const Instruction *Inst) {
 173   // The store is handled by its MemoryAccess. The load must be reached from the
 174   // roots in order to be marked as used.
 175   if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
 176     return false;
 177
 178   // Terminator instructions (in region statements) are required for control
 179   // flow.
 180   if (Inst->isTerminator())
 181     return true;
 182
 183   // Writes to memory must be honored.
 184   if (Inst->mayWriteToMemory())
 185     return true;
 186
 187   return false;
 188 }
 189
 190 /// Return true for MemoryAccesses that cannot be removed because it represents
 191 /// an llvm::Value that is used after the SCoP.
 192 static bool isEscaping(MemoryAccess *MA) {
 193   assert(MA->isOriginalValueKind());
 194   Scop *S = MA->getStatement()->getParent();
 195   return S->isEscaping(cast<Instruction>(MA->getAccessValue()));
 196 }
 197
 198 /// Add non-removable virtual instructions in @p Stmt to @p RootInsts.
 199 static void
 200 addInstructionRoots(ScopStmt *Stmt,
 201                     SmallVectorImpl<VirtualInstruction> &RootInsts) {
 202   if (!Stmt->isBlockStmt()) {
 203     // In region statements the terminator statement and all statements that
 204     // are not in the entry block cannot be eliminated and consequently must
 205     // be roots.
 206     RootInsts.emplace_back(Stmt,
 207                            Stmt->getRegion()->getEntry()->getTerminator());
 208     for (BasicBlock *BB : Stmt->getRegion()->blocks())
 209       if (Stmt->getRegion()->getEntry() != BB)
 210         for (Instruction &Inst : *BB)
 211           RootInsts.emplace_back(Stmt, &Inst);
 212     return;
 213   }
 214
 215   for (Instruction *Inst : Stmt->getInstructions())
 216     if (isRoot(Inst))
 217       RootInsts.emplace_back(Stmt, Inst);
 218 }
 219
 220 /// Add non-removable memory accesses in @p Stmt to @p RootInsts.
 221 ///
 222 /// @param Local If true, all writes are assumed to escape. markAndSweep
 223 /// algorithms can use this to be applicable to a single ScopStmt only without
 224 /// the risk of removing definitions required by other statements.
 225 ///              If false, only writes for SCoP-escaping values are roots.  This
 226 ///              is global mode, where such writes must be marked by theirs uses
 227 ///              in order to be reachable.
 228 static void addAccessRoots(ScopStmt *Stmt,
 229                            SmallVectorImpl<MemoryAccess *> &RootAccs,
 230                            bool Local) {
 231   for (auto *MA : *Stmt) {
 232     if (!MA->isWrite())
 233       continue;
 234
 235     // Writes to arrays are always used.
 236     if (MA->isLatestArrayKind())
 237       RootAccs.push_back(MA);
 238
 239     // Values are roots if they are escaping.
 240     else if (MA->isLatestValueKind()) {
 241       if (Local || isEscaping(MA))
 242         RootAccs.push_back(MA);
 243     }
 244
 245     // Exit phis are, by definition, escaping.
 246     else if (MA->isLatestExitPHIKind())
 247       RootAccs.push_back(MA);
 248
 249     // phi writes are only roots if we are not visiting the statement
 250     // containing the PHINode.
 251     else if (Local && MA->isLatestPHIKind())
 252       RootAccs.push_back(MA);
 253   }
 254 }
 255
 256 /// Determine all instruction and access roots.
 257 static void addRoots(ScopStmt *Stmt,
 258                      SmallVectorImpl<VirtualInstruction> &RootInsts,
 259                      SmallVectorImpl<MemoryAccess *> &RootAccs, bool Local) {
 260   addInstructionRoots(Stmt, RootInsts);
 261   addAccessRoots(Stmt, RootAccs, Local);
 262 }
 263
 264 /// Mark accesses and instructions as used if they are reachable from a root,
 265 /// walking the operand trees.
 266 ///
 267 /// @param S              The SCoP to walk.
 268 /// @param LI             The LoopInfo Analysis.
 269 /// @param RootInsts      List of root instructions.
 270 /// @param RootAccs       List of root accesses.
 271 /// @param UsesInsts[out] Receives all reachable instructions, including the
 272 /// roots.
 273 /// @param UsedAccs[out]  Receives all reachable accesses, including the roots.
 274 /// @param OnlyLocal      If non-nullptr, restricts walking to a single
 275 /// statement.
 276 static void walkReachable(Scop *S, LoopInfo *LI,
 277                           ArrayRef<VirtualInstruction> RootInsts,
 278                           ArrayRef<MemoryAccess *> RootAccs,
 279                           DenseSet<VirtualInstruction> &UsedInsts,
 280                           DenseSet<MemoryAccess *> &UsedAccs,
 281                           ScopStmt *OnlyLocal = nullptr) {
 282   UsedInsts.clear();
 283   UsedAccs.clear();
 284
 285   SmallVector<VirtualInstruction, 32> WorklistInsts;
 286   SmallVector<MemoryAccess *, 32> WorklistAccs;
 287
 288   WorklistInsts.append(RootInsts.begin(), RootInsts.end());
 289   WorklistAccs.append(RootAccs.begin(), RootAccs.end());
 290
 291   auto AddToWorklist = [&](VirtualUse VUse) {
 292     switch (VUse.getKind()) {
 293     case VirtualUse::Block:
 294     case VirtualUse::Constant:
 295     case VirtualUse::Synthesizable:
 296     case VirtualUse::Hoisted:
 297       break;
 298     case VirtualUse::ReadOnly:
 299       // Read-only scalars only have MemoryAccesses if ModelReadOnlyScalars is
 300       // enabled.
 301       if (!VUse.getMemoryAccess())
 302         break;
 303       [[fallthrough]];
 304     case VirtualUse::Inter:
 305       assert(VUse.getMemoryAccess());
 306       WorklistAccs.push_back(VUse.getMemoryAccess());
 307       break;
 308     case VirtualUse::Intra:
 309       WorklistInsts.emplace_back(VUse.getUser(),
 310                                  cast<Instruction>(VUse.getValue()));
 311       break;
 312     }
 313   };
 314
 315   while (true) {
 316     // We have two worklists to process: Only when the MemoryAccess worklist is
 317     // empty, we process the instruction worklist.
 318
 319     while (!WorklistAccs.empty()) {
 320       auto *Acc = WorklistAccs.pop_back_val();
 321
 322       ScopStmt *Stmt = Acc->getStatement();
 323       if (OnlyLocal && Stmt != OnlyLocal)
 324         continue;
 325
 326       auto Inserted = UsedAccs.insert(Acc);
 327       if (!Inserted.second)
 328         continue;
 329
 330       if (Acc->isRead()) {
 331         const ScopArrayInfo *SAI = Acc->getScopArrayInfo();
 332
 333         if (Acc->isLatestValueKind()) {
 334           MemoryAccess *DefAcc = S->getValueDef(SAI);
 335
 336           // Accesses to read-only values do not have a definition.
 337           if (DefAcc)
 338             WorklistAccs.push_back(S->getValueDef(SAI));
 339         }
 340
 341         if (Acc->isLatestAnyPHIKind()) {
 342           auto IncomingMAs = S->getPHIIncomings(SAI);
 343           WorklistAccs.append(IncomingMAs.begin(), IncomingMAs.end());
 344         }
 345       }
 346
 347       if (Acc->isWrite()) {
 348         if (Acc->isOriginalValueKind() ||
 349             (Acc->isOriginalArrayKind() && Acc->getAccessValue())) {
 350           Loop *Scope = Stmt->getSurroundingLoop();
 351           VirtualUse VUse =
 352               VirtualUse::create(S, Stmt, Scope, Acc->getAccessValue(), true);
 353           AddToWorklist(VUse);
 354         }
 355
 356         if (Acc->isOriginalAnyPHIKind()) {
 357           for (auto Incoming : Acc->getIncoming()) {
 358             VirtualUse VUse = VirtualUse::create(
 359                 S, Stmt, LI->getLoopFor(Incoming.first), Incoming.second, true);
 360             AddToWorklist(VUse);
 361           }
 362         }
 363
 364         if (Acc->isOriginalArrayKind())
 365           WorklistInsts.emplace_back(Stmt, Acc->getAccessInstruction());
 366       }
 367     }
 368
 369     // If both worklists are empty, stop walking.
 370     if (WorklistInsts.empty())
 371       break;
 372
 373     VirtualInstruction VInst = WorklistInsts.pop_back_val();
 374     ScopStmt *Stmt = VInst.getStmt();
 375     Instruction *Inst = VInst.getInstruction();
 376
 377     // Do not process statements other than the local.
 378     if (OnlyLocal && Stmt != OnlyLocal)
 379       continue;
 380
 381     auto InsertResult = UsedInsts.insert(VInst);
 382     if (!InsertResult.second)
 383       continue;
 384
 385     // Add all operands to the worklists.
 386     PHINode *PHI = dyn_cast<PHINode>(Inst);
 387     if (PHI && PHI->getParent() == Stmt->getEntryBlock()) {
 388       if (MemoryAccess *PHIRead = Stmt->lookupPHIReadOf(PHI))
 389         WorklistAccs.push_back(PHIRead);
 390     } else {
 391       for (VirtualUse VUse : VInst.operands())
 392         AddToWorklist(VUse);
 393     }
 394
 395     // If there is an array access, also add its MemoryAccesses to the worklist.
 396     const MemoryAccessList *Accs = Stmt->lookupArrayAccessesFor(Inst);
 397     if (!Accs)
 398       continue;
 399
 400     for (MemoryAccess *Acc : *Accs)
 401       WorklistAccs.push_back(Acc);
 402   }
 403 }
 404
 405 void polly::markReachable(Scop *S, LoopInfo *LI,
 406                           DenseSet<VirtualInstruction> &UsedInsts,
 407                           DenseSet<MemoryAccess *> &UsedAccs,
 408                           ScopStmt *OnlyLocal) {
 409   SmallVector<VirtualInstruction, 32> RootInsts;
 410   SmallVector<MemoryAccess *, 32> RootAccs;
 411
 412   if (OnlyLocal) {
 413     addRoots(OnlyLocal, RootInsts, RootAccs, true);
 414   } else {
 415     for (auto &Stmt : *S)
 416       addRoots(&Stmt, RootInsts, RootAccs, false);
 417   }
 418
 419   walkReachable(S, LI, RootInsts, RootAccs, UsedInsts, UsedAccs, OnlyLocal);
 420 }