1//===-- llvm/Support/DataFlow.h - dataflow as graphs ------------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines specializations of GraphTraits that allows Use-Def and
11// Def-Use relations to be treated as proper graphs for generic algorithms.
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_SUPPORT_DATAFLOW_H
15#define LLVM_SUPPORT_DATAFLOW_H
16
17#include "llvm/User.h"
18#include "llvm/ADT/GraphTraits.h"
19
20namespace llvm {
21
22//===----------------------------------------------------------------------===//
23// Provide specializations of GraphTraits to be able to treat def-use/use-def
24// chains as graphs
25
26template <> struct GraphTraits<const Value*> {
27  typedef const Value NodeType;
28  typedef Value::const_use_iterator ChildIteratorType;
29
30  static NodeType *getEntryNode(const Value *G) {
31    return G;
32  }
33
34  static inline ChildIteratorType child_begin(NodeType *N) {
35    return N->use_begin();
36  }
37
38  static inline ChildIteratorType child_end(NodeType *N) {
39    return N->use_end();
40  }
41};
42
43template <> struct GraphTraits<Value*> {
44  typedef Value NodeType;
45  typedef Value::use_iterator ChildIteratorType;
46
47  static NodeType *getEntryNode(Value *G) {
48    return G;
49  }
50
51  static inline ChildIteratorType child_begin(NodeType *N) {
52    return N->use_begin();
53  }
54
55  static inline ChildIteratorType child_end(NodeType *N) {
56    return N->use_end();
57  }
58};
59
60template <> struct GraphTraits<Inverse<const User*> > {
61  typedef const Value NodeType;
62  typedef User::const_op_iterator ChildIteratorType;
63
64  static NodeType *getEntryNode(Inverse<const User*> G) {
65    return G.Graph;
66  }
67
68  static inline ChildIteratorType child_begin(NodeType *N) {
69    if (const User *U = dyn_cast<User>(N))
70      return U->op_begin();
71    return NULL;
72  }
73
74  static inline ChildIteratorType child_end(NodeType *N) {
75    if(const User *U = dyn_cast<User>(N))
76      return U->op_end();
77    return NULL;
78  }
79};
80
81template <> struct GraphTraits<Inverse<User*> > {
82  typedef Value NodeType;
83  typedef User::op_iterator ChildIteratorType;
84
85  static NodeType *getEntryNode(Inverse<User*> G) {
86    return G.Graph;
87  }
88
89  static inline ChildIteratorType child_begin(NodeType *N) {
90    if (User *U = dyn_cast<User>(N))
91      return U->op_begin();
92    return NULL;
93  }
94
95  static inline ChildIteratorType child_end(NodeType *N) {
96    if (User *U = dyn_cast<User>(N))
97      return U->op_end();
98    return NULL;
99  }
100};
101
102}
103#endif
104