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