#include "llvm/Analysis/LazyCallGraph.h"#include "llvm/ADT/ArrayRef.h"#include "llvm/ADT/STLExtras.h"#include "llvm/ADT/ScopeExit.h"#include "llvm/ADT/Sequence.h"#include "llvm/ADT/SmallPtrSet.h"#include "llvm/ADT/SmallVector.h"#include "llvm/ADT/iterator_range.h"#include "llvm/Analysis/TargetLibraryInfo.h"#include "llvm/Config/llvm-config.h"#include "llvm/IR/CallSite.h"#include "llvm/IR/Function.h"#include "llvm/IR/GlobalVariable.h"#include "llvm/IR/Instruction.h"#include "llvm/IR/Module.h"#include "llvm/IR/PassManager.h"#include "llvm/Support/Casting.h"#include "llvm/Support/Compiler.h"#include "llvm/Support/Debug.h"#include "llvm/Support/GraphWriter.h"#include "llvm/Support/raw_ostream.h"#include <algorithm>#include <cassert>#include <cstddef>#include <iterator>#include <string>#include <tuple>#include <utility>
Go to the source code of this file.
Macros | |
| #define | DEBUG_TYPE "lcg" |
Functions | |
| static void | addEdge (SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK) |
| static bool | isKnownLibFunction (Function &F, TargetLibraryInfo &TLI) |
| template<typename SCCT , typename PostorderSequenceT , typename SCCIndexMapT , typename ComputeSourceConnectedSetCallableT , typename ComputeTargetConnectedSetCallableT > | |
| static iterator_range< typename PostorderSequenceT::iterator > | updatePostorderSequenceForEdgeInsertion (SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs, SCCIndexMapT &SCCIndices, ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet, ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) |
| Generic helper that updates a postorder sequence of SCCs for a potentially cycle-introducing edge insertion. More... | |
| static void | printNode (raw_ostream &OS, LazyCallGraph::Node &N) |
| static void | printSCC (raw_ostream &OS, LazyCallGraph::SCC &C) |
| static void | printRefSCC (raw_ostream &OS, LazyCallGraph::RefSCC &C) |
| static void | printNodeDOT (raw_ostream &OS, LazyCallGraph::Node &N) |
Macro Definition Documentation
◆ DEBUG_TYPE
| #define DEBUG_TYPE "lcg" |
Definition at line 41 of file LazyCallGraph.cpp.
Function Documentation
◆ addEdge()
|
static |
Definition at line 63 of file LazyCallGraph.cpp.
References assert(), C, llvm::LazyCallGraph::Edge::Call, Callee, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::SmallVectorImpl< T >::emplace_back(), F(), G, getName(), llvm::LazyCallGraph::Node::getName(), I, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, LLVM_DUMP_METHOD, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::LazyCallGraph::Edge::Ref, and llvm::LazyCallGraph::visitReferences().
Referenced by llvm::ScheduleDAGMI::addMutation(), getFilename(), and llvm::LazyCallGraph::LazyCallGraph().
◆ isKnownLibFunction()
|
static |
Definition at line 147 of file LazyCallGraph.cpp.
References llvm::TargetLibraryInfo::getLibFunc(), llvm::Value::getName(), and llvm::TargetLibraryInfo::isFunctionVectorizable().
Referenced by llvm::LazyCallGraph::LazyCallGraph().
◆ printNode()
|
static |
Definition at line 1732 of file LazyCallGraph.cpp.
References E, llvm::LazyCallGraph::Node::getFunction(), llvm::Value::getName(), and llvm::LazyCallGraph::Node::populate().
Referenced by llvm::LazyCallGraphPrinterPass::run().
◆ printNodeDOT()
|
static |
Definition at line 1779 of file LazyCallGraph.cpp.
References E, llvm::DOT::EscapeString(), llvm::LazyCallGraph::Node::getFunction(), llvm::Value::getName(), Name, and llvm::LazyCallGraph::Node::populate().
Referenced by llvm::LazyCallGraphDOTPrinterPass::run().
◆ printRefSCC()
|
static |
Definition at line 1749 of file LazyCallGraph.cpp.
References printSCC(), Size, and llvm::size().
Referenced by llvm::LazyCallGraphPrinterPass::run().
◆ printSCC()
|
static |
Definition at line 1741 of file LazyCallGraph.cpp.
References N, Size, and llvm::size().
Referenced by printRefSCC().
◆ updatePostorderSequenceForEdgeInsertion()
|
static |
Generic helper that updates a postorder sequence of SCCs for a potentially cycle-introducing edge insertion.
A postorder sequence of SCCs of a directed graph has one fundamental property: all deges in the DAG of SCCs point "up" the sequence. That is, all edges in the SCC DAG point to prior SCCs in the sequence.
This routine both updates a postorder sequence and uses that sequence to compute the set of SCCs connected into a cycle. It should only be called to insert a "downward" edge which will require changing the sequence to restore it to a postorder.
When inserting an edge from an earlier SCC to a later SCC in some postorder sequence, all of the SCCs which may be impacted are in the closed range of those two within the postorder sequence. The algorithm used here to restore the state is as follows:
1) Starting from the source SCC, construct a set of SCCs which reach the source SCC consisting of just the source SCC. Then scan toward the target SCC in postorder and for each SCC, if it has an edge to an SCC in the set, add it to the set. Otherwise, the source SCC is not a successor, move it in the postorder sequence to immediately before the source SCC, shifting the source SCC and all SCCs in the set one position toward the target SCC. Stop scanning after processing the target SCC. 2) If the source SCC is now past the target SCC in the postorder sequence, and thus the new edge will flow toward the start, we are done. 3) Otherwise, starting from the target SCC, walk all edges which reach an SCC between the source and the target, and add them to the set of connected SCCs, then recurse through them. Once a complete set of the SCCs the target connects to is known, hoist the remaining SCCs between the source and the target to be above the target. Note that there is no need to process the source SCC, it is already known to connect. 4) At this point, all of the SCCs in the closed range between the source SCC and the target SCC in the postorder sequence are connected, including the target SCC and the source SCC. Inserting the edge from the source SCC to the target SCC will form a cycle out of precisely these SCCs. Thus we can merge all of the SCCs in this closed range into a single SCC.
This process has various important properties:
- Only mutates the SCCs when adding the edge actually changes the SCC structure.
- Never mutates SCCs which are unaffected by the change.
- Updates the postorder sequence to correctly satisfy the postorder constraint after the edge is inserted.
- Only reorders SCCs in the closed postorder sequence from the source to the target, so easy to bound how much has changed even in the ordering.
- Big-O is the number of edges in the closed postorder range of SCCs from source to target.
This helper routine, in addition to updating the postorder sequence itself will also update a map from SCCs to indices within that sequence.
The sequence and the map must operate on pointers to the SCC type.
Two callbacks must be provided. The first computes the subset of SCCs in the postorder closed range from the source to the target which connect to the source SCC via some (transitive) set of edges. The second computes the subset of the same range which the target SCC connects to via some (transitive) set of edges. Both callbacks should populate the set argument provided.
Definition at line 446 of file LazyCallGraph.cpp.
References assert(), C, llvm::SmallPtrSetImplBase::clear(), llvm::SmallPtrSetImpl< PtrType >::count(), and llvm::make_range().
Referenced by llvm::LazyCallGraph::RefSCC::insertIncomingRefEdge(), and llvm::LazyCallGraph::RefSCC::switchInternalEdgeToCall().
