| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 1 | //===- HotColdSplitting.cpp -- Outline Cold Regions -------------*- C++ -*-===// | 
|  | 2 | // | 
|  | 3 | //                     The LLVM Compiler Infrastructure | 
|  | 4 | // | 
|  | 5 | // This file is distributed under the University of Illinois Open Source | 
|  | 6 | // License. See LICENSE.TXT for details. | 
|  | 7 | // | 
|  | 8 | //===----------------------------------------------------------------------===// | 
|  | 9 | // | 
|  | 10 | // Outline cold regions to a separate function. | 
|  | 11 | // TODO: Update BFI and BPI | 
|  | 12 | // TODO: Add all the outlined functions to a separate section. | 
|  | 13 | // | 
|  | 14 | //===----------------------------------------------------------------------===// | 
|  | 15 |  | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 16 | #include "llvm/ADT/PostOrderIterator.h" | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 17 | #include "llvm/ADT/SmallVector.h" | 
|  | 18 | #include "llvm/ADT/Statistic.h" | 
|  | 19 | #include "llvm/Analysis/AliasAnalysis.h" | 
|  | 20 | #include "llvm/Analysis/BlockFrequencyInfo.h" | 
|  | 21 | #include "llvm/Analysis/BranchProbabilityInfo.h" | 
|  | 22 | #include "llvm/Analysis/CFG.h" | 
|  | 23 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" | 
|  | 24 | #include "llvm/Analysis/PostDominators.h" | 
|  | 25 | #include "llvm/Analysis/ProfileSummaryInfo.h" | 
| Sebastian Pop | a1f20fc | 2018-09-10 15:08:02 +0000 | [diff] [blame] | 26 | #include "llvm/Analysis/TargetTransformInfo.h" | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 27 | #include "llvm/IR/BasicBlock.h" | 
|  | 28 | #include "llvm/IR/CFG.h" | 
| Vedant Kumar | 03f9f15 | 2018-12-07 20:24:04 +0000 | [diff] [blame] | 29 | #include "llvm/IR/CallSite.h" | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 30 | #include "llvm/IR/DataLayout.h" | 
|  | 31 | #include "llvm/IR/DiagnosticInfo.h" | 
|  | 32 | #include "llvm/IR/Dominators.h" | 
|  | 33 | #include "llvm/IR/Function.h" | 
|  | 34 | #include "llvm/IR/Instruction.h" | 
|  | 35 | #include "llvm/IR/Instructions.h" | 
| Vedant Kumar | dd4be53 | 2018-10-29 19:15:39 +0000 | [diff] [blame] | 36 | #include "llvm/IR/IntrinsicInst.h" | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 37 | #include "llvm/IR/Metadata.h" | 
|  | 38 | #include "llvm/IR/Module.h" | 
|  | 39 | #include "llvm/IR/PassManager.h" | 
|  | 40 | #include "llvm/IR/Type.h" | 
|  | 41 | #include "llvm/IR/Use.h" | 
|  | 42 | #include "llvm/IR/User.h" | 
|  | 43 | #include "llvm/IR/Value.h" | 
|  | 44 | #include "llvm/Pass.h" | 
|  | 45 | #include "llvm/Support/BlockFrequency.h" | 
|  | 46 | #include "llvm/Support/BranchProbability.h" | 
|  | 47 | #include "llvm/Support/Debug.h" | 
|  | 48 | #include "llvm/Support/raw_ostream.h" | 
|  | 49 | #include "llvm/Transforms/IPO.h" | 
| Aditya Kumar | 9e20ade | 2018-10-03 05:55:20 +0000 | [diff] [blame] | 50 | #include "llvm/Transforms/IPO/HotColdSplitting.h" | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 51 | #include "llvm/Transforms/Scalar.h" | 
|  | 52 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | 
|  | 53 | #include "llvm/Transforms/Utils/Cloning.h" | 
|  | 54 | #include "llvm/Transforms/Utils/CodeExtractor.h" | 
|  | 55 | #include "llvm/Transforms/Utils/Local.h" | 
|  | 56 | #include "llvm/Transforms/Utils/SSAUpdater.h" | 
|  | 57 | #include "llvm/Transforms/Utils/ValueMapper.h" | 
|  | 58 | #include <algorithm> | 
|  | 59 | #include <cassert> | 
|  | 60 |  | 
|  | 61 | #define DEBUG_TYPE "hotcoldsplit" | 
|  | 62 |  | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 63 | STATISTIC(NumColdRegionsFound, "Number of cold regions found."); | 
|  | 64 | STATISTIC(NumColdRegionsOutlined, "Number of cold regions outlined."); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 65 |  | 
|  | 66 | using namespace llvm; | 
|  | 67 |  | 
|  | 68 | static cl::opt<bool> EnableStaticAnalyis("hot-cold-static-analysis", | 
|  | 69 | cl::init(true), cl::Hidden); | 
|  | 70 |  | 
| Vedant Kumar | d2a895a | 2018-11-04 23:11:57 +0000 | [diff] [blame] | 71 | static cl::opt<int> | 
|  | 72 | MinOutliningThreshold("min-outlining-thresh", cl::init(3), cl::Hidden, | 
|  | 73 | cl::desc("Code size threshold for outlining within a " | 
|  | 74 | "single BB (as a multiple of TCC_Basic)")); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 75 |  | 
|  | 76 | namespace { | 
|  | 77 |  | 
|  | 78 | struct PostDomTree : PostDomTreeBase<BasicBlock> { | 
|  | 79 | PostDomTree(Function &F) { recalculate(F); } | 
|  | 80 | }; | 
|  | 81 |  | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 82 | /// A sequence of basic blocks. | 
|  | 83 | /// | 
|  | 84 | /// A 0-sized SmallVector is slightly cheaper to move than a std::vector. | 
|  | 85 | using BlockSequence = SmallVector<BasicBlock *, 0>; | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 86 |  | 
| Sebastian Pop | 542e522 | 2018-10-15 21:43:11 +0000 | [diff] [blame] | 87 | // Same as blockEndsInUnreachable in CodeGen/BranchFolding.cpp. Do not modify | 
|  | 88 | // this function unless you modify the MBB version as well. | 
|  | 89 | // | 
|  | 90 | /// A no successor, non-return block probably ends in unreachable and is cold. | 
|  | 91 | /// Also consider a block that ends in an indirect branch to be a return block, | 
|  | 92 | /// since many targets use plain indirect branches to return. | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 93 | bool blockEndsInUnreachable(const BasicBlock &BB) { | 
| Sebastian Pop | 542e522 | 2018-10-15 21:43:11 +0000 | [diff] [blame] | 94 | if (!succ_empty(&BB)) | 
|  | 95 | return false; | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 96 | if (BB.empty()) | 
|  | 97 | return true; | 
| Chandler Carruth | edb12a8 | 2018-10-15 10:04:59 +0000 | [diff] [blame] | 98 | const Instruction *I = BB.getTerminator(); | 
| Sebastian Pop | 542e522 | 2018-10-15 21:43:11 +0000 | [diff] [blame] | 99 | return !(isa<ReturnInst>(I) || isa<IndirectBrInst>(I)); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 100 | } | 
|  | 101 |  | 
| Vedant Kumar | 03f9f15 | 2018-12-07 20:24:04 +0000 | [diff] [blame] | 102 | bool unlikelyExecuted(BasicBlock &BB) { | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 103 | // Exception handling blocks are unlikely executed. | 
|  | 104 | if (BB.isEHPad()) | 
|  | 105 | return true; | 
| Vedant Kumar | 03f9f15 | 2018-12-07 20:24:04 +0000 | [diff] [blame] | 106 |  | 
|  | 107 | // The block is cold if it calls/invokes a cold function. | 
|  | 108 | for (Instruction &I : BB) | 
|  | 109 | if (auto CS = CallSite(&I)) | 
|  | 110 | if (CS.hasFnAttr(Attribute::Cold)) | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 111 | return true; | 
|  | 112 |  | 
| Vedant Kumar | 03f9f15 | 2018-12-07 20:24:04 +0000 | [diff] [blame] | 113 | // The block is cold if it has an unreachable terminator, unless it's | 
|  | 114 | // preceded by a call to a (possibly warm) noreturn call (e.g. longjmp). | 
|  | 115 | if (blockEndsInUnreachable(BB)) { | 
|  | 116 | if (auto *CI = | 
|  | 117 | dyn_cast_or_null<CallInst>(BB.getTerminator()->getPrevNode())) | 
|  | 118 | if (CI->hasFnAttr(Attribute::NoReturn)) | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 119 | return false; | 
| Vedant Kumar | 03f9f15 | 2018-12-07 20:24:04 +0000 | [diff] [blame] | 120 | return true; | 
|  | 121 | } | 
|  | 122 |  | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 123 | return false; | 
|  | 124 | } | 
|  | 125 |  | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 126 | /// Check whether it's safe to outline \p BB. | 
|  | 127 | static bool mayExtractBlock(const BasicBlock &BB) { | 
| Vedant Kumar | b3a7cae | 2018-12-11 18:05:31 +0000 | [diff] [blame] | 128 | return !BB.hasAddressTaken() && !BB.isEHPad(); | 
| Sebastian Pop | 542e522 | 2018-10-15 21:43:11 +0000 | [diff] [blame] | 129 | } | 
|  | 130 |  | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 131 | /// Check whether \p Region is profitable to outline. | 
|  | 132 | static bool isProfitableToOutline(const BlockSequence &Region, | 
| Vedant Kumar | d2a895a | 2018-11-04 23:11:57 +0000 | [diff] [blame] | 133 | TargetTransformInfo &TTI) { | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 134 | if (Region.size() > 1) | 
|  | 135 | return true; | 
|  | 136 |  | 
| Vedant Kumar | d2a895a | 2018-11-04 23:11:57 +0000 | [diff] [blame] | 137 | int Cost = 0; | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 138 | const BasicBlock &BB = *Region[0]; | 
| Vedant Kumar | dd4be53 | 2018-10-29 19:15:39 +0000 | [diff] [blame] | 139 | for (const Instruction &I : BB) { | 
|  | 140 | if (isa<DbgInfoIntrinsic>(&I) || &I == BB.getTerminator()) | 
|  | 141 | continue; | 
| Vedant Kumar | d2a895a | 2018-11-04 23:11:57 +0000 | [diff] [blame] | 142 |  | 
|  | 143 | Cost += TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize); | 
|  | 144 |  | 
|  | 145 | if (Cost >= (MinOutliningThreshold * TargetTransformInfo::TCC_Basic)) | 
| Vedant Kumar | dd4be53 | 2018-10-29 19:15:39 +0000 | [diff] [blame] | 146 | return true; | 
|  | 147 | } | 
|  | 148 | return false; | 
|  | 149 | } | 
|  | 150 |  | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 151 | /// Mark \p F cold. Return true if it's changed. | 
|  | 152 | static bool markEntireFunctionCold(Function &F) { | 
|  | 153 | assert(!F.hasFnAttribute(Attribute::OptimizeNone) && "Can't mark this cold"); | 
|  | 154 | bool Changed = false; | 
|  | 155 | if (!F.hasFnAttribute(Attribute::MinSize)) { | 
|  | 156 | F.addFnAttr(Attribute::MinSize); | 
|  | 157 | Changed = true; | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 158 | } | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 159 | // TODO: Move this function into a cold section. | 
|  | 160 | return Changed; | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 161 | } | 
|  | 162 |  | 
|  | 163 | class HotColdSplitting { | 
|  | 164 | public: | 
|  | 165 | HotColdSplitting(ProfileSummaryInfo *ProfSI, | 
|  | 166 | function_ref<BlockFrequencyInfo *(Function &)> GBFI, | 
| Sebastian Pop | a1f20fc | 2018-09-10 15:08:02 +0000 | [diff] [blame] | 167 | function_ref<TargetTransformInfo &(Function &)> GTTI, | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 168 | std::function<OptimizationRemarkEmitter &(Function &)> *GORE) | 
| Sebastian Pop | a1f20fc | 2018-09-10 15:08:02 +0000 | [diff] [blame] | 169 | : PSI(ProfSI), GetBFI(GBFI), GetTTI(GTTI), GetORE(GORE) {} | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 170 | bool run(Module &M); | 
|  | 171 |  | 
|  | 172 | private: | 
|  | 173 | bool shouldOutlineFrom(const Function &F) const; | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 174 | bool outlineColdRegions(Function &F, ProfileSummaryInfo &PSI, | 
|  | 175 | BlockFrequencyInfo *BFI, TargetTransformInfo &TTI, | 
|  | 176 | DominatorTree &DT, PostDomTree &PDT, | 
|  | 177 | OptimizationRemarkEmitter &ORE); | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 178 | Function *extractColdRegion(const BlockSequence &Region, DominatorTree &DT, | 
| Vedant Kumar | d2a895a | 2018-11-04 23:11:57 +0000 | [diff] [blame] | 179 | BlockFrequencyInfo *BFI, TargetTransformInfo &TTI, | 
| Teresa Johnson | c8dba68 | 2018-10-24 18:53:47 +0000 | [diff] [blame] | 180 | OptimizationRemarkEmitter &ORE, unsigned Count); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 181 | SmallPtrSet<const Function *, 2> OutlinedFunctions; | 
|  | 182 | ProfileSummaryInfo *PSI; | 
|  | 183 | function_ref<BlockFrequencyInfo *(Function &)> GetBFI; | 
| Sebastian Pop | a1f20fc | 2018-09-10 15:08:02 +0000 | [diff] [blame] | 184 | function_ref<TargetTransformInfo &(Function &)> GetTTI; | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 185 | std::function<OptimizationRemarkEmitter &(Function &)> *GetORE; | 
|  | 186 | }; | 
|  | 187 |  | 
|  | 188 | class HotColdSplittingLegacyPass : public ModulePass { | 
|  | 189 | public: | 
|  | 190 | static char ID; | 
|  | 191 | HotColdSplittingLegacyPass() : ModulePass(ID) { | 
|  | 192 | initializeHotColdSplittingLegacyPassPass(*PassRegistry::getPassRegistry()); | 
|  | 193 | } | 
|  | 194 |  | 
|  | 195 | void getAnalysisUsage(AnalysisUsage &AU) const override { | 
|  | 196 | AU.addRequired<AssumptionCacheTracker>(); | 
|  | 197 | AU.addRequired<BlockFrequencyInfoWrapperPass>(); | 
|  | 198 | AU.addRequired<ProfileSummaryInfoWrapperPass>(); | 
| Sebastian Pop | a1f20fc | 2018-09-10 15:08:02 +0000 | [diff] [blame] | 199 | AU.addRequired<TargetTransformInfoWrapperPass>(); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 200 | } | 
|  | 201 |  | 
|  | 202 | bool runOnModule(Module &M) override; | 
|  | 203 | }; | 
|  | 204 |  | 
|  | 205 | } // end anonymous namespace | 
|  | 206 |  | 
|  | 207 | // Returns false if the function should not be considered for hot-cold split | 
| Sebastian Pop | 0f30f08 | 2018-09-14 20:36:19 +0000 | [diff] [blame] | 208 | // optimization. | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 209 | bool HotColdSplitting::shouldOutlineFrom(const Function &F) const { | 
| Sebastian Pop | 0f30f08 | 2018-09-14 20:36:19 +0000 | [diff] [blame] | 210 | // Do not try to outline again from an already outlined cold function. | 
|  | 211 | if (OutlinedFunctions.count(&F)) | 
|  | 212 | return false; | 
|  | 213 |  | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 214 | if (F.size() <= 2) | 
|  | 215 | return false; | 
|  | 216 |  | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 217 | // TODO: Consider only skipping functions marked `optnone` or `cold`. | 
|  | 218 |  | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 219 | if (F.hasAddressTaken()) | 
|  | 220 | return false; | 
|  | 221 |  | 
|  | 222 | if (F.hasFnAttribute(Attribute::AlwaysInline)) | 
|  | 223 | return false; | 
|  | 224 |  | 
|  | 225 | if (F.hasFnAttribute(Attribute::NoInline)) | 
|  | 226 | return false; | 
|  | 227 |  | 
|  | 228 | if (F.getCallingConv() == CallingConv::Cold) | 
|  | 229 | return false; | 
|  | 230 |  | 
|  | 231 | if (PSI->isFunctionEntryCold(&F)) | 
|  | 232 | return false; | 
|  | 233 | return true; | 
|  | 234 | } | 
|  | 235 |  | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 236 | Function *HotColdSplitting::extractColdRegion(const BlockSequence &Region, | 
|  | 237 | DominatorTree &DT, | 
|  | 238 | BlockFrequencyInfo *BFI, | 
| Vedant Kumar | d2a895a | 2018-11-04 23:11:57 +0000 | [diff] [blame] | 239 | TargetTransformInfo &TTI, | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 240 | OptimizationRemarkEmitter &ORE, | 
|  | 241 | unsigned Count) { | 
| Teresa Johnson | f431a2f | 2018-10-22 19:06:42 +0000 | [diff] [blame] | 242 | assert(!Region.empty()); | 
| Sebastian Pop | 1217160 | 2018-09-14 20:36:10 +0000 | [diff] [blame] | 243 |  | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 244 | // TODO: Pass BFI and BPI to update profile information. | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 245 | CodeExtractor CE(Region, &DT, /* AggregateArgs */ false, /* BFI */ nullptr, | 
| Teresa Johnson | c8dba68 | 2018-10-24 18:53:47 +0000 | [diff] [blame] | 246 | /* BPI */ nullptr, /* AllowVarArgs */ false, | 
|  | 247 | /* AllowAlloca */ false, | 
|  | 248 | /* Suffix */ "cold." + std::to_string(Count)); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 249 |  | 
|  | 250 | SetVector<Value *> Inputs, Outputs, Sinks; | 
|  | 251 | CE.findInputsOutputs(Inputs, Outputs, Sinks); | 
|  | 252 |  | 
|  | 253 | // Do not extract regions that have live exit variables. | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 254 | if (Outputs.size() > 0) { | 
|  | 255 | LLVM_DEBUG(llvm::dbgs() << "Not outlining; live outputs\n"); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 256 | return nullptr; | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 257 | } | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 258 |  | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 259 | // TODO: Run MergeBasicBlockIntoOnlyPred on the outlined function. | 
| Teresa Johnson | f431a2f | 2018-10-22 19:06:42 +0000 | [diff] [blame] | 260 | Function *OrigF = Region[0]->getParent(); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 261 | if (Function *OutF = CE.extractCodeRegion()) { | 
|  | 262 | User *U = *OutF->user_begin(); | 
|  | 263 | CallInst *CI = cast<CallInst>(U); | 
|  | 264 | CallSite CS(CI); | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 265 | NumColdRegionsOutlined++; | 
| Vedant Kumar | d2a895a | 2018-11-04 23:11:57 +0000 | [diff] [blame] | 266 | if (TTI.useColdCCForColdCall(*OutF)) { | 
| Sebastian Pop | a1f20fc | 2018-09-10 15:08:02 +0000 | [diff] [blame] | 267 | OutF->setCallingConv(CallingConv::Cold); | 
|  | 268 | CS.setCallingConv(CallingConv::Cold); | 
|  | 269 | } | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 270 | CI->setIsNoInline(); | 
| Vedant Kumar | 5031546 | 2018-10-23 19:41:12 +0000 | [diff] [blame] | 271 |  | 
|  | 272 | // Try to make the outlined code as small as possible on the assumption | 
|  | 273 | // that it's cold. | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 274 | markEntireFunctionCold(*OutF); | 
| Vedant Kumar | 5031546 | 2018-10-23 19:41:12 +0000 | [diff] [blame] | 275 |  | 
| Sebastian Pop | 0f30f08 | 2018-09-14 20:36:19 +0000 | [diff] [blame] | 276 | LLVM_DEBUG(llvm::dbgs() << "Outlined Region: " << *OutF); | 
| Teresa Johnson | f431a2f | 2018-10-22 19:06:42 +0000 | [diff] [blame] | 277 | ORE.emit([&]() { | 
|  | 278 | return OptimizationRemark(DEBUG_TYPE, "HotColdSplit", | 
|  | 279 | &*Region[0]->begin()) | 
|  | 280 | << ore::NV("Original", OrigF) << " split cold code into " | 
|  | 281 | << ore::NV("Split", OutF); | 
|  | 282 | }); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 283 | return OutF; | 
|  | 284 | } | 
|  | 285 |  | 
|  | 286 | ORE.emit([&]() { | 
|  | 287 | return OptimizationRemarkMissed(DEBUG_TYPE, "ExtractFailed", | 
|  | 288 | &*Region[0]->begin()) | 
|  | 289 | << "Failed to extract region at block " | 
|  | 290 | << ore::NV("Block", Region.front()); | 
|  | 291 | }); | 
|  | 292 | return nullptr; | 
|  | 293 | } | 
|  | 294 |  | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 295 | /// A pair of (basic block, score). | 
|  | 296 | using BlockTy = std::pair<BasicBlock *, unsigned>; | 
|  | 297 |  | 
|  | 298 | /// A maximal outlining region. This contains all blocks post-dominated by a | 
|  | 299 | /// sink block, the sink block itself, and all blocks dominated by the sink. | 
|  | 300 | class OutliningRegion { | 
|  | 301 | /// A list of (block, score) pairs. A block's score is non-zero iff it's a | 
|  | 302 | /// viable sub-region entry point. Blocks with higher scores are better entry | 
|  | 303 | /// points (i.e. they are more distant ancestors of the sink block). | 
|  | 304 | SmallVector<BlockTy, 0> Blocks = {}; | 
|  | 305 |  | 
|  | 306 | /// The suggested entry point into the region. If the region has multiple | 
|  | 307 | /// entry points, all blocks within the region may not be reachable from this | 
|  | 308 | /// entry point. | 
|  | 309 | BasicBlock *SuggestedEntryPoint = nullptr; | 
|  | 310 |  | 
|  | 311 | /// Whether the entire function is cold. | 
|  | 312 | bool EntireFunctionCold = false; | 
|  | 313 |  | 
|  | 314 | /// Whether or not \p BB could be the entry point of an extracted region. | 
|  | 315 | static bool isViableEntryPoint(BasicBlock &BB) { return !BB.isEHPad(); } | 
|  | 316 |  | 
|  | 317 | /// If \p BB is a viable entry point, return \p Score. Return 0 otherwise. | 
|  | 318 | static unsigned getEntryPointScore(BasicBlock &BB, unsigned Score) { | 
|  | 319 | return isViableEntryPoint(BB) ? Score : 0; | 
|  | 320 | } | 
|  | 321 |  | 
|  | 322 | /// These scores should be lower than the score for predecessor blocks, | 
|  | 323 | /// because regions starting at predecessor blocks are typically larger. | 
|  | 324 | static constexpr unsigned ScoreForSuccBlock = 1; | 
|  | 325 | static constexpr unsigned ScoreForSinkBlock = 1; | 
|  | 326 |  | 
|  | 327 | OutliningRegion(const OutliningRegion &) = delete; | 
|  | 328 | OutliningRegion &operator=(const OutliningRegion &) = delete; | 
|  | 329 |  | 
|  | 330 | public: | 
|  | 331 | OutliningRegion() = default; | 
|  | 332 | OutliningRegion(OutliningRegion &&) = default; | 
|  | 333 | OutliningRegion &operator=(OutliningRegion &&) = default; | 
|  | 334 |  | 
|  | 335 | static OutliningRegion create(BasicBlock &SinkBB, const DominatorTree &DT, | 
|  | 336 | const PostDomTree &PDT) { | 
|  | 337 | OutliningRegion ColdRegion; | 
|  | 338 |  | 
|  | 339 | SmallPtrSet<BasicBlock *, 4> RegionBlocks; | 
|  | 340 |  | 
|  | 341 | auto addBlockToRegion = [&](BasicBlock *BB, unsigned Score) { | 
|  | 342 | RegionBlocks.insert(BB); | 
|  | 343 | ColdRegion.Blocks.emplace_back(BB, Score); | 
|  | 344 | assert(RegionBlocks.size() == ColdRegion.Blocks.size() && "Duplicate BB"); | 
|  | 345 | }; | 
|  | 346 |  | 
|  | 347 | // The ancestor farthest-away from SinkBB, and also post-dominated by it. | 
|  | 348 | unsigned SinkScore = getEntryPointScore(SinkBB, ScoreForSinkBlock); | 
|  | 349 | ColdRegion.SuggestedEntryPoint = (SinkScore > 0) ? &SinkBB : nullptr; | 
|  | 350 | unsigned BestScore = SinkScore; | 
|  | 351 |  | 
|  | 352 | // Visit SinkBB's ancestors using inverse DFS. | 
|  | 353 | auto PredIt = ++idf_begin(&SinkBB); | 
|  | 354 | auto PredEnd = idf_end(&SinkBB); | 
|  | 355 | while (PredIt != PredEnd) { | 
|  | 356 | BasicBlock &PredBB = **PredIt; | 
|  | 357 | bool SinkPostDom = PDT.dominates(&SinkBB, &PredBB); | 
|  | 358 |  | 
|  | 359 | // If the predecessor is cold and has no predecessors, the entire | 
|  | 360 | // function must be cold. | 
|  | 361 | if (SinkPostDom && pred_empty(&PredBB)) { | 
|  | 362 | ColdRegion.EntireFunctionCold = true; | 
|  | 363 | return ColdRegion; | 
|  | 364 | } | 
|  | 365 |  | 
|  | 366 | // If SinkBB does not post-dominate a predecessor, do not mark the | 
|  | 367 | // predecessor (or any of its predecessors) cold. | 
|  | 368 | if (!SinkPostDom || !mayExtractBlock(PredBB)) { | 
|  | 369 | PredIt.skipChildren(); | 
|  | 370 | continue; | 
|  | 371 | } | 
|  | 372 |  | 
|  | 373 | // Keep track of the post-dominated ancestor farthest away from the sink. | 
|  | 374 | // The path length is always >= 2, ensuring that predecessor blocks are | 
|  | 375 | // considered as entry points before the sink block. | 
|  | 376 | unsigned PredScore = getEntryPointScore(PredBB, PredIt.getPathLength()); | 
|  | 377 | if (PredScore > BestScore) { | 
|  | 378 | ColdRegion.SuggestedEntryPoint = &PredBB; | 
|  | 379 | BestScore = PredScore; | 
|  | 380 | } | 
|  | 381 |  | 
|  | 382 | addBlockToRegion(&PredBB, PredScore); | 
|  | 383 | ++PredIt; | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 384 | } | 
|  | 385 |  | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 386 | // Add SinkBB to the cold region. It's considered as an entry point before | 
|  | 387 | // any sink-successor blocks. | 
|  | 388 | addBlockToRegion(&SinkBB, SinkScore); | 
|  | 389 |  | 
|  | 390 | // Find all successors of SinkBB dominated by SinkBB using DFS. | 
|  | 391 | auto SuccIt = ++df_begin(&SinkBB); | 
|  | 392 | auto SuccEnd = df_end(&SinkBB); | 
|  | 393 | while (SuccIt != SuccEnd) { | 
|  | 394 | BasicBlock &SuccBB = **SuccIt; | 
|  | 395 | bool SinkDom = DT.dominates(&SinkBB, &SuccBB); | 
|  | 396 |  | 
|  | 397 | // Don't allow the backwards & forwards DFSes to mark the same block. | 
|  | 398 | bool DuplicateBlock = RegionBlocks.count(&SuccBB); | 
|  | 399 |  | 
|  | 400 | // If SinkBB does not dominate a successor, do not mark the successor (or | 
|  | 401 | // any of its successors) cold. | 
|  | 402 | if (DuplicateBlock || !SinkDom || !mayExtractBlock(SuccBB)) { | 
|  | 403 | SuccIt.skipChildren(); | 
|  | 404 | continue; | 
|  | 405 | } | 
|  | 406 |  | 
|  | 407 | unsigned SuccScore = getEntryPointScore(SuccBB, ScoreForSuccBlock); | 
|  | 408 | if (SuccScore > BestScore) { | 
|  | 409 | ColdRegion.SuggestedEntryPoint = &SuccBB; | 
|  | 410 | BestScore = SuccScore; | 
|  | 411 | } | 
|  | 412 |  | 
|  | 413 | addBlockToRegion(&SuccBB, SuccScore); | 
|  | 414 | ++SuccIt; | 
|  | 415 | } | 
|  | 416 |  | 
|  | 417 | return ColdRegion; | 
|  | 418 | } | 
|  | 419 |  | 
|  | 420 | /// Whether this region has nothing to extract. | 
|  | 421 | bool empty() const { return !SuggestedEntryPoint; } | 
|  | 422 |  | 
|  | 423 | /// The blocks in this region. | 
|  | 424 | ArrayRef<std::pair<BasicBlock *, unsigned>> blocks() const { return Blocks; } | 
|  | 425 |  | 
|  | 426 | /// Whether the entire function containing this region is cold. | 
|  | 427 | bool isEntireFunctionCold() const { return EntireFunctionCold; } | 
|  | 428 |  | 
|  | 429 | /// Remove a sub-region from this region and return it as a block sequence. | 
|  | 430 | BlockSequence takeSingleEntrySubRegion(DominatorTree &DT) { | 
|  | 431 | assert(!empty() && !isEntireFunctionCold() && "Nothing to extract"); | 
|  | 432 |  | 
|  | 433 | // Remove blocks dominated by the suggested entry point from this region. | 
|  | 434 | // During the removal, identify the next best entry point into the region. | 
|  | 435 | // Ensure that the first extracted block is the suggested entry point. | 
|  | 436 | BlockSequence SubRegion = {SuggestedEntryPoint}; | 
|  | 437 | BasicBlock *NextEntryPoint = nullptr; | 
|  | 438 | unsigned NextScore = 0; | 
|  | 439 | auto RegionEndIt = Blocks.end(); | 
|  | 440 | auto RegionStartIt = remove_if(Blocks, [&](const BlockTy &Block) { | 
|  | 441 | BasicBlock *BB = Block.first; | 
|  | 442 | unsigned Score = Block.second; | 
|  | 443 | bool InSubRegion = | 
|  | 444 | BB == SuggestedEntryPoint || DT.dominates(SuggestedEntryPoint, BB); | 
|  | 445 | if (!InSubRegion && Score > NextScore) { | 
|  | 446 | NextEntryPoint = BB; | 
|  | 447 | NextScore = Score; | 
|  | 448 | } | 
|  | 449 | if (InSubRegion && BB != SuggestedEntryPoint) | 
|  | 450 | SubRegion.push_back(BB); | 
|  | 451 | return InSubRegion; | 
|  | 452 | }); | 
|  | 453 | Blocks.erase(RegionStartIt, RegionEndIt); | 
|  | 454 |  | 
|  | 455 | // Update the suggested entry point. | 
|  | 456 | SuggestedEntryPoint = NextEntryPoint; | 
|  | 457 |  | 
|  | 458 | return SubRegion; | 
|  | 459 | } | 
|  | 460 | }; | 
|  | 461 |  | 
|  | 462 | bool HotColdSplitting::outlineColdRegions(Function &F, ProfileSummaryInfo &PSI, | 
|  | 463 | BlockFrequencyInfo *BFI, | 
|  | 464 | TargetTransformInfo &TTI, | 
|  | 465 | DominatorTree &DT, PostDomTree &PDT, | 
|  | 466 | OptimizationRemarkEmitter &ORE) { | 
|  | 467 | bool Changed = false; | 
|  | 468 |  | 
|  | 469 | // The set of cold blocks. | 
|  | 470 | SmallPtrSet<BasicBlock *, 4> ColdBlocks; | 
|  | 471 |  | 
|  | 472 | // The worklist of non-intersecting regions left to outline. | 
|  | 473 | SmallVector<OutliningRegion, 2> OutliningWorklist; | 
|  | 474 |  | 
|  | 475 | // Set up an RPO traversal. Experimentally, this performs better (outlines | 
|  | 476 | // more) than a PO traversal, because we prevent region overlap by keeping | 
|  | 477 | // the first region to contain a block. | 
|  | 478 | ReversePostOrderTraversal<Function *> RPOT(&F); | 
|  | 479 |  | 
|  | 480 | // Find all cold regions. | 
|  | 481 | for (BasicBlock *BB : RPOT) { | 
|  | 482 | // Skip blocks which can't be outlined. | 
|  | 483 | if (!mayExtractBlock(*BB)) | 
|  | 484 | continue; | 
|  | 485 |  | 
|  | 486 | // This block is already part of some outlining region. | 
|  | 487 | if (ColdBlocks.count(BB)) | 
|  | 488 | continue; | 
|  | 489 |  | 
|  | 490 | bool Cold = PSI.isColdBlock(BB, BFI) || | 
|  | 491 | (EnableStaticAnalyis && unlikelyExecuted(*BB)); | 
|  | 492 | if (!Cold) | 
|  | 493 | continue; | 
|  | 494 |  | 
|  | 495 | LLVM_DEBUG({ | 
|  | 496 | dbgs() << "Found a cold block:\n"; | 
|  | 497 | BB->dump(); | 
|  | 498 | }); | 
|  | 499 |  | 
|  | 500 | auto Region = OutliningRegion::create(*BB, DT, PDT); | 
|  | 501 | if (Region.empty()) | 
|  | 502 | continue; | 
|  | 503 |  | 
|  | 504 | if (Region.isEntireFunctionCold()) { | 
|  | 505 | LLVM_DEBUG(dbgs() << "Entire function is cold\n"); | 
|  | 506 | return markEntireFunctionCold(F); | 
|  | 507 | } | 
|  | 508 |  | 
|  | 509 | // If this outlining region intersects with another, drop the new region. | 
|  | 510 | // | 
|  | 511 | // TODO: It's theoretically possible to outline more by only keeping the | 
|  | 512 | // largest region which contains a block, but the extra bookkeeping to do | 
|  | 513 | // this is tricky/expensive. | 
|  | 514 | bool RegionsOverlap = any_of(Region.blocks(), [&](const BlockTy &Block) { | 
|  | 515 | return !ColdBlocks.insert(Block.first).second; | 
|  | 516 | }); | 
|  | 517 | if (RegionsOverlap) | 
|  | 518 | continue; | 
|  | 519 |  | 
|  | 520 | OutliningWorklist.emplace_back(std::move(Region)); | 
|  | 521 | ++NumColdRegionsFound; | 
|  | 522 | } | 
|  | 523 |  | 
|  | 524 | // Outline single-entry cold regions, splitting up larger regions as needed. | 
|  | 525 | unsigned OutlinedFunctionID = 1; | 
|  | 526 | while (!OutliningWorklist.empty()) { | 
|  | 527 | OutliningRegion Region = OutliningWorklist.pop_back_val(); | 
|  | 528 | assert(!Region.empty() && "Empty outlining region in worklist"); | 
|  | 529 | do { | 
|  | 530 | BlockSequence SubRegion = Region.takeSingleEntrySubRegion(DT); | 
|  | 531 | if (!isProfitableToOutline(SubRegion, TTI)) { | 
|  | 532 | LLVM_DEBUG({ | 
|  | 533 | dbgs() << "Skipping outlining; not profitable to outline\n"; | 
|  | 534 | SubRegion[0]->dump(); | 
|  | 535 | }); | 
|  | 536 | continue; | 
|  | 537 | } | 
|  | 538 |  | 
|  | 539 | LLVM_DEBUG({ | 
|  | 540 | dbgs() << "Hot/cold splitting attempting to outline these blocks:\n"; | 
|  | 541 | for (BasicBlock *BB : SubRegion) | 
|  | 542 | BB->dump(); | 
|  | 543 | }); | 
|  | 544 |  | 
|  | 545 | Function *Outlined = | 
|  | 546 | extractColdRegion(SubRegion, DT, BFI, TTI, ORE, OutlinedFunctionID); | 
|  | 547 | if (Outlined) { | 
|  | 548 | ++OutlinedFunctionID; | 
|  | 549 | OutlinedFunctions.insert(Outlined); | 
|  | 550 | Changed = true; | 
|  | 551 | } | 
|  | 552 | } while (!Region.empty()); | 
|  | 553 | } | 
|  | 554 |  | 
|  | 555 | return Changed; | 
|  | 556 | } | 
|  | 557 |  | 
|  | 558 | bool HotColdSplitting::run(Module &M) { | 
|  | 559 | bool Changed = false; | 
|  | 560 | OutlinedFunctions.clear(); | 
|  | 561 | for (auto &F : M) { | 
|  | 562 | if (!shouldOutlineFrom(F)) { | 
|  | 563 | LLVM_DEBUG(llvm::dbgs() << "Skipping " << F.getName() << "\n"); | 
|  | 564 | continue; | 
|  | 565 | } | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 566 | LLVM_DEBUG(llvm::dbgs() << "Outlining in " << F.getName() << "\n"); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 567 | DominatorTree DT(F); | 
|  | 568 | PostDomTree PDT(F); | 
|  | 569 | PDT.recalculate(F); | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 570 | BlockFrequencyInfo *BFI = GetBFI(F); | 
| Vedant Kumar | d2a895a | 2018-11-04 23:11:57 +0000 | [diff] [blame] | 571 | TargetTransformInfo &TTI = GetTTI(F); | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 572 | OptimizationRemarkEmitter &ORE = (*GetORE)(F); | 
| Vedant Kumar | 03aaa3e | 2018-12-07 20:23:52 +0000 | [diff] [blame] | 573 | Changed |= outlineColdRegions(F, *PSI, BFI, TTI, DT, PDT, ORE); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 574 | } | 
| Vedant Kumar | c299006 | 2018-10-24 22:15:41 +0000 | [diff] [blame] | 575 | return Changed; | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 576 | } | 
|  | 577 |  | 
|  | 578 | bool HotColdSplittingLegacyPass::runOnModule(Module &M) { | 
|  | 579 | if (skipModule(M)) | 
|  | 580 | return false; | 
|  | 581 | ProfileSummaryInfo *PSI = | 
| Vedant Kumar | e7b789b | 2018-11-19 05:23:16 +0000 | [diff] [blame] | 582 | &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); | 
| Sebastian Pop | a1f20fc | 2018-09-10 15:08:02 +0000 | [diff] [blame] | 583 | auto GTTI = [this](Function &F) -> TargetTransformInfo & { | 
|  | 584 | return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); | 
|  | 585 | }; | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 586 | auto GBFI = [this](Function &F) { | 
|  | 587 | return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI(); | 
|  | 588 | }; | 
|  | 589 | std::unique_ptr<OptimizationRemarkEmitter> ORE; | 
|  | 590 | std::function<OptimizationRemarkEmitter &(Function &)> GetORE = | 
|  | 591 | [&ORE](Function &F) -> OptimizationRemarkEmitter & { | 
|  | 592 | ORE.reset(new OptimizationRemarkEmitter(&F)); | 
|  | 593 | return *ORE.get(); | 
|  | 594 | }; | 
|  | 595 |  | 
| Sebastian Pop | a1f20fc | 2018-09-10 15:08:02 +0000 | [diff] [blame] | 596 | return HotColdSplitting(PSI, GBFI, GTTI, &GetORE).run(M); | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 597 | } | 
|  | 598 |  | 
| Aditya Kumar | 9e20ade | 2018-10-03 05:55:20 +0000 | [diff] [blame] | 599 | PreservedAnalyses | 
|  | 600 | HotColdSplittingPass::run(Module &M, ModuleAnalysisManager &AM) { | 
|  | 601 | auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); | 
|  | 602 |  | 
|  | 603 | std::function<AssumptionCache &(Function &)> GetAssumptionCache = | 
|  | 604 | [&FAM](Function &F) -> AssumptionCache & { | 
|  | 605 | return FAM.getResult<AssumptionAnalysis>(F); | 
|  | 606 | }; | 
|  | 607 |  | 
|  | 608 | auto GBFI = [&FAM](Function &F) { | 
|  | 609 | return &FAM.getResult<BlockFrequencyAnalysis>(F); | 
|  | 610 | }; | 
|  | 611 |  | 
|  | 612 | std::function<TargetTransformInfo &(Function &)> GTTI = | 
|  | 613 | [&FAM](Function &F) -> TargetTransformInfo & { | 
|  | 614 | return FAM.getResult<TargetIRAnalysis>(F); | 
|  | 615 | }; | 
|  | 616 |  | 
|  | 617 | std::unique_ptr<OptimizationRemarkEmitter> ORE; | 
|  | 618 | std::function<OptimizationRemarkEmitter &(Function &)> GetORE = | 
|  | 619 | [&ORE](Function &F) -> OptimizationRemarkEmitter & { | 
|  | 620 | ORE.reset(new OptimizationRemarkEmitter(&F)); | 
|  | 621 | return *ORE.get(); | 
|  | 622 | }; | 
|  | 623 |  | 
|  | 624 | ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M); | 
|  | 625 |  | 
|  | 626 | if (HotColdSplitting(PSI, GBFI, GTTI, &GetORE).run(M)) | 
|  | 627 | return PreservedAnalyses::none(); | 
|  | 628 | return PreservedAnalyses::all(); | 
|  | 629 | } | 
|  | 630 |  | 
| Aditya Kumar | 801394a | 2018-09-07 15:03:49 +0000 | [diff] [blame] | 631 | char HotColdSplittingLegacyPass::ID = 0; | 
|  | 632 | INITIALIZE_PASS_BEGIN(HotColdSplittingLegacyPass, "hotcoldsplit", | 
|  | 633 | "Hot Cold Splitting", false, false) | 
|  | 634 | INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) | 
|  | 635 | INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) | 
|  | 636 | INITIALIZE_PASS_END(HotColdSplittingLegacyPass, "hotcoldsplit", | 
|  | 637 | "Hot Cold Splitting", false, false) | 
|  | 638 |  | 
|  | 639 | ModulePass *llvm::createHotColdSplittingPass() { | 
|  | 640 | return new HotColdSplittingLegacyPass(); | 
|  | 641 | } |