mach/proto/ncg/equiv.c

   1 #ifndef NORCSID
   2 static char rcsid[] = "$Id: equiv.c,v 0.6 1994/06/24 13:27:11 ceriel Exp $";
   3 #endif
   4
   5 #include "assert.h"
   6 #include "equiv.h"
   7 #include "param.h"
   8 #include "tables.h"
   9 #include "types.h"
  10 #include <cgg_cg.h>
  11 #include "data.h"
  12 #include "result.h"
  13 #include "extern.h"
  14
  15 /*
  16  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  17  * See the copyright notice in the ACK home directory, in the file "Copyright".
  18  *
  19  * Author: Hans van Staveren
  20  */
  21
  22 extern string myalloc();
  23
  24 int rar[MAXCREG];
  25 rl_p *lar;
  26 int maxindex;
  27 int regclass[NREGS];
  28 struct perm *perms;
  29
  30 struct perm *
  31 tuples(regls,nregneeded) rl_p *regls; {
  32         int class=0;
  33         register i,j;
  34         register struct reginfo *rp;
  35
  36         /*
  37          * First compute equivalence classes of registers.
  38          */
  39
  40         for (i=NREGS, rp = &machregs[NREGS-1];--i>=0;rp--) {
  41                 regclass[i] = class++;
  42                 if (getrefcount(i, FALSE) == 0) {
  43                         for (j=NREGS;--j>i;) {
  44                                 if (eqregclass(i,j) &&
  45                                     eqtoken(&rp->r_contents,
  46                                             &machregs[j].r_contents)) {
  47                                         regclass[i] = regclass[j];
  48                                         break;
  49                                 }
  50                         }
  51                 }
  52         }
  53
  54         /*
  55          * Now create tuples through a recursive function
  56          */
  57
  58         maxindex = nregneeded;
  59         lar = regls;
  60         perms = 0;
  61         permute(0);
  62         return(perms);
  63 }
  64
  65 permute(index) {
  66         register struct perm *pp;
  67         register rl_p rlp;
  68         register i,j;
  69
  70         if (index == maxindex) {
  71                 for (pp=perms; pp != 0; pp=pp->p_next) {
  72                         for (i=0; i<maxindex; i++)
  73                                 if (regclass[rar[i]] != regclass[pp->p_rar[i]])
  74                                         goto diff;
  75                         for (i=0; i<maxindex; i++) {
  76                                 int rari = rar[i], p_rari = pp->p_rar[i];
  77                                 for (j=0; j<i; j++)
  78                                         if (clash(rari,rar[j]) !=
  79                                             clash(p_rari,pp->p_rar[j]))
  80                                                 goto diff;
  81                         }
  82                         return;
  83                     diff: ;
  84                 }
  85                 pp = (struct perm *) myalloc(sizeof ( *pp ));
  86                 pp->p_next = perms;
  87                 for (i=0; i<maxindex; i++)
  88                         pp->p_rar[i] = rar[i];
  89                 perms = pp;
  90         } else {
  91                 rlp=lar[index];
  92                 for (i=rlp->rl_n; i>0; i--) {
  93                         rar[index] = rlp->rl_list[rlp->rl_n-i];
  94                         permute(index+1);
  95                 }
  96         }
  97 }