include/llvm/ExecutionEngine/Orc/SpeculateAnalyses.h

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