aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/DataStructure/DependenceGraph.h
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/DataStructure/DependenceGraph.h')
-rw-r--r--lib/Analysis/DataStructure/DependenceGraph.h255
1 files changed, 0 insertions, 255 deletions
diff --git a/lib/Analysis/DataStructure/DependenceGraph.h b/lib/Analysis/DataStructure/DependenceGraph.h
deleted file mode 100644
index 520b008528..0000000000
--- a/lib/Analysis/DataStructure/DependenceGraph.h
+++ /dev/null
@@ -1,255 +0,0 @@
-//===- DependenceGraph.h - Dependence graph for a function ------*- C++ -*-===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file provides an explicit representation for the dependence graph
-// of a function, with one node per instruction and one edge per dependence.
-// Dependences include both data and control dependences.
-//
-// Each dep. graph node (class DepGraphNode) keeps lists of incoming and
-// outgoing dependence edges.
-//
-// Each dep. graph edge (class Dependence) keeps a pointer to one end-point
-// of the dependence. This saves space and is important because dep. graphs
-// can grow quickly. It works just fine because the standard idiom is to
-// start with a known node and enumerate the dependences to or from that node.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DEPENDENCEGRAPH_H
-#define LLVM_ANALYSIS_DEPENDENCEGRAPH_H
-
-#include "llvm/ADT/hash_map"
-#include <cassert>
-#include <iosfwd>
-#include <utility>
-#include <vector>
-
-namespace llvm {
-
-class Instruction;
-class Function;
-class Dependence;
-class DepGraphNode;
-class DependenceGraph;
-
-//----------------------------------------------------------------------------
-/// enum DependenceType - The standard data dependence types
-///
-enum DependenceType {
- NoDependence = 0x0,
- TrueDependence = 0x1,
- AntiDependence = 0x2,
- OutputDependence = 0x4,
- ControlDependence = 0x8, // from a terminator to some other instr.
- IncomingFlag = 0x10 // is this an incoming or outgoing dep?
-};
-
-//----------------------------------------------------------------------------
-/// Dependence Class - A representation of a simple (non-loop-related)
-/// dependence.
-///
-class Dependence {
- DepGraphNode* toOrFromNode;
- unsigned char depType;
-
-public:
- Dependence(DepGraphNode* toOrFromN, DependenceType type, bool isIncoming)
- : toOrFromNode(toOrFromN),
- depType(type | (isIncoming? IncomingFlag : 0x0)) { }
-
- Dependence(const Dependence& D) : toOrFromNode(D.toOrFromNode),
- depType(D.depType) { }
-
- bool operator==(const Dependence& D) const {
- return toOrFromNode == D.toOrFromNode && depType == D.depType;
- }
-
- /// Get information about the type of dependence.
- ///
- unsigned getDepType() const {
- return depType;
- }
-
- /// Get source or sink depending on what type of node this is!
- ///
- DepGraphNode* getSrc() {
- assert(depType & IncomingFlag); return toOrFromNode;
- }
- const DepGraphNode* getSrc() const {
- assert(depType & IncomingFlag); return toOrFromNode;
- }
-
- DepGraphNode* getSink() {
- assert(! (depType & IncomingFlag)); return toOrFromNode;
- }
- const DepGraphNode* getSink() const {
- assert(! (depType & IncomingFlag)); return toOrFromNode;
- }
-
- /// Debugging support methods
- ///
- void print(std::ostream &O) const;
-
- // Default constructor: Do not use directly except for graph builder code
- //
- Dependence() : toOrFromNode(NULL), depType(NoDependence) { }
-};
-
-#ifdef SUPPORTING_LOOP_DEPENDENCES
-struct LoopDependence: public Dependence {
- DependenceDirection dir;
- int distance;
- short level;
- LoopInfo* enclosingLoop;
-};
-#endif
-
-
-//----------------------------------------------------------------------------
-/// DepGraphNode Class - A representation of a single node in a dependence
-/// graph, corresponding to a single instruction.
-///
-class DepGraphNode {
- Instruction* instr;
- std::vector<Dependence> inDeps;
- std::vector<Dependence> outDeps;
- friend class DependenceGraph;
-
- typedef std::vector<Dependence>:: iterator iterator;
- typedef std::vector<Dependence>::const_iterator const_iterator;
-
- iterator inDepBegin() { return inDeps.begin(); }
- const_iterator inDepBegin() const { return inDeps.begin(); }
- iterator inDepEnd() { return inDeps.end(); }
- const_iterator inDepEnd() const { return inDeps.end(); }
-
- iterator outDepBegin() { return outDeps.begin(); }
- const_iterator outDepBegin() const { return outDeps.begin(); }
- iterator outDepEnd() { return outDeps.end(); }
- const_iterator outDepEnd() const { return outDeps.end(); }
-
-public:
- DepGraphNode(Instruction& I) : instr(&I) { }
-
- Instruction& getInstr() { return *instr; }
- const Instruction& getInstr() const { return *instr; }
-
- /// Debugging support methods
- ///
- void print(std::ostream &O) const;
-};
-
-
-//----------------------------------------------------------------------------
-/// DependenceGraph Class - A representation of a dependence graph for a
-/// procedure. The primary query operation here is to look up a DepGraphNode for
-/// a particular instruction, and then use the in/out dependence iterators
-/// for the node.
-///
-class DependenceGraph {
- DependenceGraph(const DependenceGraph&); // DO NOT IMPLEMENT
- void operator=(const DependenceGraph&); // DO NOT IMPLEMENT
-
- typedef hash_map<Instruction*, DepGraphNode*> DepNodeMapType;
- typedef DepNodeMapType:: iterator map_iterator;
- typedef DepNodeMapType::const_iterator const_map_iterator;
-
- DepNodeMapType depNodeMap;
-
- inline DepGraphNode* getNodeInternal(Instruction& inst,
- bool createIfMissing = false) {
- map_iterator I = depNodeMap.find(&inst);
- if (I == depNodeMap.end())
- return (!createIfMissing)? NULL :
- depNodeMap.insert(
- std::make_pair(&inst, new DepGraphNode(inst))).first->second;
- else
- return I->second;
- }
-
-public:
- typedef std::vector<Dependence>:: iterator iterator;
- typedef std::vector<Dependence>::const_iterator const_iterator;
-
-public:
- DependenceGraph() { }
- ~DependenceGraph();
-
- /// Get the graph node for an instruction. There will be one if and
- /// only if there are any dependences incident on this instruction.
- /// If there is none, these methods will return NULL.
- ///
- DepGraphNode* getNode(Instruction& inst, bool createIfMissing = false) {
- return getNodeInternal(inst, createIfMissing);
- }
- const DepGraphNode* getNode(const Instruction& inst) const {
- return const_cast<DependenceGraph*>(this)
- ->getNodeInternal(const_cast<Instruction&>(inst));
- }
-
- iterator inDepBegin(DepGraphNode& T) {
- return T.inDeps.begin();
- }
- const_iterator inDepBegin (const DepGraphNode& T) const {
- return T.inDeps.begin();
- }
-
- iterator inDepEnd(DepGraphNode& T) {
- return T.inDeps.end();
- }
- const_iterator inDepEnd(const DepGraphNode& T) const {
- return T.inDeps.end();
- }
-
- iterator outDepBegin(DepGraphNode& F) {
- return F.outDeps.begin();
- }
- const_iterator outDepBegin(const DepGraphNode& F) const {
- return F.outDeps.begin();
- }
-
- iterator outDepEnd(DepGraphNode& F) {
- return F.outDeps.end();
- }
- const_iterator outDepEnd(const DepGraphNode& F) const {
- return F.outDeps.end();
- }
-
- /// Debugging support methods
- ///
- void print(const Function& func, std::ostream &O) const;
-
-public:
- /// AddSimpleDependence - adding and modifying the dependence graph.
- /// These should to be used only by dependence analysis implementations.
- ///
- void AddSimpleDependence(Instruction& fromI, Instruction& toI,
- DependenceType depType) {
- DepGraphNode* fromNode = getNodeInternal(fromI, /*create*/ true);
- DepGraphNode* toNode = getNodeInternal(toI, /*create*/ true);
- fromNode->outDeps.push_back(Dependence(toNode, depType, false));
- toNode-> inDeps. push_back(Dependence(fromNode, depType, true));
- }
-
-#ifdef SUPPORTING_LOOP_DEPENDENCES
- // This interface is a placeholder to show what information is needed.
- // It will probably change when it starts being used.
- void AddLoopDependence(Instruction& fromI,
- Instruction& toI,
- DependenceType depType,
- DependenceDirection dir,
- int distance,
- short level,
- LoopInfo* enclosingLoop);
-#endif // SUPPORTING_LOOP_DEPENDENCES
-};
-
-} // End llvm namespace
-
-#endif
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-26 19:01:29 +0000