001 002 #include "RegAlloc.HC"; 003 // 004 // <1>005 // 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 // Value numbering is simple,first "group" the instructions by liveness, 049 // then assign the variables numbers 050 051 U0 RenumberNode(CAST *a,U8 *new_name,U8 *old_name) { 052 if(!a) return; 053 switch(a->type) { 054 case ASTT_NAME: 055 if(!StrCmp(a->name,old_name)) 056 StrCpy(a->name,new_name); 057 break; 058 case ASTT_GOSUB: 059 case ASTT_GOTO: 060 case ASTT_OPERATOR: 061 case ASTT_PRINT: 062 case ASTT_GET: 063 RenumberNode(a->left,new_name,old_name); 064 RenumberNode(a->right,new_name,old_name); 065 break; 066 } 067 } 068 069 070 071 072 Bool GetGlobsForVar(CI64Set *asts,I64 start_at,I64 for_var,I64 renumber_as) { 073 CAST *ast,*tmp; 074 I64 idx,has_var,pass=FALSE; 075 U8 new_name[STR_LEN]; 076 Bool found_kill; 077 StrPrint(new_name,"%s.%d",NumberToVarName(for_var),renumber_as); 078 AddVarName(new_name); 079 CI64Set *to_check=I64SetNew; 080 CI64Set *visited=I64SetNew; 081 I64SetAdd(to_check,asts->body[start_at]); 082 while(to_check->cnt) { 083 ast=to_check->body[0]; 084 I64SetRem(to_check,ast); 085 I64SetAdd(visited,ast); 086 has_var=FALSE; 087 for(idx=0;idx!=ast->alive->cnt;idx++) { 088 tmp=ast->alive->body[idx]; 089 if(tmp==for_var) { 090 RenumberNode(ast,new_name,NumberToVarName(for_var)); 091 ast->alive->body[idx]=VarNameToNumber(new_name); 092 has_var=TRUE; 093 pass=TRUE; 094 } 095 } 096 found_kill=FALSE; 097 for(idx=0;idx!=ast->kill->cnt;idx++) { 098 tmp=ast->kill->body[idx]; 099 if(tmp==for_var) { 100 RenumberNode(ast,new_name,NumberToVarName(for_var)); 101 ast->kill->body[idx]=VarNameToNumber(new_name); 102 has_var=TRUE; 103 found_kill=TRUE; 104 pass=TRUE; 105 } 106 } 107 if(has_var) { 108 I64SetAddAll(to_check,ast->incoming); 109 I64SetAddAll(to_check,ast->outgoing); 110 I64SetRemAll(to_check,visited); 111 } 112 } 113 I64SetDel(to_check); 114 I64SetDel(visited); 115 return pass; 116 } 117 U0 RenumberVars(CI64Set *asts) { 118 CI64Set *canidates=I64SetNew; 119 CI64Set *visited=I64SetNew; 120 CAST *ast; 121 I64 idx,idx2,tmp; 122 I64 version_num=0; 123 for(idx=0;idx!=asts->cnt;idx++) { 124 ast=asts->body[idx]; 125 for(idx2=0;idx2!=ast->alive->cnt;idx2++) { 126 tmp=ast->alive->body[idx2]; 127 I64SetRem(canidates,tmp); //Ensure only 1 occurance 128 I64SetAdd(canidates,tmp); 129 } 130 for(idx2=0;idx2!=ast->kill->cnt;idx2++) { 131 tmp=ast->kill->body[idx2]; 132 I64SetRem(canidates,tmp); //Ensure only 1 occurance 133 I64SetAdd(canidates,tmp); 134 } 135 } 136 for(idx2=0;idx2!=canidates->cnt;idx2++) { 137 version_num=0; 138 for(idx=0;idx!=asts->cnt;idx++) { 139 if(GetGlobsForVar(asts,idx,canidates->body[idx2],version_num)) 140 version_num++; 141 } 142 } 143 I64SetDel(visited); 144 I64SetDel(canidates); 145 } 146 147 #if __CMD_LINE__ 148 CI64Set *asts=ParseToStatements( 149 "a=1\n" 150 "b=1\n" 151 "d=a+b\n" 152 "c=a\n" 153 "b=1+a\n" 154 "d=b+c\n" 155 ); 156 LiveAnaylsis(asts); 157 WinMax; 158 DocClear; 159 DrawGraph(CreateGraphColoring(asts)); 160 RenumberVars(asts); 161 I64 idx=0; 162 for(idx=0;idx!=asts->cnt;idx++) 163 DumpAST(asts->body[idx]); 164 WinMax; 165 LiveAnaylsis(asts); 166 DrawGraph(CreateGraphColoring(asts)); 167 168 169 170 171 //Without Renumbering(4 registers in use) 172 <2>173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 // 216 // With recoloring,3 colors 217 // 218 219 <3>220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 #endif