001 //Part 3,Register allocater 002 003 004 #include "Parser"; 005 <1>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 //To do this,we first do live-variable anaylsis: 037 //This will detirmine what variables are alive at what points 038 <2>039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 U0 AddVarName(U8 *name) { 066 static I64 cnt=1; 067 if(!FramePtr(name)) { 068 U8 *reverse=MStrPrint("VAR%d",cnt); 069 FramePtrAdd(reverse,StrNew(name)); 070 FramePtrAdd(name,cnt++); 071 Free(reverse); 072 } 073 } 074 I64 VarNameToNumber(U8 *name) { 075 I64 r=FramePtr(name); 076 077 if(!HashFind(name,Fs->hash_table,HTT_FRAME_PTR)) { 078 AddVarName(name); 079 r=FramePtr(name); 080 } 081 return r; 082 } 083 U8 *NumberToVarName(I64 cnt) { 084 U8 *reverse=MStrPrint("VAR%d",cnt); 085 U8 *name=FramePtr(reverse); 086 Free(reverse); 087 return name; 088 } 089 U0 SetVarNumber(U8 *name,I64 num) { 090 FramePtrSet(name,num); 091 } 092 093 U0 ScanNames(CAST *a,CI64Set *add_to) { 094 if(!a) return; 095 switch(a->type) { 096 case ASTT_NAME: 097 I64SetAdd(add_to,VarNameToNumber(a->name)); 098 break; 099 case ASTT_GOSUB: 100 case ASTT_GOTO: 101 case ASTT_OPERATOR: 102 case ASTT_PRINT: 103 case ASTT_GET: 104 ScanNames(a->left,add_to); 105 ScanNames(a->right,add_to); 106 break; 107 } 108 } 109 U0 I64SetAddAll(CI64Set *to, CI64Set *from) { 110 I64 c=from->cnt,idx; 111 while(--c>=0) { 112 I64SetRem(to,from->body[c]); //Remove old occurances to avoid multiple 113 I64SetAdd(to,from->body[c]); 114 } 115 } 116 U0 I64SetRemAll(CI64Set *to, CI64Set *from) { 117 I64 c=from->cnt; 118 while(--c>=0) { 119 I64SetRem(to,from->body[c]); 120 } 121 } 122 extern U0 ComputeIncomingOutgoing(CI64Set *asts); 123 U0 LiveAnaylsis(CI64Set *asts,Bool display=FALSE) { 124 I64 idx,idx2,idx3; 125 Bool changed=TRUE; 126 CAST *tmp,*next; 127 CI64Set *orig; 128 ComputeIncomingOutgoing(asts); 129 for(idx=0;idx!=asts->cnt;idx++) { 130 tmp=asts->body[idx]; 131 tmp->kill=I64SetNew; 132 tmp->read=I64SetNew; 133 tmp->alive=I64SetNew; 134 if(tmp->type==ASTT_OPERATOR&&!StrCmp(tmp->name,"=")) { 135 kill: 136 I64SetAdd(tmp->kill,VarNameToNumber(tmp->left->name)); //left=EXPR 137 ScanNames(tmp->right,tmp->read); 138 } else if(tmp->type==ASTT_GET) { 139 goto kill; 140 } else 141 ScanNames(tmp,tmp->read); 142 } 143 while(changed) { 144 changed=FALSE; 145 for(idx=0;idx<asts->cnt;idx++) { 146 tmp=asts->body[idx]; 147 orig=tmp->alive; 148 tmp->alive=I64SetNew; 149 I64SetAddAll(tmp->alive,tmp->read); 150 for(idx2=0;idx2!=tmp->outgoing->cnt;idx2++) { 151 next=tmp->outgoing->body[idx2]; 152 I64SetAddAll(tmp->alive,next->alive); 153 } 154 I64SetRemAll(tmp->alive,tmp->kill); 155 I64SetAddAll(tmp->alive,tmp->read); //Account for read before kill 156 if(orig->cnt!=tmp->alive->cnt) 157 changed=TRUE; 158 I64SetDel(orig); 159 160 if(display) { 161 DocClear; 162 DocLock(DocPut); 163 for(idx2=asts->cnt-1;idx2>=0;idx2--) { 164 tmp=asts->body[idx2]; 165 if(idx2==idx) "$FD$HERE==> "; 166 else " "; 167 DumpASTFlat(tmp); 168 " Alive: $BROWN$"; 169 for(idx3=0;idx3!=tmp->alive->cnt;idx3++) { 170 if(idx3) ","; 171 "%s",NumberToVarName(tmp->alive->body[idx3]); 172 } 173 "\n"; 174 } 175 DocUnlock(DocPut); 176 Sleep(200); 177 "$FD$"; 178 } 179 } 180 } 181 } 182 183 CI64Set *ParseToStatements(U8 *str) { 184 CAST *s; 185 CI64Set *ret=I64SetNew; 186 CLexer *l=LexerNew(str); 187 Lex(l); 188 while(s=PrsStmt(l)) { 189 I64SetAdd(ret,s); 190 } 191 return ret; 192 } 193 194 // 195 // Do not Read section 196 // 197 CAST *FindLabel(U8 *name,CI64Set *asts) { 198 CAST *tmp; 199 I64 idx; 200 for(idx=0;idx!=asts->cnt;idx++) { 201 tmp=asts->body[idx]; 202 if(tmp->type==ASTT_LABEL&&!StrCmp(name,tmp->name)) 203 return tmp; 204 } 205 "Undefined label \"%s\"\n",name; 206 throw('Compiler'); 207 } 208 CI64Set *FindEndSubs(U8 *for_label,CI64Set *asts,Bool mark_false=TRUE) { 209 I64 idx,start_idx=-1; 210 CI64Set *ret=I64SetNew,*recurse; 211 CAST *tmp; 212 for(idx=0;idx!=asts->cnt;idx++) { 213 tmp=asts->body[idx]; 214 if(mark_false) tmp->marked=FALSE; 215 if(tmp->type==ASTT_LABEL&&!StrCmp(for_label,tmp->name)) 216 start_idx=idx; 217 } 218 if(-1==start_idx) throw('Compiler'); 219 for(idx=start_idx;idx!=asts->cnt;idx++) { 220 tmp=asts->body[idx]; 221 if(!tmp->marked) { 222 tmp->marked=TRUE; 223 if(tmp->type==ASTT_GOTO) { 224 recurse=FindEndSubs(tmp->name,asts,FALSE); 225 I64SetAddAll(ret,recurse); 226 I64SetDel(recurse); 227 //->left is set on "GOTO label IF expr" 228 if(!tmp->left) break; 229 } else if(tmp->type==ASTT_ENDSUB) 230 break; 231 } 232 } 233 return ret; 234 } 235 U0 ComputeIncomingOutgoing(CI64Set *asts) { 236 I64 idx; 237 CAST *tmp,*label,*next; 238 CI64Set *returns; 239 for(idx=0;idx!=asts->cnt;idx++) { 240 tmp=asts->body[idx]; 241 tmp->incoming=I64SetNew; 242 tmp->outgoing=I64SetNew; 243 } 244 for(idx=0;idx!=asts->cnt;idx++) { 245 tmp=asts->body[idx]; 246 if(tmp->type==ASTT_ENDSUB) { 247 } else if(tmp->type==ASTT_GOTO) { 248 next=FindLabel(tmp->name,asts); 249 I64SetAdd(tmp->outgoing,next); 250 I64SetAdd(next->incoming,tmp); 251 if(tmp->left) //GOTO IF 252 goto normal; 253 } else if(tmp->type==ASTT_GOSUB) { 254 next=FindLabel(tmp->name,asts); 255 I64SetAdd(tmp->outgoing,next); 256 257 returns=FindEndSubs(tmp->name,asts); 258 259 if(idx+1<asts->cnt) { 260 next=asts->body[idx+1]; 261 I64SetAddAll(next->incoming,returns); 262 } 263 I64SetDel(returns); 264 } else { 265 normal: 266 if(idx+1<asts->cnt) { 267 next=asts->body[idx+1]; 268 I64SetAdd(tmp->outgoing,next); 269 I64SetAdd(next->incoming,tmp); 270 } 271 } 272 } 273 } 274 #if __CMD_LINE__ 275 CI64Set *stmts=ParseToStatements( 276 "cat=1\n" 277 "GOSUB abc\n" 278 "GOTO exit\n" 279 "LABEL abc\n" 280 "cat2=2\n" 281 "person=3\n" 282 "GOTO pass IF cat + cat2\n" 283 "potato=4\n" 284 "GOTO end\n" 285 "LABEL pass\n" 286 "potato=5\n" 287 "LABEL end\n" 288 "show=potato * person \n" 289 "ENDSUB\n" 290 "LABEL exit\n" 291 ); 292 LiveAnaylsis(stmts,TRUE); 293 #endif