damain.cc

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <iostream>
   4 #include <map>
   5
   6 #include "version.h"
   7
   8 #include <isa/yaml.h>
   9 #include <isa/pdg.h>
  10 #include "da.h"
  11
  12 #include <isl/set.h>
  13 #include <isl/map.h>
  14
  15 #include "da_options.h"
  16
  17 using pdg::PDG;
  18 using namespace std;
  19 using namespace da;
  20
  21 /* Return an input array that is otherwise a copy of a */
  22 pdg::array *input_copy(PDG *pdg, pdg::array *a)
  23 {
  24         pdg::array *copy = new pdg::array;
  25         copy->id = a->id;
  26         copy->name = a->name;
  27         copy->dims = a->dims;
  28         copy->element_type = a->element_type;
  29         copy->type = pdg::array::input;
  30         pdg->arrays.push_back(copy);
  31         return copy;
  32 }
  33
  34 /* Determine the type (input/output/temp) of each array in the program.
  35  * An array is considered
  36  *      - input, if some element is read without being written
  37  *        If so, the corresponding access are changed to read from
  38  *        a copy of the array marked as input.  The original array
  39  *        is then marked temporary or output, as appropriate.
  40  *      - output, if some element is written without being subsequently read
  41  *        or overwritten
  42  *      - temporary, otherwhise
  43  */
  44 void determine_array_types(PDG *pdg, bool verbose)
  45 {
  46         struct isl_ctx *ctx = pdg->get_isl_ctx();
  47         isl_printer *prn;
  48         std::map<pdg::node *, isl_set *> exposed;
  49         std::map<pdg::array *, pdg::array *> shadow_input;
  50
  51         unsigned nparam = pdg->params.size();
  52         for (int j = 0; j < pdg->arrays.size(); ++j)
  53                 pdg->arrays[j]->type = pdg::array::temp;
  54         for (int j = 0; j < pdg->dependences.size(); ++j) {
  55                 pdg::dependence *dep = pdg->dependences[j];
  56                 pdg::array *a = dep->array;
  57                 if (dep->type != pdg::dependence::uninitialized)
  58                         continue;
  59                 if (shadow_input.find(a) == shadow_input.end())
  60                         shadow_input[a] = input_copy(pdg, a);
  61                 dep->array = shadow_input[a];
  62         }
  63         for (int i = 0; i < pdg->nodes.size(); ++i) {
  64                 pdg::node *node = pdg->nodes[i];
  65                 pdg::statement *s = node->statement;
  66
  67                 isl_set *context = pdg->get_context_isl_set();
  68                 exposed[node] = node->source->get_isl_set(ctx);
  69                 exposed[node] = isl_set_intersect_params(exposed[node],
  70                                                             context);
  71         }
  72         for (int i = 0; i < pdg->dependences.size(); ++i) {
  73                 pdg::dependence *dep = pdg->dependences[i];
  74                 if (dep->type != pdg::dependence::flow &&
  75                     dep->type != pdg::dependence::output)
  76                         continue;
  77                 pdg::node *node = dep->from;
  78                 isl_map *rel = dep->relation->get_isl_map(ctx);
  79                 exposed[node] = isl_set_subtract(exposed[node],
  80                                                 isl_map_domain(rel));
  81         }
  82         for (int i = 0; i < pdg->nodes.size(); ++i) {
  83                 pdg::node *node = pdg->nodes[i];
  84                 pdg::statement *s = node->statement;
  85
  86                 int is_empty = isl_set_is_empty(exposed[node]);
  87                 assert(is_empty >= 0);
  88                 if (verbose && !is_empty) {
  89                         fprintf(stderr,
  90                                 "exposed write domain for node %d, line %d\n",
  91                                 node->nr, node->statement->line);
  92                         prn = isl_printer_to_file(ctx, stderr);
  93                         prn = isl_printer_set_indent(prn, 4);
  94                         prn = isl_printer_print_set(prn, exposed[node]);
  95                         prn = isl_printer_end_line(prn);
  96                         isl_printer_free(prn);
  97                 }
  98                 isl_set_free(exposed[node]);
  99                 if (is_empty)
 100                         continue;
 101
 102                 for (int j = 0; j < s->accesses.size(); ++j) {
 103                         if (s->accesses[j]->type != pdg::access::write)
 104                                 continue;
 105                         pdg::array *a = s->accesses[j]->array;
 106                         a->type = pdg::array::output;
 107                 }
 108         }
 109 }
 110
 111 int main(int argc, char * argv[])
 112 {
 113     isl_ctx *ctx = isl_ctx_alloc();
 114     FILE *in = stdin, *out = stdout;
 115     PDG *pdg;
 116     struct options *options = options_new_with_defaults();
 117
 118     argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 119
 120     if (options->input && strcmp(options->input, "-")) {
 121         in = fopen(options->input, "r");
 122         assert(in);
 123         if (!options->output) {
 124             int len = strlen(options->input);
 125             if (len > 5 && !strcmp(options->input+len-5, ".yaml"))
 126                 len -= 5;
 127             options->output = (char *)malloc(len+9+1);
 128             strncpy(options->output, options->input, len);
 129             strcpy(options->output+len, "_da.yaml");
 130         }
 131     }
 132
 133     if (options->array_types)
 134         options->types |= TYPE_FLOW;
 135
 136     pdg = PDG::Load(in, ctx);
 137     assert(pdg);
 138
 139     compute_filter_sources(pdg);
 140     for (int i = 0; i < pdg->arrays.size(); ++i) {
 141         if (options->types & (TYPE_FLOW))
 142             find_deps(pdg, pdg->arrays[i], flow);
 143         if (options->types & (TYPE_ANTI))
 144             find_deps(pdg, pdg->arrays[i], anti);
 145         if (options->types & (TYPE_REUSE_PAIR))
 146             find_deps(pdg, pdg->arrays[i], reuse_pair);
 147         if (options->types & (TYPE_OUTPUT))
 148             find_deps(pdg, pdg->arrays[i], output);
 149     }
 150
 151     if (options->array_types)
 152         determine_array_types(pdg, options->verbose);
 153
 154     if (options->output && strcmp(options->output, "-")) {
 155         out = fopen(options->output, "w");
 156         assert(out);
 157     }
 158
 159     pdg->add_history_line("da", argc, argv);
 160
 161     pdg->Dump(out);
 162     pdg->free();
 163     delete pdg;
 164
 165     options_free(options);
 166     isl_ctx_free(ctx);
 167
 168     return 0;
 169 }