1 //===-- SpeculateAnalyses.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 #include "llvm/ExecutionEngine/Orc/SpeculateAnalyses.h" 10 #include "llvm/ADT/ArrayRef.h" 11 #include "llvm/ADT/DenseMap.h" 12 #include "llvm/ADT/STLExtras.h" 13 #include "llvm/ADT/SmallVector.h" 14 #include "llvm/Analysis/BlockFrequencyInfo.h" 15 #include "llvm/Analysis/BranchProbabilityInfo.h" 16 #include "llvm/Analysis/CFG.h" 17 #include "llvm/IR/PassManager.h" 18 #include "llvm/Passes/PassBuilder.h" 19 #include "llvm/Support/ErrorHandling.h" 20 21 namespace { 22 using namespace llvm; 23 SmallVector<const BasicBlock *, 8> findBBwithCalls(const Function &F, 24 bool IndirectCall = false) { 25 SmallVector<const BasicBlock *, 8> BBs; 26 27 auto findCallInst = [&IndirectCall](const Instruction &I) { 28 if (auto Call = dyn_cast<CallBase>(&I)) 29 return Call->isIndirectCall() ? IndirectCall : true; 30 else 31 return false; 32 }; 33 for (auto &BB : F) 34 if (findCallInst(*BB.getTerminator()) || 35 llvm::any_of(BB.instructionsWithoutDebug(), findCallInst)) 36 BBs.emplace_back(&BB); 37 38 return BBs; 39 } 40 } // namespace 41 42 // Implementations of Queries shouldn't need to lock the resources 43 // such as LLVMContext, each argument (function) has a non-shared LLVMContext 44 // Plus, if Queries contain states necessary locking scheme should be provided. 45 namespace llvm { 46 namespace orc { 47 48 // Collect direct calls only 49 void SpeculateQuery::findCalles(const BasicBlock *BB, 50 DenseSet<StringRef> &CallesNames) { 51 assert(BB != nullptr && "Traversing Null BB to find calls?"); 52 53 auto getCalledFunction = [&CallesNames](const CallBase *Call) { 54 auto CalledValue = Call->getCalledOperand()->stripPointerCasts(); 55 if (auto DirectCall = dyn_cast<Function>(CalledValue)) 56 CallesNames.insert(DirectCall->getName()); 57 }; 58 for (auto &I : BB->instructionsWithoutDebug()) 59 if (auto CI = dyn_cast<CallInst>(&I)) 60 getCalledFunction(CI); 61 62 if (auto II = dyn_cast<InvokeInst>(BB->getTerminator())) 63 getCalledFunction(II); 64 } 65 66 bool SpeculateQuery::isStraightLine(const Function &F) { 67 return llvm::all_of(F, [](const BasicBlock &BB) { 68 return BB.getSingleSuccessor() != nullptr; 69 }); 70 } 71 72 // BlockFreqQuery Implementations 73 74 size_t BlockFreqQuery::numBBToGet(size_t numBB) { 75 // small CFG 76 if (numBB < 4) 77 return numBB; 78 // mid-size CFG 79 else if (numBB < 20) 80 return (numBB / 2); 81 else 82 return (numBB / 2) + (numBB / 4); 83 } 84 85 BlockFreqQuery::ResultTy BlockFreqQuery::operator()(Function &F) { 86 DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles; 87 DenseSet<StringRef> Calles; 88 SmallVector<std::pair<const BasicBlock *, uint64_t>, 8> BBFreqs; 89 90 PassBuilder PB; 91 FunctionAnalysisManager FAM; 92 PB.registerFunctionAnalyses(FAM); 93 94 auto IBBs = findBBwithCalls(F); 95 96 if (IBBs.empty()) 97 return std::nullopt; 98 99 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F); 100 101 for (const auto I : IBBs) 102 BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()}); 103 104 assert(IBBs.size() == BBFreqs.size() && "BB Count Mismatch"); 105 106 llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference BBF, 107 decltype(BBFreqs)::const_reference BBS) { 108 return BBF.second > BBS.second ? true : false; 109 }); 110 111 // ignoring number of direct calls in a BB 112 auto Topk = numBBToGet(BBFreqs.size()); 113 114 for (size_t i = 0; i < Topk; i++) 115 findCalles(BBFreqs[i].first, Calles); 116 117 assert(!Calles.empty() && "Running Analysis on Function with no calls?"); 118 119 CallerAndCalles.insert({F.getName(), std::move(Calles)}); 120 121 return CallerAndCalles; 122 } 123 124 // SequenceBBQuery Implementation 125 std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) { 126 if (TotalBlocks == 1) 127 return TotalBlocks; 128 return TotalBlocks / 2; 129 } 130 131 // FIXME : find good implementation. 132 SequenceBBQuery::BlockListTy 133 SequenceBBQuery::rearrangeBB(const Function &F, const BlockListTy &BBList) { 134 BlockListTy RearrangedBBSet; 135 136 for (auto &Block : F) 137 if (llvm::is_contained(BBList, &Block)) 138 RearrangedBBSet.push_back(&Block); 139 140 assert(RearrangedBBSet.size() == BBList.size() && 141 "BasicBlock missing while rearranging?"); 142 return RearrangedBBSet; 143 } 144 145 void SequenceBBQuery::traverseToEntryBlock(const BasicBlock *AtBB, 146 const BlockListTy &CallerBlocks, 147 const BackEdgesInfoTy &BackEdgesInfo, 148 const BranchProbabilityInfo *BPI, 149 VisitedBlocksInfoTy &VisitedBlocks) { 150 auto Itr = VisitedBlocks.find(AtBB); 151 if (Itr != VisitedBlocks.end()) { // already visited. 152 if (!Itr->second.Upward) 153 return; 154 Itr->second.Upward = false; 155 } else { 156 // Create hint for newly discoverd blocks. 157 WalkDirection BlockHint; 158 BlockHint.Upward = false; 159 // FIXME: Expensive Check 160 if (llvm::is_contained(CallerBlocks, AtBB)) 161 BlockHint.CallerBlock = true; 162 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint)); 163 } 164 165 const_pred_iterator PIt = pred_begin(AtBB), EIt = pred_end(AtBB); 166 // Move this check to top, when we have code setup to launch speculative 167 // compiles for function in entry BB, this triggers the speculative compiles 168 // before running the program. 169 if (PIt == EIt) // No Preds. 170 return; 171 172 DenseSet<const BasicBlock *> PredSkipNodes; 173 174 // Since we are checking for predecessor's backedges, this Block 175 // occurs in second position. 176 for (auto &I : BackEdgesInfo) 177 if (I.second == AtBB) 178 PredSkipNodes.insert(I.first); 179 180 // Skip predecessors which source of back-edges. 181 for (; PIt != EIt; ++PIt) 182 // checking EdgeHotness is cheaper 183 if (BPI->isEdgeHot(*PIt, AtBB) && !PredSkipNodes.count(*PIt)) 184 traverseToEntryBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI, 185 VisitedBlocks); 186 } 187 188 void SequenceBBQuery::traverseToExitBlock(const BasicBlock *AtBB, 189 const BlockListTy &CallerBlocks, 190 const BackEdgesInfoTy &BackEdgesInfo, 191 const BranchProbabilityInfo *BPI, 192 VisitedBlocksInfoTy &VisitedBlocks) { 193 auto Itr = VisitedBlocks.find(AtBB); 194 if (Itr != VisitedBlocks.end()) { // already visited. 195 if (!Itr->second.Downward) 196 return; 197 Itr->second.Downward = false; 198 } else { 199 // Create hint for newly discoverd blocks. 200 WalkDirection BlockHint; 201 BlockHint.Downward = false; 202 // FIXME: Expensive Check 203 if (llvm::is_contained(CallerBlocks, AtBB)) 204 BlockHint.CallerBlock = true; 205 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint)); 206 } 207 208 const_succ_iterator PIt = succ_begin(AtBB), EIt = succ_end(AtBB); 209 if (PIt == EIt) // No succs. 210 return; 211 212 // If there are hot edges, then compute SuccSkipNodes. 213 DenseSet<const BasicBlock *> SuccSkipNodes; 214 215 // Since we are checking for successor's backedges, this Block 216 // occurs in first position. 217 for (auto &I : BackEdgesInfo) 218 if (I.first == AtBB) 219 SuccSkipNodes.insert(I.second); 220 221 for (; PIt != EIt; ++PIt) 222 if (BPI->isEdgeHot(AtBB, *PIt) && !SuccSkipNodes.count(*PIt)) 223 traverseToExitBlock(*PIt, CallerBlocks, BackEdgesInfo, BPI, 224 VisitedBlocks); 225 } 226 227 // Get Block frequencies for blocks and take most frequently executed block, 228 // walk towards the entry block from those blocks and discover the basic blocks 229 // with call. 230 SequenceBBQuery::BlockListTy 231 SequenceBBQuery::queryCFG(Function &F, const BlockListTy &CallerBlocks) { 232 233 BlockFreqInfoTy BBFreqs; 234 VisitedBlocksInfoTy VisitedBlocks; 235 BackEdgesInfoTy BackEdgesInfo; 236 237 PassBuilder PB; 238 FunctionAnalysisManager FAM; 239 PB.registerFunctionAnalyses(FAM); 240 241 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F); 242 243 llvm::FindFunctionBackedges(F, BackEdgesInfo); 244 245 for (const auto I : CallerBlocks) 246 BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()}); 247 248 llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference Bbf, 249 decltype(BBFreqs)::const_reference Bbs) { 250 return Bbf.second > Bbs.second; 251 }); 252 253 ArrayRef<std::pair<const BasicBlock *, uint64_t>> HotBlocksRef(BBFreqs); 254 HotBlocksRef = 255 HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size())); 256 257 BranchProbabilityInfo *BPI = 258 FAM.getCachedResult<BranchProbabilityAnalysis>(F); 259 260 // visit NHotBlocks, 261 // traverse upwards to entry 262 // traverse downwards to end. 263 264 for (auto I : HotBlocksRef) { 265 traverseToEntryBlock(I.first, CallerBlocks, BackEdgesInfo, BPI, 266 VisitedBlocks); 267 traverseToExitBlock(I.first, CallerBlocks, BackEdgesInfo, BPI, 268 VisitedBlocks); 269 } 270 271 BlockListTy MinCallerBlocks; 272 for (auto &I : VisitedBlocks) 273 if (I.second.CallerBlock) 274 MinCallerBlocks.push_back(std::move(I.first)); 275 276 return rearrangeBB(F, MinCallerBlocks); 277 } 278 279 SpeculateQuery::ResultTy SequenceBBQuery::operator()(Function &F) { 280 // reduce the number of lists! 281 DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles; 282 DenseSet<StringRef> Calles; 283 BlockListTy SequencedBlocks; 284 BlockListTy CallerBlocks; 285 286 CallerBlocks = findBBwithCalls(F); 287 if (CallerBlocks.empty()) 288 return std::nullopt; 289 290 if (isStraightLine(F)) 291 SequencedBlocks = rearrangeBB(F, CallerBlocks); 292 else 293 SequencedBlocks = queryCFG(F, CallerBlocks); 294 295 for (const auto *BB : SequencedBlocks) 296 findCalles(BB, Calles); 297 298 CallerAndCalles.insert({F.getName(), std::move(Calles)}); 299 return CallerAndCalles; 300 } 301 302 } // namespace orc 303 } // namespace llvm 304