src/baseparsuif/dependence/normalize.cc

   1 /* file "normalize.cc" */
   2
   3 /*  Copyright (c) 1994 Stanford University
   4
   5     All rights reserved.
   6
   7     This software is provided under the terms described in
   8     the "suif_copyright.h" include file. */
   9
  10 #include <suif_copyright.h>
  11
  12 #define _MODULE_ "libdependence.a"
  13
  14 #include <stdio.h>
  15 #include <suif1.h>
  16 #include <builder.h>
  17 #include <suifmath.h>
  18 #include "dependence.h"
  19
  20 //
  21 // normalize.c
  22 //
  23 //  Normalize the access vectors for all array references and loop
  24 //    definitoins so that the loop increment is always 1
  25 //
  26 //  for i = a to b by c  (where a and b may be funcs of other induc vars)
  27 //      [xi + ...]
  28 // has it's access vectors transformed to
  29 // for i = 0 to (b-a)div c by 1
  30 //      [xci + xa + ...]
  31 // (unless c is 1 in which case no normalization is done)
  32 // Two sets of routines:
  33 //      ref routines change i->xci+xa for all references (including more deeply
  34 //                                                nested loop definintions)
  35 //      loop definition routines change lb<-0, ub<- (b-a)divc, step<-1
  36 // to work correctly, all references must be changed before enclosing defs
  37 //    and the references in a loop definition must be changed before
  38 //    statements inside the loop,
  39 //    ie for i = .  . .
  40 //          for j = a*i b c
  41 //              [i,j]
  42 //
  43 // Also routine to normalize access vectors and test so test is <=
  44 //
  45 //    must change for j = a' b' c' ref first (to take into account changes in i)
  46 //    then change ref [i,j] and finally change loop definitions (a'<-0, etc)
  47 //
  48
  49
  50 // nomalize the reference in an array_info
  51 void array_info::normalize_step_ref()
  52 {
  53     array_info *temp_info = new array_info;
  54
  55     array_info_iter iter1(this);
  56     while (!iter1.is_empty()) {  // normalize each dimension
  57         access_vector *temp_vector = iter1.step();
  58         temp_vector->normalize_step_ref();
  59         temp_info->append(temp_vector);
  60     }
  61
  62     clear();
  63     // copy normalized versions back onto this array_info
  64     array_info_iter iter2(temp_info);
  65     while (!iter2.is_empty()) {
  66         access_vector *temp_vector = iter2.step();
  67         append(temp_vector);
  68         temp_info->remove(iter2.cur_elem());
  69     }
  70     delete temp_info;
  71 }
  72
  73
  74 // normalize an acess_vector for a reference
  75 // ie ai+bj+... b => a*step1*i+a*lb1 + b*step2*j+b*lb2 + ...
  76 void access_vector::normalize_step_ref()
  77 {
  78     if (too_messy) return;  // cannot undo a mess
  79
  80     access_list_iter ai(&elts);
  81     while(!ai.is_empty()) {   // for each induction variable referenced
  82         normalize_step_ref(ai.step());
  83         if (too_messy) return;  // cannot undo a mess
  84     }
  85 }
  86
  87
  88 // normalize one variable of an access variable referenced
  89 // ie a*i => a*step*i + a*lb
  90 void access_vector::normalize_step_ref(access_list_e *induct)
  91 {
  92     tree_node * tn = (tree_node *)induct->var();
  93     dep_for_annote * ann  =
  94         (dep_for_annote *) tn->peek_annote(k_dep_for_annote);
  95     array_info *low = ann->lb;
  96     access_vector *step = ann->stp;
  97
  98     if (step->too_messy || !step->elts.is_empty()) {
  99         too_messy++;
 100         return;
 101     }
 102     if (step->con == 1) return;  // already normalized
 103
 104     /* keep only the first lower bound */
 105     if (low->count() > 1) {
 106         array_info *ai = new array_info();
 107         ai->append(new access_vector(low->first()));
 108         delete low;
 109         ann->lb = low = ai;
 110     }
 111     assert(low->count() == 1);
 112     access_vector *lb = low->first();
 113
 114
 115     if (lb->too_messy || (step->con == 0)) {
 116         too_messy++;
 117         return;
 118     }
 119
 120
 121     int a = induct->info;
 122     induct->info = a*step->con;  // a*i => a*step*i
 123
 124     // now add a*lb to access vector
 125     access_list_iter ai(&lb->elts);
 126     while (!ai.is_empty()) {
 127         access_list_e *lb_element = ai.step();
 128         access_list_e *this_element = elts.search(lb_element->var());
 129         if (this_element) {
 130             this_element->info = this_element->val() + a*(lb_element->val());
 131         } else {
 132             add((tree_node *) lb_element->var(),a*lb_element->val());
 133         }
 134     }
 135     con += a*lb->con;
 136
 137     // now add it to conregs and conpaths and memregs
 138     ai.reset(&lb->conregs);
 139     while (!ai.is_empty()) {
 140         access_list_e *lb_element = ai.step();
 141         access_list_e *this_element = conregs.search(lb_element->var());
 142         if (this_element) {
 143             this_element->info = (this_element->val() + a*(lb_element->val()));
 144         } else {
 145             add((var_sym *) lb_element->var(),0,a*lb_element->val());
 146         }
 147     }
 148     ai.reset(&lb->memregs);
 149     while (!ai.is_empty()) {
 150         access_list_e *lb_element = ai.step();
 151         access_list_e *this_element = memregs.search(lb_element->var());
 152         if (this_element) {
 153             this_element->info = (this_element->val() +
 154                                            a*(lb_element->val()));
 155         } else {
 156             add((var_sym *) lb_element->var(),1,a*lb_element->val());
 157         }
 158     }
 159 }
 160
 161
 162
 163
 164 // normalize the access vectors for the bounds and steps of a loop
 165 void normalize_step_loops(array_info *low, array_info *up,
 166                           access_vector *step, tree_for_test test)
 167 {
 168     if (step->too_messy) return;
 169     if (step->is_const() &&
 170         step ->con == 1) return;   // loop already step_normalized
 171
 172     /* keep only the first lower/upper bound */
 173     access_vector *lb=low->pop();
 174     while (low->count()) delete low->pop();
 175     low->push(lb);
 176     assert(low->count() == 1);
 177
 178     access_vector *ub=up->pop();
 179     while (up->count()) delete up->pop();
 180     up->push(ub);
 181     assert(up->count() == 1);
 182
 183     if (!step->is_const()) {  // non constant step, give up
 184         step->too_messy++;
 185         lb->too_messy++;
 186         ub->too_messy++;
 187         return;
 188     }
 189     if (step->con == 0) {  // perverse case, die
 190         step->too_messy++;
 191         lb->too_messy++;
 192         ub->too_messy++;
 193         return;
 194     }
 195     if (lb->too_messy) {  // can't normalize so give up
 196         step->too_messy++;
 197         lb->too_messy++;
 198         ub->too_messy++;
 199         return;
 200     }
 201     int ub_offset = 0;
 202     if (step->con < 0) {  // reverse sign of test
 203         if (test == FOR_SLT) {
 204             ub_offset = -1;
 205         } else if (test == FOR_ULT) {
 206             ub_offset = -1;
 207         } else if (test == FOR_SLTE) {
 208             ;
 209         } else if (test == FOR_ULTE) {
 210             ;
 211         } else if (test == FOR_SGT) {
 212             ub_offset = -1;
 213         } else if (test == FOR_UGT) {
 214             ub_offset = -1;
 215         } else if (test == FOR_SGTE) {
 216             ;
 217         } else if (test == FOR_UGTE) {
 218             ;
 219         } else {
 220             step->too_messy++;
 221             lb->too_messy++;
 222             ub->too_messy++;
 223             return;
 224         }
 225     }
 226
 227     if (ub->too_messy) {  // can normalize, but ub stays messy
 228     } else {
 229         // ub <- ub - lb
 230         access_list_iter ai(&lb->elts);
 231         while(!ai.is_empty()) {  // subtract off each lower bound component
 232             access_list_e *lb_element = ai.step();
 233             access_list_e *ub_element = ub->elts.search(lb_element->var());
 234             if (ub_element) {
 235                 ub_element->info = ub_element->val() -
 236                                      lb->val((tree_node *) lb_element->var());
 237             } else {
 238                 ub->add((tree_node *) lb_element->key,
 239                         -lb->val((tree_node *) lb_element->var()));
 240             }
 241         }
 242         ub->con -= lb->con;
 243         ai.reset(&lb->conregs);
 244         while(!ai.is_empty()) {  // subtract off each lower bound component
 245             access_list_e *lb_element = ai.step();
 246             access_list_e *ub_element = ub->conregs.search(lb_element->var());
 247             if (ub_element) {
 248                 ub_element->info = (ub_element->val() -
 249                                              lb->val((var_sym *)lb_element->var(),0));
 250             } else {
 251                 ub->add((var_sym *) lb_element->key,0,
 252                         -lb->val((var_sym *)lb_element->var(),0));
 253             }
 254         }
 255         ai.reset(&lb->memregs);
 256         while(!ai.is_empty()) {  // subtract off each lower bound component
 257             access_list_e *lb_element = ai.step();
 258             access_list_e *ub_element = ub->memregs.search(lb_element->var());
 259             if (ub_element) {
 260                 ub_element->info = (ub_element->val() -
 261                                              lb->val((var_sym *)lb_element->var(),1));
 262             } else {
 263                 ub->add((var_sym *) lb_element->key,1,
 264                         -lb->val((var_sym *)lb_element->var(),1));
 265             }
 266         }
 267
 268         // ub <- ub / step
 269         ai.reset(&ub->elts);
 270         while(!ai.is_empty()) {
 271             access_list_e *ub_element = ai.step();
 272             if ((ub_element->val() % step->con) != 0)  {
 273                 /*
 274                   lb->too_messy++;
 275                   ub->too_messy++;
 276                   step->too_messy++;
 277                   return;
 278                   */
 279                 ub->too_messy++;
 280                 lb->con = 0;
 281                 while(!lb->elts.is_empty())
 282                     lb->elts.pop();// erase lb vars
 283                 while (!lb->conregs.is_empty())
 284                     lb->conregs.pop();
 285                 while (!lb->memregs.is_empty())
 286                     lb->memregs.pop();
 287                 step->con = 1;
 288                 return;
 289             } else {
 290                 ub_element->info =
 291                     (ub->val((tree_node *)ub_element->key) / step->con);
 292             }
 293         }
 294         if ((ub->con % step->con) != 0)  {
 295             ub->too_messy++;
 296             lb->con = 0;
 297             while(!lb->elts.is_empty()) lb->elts.pop();// erase lb vars
 298             while (!lb->conregs.is_empty()) lb->conregs.pop();
 299             while (!lb->memregs.is_empty()) lb->memregs.pop();
 300             step->con = 1;
 301             return;
 302         } else {
 303             ub->con /= step->con;
 304             ub->con += ub_offset;
 305         }
 306         ai.reset(&ub->conregs);
 307         while(!ai.is_empty()) {
 308             access_list_e *ub_element = ai.step();
 309             if ((ub_element->val() % step->con) != 0)  {
 310                 ub->too_messy++;
 311                 lb->con = 0;
 312                 while(!lb->elts.is_empty())
 313                     lb->elts.pop();// erase lb vars
 314                 while (!lb->conregs.is_empty())
 315                     lb->conregs.pop();
 316                 while (!lb->memregs.is_empty())
 317                     lb->memregs.pop();
 318                 step->con = 1;
 319                 return;
 320 /*
 321   lb->too_messy++;
 322   ub->too_messy++;
 323   step->too_messy++;
 324   return;
 325   */
 326             } else {
 327                 ub_element->info =
 328                     (ub->val((var_sym *)ub_element->key,0) / step->con);
 329             }
 330         }
 331         ai.reset(&ub->memregs);
 332         while(!ai.is_empty()) {
 333             access_list_e *ub_element = ai.step();
 334             if ((ub_element->val() % step->con) != 0)  {
 335 /*
 336   lb->too_messy++;
 337   ub->too_messy++;
 338   step->too_messy++;
 339   */
 340                 ub->too_messy++;
 341                 lb->con = 0;
 342                 while(!lb->elts.is_empty())
 343                     lb->elts.pop();// erase lb vars
 344                 while (!lb->conregs.is_empty())
 345                     lb->conregs.pop();
 346                 while (!lb->memregs.is_empty())
 347                     lb->memregs.pop();
 348                 step->con = 1;
 349                 return;
 350             } else {
 351                 ub_element->info =
 352                     (ub->val((var_sym *)ub_element->key,1) / step->con);
 353             }
 354         }
 355     }
 356
 357     lb->con = 0;
 358     while (!lb->elts.is_empty()) lb->elts.pop();  // erase lb vars
 359     while (!lb->conregs.is_empty()) lb->conregs.pop();
 360     while (!lb->memregs.is_empty()) lb->memregs.pop();
 361     step->con = 1;
 362 }
 363
 364
 365 void normalize_test(array_info *low,array_info *up,
 366                     access_vector *step, tree_for_test test)
 367 {
 368     array_info_iter ai(up);
 369     while (!ai.is_empty()) {
 370         access_vector *ub = ai.step();
 371
 372         if (test == FOR_SLT) {
 373             ub->con--;
 374             if (ub->min) (*ub->min) --;
 375         } else if (test == FOR_ULT) {
 376             ub->con--;
 377             if (ub->min) (*ub->min) --;
 378         } else if ((test == FOR_SLTE) || (test == FOR_ULTE)) {
 379         } else {
 380             ub->too_messy++;
 381             step->too_messy++;
 382         }
 383     }
 384     array_info_iter ai2(low);
 385     while (!ai2.is_empty()) {
 386         access_vector *lb = ai2.step();
 387
 388         if (test == FOR_SLT) {
 389         } else if (test == FOR_ULT) {
 390         } else if ((test == FOR_SLTE) || (test == FOR_ULTE)) {
 391         } else {
 392             lb->too_messy++;
 393         }
 394     }
 395
 396 }