dependence_graph.h

   1 #ifndef DEPENDENCE_GRAPH_H
   2 #define DEPENDENCE_GRAPH_H
   3
   4 #include <vector>
   5 #include <isl/map.h>
   6 #include <isl/set.h>
   7 #include <isa/pdg.h>
   8
   9 struct computation;
  10
  11 struct edge {
  12         computation             *source;
  13         isl_map                 *relation;
  14         unsigned                 pos;
  15         enum type {
  16                 normal,
  17                 expansion,
  18         } type;
  19
  20         edge() : type(normal) { }
  21         ~edge() {
  22                 isl_map_free(relation);
  23         }
  24
  25         void dump(void);
  26 };
  27
  28 struct computation {
  29         isl_set                 *domain;
  30         const char              *operation;
  31         unsigned                 arity;
  32         int                      location;
  33         int                      dim;
  34         unsigned                 input : 1;
  35         unsigned                 is_expanded : 1;
  36         computation             *original;
  37
  38         std::vector<edge *>      edges;
  39
  40         computation() : input(0), is_expanded(0), original(NULL), dim(-1) {}
  41
  42         ~computation() {
  43                 for (int i = 0; i < edges.size(); ++i)
  44                         delete edges[i];
  45                 isl_set_free(domain);
  46                 free((char *)operation);
  47         }
  48
  49         bool has_same_source(computation *other) const {
  50                 if (this == other)
  51                         return 1;
  52                 if (this->original == other)
  53                         return 1;
  54                 if (this == other->original)
  55                         return 1;
  56                 if (this->original && this->original == other->original)
  57                         return 1;
  58                 return 0;
  59         }
  60
  61         bool is_input() const {
  62                 return input;
  63         }
  64
  65         bool is_copy() const {
  66                 return !input && !is_expanded &&
  67                        !strcmp(operation, "") && arity == 1;
  68         }
  69
  70         void dump(void);
  71 };
  72
  73 struct input_array : computation {
  74         input_array(const char *name, __isl_take isl_space *dims) {
  75                 dim = isl_space_dim(dims, isl_dim_set);
  76                 if (*name)
  77                         dims = isl_space_set_tuple_name(dims,
  78                                                         isl_dim_set, name);
  79                 domain = isl_set_universe(dims);
  80                 operation = strdup(name);
  81                 arity = 0;
  82                 location = -1;
  83                 input = 1;
  84         }
  85 };
  86
  87 struct dependence_graph {
  88         isl_set                         *context;
  89         std::vector<char *>              output_arrays;
  90         std::vector<unsigned>            output_array_dims;
  91         std::vector<computation *>       vertices;
  92         std::vector<computation *>       input_computations;
  93         computation                     *out;
  94
  95         dependence_graph() : out(NULL), context(NULL) {}
  96         ~dependence_graph() {
  97                 isl_set_free(context);
  98                 for (int i = 0; i < output_arrays.size(); ++i)
  99                         free(output_arrays[i]);
 100                 for (int i = 0; i < vertices.size(); ++i)
 101                         delete vertices[i];
 102                 delete out;
 103         }
 104
 105         void splice(computation *comp, edge *e);
 106         computation *split_comp(computation *comp, edge *e);
 107         void split_edges(computation *comp_orig, computation *comp_dup);
 108         void split_edges(computation *comp,
 109                          computation *comp_orig, computation *comp_dup);
 110         computation *associative_node(edge **e,
 111                 const std::vector<const char *> &associative);
 112         void flatten_associative_operators(
 113                 const std::vector<const char *> &associative);
 114         void dump(void);
 115 };
 116
 117 dependence_graph *pdg_to_dg(pdg::PDG *pdg, unsigned out_dim,
 118         __isl_take isl_set *context);
 119
 120 #endif