source/ident.c

   1
   2    /*--------------------------------------------------------------------+
   3     |                              Clay                                  |
   4     |--------------------------------------------------------------------|
   5     |                            ident.c                                 |
   6     |--------------------------------------------------------------------|
   7     |                    First version: 03/04/2012                       |
   8     +--------------------------------------------------------------------+
   9
  10  +--------------------------------------------------------------------------+
  11  |  / __)(  )    /__\ ( \/ )                                                |
  12  | ( (__  )(__  /(__)\ \  /         Chunky Loop Alteration wizardrY         |
  13  |  \___)(____)(__)(__)(__)                                                 |
  14  +--------------------------------------------------------------------------+
  15  | Copyright (C) 2012 University of Paris-Sud                               |
  16  |                                                                          |
  17  | This library is free software; you can redistribute it and/or modify it  |
  18  | under the terms of the GNU Lesser General Public License as published by |
  19  | the Free Software Foundation; either version 2.1 of the License, or      |
  20  | (at your option) any later version.                                      |
  21  |                                                                          |
  22  | This library is distributed in the hope that it will be useful but       |
  23  | WITHOUT ANY WARRANTY; without even the implied warranty of               |
  24  | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser  |
  25  | General Public License for more details.                                 |
  26  |                                                                          |
  27  | You should have received a copy of the GNU Lesser General Public License |
  28  | along with this software; if not, write to the Free Software Foundation, |
  29  | Inc., 51 Franklin Street, Fifth Floor,                                   |
  30  | Boston, MA  02110-1301  USA                                              |
  31  |                                                                          |
  32  | Clay, the Chunky Loop Alteration wizardrY                                |
  33  | Written by Joel Poudroux, joel.poudroux@u-psud.fr                        |
  34  +--------------------------------------------------------------------------*/
  35
  36 #include <stdio.h>
  37 #include <stdlib.h>
  38 #include <string.h>
  39
  40 #include <osl/scop.h>
  41 #include <osl/extensions/arrays.h>
  42
  43 #include <clay/macros.h>
  44 #include <clay/array.h>
  45 #include <clay/beta.h>
  46 #include <clay/betatree.h>
  47 #include <clay/util.h>
  48 #include <clay/ident.h>
  49
  50
  51 /**
  52  * clay_ident_find_stmt function:
  53  * Search the corresponding beta of the `ident'th statement
  54  * \param[in] scop
  55  * \param[in] ident       >= 0
  56  * \return
  57  */
  58 clay_array_p clay_ident_find_stmt(osl_scop_p scop, int ident) {
  59
  60   if (ident < 0)
  61     return NULL;
  62
  63   osl_statement_p sout;
  64   clay_array_p beta;
  65   clay_array_p beta_last;
  66   int i = 0;
  67
  68   beta_last = clay_array_malloc(); // empty beta
  69   beta = clay_beta_next(scop->statement, beta_last, &sout);
  70
  71   while (i < ident) {
  72     clay_array_free(beta_last);
  73     beta_last = beta;
  74     beta = clay_beta_next(scop->statement, beta_last, &sout);
  75
  76     if (beta == NULL) {
  77       clay_array_free(beta_last);
  78       return NULL;
  79     }
  80
  81     i++;
  82   }
  83
  84   clay_array_free(beta_last);
  85
  86   return beta;
  87 }
  88
  89
  90 /**
  91  * clay_ident_find_iterator function:
  92  * Search the first loop which has the `iter' in original iterator
  93  * \param[in] scop
  94  * \param[in] iter       name of the original iterator we want to search
  95  * \return
  96  */
  97 clay_array_p clay_ident_find_iterator(osl_scop_p scop, char *iter) {
  98
  99   osl_statement_p sout;
 100   clay_array_p beta;
 101   clay_array_p beta_last;
 102   int i = -1;
 103
 104   beta_last = clay_array_malloc(); // empty beta
 105   beta = clay_beta_next(scop->statement, beta_last, &sout);
 106
 107   if (beta == NULL) {
 108     clay_array_free(beta_last);
 109     return NULL;
 110   }
 111
 112   while ((i = clay_util_statement_find_iterator(sout, iter)) == -1) {
 113     clay_array_free(beta_last);
 114     beta_last = beta;
 115     beta = clay_beta_next(scop->statement, beta_last, &sout);
 116
 117     if (beta == NULL) {
 118       clay_array_free(beta_last);
 119       return NULL;
 120     }
 121   }
 122
 123   clay_array_free(beta_last);
 124
 125   if (i == -1) {
 126     clay_array_free(beta);
 127   } else {
 128     beta->size = i+1;
 129   }
 130
 131   return beta;
 132 }
 133
 134
 135 /**
 136  * clay_ident_find_loop function:
 137  * Search the `ident'th loop
 138  * /!\ Assume that all nodes are sorted in ascending order
 139  * \param[in] scop
 140  * \param[in] ident       >= 1
 141  * \return
 142  */
 143 clay_array_p clay_ident_find_loop(clay_betatree_p tree, int ident) {
 144   int *count;
 145   clay_array_p beta;
 146
 147   CLAY_malloc(count, int*, sizeof(int));
 148   *count = 0;
 149
 150   beta = clay_ident_find_loop_aux(tree, ident, count);
 151   free(count);
 152
 153   return beta;
 154 }
 155
 156
 157 /**
 158  * clay_ident_find_loop_aux function:
 159  * Required by clay_ident_find_loop
 160  */
 161 clay_array_p clay_ident_find_loop_aux(clay_betatree_p tree, int ident,
 162                                       int *count) {
 163
 164   if (tree->nbnodes == 0 || ident < 0)
 165     return NULL;
 166
 167   if (*count > ident) {
 168     free(count);
 169     return NULL;
 170   }
 171
 172   int i;
 173   clay_betatree_p node;
 174   clay_array_p beta;
 175   clay_array_p beta_rest;
 176
 177   beta = clay_array_malloc();
 178
 179   // if we are not at the root (the root has no value)
 180   if (*count != 0)
 181     clay_array_add(beta, tree->value);
 182
 183   // OK the beta is found
 184   if (*count == ident)
 185     return beta;
 186
 187   (*count)++;
 188
 189   // TODO : we need to sort the nodes before
 190   // No problems for now because when we create a tree from a scop, the nodes
 191   // are sorted by ascending order
 192   for (i = 0 ; i < tree->nbnodes ; i++) {
 193     node = tree->nodes[i];
 194
 195     // get the rest of the branch
 196     // if not null, we have found the `ident'th loop
 197     beta_rest = clay_ident_find_loop_aux(node, ident, count);
 198
 199     if (beta_rest != NULL) {
 200       clay_array_concat(beta, beta_rest);
 201       clay_array_free(beta_rest);
 202       return beta;
 203     }
 204
 205     clay_array_free(beta_rest);
 206   }
 207
 208   clay_array_free(beta);
 209
 210   return NULL;
 211 }