equiv.c 1.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899
  1. #ifndef NORCSID
  2. static char rcsid[] = "$Id$";
  3. #endif
  4. #include <stdlib.h>
  5. #include <stdio.h>
  6. #include "assert.h"
  7. #include "equiv.h"
  8. #include "param.h"
  9. #include "tables.h"
  10. #include "types.h"
  11. #include <cgg_cg.h>
  12. #include "data.h"
  13. #include "result.h"
  14. #include "extern.h"
  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. extern string myalloc();
  22. int rar[MAXCREG];
  23. rl_p *lar;
  24. int maxindex;
  25. int regclass[NREGS];
  26. struct perm *perms;
  27. struct perm *
  28. tuples(regls,nregneeded) rl_p *regls; {
  29. int class=0;
  30. register i,j;
  31. register struct reginfo *rp;
  32. /*
  33. * First compute equivalence classes of registers.
  34. */
  35. for (i=NREGS, rp = &machregs[NREGS-1];--i>=0;rp--) {
  36. regclass[i] = class++;
  37. if (getrefcount(i, FALSE) == 0) {
  38. for (j=NREGS;--j>i;) {
  39. if (eqregclass(i,j) &&
  40. eqtoken(&rp->r_contents,
  41. &machregs[j].r_contents)) {
  42. regclass[i] = regclass[j];
  43. break;
  44. }
  45. }
  46. }
  47. }
  48. /*
  49. * Now create tuples through a recursive function
  50. */
  51. maxindex = nregneeded;
  52. lar = regls;
  53. perms = 0;
  54. permute(0);
  55. return(perms);
  56. }
  57. permute(index) {
  58. register struct perm *pp;
  59. register rl_p rlp;
  60. register i,j;
  61. if (index == maxindex) {
  62. for (pp=perms; pp != 0; pp=pp->p_next) {
  63. for (i=0; i<maxindex; i++)
  64. if (regclass[rar[i]] != regclass[pp->p_rar[i]])
  65. goto diff;
  66. for (i=0; i<maxindex; i++) {
  67. int rari = rar[i], p_rari = pp->p_rar[i];
  68. for (j=0; j<i; j++)
  69. if (clash(rari,rar[j]) !=
  70. clash(p_rari,pp->p_rar[j]))
  71. goto diff;
  72. }
  73. return;
  74. diff: ;
  75. }
  76. pp = (struct perm *) myalloc(sizeof ( *pp ));
  77. pp->p_next = perms;
  78. for (i=0; i<maxindex; i++)
  79. pp->p_rar[i] = rar[i];
  80. perms = pp;
  81. } else {
  82. rlp=lar[index];
  83. for (i=rlp->rl_n; i>0; i--) {
  84. rar[index] = rlp->rl_list[rlp->rl_n-i];
  85. permute(index+1);
  86. }
  87. }
  88. }