Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 1 | //===- MustExecute.cpp - Printer for isGuaranteedToExecute ----------------===// |
| 2 | // |
Chandler Carruth | 2946cd7 | 2019-01-19 08:50:56 +0000 | [diff] [blame] | 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 |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
Philip Reames | e4b728e | 2018-03-29 19:22:12 +0000 | [diff] [blame] | 9 | #include "llvm/Analysis/MustExecute.h" |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 10 | #include "llvm/Analysis/InstructionSimplify.h" |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 11 | #include "llvm/Analysis/LoopInfo.h" |
| 12 | #include "llvm/Analysis/Passes.h" |
| 13 | #include "llvm/Analysis/ValueTracking.h" |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 14 | #include "llvm/IR/AssemblyAnnotationWriter.h" |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 15 | #include "llvm/IR/DataLayout.h" |
| 16 | #include "llvm/IR/InstIterator.h" |
| 17 | #include "llvm/IR/LLVMContext.h" |
| 18 | #include "llvm/IR/Module.h" |
| 19 | #include "llvm/Support/ErrorHandling.h" |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 20 | #include "llvm/Support/FormattedStream.h" |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 21 | #include "llvm/Support/raw_ostream.h" |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 22 | using namespace llvm; |
| 23 | |
Max Kazantsev | 8d56be7 | 2018-10-16 08:07:14 +0000 | [diff] [blame] | 24 | const DenseMap<BasicBlock *, ColorVector> & |
| 25 | LoopSafetyInfo::getBlockColors() const { |
| 26 | return BlockColors; |
| 27 | } |
| 28 | |
| 29 | void LoopSafetyInfo::copyColors(BasicBlock *New, BasicBlock *Old) { |
| 30 | ColorVector &ColorsForNewBlock = BlockColors[New]; |
| 31 | ColorVector &ColorsForOldBlock = BlockColors[Old]; |
| 32 | ColorsForNewBlock = ColorsForOldBlock; |
| 33 | } |
| 34 | |
Max Kazantsev | 9c90ec2 | 2018-10-16 08:31:05 +0000 | [diff] [blame] | 35 | bool SimpleLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const { |
Max Kazantsev | 6a4f5e2 | 2018-10-16 07:50:14 +0000 | [diff] [blame] | 36 | (void)BB; |
| 37 | return anyBlockMayThrow(); |
| 38 | } |
| 39 | |
Max Kazantsev | 9c90ec2 | 2018-10-16 08:31:05 +0000 | [diff] [blame] | 40 | bool SimpleLoopSafetyInfo::anyBlockMayThrow() const { |
Max Kazantsev | 530b8d1 | 2018-08-15 05:55:43 +0000 | [diff] [blame] | 41 | return MayThrow; |
| 42 | } |
| 43 | |
Max Kazantsev | 9c90ec2 | 2018-10-16 08:31:05 +0000 | [diff] [blame] | 44 | void SimpleLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) { |
Shoaib Meenai | a57d713 | 2018-07-19 19:11:29 +0000 | [diff] [blame] | 45 | assert(CurLoop != nullptr && "CurLoop can't be null"); |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 46 | BasicBlock *Header = CurLoop->getHeader(); |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 47 | // Iterate over header and compute safety info. |
Max Kazantsev | 530b8d1 | 2018-08-15 05:55:43 +0000 | [diff] [blame] | 48 | HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header); |
| 49 | MayThrow = HeaderMayThrow; |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 50 | // Iterate over loop instructions and compute safety info. |
| 51 | // Skip header as it has been computed and stored in HeaderMayThrow. |
| 52 | // The first block in loopinfo.Blocks is guaranteed to be the header. |
| 53 | assert(Header == *CurLoop->getBlocks().begin() && |
| 54 | "First block must be header"); |
| 55 | for (Loop::block_iterator BB = std::next(CurLoop->block_begin()), |
| 56 | BBE = CurLoop->block_end(); |
Max Kazantsev | 530b8d1 | 2018-08-15 05:55:43 +0000 | [diff] [blame] | 57 | (BB != BBE) && !MayThrow; ++BB) |
| 58 | MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB); |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 59 | |
Max Kazantsev | 8d56be7 | 2018-10-16 08:07:14 +0000 | [diff] [blame] | 60 | computeBlockColors(CurLoop); |
| 61 | } |
| 62 | |
Max Kazantsev | 5f9acd2 | 2018-10-16 09:58:09 +0000 | [diff] [blame] | 63 | bool ICFLoopSafetyInfo::blockMayThrow(const BasicBlock *BB) const { |
| 64 | return ICF.hasICF(BB); |
| 65 | } |
| 66 | |
| 67 | bool ICFLoopSafetyInfo::anyBlockMayThrow() const { |
| 68 | return MayThrow; |
| 69 | } |
| 70 | |
| 71 | void ICFLoopSafetyInfo::computeLoopSafetyInfo(const Loop *CurLoop) { |
| 72 | assert(CurLoop != nullptr && "CurLoop can't be null"); |
| 73 | ICF.clear(); |
Max Kazantsev | 7d49a3a | 2018-11-12 09:29:58 +0000 | [diff] [blame] | 74 | MW.clear(); |
Max Kazantsev | 5f9acd2 | 2018-10-16 09:58:09 +0000 | [diff] [blame] | 75 | MayThrow = false; |
| 76 | // Figure out the fact that at least one block may throw. |
| 77 | for (auto &BB : CurLoop->blocks()) |
| 78 | if (ICF.hasICF(&*BB)) { |
| 79 | MayThrow = true; |
| 80 | break; |
| 81 | } |
| 82 | computeBlockColors(CurLoop); |
| 83 | } |
| 84 | |
Max Kazantsev | 4615a50 | 2019-01-09 07:28:13 +0000 | [diff] [blame] | 85 | void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst, |
| 86 | const BasicBlock *BB) { |
| 87 | ICF.insertInstructionTo(Inst, BB); |
| 88 | MW.insertInstructionTo(Inst, BB); |
Max Kazantsev | 5f9acd2 | 2018-10-16 09:58:09 +0000 | [diff] [blame] | 89 | } |
| 90 | |
Max Kazantsev | bb84407 | 2018-11-01 10:16:06 +0000 | [diff] [blame] | 91 | void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) { |
Max Kazantsev | 4615a50 | 2019-01-09 07:28:13 +0000 | [diff] [blame] | 92 | ICF.removeInstruction(Inst); |
| 93 | MW.removeInstruction(Inst); |
Max Kazantsev | bb84407 | 2018-11-01 10:16:06 +0000 | [diff] [blame] | 94 | } |
| 95 | |
Max Kazantsev | 8d56be7 | 2018-10-16 08:07:14 +0000 | [diff] [blame] | 96 | void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) { |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 97 | // Compute funclet colors if we might sink/hoist in a function with a funclet |
| 98 | // personality routine. |
| 99 | Function *Fn = CurLoop->getHeader()->getParent(); |
| 100 | if (Fn->hasPersonalityFn()) |
| 101 | if (Constant *PersonalityFn = Fn->getPersonalityFn()) |
Heejin Ahn | b4be38f | 2018-05-17 20:52:03 +0000 | [diff] [blame] | 102 | if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn))) |
Max Kazantsev | 530b8d1 | 2018-08-15 05:55:43 +0000 | [diff] [blame] | 103 | BlockColors = colorEHFunclets(*Fn); |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 104 | } |
| 105 | |
| 106 | /// Return true if we can prove that the given ExitBlock is not reached on the |
| 107 | /// first iteration of the given loop. That is, the backedge of the loop must |
| 108 | /// be executed before the ExitBlock is executed in any dynamic execution trace. |
Max Kazantsev | a741587 | 2018-08-16 06:28:04 +0000 | [diff] [blame] | 109 | static bool CanProveNotTakenFirstIteration(const BasicBlock *ExitBlock, |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 110 | const DominatorTree *DT, |
| 111 | const Loop *CurLoop) { |
| 112 | auto *CondExitBlock = ExitBlock->getSinglePredecessor(); |
| 113 | if (!CondExitBlock) |
| 114 | // expect unique exits |
| 115 | return false; |
| 116 | assert(CurLoop->contains(CondExitBlock) && "meaning of exit block"); |
| 117 | auto *BI = dyn_cast<BranchInst>(CondExitBlock->getTerminator()); |
| 118 | if (!BI || !BI->isConditional()) |
| 119 | return false; |
Serguei Katkov | 5095883 | 2018-05-18 04:56:28 +0000 | [diff] [blame] | 120 | // If condition is constant and false leads to ExitBlock then we always |
| 121 | // execute the true branch. |
| 122 | if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) |
| 123 | return BI->getSuccessor(Cond->getZExtValue() ? 1 : 0) == ExitBlock; |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 124 | auto *Cond = dyn_cast<CmpInst>(BI->getCondition()); |
| 125 | if (!Cond) |
| 126 | return false; |
| 127 | // todo: this would be a lot more powerful if we used scev, but all the |
| 128 | // plumbing is currently missing to pass a pointer in from the pass |
| 129 | // Check for cmp (phi [x, preheader] ...), y where (pred x, y is known |
| 130 | auto *LHS = dyn_cast<PHINode>(Cond->getOperand(0)); |
| 131 | auto *RHS = Cond->getOperand(1); |
| 132 | if (!LHS || LHS->getParent() != CurLoop->getHeader()) |
| 133 | return false; |
| 134 | auto DL = ExitBlock->getModule()->getDataLayout(); |
| 135 | auto *IVStart = LHS->getIncomingValueForBlock(CurLoop->getLoopPreheader()); |
| 136 | auto *SimpleValOrNull = SimplifyCmpInst(Cond->getPredicate(), |
| 137 | IVStart, RHS, |
| 138 | {DL, /*TLI*/ nullptr, |
| 139 | DT, /*AC*/ nullptr, BI}); |
| 140 | auto *SimpleCst = dyn_cast_or_null<Constant>(SimpleValOrNull); |
| 141 | if (!SimpleCst) |
| 142 | return false; |
| 143 | if (ExitBlock == BI->getSuccessor(0)) |
| 144 | return SimpleCst->isZeroValue(); |
| 145 | assert(ExitBlock == BI->getSuccessor(1) && "implied by above"); |
| 146 | return SimpleCst->isAllOnesValue(); |
| 147 | } |
| 148 | |
Max Kazantsev | 4855b74 | 2018-11-06 09:07:03 +0000 | [diff] [blame] | 149 | /// Collect all blocks from \p CurLoop which lie on all possible paths from |
| 150 | /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set |
| 151 | /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty. |
| 152 | static void collectTransitivePredecessors( |
Max Kazantsev | bfbd4d1 | 2018-08-21 07:15:06 +0000 | [diff] [blame] | 153 | const Loop *CurLoop, const BasicBlock *BB, |
Max Kazantsev | 4855b74 | 2018-11-06 09:07:03 +0000 | [diff] [blame] | 154 | SmallPtrSetImpl<const BasicBlock *> &Predecessors) { |
Max Kazantsev | bfbd4d1 | 2018-08-21 07:15:06 +0000 | [diff] [blame] | 155 | assert(Predecessors.empty() && "Garbage in predecessors set?"); |
Max Kazantsev | 7b78d39 | 2018-08-17 06:19:17 +0000 | [diff] [blame] | 156 | assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); |
Max Kazantsev | 7b78d39 | 2018-08-17 06:19:17 +0000 | [diff] [blame] | 157 | if (BB == CurLoop->getHeader()) |
Max Kazantsev | bfbd4d1 | 2018-08-21 07:15:06 +0000 | [diff] [blame] | 158 | return; |
Max Kazantsev | 7b78d39 | 2018-08-17 06:19:17 +0000 | [diff] [blame] | 159 | SmallVector<const BasicBlock *, 4> WorkList; |
| 160 | for (auto *Pred : predecessors(BB)) { |
| 161 | Predecessors.insert(Pred); |
| 162 | WorkList.push_back(Pred); |
| 163 | } |
| 164 | while (!WorkList.empty()) { |
| 165 | auto *Pred = WorkList.pop_back_val(); |
| 166 | assert(CurLoop->contains(Pred) && "Should only reach loop blocks!"); |
| 167 | // We are not interested in backedges and we don't want to leave loop. |
| 168 | if (Pred == CurLoop->getHeader()) |
| 169 | continue; |
| 170 | // TODO: If BB lies in an inner loop of CurLoop, this will traverse over all |
| 171 | // blocks of this inner loop, even those that are always executed AFTER the |
| 172 | // BB. It may make our analysis more conservative than it could be, see test |
| 173 | // @nested and @nested_no_throw in test/Analysis/MustExecute/loop-header.ll. |
| 174 | // We can ignore backedge of all loops containing BB to get a sligtly more |
| 175 | // optimistic result. |
| 176 | for (auto *PredPred : predecessors(Pred)) |
| 177 | if (Predecessors.insert(PredPred).second) |
| 178 | WorkList.push_back(PredPred); |
| 179 | } |
Max Kazantsev | bfbd4d1 | 2018-08-21 07:15:06 +0000 | [diff] [blame] | 180 | } |
| 181 | |
| 182 | bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop, |
| 183 | const BasicBlock *BB, |
| 184 | const DominatorTree *DT) const { |
| 185 | assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); |
| 186 | |
| 187 | // Fast path: header is always reached once the loop is entered. |
| 188 | if (BB == CurLoop->getHeader()) |
| 189 | return true; |
| 190 | |
| 191 | // Collect all transitive predecessors of BB in the same loop. This set will |
| 192 | // be a subset of the blocks within the loop. |
| 193 | SmallPtrSet<const BasicBlock *, 4> Predecessors; |
| 194 | collectTransitivePredecessors(CurLoop, BB, Predecessors); |
Max Kazantsev | 7b78d39 | 2018-08-17 06:19:17 +0000 | [diff] [blame] | 195 | |
| 196 | // Make sure that all successors of all predecessors of BB are either: |
| 197 | // 1) BB, |
| 198 | // 2) Also predecessors of BB, |
| 199 | // 3) Exit blocks which are not taken on 1st iteration. |
| 200 | // Memoize blocks we've already checked. |
| 201 | SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors; |
Max Kazantsev | 6a4f5e2 | 2018-10-16 07:50:14 +0000 | [diff] [blame] | 202 | for (auto *Pred : Predecessors) { |
| 203 | // Predecessor block may throw, so it has a side exit. |
| 204 | if (blockMayThrow(Pred)) |
| 205 | return false; |
Max Kazantsev | 7b78d39 | 2018-08-17 06:19:17 +0000 | [diff] [blame] | 206 | for (auto *Succ : successors(Pred)) |
| 207 | if (CheckedSuccessors.insert(Succ).second && |
| 208 | Succ != BB && !Predecessors.count(Succ)) |
| 209 | // By discharging conditions that are not executed on the 1st iteration, |
| 210 | // we guarantee that *at least* on the first iteration all paths from |
| 211 | // header that *may* execute will lead us to the block of interest. So |
| 212 | // that if we had virtually peeled one iteration away, in this peeled |
| 213 | // iteration the set of predecessors would contain only paths from |
| 214 | // header to BB without any exiting edges that may execute. |
| 215 | // |
| 216 | // TODO: We only do it for exiting edges currently. We could use the |
| 217 | // same function to skip some of the edges within the loop if we know |
| 218 | // that they will not be taken on the 1st iteration. |
| 219 | // |
| 220 | // TODO: If we somehow know the number of iterations in loop, the same |
| 221 | // check may be done for any arbitrary N-th iteration as long as N is |
| 222 | // not greater than minimum number of iterations in this loop. |
| 223 | if (CurLoop->contains(Succ) || |
| 224 | !CanProveNotTakenFirstIteration(Succ, DT, CurLoop)) |
| 225 | return false; |
Max Kazantsev | 6a4f5e2 | 2018-10-16 07:50:14 +0000 | [diff] [blame] | 226 | } |
Max Kazantsev | 7b78d39 | 2018-08-17 06:19:17 +0000 | [diff] [blame] | 227 | |
| 228 | // All predecessors can only lead us to BB. |
| 229 | return true; |
| 230 | } |
| 231 | |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 232 | /// Returns true if the instruction in a loop is guaranteed to execute at least |
| 233 | /// once. |
Max Kazantsev | 9c90ec2 | 2018-10-16 08:31:05 +0000 | [diff] [blame] | 234 | bool SimpleLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst, |
| 235 | const DominatorTree *DT, |
| 236 | const Loop *CurLoop) const { |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 237 | // If the instruction is in the header block for the loop (which is very |
| 238 | // common), it is always guaranteed to dominate the exit blocks. Since this |
| 239 | // is a common case, and can save some work, check it now. |
| 240 | if (Inst.getParent() == CurLoop->getHeader()) |
| 241 | // If there's a throw in the header block, we can't guarantee we'll reach |
Philip Reames | e4ec473 | 2018-04-27 20:44:01 +0000 | [diff] [blame] | 242 | // Inst unless we can prove that Inst comes before the potential implicit |
| 243 | // exit. At the moment, we use a (cheap) hack for the common case where |
| 244 | // the instruction of interest is the first one in the block. |
Max Kazantsev | 87de55a | 2018-10-16 09:11:25 +0000 | [diff] [blame] | 245 | return !HeaderMayThrow || |
Max Kazantsev | c8466f9 | 2018-10-16 06:34:53 +0000 | [diff] [blame] | 246 | Inst.getParent()->getFirstNonPHIOrDbg() == &Inst; |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 247 | |
Max Kazantsev | 7b78d39 | 2018-08-17 06:19:17 +0000 | [diff] [blame] | 248 | // If there is a path from header to exit or latch that doesn't lead to our |
| 249 | // instruction's block, return false. |
Max Kazantsev | 87de55a | 2018-10-16 09:11:25 +0000 | [diff] [blame] | 250 | return allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT); |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 251 | } |
| 252 | |
Max Kazantsev | 5f9acd2 | 2018-10-16 09:58:09 +0000 | [diff] [blame] | 253 | bool ICFLoopSafetyInfo::isGuaranteedToExecute(const Instruction &Inst, |
| 254 | const DominatorTree *DT, |
| 255 | const Loop *CurLoop) const { |
| 256 | return !ICF.isDominatedByICFIFromSameBlock(&Inst) && |
| 257 | allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT); |
| 258 | } |
Philip Reames | 23aed5e | 2018-03-20 22:45:23 +0000 | [diff] [blame] | 259 | |
Max Kazantsev | 7d49a3a | 2018-11-12 09:29:58 +0000 | [diff] [blame] | 260 | bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const BasicBlock *BB, |
| 261 | const Loop *CurLoop) const { |
| 262 | assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); |
| 263 | |
| 264 | // Fast path: there are no instructions before header. |
| 265 | if (BB == CurLoop->getHeader()) |
| 266 | return true; |
| 267 | |
| 268 | // Collect all transitive predecessors of BB in the same loop. This set will |
| 269 | // be a subset of the blocks within the loop. |
| 270 | SmallPtrSet<const BasicBlock *, 4> Predecessors; |
| 271 | collectTransitivePredecessors(CurLoop, BB, Predecessors); |
| 272 | // Find if there any instruction in either predecessor that could write |
| 273 | // to memory. |
| 274 | for (auto *Pred : Predecessors) |
| 275 | if (MW.mayWriteToMemory(Pred)) |
| 276 | return false; |
| 277 | return true; |
| 278 | } |
| 279 | |
| 280 | bool ICFLoopSafetyInfo::doesNotWriteMemoryBefore(const Instruction &I, |
| 281 | const Loop *CurLoop) const { |
| 282 | auto *BB = I.getParent(); |
| 283 | assert(CurLoop->contains(BB) && "Should only be called for loop blocks!"); |
| 284 | return !MW.isDominatedByMemoryWriteFromSameBlock(&I) && |
| 285 | doesNotWriteMemoryBefore(BB, CurLoop); |
| 286 | } |
| 287 | |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 288 | namespace { |
| 289 | struct MustExecutePrinter : public FunctionPass { |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 290 | |
| 291 | static char ID; // Pass identification, replacement for typeid |
| 292 | MustExecutePrinter() : FunctionPass(ID) { |
| 293 | initializeMustExecutePrinterPass(*PassRegistry::getPassRegistry()); |
| 294 | } |
| 295 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
| 296 | AU.setPreservesAll(); |
| 297 | AU.addRequired<DominatorTreeWrapperPass>(); |
| 298 | AU.addRequired<LoopInfoWrapperPass>(); |
| 299 | } |
| 300 | bool runOnFunction(Function &F) override; |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 301 | }; |
| 302 | } |
| 303 | |
| 304 | char MustExecutePrinter::ID = 0; |
| 305 | INITIALIZE_PASS_BEGIN(MustExecutePrinter, "print-mustexecute", |
| 306 | "Instructions which execute on loop entry", false, true) |
| 307 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
| 308 | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) |
| 309 | INITIALIZE_PASS_END(MustExecutePrinter, "print-mustexecute", |
| 310 | "Instructions which execute on loop entry", false, true) |
| 311 | |
| 312 | FunctionPass *llvm::createMustExecutePrinter() { |
| 313 | return new MustExecutePrinter(); |
| 314 | } |
| 315 | |
Benjamin Kramer | 1fc0da4 | 2018-04-04 11:45:11 +0000 | [diff] [blame] | 316 | static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) { |
Philip Reames | 37a1a29 | 2018-03-20 23:00:54 +0000 | [diff] [blame] | 317 | // TODO: merge these two routines. For the moment, we display the best |
| 318 | // result obtained by *either* implementation. This is a bit unfair since no |
| 319 | // caller actually gets the full power at the moment. |
Max Kazantsev | 9c90ec2 | 2018-10-16 08:31:05 +0000 | [diff] [blame] | 320 | SimpleLoopSafetyInfo LSI; |
Max Kazantsev | 530b8d1 | 2018-08-15 05:55:43 +0000 | [diff] [blame] | 321 | LSI.computeLoopSafetyInfo(L); |
Max Kazantsev | c8466f9 | 2018-10-16 06:34:53 +0000 | [diff] [blame] | 322 | return LSI.isGuaranteedToExecute(I, DT, L) || |
Philip Reames | 37a1a29 | 2018-03-20 23:00:54 +0000 | [diff] [blame] | 323 | isGuaranteedToExecuteForEveryIteration(&I, L); |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 324 | } |
| 325 | |
Benjamin Kramer | 1fc0da4 | 2018-04-04 11:45:11 +0000 | [diff] [blame] | 326 | namespace { |
Adrian Prantl | 5f8f34e4 | 2018-05-01 15:54:18 +0000 | [diff] [blame] | 327 | /// An assembly annotator class to print must execute information in |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 328 | /// comments. |
| 329 | class MustExecuteAnnotatedWriter : public AssemblyAnnotationWriter { |
| 330 | DenseMap<const Value*, SmallVector<Loop*, 4> > MustExec; |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 331 | |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 332 | public: |
| 333 | MustExecuteAnnotatedWriter(const Function &F, |
| 334 | DominatorTree &DT, LoopInfo &LI) { |
| 335 | for (auto &I: instructions(F)) { |
| 336 | Loop *L = LI.getLoopFor(I.getParent()); |
| 337 | while (L) { |
| 338 | if (isMustExecuteIn(I, L, &DT)) { |
| 339 | MustExec[&I].push_back(L); |
| 340 | } |
| 341 | L = L->getParentLoop(); |
| 342 | }; |
| 343 | } |
| 344 | } |
| 345 | MustExecuteAnnotatedWriter(const Module &M, |
| 346 | DominatorTree &DT, LoopInfo &LI) { |
| 347 | for (auto &F : M) |
| 348 | for (auto &I: instructions(F)) { |
| 349 | Loop *L = LI.getLoopFor(I.getParent()); |
| 350 | while (L) { |
| 351 | if (isMustExecuteIn(I, L, &DT)) { |
| 352 | MustExec[&I].push_back(L); |
| 353 | } |
| 354 | L = L->getParentLoop(); |
| 355 | }; |
| 356 | } |
| 357 | } |
| 358 | |
| 359 | |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 360 | void printInfoComment(const Value &V, formatted_raw_ostream &OS) override { |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 361 | if (!MustExec.count(&V)) |
| 362 | return; |
| 363 | |
| 364 | const auto &Loops = MustExec.lookup(&V); |
| 365 | const auto NumLoops = Loops.size(); |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 366 | if (NumLoops > 1) |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 367 | OS << " ; (mustexec in " << NumLoops << " loops: "; |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 368 | else |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 369 | OS << " ; (mustexec in: "; |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 370 | |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 371 | bool first = true; |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 372 | for (const Loop *L : Loops) { |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 373 | if (!first) |
| 374 | OS << ", "; |
| 375 | first = false; |
| 376 | OS << L->getHeader()->getName(); |
| 377 | } |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 378 | OS << ")"; |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 379 | } |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 380 | }; |
Benjamin Kramer | 1fc0da4 | 2018-04-04 11:45:11 +0000 | [diff] [blame] | 381 | } // namespace |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 382 | |
| 383 | bool MustExecutePrinter::runOnFunction(Function &F) { |
| 384 | auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
| 385 | auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
| 386 | |
| 387 | MustExecuteAnnotatedWriter Writer(F, DT, LI); |
| 388 | F.print(dbgs(), &Writer); |
Fangrui Song | f78650a | 2018-07-30 19:41:25 +0000 | [diff] [blame] | 389 | |
Philip Reames | ce998ad | 2018-03-20 18:43:44 +0000 | [diff] [blame] | 390 | return false; |
Philip Reames | 89f2241 | 2018-03-20 17:09:21 +0000 | [diff] [blame] | 391 | } |