From 15a56d4ec1e3944d16d60b01009c2dd7cda5157b Mon Sep 17 00:00:00 2001 From: Eugene Zelenko Date: Fri, 21 Jul 2017 21:37:46 +0000 Subject: [PATCH] [Analysis] Fix some Clang-tidy modernize and Include What You Use warnings; other minor fixes (NFC). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@308787 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/BlockFrequencyInfo.h | 27 ++- .../llvm/Analysis/BlockFrequencyInfoImpl.h | 221 +++++++++++------- include/llvm/Analysis/BranchProbabilityInfo.h | 40 ++-- include/llvm/Analysis/DemandedBits.h | 33 +-- include/llvm/Analysis/Trace.h | 29 +-- lib/Analysis/BlockFrequencyInfo.cpp | 36 +-- lib/Analysis/BlockFrequencyInfoImpl.cpp | 46 ++-- lib/Analysis/BranchProbabilityInfo.cpp | 19 +- lib/Analysis/DemandedBits.cpp | 19 +- lib/Analysis/Trace.cpp | 5 +- 10 files changed, 299 insertions(+), 176 deletions(-) diff --git a/include/llvm/Analysis/BlockFrequencyInfo.h b/include/llvm/Analysis/BlockFrequencyInfo.h index cbae01c9102..4162734fd54 100644 --- a/include/llvm/Analysis/BlockFrequencyInfo.h +++ b/include/llvm/Analysis/BlockFrequencyInfo.h @@ -18,31 +18,34 @@ #include "llvm/IR/PassManager.h" #include "llvm/Pass.h" #include "llvm/Support/BlockFrequency.h" -#include +#include +#include namespace llvm { +class BasicBlock; class BranchProbabilityInfo; +class Function; class LoopInfo; +class Module; +class raw_ostream; template class BlockFrequencyInfoImpl; /// BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to /// estimate IR basic block frequencies. class BlockFrequencyInfo { - typedef BlockFrequencyInfoImpl ImplType; - std::unique_ptr BFI; + using ImplType = BlockFrequencyInfoImpl; - void operator=(const BlockFrequencyInfo &) = delete; - BlockFrequencyInfo(const BlockFrequencyInfo &) = delete; + std::unique_ptr BFI; public: BlockFrequencyInfo(); BlockFrequencyInfo(const Function &F, const BranchProbabilityInfo &BPI, const LoopInfo &LI); + BlockFrequencyInfo(const BlockFrequencyInfo &) = delete; + BlockFrequencyInfo &operator=(const BlockFrequencyInfo &) = delete; BlockFrequencyInfo(BlockFrequencyInfo &&Arg); - BlockFrequencyInfo &operator=(BlockFrequencyInfo &&RHS); - ~BlockFrequencyInfo(); /// Handle invalidation explicitly. @@ -100,11 +103,12 @@ public: class BlockFrequencyAnalysis : public AnalysisInfoMixin { friend AnalysisInfoMixin; + static AnalysisKey Key; public: - /// \brief Provide the result typedef for this analysis pass. - typedef BlockFrequencyInfo Result; + /// \brief Provide the result type for this analysis pass. + using Result = BlockFrequencyInfo; /// \brief Run the analysis pass over a function and produce BFI. Result run(Function &F, FunctionAnalysisManager &AM); @@ -117,6 +121,7 @@ class BlockFrequencyPrinterPass public: explicit BlockFrequencyPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; @@ -140,6 +145,6 @@ public: void print(raw_ostream &OS, const Module *M) const override; }; -} +} // end namespace llvm -#endif +#endif // LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h index 5de3821242e..a5f3e82876f 100644 --- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h +++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h @@ -1,4 +1,4 @@ -//==- BlockFrequencyInfoImpl.h - Block Frequency Implementation -*- C++ -*-===// +//==- BlockFrequencyInfoImpl.h - Block Frequency Implementation --*- C++ -*-==// // // The LLVM Compiler Infrastructure // @@ -19,25 +19,34 @@ #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Twine.h" #include "llvm/ADT/iterator_range.h" #include "llvm/IR/BasicBlock.h" #include "llvm/Support/BlockFrequency.h" #include "llvm/Support/BranchProbability.h" #include "llvm/Support/DOTGraphTraits.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/Format.h" #include "llvm/Support/ScaledNumber.h" #include "llvm/Support/raw_ostream.h" +#include +#include +#include +#include #include +#include +#include #include #include +#include #include #define DEBUG_TYPE "block-freq" namespace llvm { -class BasicBlock; class BranchProbabilityInfo; class Function; class Loop; @@ -58,7 +67,8 @@ template struct BlockEdgesAdder; /// \brief Mass of a block. /// /// This class implements a sort of fixed-point fraction always between 0.0 and -/// 1.0. getMass() == UINT64_MAX indicates a value of 1.0. +/// 1.0. getMass() == std::numeric_limits::max() indicates a value of +/// 1.0. /// /// Masses can be added and subtracted. Simple saturation arithmetic is used, /// so arithmetic operations never overflow or underflow. @@ -69,18 +79,21 @@ template struct BlockEdgesAdder; /// /// Masses can be scaled by \a BranchProbability at maximum precision. class BlockMass { - uint64_t Mass; + uint64_t Mass = 0; public: - BlockMass() : Mass(0) {} + BlockMass() = default; explicit BlockMass(uint64_t Mass) : Mass(Mass) {} static BlockMass getEmpty() { return BlockMass(); } - static BlockMass getFull() { return BlockMass(UINT64_MAX); } + + static BlockMass getFull() { + return BlockMass(std::numeric_limits::max()); + } uint64_t getMass() const { return Mass; } - bool isFull() const { return Mass == UINT64_MAX; } + bool isFull() const { return Mass == std::numeric_limits::max(); } bool isEmpty() const { return !Mass; } bool operator!() const { return isEmpty(); } @@ -90,7 +103,7 @@ public: /// Adds another mass, saturating at \a isFull() rather than overflowing. BlockMass &operator+=(BlockMass X) { uint64_t Sum = Mass + X.Mass; - Mass = Sum < Mass ? UINT64_MAX : Sum; + Mass = Sum < Mass ? std::numeric_limits::max() : Sum; return *this; } @@ -159,8 +172,8 @@ template <> struct isPodLike { /// BlockFrequencyInfoImpl. See there for details. class BlockFrequencyInfoImplBase { public: - typedef ScaledNumber Scaled64; - typedef bfi_detail::BlockMass BlockMass; + using Scaled64 = ScaledNumber; + using BlockMass = bfi_detail::BlockMass; /// \brief Representative of a block. /// @@ -170,8 +183,12 @@ public: /// Unlike a block pointer, its order has meaning (location in the /// topological sort) and it's class is the same regardless of block type. struct BlockNode { - typedef uint32_t IndexType; - IndexType Index; + using IndexType = uint32_t; + + IndexType Index = std::numeric_limits::max(); + + BlockNode() = default; + BlockNode(IndexType Index) : Index(Index) {} bool operator==(const BlockNode &X) const { return Index == X.Index; } bool operator!=(const BlockNode &X) const { return Index != X.Index; } @@ -180,11 +197,11 @@ public: bool operator<(const BlockNode &X) const { return Index < X.Index; } bool operator>(const BlockNode &X) const { return Index > X.Index; } - BlockNode() : Index(UINT32_MAX) {} - BlockNode(IndexType Index) : Index(Index) {} - bool isValid() const { return Index <= getMaxIndex(); } - static size_t getMaxIndex() { return UINT32_MAX - 1; } + + static size_t getMaxIndex() { + return std::numeric_limits::max() - 1; + } }; /// \brief Stats about a block itself. @@ -198,12 +215,13 @@ public: /// Contains the data necessary to represent a loop as a pseudo-node once it's /// packaged. struct LoopData { - typedef SmallVector, 4> ExitMap; - typedef SmallVector NodeList; - typedef SmallVector HeaderMassList; + using ExitMap = SmallVector, 4>; + using NodeList = SmallVector; + using HeaderMassList = SmallVector; + LoopData *Parent; ///< The parent loop. - bool IsPackaged; ///< Whether this has been packaged. - uint32_t NumHeaders; ///< Number of headers. + bool IsPackaged = false; ///< Whether this has been packaged. + uint32_t NumHeaders = 1; ///< Number of headers. ExitMap Exits; ///< Successor edges (and weights). NodeList Nodes; ///< Header and the members of the loop. HeaderMassList BackedgeMass; ///< Mass returned to each loop header. @@ -211,22 +229,24 @@ public: Scaled64 Scale; LoopData(LoopData *Parent, const BlockNode &Header) - : Parent(Parent), IsPackaged(false), NumHeaders(1), Nodes(1, Header), - BackedgeMass(1) {} + : Parent(Parent), Nodes(1, Header), BackedgeMass(1) {} + template LoopData(LoopData *Parent, It1 FirstHeader, It1 LastHeader, It2 FirstOther, It2 LastOther) - : Parent(Parent), IsPackaged(false), Nodes(FirstHeader, LastHeader) { + : Parent(Parent), Nodes(FirstHeader, LastHeader) { NumHeaders = Nodes.size(); Nodes.insert(Nodes.end(), FirstOther, LastOther); BackedgeMass.resize(NumHeaders); } + bool isHeader(const BlockNode &Node) const { if (isIrreducible()) return std::binary_search(Nodes.begin(), Nodes.begin() + NumHeaders, Node); return Node == Nodes[0]; } + BlockNode getHeader() const { return Nodes[0]; } bool isIrreducible() const { return NumHeaders > 1; } @@ -241,6 +261,7 @@ public: NodeList::const_iterator members_begin() const { return Nodes.begin() + NumHeaders; } + NodeList::const_iterator members_end() const { return Nodes.end(); } iterator_range members() const { return make_range(members_begin(), members_end()); @@ -249,13 +270,14 @@ public: /// \brief Index of loop information. struct WorkingData { - BlockNode Node; ///< This node. - LoopData *Loop; ///< The loop this block is inside. - BlockMass Mass; ///< Mass distribution from the entry block. + BlockNode Node; ///< This node. + LoopData *Loop = nullptr; ///< The loop this block is inside. + BlockMass Mass; ///< Mass distribution from the entry block. - WorkingData(const BlockNode &Node) : Node(Node), Loop(nullptr) {} + WorkingData(const BlockNode &Node) : Node(Node) {} bool isLoopHeader() const { return Loop && Loop->isHeader(Node); } + bool isDoubleLoopHeader() const { return isLoopHeader() && Loop->Parent && Loop->Parent->isIrreducible() && Loop->Parent->isHeader(Node); @@ -286,6 +308,7 @@ public: auto L = getPackagedLoop(); return L ? L->getHeader() : Node; } + LoopData *getPackagedLoop() const { if (!Loop || !Loop->IsPackaged) return nullptr; @@ -310,8 +333,10 @@ public: /// \brief Has ContainingLoop been packaged up? bool isPackaged() const { return getResolvedNode() != Node; } + /// \brief Has Loop been packaged up? bool isAPackage() const { return isLoopHeader() && Loop->IsPackaged; } + /// \brief Has Loop been packaged up twice? bool isADoublePackage() const { return isDoubleLoopHeader() && Loop->Parent->IsPackaged; @@ -333,10 +358,11 @@ public: /// backedge to the loop header? struct Weight { enum DistType { Local, Exit, Backedge }; - DistType Type; + DistType Type = Local; BlockNode TargetNode; - uint64_t Amount; - Weight() : Type(Local), Amount(0) {} + uint64_t Amount = 0; + + Weight() = default; Weight(DistType Type, BlockNode TargetNode, uint64_t Amount) : Type(Type), TargetNode(TargetNode), Amount(Amount) {} }; @@ -350,18 +376,22 @@ public: /// \a DidOverflow indicates whether \a Total did overflow while adding to /// the distribution. It should never overflow twice. struct Distribution { - typedef SmallVector WeightList; - WeightList Weights; ///< Individual successor weights. - uint64_t Total; ///< Sum of all weights. - bool DidOverflow; ///< Whether \a Total did overflow. + using WeightList = SmallVector; + + WeightList Weights; ///< Individual successor weights. + uint64_t Total = 0; ///< Sum of all weights. + bool DidOverflow = false; ///< Whether \a Total did overflow. + + Distribution() = default; - Distribution() : Total(0), DidOverflow(false) {} void addLocal(const BlockNode &Node, uint64_t Amount) { add(Node, Amount, Weight::Local); } + void addExit(const BlockNode &Node, uint64_t Amount) { add(Node, Amount, Weight::Exit); } + void addBackedge(const BlockNode &Node, uint64_t Amount) { add(Node, Amount, Weight::Backedge); } @@ -390,6 +420,12 @@ public: /// \brief Indexed information about loops. std::list Loops; + /// \brief Virtual destructor. + /// + /// Need a virtual destructor to mask the compiler warning about + /// getBlockName(). + virtual ~BlockFrequencyInfoImplBase() = default; + /// \brief Add all edges out of a packaged loop to the distribution. /// /// Adds all edges from LocalLoopHead to Dist. Calls addToDist() to add each @@ -495,28 +531,24 @@ public: assert(!Freqs.empty()); return Freqs[0].Integer; } - /// \brief Virtual destructor. - /// - /// Need a virtual destructor to mask the compiler warning about - /// getBlockName(). - virtual ~BlockFrequencyInfoImplBase() {} }; namespace bfi_detail { + template struct TypeMap {}; template <> struct TypeMap { - typedef BasicBlock BlockT; - typedef Function FunctionT; - typedef BranchProbabilityInfo BranchProbabilityInfoT; - typedef Loop LoopT; - typedef LoopInfo LoopInfoT; + using BlockT = BasicBlock; + using FunctionT = Function; + using BranchProbabilityInfoT = BranchProbabilityInfo; + using LoopT = Loop; + using LoopInfoT = LoopInfo; }; template <> struct TypeMap { - typedef MachineBasicBlock BlockT; - typedef MachineFunction FunctionT; - typedef MachineBranchProbabilityInfo BranchProbabilityInfoT; - typedef MachineLoop LoopT; - typedef MachineLoopInfo LoopInfoT; + using BlockT = MachineBasicBlock; + using FunctionT = MachineFunction; + using BranchProbabilityInfoT = MachineBranchProbabilityInfo; + using LoopT = MachineLoop; + using LoopInfoT = MachineLoopInfo; }; /// \brief Get the name of a MachineBasicBlock. @@ -554,25 +586,27 @@ template <> inline std::string getBlockName(const BasicBlock *BB) { /// and it explicitly lists predecessors and successors. The initialization /// that relies on \c MachineBasicBlock is defined in the header. struct IrreducibleGraph { - typedef BlockFrequencyInfoImplBase BFIBase; + using BFIBase = BlockFrequencyInfoImplBase; BFIBase &BFI; - typedef BFIBase::BlockNode BlockNode; + using BlockNode = BFIBase::BlockNode; struct IrrNode { BlockNode Node; - unsigned NumIn; + unsigned NumIn = 0; std::deque Edges; - IrrNode(const BlockNode &Node) : Node(Node), NumIn(0) {} - typedef std::deque::const_iterator iterator; + IrrNode(const BlockNode &Node) : Node(Node) {} + + using iterator = std::deque::const_iterator; + iterator pred_begin() const { return Edges.begin(); } iterator succ_begin() const { return Edges.begin() + NumIn; } iterator pred_end() const { return succ_begin(); } iterator succ_end() const { return Edges.end(); } }; BlockNode Start; - const IrrNode *StartIrr; + const IrrNode *StartIrr = nullptr; std::vector Nodes; SmallDenseMap Lookup; @@ -587,8 +621,7 @@ struct IrreducibleGraph { /// user of this. template IrreducibleGraph(BFIBase &BFI, const BFIBase::LoopData *OuterLoop, - BlockEdgesAdder addBlockEdges) - : BFI(BFI), StartIrr(nullptr) { + BlockEdgesAdder addBlockEdges) : BFI(BFI) { initialize(OuterLoop, addBlockEdges); } @@ -597,10 +630,12 @@ struct IrreducibleGraph { BlockEdgesAdder addBlockEdges); void addNodesInLoop(const BFIBase::LoopData &OuterLoop); void addNodesInFunction(); + void addNode(const BlockNode &Node) { Nodes.emplace_back(Node); BFI.Working[Node.Index].getMass() = BlockMass::getEmpty(); } + void indexNodes(); template void addEdges(const BlockNode &Node, const BFIBase::LoopData *OuterLoop, @@ -608,6 +643,7 @@ struct IrreducibleGraph { void addEdge(IrrNode &Irr, const BlockNode &Succ, const BFIBase::LoopData *OuterLoop); }; + template void IrreducibleGraph::initialize(const BFIBase::LoopData *OuterLoop, BlockEdgesAdder addBlockEdges) { @@ -622,6 +658,7 @@ void IrreducibleGraph::initialize(const BFIBase::LoopData *OuterLoop, } StartIrr = Lookup[Start.Index]; } + template void IrreducibleGraph::addEdges(const BlockNode &Node, const BFIBase::LoopData *OuterLoop, @@ -638,7 +675,8 @@ void IrreducibleGraph::addEdges(const BlockNode &Node, else addBlockEdges(*this, Irr, OuterLoop); } -} + +} // end namespace bfi_detail /// \brief Shared implementation for block frequency analysis. /// @@ -794,28 +832,27 @@ void IrreducibleGraph::addEdges(const BlockNode &Node, /// (Running this until fixed point would "solve" the geometric /// series by simulation.) template class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase { - typedef typename bfi_detail::TypeMap::BlockT BlockT; - typedef typename bfi_detail::TypeMap::FunctionT FunctionT; - typedef typename bfi_detail::TypeMap::BranchProbabilityInfoT - BranchProbabilityInfoT; - typedef typename bfi_detail::TypeMap::LoopT LoopT; - typedef typename bfi_detail::TypeMap::LoopInfoT LoopInfoT; - // This is part of a workaround for a GCC 4.7 crash on lambdas. friend struct bfi_detail::BlockEdgesAdder; - typedef GraphTraits Successor; - typedef GraphTraits> Predecessor; + using BlockT = typename bfi_detail::TypeMap::BlockT; + using FunctionT = typename bfi_detail::TypeMap::FunctionT; + using BranchProbabilityInfoT = + typename bfi_detail::TypeMap::BranchProbabilityInfoT; + using LoopT = typename bfi_detail::TypeMap::LoopT; + using LoopInfoT = typename bfi_detail::TypeMap::LoopInfoT; + using Successor = GraphTraits; + using Predecessor = GraphTraits>; - const BranchProbabilityInfoT *BPI; - const LoopInfoT *LI; - const FunctionT *F; + const BranchProbabilityInfoT *BPI = nullptr; + const LoopInfoT *LI = nullptr; + const FunctionT *F = nullptr; // All blocks in reverse postorder. std::vector RPOT; DenseMap Nodes; - typedef typename std::vector::const_iterator rpot_iterator; + using rpot_iterator = typename std::vector::const_iterator; rpot_iterator rpot_begin() const { return RPOT.begin(); } rpot_iterator rpot_end() const { return RPOT.end(); } @@ -913,25 +950,31 @@ template class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase { } public: + BlockFrequencyInfoImpl() = default; + const FunctionT *getFunction() const { return F; } void calculate(const FunctionT &F, const BranchProbabilityInfoT &BPI, const LoopInfoT &LI); - BlockFrequencyInfoImpl() : BPI(nullptr), LI(nullptr), F(nullptr) {} using BlockFrequencyInfoImplBase::getEntryFreq; + BlockFrequency getBlockFreq(const BlockT *BB) const { return BlockFrequencyInfoImplBase::getBlockFreq(getNode(BB)); } + Optional getBlockProfileCount(const Function &F, const BlockT *BB) const { return BlockFrequencyInfoImplBase::getBlockProfileCount(F, getNode(BB)); } + Optional getProfileCountFromFreq(const Function &F, uint64_t Freq) const { return BlockFrequencyInfoImplBase::getProfileCountFromFreq(F, Freq); } + void setBlockFreq(const BlockT *BB, uint64_t Freq); + Scaled64 getFloatingBlockFreq(const BlockT *BB) const { return BlockFrequencyInfoImplBase::getFloatingBlockFreq(getNode(BB)); } @@ -950,9 +993,10 @@ public: /// \a BlockFrequencyInfoImplBase::print() only knows reverse post-order, so /// we need to override it here. raw_ostream &print(raw_ostream &OS) const override; - using BlockFrequencyInfoImplBase::dump; + using BlockFrequencyInfoImplBase::dump; using BlockFrequencyInfoImplBase::printBlockFreq; + raw_ostream &printBlockFreq(raw_ostream &OS, const BlockT *BB) const { return BlockFrequencyInfoImplBase::printBlockFreq(OS, getNode(BB)); } @@ -1153,14 +1197,17 @@ template void BlockFrequencyInfoImpl::computeMassInFunction() { /// \note This should be a lambda, but that crashes GCC 4.7. namespace bfi_detail { + template struct BlockEdgesAdder { - typedef BT BlockT; - typedef BlockFrequencyInfoImplBase::LoopData LoopData; - typedef GraphTraits Successor; + using BlockT = BT; + using LoopData = BlockFrequencyInfoImplBase::LoopData; + using Successor = GraphTraits; const BlockFrequencyInfoImpl &BFI; + explicit BlockEdgesAdder(const BlockFrequencyInfoImpl &BFI) : BFI(BFI) {} + void operator()(IrreducibleGraph &G, IrreducibleGraph::IrrNode &Irr, const LoopData *OuterLoop) { const BlockT *BB = BFI.RPOT[Irr.Node.Index]; @@ -1168,7 +1215,9 @@ template struct BlockEdgesAdder { G.addEdge(Irr, BFI.getNode(Succ), OuterLoop); } }; -} + +} // end namespace bfi_detail + template void BlockFrequencyInfoImpl::computeIrreducibleMass( LoopData *OuterLoop, std::list::iterator Insert) { @@ -1177,6 +1226,7 @@ void BlockFrequencyInfoImpl::computeIrreducibleMass( else dbgs() << "function\n"); using namespace bfi_detail; + // Ideally, addBlockEdges() would be declared here as a lambda, but that // crashes GCC 4.7. BlockEdgesAdder addBlockEdges(*this); @@ -1245,15 +1295,16 @@ enum GVDAGType { GVDT_None, GVDT_Fraction, GVDT_Integer, GVDT_Count }; template struct BFIDOTGraphTraitsBase : public DefaultDOTGraphTraits { + using GTraits = GraphTraits; + using NodeRef = typename GTraits::NodeRef; + using EdgeIter = typename GTraits::ChildIteratorType; + using NodeIter = typename GTraits::nodes_iterator; + + uint64_t MaxFrequency = 0; + explicit BFIDOTGraphTraitsBase(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} - typedef GraphTraits GTraits; - typedef typename GTraits::NodeRef NodeRef; - typedef typename GTraits::ChildIteratorType EdgeIter; - typedef typename GTraits::nodes_iterator NodeIter; - - uint64_t MaxFrequency = 0; static std::string getGraphName(const BlockFrequencyInfoT *G) { return G->getFunction()->getName(); } diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 94d3d4de6c9..88ce6b4bd94 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -1,4 +1,4 @@ -//===--- BranchProbabilityInfo.h - Branch Probability Analysis --*- C++ -*-===// +//===- BranchProbabilityInfo.h - Branch Probability Analysis ----*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -15,19 +15,28 @@ #define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/ValueHandle.h" -#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/BranchProbability.h" +#include "llvm/Support/Casting.h" +#include +#include +#include +#include namespace llvm { + +class Function; class LoopInfo; -class TargetLibraryInfo; class raw_ostream; +class TargetLibraryInfo; +class Value; /// \brief Analysis providing branch probability information. /// @@ -43,7 +52,8 @@ class raw_ostream; /// value 10. class BranchProbabilityInfo { public: - BranchProbabilityInfo() {} + BranchProbabilityInfo() = default; + BranchProbabilityInfo(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI = nullptr) { calculate(F, LI, TLI); @@ -54,6 +64,9 @@ public: PostDominatedByUnreachable(std::move(Arg.PostDominatedByUnreachable)), PostDominatedByColdCall(std::move(Arg.PostDominatedByColdCall)) {} + BranchProbabilityInfo(const BranchProbabilityInfo &) = delete; + BranchProbabilityInfo &operator=(const BranchProbabilityInfo &) = delete; + BranchProbabilityInfo &operator=(BranchProbabilityInfo &&RHS) { releaseMemory(); Probs = std::move(RHS.Probs); @@ -125,13 +138,11 @@ public: void eraseBlock(const BasicBlock *BB); private: - void operator=(const BranchProbabilityInfo &) = delete; - BranchProbabilityInfo(const BranchProbabilityInfo &) = delete; - // We need to store CallbackVH's in order to correctly handle basic block // removal. class BasicBlockCallbackVH final : public CallbackVH { BranchProbabilityInfo *BPI; + void deleted() override { assert(BPI != nullptr); BPI->eraseBlock(cast(getValPtr())); @@ -139,14 +150,15 @@ private: } public: - BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI=nullptr) + BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr) : CallbackVH(const_cast(V)), BPI(BPI) {} }; + DenseSet> Handles; // Since we allow duplicate edges from one basic block to another, we use // a pair (PredBlock and an index in the successors) to specify an edge. - typedef std::pair Edge; + using Edge = std::pair; // Default weight value. Used when we don't have information about the edge. // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of @@ -183,11 +195,12 @@ private: class BranchProbabilityAnalysis : public AnalysisInfoMixin { friend AnalysisInfoMixin; + static AnalysisKey Key; public: - /// \brief Provide the result typedef for this analysis pass. - typedef BranchProbabilityInfo Result; + /// \brief Provide the result type for this analysis pass. + using Result = BranchProbabilityInfo; /// \brief Run the analysis pass over a function and produce BPI. BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM); @@ -200,6 +213,7 @@ class BranchProbabilityPrinterPass public: explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; @@ -224,6 +238,6 @@ public: void print(raw_ostream &OS, const Module *M = nullptr) const override; }; -} +} // end namespace llvm -#endif +#endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H diff --git a/include/llvm/Analysis/DemandedBits.h b/include/llvm/Analysis/DemandedBits.h index e52c66f361c..27e47679a25 100644 --- a/include/llvm/Analysis/DemandedBits.h +++ b/include/llvm/Analysis/DemandedBits.h @@ -1,4 +1,4 @@ -//===-- llvm/Analysis/DemandedBits.h - Determine demanded bits --*- C++ -*-===// +//===- llvm/Analysis/DemandedBits.h - Determine demanded bits ---*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -24,23 +24,24 @@ #include "llvm/ADT/APInt.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/IR/PassManager.h" #include "llvm/Pass.h" namespace llvm { -class FunctionPass; +class AssumptionCache; +class DominatorTree; class Function; class Instruction; -class DominatorTree; -class AssumptionCache; struct KnownBits; +class raw_ostream; class DemandedBits { public: DemandedBits(Function &F, AssumptionCache &AC, DominatorTree &DT) : - F(F), AC(AC), DT(DT), Analyzed(false) {} + F(F), AC(AC), DT(DT) {} /// Return the bits demanded from instruction I. APInt getDemandedBits(Instruction *I); @@ -51,17 +52,17 @@ public: void print(raw_ostream &OS); private: - Function &F; - AssumptionCache &AC; - DominatorTree &DT; - void performAnalysis(); void determineLiveOperandBits(const Instruction *UserI, const Instruction *I, unsigned OperandNo, const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2); - bool Analyzed; + Function &F; + AssumptionCache &AC; + DominatorTree &DT; + + bool Analyzed = false; // The set of visited instructions (non-integer-typed only). SmallPtrSet Visited; @@ -71,8 +72,10 @@ private: class DemandedBitsWrapperPass : public FunctionPass { private: mutable Optional DB; + public: static char ID; // Pass identification, replacement for typeid + DemandedBitsWrapperPass(); bool runOnFunction(Function &F) override; @@ -89,11 +92,12 @@ public: /// An analysis that produces \c DemandedBits for a function. class DemandedBitsAnalysis : public AnalysisInfoMixin { friend AnalysisInfoMixin; + static AnalysisKey Key; public: - /// \brief Provide the result typedef for this analysis pass. - typedef DemandedBits Result; + /// \brief Provide the result type for this analysis pass. + using Result = DemandedBits; /// \brief Run the analysis pass over a function and produce demanded bits /// information. @@ -106,12 +110,13 @@ class DemandedBitsPrinterPass : public PassInfoMixin { public: explicit DemandedBitsPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; /// Create a demanded bits analysis pass. FunctionPass *createDemandedBitsWrapperPass(); -} // End llvm namespace +} // end namespace llvm -#endif +#endif // LLVM_ANALYSIS_DEMANDED_BITS_H diff --git a/include/llvm/Analysis/Trace.h b/include/llvm/Analysis/Trace.h index bedd654c652..b05d384ab1a 100644 --- a/include/llvm/Analysis/Trace.h +++ b/include/llvm/Analysis/Trace.h @@ -22,39 +22,36 @@ #include namespace llvm { - class BasicBlock; - class Function; - class Module; - class raw_ostream; + +class BasicBlock; +class Function; +class Module; +class raw_ostream; class Trace { - typedef std::vector BasicBlockListType; + using BasicBlockListType = std::vector; + BasicBlockListType BasicBlocks; public: /// Trace ctor - Make a new trace from a vector of basic blocks, /// residing in the function which is the parent of the first /// basic block in the vector. - /// Trace(const std::vector &vBB) : BasicBlocks (vBB) {} /// getEntryBasicBlock - Return the entry basic block (first block) /// of the trace. - /// BasicBlock *getEntryBasicBlock () const { return BasicBlocks[0]; } /// operator[]/getBlock - Return basic block N in the trace. - /// BasicBlock *operator[](unsigned i) const { return BasicBlocks[i]; } BasicBlock *getBlock(unsigned i) const { return BasicBlocks[i]; } /// getFunction - Return this trace's parent function. - /// Function *getFunction () const; /// getModule - Return this Module that contains this trace's parent /// function. - /// Module *getModule () const; /// getBlockIndex - Return the index of the specified basic block in the @@ -68,14 +65,12 @@ public: /// contains - Returns true if this trace contains the given basic /// block. - /// bool contains(const BasicBlock *X) const { return getBlockIndex(X) != -1; } /// Returns true if B1 occurs before B2 in the trace, or if it is the same /// block as B2.. Both blocks must be in the trace. - /// bool dominates(const BasicBlock *B1, const BasicBlock *B2) const { int B1Idx = getBlockIndex(B1), B2Idx = getBlockIndex(B2); assert(B1Idx != -1 && B2Idx != -1 && "Block is not in the trace!"); @@ -83,10 +78,10 @@ public: } // BasicBlock iterators... - typedef BasicBlockListType::iterator iterator; - typedef BasicBlockListType::const_iterator const_iterator; - typedef std::reverse_iterator const_reverse_iterator; - typedef std::reverse_iterator reverse_iterator; + using iterator = BasicBlockListType::iterator; + using const_iterator = BasicBlockListType::const_iterator; + using reverse_iterator = std::reverse_iterator; + using const_reverse_iterator = std::reverse_iterator; iterator begin() { return BasicBlocks.begin(); } const_iterator begin() const { return BasicBlocks.begin(); } @@ -105,12 +100,10 @@ public: iterator erase(iterator q1, iterator q2) { return BasicBlocks.erase (q1, q2); } /// print - Write trace to output stream. - /// void print(raw_ostream &O) const; /// dump - Debugger convenience method; writes trace to standard error /// output stream. - /// void dump() const; }; diff --git a/lib/Analysis/BlockFrequencyInfo.cpp b/lib/Analysis/BlockFrequencyInfo.cpp index 07a2a9229fd..8175aa07d15 100644 --- a/lib/Analysis/BlockFrequencyInfo.cpp +++ b/lib/Analysis/BlockFrequencyInfo.cpp @@ -12,15 +12,22 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/iterator.h" #include "llvm/Analysis/BlockFrequencyInfoImpl.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/Passes.h" #include "llvm/IR/CFG.h" -#include "llvm/InitializePasses.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" #include "llvm/Support/GraphWriter.h" +#include "llvm/Support/raw_ostream.h" +#include +#include +#include using namespace llvm; @@ -71,7 +78,6 @@ cl::opt namespace llvm { static GVDAGType getGVDT() { - if (PGOViewCounts) return GVDT_Count; return ViewBlockFreqPropagationDAG; @@ -79,27 +85,31 @@ static GVDAGType getGVDT() { template <> struct GraphTraits { - typedef const BasicBlock *NodeRef; - typedef succ_const_iterator ChildIteratorType; - typedef pointer_iterator nodes_iterator; + using NodeRef = const BasicBlock *; + using ChildIteratorType = succ_const_iterator; + using nodes_iterator = pointer_iterator; static NodeRef getEntryNode(const BlockFrequencyInfo *G) { return &G->getFunction()->front(); } + static ChildIteratorType child_begin(const NodeRef N) { return succ_begin(N); } + static ChildIteratorType child_end(const NodeRef N) { return succ_end(N); } + static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) { return nodes_iterator(G->getFunction()->begin()); } + static nodes_iterator nodes_end(const BlockFrequencyInfo *G) { return nodes_iterator(G->getFunction()->end()); } }; -typedef BFIDOTGraphTraitsBase - BFIDOTGTraitsBase; +using BFIDOTGTraitsBase = + BFIDOTGraphTraitsBase; template <> struct DOTGraphTraits : public BFIDOTGTraitsBase { @@ -127,7 +137,7 @@ struct DOTGraphTraits : public BFIDOTGTraitsBase { } // end namespace llvm -BlockFrequencyInfo::BlockFrequencyInfo() {} +BlockFrequencyInfo::BlockFrequencyInfo() = default; BlockFrequencyInfo::BlockFrequencyInfo(const Function &F, const BranchProbabilityInfo &BPI, @@ -148,7 +158,7 @@ BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) { // defined at the first ODR-use which is the BFI member in the // LazyBlockFrequencyInfo header. The dtor needs the BlockFrequencyInfoImpl // template instantiated which is not available in the header. -BlockFrequencyInfo::~BlockFrequencyInfo() {} +BlockFrequencyInfo::~BlockFrequencyInfo() = default; bool BlockFrequencyInfo::invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &) { @@ -254,7 +264,6 @@ void BlockFrequencyInfo::print(raw_ostream &OS) const { BFI->print(OS); } - INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq", "Block Frequency Analysis", true, true) INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass) @@ -264,13 +273,12 @@ INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq", char BlockFrequencyInfoWrapperPass::ID = 0; - BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass() : FunctionPass(ID) { initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry()); } -BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() {} +BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() = default; void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS, const Module *) const { diff --git a/lib/Analysis/BlockFrequencyInfoImpl.cpp b/lib/Analysis/BlockFrequencyInfoImpl.cpp index e5d8c3347c1..1030407b766 100644 --- a/lib/Analysis/BlockFrequencyInfoImpl.cpp +++ b/lib/Analysis/BlockFrequencyInfoImpl.cpp @@ -12,10 +12,28 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/BlockFrequencyInfoImpl.h" +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/None.h" #include "llvm/ADT/SCCIterator.h" #include "llvm/IR/Function.h" +#include "llvm/Support/BlockFrequency.h" +#include "llvm/Support/BranchProbability.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ScaledNumber.h" +#include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" +#include +#include +#include +#include +#include +#include #include +#include +#include using namespace llvm; using namespace llvm::bfi_detail; @@ -47,13 +65,13 @@ raw_ostream &BlockMass::print(raw_ostream &OS) const { namespace { -typedef BlockFrequencyInfoImplBase::BlockNode BlockNode; -typedef BlockFrequencyInfoImplBase::Distribution Distribution; -typedef BlockFrequencyInfoImplBase::Distribution::WeightList WeightList; -typedef BlockFrequencyInfoImplBase::Scaled64 Scaled64; -typedef BlockFrequencyInfoImplBase::LoopData LoopData; -typedef BlockFrequencyInfoImplBase::Weight Weight; -typedef BlockFrequencyInfoImplBase::FrequencyData FrequencyData; +using BlockNode = BlockFrequencyInfoImplBase::BlockNode; +using Distribution = BlockFrequencyInfoImplBase::Distribution; +using WeightList = BlockFrequencyInfoImplBase::Distribution::WeightList; +using Scaled64 = BlockFrequencyInfoImplBase::Scaled64; +using LoopData = BlockFrequencyInfoImplBase::LoopData; +using Weight = BlockFrequencyInfoImplBase::Weight; +using FrequencyData = BlockFrequencyInfoImplBase::FrequencyData; /// \brief Dithering mass distributer. /// @@ -158,7 +176,8 @@ static void combineWeightsBySorting(WeightList &Weights) { static void combineWeightsByHashing(WeightList &Weights) { // Collect weights into a DenseMap. - typedef DenseMap HashTable; + using HashTable = DenseMap; + HashTable Combined(NextPowerOf2(2 * Weights.size())); for (const Weight &W : Weights) combineWeight(Combined[W.TargetNode.Index], W); @@ -569,7 +588,7 @@ void BlockFrequencyInfoImplBase::setBlockFreq(const BlockNode &Node, std::string BlockFrequencyInfoImplBase::getBlockName(const BlockNode &Node) const { - return std::string(); + return {}; } std::string @@ -627,16 +646,17 @@ void IrreducibleGraph::addEdge(IrrNode &Irr, const BlockNode &Succ, } namespace llvm { -template <> struct GraphTraits { - typedef bfi_detail::IrreducibleGraph GraphT; - typedef const GraphT::IrrNode *NodeRef; - typedef GraphT::IrrNode::iterator ChildIteratorType; +template <> struct GraphTraits { + using GraphT = bfi_detail::IrreducibleGraph; + using NodeRef = const GraphT::IrrNode *; + using ChildIteratorType = GraphT::IrrNode::iterator; static NodeRef getEntryNode(const GraphT &G) { return G.StartIrr; } static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } }; + } // end namespace llvm /// \brief Find extra irreducible headers. diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index a329e5ad48c..3748c651fd2 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -1,4 +1,4 @@ -//===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -----------===// +//===- BranchProbabilityInfo.cpp - Branch Probability Analysis ------------===// // // The LLVM Compiler Infrastructure // @@ -13,16 +13,32 @@ #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/Attributes.h" +#include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" +#include "llvm/IR/PassManager.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Value.h" +#include "llvm/Pass.h" +#include "llvm/Support/BranchProbability.h" +#include "llvm/Support/Casting.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include +#include +#include +#include using namespace llvm; @@ -722,7 +738,6 @@ raw_ostream & BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, const BasicBlock *Dst) const { - const BranchProbability Prob = getEdgeProbability(Src, Dst); OS << "edge " << Src->getName() << " -> " << Dst->getName() << " probability is " << Prob diff --git a/lib/Analysis/DemandedBits.cpp b/lib/Analysis/DemandedBits.cpp index 9c53f9140ca..7e6d6b01a35 100644 --- a/lib/Analysis/DemandedBits.cpp +++ b/lib/Analysis/DemandedBits.cpp @@ -1,4 +1,4 @@ -//===---- DemandedBits.cpp - Determine demanded bits ----------------------===// +//===- DemandedBits.cpp - Determine demanded bits -------------------------===// // // The LLVM Compiler Infrastructure // @@ -20,30 +20,41 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/DemandedBits.h" -#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/APInt.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/BasicBlock.h" -#include "llvm/IR/CFG.h" +#include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" +#include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/InstIterator.h" -#include "llvm/IR/Instructions.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Instruction.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Intrinsics.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" +#include "llvm/IR/PassManager.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Use.h" #include "llvm/Pass.h" +#include "llvm/Support/Casting.h" #include "llvm/Support/Debug.h" #include "llvm/Support/KnownBits.h" #include "llvm/Support/raw_ostream.h" +#include +#include + using namespace llvm; #define DEBUG_TYPE "demanded-bits" char DemandedBitsWrapperPass::ID = 0; + INITIALIZE_PASS_BEGIN(DemandedBitsWrapperPass, "demanded-bits", "Demanded bits analysis", false, false) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) diff --git a/lib/Analysis/Trace.cpp b/lib/Analysis/Trace.cpp index c7e2c0f3412..34c998501a6 100644 --- a/lib/Analysis/Trace.cpp +++ b/lib/Analysis/Trace.cpp @@ -16,9 +16,12 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/Trace.h" +#include "llvm/IR/BasicBlock.h" #include "llvm/IR/Function.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" + using namespace llvm; Function *Trace::getFunction() const { @@ -30,7 +33,6 @@ Module *Trace::getModule() const { } /// print - Write trace to output stream. -/// void Trace::print(raw_ostream &O) const { Function *F = getFunction(); O << "; Trace from function " << F->getName() << ", blocks:\n"; @@ -45,7 +47,6 @@ void Trace::print(raw_ostream &O) const { #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) /// dump - Debugger convenience method; writes trace to standard error /// output stream. -/// LLVM_DUMP_METHOD void Trace::dump() const { print(dbgs()); } -- 2.50.1