equiv.c 1.9 KB

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