1 /* 2 * Register - track pseudo usage, maybe eventually try to do register 3 * allocation. 4 * 5 * Copyright (C) 2004 Linus Torvalds 6 */ 7 8 #include <assert.h> 9 10 #include "parse.h" 11 #include "expression.h" 12 #include "linearize.h" 13 #include "flow.h" 14 15 static void phi_defines(struct instruction * phi_node, pseudo_t target, 16 void (*defines)(struct basic_block *, pseudo_t)) 17 { 18 pseudo_t phi; 19 FOR_EACH_PTR(phi_node->phi_list, phi) { 20 struct instruction *def; 21 if (phi == VOID) 22 continue; 23 def = phi->def; 24 if (!def || !def->bb) 25 continue; 26 defines(def->bb, target); 27 } END_FOR_EACH_PTR(phi); 28 } 29 30 static void asm_liveness(struct basic_block *bb, struct instruction *insn, 31 void (*def)(struct basic_block *, pseudo_t), 32 void (*use)(struct basic_block *, pseudo_t)) 33 { 34 struct asm_constraint *entry; 35 36 FOR_EACH_PTR(insn->asm_rules->inputs, entry) { 37 use(bb, entry->pseudo); 38 } END_FOR_EACH_PTR(entry); 39 40 FOR_EACH_PTR(insn->asm_rules->outputs, entry) { 41 def(bb, entry->pseudo); 42 } END_FOR_EACH_PTR(entry); 43 } 44 45 static void track_instruction_usage(struct basic_block *bb, struct instruction *insn, 46 void (*def)(struct basic_block *, pseudo_t), 47 void (*use)(struct basic_block *, pseudo_t)) 48 { 49 pseudo_t pseudo; 50 51 #define USES(x) use(bb, insn->x) 52 #define DEFINES(x) def(bb, insn->x) 53 54 switch (insn->opcode) { 55 case OP_RET: 56 USES(src); 57 break; 58 59 case OP_CBR: 60 case OP_SWITCH: 61 USES(cond); 62 break; 63 64 case OP_COMPUTEDGOTO: 65 USES(target); 66 break; 67 68 /* Binary */ 69 case OP_BINARY ... OP_BINARY_END: 70 case OP_BINCMP ... OP_BINCMP_END: 71 USES(src1); USES(src2); DEFINES(target); 72 break; 73 74 /* Uni */ 75 case OP_NOT: case OP_NEG: 76 USES(src1); DEFINES(target); 77 break; 78 79 case OP_SEL: 80 USES(src1); USES(src2); USES(src3); DEFINES(target); 81 break; 82 83 /* Memory */ 84 case OP_LOAD: 85 USES(src); DEFINES(target); 86 break; 87 88 case OP_STORE: 89 USES(src); USES(target); 90 break; 91 92 case OP_SETVAL: 93 DEFINES(target); 94 break; 95 96 case OP_SYMADDR: 97 USES(symbol); DEFINES(target); 98 break; 99 100 /* Other */ 101 case OP_PHI: 102 /* Phi-nodes are "backwards" nodes. Their def doesn't matter */ 103 phi_defines(insn, insn->target, def); 104 break; 105 106 case OP_PHISOURCE: 107 /* 108 * We don't care about the phi-source define, they get set 109 * up and expanded by the OP_PHI 110 */ 111 USES(phi_src); 112 break; 113 114 case OP_CAST: 115 case OP_SCAST: 116 case OP_FPCAST: 117 case OP_PTRCAST: 118 USES(src); DEFINES(target); 119 break; 120 121 case OP_CALL: 122 USES(func); 123 if (insn->target != VOID) 124 DEFINES(target); 125 FOR_EACH_PTR(insn->arguments, pseudo) { 126 use(bb, pseudo); 127 } END_FOR_EACH_PTR(pseudo); 128 break; 129 130 case OP_SLICE: 131 USES(base); DEFINES(target); 132 break; 133 134 case OP_ASM: 135 asm_liveness(bb, insn, def, use); 136 break; 137 138 case OP_RANGE: 139 USES(src1); USES(src2); USES(src3); 140 break; 141 142 case OP_BADOP: 143 case OP_INVOKE: 144 case OP_UNWIND: 145 case OP_MALLOC: 146 case OP_FREE: 147 case OP_ALLOCA: 148 case OP_GET_ELEMENT_PTR: 149 case OP_VANEXT: 150 case OP_VAARG: 151 case OP_SNOP: 152 case OP_LNOP: 153 case OP_NOP: 154 case OP_CONTEXT: 155 break; 156 } 157 } 158 159 int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo) 160 { 161 pseudo_t old; 162 FOR_EACH_PTR(list,old) { 163 if (old == pseudo) 164 return 1; 165 } END_FOR_EACH_PTR(old); 166 return 0; 167 } 168 169 static int liveness_changed; 170 171 static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo) 172 { 173 if (!pseudo_in_list(*list, pseudo)) { 174 liveness_changed = 1; 175 add_pseudo(list, pseudo); 176 } 177 } 178 179 static inline int trackable_pseudo(pseudo_t pseudo) 180 { 181 return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG); 182 } 183 184 static void insn_uses(struct basic_block *bb, pseudo_t pseudo) 185 { 186 if (trackable_pseudo(pseudo)) { 187 struct instruction *def = pseudo->def; 188 if (pseudo->type != PSEUDO_REG || def->bb != bb || def->opcode == OP_PHI) 189 add_pseudo_exclusive(&bb->needs, pseudo); 190 } 191 } 192 193 static void insn_defines(struct basic_block *bb, pseudo_t pseudo) 194 { 195 assert(trackable_pseudo(pseudo)); 196 add_pseudo(&bb->defines, pseudo); 197 } 198 199 static void track_bb_liveness(struct basic_block *bb) 200 { 201 pseudo_t needs; 202 203 FOR_EACH_PTR(bb->needs, needs) { 204 struct basic_block *parent; 205 FOR_EACH_PTR(bb->parents, parent) { 206 if (!pseudo_in_list(parent->defines, needs)) { 207 add_pseudo_exclusive(&parent->needs, needs); 208 } 209 } END_FOR_EACH_PTR(parent); 210 } END_FOR_EACH_PTR(needs); 211 } 212 213 /* 214 * We need to clear the liveness information if we 215 * are going to re-run it. 216 */ 217 void clear_liveness(struct entrypoint *ep) 218 { 219 struct basic_block *bb; 220 221 FOR_EACH_PTR(ep->bbs, bb) { 222 free_ptr_list(&bb->needs); 223 free_ptr_list(&bb->defines); 224 } END_FOR_EACH_PTR(bb); 225 } 226 227 /* 228 * Track inter-bb pseudo liveness. The intra-bb case 229 * is purely local information. 230 */ 231 void track_pseudo_liveness(struct entrypoint *ep) 232 { 233 struct basic_block *bb; 234 235 /* Add all the bb pseudo usage */ 236 FOR_EACH_PTR(ep->bbs, bb) { 237 struct instruction *insn; 238 FOR_EACH_PTR(bb->insns, insn) { 239 if (!insn->bb) 240 continue; 241 assert(insn->bb == bb); 242 track_instruction_usage(bb, insn, insn_defines, insn_uses); 243 } END_FOR_EACH_PTR(insn); 244 } END_FOR_EACH_PTR(bb); 245 246 /* Calculate liveness.. */ 247 do { 248 liveness_changed = 0; 249 FOR_EACH_PTR_REVERSE(ep->bbs, bb) { 250 track_bb_liveness(bb); 251 } END_FOR_EACH_PTR_REVERSE(bb); 252 } while (liveness_changed); 253 254 /* Remove the pseudos from the "defines" list that are used internally */ 255 FOR_EACH_PTR(ep->bbs, bb) { 256 pseudo_t def; 257 FOR_EACH_PTR(bb->defines, def) { 258 struct basic_block *child; 259 FOR_EACH_PTR(bb->children, child) { 260 if (pseudo_in_list(child->needs, def)) 261 goto is_used; 262 } END_FOR_EACH_PTR(child); 263 DELETE_CURRENT_PTR(def); 264 is_used: 265 ; 266 } END_FOR_EACH_PTR(def); 267 PACK_PTR_LIST(&bb->defines); 268 } END_FOR_EACH_PTR(bb); 269 } 270 271 static void merge_pseudo_list(struct pseudo_list *src, struct pseudo_list **dest) 272 { 273 pseudo_t pseudo; 274 FOR_EACH_PTR(src, pseudo) { 275 add_pseudo_exclusive(dest, pseudo); 276 } END_FOR_EACH_PTR(pseudo); 277 } 278 279 void track_phi_uses(struct instruction *insn) 280 { 281 pseudo_t phi; 282 FOR_EACH_PTR(insn->phi_list, phi) { 283 struct instruction *def; 284 if (phi == VOID || !phi->def) 285 continue; 286 def = phi->def; 287 assert(def->opcode == OP_PHISOURCE); 288 add_ptr_list(&def->phi_users, insn); 289 } END_FOR_EACH_PTR(phi); 290 } 291 292 static void track_bb_phi_uses(struct basic_block *bb) 293 { 294 struct instruction *insn; 295 FOR_EACH_PTR(bb->insns, insn) { 296 if (insn->bb && insn->opcode == OP_PHI) 297 track_phi_uses(insn); 298 } END_FOR_EACH_PTR(insn); 299 } 300 301 static struct pseudo_list **live_list; 302 static struct pseudo_list *dead_list; 303 304 static void death_def(struct basic_block *bb, pseudo_t pseudo) 305 { 306 } 307 308 static void death_use(struct basic_block *bb, pseudo_t pseudo) 309 { 310 if (trackable_pseudo(pseudo) && !pseudo_in_list(*live_list, pseudo)) { 311 add_pseudo(&dead_list, pseudo); 312 add_pseudo(live_list, pseudo); 313 } 314 } 315 316 static void track_pseudo_death_bb(struct basic_block *bb) 317 { 318 struct pseudo_list *live = NULL; 319 struct basic_block *child; 320 struct instruction *insn; 321 322 FOR_EACH_PTR(bb->children, child) { 323 merge_pseudo_list(child->needs, &live); 324 } END_FOR_EACH_PTR(child); 325 326 live_list = &live; 327 FOR_EACH_PTR_REVERSE(bb->insns, insn) { 328 if (!insn->bb) 329 continue; 330 331 dead_list = NULL; 332 track_instruction_usage(bb, insn, death_def, death_use); 333 if (dead_list) { 334 pseudo_t dead; 335 FOR_EACH_PTR(dead_list, dead) { 336 struct instruction *deathnote = __alloc_instruction(0); 337 deathnote->bb = bb; 338 deathnote->opcode = OP_DEATHNOTE; 339 deathnote->target = dead; 340 INSERT_CURRENT(deathnote, insn); 341 } END_FOR_EACH_PTR(dead); 342 free_ptr_list(&dead_list); 343 } 344 } END_FOR_EACH_PTR_REVERSE(insn); 345 free_ptr_list(&live); 346 } 347 348 void track_pseudo_death(struct entrypoint *ep) 349 { 350 struct basic_block *bb; 351 352 FOR_EACH_PTR(ep->bbs, bb) { 353 track_bb_phi_uses(bb); 354 } END_FOR_EACH_PTR(bb); 355 356 FOR_EACH_PTR(ep->bbs, bb) { 357 track_pseudo_death_bb(bb); 358 } END_FOR_EACH_PTR(bb); 359 } 360