001 //Lesson 4 002 003 #include "LiveVar.HC"; 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 <2>037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 class CGraph { 059 CHashTable *connects; 060 I64 min_node_num; 061 I64 max_node_num; 062 I64 *colors; 063 }; 064 CGraph *GraphNew() { 065 CGraph *g=CAlloc(sizeof CGraph); 066 g->connects=HashTableNew(0x20); 067 g->min_node_num=I64_MAX; 068 return g; 069 } 070 Bool GraphIsConnectedTo(CGraph *g,I64 a,I64 b) { 071 U8 *name=MStrPrint("%d->%d",a,b); 072 CHashGeneric *f=HashFind(name,g->connects,HTT_FRAME_PTR); 073 Free(name); 074 if(f) 075 return TRUE; 076 return FALSE; 077 } 078 U0 GraphConnect(CGraph *g,I64 a,I64 b) { 079 if(GraphIsConnectedTo(g,a,b)) return; 080 U8 *name=MStrPrint("%d->%d",a,b); 081 CHashGeneric *gen=CAlloc(sizeof CHashGeneric); 082 gen->type=HTT_FRAME_PTR; 083 gen->str=name; 084 gen->user_data1=1; 085 g->max_node_num=MaxI64(g->max_node_num,a); 086 g->max_node_num=MaxI64(g->max_node_num,b); 087 g->min_node_num=MinI64(g->min_node_num,a); 088 g->min_node_num=MinI64(g->min_node_num,b); 089 HashAdd(gen,g->connects); 090 } 091 CGraph *CreateGraphColoring(CI64Set *asts) { 092 I64 idx,idx2,idx3; 093 CGraph *interfere=GraphNew; 094 CAST *tmp; 095 I64 *colors; 096 I64 color_cnt,old_color; 097 I64 cnt; 098 I64 run=0; 099 I64 used_regs; 100 Bool false; 101 // 102 // First construct an motherfucking interference graph 103 // Find which fucking variables are alive at the same time 104 // 105 LiveAnaylsis(asts); 106 idx=asts->cnt; 107 while(--idx>=0) { 108 tmp=asts->body[idx]; 109 idx2=tmp->alive->cnt; 110 while(--idx2>=0) { 111 idx3=tmp->alive->cnt; 112 while(--idx3>=0) { 113 GraphConnect(interfere, 114 tmp->alive->body[idx2], 115 tmp->alive->body[idx3]); 116 GraphConnect(interfere, 117 tmp->alive->body[idx3], 118 tmp->alive->body[idx2]); 119 } 120 //Account for kills too 121 idx3=tmp->kill->cnt; 122 while(--idx3>=0) { 123 GraphConnect(interfere, 124 tmp->alive->body[idx2], 125 tmp->kill->body[idx3]); 126 GraphConnect(interfere, 127 tmp->kill->body[idx3], 128 tmp->alive->body[idx2]); 129 } 130 } 131 } 132 // 133 //Second we color the graph,ask a genius for an effective method. 134 // An easy way to do this is to assume all 0s then correct the graph coloring to make sure no one has adjacent colors 135 // 136 cnt=1+interfere->max_node_num; 137 colors=CAlloc(cnt*8); 138 color_cnt=(2+5+1); //TempleOS ABI is RSI/RDI/R10-R15 139 for(idx=0;idx!=cnt;idx++) { 140 colors[idx]=0; 141 } 142 //Correct 143 for(cnt=0;cnt!=9;cnt++) { 144 for(idx=interfere->min_node_num;idx!=interfere->max_node_num+1;idx++) { 145 old_color=colors[idx]; 146 used_regs=0; 147 if(old_color!=-1) { 148 for(idx3=0;idx3!=color_cnt;idx3++) { 149 //Check if color is not adjacent 150 for(idx2=interfere->min_node_num;idx2!=interfere->max_node_num+1;idx2++) { 151 if(idx!=idx2) { 152 if(GraphIsConnectedTo(interfere,idx,idx2)) { 153 if(colors[idx2]==idx3) { 154 Bts(&used_regs,idx3); 155 goto next; 156 } 157 } 158 } 159 } 160 next: 161 } 162 //9 is last run so dont modiy except for marking as spill 163 if(cnt==9&&Bt(&used_regs,old_color)) { 164 colors[idx]=-1;//No avialble registers 165 } else if(cnt!=9) { 166 colors[idx]=Bsf(~used_regs);; 167 } 168 correct:; 169 } 170 } 171 } 172 interfere->colors=colors; 173 CI64Set *var_names=I64SetNew; 174 for(idx2=interfere->min_node_num;idx2!=interfere->max_node_num+1;idx2++) { 175 I64SetAdd(var_names,NumberToVarName(idx2)); 176 } 177 for(idx=0;idx!=var_names->cnt;idx++) { 178 SetVarNumber(var_names->body[idx],colors[idx+interfere->min_node_num]); 179 } 180 I64SetDel(var_names); 181 return interfere; 182 } 183 //Returns radius 184 #define BUBBLE_RADIUS 30. 185 U0 DrawBubble(F64 x,F64 y,U8 *text,I64 color) { 186 gr.dc->color=LTBLUE+color%5; 187 text=MStrPrint("%s(%d)",text,color); 188 I64 l=8*StrLen(text); 189 gr.dc->thick=2; 190 GrFillCircle(gr.dc,x+BUBBLE_RADIUS,y+BUBBLE_RADIUS,0,BUBBLE_RADIUS*2); 191 gr.dc->color=RED; 192 GrPutS(gr.dc,x+BUBBLE_RADIUS-l/2,y-4+BUBBLE_RADIUS,text); 193 Free(text); 194 } 195 U0 DrawBubbleConnect(F64 x,F64 y,F64 x2,F64 y2) { 196 gr.dc->color=BLACK; 197 gr.dc->thick=2; 198 F64 angle=Arg(x2-x,y2-y); 199 x+=BUBBLE_RADIUS*Cos(angle); 200 y+=BUBBLE_RADIUS*Sin(angle); 201 x2-=BUBBLE_RADIUS*Cos(angle); 202 y2-=BUBBLE_RADIUS*Sin(angle); 203 GrArrow3(gr.dc,x,y,0,x2,y2,0); 204 GrArrow3(gr.dc,x2,y2,0,x,y,0); 205 } 206 U0 DrawGraph(CGraph *c) { 207 I64 *colors=c->colors+c->min_node_num; 208 I64 cnt=c->max_node_num-c->min_node_num+1,idx,idx2,idx3; 209 Bool *useless_nodes=CAlloc(cnt); 210 for(idx=0;idx!=cnt;idx++) { 211 "%s:%d\n",NumberToVarName(idx+c->min_node_num),colors[idx]; 212 } 213 F64 *xs=CAlloc(cnt*8); 214 F64 *ys=CAlloc(cnt*8); 215 F64 *radius=CAlloc(cnt*8); 216 F64 angle; 217 for(idx=0;idx!=cnt;idx++) { 218 xs[idx]=100+(GR_WIDTH-200)*Rand; 219 ys[idx]=100+(GR_HEIGHT-200)*Rand; 220 } 221 for(idx=0;idx!=cnt;idx++) { 222 for(idx2=0;idx2!=cnt;idx2++) { 223 if(GraphIsConnectedTo(c,idx+c->min_node_num,idx2+c->min_node_num)) { 224 goto usefull; 225 } 226 } 227 useless_nodes[idx]=TRUE; 228 usefull:; 229 } 230 for(idx=0;idx!=10;idx++) //Try multiple times 231 //If close to other node,move 232 for(idx2=0;idx2!=cnt;idx2++) { 233 if(!useless_nodes[idx2]) 234 for(idx3=0;idx3!=cnt;idx3++) { 235 if(Sqrt(Sqr(xs[idx2]-xs[idx3])+Sqr(ys[idx2]-ys[idx3]))<100.&&idx2!=idx3) { 236 if(Rand>.5) { 237 xs[idx2]=xs[idx3]+BUBBLE_RADIUS*4; 238 } else if(Rand>.5) 239 xs[idx2]=xs[idx3]-BUBBLE_RADIUS*4; 240 if(Rand>.5) { 241 ys[idx2]=ys[idx3]+BUBBLE_RADIUS*4; 242 } else if(Rand>.5) 243 ys[idx2]=ys[idx3]-BUBBLE_RADIUS*4; 244 xs[idx2]=Clamp(xs[idx2],100,GR_WIDTH-100); 245 ys[idx2]=Clamp(ys[idx2],100,GR_HEIGHT-100); 246 } 247 } 248 } 249 DCFill; 250 for(idx=0;idx!=cnt;idx++) { 251 for(idx2=0;idx2!=cnt;idx2++) { 252 if(GraphIsConnectedTo(c,idx+c->min_node_num,idx2+c->min_node_num)) { 253 if(idx!=idx2) { 254 DrawBubbleConnect( 255 xs[idx]+BUBBLE_RADIUS, 256 ys[idx]+BUBBLE_RADIUS, 257 xs[idx2]+BUBBLE_RADIUS, 258 ys[idx2]+BUBBLE_RADIUS 259 ); 260 } 261 } 262 } 263 } 264 for(idx=0;idx!=cnt;idx++) { 265 if(!useless_nodes[idx]) 266 if(NumberToVarName(idx+c->min_node_num)) { 267 DrawBubble(xs[idx],ys[idx],NumberToVarName(idx+c->min_node_num),colors[idx]); 268 } 269 } 270 PressAKey; 271 DCFill; 272 Free(xs); 273 Free(ys); 274 Free(radius); 275 Free(useless_nodes); 276 } 277 #if __CMD_LINE__ 278 279 CI64Set *stmts=ParseToStatements( 280 "a=1\n" 281 "b=2\n" 282 "c=a+b\n" 283 "d=c\n" 284 ); 285 DrawGraph(CreateGraphColoring(stmts)); 286 //Possible result 287 <3>288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 #endif