dependence_graph.h

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