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