421 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// Tools for determining which instructions are within a statement and the10// nature of their operands.11//12//===----------------------------------------------------------------------===//13 14#include "polly/Support/VirtualInstruction.h"15 16using namespace polly;17using namespace llvm;18 19VirtualUse 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 52VirtualUse 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 pruned64 // (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 const SCEV *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 and74 // 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 the80 // 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., they86 // cannot be written to inside the SCoP. Arguments are defined before any87 // instructions, hence also before the SCoP. If the user has been pruned88 // (UserStmt == nullptr) and is not SCEVable, assume it is read-only as it is89 // 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, or98 // there is a MemoryAccess that reads its value that has been written by99 // 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 106void 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 else137 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)148LLVM_DUMP_METHOD void VirtualUse::dump() const {149 print(errs(), false);150 errs() << '\n';151}152#endif153 154void 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)165LLVM_DUMP_METHOD void VirtualInstruction::dump() const {166 print(errs(), false);167 errs() << '\n';168}169#endif170 171/// Return true if @p Inst cannot be removed, even if it is nowhere referenced.172static bool isRoot(const Instruction *Inst) {173 // The store is handled by its MemoryAccess. The load must be reached from the174 // 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 control179 // 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 represents191/// an llvm::Value that is used after the SCoP.192static 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.199static void200addInstructionRoots(ScopStmt *Stmt,201 SmallVectorImpl<VirtualInstruction> &RootInsts) {202 if (!Stmt->isBlockStmt()) {203 // In region statements the terminator statement and all statements that204 // are not in the entry block cannot be eliminated and consequently must205 // 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. markAndSweep223/// algorithms can use this to be applicable to a single ScopStmt only without224/// the risk of removing definitions required by other statements.225/// If false, only writes for SCoP-escaping values are roots. This226/// is global mode, where such writes must be marked by theirs uses227/// in order to be reachable.228static 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 statement250 // containing the PHINode.251 else if (Local && MA->isLatestPHIKind())252 RootAccs.push_back(MA);253 }254}255 256/// Determine all instruction and access roots.257static 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 the272/// roots.273/// @param UsedAccs[out] Receives all reachable accesses, including the roots.274/// @param OnlyLocal If non-nullptr, restricts walking to a single275/// statement.276static 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 is300 // 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 is317 // 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 405void 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}421