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