ExecutionEngine/Orc/SpeculateAnalyses.h

0001 //===-- SpeculateAnalyses.h  --*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 /// \file
0009 /// Contains the Analyses and Result Interpretation to select likely functions
0010 /// to Speculatively compile before they are called. [Purely Experimentation]
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_EXECUTIONENGINE_ORC_SPECULATEANALYSES_H
0014 #define LLVM_EXECUTIONENGINE_ORC_SPECULATEANALYSES_H
0015
0016 #include "llvm/Analysis/BranchProbabilityInfo.h"
0017 #include "llvm/ExecutionEngine/Orc/Core.h"
0018 #include "llvm/ExecutionEngine/Orc/Speculation.h"
0019
0020 namespace llvm {
0021
0022 namespace orc {
0023
0024 // Provides common code.
0025 class SpeculateQuery {
0026 protected:
0027   void findCalles(const BasicBlock *, DenseSet<StringRef> &);
0028   bool isStraightLine(const Function &F);
0029
0030 public:
0031   using ResultTy = std::optional<DenseMap<StringRef, DenseSet<StringRef>>>;
0032 };
0033
0034 // Direct calls in high frequency basic blocks are extracted.
0035 class BlockFreqQuery : public SpeculateQuery {
0036   size_t numBBToGet(size_t);
0037
0038 public:
0039   // Find likely next executables based on IR Block Frequency
0040   ResultTy operator()(Function &F);
0041 };
0042
0043 // This Query generates a sequence of basic blocks which follows the order of
0044 // execution.
0045 // A handful of BB with higher block frequencies are taken, then path to entry
0046 // and end BB are discovered by traversing up & down the CFG.
0047 class SequenceBBQuery : public SpeculateQuery {
0048   struct WalkDirection {
0049     bool Upward = true, Downward = true;
0050     // the block associated contain a call
0051     bool CallerBlock = false;
0052   };
0053
0054 public:
0055   using VisitedBlocksInfoTy = DenseMap<const BasicBlock *, WalkDirection>;
0056   using BlockListTy = SmallVector<const BasicBlock *, 8>;
0057   using BackEdgesInfoTy =
0058       SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 8>;
0059   using BlockFreqInfoTy =
0060       SmallVector<std::pair<const BasicBlock *, uint64_t>, 8>;
0061
0062 private:
0063   std::size_t getHottestBlocks(std::size_t TotalBlocks);
0064   BlockListTy rearrangeBB(const Function &, const BlockListTy &);
0065   BlockListTy queryCFG(Function &, const BlockListTy &);
0066   void traverseToEntryBlock(const BasicBlock *, const BlockListTy &,
0067                             const BackEdgesInfoTy &,
0068                             const BranchProbabilityInfo *,
0069                             VisitedBlocksInfoTy &);
0070   void traverseToExitBlock(const BasicBlock *, const BlockListTy &,
0071                            const BackEdgesInfoTy &,
0072                            const BranchProbabilityInfo *,
0073                            VisitedBlocksInfoTy &);
0074
0075 public:
0076   ResultTy operator()(Function &F);
0077 };
0078
0079 } // namespace orc
0080 } // namespace llvm
0081
0082 #endif // LLVM_EXECUTIONENGINE_ORC_SPECULATEANALYSES_H