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