Index: include/llvm/Analysis/ControlDependenceEquivalence.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ControlDependenceEquivalence.h @@ -0,0 +1,255 @@ +//===- ControlDependenceEquivalence.h - Compute Control Equivalence-------*- C++ +//-*---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// \file +// \brief Determines control dependence equivalence classes for basic +// blocks. Any two blocks having the same set of control dependences land in one +// class. +// ===---------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CONTROLDEPENDENCEEQUIV_H +#define LLVM_ANALYSIS_CONTROLDEPENDENCEEQUIV_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Function.h" +#include "llvm/Pass.h" +#include "llvm/Support/raw_ostream.h" +#include +#include + +namespace llvm { +class BasicBlock; + +/// \brief Compute control dependence equivalence classes for all nodes of the +/// CFG. +/// Note that this implementation actually uses cycle equivalence to establish +/// class numbers. Any two nodes are cycle equivalent if they occur in the same +/// set of cycles. It can be shown that control dependence equivalence reduces +/// to undirected cycle equivalence for strongly connected control flow graphs. +/// +/// The algorithm is based on the paper, "The program structure tree: computing +/// control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which +/// also contains proofs for the aforementioned equivalence. References to line +/// numbers in the algorithm from figure 4 have been added [line:x]. +class ControlDependenceEquivalence : public FunctionPass { +public: + ControlDependenceEquivalence() + : FunctionPass(ID), Computed(false), FakeStart(nullptr), + FakeEnd(nullptr) { + initializeControlDependenceEquivalencePass( + *PassRegistry::getPassRegistry()); + } + static char ID; + + bool runOnFunction(Function &F) override; + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesAll(); + } + void releaseMemory() override; + + void print(raw_ostream &O, const Module * = nullptr) const override; + + /// \brief Return the control dependence class number for \p BB. All basic + /// blocks with the same class number have the same control dependences + unsigned getClassNumber(BasicBlock *BB) { + assert(Computed && "Trying to get equivalence classes before computation"); + return BlockInfo[BB].ClassNumber; + } + +private: + typedef enum { PredDirection, SuccDirection } DFSDirection; + struct Bracket; + typedef std::list BracketList; + struct Bracket { + // Direction in which this bracket was added. + DFSDirection Direction; + // Cached class when bracket was topmost. + unsigned RecentClass; + // Cached set-size when bracket was topmost. + unsigned RecentSize; + // Block that this bracket originates from. + const BasicBlock *From; + // Block that this bracket points to. + const BasicBlock *To; + // Whether this is a capping bracket + bool Capping; + }; + typedef SmallVector FakeEdgeListType; + + /// \brief A combined iterator class that walks both real CFG edges, and ones + /// from a vector of CFG edges. + /// + /// We use combined iterators to allow fake and real edges to be next to each + /// other. This is used to connect entry/exit blocks, and other edges. We do + /// not expect these will work for anything but our use. + template + class const_combined_iterator + : public std::iterator { + typedef std::iterator super; + + public: + typedef typename super::pointer pointer; + typedef typename super::reference reference; + + // We need to know when we hit the end, so we have to have the end + // iterator too + inline const_combined_iterator(RealType Begin, RealType End, + FakeType FBegin, FakeType FEnd) + : Real(Begin), RealEnd(End), Fake(FBegin), FakeEnd(FEnd) {} + inline bool operator==(const_combined_iterator &x) const { + return Real == x.Real && Fake == x.Fake; + } + inline bool operator!=(const_combined_iterator &x) const { + return !operator==(x); + } + inline reference operator*() const { + if (Real != RealEnd) + return *Real; + if (Fake != FakeEnd) + return *Fake; + llvm_unreachable("Tried to access past the end of our iterator"); + } + inline pointer *operator->() const { return &operator*(); } + + inline const_combined_iterator &operator++() { + if (Real != RealEnd) { + ++Real; + return *this; + } + if (Fake != FakeEnd) { + ++Fake; + return *this; + } + llvm_unreachable("Fell off the end of the iterator"); + } + + private: + RealType Real; + RealType RealEnd; + FakeType Fake; + FakeType FakeEnd; + }; + + typedef const_combined_iterator + const_combined_pred_iterator; + typedef const_combined_iterator + const_combined_succ_iterator; + inline const_combined_pred_iterator + combined_pred_begin(const BasicBlock *B, const FakeEdgeListType &EL) { + return const_combined_pred_iterator(pred_begin(B), pred_end(B), EL.begin(), + EL.end()); + } + + inline const_combined_pred_iterator + combined_pred_end(const BasicBlock *B, const FakeEdgeListType &EL) { + return const_combined_pred_iterator(pred_end(B), pred_end(B), EL.end(), + EL.end()); + } + inline const_combined_succ_iterator + combined_succ_begin(const BasicBlock *B, const FakeEdgeListType &EL) { + return const_combined_succ_iterator(succ_begin(B), succ_end(B), EL.begin(), + EL.end()); + } + + inline const_combined_succ_iterator + combined_succ_end(const BasicBlock *B, const FakeEdgeListType &EL) { + return const_combined_succ_iterator(succ_end(B), succ_end(B), EL.end(), + EL.end()); + } + + struct BlockData { + // Equivalence class number assigned to Block. + unsigned ClassNumber; + // Pre-order DFS number assigned to Block. + unsigned DFSNumber; + // Indicates Block has already been visited. + bool Visited; + // Indicates Block is on DFS stack during walk. + bool OnStack; + // List of brackets per Block. + BracketList BList; + // List of fake successor edges, if any + FakeEdgeListType FakeSuccEdges; + // List of fake predecessor edges, if any + FakeEdgeListType FakePredEdges; + // List of bracket iterators that point to us + std::list BracketIterators; + // Immediate child list + SmallVector Children; + // Backedges List. This is backedges to other nodes, not to our node. + SmallVector Backedges; + // Hi node value + const BasicBlock *Hi; + BlockData() + : ClassNumber(0), DFSNumber(0), Visited(false), OnStack(false) {} + ~BlockData() {} + }; + struct DFSStackEntry { + // Direction currently used in DFS walk. + DFSDirection Direction; + // Iterator used for "pred" direction. + const_combined_pred_iterator Pred; + // Iterator end for "pred" direction + const_combined_pred_iterator PredEnd; + // Iterator used for "succ" direction. + const_combined_succ_iterator Succ; + // Iterator end for "succ" direction. + const_combined_succ_iterator SuccEnd; + // Parent Block of entry during DFS walk. + const BasicBlock *ParentBlock; + // Basic Block that this stack entry belongs to + const BasicBlock *Block; + }; + // The stack is used during the undirected DFS walk. + typedef std::stack DFSStack; + void runUndirectedDFS(const BasicBlock *); + + // Called during the undirected DFS, these functions are helpers for the + // walk. + bool visitInPredDirection(DFSStack &, DFSStackEntry &); + bool visitInSuccDirection(DFSStack &, DFSStackEntry &); + void visitHelper(DFSStack &, DFSStackEntry &, const BasicBlock *, + const BasicBlock *, DFSDirection); + + // Called at pre-visit during DFS walk. + void visitPre(const BasicBlock *); + + // Called at mid-visit during DFS walk. + void visitMid(const BasicBlock *, DFSDirection); + + // Called at post-visit during DFS walk. + void visitPost(const BasicBlock *, const BasicBlock *, DFSDirection); + + // Called when visiting a backedge during DFS walk. + void visitBackedge(const BasicBlock *, const BasicBlock *, DFSDirection); + + void pushDFS(DFSStack &, const BasicBlock *, const BasicBlock *, + DFSDirection); + void popDFS(DFSStack &, const BasicBlock *); + void debugBracketList(const BracketList &); + void removeBracketsPointingTo(BlockData &, const BasicBlock *, DFSDirection); + unsigned DFSNumber; + unsigned ClassNumber; + SmallDenseMap BlockInfo; + bool Computed; + const BasicBlock *FakeStart; + const BasicBlock *FakeEnd; +}; +} + +#endif Index: include/llvm/Analysis/Passes.h =================================================================== --- include/llvm/Analysis/Passes.h +++ include/llvm/Analysis/Passes.h @@ -173,6 +173,20 @@ // FunctionPass *createMemDerefPrinter(); + //===--------------------------------------------------------------------===// + // + // createControlDependenceEquivalencePass - This pass collects control dependence info + // information + // + FunctionPass *createControlDependenceEquivalencePass(); + + //===--------------------------------------------------------------------===// + // + // createControlDependenceEquivalencePrinter - This pass collects control dependence info + // information and prints it with -print-controldeps + // + FunctionPass *createControlDependenceEquivalencePrinter(); + } #endif Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -99,6 +99,8 @@ void initializeCodeGenPreparePass(PassRegistry&); void initializeConstantMergePass(PassRegistry&); void initializeConstantPropagationPass(PassRegistry&); +void initializeControlDependenceEquivalencePass(PassRegistry&); +void initializeControlDependenceEquivalencePrinterPass(PassRegistry&); void initializeMachineCopyPropagationPass(PassRegistry&); void initializeCostModelAnalysisPass(PassRegistry&); void initializeCorrelatedValuePropagationPass(PassRegistry&); Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h +++ include/llvm/LinkAllPasses.h @@ -70,6 +70,8 @@ (void) llvm::createStructurizeCFGPass(); (void) llvm::createConstantMergePass(); (void) llvm::createConstantPropagationPass(); + (void) llvm::createControlDependenceEquivalencePass(); + (void) llvm::createControlDependenceEquivalencePrinter(); (void) llvm::createCostModelAnalysisPass(); (void) llvm::createDeadArgEliminationPass(); (void) llvm::createDeadCodeEliminationPass(); Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -35,6 +35,8 @@ initializeCFGOnlyViewerPass(Registry); initializeCFGOnlyPrinterPass(Registry); initializeCFLAliasAnalysisPass(Registry); + initializeControlDependenceEquivalencePass(Registry); + initializeControlDependenceEquivalencePrinterPass(Registry); initializeDependenceAnalysisPass(Registry); initializeDelinearizationPass(Registry); initializeDivergenceAnalysisPass(Registry); Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -18,6 +18,7 @@ CostModel.cpp CodeMetrics.cpp ConstantFolding.cpp + ControlDependenceEquivalence.cpp Delinearization.cpp DependenceAnalysis.cpp DivergenceAnalysis.cpp Index: lib/Analysis/ControlDependenceEquivalence.cpp =================================================================== --- /dev/null +++ lib/Analysis/ControlDependenceEquivalence.cpp @@ -0,0 +1,565 @@ +//===- ControlDependenceEquivalence.cpp - Compute Control Equivalence------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +///\brief This implements a pass to compute control dependence equivalence +/// classes. +//===----------------------------------------------------------------------===// +#include "llvm/Analysis/ControlDependenceEquivalence.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Debug.h" +#include +#include +#include +using namespace llvm; + +#define DEBUG_TYPE "controlequiv" + +char ControlDependenceEquivalence::ID = 0; + +INITIALIZE_PASS(ControlDependenceEquivalence, "controldep", + "Control Dependence Construction", true, true); + +/// \brief Run the main algorithm starting from the exit blocks. We proceed to +/// perform an undirected depth-first backwards traversal that determines class +/// numbers for all participating blocks. Takes O(E) time and O(N) space. +bool ControlDependenceEquivalence::runOnFunction(Function &F) { + Computed = false; + DFSNumber = 0; + ClassNumber = 1; + // The algorithm requires we transform the CFG into a strongly connected + // component. We make a fake end and fake start, connect exiting blocks to the + // fake end, and then connect the fake start and the real start. We then + // start the DFS walk from the fake start block. + // The fake start also ensures that, for single block functions, we hit a + // backedge. If we did not have a fake start, we would have to special case + // the single block functions. + FakeStart = BasicBlock::Create(F.getContext(), "FakeStart"); + FakeEnd = BasicBlock::Create(F.getContext(), "FakeEnd"); + BlockInfo[FakeStart].FakePredEdges.push_back(FakeEnd); + BlockInfo[FakeEnd].FakeSuccEdges.push_back(FakeStart); + BlockInfo[&F.getEntryBlock()].FakePredEdges.push_back(FakeStart); + BlockInfo[FakeStart].FakeSuccEdges.push_back(&F.getEntryBlock()); + + for (auto &B : F) { + BlockData &Info = BlockInfo[&B]; + // If this is a reverse-unreachable block, connect it to fake start + // If we don't do this, we can end up in situations where we never hit a + // backedge, triggering an assert below + if (pred_empty(&B) && &B != &F.getEntryBlock()) { + Info.FakePredEdges.push_back(FakeStart); + BlockInfo[FakeStart].FakeSuccEdges.push_back(&B); + } + // If there are no successors, or it only connects to itself, we need to + // connect it to the exit block + if (succ_empty(&B)) { + // Connect leaves to fake end + Info.FakeSuccEdges.push_back(FakeEnd); + BlockInfo[FakeEnd].FakePredEdges.push_back(&B); + } + } + runUndirectedDFS(FakeEnd); + Computed = true; + return false; +} + +void ControlDependenceEquivalence::releaseMemory() { + if (Computed) { + BlockInfo.clear(); + delete FakeStart; + FakeStart = nullptr; + delete FakeEnd; + FakeEnd = nullptr; + } + Computed = false; +} + +void ControlDependenceEquivalence::print(raw_ostream &O, + const Module *M) const {} + +/// \brief Perform the common part of the successor and predecessor visits. +/// +/// Different iterator types make sharing all of the pred/successor visitation +/// code hard, this is the part that can be shared between the two. +void ControlDependenceEquivalence::visitHelper(DFSStack &Stack, + DFSStackEntry &Entry, + const BasicBlock *Block, + const BasicBlock *Next, + DFSDirection Direction) { + BlockData &Info = BlockInfo.find(Next)->second; + if (Info.Visited) + return; + // If it's on the stack, we've found a backedge, otherwise, push it + // and preorder-visit + if (Info.OnStack) { + DEBUG(dbgs() << "Maybe visit succ backedge\n"); + if (Block != Entry.ParentBlock) { + BlockInfo[Block].Backedges.push_back(Next); + visitBackedge(Block, Next, Direction); + } + } else { + BlockInfo[Block].Children.push_back(Next); + pushDFS(Stack, Next, Block, Direction); + visitPre(Next); + } +} + +/// \brief Perform the successor visit part of the undirected DFS. +/// +/// \return True if we are completely done with the stack entry. +bool ControlDependenceEquivalence::visitInSuccDirection(DFSStack &Stack, + DFSStackEntry &Entry) { + const BasicBlock *B = Entry.Block; + + if (Entry.Succ != Entry.SuccEnd) { + const BasicBlock *Succ = *Entry.Succ; + ++(Entry.Succ); + visitHelper(Stack, Entry, B, Succ, SuccDirection); + return false; + } + // Swap directions to predecessors + if (Entry.Pred != Entry.PredEnd) { + Entry.Direction = PredDirection; + visitMid(B, SuccDirection); + return false; + } + return true; +} + +/// \brief Perform the predecessor visit part of the undirected DFS. +/// +/// \return True if we are completely done with the stack entry. +bool ControlDependenceEquivalence::visitInPredDirection(DFSStack &Stack, + DFSStackEntry &Entry) { + const BasicBlock *B = Entry.Block; + + if (Entry.Pred != Entry.PredEnd) { + const BasicBlock *Pred = *Entry.Pred; + ++(Entry.Pred); + visitHelper(Stack, Entry, B, Pred, PredDirection); + return false; + } + // Swap directions to successors + if (Entry.Succ != Entry.SuccEnd) { + Entry.Direction = SuccDirection; + visitMid(B, PredDirection); + return false; + } + return true; +} + +/// \brief Performs and undirected DFS walk of the CFG. +/// +/// Conceptually all nodes are expanded, splitting "predecessors" and +/// "successors" out into separate nodes. During the traversal, edges towards +/// the representative type are preferred. +/// +/// \ / - Pre-visit: When N1 is visited in direction D the preferred +/// x N1 edge towards N is taken next, calling VisitPre(N). +/// | - Mid-visit: After all edges out of N2 in direction D have +/// | N been visited, we switch the direction and start considering +/// | edges out of N1 now, and we call VisitMid(N). +/// x N2 - Post-visit: After all edges out of N1 in direction opposite +/// / \ to D have been visited, we pop N and call VisitPost(N). +/// +/// This will yield a true spanning tree (without cross or forward edges) and +/// also discover proper back edges in both directions. +void ControlDependenceEquivalence::runUndirectedDFS( + const BasicBlock *StartBlock) { + DFSStack Stack; + // Start out walking backwards + pushDFS(Stack, StartBlock, nullptr, PredDirection); + + while (!Stack.empty()) { + DFSStackEntry &Entry = Stack.top(); + const BasicBlock *B = Entry.Block; + DEBUG(dbgs() << "Starting from block "); + DEBUG(B->printAsOperand(dbgs())); + DEBUG(dbgs() << "\n"); + // First visit in pred direction, then swap directions, then visit in succ + // direction, and swap back. Swapping is handling by the visit functins. + if (Entry.Direction == PredDirection) { + if (!visitInPredDirection(Stack, Entry)) + continue; + } + if (Entry.Direction == SuccDirection) { + if (!visitInSuccDirection(Stack, Entry)) + continue; + } + // Pop block from stack when done with all preds and succs. + assert(Entry.Pred == Entry.PredEnd && + "Did not finish predecessors before popping"); + assert(Entry.Succ == Entry.SuccEnd && + "Did not finish successors before popping"); + popDFS(Stack, B); + visitPost(B, Entry.ParentBlock, Entry.Direction); + } +} + +/// \brief Push an entry onto the DFS stack. +void ControlDependenceEquivalence::pushDFS(DFSStack &Stack, const BasicBlock *B, + const BasicBlock *From, + DFSDirection Direction) { + auto BlockResult = BlockInfo.find(B); + assert(BlockResult != BlockInfo.end() && "Should have found block data"); + + auto &BlockResultData = BlockResult->second; + assert(!BlockResultData.Visited && "Should not have been visited yet"); + + BlockResultData.OnStack = true; + Stack.push(DFSStackEntry{ + Direction, combined_pred_begin(B, BlockResultData.FakePredEdges), + combined_pred_end(B, BlockResultData.FakePredEdges), + combined_succ_begin(B, BlockResultData.FakeSuccEdges), + combined_succ_end(B, BlockResultData.FakeSuccEdges), From, B}); +} + +/// \brief Pop an entry from the DFS stack. +void ControlDependenceEquivalence::popDFS(DFSStack &Stack, + const BasicBlock *B) { + assert(Stack.top().Block == B && "Stack top is wrong"); + auto BlockResult = BlockInfo.find(B); + + assert(BlockResult != BlockInfo.end() && "Should have found block data"); + auto &BlockResultData = BlockResult->second; + BlockResultData.OnStack = false; + BlockResultData.Visited = true; + Stack.pop(); +} + +/// \brief Pre-order visitation is only used to generate DFS numbers for the +/// blocks. +void ControlDependenceEquivalence::visitPre(const BasicBlock *B) { + DEBUG(dbgs() << "pre-order visit of block "); + DEBUG(B->printAsOperand(dbgs())); + DEBUG(dbgs() << "\n"); + + BlockInfo[B].DFSNumber = ++DFSNumber; + DEBUG(dbgs() << "Assigned DFS Number " << BlockInfo[B].DFSNumber << "\n"); +} + +void ControlDependenceEquivalence::debugBracketList(const BracketList &BList) { + dbgs() << "{"; + for (auto &Bracket : BList) { + dbgs() << "("; + Bracket.From->printAsOperand(dbgs()); + dbgs() << ","; + Bracket.To->printAsOperand(dbgs()); + dbgs() << ") "; + if (Bracket.Capping) + dbgs() << "[capping]"; + } + dbgs() << "}"; +} + +void ControlDependenceEquivalence::removeBracketsPointingTo( + BlockData &Info, const BasicBlock *B, DFSDirection Direction) { + for (auto BII = Info.BracketIterators.begin(), + BIE = Info.BracketIterators.end(); + BII != BIE;) { + BracketList::iterator &BLI = *BII; + Bracket &BR = *BLI; + if (BR.To == B && BR.Direction != Direction) { + Info.BList.erase(BLI); + BII = Info.BracketIterators.erase(BII); + } else { + ++BII; + } + } +} + +void ControlDependenceEquivalence::visitMid(const BasicBlock *B, + DFSDirection Direction) { + DEBUG(dbgs() << "mid-order visit of block "); + DEBUG(B->printAsOperand(dbgs())); + DEBUG(dbgs() << "\n"); + BlockData &Info = BlockInfo[B]; + BracketList &BList = Info.BList; + // Remove brackets pointing to this node [line:19]. + DEBUG(dbgs() << "Removing brackets pointing to "); + DEBUG(B->printAsOperand(dbgs())); + DEBUG(dbgs() << "\n"); + + // By the time we hit this node, we are guaranteed these iterators will point + // into our list, because it must have been spliced into us. + removeBracketsPointingTo(Info, B, Direction); + + // Potentially introduce artificial dependency from this to start or this to + // end. This case happens when we hit things like unconnected infinite + // loops, or other similar situations. Rather than attempt to connect every + // possible situation to fake start or fake end ahead of time, it's a lot + // easier to just do it here. + if (BList.empty()) { + // The backedge goes to the opposite place of the direction, IE start for + // succs, end for preds + if (Direction == PredDirection) + visitBackedge(B, FakeEnd, PredDirection); + else + visitBackedge(B, FakeStart, SuccDirection); + } + + assert(!BList.empty() && "This should have never happened at this point, we " + "should have hit at least one backedge"); + + // Handle capping brackets. This is a corrected version of the algorithm, from + // "The Static Single Information Form", by C. Scott Ananian. The basic + // notion of capping brackets is as follows: The algorithm depends on being a compact name for the equivalence + // class. Normally, in even unstructured trees (remember, we are really + // working on a DFS spanning tree), the innermost bracket will end up as the + // topmost bracket, so there is no need to store all of the bracket info for + // that edge. However, when you merge two children's bracket sets, it's not + // clear which one is really the innermost anymore, and thus, what the new + // topmost bracket should be. If you choose "the wrong" one, you will end up + // saying things are not cycle equivalent that are. To solve this, capping + // brackets are added, which are the new "topmost" bracket, so that the + // children can be concatenated in any order, and still give the right answer. + // Very few real CFGs depend on capping edges being correct. + + const BasicBlock *Hi0 = nullptr; + if (Info.Backedges.size() > 0) { + auto hi0iter = std::max_element( + Info.Backedges.begin(), Info.Backedges.end(), + [this](const BasicBlock *A, const BasicBlock *B) { + return BlockInfo[A].DFSNumber < BlockInfo[B].DFSNumber; + }); + Hi0 = *hi0iter; + } + const BasicBlock *Hi1 = nullptr; + const BasicBlock *Hi2 = nullptr; + if (Info.Children.size() > 0) { + if (Info.Children.size() == 1) + Hi1 = Info.Children[0]; + else { + // Get the min and the max through our children + auto Hi1Iter = std::min_element( + Info.Children.begin(), Info.Children.end(), + [this](const BasicBlock *A, const BasicBlock *B) { + return BlockInfo[A].DFSNumber < BlockInfo[B].DFSNumber; + }); + auto Hi2Iter = std::max_element( + Info.Children.begin(), Info.Children.end(), + [this](const BasicBlock *A, const BasicBlock *B) { + return BlockInfo[A].DFSNumber < BlockInfo[B].DFSNumber; + }); + Hi1 = *Hi1Iter; + Hi2 = *Hi2Iter; + + // This is the original algorithm's version of this + // // Get the lowest two elements by DFS number, which in turn are the + // // highest two points in the tree. + // std::nth_element(Info.Children.begin(), Info.Children.begin() + 1, + // Info.Children.end(), + // [this](const BasicBlock *A, const BasicBlock *B) { + // return BlockInfo[A].DFSNumber < + // BlockInfo[B].DFSNumber; + // }); + // Hi1 = Info.Children[0]; + // Hi2 = Info.Children[1]; + } + } + if (Hi0 == nullptr) + Info.Hi = Hi1; + else if (Hi1 == nullptr) + Info.Hi = Hi0; + else + Info.Hi = BlockInfo[Hi0].DFSNumber < BlockInfo[Hi1].DFSNumber ? Hi0 : Hi1; + + // This is the original version of the algorithm (line 27) + // if (Hi2 && (Hi0 == nullptr || BlockInfo[Hi2].DFSNumber < + // BlockInfo[Hi0].DFSNumber)) { + if (Info.Children.size() > 1) { + // Push capping backedge onto the bracket list [line:29]. + BlockData &Info = BlockInfo[B]; + BracketList &BList = Info.BList; + auto Place = + BList.insert(BList.end(), Bracket{Direction, 0, 0, B, Hi2, true}); + BlockInfo[Hi2].BracketIterators.push_back(Place); + } + // Capping backedges are specific to the non-representative nodes, so when we + // switch directions (and thus, switch non-representative nodes from N1 to N2, + // above), we need to + // reset for the new children and backedges + Info.Children.clear(); + Info.Backedges.clear(); + + DEBUG(dbgs() << "Bracket list is "); + DEBUG(debugBracketList(BList)); + DEBUG(dbgs() << "\n"); + + // Potentially start a new equivalence class [line:37] + Bracket &Recent = BList.back(); + if (Recent.RecentSize != BList.size()) { + Recent.RecentSize = BList.size(); + Recent.RecentClass = ++ClassNumber; + } + Info.ClassNumber = Recent.RecentClass; + + DEBUG(dbgs() << "Assigned class number is " << Info.ClassNumber << "\n"); +} + +void ControlDependenceEquivalence::visitPost(const BasicBlock *B, + const BasicBlock *ParentBlock, + DFSDirection Direction) { + DEBUG(dbgs() << "post-order visit of block "); + DEBUG(B->printAsOperand(dbgs())); + DEBUG(dbgs() << "\n"); + BlockData &Info = BlockInfo[B]; + BracketList &BList = Info.BList; + // Remove brackets pointing to this node [line:19]. + DEBUG(dbgs() << "Removing brackets pointing to "); + DEBUG(B->printAsOperand(dbgs())); + DEBUG(dbgs() << "\n"); + + // By the time we hit this node, we are guaranteed these iterators will point + // into our list, because it must have been spliced into us. + removeBracketsPointingTo(Info, B, Direction); + + // Propagate bracket list up the DFS tree [line:13]. + if (ParentBlock != nullptr) { + DEBUG(dbgs() << "Splicing bracket into "); + DEBUG(ParentBlock->printAsOperand(dbgs())); + DEBUG(dbgs() << "\n"); + BracketList &ParentBList = BlockInfo[ParentBlock].BList; + ParentBList.splice(ParentBList.end(), BList); + DEBUG(dbgs() << "Parent bracket list is now"); + DEBUG(debugBracketList(ParentBList)); + DEBUG(dbgs() << "\n"); + } +} + +void ControlDependenceEquivalence::visitBackedge(const BasicBlock *From, + const BasicBlock *To, + DFSDirection Direction) { + DEBUG(dbgs() << "visit backedge from block "); + DEBUG(From->printAsOperand(dbgs())); + DEBUG(dbgs() << " to block "); + DEBUG(To->printAsOperand(dbgs())); + DEBUG(dbgs() << "\n"); + + // Push backedge onto the bracket list [line:25]. + BlockData &Info = BlockInfo[From]; + BracketList &BList = Info.BList; + auto Place = + BList.insert(BList.end(), Bracket{Direction, 0, 0, From, To, false}); + BlockInfo[To].BracketIterators.push_back(Place); +} + +FunctionPass *llvm::createControlDependenceEquivalencePass() { + return new ControlDependenceEquivalence(); +} + +namespace { + +class ControlDependenceEquivalencePrinter : public FunctionPass { + const Function *F; + +public: + ControlDependenceEquivalencePrinter() : FunctionPass(ID) { + initializeControlDependenceEquivalencePrinterPass( + *PassRegistry::getPassRegistry()); + } + // run - Calculate control Equivalence for this function + bool runOnFunction(Function &F) override; + + // getAnalysisUsage - Implement the Pass API + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.setPreservesAll(); + } + // releaseMemory - Reset state back to before function was analyzed + void releaseMemory() override { + F = nullptr; + EquivClasses.clear(); + } + + // print - Show contents in human readable format... + void print(raw_ostream &O, const Module * = nullptr) const override; + + static char ID; + std::vector> EquivClasses; +}; +} +char ControlDependenceEquivalencePrinter::ID = 0; + +INITIALIZE_PASS_BEGIN(ControlDependenceEquivalencePrinter, "print-controldep", + "Print Control Dependence of function", true, true) +INITIALIZE_PASS_DEPENDENCY(ControlDependenceEquivalence) +INITIALIZE_PASS_END(ControlDependenceEquivalencePrinter, "print-controldep", + "Print Control Dependence of function", true, true) + +FunctionPass *llvm::createControlDependenceEquivalencePrinter() { + return new ControlDependenceEquivalencePrinter(); +} + +void ControlDependenceEquivalencePrinter::print(raw_ostream &OS, + const Module *) const { + OS << "Equivalence classes: ("; + for (auto &V : EquivClasses) { + OS << "{"; + for (auto &B : V) { + if (B->hasName()) + OS << B->getName(); + else + B->printAsOperand(OS); + if (&B != &V.back()) + OS << ","; + } + OS << "}"; + if (&V != &EquivClasses.back()) + OS << ","; + } + OS << ")\n"; +} + +bool ControlDependenceEquivalencePrinter::runOnFunction(Function &F) { + this->F = &F; + ControlDependenceEquivalence &CD = + getAnalysis(); + // Make a nice map from class number to vectors of bb's + std::map> ClassSets; + for (auto &BB : F) { + unsigned ClassNum = CD.getClassNumber(&BB); + ClassSets[ClassNum].push_back(&BB); + } + + // Sort each vector by bb name, putting named bbs before unnamed ones, then + // add it to the equivalence class list + for (auto &V : ClassSets) { + std::stable_sort(V.second.begin(), V.second.end(), + [](const BasicBlock *A, const BasicBlock *B) { + if (A->hasName() && !B->hasName()) + return true; + if (B->hasName() && !A->hasName()) + return false; + if (!A->hasName() && !B->hasName()) + return false; + return A->getName() < B->getName(); + }); + EquivClasses.push_back(V.second); + } + // Now stable sort by size and then name + std::stable_sort(EquivClasses.begin(), EquivClasses.end(), + [](const std::vector &A, + const std::vector &B) { + if (A.size() < B.size()) + return true; + if (A.size() > B.size()) + return false; + // The same block can't be in multiple equivalence classes, + // so we know that the above sorting means we can just + // compare the first elements + if (A[0]->hasName() && !B[0]->hasName()) + return true; + if (B[0]->hasName() && !A[0]->hasName()) + return false; + return A[0]->getName() < B[0]->getName(); + }); + return false; +} Index: test/Analysis/ControlDependence/testdiamond.ll =================================================================== --- /dev/null +++ test/Analysis/ControlDependence/testdiamond.ll @@ -0,0 +1,15 @@ +; RUN: opt < %s -print-controldep -analyze | FileCheck %s + +target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128" +define void @testdiamond() { +start: + br i1 true, label %same, label %different +same: + br label %returnit +different: + br label %returnit +returnit: + ret void +} +; CHECK: ({different},{same},{returnit,start}) + Index: test/Analysis/ControlDependence/testembeddeddiamond.ll =================================================================== --- /dev/null +++ test/Analysis/ControlDependence/testembeddeddiamond.ll @@ -0,0 +1,20 @@ +; RUN: opt < %s -print-controldep -analyze | FileCheck %s + +target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128" +define void @testembeddeddiamond() { +start: + br i1 true, label %same, label %different +same: + br i1 true, label %samepart1, label %samepart2 +samepart1: + br label %samemergepoint +samepart2: + br label %samemergepoint +samemergepoint: + br label %returnit +different: + br label %returnit +returnit: + ret void +} +; CHECK: ({different},{samepart1},{samepart2},{returnit,start},{same,samemergepoint}) Index: test/Analysis/ControlDependence/testifinloop.ll =================================================================== --- /dev/null +++ test/Analysis/ControlDependence/testifinloop.ll @@ -0,0 +1,24 @@ +; RUN: opt < %s -print-controldep -analyze | FileCheck %s + +target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128" +define void @testifinloop() { +start: + br label %loop +loop: + br label %loopbody +loopbody: + br label %loopif +loopif: + br i1 true, label %looptrue, label %loopfalse +looptrue: + br label %loopifmerge +loopfalse: + br label %loopifmerge +loopifmerge: + br label %looptest +looptest: + br i1 true, label %loop, label %returnit +returnit: + ret void +} +; CHECK: ({loopfalse},{looptrue},{returnit},{start},{loop,loopbody,loopif,loopifmerge,looptest}) Index: test/Analysis/ControlDependence/testloop.ll =================================================================== --- /dev/null +++ test/Analysis/ControlDependence/testloop.ll @@ -0,0 +1,17 @@ +; RUN: opt < %s -print-controldep -analyze | FileCheck %s + +target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128" + +define void @testbasicloop() { +start: + br label %loop +loop: + br label %loopbody +loopbody: + br label %looptest +looptest: + br i1 true, label %loop, label %returnit +returnit: + ret void +} +; CHECK: ({returnit},{start},{loop,loopbody,looptest}) Index: test/Analysis/ControlDependence/testnomergebranch.ll =================================================================== --- /dev/null +++ test/Analysis/ControlDependence/testnomergebranch.ll @@ -0,0 +1,13 @@ +; RUN: opt < %s -print-controldep -analyze | FileCheck %s + +target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128" +define void @testnomergebranch() { +start: + br i1 true, label %same, label %different +same: + ret void +different: + ret void +} +; CHECK: ({different},{same},{start}) + Index: test/Analysis/ControlDependence/teststraightline.ll =================================================================== --- /dev/null +++ test/Analysis/ControlDependence/teststraightline.ll @@ -0,0 +1,13 @@ +; RUN: opt < %s -print-controldep -analyze | FileCheck %s + +target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128" +define void @teststraightline() { +start: + br label %next +next: + br label %returnit +returnit: + ret void +} +; CHECK: ({next,returnit,start}) + Index: test/Analysis/ControlDependence/testunreachableinfiniteloop.ll =================================================================== --- /dev/null +++ test/Analysis/ControlDependence/testunreachableinfiniteloop.ll @@ -0,0 +1,12 @@ +; RUN: opt < %s -print-controldep -analyze | FileCheck %s +target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128" + +; Function Attrs: nounwind uwtable +define hidden void @zot() #0 align 2 { +bb: + br label %bb168 + +bb168: ; preds = %bb168, %bb + br label %bb168 +} +;CHECK: ({bb},{bb168})