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                 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 }