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_SETVAL:
  96         case OP_SETFVAL:
  97                 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_CALL:
 115                 USES(func);
 116                 if (insn->target != VOID)
 117                         DEFINES(target);
 118                 FOR_EACH_PTR(insn->arguments, pseudo) {
 119                         use(bb, pseudo);
 120                 } END_FOR_EACH_PTR(pseudo);
 121                 break;
 122
 123         case OP_SLICE:
 124                 USES(base); DEFINES(target);
 125                 break;
 126
 127         case OP_ASM:
 128                 asm_liveness(bb, insn, def, use);
 129                 break;
 130
 131         case OP_RANGE:
 132                 USES(src1); USES(src2); USES(src3);
 133                 break;
 134
 135         case OP_BADOP:
 136         case OP_NOP:
 137         case OP_CONTEXT:
 138                 break;
 139         }
 140 }
 141
 142
 143 static int liveness_changed;
 144
 145 static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
 146 {
 147         if (!pseudo_in_list(*list, pseudo)) {
 148                 liveness_changed = 1;
 149                 add_pseudo(list, pseudo);
 150         }
 151 }
 152
 153 static inline int trackable_pseudo(pseudo_t pseudo)
 154 {
 155         return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
 156 }
 157
 158 static void insn_uses(struct basic_block *bb, pseudo_t pseudo)
 159 {
 160         if (trackable_pseudo(pseudo)) {
 161                 struct instruction *def = pseudo->def;
 162                 if (pseudo->type != PSEUDO_REG || def->bb != bb || def->opcode == OP_PHI)
 163                         add_pseudo_exclusive(&bb->needs, pseudo);
 164         }
 165 }
 166
 167 static void insn_defines(struct basic_block *bb, pseudo_t pseudo)
 168 {
 169         assert(trackable_pseudo(pseudo));
 170         add_pseudo(&bb->defines, pseudo);
 171 }
 172
 173 static void track_bb_liveness(struct basic_block *bb)
 174 {
 175         pseudo_t needs;
 176
 177         FOR_EACH_PTR(bb->needs, needs) {
 178                 struct basic_block *parent;
 179                 FOR_EACH_PTR(bb->parents, parent) {
 180                         if (!pseudo_in_list(parent->defines, needs)) {
 181                                 add_pseudo_exclusive(&parent->needs, needs);
 182                         }
 183                 } END_FOR_EACH_PTR(parent);
 184         } END_FOR_EACH_PTR(needs);
 185 }
 186
 187 /*
 188  * We need to clear the liveness information if we
 189  * are going to re-run it.
 190  */
 191 void clear_liveness(struct entrypoint *ep)
 192 {
 193         struct basic_block *bb;
 194
 195         FOR_EACH_PTR(ep->bbs, bb) {
 196                 free_ptr_list(&bb->needs);
 197                 free_ptr_list(&bb->defines);
 198         } END_FOR_EACH_PTR(bb);
 199 }
 200
 201 /*
 202  * Track inter-bb pseudo liveness. The intra-bb case
 203  * is purely local information.
 204  */
 205 void track_pseudo_liveness(struct entrypoint *ep)
 206 {
 207         struct basic_block *bb;
 208
 209         /* Add all the bb pseudo usage */
 210         FOR_EACH_PTR(ep->bbs, bb) {
 211                 struct instruction *insn;
 212                 FOR_EACH_PTR(bb->insns, insn) {
 213                         if (!insn->bb)
 214                                 continue;
 215                         assert(insn->bb == bb);
 216                         track_instruction_usage(bb, insn, insn_defines, insn_uses);
 217                 } END_FOR_EACH_PTR(insn);
 218         } END_FOR_EACH_PTR(bb);
 219
 220         /* Calculate liveness.. */
 221         do {
 222                 liveness_changed = 0;
 223                 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
 224                         track_bb_liveness(bb);
 225                 } END_FOR_EACH_PTR_REVERSE(bb);
 226         } while (liveness_changed);
 227
 228         /* Remove the pseudos from the "defines" list that are used internally */
 229         FOR_EACH_PTR(ep->bbs, bb) {
 230                 pseudo_t def;
 231                 FOR_EACH_PTR(bb->defines, def) {
 232                         struct basic_block *child;
 233                         FOR_EACH_PTR(bb->children, child) {
 234                                 if (pseudo_in_list(child->needs, def))
 235                                         goto is_used;
 236                         } END_FOR_EACH_PTR(child);
 237                         DELETE_CURRENT_PTR(def);
 238 is_used:
 239                 ;
 240                 } END_FOR_EACH_PTR(def);
 241                 PACK_PTR_LIST(&bb->defines);
 242         } END_FOR_EACH_PTR(bb);
 243 }
 244
 245 static void merge_pseudo_list(struct pseudo_list *src, struct pseudo_list **dest)
 246 {
 247         pseudo_t pseudo;
 248         FOR_EACH_PTR(src, pseudo) {
 249                 add_pseudo_exclusive(dest, pseudo);
 250         } END_FOR_EACH_PTR(pseudo);
 251 }
 252
 253 static void track_phi_uses(struct instruction *insn)
 254 {
 255         pseudo_t phi;
 256         FOR_EACH_PTR(insn->phi_list, phi) {
 257                 struct instruction *def;
 258                 if (phi == VOID || !phi->def)
 259                         continue;
 260                 def = phi->def;
 261                 assert(def->opcode == OP_PHISOURCE);
 262                 add_ptr_list(&def->phi_users, insn);
 263         } END_FOR_EACH_PTR(phi);
 264 }
 265
 266 static void track_bb_phi_uses(struct basic_block *bb)
 267 {
 268         struct instruction *insn;
 269         FOR_EACH_PTR(bb->insns, insn) {
 270                 if (insn->bb && insn->opcode == OP_PHI)
 271                         track_phi_uses(insn);
 272         } END_FOR_EACH_PTR(insn);
 273 }
 274
 275 static struct pseudo_list **live_list;
 276 static struct pseudo_list *dead_list;
 277
 278 static void death_def(struct basic_block *bb, pseudo_t pseudo)
 279 {
 280 }
 281
 282 static void death_use(struct basic_block *bb, pseudo_t pseudo)
 283 {
 284         if (trackable_pseudo(pseudo) && !pseudo_in_list(*live_list, pseudo)) {
 285                 add_pseudo(&dead_list, pseudo);
 286                 add_pseudo(live_list, pseudo);
 287         }
 288 }
 289
 290 static void track_pseudo_death_bb(struct basic_block *bb)
 291 {
 292         struct pseudo_list *live = NULL;
 293         struct basic_block *child;
 294         struct instruction *insn;
 295
 296         FOR_EACH_PTR(bb->children, child) {
 297                 merge_pseudo_list(child->needs, &live);
 298         } END_FOR_EACH_PTR(child);
 299
 300         live_list = &live;
 301         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
 302                 if (!insn->bb)
 303                         continue;
 304
 305                 dead_list = NULL;
 306                 track_instruction_usage(bb, insn, death_def, death_use);
 307                 if (dead_list) {
 308                         pseudo_t dead;
 309                         FOR_EACH_PTR(dead_list, dead) {
 310                                 struct instruction *deathnote = __alloc_instruction(0);
 311                                 deathnote->bb = bb;
 312                                 deathnote->opcode = OP_DEATHNOTE;
 313                                 deathnote->target = dead;
 314                                 INSERT_CURRENT(deathnote, insn);
 315                         } END_FOR_EACH_PTR(dead);
 316                         free_ptr_list(&dead_list);
 317                 }
 318         } END_FOR_EACH_PTR_REVERSE(insn);
 319         free_ptr_list(&live);
 320 }
 321
 322 void track_pseudo_death(struct entrypoint *ep)
 323 {
 324         struct basic_block *bb;
 325
 326         FOR_EACH_PTR(ep->bbs, bb) {
 327                 track_bb_phi_uses(bb);
 328         } END_FOR_EACH_PTR(bb);
 329
 330         FOR_EACH_PTR(ep->bbs, bb) {
 331                 track_pseudo_death_bb(bb);
 332         } END_FOR_EACH_PTR(bb);
 333 }