damain.cc

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