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