source/util.c

   1
   2    /**------ ( ----------------------------------------------------------**
   3     **       )\                      CAnDL                               **
   4     **----- /  ) --------------------------------------------------------**
   5     **     ( * (                   util.c                                **
   6     **----  \#/  --------------------------------------------------------**
   7     **    .-"#'-.        First version: june 7th 2012                    **
   8     **--- |"-.-"| -------------------------------------------------------**
   9           |     |
  10           |     |
  11  ******** |     | *************************************************************
  12  * CAnDL  '-._,-' the Chunky Analyzer for Dependences in Loops (experimental) *
  13  ******************************************************************************
  14  *                                                                            *
  15  * Copyright (C) 2003-2008 Cedric Bastoul                                     *
  16  *                                                                            *
  17  * This is free software; you can redistribute it and/or modify it under the  *
  18  * terms of the GNU General Public License as published by the Free Software  *
  19  * Foundation; either version 2 of the License, or (at your option) any later *
  20  * version.                                                                   *
  21  *                                                                            *
  22  * This software is distributed in the hope that it will be useful, but       *
  23  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
  24  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License   *
  25  * for more details.                                                          *
  26  *                                                                            *
  27  * You should have received a copy of the GNU General Public License along    *
  28  * with software; if not, write to the Free Software Foundation, Inc.,        *
  29  * 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA                     *
  30  *                                                                            *
  31  * CAnDL, the Chunky Dependence Analyzer                                      *
  32  * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr                         *
  33  *                                                                            *
  34  ******************************************************************************/
  35
  36 /*
  37  * author Joel Poudroux and Cedric Bastoul
  38  */
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <osl/statement.h>
  43 #include <osl/relation.h>
  44 #include <osl/macros.h>
  45 #include <osl/extensions/dependence.h>
  46 #include <osl/relation_list.h>
  47 #include <osl/scop.h>
  48 #include <candl/macros.h>
  49 #include <candl/util.h>
  50 #include <candl/statement.h>
  51
  52
  53 /**
  54  * candl_util_relation_get_line function:
  55  * Because the lines in the scattering matrix may have not ordered, we have to
  56  * search the corresponding line. It returns the first line where the value is
  57  * different from zero in the `column'. `column' is between 0 and
  58  * nb_output_dims-1
  59  * \param[in] relation
  60  * \param[in] column        Line to search
  61  * \return                  Return the real line
  62  */
  63 int candl_util_relation_get_line(osl_relation_p relation, int column) {
  64   if (column < 0 || column > relation->nb_output_dims)
  65     return -1;
  66   int i;
  67   int precision = relation->precision;
  68   for (i = 0 ; i < relation->nb_rows ; i++) {
  69     if (!osl_int_zero(precision, relation->m[i][column + 1])) {
  70       break;
  71     }
  72   }
  73   return (i == relation->nb_rows ? -1 : i );
  74 }
  75
  76
  77
  78 /* Check if two scop can be compared (same number of statements and
  79  * same access array/domain in the same order)
  80  *
  81  * \param[in] s1  first scop to compare
  82  * \param[in] s2  second scop to compare
  83  * \return        1 if two scops equal, 0 otherwise
  84  */
  85 int candl_util_check_scop(osl_scop_p s1, osl_scop_p s2) {
  86
  87   osl_statement_p it1 = s1->statement, it2 = s2->statement;
  88   for (; it1 != NULL && it2 != NULL ; it1 = it1->next, it2 = it2->next) {
  89     if (!osl_relation_list_equal(it1->access, it2->access))
  90       return 0;
  91     if (!osl_relation_equal(it1->domain, it2->domain))
  92       return 0;
  93   }
  94
  95   /* Different number of statements */
  96   if ((it1 == NULL || it2 == NULL) && it1 != it2)
  97     return 0;
  98
  99   return 1;
 100 }
 101
 102 /* Extends the candl_util_check_scop() functionality to a list of scops
 103  * Compares each scop in s1 to the corresponding element in list s2
 104  * same access array/domain in the same order)
 105  *
 106  * \param[in] s1  first scop List to compare
 107  * \param[in] s2  second scop List to compare
 108  * \return    1 if two scops lists equal, 0 otherwise
 109  */
 110 int candl_util_check_scop_list(osl_scop_p s1, osl_scop_p s2) {
 111
 112   while ((s1!=NULL) && (s2!=NULL)) {
 113     if(!candl_util_check_scop(s1, s2))
 114       return 0;
 115
 116     s1 = s1->next;
 117     s2 = s2->next;
 118   }
 119
 120   /* Different number of scops */
 121   if ((s1 == NULL || s2 == NULL) && s1 != s2)
 122     return 0;
 123
 124   /*scop lists can be compared*/
 125   return 1;
 126 }
 127
 128 /* Return the number access array which have the type `type'
 129  */
 130 static int count_nb_access(osl_statement_p st, int type) {
 131   osl_relation_list_p access = st->access;
 132   int count = 0;
 133   for (; access != NULL ; access = access->next)
 134     if (access->elt->type == type)
 135       count ++;
 136   return count;
 137 }
 138
 139
 140 /**
 141  * candl_util_statement_commute function:
 142  * This function returns 1 if the two statements given as parameter commute,
 143  * 0 otherwise. It uses the statement type information to answer the question.
 144  * - 09/12/2005: first version.
 145  */
 146 int candl_util_statement_commute(osl_statement_p statement1,
 147                                  osl_statement_p statement2) {
 148   candl_statement_usr_p usr1, usr2;
 149   int type1, type2;
 150   int id1, id2;
 151
 152   usr1  = statement1->usr;
 153   usr2  = statement2->usr;
 154   type1 = usr1->type;
 155   type2 = usr2->type;
 156
 157   /* In the case of self-dependence, a statement commutes with hitself if
 158    * it is a reduction.
 159    */
 160   if ((statement1 == statement2) &&
 161       ((type1 == OSL_DEPENDENCE_P_REDUCTION) ||
 162        (type1 == OSL_DEPENDENCE_M_REDUCTION) ||
 163        (type1 == OSL_DEPENDENCE_T_REDUCTION)))
 164   return 1;
 165
 166   /* Two statement commute when they are a reduction of the same type (or if
 167    * their left and right members are the same, but it's not exploited here).
 168    * The type may differ if it is either minus or plus-reduction. Furthermore,
 169    * they have to write onto the same array (and only one array).
 170    */
 171   if ((type1 == OSL_DEPENDENCE_P_REDUCTION && type2 == OSL_DEPENDENCE_P_REDUCTION) ||
 172       (type1 == OSL_DEPENDENCE_M_REDUCTION && type2 == OSL_DEPENDENCE_M_REDUCTION) ||
 173       (type1 == OSL_DEPENDENCE_T_REDUCTION && type2 == OSL_DEPENDENCE_T_REDUCTION) ||
 174       (type1 == OSL_DEPENDENCE_P_REDUCTION && type2 == OSL_DEPENDENCE_M_REDUCTION) ||
 175       (type1 == OSL_DEPENDENCE_M_REDUCTION && type2 == OSL_DEPENDENCE_P_REDUCTION)) {
 176     /* Here we check that there is one, only one and the same array. */
 177     if (count_nb_access(statement1, OSL_TYPE_WRITE) > 1 ||
 178         count_nb_access(statement2, OSL_TYPE_WRITE) > 1)
 179       return 0;
 180
 181     /* search the first osl_write access */
 182     osl_relation_list_p access1 = statement1->access;
 183     osl_relation_list_p access2 = statement2->access;
 184     for (; access1 != NULL && access2 != NULL ;
 185          access1 = access1->next, access2 = access2->next)
 186       if (access1->elt->type == OSL_TYPE_WRITE)
 187         break;
 188
 189     if (access1 == NULL || access2 == NULL ||
 190         access2->elt->type != OSL_TYPE_WRITE ||
 191         access2->elt->nb_output_dims != access1->elt->nb_output_dims) {
 192       osl_statement_dump(stderr, statement1);
 193       osl_statement_dump(stderr, statement2);
 194       CANDL_error("These statements haven't the same access array or access is NULL");
 195     }
 196
 197     /* Check if the first dim (the Arr column) is the same */
 198     id1 = osl_relation_get_array_id(access1->elt);
 199     id2 = osl_relation_get_array_id(access2->elt);
 200     if (id1 != id2)
 201       return 0;
 202
 203     return 1;
 204   }
 205
 206   return 0;
 207 }