1f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===// 2f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// 3f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// The LLVM Compiler Infrastructure 4f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// 5f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// This file is distributed under the University of Illinois Open Source 6f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// License. See LICENSE.TXT for details. 7f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// 8f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot//===----------------------------------------------------------------------===// 9f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// 10f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// This file defines the DominanceFrontier class, which calculate and holds the 11f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// dominance frontier for a function. 12f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// 13f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// This should be considered deprecated, don't add any more uses of this data 14f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// structure. 15f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot// 16f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot//===----------------------------------------------------------------------===// 17f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 18f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H 19f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#define LLVM_ANALYSIS_DOMINANCEFRONTIER_H 20f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 21f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#include "llvm/ADT/GraphTraits.h" 22f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#include "llvm/IR/PassManager.h" 23f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#include "llvm/Pass.h" 24f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#include "llvm/Support/GenericDomTree.h" 25f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#include <cassert> 26f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#include <map> 27f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#include <set> 28f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#include <utility> 29f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#include <vector> 30f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 31f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotnamespace llvm { 32f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 33f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotclass Function; 34f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotclass raw_ostream; 35f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 36f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot//===----------------------------------------------------------------------===// 37f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot/// DominanceFrontierBase - Common base class for computing forward and inverse 38f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot/// dominance frontiers for a function. 39f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot/// 40f3014761c955345d6e05491608e73228d014afbandroid-build-team Robottemplate <class BlockT, bool IsPostDom> 41f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotclass DominanceFrontierBase { 42f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotpublic: 43f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using DomSetType = std::set<BlockT *>; // Dom set for a bb 44f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using DomSetMapType = std::map<BlockT *, DomSetType>; // Dom set map 45f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 46f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotprotected: 47f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using BlockTraits = GraphTraits<BlockT *>; 48f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 49f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot DomSetMapType Frontiers; 50f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot // Postdominators can have multiple roots. 51f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot SmallVector<BlockT *, IsPostDom ? 4 : 1> Roots; 52f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot static constexpr bool IsPostDominators = IsPostDom; 53f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 54f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotpublic: 55f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot DominanceFrontierBase() = default; 56f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 57f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// getRoots - Return the root blocks of the current CFG. This may include 58f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// multiple blocks if we are computing post dominators. For forward 59f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// dominators, this will always be a single block (the entry node). 60f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; } 61f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 62f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot BlockT *getRoot() const { 63f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot assert(Roots.size() == 1 && "Should always have entry node!"); 64f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot return Roots[0]; 65f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot } 66f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 67f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// isPostDominator - Returns true if analysis based of postdoms 68f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot bool isPostDominator() const { 69f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot return IsPostDominators; 70f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot } 71f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 72f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void releaseMemory() { 73f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot Frontiers.clear(); 74f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot } 75f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 76f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot // Accessor interface: 77f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using iterator = typename DomSetMapType::iterator; 78f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using const_iterator = typename DomSetMapType::const_iterator; 79f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 80f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot iterator begin() { return Frontiers.begin(); } 81f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot const_iterator begin() const { return Frontiers.begin(); } 82f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot iterator end() { return Frontiers.end(); } 83f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot const_iterator end() const { return Frontiers.end(); } 84f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot iterator find(BlockT *B) { return Frontiers.find(B); } 85f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot const_iterator find(BlockT *B) const { return Frontiers.find(B); } 86f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 87f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) { 88f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot assert(find(BB) == end() && "Block already in DominanceFrontier!"); 89f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot return Frontiers.insert(std::make_pair(BB, frontier)).first; 90f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot } 91f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 92f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// removeBlock - Remove basic block BB's frontier. 93f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void removeBlock(BlockT *BB); 94f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 95f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void addToFrontier(iterator I, BlockT *Node); 96f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 97f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void removeFromFrontier(iterator I, BlockT *Node); 98f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 99f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// compareDomSet - Return false if two domsets match. Otherwise 100f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// return true; 101f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const; 102f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 103f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// compare - Return true if the other dominance frontier base matches 104f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// this dominance frontier base. Otherwise return false. 105f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot bool compare(DominanceFrontierBase &Other) const; 106f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 107f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// print - Convert to human readable form 108f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// 109f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void print(raw_ostream &OS) const; 110f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 111f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// dump - Dump the dominance frontier to dbgs(). 112f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 113f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void dump() const; 114f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#endif 115f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot}; 116f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 117f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot//===------------------------------------- 118f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is 119f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot/// used to compute a forward dominator frontiers. 120f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot/// 121f3014761c955345d6e05491608e73228d014afbandroid-build-team Robottemplate <class BlockT> 122f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotclass ForwardDominanceFrontierBase 123f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot : public DominanceFrontierBase<BlockT, false> { 124f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotprivate: 125f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using BlockTraits = GraphTraits<BlockT *>; 126f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 127f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotpublic: 128f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using DomTreeT = DomTreeBase<BlockT>; 129f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using DomTreeNodeT = DomTreeNodeBase<BlockT>; 130f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using DomSetType = typename DominanceFrontierBase<BlockT, false>::DomSetType; 131f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 132f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void analyze(DomTreeT &DT) { 133f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot assert(DT.getRoots().size() == 1 && 134f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot "Only one entry block for forward domfronts!"); 135f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot this->Roots = {DT.getRoot()}; 136f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot calculate(DT, DT[this->Roots[0]]); 137f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot } 138f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 139f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node); 140f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot}; 141f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 142f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotclass DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> { 143f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotpublic: 144f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using DomTreeT = DomTreeBase<BasicBlock>; 145f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using DomTreeNodeT = DomTreeNodeBase<BasicBlock>; 146f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using DomSetType = DominanceFrontierBase<BasicBlock, false>::DomSetType; 147f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using iterator = DominanceFrontierBase<BasicBlock, false>::iterator; 148f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using const_iterator = 149f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot DominanceFrontierBase<BasicBlock, false>::const_iterator; 150f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 151f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// Handle invalidation explicitly. 152f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot bool invalidate(Function &F, const PreservedAnalyses &PA, 153f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot FunctionAnalysisManager::Invalidator &); 154f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot}; 155f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 156f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotclass DominanceFrontierWrapperPass : public FunctionPass { 157f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot DominanceFrontier DF; 158f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 159f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotpublic: 160f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot static char ID; // Pass ID, replacement for typeid 161f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 162f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot DominanceFrontierWrapperPass(); 163f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 164f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot DominanceFrontier &getDominanceFrontier() { return DF; } 165f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot const DominanceFrontier &getDominanceFrontier() const { return DF; } 166f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 167f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void releaseMemory() override; 168f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 169f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot bool runOnFunction(Function &) override; 170f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 171f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void getAnalysisUsage(AnalysisUsage &AU) const override; 172f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 173f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void print(raw_ostream &OS, const Module * = nullptr) const override; 174f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 175f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot void dump() const; 176f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot}; 177f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 178f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotextern template class DominanceFrontierBase<BasicBlock, false>; 179f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotextern template class DominanceFrontierBase<BasicBlock, true>; 180f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotextern template class ForwardDominanceFrontierBase<BasicBlock>; 181f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 182f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot/// \brief Analysis pass which computes a \c DominanceFrontier. 183f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotclass DominanceFrontierAnalysis 184f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot : public AnalysisInfoMixin<DominanceFrontierAnalysis> { 185f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot friend AnalysisInfoMixin<DominanceFrontierAnalysis>; 186f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 187f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot static AnalysisKey Key; 188f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 189f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotpublic: 190f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// \brief Provide the result type for this analysis pass. 191f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot using Result = DominanceFrontier; 192f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 193f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot /// \brief Run the analysis pass over a function and produce a dominator tree. 194f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot DominanceFrontier run(Function &F, FunctionAnalysisManager &AM); 195f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot}; 196f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 197f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot/// \brief Printer pass for the \c DominanceFrontier. 198f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotclass DominanceFrontierPrinterPass 199f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot : public PassInfoMixin<DominanceFrontierPrinterPass> { 200f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot raw_ostream &OS; 201f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 202f3014761c955345d6e05491608e73228d014afbandroid-build-team Robotpublic: 203f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot explicit DominanceFrontierPrinterPass(raw_ostream &OS); 204f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 205f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 206f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot}; 207f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 208f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot} // end namespace llvm 209f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot 210f3014761c955345d6e05491608e73228d014afbandroid-build-team Robot#endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H 211