1 //===-- SpeculateAnalyses.h --*- 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 /// \file 9 /// Contains the Analyses and Result Interpretation to select likely functions 10 /// to Speculatively compile before they are called. [Purely Experimentation] 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_EXECUTIONENGINE_ORC_SPECULATEANALYSES_H 14 #define LLVM_EXECUTIONENGINE_ORC_SPECULATEANALYSES_H 15 16 #include "llvm/Analysis/BranchProbabilityInfo.h" 17 #include "llvm/ExecutionEngine/Orc/Core.h" 18 #include "llvm/ExecutionEngine/Orc/Speculation.h" 19 20 namespace llvm { 21 22 namespace orc { 23 24 // Provides common code. 25 class SpeculateQuery { 26 protected: 27 void findCalles(const BasicBlock *, DenseSet<StringRef> &); 28 bool isStraightLine(const Function &F); 29 30 public: 31 using ResultTy = std::optional<DenseMap<StringRef, DenseSet<StringRef>>>; 32 }; 33 34 // Direct calls in high frequency basic blocks are extracted. 35 class BlockFreqQuery : public SpeculateQuery { 36 size_t numBBToGet(size_t); 37 38 public: 39 // Find likely next executables based on IR Block Frequency 40 ResultTy operator()(Function &F); 41 }; 42 43 // This Query generates a sequence of basic blocks which follows the order of 44 // execution. 45 // A handful of BB with higher block frequencies are taken, then path to entry 46 // and end BB are discovered by traversing up & down the CFG. 47 class SequenceBBQuery : public SpeculateQuery { 48 struct WalkDirection { 49 bool Upward = true, Downward = true; 50 // the block associated contain a call 51 bool CallerBlock = false; 52 }; 53 54 public: 55 using VisitedBlocksInfoTy = DenseMap<const BasicBlock *, WalkDirection>; 56 using BlockListTy = SmallVector<const BasicBlock *, 8>; 57 using BackEdgesInfoTy = 58 SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 8>; 59 using BlockFreqInfoTy = 60 SmallVector<std::pair<const BasicBlock *, uint64_t>, 8>; 61 62 private: 63 std::size_t getHottestBlocks(std::size_t TotalBlocks); 64 BlockListTy rearrangeBB(const Function &, const BlockListTy &); 65 BlockListTy queryCFG(Function &, const BlockListTy &); 66 void traverseToEntryBlock(const BasicBlock *, const BlockListTy &, 67 const BackEdgesInfoTy &, 68 const BranchProbabilityInfo *, 69 VisitedBlocksInfoTy &); 70 void traverseToExitBlock(const BasicBlock *, const BlockListTy &, 71 const BackEdgesInfoTy &, 72 const BranchProbabilityInfo *, 73 VisitedBlocksInfoTy &); 74 75 public: 76 ResultTy operator()(Function &F); 77 }; 78 79 } // namespace orc 80 } // namespace llvm 81 82 #endif // LLVM_EXECUTIONENGINE_ORC_SPECULATEANALYSES_H 83