src/baseparsuif/dependence/access_vector.cc

   1 /* file "access_vector.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 #pragma implementation "access_vector.h"
  14
  15 #include <stdio.h>
  16 #include <suif1.h>
  17 #include <builder.h>
  18 #include <suifmath.h>
  19 #include "dependence.h"
  20 #include "include.h"
  21
  22 #include <stdlib.h>
  23
  24 // allow a[i] where i is a global
  25 #define INDEX_IS_FUNKY_PATH
  26
  27 int forget_about_mod_this = 0;
  28
  29 /************************************************************************
  30  *                                                                      *
  31  * Add value i if entry for 'v' exists. otherwise create an entry for v *
  32  * with value i.                                                        *
  33  *                                                                      *
  34  ************************************************************************/
  35 void access_list::enter(const void *v,int i)    // compiler bug, couldn\'t inline
  36 {
  37     access_list_e *e=search(v);
  38     if(e) {
  39         int newval = e->info + i;
  40         e->info = newval;
  41         if(newval == 0) {
  42             remove(e);
  43             delete e;
  44         }
  45     }
  46     else if(i)
  47         ass_list<int>::enter(v, i);
  48 }
  49
  50 int av_compare_access_lists(const access_list *av,  const access_list *av2)
  51 {
  52     // first check that all values on one list are on other
  53     access_list_iter ai(av2);
  54     while(!ai.is_empty()) {
  55         access_list_e *e = ai.step();
  56         access_list_e *ave = av->search(e->var());
  57         assert(e->val() != 0);
  58         if(!ave) {
  59             return 0;
  60         } else {
  61             assert(ave->val() != 0);
  62             if(e->val() != ave->val()) return 0;
  63         }
  64     }
  65
  66     // now check that any values on av but not av2 are zero
  67     access_list_iter avi(av);
  68     while(!avi.is_empty()) {
  69         access_list_e *e = avi.step();
  70         if(av2->search(e->key) == 0) {
  71             assert(e->val() != 0);
  72             return 0;
  73         }
  74     }
  75
  76     return 1;
  77 }
  78
  79 av_compare_info::av_compare_info(const access_vector *av,
  80                                  const access_vector *av2)
  81 {
  82 //    flag = 0;
  83     flag = 8;
  84     assert(!av->too_messy && !av2->too_messy);
  85     if(av_compare_access_lists(&av->elts, &av2->elts)) flag |= 1;
  86     if(av_compare_access_lists(&av->conregs, &av2->conregs)) flag |= 2;
  87     if(av_compare_access_lists(&av->memregs, &av2->memregs)) flag |= 4;
  88     if(av->con == av2->con) flag |= 16;
  89 }
  90
  91 void print_prefix(FILE *f,int i,int *first)
  92 {
  93     assert(i != 0);
  94     if(i > 0 && !*first)
  95         fprintf(f,"+");
  96     *first = 0;
  97
  98     if(i == -1)
  99         fprintf(f,"-");
 100     else if(i != 1)
 101         fprintf(f,"%d*",i);
 102 }
 103
 104 void access_vector::print(FILE *f)
 105 {
 106     if(too_messy) {
 107         fprintf(f,"<too messy>");
 108         return;
 109     }
 110     int first = 1;
 111
 112     access_list_iter ai(&elts);
 113     while(!ai.is_empty()) {
 114         access_list_e *e = ai.step();
 115         tree_node *n = (tree_node *) e->var();
 116         int i = e->val();
 117         var_sym * index;
 118         switch(n->kind()) {
 119         case TREE_FOR:
 120             print_prefix(f,i,&first);
 121             index = ((tree_for *)n)->index();
 122             fprintf(f,"%s",index->name());
 123             break;
 124         default:
 125             assert(0);
 126         }
 127     }
 128     ai.reset(&conregs);
 129     while(!ai.is_empty()) {
 130         access_list_e *e = ai.step();
 131         var_sym * v = (var_sym *) e->var();
 132         print_prefix(f,e->val(),&first);
 133         fprintf(f,"%s",v->name());
 134     }
 135     ai.reset(&memregs);
 136     while(!ai.is_empty()) {
 137         access_list_e *e = ai.step();
 138         tree_node *n = (tree_node *) e->var();
 139         int i = e->val();
 140         var_sym * index;
 141         switch(n->kind()) {
 142         case TREE_FOR:
 143             print_prefix(f,i,&first);
 144             index = ((tree_for *)n)->index();
 145             fprintf(f,"%s",index->name());
 146             break;
 147         default:
 148             assert(0);
 149         }
 150     }
 151     if(first || con < 0)
 152         fprintf(f,"%d",con);
 153     else if(con>0)
 154         fprintf(f,"+%d",con);
 155     if(mod_this) {
 156         assert(mod_this->kind() == TREE_FOR);
 157         fprintf(f,"`mod by: %s'",mod_this->index()->name());
 158     }
 159 }
 160
 161 access_vector::~access_vector()
 162 {
 163     if (min) delete min;
 164     if (max) delete max;
 165     while(!elts.is_empty()) delete elts.pop();
 166     while(!conregs.is_empty()) delete conregs.pop();
 167     while(!memregs.is_empty()) delete memregs.pop();
 168 }
 169
 170 int is_const(const operand & op, int *val)
 171 {
 172     if(!op.is_instr()) return 0;
 173     instruction * in = op.instr();
 174     if(!in) return 0;
 175     if(in->opcode() == io_cvt)
 176         return is_const(((in_rrr *)in)->src1_op(), val);
 177     if(in->opcode() != io_ldc) return 0;
 178     immed ic = ((in_ldc *) in)->value();
 179     if(ic.kind() == im_int) *val = ic.integer();
 180     return (ic.kind() == im_int);
 181 }
 182
 183 tree_for * is_index(var_sym * v, tree_node *tn)
 184 {
 185     assert(v);
 186     for(tree_node *n = tn; n; n = n->parent()->parent()) {
 187         if(n->kind() == TREE_FOR &&
 188            ((tree_for *)n)->index() == v)
 189             return (tree_for *) n;
 190         if(n->parent()==NULL) break;
 191     }
 192     return NULL;
 193 }
 194
 195 static void put_index_info(tree_for * fn,               /* deepest for node */
 196                            const operand & op,          /* expression */
 197                            access_vector *av,
 198                            int factor)
 199 {
 200     assert(av);
 201
 202     tree_for *nf=NULL;
 203     if(op.kind() == OPER_SYM) {
 204         if(op.symbol()->is_var() == 0) {
 205             av->too_messy++;
 206             return;
 207         }
 208         if(fn) {
 209             nf = is_index((var_sym *)op.symbol(), fn);
 210             if(nf)
 211                 av->add(nf, factor);
 212             else
 213                 av->add((var_sym *)op.symbol(), 0, factor);
 214         } else
 215             av->add((var_sym *)op.symbol(), 0, factor);
 216         return;
 217     }
 218
 219     if(op.kind() != OPER_INSTR) {
 220         av->too_messy++;
 221         return;
 222     }
 223     instruction * ins = op.instr();
 224     in_rrr *i3r = (in_rrr *) ins;
 225     if(ins->format() == inf_rrr) {
 226         int val;
 227         if(is_const(operand(ins), &val)) {
 228             av->con += val*factor;
 229             return;
 230         }
 231     } else if(ins->format() == inf_ldc) {
 232         in_ldc * ld = (in_ldc *)ins;
 233         if(ld->value().is_int_const())
 234             av->con += ld->value().integer() * factor;
 235         else
 236             av->too_messy++;
 237         return;
 238     }
 239     switch(ins->opcode()) {
 240         // not that io_cvt is too messy.  That way we can assume that
 241         // lods have the correct type, and in general it allows us
 242         // to rebuild from the access vectors.
 243         // Saman 12/1/94:
 244         // io_cvt is needed in SGI64 format, so here we go.
 245     case io_cvt: {
 246         put_index_info(fn, i3r->src1_op(), av, factor);
 247         break;
 248     }
 249
 250     default:
 251         av->too_messy++;
 252         break;
 253     case io_lod: {
 254         // could be a constant path
 255         operand  s1 = i3r->src1_op();
 256         if(s1.is_instr() && s1.instr()->opcode() == io_array) {
 257             //BUGBUG:10/22/93
 258             // For a bound DO i=1, U(A(0))
 259             // returning upper bound to be 0 is incorrect.
 260             av->too_messy++;
 261             // all indexes had better be zero or forget it
 262             in_array *ia = (in_array *) s1.instr();
 263             s1 = ia->base_op();
 264             int i;
 265             for(i = 0; ((unsigned)i) < ia->dims(); i++) {
 266                 int val;
 267                 if(!is_const(ia->index(i), &val) || val)
 268                     break;
 269             }
 270             if(((unsigned)i) != ia->dims()) {
 271                 av->too_messy++;
 272                 break;
 273             }
 274             ins = s1.instr();   // look at the base of the array.
 275         }
 276         av->too_messy++;
 277         break;
 278     }
 279     case io_neg:
 280         put_index_info(fn, i3r->src1_op(), av, -factor);
 281         break;
 282     case io_add:
 283         put_index_info(fn, i3r->src1_op(), av, factor);
 284         put_index_info(fn, i3r->src2_op(), av, factor);
 285         break;
 286     case io_sub:
 287         put_index_info(fn, i3r->src1_op(), av, factor);
 288         put_index_info(fn, i3r->src2_op(), av, -factor);
 289         break;
 290     case io_mul: {
 291         int val;
 292         // var*const or const*var
 293         if(is_const(i3r->src1_op(), &val))
 294             put_index_info(fn, i3r->src2_op(), av, factor * val);
 295         else if(is_const(i3r->src2_op(), &val))
 296             put_index_info(fn, i3r->src1_op(), av, factor * val);
 297         else
 298             av->too_messy++;
 299     }
 300         break;
 301     case io_div:
 302     case io_divfloor:
 303     case io_divceil: {
 304         int val;
 305         // var/const
 306         if(!is_const(i3r->src2_op(),&val) || (val == 0) || factor % val)
 307             av->too_messy++;
 308         else
 309             put_index_info(fn, i3r->src1_op(), av, factor / val);
 310     }
 311         break;
 312     case io_lsl: {
 313         int val;
 314         if(!is_const(i3r->src2_op(), &val) || val < 0)
 315             av->too_messy++;
 316         else
 317             put_index_info(fn, i3r->src1_op(), av, factor<<val);
 318     };
 319         break;
 320     case io_cpy:
 321         put_index_info(fn, i3r->src1_op(), av, factor);
 322         break;
 323     }
 324 }
 325
 326 void access_vector::enter_als(const access_vector *a)
 327 {
 328     access_list_iter ai(&a->elts);
 329     while (!ai.is_empty()){
 330         access_list_e * ae = ai.step();
 331         elts.enter(ae->var(),ae->val());
 332     }
 333
 334     ai.reset(&a->conregs);
 335     while (!ai.is_empty()){
 336         access_list_e * ae = ai.step();
 337         conregs.enter(ae->var(),ae->val());
 338     }
 339
 340     ai.reset(&a->memregs);
 341     while (!ai.is_empty()){
 342         access_list_e * ae = ai.step();
 343         memregs.enter(ae->var(),ae->val());
 344     }
 345 }
 346
 347
 348 access_vector::access_vector(const access_vector *a): glist_e()
 349 {
 350     too_messy = a -> too_messy;
 351     mod_this = forget_about_mod_this ? 0 : a->mod_this;
 352
 353     con = a->con;
 354     if (a->min) {
 355         min = new int;
 356         *min = *a->min;
 357     } else min = NULL;
 358     if (a->max) {
 359         max = new int;
 360         *max = *a->max;
 361     } else max = NULL;
 362
 363     enter_als(a);
 364 }
 365
 366
 367 access_vector::access_vector(const access_vector &a): glist_e()
 368 {
 369     too_messy = a.too_messy;
 370     mod_this = forget_about_mod_this ? 0 : a.mod_this;
 371
 372     con = a.con;
 373     if (a.min) {
 374         min = new int;
 375         *min = *a.min;
 376     } else min = NULL;
 377     if (a.max) {
 378         max = new int;
 379         *max = *a.max;
 380     } else max = NULL;
 381
 382     enter_als(&a);
 383 }
 384
 385
 386 access_vector::access_vector(tree_instr *n, int fancy):
 387     glist_e(), too_messy(0), con(0)
 388 {
 389     min = max = 0;
 390     mod_this = 0;
 391     tree_for * tf = (tree_for *)next_further_out(n, TREE_FOR);
 392     put_index_info(tf, operand(n->instr()), this, 1);
 393
 394     if(fancy == 0 &&
 395        !(conregs.is_empty() && memregs.is_empty()))
 396         too_messy++;
 397     else if(fancy == 1 &&
 398             !(memregs.is_empty()))
 399         too_messy++;
 400     if(!forget_about_mod_this)
 401         set_mod_this(n);
 402     //set_min_max();  // gets messed up by normalization
 403 }
 404
 405 access_vector::access_vector(operand op, tree_node * tn, int fancy):
 406     glist_e(), too_messy(0), con(0)
 407 {
 408     min = max = 0;
 409     mod_this = 0;
 410
 411
 412     tree_for * tf = (tree_for *)next_further_out(tn, TREE_FOR, TRUE);
 413     put_index_info(tf, op, this, 1);
 414
 415     if(!fancy &&
 416        !(conregs.is_empty() && memregs.is_empty()))
 417         too_messy++;
 418     else if(fancy == 1 &&
 419             !(memregs.is_empty()))
 420         too_messy++;
 421     if(!forget_about_mod_this)
 422         if(tf)
 423             set_mod_this(tf);
 424     //set_min_max();  /* gets messed up by normalization */
 425 }
 426
 427 access_vector::access_vector(instruction  * inst, int fancy):
 428     glist_e(), too_messy(0), con(0)
 429 {
 430     min = max = 0;
 431     mod_this = 0;
 432
 433     assert(inst);
 434
 435     tree_for * tf = (tree_for *)next_further_out(inst->parent(), TREE_FOR, TRUE);
 436     put_index_info(tf, operand(inst), this, 1);
 437
 438     if(!fancy &&
 439        !(conregs.is_empty() && memregs.is_empty()))
 440         too_messy++;
 441     else if(fancy == 1 &&
 442             !(memregs.is_empty()))
 443         too_messy++;
 444     if(!forget_about_mod_this)
 445         set_mod_this(tf);
 446     //set_min_max();  /* gets messed up by normalization */
 447 }
 448
 449
 450 void array_info::print(FILE *f)
 451 {
 452     int print_comma = 0;
 453     fprintf(f,"[");
 454     array_info_iter ai(this);
 455     while(!ai.is_empty()) {
 456         if(print_comma++) fprintf(f,",");
 457         ai.step()->print(f);
 458     }
 459     fprintf(f,"]");
 460 }
 461
 462 array_info::~array_info()
 463 {
 464     while(!is_empty()) delete pop();
 465 }
 466
 467 array_info::array_info(instruction * ins, int fancy)
 468 {
 469     assert(ins->opcode() == io_array);
 470     in_array *i = (in_array *) ins;
 471
 472     for(int cnt = 0; ((unsigned)cnt) < i->dims(); cnt++) {
 473         access_vector *av;
 474         av = new access_vector(i->index(cnt), ins->parent(), fancy);
 475         append(av);
 476     }
 477 }
 478
 479
 480 array_info::array_info(array_info * ainfo)
 481 {
 482     array_info_iter iter(ainfo);
 483
 484     while(!iter.is_empty()) {
 485         access_vector * av = iter.step();
 486         append(new access_vector(av));
 487     }
 488 }
 489
 490 static void build_block(block &B, boolean &block_empty, binary_op bop, block &A)
 491 {
 492     if (block_empty) {
 493         switch (bop) {
 494         case bop_add: B.set(A);  break;
 495         case bop_sub: B.set(-A); break;
 496         default: assert(0);
 497         }
 498     }
 499     else B.set(B.dobinop(bop,A));
 500     block_empty = FALSE;
 501 }
 502
 503
 504 operand access_vector::generate_code(tree_proc *p, block_symtab * sym)
 505 {
 506     // ignores the step, so if the step\'s not one, be careful!
 507
 508     assert(!too_messy);
 509
 510     block::set_proc(p); // block::set_proc(p) didn't compile
 511     block B;
 512     boolean block_empty = TRUE;
 513
 514     // Only set the block to the constant value if the constant is non-zero.
 515     if (con) {
 516         B.set(block(con));
 517         block_empty = FALSE;
 518     }
 519
 520     access_list_iter ai(&elts);
 521     while (!ai.is_empty()) {
 522         access_list_e *ae = ai.step();
 523         tree_for *a = (tree_for *) ae->var();
 524         int i = ae->val();
 525         block var(a->index());
 526         if(i == 0) continue;
 527         else if(i == 1) build_block(B,block_empty,bop_add,var);
 528         else if(i == -1) build_block(B,block_empty,bop_sub,var);
 529         else {
 530             block multi(i);
 531             build_block(B,block_empty,bop_add,multi*var);
 532         }
 533     }
 534
 535     ai.reset(&conregs);
 536     while (!ai.is_empty()) {
 537         access_list_e *ae = ai.step();
 538         var_sym * v = (var_sym *) ae->var();
 539         int i = ae->val();
 540         block var(v);
 541         if(i == 0) continue;
 542         else if(i == 1) build_block(B,block_empty,bop_add,var);
 543         else if(i == -1) build_block(B,block_empty,bop_sub,var);
 544         else {
 545             block multi(i);
 546             build_block(B,block_empty,bop_add,multi*var);
 547         }
 548     }
 549
 550     ai.reset(&memregs);
 551     while (!ai.is_empty()) {
 552         access_list_e *ae = ai.step();
 553         var_sym * v = (var_sym *) ae->var();
 554         int i = ae->val();
 555         block var(v);
 556         if(i == 0) continue;
 557         else if(i == 1) build_block(B,block_empty,bop_add,var);
 558         else if(i == -1) build_block(B,block_empty,bop_sub,var);
 559         else {
 560             block multi(i);
 561             build_block(B,block_empty,bop_add,multi*var);
 562         }
 563     }
 564
 565     // If the block is still empty, then add the zero constant.
 566     if (block_empty)
 567         B.set(block(con));
 568
 569     instruction * inst;
 570     if(sym)
 571         inst = B.make_instruction();  // B.make_instruction(sym)
 572     else
 573         inst = B.make_instruction();
 574
 575     return operand(inst);
 576 }
 577
 578
 579
 580 void access_vector::operator = (const access_vector &a)
 581 {
 582         too_messy = a.too_messy;
 583         con = a.con;
 584         if (a.min) {
 585                 min = new int;
 586                 *min = *a.min;
 587         } else min = 0;
 588         if (a.max) {
 589                 max = new int;
 590                 *max = *a.max;
 591         } else max = 0;
 592
 593         while(!elts.is_empty()) delete elts.pop();
 594         while(!conregs.is_empty()) delete conregs.pop();
 595         while(!memregs.is_empty()) delete memregs.pop();
 596
 597         enter_als(&a);
 598 }
 599
 600 void access_vector::operator += (const access_vector &a)
 601 {
 602         if (min && a.min) {
 603             *min += *a.min;
 604         } else {
 605             if(min) delete min;
 606             min = 0;
 607         }
 608
 609         if (max && a.max) {
 610             *max += *a.max;
 611         } else {
 612             if(max) delete max;
 613             max = 0;
 614         }
 615
 616         if(a.too_messy)
 617                 too_messy++;
 618         if(too_messy)
 619                 return;
 620
 621         con += a.con;
 622
 623         enter_als(&a);
 624 }
 625
 626 void access_vector::operator -= (const access_vector &a)
 627 {
 628     if (min && a.min) {
 629         *min -= *a.min;
 630     } else {
 631         if(min) delete min; min = 0;
 632     }
 633
 634     if (max && a.max) {
 635         *max -= *a.max;
 636     } else {
 637         if(max) delete max; max = 0;
 638     }
 639
 640         if(a.too_messy)
 641                 too_messy++;
 642         if(too_messy)
 643                 return;
 644
 645         con -= a.con;
 646
 647         access_list_iter ai(&a.elts);
 648         while (!ai.is_empty()){
 649             access_list_e * ae = ai.step();
 650             elts.enter(ae->var(),-ae->val());
 651         }
 652
 653         ai.reset(&a.conregs);
 654         while (!ai.is_empty()){
 655             access_list_e * ae = ai.step();
 656             conregs.enter(ae->var(),-ae->val());
 657         }
 658
 659         ai.reset(&a.memregs);
 660         while (!ai.is_empty()){
 661             access_list_e * ae = ai.step();
 662             memregs.enter(ae->var(),-ae->val());
 663         }
 664
 665 }
 666
 667 void access_vector::operator *= (int f)
 668 {
 669         if (min) {
 670                 *min *= f;
 671         }
 672
 673         if (max) {
 674                 *max *= f;
 675         }
 676
 677         if (f < 0) {
 678                 int *temp = min;
 679                 min = max;
 680                 max = temp;
 681         }
 682
 683         if(too_messy || f == 1)
 684                 return;
 685
 686         if(f == 0) {
 687                 access_vector av;
 688                 *this = av;
 689                 return;
 690         }
 691
 692         con *= f;
 693
 694         access_list_iter ai(&elts);
 695         while (!ai.is_empty()){
 696             access_list_e * ae = ai.step();
 697             ae->info = ae->info * f;
 698         }
 699
 700         ai.reset(&conregs);
 701         while (!ai.is_empty()){
 702             access_list_e * ae = ai.step();
 703             ae->info = ae->info * f;
 704         }
 705
 706         ai.reset(&memregs);
 707         while (!ai.is_empty()){
 708             access_list_e * ae = ai.step();
 709             ae->info = ae->info * f;
 710         }
 711
 712 }
 713
 714 void access_vector::operator /= (int f)
 715 {
 716         assert(f != 0);
 717
 718         int f2=f;
 719         if (f < 0) {
 720                 f2 = -f;
 721                 int *temp = min;
 722                 min = max;
 723                 max = temp;
 724                 if (min) *min = -*min;
 725                 if (max) *max = -*max;
 726         }
 727
 728         if (min) {
 729                 if (*min % f2 == 0) *min /= f2;
 730                 else if (*min > 0) *min /= f2;
 731                 else *min = *min / f2 - 1;
 732         }
 733         if (max) {
 734                 if (*max % f2 == 0) *max /= f2;
 735                 else if (*max > 0) *max = *max/f2 + 1;
 736                 else *max = *max / f2 ;
 737         }
 738
 739
 740         if(too_messy || f == 1)
 741                 return;
 742
 743         if(con % f) too_messy++;
 744         else con /= f;
 745
 746         access_list_iter ai(&elts);
 747         while (!ai.is_empty()){
 748             access_list_e * ae = ai.step();
 749             if((int) ae->info % f) too_messy++;
 750             else ae->info = ae->info / f;
 751         }
 752
 753         ai.reset(&conregs);
 754         while (!ai.is_empty()){
 755             access_list_e * ae = ai.step();
 756             if((int) ae->info % f) too_messy++;
 757             else ae->info = ae->info / f;
 758         }
 759
 760         ai.reset(&memregs);
 761         while (!ai.is_empty()){
 762             access_list_e * ae = ai.step();
 763             if((int) ae->info % f) too_messy++;
 764             else ae->info = ae->info / f;
 765         }
 766
 767 }
 768
 769
 770
 771 //
 772 // find the innermost for loop which might assign this acceess vector
 773 //
 774 void access_vector::set_mod_this(tree_node * ti)
 775 {
 776     assert(forget_about_mod_this == 0);
 777
 778     mod_this = 0;
 779
 780     tree_for *find_inner(tree_node *, var_sym *);
 781     int is_ancestor(tree_node *, tree_node *);
 782
 783     // first find innermost for loop
 784     tree_node *inner = (tree_node *) ti;
 785     tree_node *prev = inner;
 786     while(inner->kind() != TREE_FOR) {
 787         assert(inner->parent());
 788         inner = inner->parent()->parent();
 789         if (!inner) {                           // not inside a for loop
 790             mod_this = NULL;
 791             return;
 792         }
 793         prev = inner;
 794     }
 795
 796     // go through all the registers
 797     access_list_iter ali(&conregs);
 798     while (!ali.is_empty()) {
 799         access_list_e *e = ali.step();
 800         var_sym * sym = (var_sym *)e->var();
 801         tree_for *temp = find_inner(inner, sym);
 802         if (temp) {
 803             if(!mod_this || is_ancestor(mod_this, temp)) {
 804                 mod_this = temp;
 805             }
 806         }
 807     }
 808
 809     // go through all the memory registers
 810     ali.reset(&memregs);
 811     while (!ali.is_empty()) {
 812         access_list_e *e = ali.step();
 813         var_sym * sym = (var_sym *)e->var();
 814         tree_for *temp = find_inner(inner, sym);
 815         if (temp) {
 816             if(!mod_this || is_ancestor(mod_this,temp)) {
 817                 mod_this = temp;
 818             }
 819         }
 820     }
 821
 822     // copout.  We need to handle this case eventually ...
 823     if (!memregs.is_empty()) {
 824         assert(inner && inner->kind() == TREE_FOR);
 825         mod_this = (tree_for *) inner;
 826         return;
 827     }
 828
 829 }
 830
 831
 832 // is node 1 an ancestor of node 2
 833 int is_ancestor(tree_node *node1, tree_node *node2)
 834 {
 835     if(node2->parent() == NULL) return 0;
 836     node2 = node2->parent()->parent();
 837     while (node2) {
 838         if (node2 == node1) return 1;
 839         if(node2->parent() == NULL) return 0;
 840         node2 = node2->parent()->parent();
 841     }
 842     return 0;
 843 }
 844
 845
 846 // find the innermost for loop which might assign a register
 847 tree_for *find_inner(tree_node *n, var_sym * v)
 848 {
 849     tree_for *prev = 0;
 850
 851     while (n) {
 852         if (n->kind() == TREE_FOR) {
 853             tree_for *tnf = (tree_for *)n;
 854             if (sym_modified(v, tnf->body(), prev)) {
 855                 return tnf;
 856             } else if (sym_modified(v, tnf->ub_list(), prev)) {
 857                 return tnf;
 858             } else if (sym_modified(v, tnf->step_list(), prev)) {
 859                 return tnf;
 860             } else if (sym_modified(v, tnf->lb_list(), prev)) {
 861                 return tnf;
 862             }
 863             prev = tnf;
 864         }
 865
 866         n = (n->parent())?n->parent()->parent():NULL;
 867     }
 868     return 0;
 869 }
 870
 871
 872
 873 // routines to manipulate access lists
 874
 875 // set the union of two lists
 876 void access_list::unite(access_list *a1, access_list *a2)
 877 {
 878         access_list_iter ai(a1);
 879         while(!ai.is_empty()) {
 880                 access_list_e *e = ai.step();
 881                 enter(e->var(),e->val());
 882         }
 883         access_list_iter ai2(a2);
 884         while(!ai2.is_empty()) {
 885                 access_list_e *e = ai2.step();
 886                 if (!this->search(e->var())) {
 887                         enter(e->var(),e->val());
 888                 }
 889         }
 890 }
 891
 892 // set the union of this to another list
 893 void access_list::unite(access_list *a1)
 894 {
 895         access_list_iter ai(a1);
 896         while(!ai.is_empty()) {
 897                 access_list_e *e = ai.step();
 898                 if (!this->search(e->var())) {
 899                         enter(e->var(),e->val());
 900                 }
 901         }
 902 }
 903
 904 // set the intersection of two lists
 905 void access_list::intersect(access_list *a1, access_list *a2)
 906 {
 907         access_list_iter ai(a1);
 908         while(!ai.is_empty()) {
 909                 access_list_e *e = ai.step();
 910                 if (a2->search(e->var())){
 911                         enter(e->var(),e->val());
 912                 }
 913         }
 914 }
 915
 916 // set the intersection of this to another list
 917 void access_list::intersect(access_list *a1)
 918 {
 919         access_list_iter ai(this);
 920         while(!ai.is_empty()) {
 921                 access_list_e *e = ai.step();
 922                 if (!a1->search(e->var())){
 923                         remove(e);
 924                 }
 925         }
 926 }
 927
 928 // how many elements
 929 int access_list::count()
 930 {
 931         int cnt;
 932         access_list_iter ai(this);
 933         for (cnt=0; !ai.is_empty(); ai.step()) cnt++;
 934         return cnt;
 935 }
 936
 937 // find the min and max of this access_vector
 938 void access_vector::set_min_max()
 939 {
 940         if (max) {
 941                 delete max;
 942                 max = 0;
 943         }
 944         if (min) {
 945                 delete min;
 946                 min = 0;
 947         }
 948
 949         if (too_messy || !conregs.is_empty() ||
 950             !memregs.is_empty()) {
 951                 max = 0; min = 0;
 952                 return;
 953         }
 954
 955         min = new int;
 956         max = new int;
 957         *max = *min = con;
 958
 959         access_list_iter ai(&elts);
 960         while(!ai.is_empty()) {
 961             access_list_e *induct = ai.step();
 962             int value = induct->val();
 963             if(value==0)
 964                 continue;
 965             dep_for_annote *dfa = NULL;  // = (tree_for *) induct->var();
 966             assert(dfa);
 967
 968             int *formin = 0;
 969             if(dfa->lb) {
 970                 array_info_iter ai(dfa->lb);
 971                 while (!ai.is_empty()) {
 972                     access_vector *av = ai.step();
 973                     if (!av->too_messy && av->min) {
 974                         if (!formin || (*av->min < *formin)) {
 975                             formin = av->min;
 976                         }
 977                     }
 978                 }
 979             }
 980             int *formax = 0;
 981             if(dfa->ub) {
 982                 array_info_iter ai2(dfa->ub);
 983                 while (!ai2.is_empty()) {
 984                     access_vector *av = ai2.step();
 985                     if (!av->too_messy && av->max) {
 986                         if (!formax || (*av->max > *formax)) {
 987                             formax = av->max;
 988                         }
 989                     }
 990                 }
 991             }
 992
 993             int *fmin = value > 0 ? formin : formax;
 994             int *fmax = value > 0 ? formax : formin;
 995
 996             if (min && fmin) {
 997                 *min = *min + value * *fmin;
 998             } else {
 999                 if(min) delete min;
1000                 min = 0;
1001             }
1002             if (max && fmax) {
1003                 *max = *max + value * *fmax;
1004             } else {
1005                 if(max) delete max;
1006                 max = 0;
1007             }
1008         }
1009 }
1010
1011
1012
1013