Index: include/llvm/Analysis/ControlDependence.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ControlDependence.h @@ -0,0 +1,229 @@ +//===- ControlDependence.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. +// +//===----------------------------------------------------------------------===// +// 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_CONTROLDEPENDENCE_H +#define LLVM_ANALYSIS_CONTROLDEPENDENCE_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; + +// 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 ControlDependence : public FunctionPass { +public: + ControlDependence() : FunctionPass(ID), Computed(false) { + initializeControlDependencePass(*PassRegistry::getPassRegistry()); + } + static char ID; + + // run - Calculate control Equivalence for this function + bool runOnFunction(Function &F) override; + + // getAnalysisUsage - Implement the Pass API + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesAll(); + } + // releaseMemory - Reset state back to before function was analyzed + void releaseMemory() override; + // print - Show contents in human readable format... + void print(raw_ostream &O, const Module * = nullptr) const override; + + 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; + }; + typedef SmallVector FakeEdgeListType; + + // We use combined iterators to allow fake and real edges to be next to each + // other. 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; + // Indicates Block participates in DFS walk. + bool Participates; + // 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; + BlockData() + : ClassNumber(0), DFSNumber(0), Visited(false), OnStack(false), + Participates(true) {} + ~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 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); + void visitBackedge(const BasicBlock *, const BasicBlock *, DFSDirection); + + void pushDFS(DFSStack &, const BasicBlock *, const BasicBlock *, + DFSDirection); + void popDFS(DFSStack &, const BasicBlock *); + void debugBracketList(const BracketList &); + + unsigned DFSNumber; + unsigned ClassNumber; + SmallDenseMap BlockInfo; + bool Computed; + const BasicBlock *FakeEnd; +}; +} + +#endif Index: include/llvm/Analysis/Passes.h =================================================================== --- include/llvm/Analysis/Passes.h +++ include/llvm/Analysis/Passes.h @@ -166,6 +166,20 @@ // FunctionPass *createMemDerefPrinter(); + //===--------------------------------------------------------------------===// + // + // createControlDependencePass - This pass collects control dependence info + // information + // + FunctionPass *createControlDependencePass(); + + //===--------------------------------------------------------------------===// + // + // createControlDependencePrinter - This pass collects control dependence info + // information and prints it with -print-controldeps + // + FunctionPass *createControlDependencePrinter(); + } #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 initializeControlDependencePass(PassRegistry&); +void initializeControlDependencePrinterPass(PassRegistry&); void initializeMachineCopyPropagationPass(PassRegistry&); void initializeCostModelAnalysisPass(PassRegistry&); void initializeCorrelatedValuePropagationPass(PassRegistry&); Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h +++ include/llvm/LinkAllPasses.h @@ -68,6 +68,8 @@ (void) llvm::createStructurizeCFGPass(); (void) llvm::createConstantMergePass(); (void) llvm::createConstantPropagationPass(); + (void) llvm::createControlDependencePass(); + (void) llvm::createControlDependencePrinter(); (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); + initializeControlDependencePass(Registry); + initializeControlDependencePrinterPass(Registry); initializeDependenceAnalysisPass(Registry); initializeDelinearizationPass(Registry); initializeDominanceFrontierPass(Registry); Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -18,6 +18,7 @@ CostModel.cpp CodeMetrics.cpp ConstantFolding.cpp + ControlDependence.cpp Delinearization.cpp DependenceAnalysis.cpp DomPrinter.cpp Index: lib/Analysis/ControlDependence.cpp =================================================================== --- /dev/null +++ lib/Analysis/ControlDependence.cpp @@ -0,0 +1,424 @@ +//===- ControlDependence.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. +// +//===----------------------------------------------------------------------===// +// This implements a pass to compute control dependence equivalence classes +// +//===----------------------------------------------------------------------===// +#include "llvm/Analysis/ControlDependence.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; +char ControlDependence::ID = 0; +#define DEBUG_TYPE "controlequiv" +INITIALIZE_PASS(ControlDependence, "controldep", + "Control Dependence Construction", true, true); + +// 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 ControlDependence::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, connect exiting blocks to the fake end, and + // then connect the fake end and the real start. We then start the DFS walk + // from the fake exit block instead of a fake start block + FakeEnd = BasicBlock::Create(F.getContext(), "FakeEnd"); + BlockInfo[FakeEnd].FakeSuccEdges.push_back(&F.getEntryBlock()); + BlockInfo[&F.getEntryBlock()].FakePredEdges.push_back(FakeEnd); + + // BlockInfo.resize(F.size()); + for (auto &B : F) { + BlockData &Info = BlockInfo[&B]; + // If this is a reverse-unreachable block, we don't care about it + if (pred_empty(&B) && &B != &F.getEntryBlock()) { + Info.Participates = false; + } + // If there are no successors, 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 ControlDependence::releaseMemory() { + if (Computed) { + BlockInfo.clear(); + delete FakeEnd; + } + Computed = false; +} + +// print - Show contents in human readable format... +void ControlDependence::print(raw_ostream &O, const Module *M) const {} + +// 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 ControlDependence::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 + if (Entry.Direction == PredDirection) { + // Pred direction + if (Entry.Pred != Entry.PredEnd) { + const BasicBlock *Pred = *Entry.Pred; + ++(Entry.Pred); + BlockData &PredData = BlockInfo.find(Pred)->second; + if (!PredData.Participates) + continue; + if (PredData.Visited) + continue; + // If it's on the stack, we've found a backedge, otherwise, push it + // and preorder-visit + if (PredData.OnStack) { + DEBUG(dbgs() << "Maybe visit pred backedge\n"); + if (Pred != Entry.ParentBlock) + visitBackedge(B, Pred, PredDirection); + } else { + pushDFS(Stack, Pred, B, PredDirection); + visitPre(Pred); + } + continue; + } + // Swap directions to successors + if (Entry.Succ != Entry.SuccEnd) { + Entry.Direction = SuccDirection; + visitMid(B, PredDirection); + continue; + } + } + + if (Entry.Direction == SuccDirection) { + if (Entry.Succ != Entry.SuccEnd) { + const BasicBlock *Succ = *Entry.Succ; + ++(Entry.Succ); + BlockData &SuccData = BlockInfo.find(Succ)->second; + if (!SuccData.Participates) + continue; + if (SuccData.Visited) + continue; + // If it's on the stack, we've found a backedge, otherwise, push it + // and preorder-visit + if (SuccData.OnStack) { + DEBUG(dbgs() << "Maybe visit succ backedge\n"); + if (Succ != Entry.ParentBlock) + visitBackedge(B, Succ, SuccDirection); + } else { + pushDFS(Stack, Succ, B, SuccDirection); + visitPre(Succ); + } + continue; + } + // Swap directions to predecessors + if (Entry.Pred != Entry.PredEnd) { + Entry.Direction = PredDirection; + visitMid(B, SuccDirection); + 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); + } +} + +void ControlDependence::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"); + assert(BlockResultData.Participates && + "Somehow visited a node that doesn't participate"); + + 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}); +} +void ControlDependence::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(); +} + +void ControlDependence::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 ControlDependence::debugBracketList(const BracketList &BList) { + dbgs() << "{"; + for (auto &Bracket : BList) { + dbgs() << "("; + Bracket.From->printAsOperand(dbgs()); + dbgs() << ","; + Bracket.To->printAsOperand(dbgs()); + dbgs() << ") "; + } + dbgs() << "}"; +} + +void ControlDependence::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. + + for (auto BII = Info.BracketIterators.begin(), + BIE = Info.BracketIterators.end(); + BII != BIE;) { + if ((*BII)->To == B && (*BII)->Direction != Direction) { + Info.BList.erase(*BII); + BII = Info.BracketIterators.erase(BII); + } else + ++BII; + } + + // We should have at least hit the artificial edge connecting end and start as + // a backedge, which would have started a bracket list that would have + // propagated up to this point, so this should not be possible. + assert(!BList.empty() && "This should have never happened at this point, we " + "should have hit at least one backedge"); + + 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 ControlDependence::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. + for (auto BII = Info.BracketIterators.begin(), + BIE = Info.BracketIterators.end(); + BII != BIE;) { + if ((*BII)->To == B && (*BII)->Direction != Direction) { + Info.BList.erase(*BII); + BII = Info.BracketIterators.erase(BII); + } else + ++BII; + } + + // 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; + // TODO + ParentBList.splice(ParentBList.end(), BList); + DEBUG(dbgs() << "Parent bracket list is now"); + DEBUG(debugBracketList(ParentBList)); + DEBUG(dbgs() << "\n"); + } +} + +void ControlDependence::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}); + BlockInfo[To].BracketIterators.push_back(Place); +} +FunctionPass *llvm::createControlDependencePass() { + return new ControlDependence(); +} + +namespace { + +class ControlDependencePrinter : public FunctionPass { + const Function *F; + +public: + ControlDependencePrinter() : FunctionPass(ID) { + initializeControlDependencePrinterPass(*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 ControlDependencePrinter::ID = 0; + +INITIALIZE_PASS_BEGIN(ControlDependencePrinter, "print-controldep", + "Print Control Dependence of function", true, true) +INITIALIZE_PASS_DEPENDENCY(ControlDependence) +INITIALIZE_PASS_END(ControlDependencePrinter, "print-controldep", + "Print Control Dependence of function", true, true) + +FunctionPass *llvm::createControlDependencePrinter() { + return new ControlDependencePrinter(); +} + +void ControlDependencePrinter::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 ControlDependencePrinter::runOnFunction(Function &F) { + this->F = &F; + ControlDependence &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; +}