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 | |