diff --git a/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h b/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h index 7c826780c318..fb6605285156 100644 --- a/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h +++ b/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h @@ -1,89 +1,89 @@ //===- IteratedDominanceFrontier.h - Calculate IDF --------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_IDF_H #define LLVM_ANALYSIS_IDF_H -#include "llvm/IR/CFGDiff.h" +#include "llvm/Support/CFGDiff.h" #include "llvm/Support/GenericIteratedDominanceFrontier.h" namespace llvm { class BasicBlock; namespace IDFCalculatorDetail { /// Specialization for BasicBlock for the optional use of GraphDiff. template struct ChildrenGetterTy { using NodeRef = BasicBlock *; using ChildrenTy = SmallVector; ChildrenGetterTy() = default; ChildrenGetterTy(const GraphDiff *GD) : GD(GD) { assert(GD); } ChildrenTy get(const NodeRef &N); const GraphDiff *GD = nullptr; }; } // end of namespace IDFCalculatorDetail template class IDFCalculator final : public IDFCalculatorBase { public: using IDFCalculatorBase = typename llvm::IDFCalculatorBase; using ChildrenGetterTy = typename IDFCalculatorBase::ChildrenGetterTy; IDFCalculator(DominatorTreeBase &DT) : IDFCalculatorBase(DT) {} IDFCalculator(DominatorTreeBase &DT, const GraphDiff *GD) : IDFCalculatorBase(DT, ChildrenGetterTy(GD)) { assert(GD); } }; using ForwardIDFCalculator = IDFCalculator; using ReverseIDFCalculator = IDFCalculator; //===----------------------------------------------------------------------===// // Implementation. //===----------------------------------------------------------------------===// namespace IDFCalculatorDetail { template typename ChildrenGetterTy::ChildrenTy ChildrenGetterTy::get(const NodeRef &N) { using OrderedNodeTy = typename IDFCalculatorBase::OrderedNodeTy; if (!GD) { auto Children = children(N); return {Children.begin(), Children.end()}; } using SnapShotBBPairTy = std::pair *, OrderedNodeTy>; ChildrenTy Ret; for (const auto &SnapShotBBPair : children({GD, N})) Ret.emplace_back(SnapShotBBPair.second); return Ret; } } // end of namespace IDFCalculatorDetail } // end of namespace llvm #endif diff --git a/llvm/include/llvm/Analysis/MemorySSAUpdater.h b/llvm/include/llvm/Analysis/MemorySSAUpdater.h index 1d34663721e3..39b0e311c7d6 100644 --- a/llvm/include/llvm/Analysis/MemorySSAUpdater.h +++ b/llvm/include/llvm/Analysis/MemorySSAUpdater.h @@ -1,309 +1,309 @@ //===- MemorySSAUpdater.h - Memory SSA Updater-------------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // \file // An automatic updater for MemorySSA that handles arbitrary insertion, // deletion, and moves. It performs phi insertion where necessary, and // automatically updates the MemorySSA IR to be correct. // While updating loads or removing instructions is often easy enough to not // need this, updating stores should generally not be attemped outside this // API. // // Basic API usage: // Create the memory access you want for the instruction (this is mainly so // we know where it is, without having to duplicate the entire set of create // functions MemorySSA supports). // Call insertDef or insertUse depending on whether it's a MemoryUse or a // MemoryDef. // That's it. // // For moving, first, move the instruction itself using the normal SSA // instruction moving API, then just call moveBefore, moveAfter,or moveTo with // the right arguments. // //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/IR/BasicBlock.h" -#include "llvm/IR/CFGDiff.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Module.h" #include "llvm/IR/OperandTraits.h" #include "llvm/IR/Type.h" #include "llvm/IR/Use.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/IR/ValueHandle.h" #include "llvm/IR/ValueMap.h" #include "llvm/Pass.h" +#include "llvm/Support/CFGDiff.h" #include "llvm/Support/Casting.h" #include "llvm/Support/ErrorHandling.h" namespace llvm { class Function; class Instruction; class MemoryAccess; class LLVMContext; class raw_ostream; using ValueToValueMapTy = ValueMap; using PhiToDefMap = SmallDenseMap; using CFGUpdate = cfg::Update; using GraphDiffInvBBPair = std::pair *, Inverse>; class MemorySSAUpdater { private: MemorySSA *MSSA; /// We use WeakVH rather than a costly deletion to deal with dangling pointers. /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards. SmallVector InsertedPHIs; SmallPtrSet VisitedBlocks; SmallSet, 8> NonOptPhis; public: MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} /// Insert a definition into the MemorySSA IR. RenameUses will rename any use /// below the new def block (and any inserted phis). RenameUses should be set /// to true if the definition may cause new aliases for loads below it. This /// is not the case for hoisting or sinking or other forms of code *movement*. /// It *is* the case for straight code insertion. /// For example: /// store a /// if (foo) { } /// load a /// /// Moving the store into the if block, and calling insertDef, does not /// require RenameUses. /// However, changing it to: /// store a /// if (foo) { store b } /// load a /// Where a mayalias b, *does* require RenameUses be set to true. void insertDef(MemoryDef *Def, bool RenameUses = false); void insertUse(MemoryUse *Use, bool RenameUses = false); /// Update the MemoryPhi in `To` following an edge deletion between `From` and /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made. void removeEdge(BasicBlock *From, BasicBlock *To); /// Update the MemoryPhi in `To` to have a single incoming edge from `From`, /// following a CFG change that replaced multiple edges (switch) with a direct /// branch. void removeDuplicatePhiEdgesBetween(const BasicBlock *From, const BasicBlock *To); /// Update MemorySSA when inserting a unique backedge block for a loop. void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader, BasicBlock *LoopPreheader, BasicBlock *BackedgeBlock); /// Update MemorySSA after a loop was cloned, given the blocks in RPO order, /// the exit blocks and a 1:1 mapping of all blocks and instructions /// cloned. This involves duplicating all defs and uses in the cloned blocks /// Updating phi nodes in exit block successors is done separately. void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks, ArrayRef ExitBlocks, const ValueToValueMapTy &VM, bool IgnoreIncomingWithNoClones = false); // Block BB was fully or partially cloned into its predecessor P1. Map // contains the 1:1 mapping of instructions cloned and VM[BB]=P1. void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM); /// Update phi nodes in exit block successors following cloning. Exit blocks /// that were not cloned don't have additional predecessors added. void updateExitBlocksForClonedLoop(ArrayRef ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT); void updateExitBlocksForClonedLoop( ArrayRef ExitBlocks, ArrayRef> VMaps, DominatorTree &DT); /// Apply CFG updates, analogous with the DT edge updates. void applyUpdates(ArrayRef Updates, DominatorTree &DT); /// Apply CFG insert updates, analogous with the DT edge updates. void applyInsertUpdates(ArrayRef Updates, DominatorTree &DT); void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where); /// `From` block was spliced into `From` and `To`. There is a CFG edge from /// `From` to `To`. Move all accesses from `From` to `To` starting at /// instruction `Start`. `To` is newly created BB, so empty of /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of /// `To` with MPhi nodes need to update incoming block. /// |------| |------| /// | From | | From | /// | | |------| /// | | || /// | | => \/ /// | | |------| <- Start /// | | | To | /// |------| |------| void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start); /// `From` block was merged into `To`. There is a CFG edge from `To` to /// `From`.`To` still branches to `From`, but all instructions were moved and /// `From` is now an empty block; `From` is about to be deleted. Move all /// accesses from `From` to `To` starting at instruction `Start`. `To` may /// have multiple successors, `From` has a single predecessor. `From` may have /// successors with MPhi nodes, replace their incoming block with `To`. /// |------| |------| /// | To | | To | /// |------| | | /// || => | | /// \/ | | /// |------| | | <- Start /// | From | | | /// |------| |------| void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start); /// A new empty BasicBlock (New) now branches directly to Old. Some of /// Old's predecessors (Preds) are now branching to New instead of Old. /// If New is the only predecessor, move Old's Phi, if present, to New. /// Otherwise, add a new Phi in New with appropriate incoming values, and /// update the incoming values in Old's Phi node too, if present. void wireOldPredecessorsToNewImmediatePredecessor( BasicBlock *Old, BasicBlock *New, ArrayRef Preds, bool IdenticalEdgesWereMerged = true); // The below are utility functions. Other than creation of accesses to pass // to insertDef, and removeAccess to remove accesses, you should generally // not attempt to update memoryssa yourself. It is very non-trivial to get // the edge cases right, and the above calls already operate in near-optimal // time bounds. /// Create a MemoryAccess in MemorySSA at a specified point in a block, /// with a specified clobbering definition. /// /// Returns the new MemoryAccess. /// This should be called when a memory instruction is created that is being /// used to replace an existing memory instruction. It will *not* create PHI /// nodes, or verify the clobbering definition. The insertion place is used /// solely to determine where in the memoryssa access lists the instruction /// will be placed. The caller is expected to keep ordering the same as /// instructions. /// It will return the new MemoryAccess. /// Note: If a MemoryAccess already exists for I, this function will make it /// inaccessible and it *must* have removeMemoryAccess called on it. MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point); /// Create a MemoryAccess in MemorySSA before or after an existing /// MemoryAccess. /// /// Returns the new MemoryAccess. /// This should be called when a memory instruction is created that is being /// used to replace an existing memory instruction. It will *not* create PHI /// nodes, or verify the clobbering definition. /// /// Note: If a MemoryAccess already exists for I, this function will make it /// inaccessible and it *must* have removeMemoryAccess called on it. MemoryUseOrDef *createMemoryAccessBefore(Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt); MemoryUseOrDef *createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt); /// Remove a MemoryAccess from MemorySSA, including updating all /// definitions and uses. /// This should be called when a memory instruction that has a MemoryAccess /// associated with it is erased from the program. For example, if a store or /// load is simply erased (not replaced), removeMemoryAccess should be called /// on the MemoryAccess for that store/load. void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false); /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists. /// This should be called when an instruction (load/store) is deleted from /// the program. void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) { if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) removeMemoryAccess(MA, OptimizePhis); } /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted. /// Assumption we make here: all uses of deleted defs and phi must either /// occur in blocks about to be deleted (thus will be deleted as well), or /// they occur in phis that will simply lose an incoming value. /// Deleted blocks still have successor info, but their predecessor edges and /// Phi nodes may already be updated. Instructions in DeadBlocks should be /// deleted after this call. void removeBlocks(const SmallSetVector &DeadBlocks); /// Instruction I will be changed to an unreachable. Remove all accesses in /// I's block that follow I (inclusive), and update the Phis in the blocks' /// successors. void changeToUnreachable(const Instruction *I); /// Conditional branch BI is changed or replaced with an unconditional branch /// to `To`. Update Phis in BI's successors to remove BI's BB. void changeCondBranchToUnconditionalTo(const BranchInst *BI, const BasicBlock *To); /// Get handle on MemorySSA. MemorySSA* getMemorySSA() const { return MSSA; } private: // Move What before Where in the MemorySSA IR. template void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where); // Move all memory accesses from `From` to `To` starting at `Start`. // Restrictions apply, see public wrappers of this method. void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start); MemoryAccess *getPreviousDef(MemoryAccess *); MemoryAccess *getPreviousDefInBlock(MemoryAccess *); MemoryAccess * getPreviousDefFromEnd(BasicBlock *, DenseMap> &); MemoryAccess * getPreviousDefRecursive(BasicBlock *, DenseMap> &); MemoryAccess *recursePhi(MemoryAccess *Phi); MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi); template MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); void tryRemoveTrivialPhis(ArrayRef UpdatedPHIs); void fixupDefs(const SmallVectorImpl &); // Clone all uses and defs from BB to NewBB given a 1:1 map of all // instructions and blocks cloned, and a map of MemoryPhi : Definition // (MemoryAccess Phi or Def). VMap maps old instructions to cloned // instructions and old blocks to cloned blocks. MPhiMap, is created in the // caller of this private method, and maps existing MemoryPhis to new // definitions that new MemoryAccesses must point to. These definitions may // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such, // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses // may be MemoryPhis or MemoryDefs and not MemoryUses. // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that // the clone involved simplifications that may have: (1) turned a MemoryUse // into an instruction that MemorySSA has no representation for, or (2) turned // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no // representation for. No other cases are supported. void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB, const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap, bool CloneWasSimplified = false); template void privateUpdateExitBlocksForClonedLoop(ArrayRef ExitBlocks, Iter ValuesBegin, Iter ValuesEnd, DominatorTree &DT); void applyInsertUpdates(ArrayRef, DominatorTree &DT, const GraphDiff *GD); }; } // end namespace llvm #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H diff --git a/llvm/include/llvm/IR/CFGDiff.h b/llvm/include/llvm/Support/CFGDiff.h similarity index 98% rename from llvm/include/llvm/IR/CFGDiff.h rename to llvm/include/llvm/Support/CFGDiff.h index c50db0de79a3..94734ce70e02 100644 --- a/llvm/include/llvm/IR/CFGDiff.h +++ b/llvm/include/llvm/Support/CFGDiff.h @@ -1,251 +1,250 @@ //===- CFGDiff.h - Define a CFG snapshot. -----------------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file defines specializations of GraphTraits that allows generic // algorithms to see a different snapshot of a CFG. // //===----------------------------------------------------------------------===// -#ifndef LLVM_IR_CFGDIFF_H -#define LLVM_IR_CFGDIFF_H +#ifndef LLVM_SUPPORT_CFGDIFF_H +#define LLVM_SUPPORT_CFGDIFF_H #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" -#include "llvm/IR/CFG.h" #include "llvm/Support/CFGUpdate.h" #include "llvm/Support/type_traits.h" #include #include #include // Two booleans are used to define orders in graphs: // InverseGraph defines when we need to reverse the whole graph and is as such // also equivalent to applying updates in reverse. // InverseEdge defines whether we want to change the edges direction. E.g., for // a non-inversed graph, the children are naturally the successors when // InverseEdge is false and the predecessors when InverseEdge is true. // We define two base clases that call into GraphDiff, one for successors // (CFGSuccessors), where InverseEdge is false, and one for predecessors // (CFGPredecessors), where InverseEdge is true. // FIXME: Further refactoring may merge the two base classes into a single one // templated / parametrized on using succ_iterator/pred_iterator and false/true // for the InverseEdge. // CFGViewChildren and CFGViewPredecessors, both can be parametrized to // consider the graph inverted or not (i.e. InverseGraph). Successors // implicitly has InverseEdge = false and Predecessors implicitly has // InverseEdge = true (see calls to GraphDiff methods in there). The GraphTraits // instantiations that follow define the value of InverseGraph. // GraphTraits instantiations: // - GraphDiff is equivalent to InverseGraph = false // - GraphDiff> is equivalent to InverseGraph = true // - second pair item is BasicBlock *, then InverseEdge = false (so it inherits // from CFGViewChildren). // - second pair item is Inverse, then InverseEdge = true (so it // inherits from CFGViewPredecessors). // The 4 GraphTraits are as follows: // 1. std::pair *, BasicBlock *>> : // CFGViewChildren // Regular CFG, children means successors, InverseGraph = false, // InverseEdge = false. // 2. std::pair> *, BasicBlock *>> : // CFGViewChildren // Reverse the graph, get successors but reverse-apply updates, // InverseGraph = true, InverseEdge = false. // 3. std::pair *, Inverse>> : // CFGViewPredecessors // Regular CFG, reverse edges, so children mean predecessors, // InverseGraph = false, InverseEdge = true. // 4. std::pair> *, Inverse> // : CFGViewPredecessors // Reverse the graph and the edges, InverseGraph = true, InverseEdge = true. namespace llvm { // GraphDiff defines a CFG snapshot: given a set of Update, provide // utilities to skip edges marked as deleted and return a set of edges marked as // newly inserted. The current diff treats the CFG as a graph rather than a // multigraph. Added edges are pruned to be unique, and deleted edges will // remove all existing edges between two blocks. template class GraphDiff { using UpdateMapType = SmallDenseMap>; struct EdgesInsertedDeleted { UpdateMapType Succ; UpdateMapType Pred; }; // Store Deleted edges on position 0, and Inserted edges on position 1. EdgesInsertedDeleted Edges[2]; // By default, it is assumed that, given a CFG and a set of updates, we wish // to apply these updates as given. If UpdatedAreReverseApplied is set, the // updates will be applied in reverse: deleted edges are considered re-added // and inserted edges are considered deleted when returning children. bool UpdatedAreReverseApplied; // Using a singleton empty vector for all node requests with no // children. SmallVector Empty; // Keep the list of legalized updates for a deterministic order of updates // when using a GraphDiff for incremental updates in the DominatorTree. // The list is kept in reverse to allow popping from end. SmallVector, 4> LegalizedUpdates; void printMap(raw_ostream &OS, const UpdateMapType &M) const { for (auto Pair : M) for (auto Child : Pair.second) { OS << "("; Pair.first->printAsOperand(OS, false); OS << ", "; Child->printAsOperand(OS, false); OS << ") "; } OS << "\n"; } public: GraphDiff() : UpdatedAreReverseApplied(false) {} GraphDiff(ArrayRef> Updates, bool ReverseApplyUpdates = false) { cfg::LegalizeUpdates(Updates, LegalizedUpdates, InverseGraph, /*ReverseResultOrder=*/true); // The legalized updates are stored in reverse so we can pop_back when doing // incremental updates. for (auto U : LegalizedUpdates) { unsigned IsInsert = (U.getKind() == cfg::UpdateKind::Insert) == !ReverseApplyUpdates; Edges[IsInsert].Succ[U.getFrom()].push_back(U.getTo()); Edges[IsInsert].Pred[U.getTo()].push_back(U.getFrom()); } UpdatedAreReverseApplied = ReverseApplyUpdates; } auto getLegalizedUpdates() const { return make_range(LegalizedUpdates.begin(), LegalizedUpdates.end()); } unsigned getNumLegalizedUpdates() const { return LegalizedUpdates.size(); } cfg::Update popUpdateForIncrementalUpdates() { assert(!LegalizedUpdates.empty() && "No updates to apply!"); auto U = LegalizedUpdates.pop_back_val(); unsigned IsInsert = (U.getKind() == cfg::UpdateKind::Insert) == !UpdatedAreReverseApplied; auto &SuccList = Edges[IsInsert].Succ[U.getFrom()]; assert(SuccList.back() == U.getTo()); SuccList.pop_back(); if (SuccList.empty()) Edges[IsInsert].Succ.erase(U.getFrom()); auto &PredList = Edges[IsInsert].Pred[U.getTo()]; assert(PredList.back() == U.getFrom()); PredList.pop_back(); if (PredList.empty()) Edges[IsInsert].Pred.erase(U.getTo()); return U; } bool ignoreChild(const NodePtr BB, NodePtr EdgeEnd, bool InverseEdge) const { // Used to filter nullptr in clang. if (EdgeEnd == nullptr) return true; auto &DeleteChildren = (InverseEdge != InverseGraph) ? Edges[0].Pred : Edges[0].Succ; auto It = DeleteChildren.find(BB); if (It == DeleteChildren.end()) return false; auto &EdgesForBB = It->second; return llvm::find(EdgesForBB, EdgeEnd) != EdgesForBB.end(); } iterator_range::const_iterator> getAddedChildren(const NodePtr BB, bool InverseEdge) const { auto &InsertChildren = (InverseEdge != InverseGraph) ? Edges[1].Pred : Edges[1].Succ; auto It = InsertChildren.find(BB); if (It == InsertChildren.end()) return make_range(Empty.begin(), Empty.end()); return make_range(It->second.begin(), It->second.end()); } void print(raw_ostream &OS) const { OS << "===== GraphDiff: CFG edge changes to create a CFG snapshot. \n" "===== (Note: notion of children/inverse_children depends on " "the direction of edges and the graph.)\n"; OS << "Children to insert:\n\t"; printMap(OS, Edges[1].Succ); OS << "Children to delete:\n\t"; printMap(OS, Edges[0].Succ); OS << "Inverse_children to insert:\n\t"; printMap(OS, Edges[1].Pred); OS << "Inverse_children to delete:\n\t"; printMap(OS, Edges[0].Pred); OS << "\n"; } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) LLVM_DUMP_METHOD void dump() const { print(dbgs()); } #endif }; template > struct CFGViewChildren { using DataRef = const GraphDiff *; using NodeRef = std::pair; template static auto makeChildRange(Range &&R, DataRef DR) { using Iter = WrappedPairNodeDataIterator(R).begin()), NodeRef, DataRef>; return make_range(Iter(R.begin(), DR), Iter(R.end(), DR)); } static auto children(NodeRef N) { // filter iterator init: auto R = make_range(GT::child_begin(N.second), GT::child_end(N.second)); // This lambda is copied into the iterators and persists to callers, ensure // captures are by value or otherwise have sufficient lifetime. auto First = make_filter_range(makeChildRange(R, N.first), [N](NodeRef C) { return !C.first->ignoreChild(N.second, C.second, InverseEdge); }); // new inserts iterator init: auto InsertVec = N.first->getAddedChildren(N.second, InverseEdge); auto Second = makeChildRange(InsertVec, N.first); auto CR = concat(First, Second); // concat_range contains references to other ranges, returning it would // leave those references dangling - the iterators contain // other iterators by value so they're safe to return. return make_range(CR.begin(), CR.end()); } static auto child_begin(NodeRef N) { return children(N).begin(); } static auto child_end(NodeRef N) { return children(N).end(); } using ChildIteratorType = decltype(child_end(std::declval())); }; template struct GraphTraits *, T>> : CFGViewChildren {}; template struct GraphTraits *, Inverse>> : CFGViewChildren, B, true> {}; } // end namespace llvm -#endif // LLVM_IR_CFGDIFF_H +#endif // LLVM_SUPPORT_CFGDIFF_H diff --git a/llvm/include/llvm/module.modulemap b/llvm/include/llvm/module.modulemap index 1709ee6e047c..4121bb0f131b 100644 --- a/llvm/include/llvm/module.modulemap +++ b/llvm/include/llvm/module.modulemap @@ -1,423 +1,422 @@ module LLVM_Analysis { requires cplusplus umbrella "Analysis" module * { export * } // This is intended for (repeated) textual inclusion. textual header "Analysis/TargetLibraryInfo.def" textual header "Analysis/VecFuncs.def" } module LLVM_AsmParser { requires cplusplus umbrella "AsmParser" module * { export * } } // A module covering CodeGen/ and Target/. These are intertwined // and codependent, and thus notionally form a single module. module LLVM_Backend { requires cplusplus module CodeGen { umbrella "CodeGen" module * { export * } // Exclude these; they're intended to be included into only a single // translation unit (or none) and aren't part of this module. exclude header "CodeGen/LinkAllAsmWriterComponents.h" exclude header "CodeGen/LinkAllCodegenComponents.h" // These are intended for (repeated) textual inclusion. textual header "CodeGen/DIEValue.def" } } // FIXME: Make this as a submodule of LLVM_Backend again. // Doing so causes a linker error in clang-format. module LLVM_Backend_Target { umbrella "Target" module * { export * } } module LLVM_Bitcode { requires cplusplus umbrella "Bitcode" module * { export * } } module LLVM_Bitstream { requires cplusplus umbrella "Bitstream" module * { export * } } module LLVM_BinaryFormat { requires cplusplus umbrella "BinaryFormat" module * { export * } textual header "BinaryFormat/Dwarf.def" textual header "BinaryFormat/DynamicTags.def" textual header "BinaryFormat/MachO.def" textual header "BinaryFormat/MinidumpConstants.def" textual header "BinaryFormat/ELFRelocs/AArch64.def" textual header "BinaryFormat/ELFRelocs/AMDGPU.def" textual header "BinaryFormat/ELFRelocs/ARM.def" textual header "BinaryFormat/ELFRelocs/ARC.def" textual header "BinaryFormat/ELFRelocs/AVR.def" textual header "BinaryFormat/ELFRelocs/BPF.def" textual header "BinaryFormat/ELFRelocs/Hexagon.def" textual header "BinaryFormat/ELFRelocs/i386.def" textual header "BinaryFormat/ELFRelocs/Lanai.def" textual header "BinaryFormat/ELFRelocs/Mips.def" textual header "BinaryFormat/ELFRelocs/MSP430.def" textual header "BinaryFormat/ELFRelocs/PowerPC64.def" textual header "BinaryFormat/ELFRelocs/PowerPC.def" textual header "BinaryFormat/ELFRelocs/RISCV.def" textual header "BinaryFormat/ELFRelocs/Sparc.def" textual header "BinaryFormat/ELFRelocs/SystemZ.def" textual header "BinaryFormat/ELFRelocs/x86_64.def" textual header "BinaryFormat/WasmRelocs.def" textual header "BinaryFormat/MsgPack.def" } module LLVM_Config { requires cplusplus umbrella "Config" extern module LLVM_Extern_Config_Def "module.extern.modulemap" module * { export * } } module LLVM_DebugInfo { requires cplusplus module DIContext { header "DebugInfo/DIContext.h" export * } } module LLVM_DebugInfo_DWARF { requires cplusplus umbrella "DebugInfo/DWARF" module * { export * } } module LLVM_DebugInfo_PDB { requires cplusplus umbrella "DebugInfo/PDB" module * { export * } // Separate out this subdirectory; it's an optional component that depends on // a separate library which might not be available. // // FIXME: There should be a better way to specify this. exclude header "DebugInfo/PDB/DIA/DIADataStream.h" exclude header "DebugInfo/PDB/DIA/DIAEnumDebugStreams.h" exclude header "DebugInfo/PDB/DIA/DIAEnumFrameData.h" exclude header "DebugInfo/PDB/DIA/DIAEnumInjectedSources.h" exclude header "DebugInfo/PDB/DIA/DIAEnumLineNumbers.h" exclude header "DebugInfo/PDB/DIA/DIAEnumSectionContribs.h" exclude header "DebugInfo/PDB/DIA/DIAEnumSourceFiles.h" exclude header "DebugInfo/PDB/DIA/DIAEnumSymbols.h" exclude header "DebugInfo/PDB/DIA/DIAEnumTables.h" exclude header "DebugInfo/PDB/DIA/DIAFrameData.h" exclude header "DebugInfo/PDB/DIA/DIAInjectedSource.h" exclude header "DebugInfo/PDB/DIA/DIALineNumber.h" exclude header "DebugInfo/PDB/DIA/DIARawSymbol.h" exclude header "DebugInfo/PDB/DIA/DIASectionContrib.h" exclude header "DebugInfo/PDB/DIA/DIASession.h" exclude header "DebugInfo/PDB/DIA/DIASourceFile.h" exclude header "DebugInfo/PDB/DIA/DIASupport.h" exclude header "DebugInfo/PDB/DIA/DIATable.h" exclude header "DebugInfo/PDB/DIA/DIAUtils.h" } module LLVM_DebugInfo_PDB_DIA { requires cplusplus umbrella "DebugInfo/PDB/DIA" module * { export * } } module LLVM_DebugInfo_MSF { requires cplusplus umbrella "DebugInfo/MSF" module * { export * } } module LLVM_DebugInfo_CodeView { requires cplusplus umbrella "DebugInfo/CodeView" module * { export * } // These are intended for (repeated) textual inclusion. textual header "DebugInfo/CodeView/CodeViewRegisters.def" textual header "DebugInfo/CodeView/CodeViewTypes.def" textual header "DebugInfo/CodeView/CodeViewSymbols.def" } module LLVM_DWARFLinker { requires cplusplus umbrella "DWARFLinker" module * { export * } } module LLVM_ExecutionEngine { requires cplusplus umbrella "ExecutionEngine" module * { export * } // Exclude this; it's an optional component of the ExecutionEngine. exclude header "ExecutionEngine/OProfileWrapper.h" // Exclude these; they're intended to be included into only a single // translation unit (or none) and aren't part of this module. exclude header "ExecutionEngine/MCJIT.h" exclude header "ExecutionEngine/Interpreter.h" exclude header "ExecutionEngine/OrcMCJITReplacement.h" // FIXME: These exclude directives were added as a workaround for // and should be removed once it is fixed. exclude header "ExecutionEngine/Orc/OrcRemoteTargetRPCAPI.h" exclude header "ExecutionEngine/Orc/OrcRemoteTargetClient.h" exclude header "ExecutionEngine/Orc/OrcRemoteTargetServer.h" exclude header "ExecutionEngine/Orc/RemoteObjectLayer.h" // Exclude headers from LLVM_OrcSupport. exclude header "ExecutionEngine/Orc/OrcError.h" exclude header "ExecutionEngine/Orc/RPC/RPCUtils.h" exclude header "ExecutionEngine/Orc/RPC/RPCSerialization.h" exclude header "ExecutionEngine/Orc/RPC/RawByteChannel.h" } // Orc utilities that don't depend only on Support (not ExecutionEngine or // IR). This is a workaround for ExecutionEngine's broken layering, and will // be removed in the future. module LLVM_OrcSupport { requires cplusplus header "ExecutionEngine/Orc/OrcError.h" header "ExecutionEngine/Orc/RPC/RPCUtils.h" header "ExecutionEngine/Orc/RPC/RPCSerialization.h" header "ExecutionEngine/Orc/RPC/RawByteChannel.h" export * } module LLVM_Pass { module Pass { // PassSupport.h and PassAnalysisSupport.h are made available only through // Pass.h. header "Pass.h" header "PassSupport.h" header "PassAnalysisSupport.h" export * } module PassRegistry { header "PassRegistry.h" export * } module InitializePasses { header "InitializePasses.h" export * } } module LLVM_intrinsic_gen { requires cplusplus // Delay building the modules containing dependencies to Attributes.h and // Intrinsics.h because they need to be generated by tablegen first. // Attributes.h module IR_Argument { header "IR/Argument.h" export * } module IR_Attributes { header "IR/Attributes.h" extern module LLVM_Extern_IR_Attributes_Gen "module.extern.modulemap" export * } module IR_CallSite { header "IR/CallSite.h" export * } module IR_ConstantFolder { header "IR/ConstantFolder.h" export * } module IR_GlobalVariable { header "IR/GlobalVariable.h" export * } module IR_NoFolder { header "IR/NoFolder.h" export * } module IRBuilderFolder { header "IR/IRBuilderFolder.h" export * } module IR_Module { header "IR/Module.h" export * } module IR_ModuleSummaryIndex { header "IR/ModuleSummaryIndex.h" export * } module IR_ModuleSummaryIndexYAML { header "IR/ModuleSummaryIndexYAML.h" export * } module IR_Function { header "IR/Function.h" export * } module IR_InstrTypes { header "IR/InstrTypes.h" export * } module IR_Instructions { header "IR/Instructions.h" export * } // Intrinsics.h module IR_CFG { header "IR/CFG.h" export * } - module IR_CFGDiff { header "IR/CFGDiff.h" export * } module IR_ConstantRange { header "IR/ConstantRange.h" export * } module IR_Dominators { header "IR/Dominators.h" export * } module Analysis_PostDominators { header "Analysis/PostDominators.h" export * } module Analysis_DomTreeUpdater { header "Analysis/DomTreeUpdater.h" export * } module IR_IRBuilder { header "IR/IRBuilder.h" export * } module IR_MatrixBuilder { header "IR/MatrixBuilder.h" export * } module IR_PassManager { header "IR/PassManager.h" export * } module IR_PassManagerImpl { header "IR/PassManagerImpl.h" export * } module IR_PredIteratorCache { header "IR/PredIteratorCache.h" export * } module IR_Verifier { header "IR/Verifier.h" export * } module IR_InstIterator { header "IR/InstIterator.h" export * } module IR_InstVisitor { header "IR/InstVisitor.h" export * } module IR_Intrinsics { header "IR/Intrinsics.h" extern module LLVM_Extern_IR_Intricsics_Gen "module.extern.modulemap" extern module LLVM_Extern_IR_Intrinsics_Enum "module.extern.modulemap" export * } module IR_IntrinsicInst { header "IR/IntrinsicInst.h" export * } module IR_PatternMatch { header "IR/PatternMatch.h" export * } module IR_SafepointIRVerifier { header "IR/SafepointIRVerifier.h" export * } module IR_Statepoint { header "IR/Statepoint.h" export * } export * } module LLVM_IR { requires cplusplus umbrella "IR" module * { export * } // These are intended for (repeated) textual inclusion. textual header "IR/ConstrainedOps.def" textual header "IR/DebugInfoFlags.def" textual header "IR/Instruction.def" textual header "IR/Metadata.def" textual header "IR/FixedMetadataKinds.def" textual header "IR/Value.def" textual header "IR/VPIntrinsics.def" textual header "IR/RuntimeLibcalls.def" } module LLVM_IRReader { requires cplusplus umbrella "IRReader" module * { export * } } module LLVM_LineEditor { requires cplusplus umbrella "LineEditor" module * { export * } } module LLVM_LTO { requires cplusplus umbrella "LTO" module * { export * } } module LLVM_MC { requires cplusplus umbrella "MC" module * { export * } } // Used by llvm-tblgen module LLVM_MC_TableGen { requires cplusplus module MC_LaneBitmask { header "MC/LaneBitmask.h" export * } module MC_FixedLenDisassembler { header "MC/MCFixedLenDisassembler.h" export * } module MC_InstrItineraries { header "MC/MCInstrItineraries.h" export * } module MC_Schedule { header "MC/MCSchedule.h" export * } module MC_SubtargetFeature { header "MC/SubtargetFeature.h" export * } } module LLVM_Object { requires cplusplus umbrella "Object" module * { export * } } module LLVM_Option { requires cplusplus umbrella "Option" module * { export * } } module LLVM_ProfileData { requires cplusplus umbrella "ProfileData" module * { export * } textual header "ProfileData/InstrProfData.inc" } // FIXME: Mislayered? module LLVM_Support_TargetRegistry { requires cplusplus header "Support/TargetRegistry.h" export * } module LLVM_TableGen { requires cplusplus umbrella "TableGen" module * { export * } } module LLVM_Transforms { requires cplusplus umbrella "Transforms" module * { export * } } extern module LLVM_Extern_Utils_DataTypes "module.extern.modulemap" // A module covering ADT/ and Support/. These are intertwined and // codependent, and notionally form a single module. module LLVM_Utils { module ADT { requires cplusplus umbrella "ADT" module * { export * } } module Support { requires cplusplus umbrella "Support" module * { export * } // Exclude this; it should only be used on Windows. exclude header "Support/Windows/WindowsSupport.h" // Exclude these; they are fundamentally non-modular. exclude header "Support/PluginLoader.h" exclude header "Support/Solaris/sys/regset.h" // These are intended for textual inclusion. textual header "Support/ARMTargetParser.def" textual header "Support/AArch64TargetParser.def" textual header "Support/TargetOpcodes.def" textual header "Support/X86TargetParser.def" } // This part of the module is usable from both C and C++ code. module ConvertUTF { header "Support/ConvertUTF.h" export * } } // This is used for a $src == $build compilation. Otherwise we use // LLVM_Support_DataTypes_Build, defined in a module map that is // copied into the build area. module LLVM_Support_DataTypes_Src { header "llvm/Support/DataTypes.h" export * } module LLVM_WindowsManifest { requires cplusplus umbrella "WindowsManifest" module * { export * } }