/* * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands. * See the copyright notice in the ACK home directory, in the file "Copyright". */ #include "assert.h" #include "param.h" #include "set.h" #include "hall.h" #include "error.h" #include /* * This file implements the marriage thesis from Hall. * The thesis says that given a number, say N, of subsets from * a finite set, it is possible to create a set with cardinality N, * that contains one member for each of the subsets, * iff for each number, say M, of subsets from 2 to N the union of * each M-tuple sets has cardinality >= M. * * So what, you might say. As indeed I did. * But this is actually used here to check the possibility of each * code rule. If a code rule has a number of token_sets in the with * clause and a number of properties in the uses rule it must be * possible to do this from an empty fakestack. Hall helps. */ #define MAXHALL (TOKPATMAX+MAXALLREG) short hallsets[MAXHALL][SETSIZE]; int nhallsets= -1; int hallfreq[MAXHALL][2]; void hallverbose() { int i; int max; fprintf(stderr,"Table of hall frequencies\n # pre post\n"); for (max=MAXHALL-1;hallfreq[max][0]==0 && hallfreq[max][1]==0;max--) ; for (i=0;i<=max;i++) fprintf(stderr,"%3d%6d%6d\n",i,hallfreq[i][0],hallfreq[i][1]); } void inithall() { assert(nhallsets == -1); nhallsets=0; } void nexthall(short *sp) { int i; assert(nhallsets>=0); for(i=0;i=0); if (!hall()) error("Hall says: \"You can't have those registers\""); } int hall() { int i,j,k; int ok; hallfreq[nhallsets][0]++; /* * If a set has cardinality >= nhallsets it can never be the cause * of the hall algorithm failing. So it can be thrown away. * But then nhallsets is less, so this step can be re-applied. */ do { ok = 0; for(i=0;i=nhallsets) { for (j=i+1;j