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