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