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
20namespace llvm {
21
22namespace orc {
23
24// Provides common code.
25class SpeculateQuery {
26protected:
27 void findCalles(const BasicBlock *, DenseSet<StringRef> &);
28 bool isStraightLine(const Function &F);
29
30public:
31 using ResultTy = std::optional<DenseMap<StringRef, DenseSet<StringRef>>>;
32};
33
34// Direct calls in high frequency basic blocks are extracted.
35class BlockFreqQuery : public SpeculateQuery {
36 size_t numBBToGet(size_t);
37
38public:
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.
47class 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
54public:
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
62private:
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
75public:
76 ResultTy operator()(Function &F);
77};
78
79} // namespace orc
80} // namespace llvm
81
82#endif // LLVM_EXECUTIONENGINE_ORC_SPECULATEANALYSES_H
83

source code of llvm/include/llvm/ExecutionEngine/Orc/SpeculateAnalyses.h