liveness.c

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