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 <candl/candl.h>
  48 #include <candl/util.h>
  49 #include <candl/scop.h>
  50 #include <candl/statement.h>
  51
  52
  53
  54 /**
  55  * candl_relation_get_line function:
  56  * Because the lines in the scattering matrix may have not ordered, we have to
  57  * search the corresponding line. It returns the first line where the value is
  58  * different from zero in the `column'. `column' is between 0 and
  59  * nb_output_dims-1
  60  * \param[in] relation
  61  * \param[in] column        Line to search
  62  * \return                  Return the real line
  63  */
  64 int candl_relation_get_line(osl_relation_p relation, int column) {
  65   if (column < 0 || column > relation->nb_output_dims)
  66     return -1;
  67   int i;
  68   int precision = relation->precision;
  69   for (i = 0 ; i < relation->nb_rows ; i++) {
  70     if (!osl_int_zero(precision, relation->m[i][column + 1])) {
  71       break;
  72     }
  73   }
  74   return (i == relation->nb_rows ? -1 : i );
  75 }
  76
  77
  78
  79 /* Check if two scop can be compared (same number of statements and
  80  * same access array/domain in the same order)
  81  */
  82 int candl_util_check_scop(osl_scop_p s1, osl_scop_p s2) {
  83
  84   osl_statement_p it1 = s1->statement, it2 = s2->statement;
  85   for (; it1 != NULL && it2 != NULL ; it1 = it1->next, it2 = it2->next) {
  86     if (!osl_relation_list_equal(it1->access, it2->access))
  87       return 0;
  88     if (!osl_relation_equal(it1->domain, it2->domain))
  89       return 0;
  90   }
  91
  92   /* Different number of statements */
  93   if ((it1 == NULL || it2 == NULL) && it1 != it2)
  94     return 0;
  95
  96   return 1;
  97 }
  98
  99
 100 /* Return the number access array which have the type `type'
 101  */
 102 static int count_nb_access(osl_statement_p st, int type) {
 103   osl_relation_list_p access = st->access;
 104   int count = 0;
 105   for (; access != NULL ; access = access->next)
 106     if (access->elt->type == type)
 107       count ++;
 108   return count;
 109 }
 110
 111
 112 /**
 113  * candl_util_statement_commute function:
 114  * This function returns 1 if the two statements given as parameter commute,
 115  * 0 otherwise. It uses the statement type information to answer the question.
 116  * - 09/12/2005: first version.
 117  */
 118 int candl_util_statement_commute(osl_statement_p statement1,
 119                                  osl_statement_p statement2) {
 120   candl_statement_usr_p usr1, usr2;
 121   int type1, type2;
 122   int precision = statement1->domain->precision;
 123   int row_1, row_2;
 124
 125   usr1  = statement1->usr;
 126   usr2  = statement2->usr;
 127   type1 = usr1->type;
 128   type2 = usr2->type;
 129
 130   /* In the case of self-dependence, a statement commutes with hitself if
 131    * it is a reduction.
 132    */
 133   if ((statement1 == statement2) &&
 134       ((type1 == OSL_DEPENDENCE_P_REDUCTION) ||
 135        (type1 == OSL_DEPENDENCE_M_REDUCTION) ||
 136        (type1 == OSL_DEPENDENCE_T_REDUCTION)))
 137   return 1;
 138
 139   /* Two statement commute when they are a reduction of the same type (or if
 140    * their left and right members are the same, but it's not exploited here).
 141    * The type may differ if it is either minus or plus-reduction. Furthermore,
 142    * they have to write onto the same array (and only one array).
 143    */
 144   if ((type1 == OSL_DEPENDENCE_P_REDUCTION && type2 == OSL_DEPENDENCE_P_REDUCTION) ||
 145       (type1 == OSL_DEPENDENCE_M_REDUCTION && type2 == OSL_DEPENDENCE_M_REDUCTION) ||
 146       (type1 == OSL_DEPENDENCE_T_REDUCTION && type2 == OSL_DEPENDENCE_T_REDUCTION) ||
 147       (type1 == OSL_DEPENDENCE_P_REDUCTION && type2 == OSL_DEPENDENCE_M_REDUCTION) ||
 148       (type1 == OSL_DEPENDENCE_M_REDUCTION && type2 == OSL_DEPENDENCE_P_REDUCTION)) {
 149     /* Here we check that there is one, only one and the same array. */
 150     if (count_nb_access(statement1, OSL_TYPE_WRITE) > 1 ||
 151         count_nb_access(statement2, OSL_TYPE_WRITE) > 1)
 152       return 0;
 153
 154     /* search the first osl_write access */
 155     osl_relation_list_p access1 = statement1->access;
 156     osl_relation_list_p access2 = statement2->access;
 157     for (; access1 != NULL && access2 != NULL ;
 158          access1 = access1->next, access2 = access2->next)
 159       if (access1->elt->type == OSL_TYPE_WRITE)
 160         break;
 161
 162     if (access1 == NULL || access2 == NULL ||
 163         access2->elt->type != OSL_TYPE_WRITE ||
 164         access2->elt->nb_output_dims != access1->elt->nb_output_dims) {
 165       osl_statement_dump(stderr, statement1);
 166       osl_statement_dump(stderr, statement2);
 167       CANDL_error("These statements haven't the same access array or access is NULL");
 168     }
 169
 170     /* Check if the first dim (the Arr column) is the same */
 171     row_1 = candl_relation_get_line(access1->elt, 0);
 172     row_2 = candl_relation_get_line(access2->elt, 0);
 173     if (!osl_int_eq(precision,
 174                     access1->elt->m[row_1][access1->elt->nb_columns - 1],
 175                     access2->elt->m[row_2][access2->elt->nb_columns - 1]))
 176       return 0;
 177
 178     return 1;
 179   }
 180
 181   return 0;
 182 }
 183