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