unssa.c

   1 /*
   2  * UnSSA - translate the SSA back to normal form.
   3  *
   4  * For now it's done by replacing to set of copies:
   5  * 1) For each phi-node, replace all their phisrc by copies to a common
   6  *    temporary.
   7  * 2) Replace all the phi-nodes by copies of the temporaries to the phi-node target.
   8  *    This is node to preserve the semantic of the phi-node (they should all "execute"
   9  *    simultaneously on entry in the basic block in which they belong).
  10  *
  11  * This is similar to the "Sreedhar method I" except that the copies to the
  12  * temporaries are not placed at the end of the predecessor basic blocks, but
  13  * at the place where the phi-node operands are defined.
  14  * This is particulary easy since these copies are essentialy already present
  15  * as the corresponding OP_PHISOURCE.
  16  *
  17  * While very simple this method create a lot more copies that really necessary.
  18  * We eliminate some of these copies but most probably most of them are still
  19  * useless.
  20  * Ideally, "Sreedhar method III" should be used:
  21  * "Translating Out of Static Single Assignment Form", V. C. Sreedhar, R. D.-C. Ju,
  22  * D. M. Gillies and V. Santhanam.  SAS'99, Vol. 1694 of Lecture Notes in Computer
  23  * Science, Springer-Verlag, pp. 194-210, 1999.
  24  * But for this we need precise liveness, on each %phi and not only on OP_PHI's
  25  * target pseudos.
  26  *
  27  * Copyright (C) 2005 Luc Van Oostenryck
  28  */
  29
  30 #include "lib.h"
  31 #include "linearize.h"
  32 #include "allocate.h"
  33 #include "flow.h"
  34 #include <assert.h>
  35
  36
  37 static inline int nbr_pseudo_users(pseudo_t p)
  38 {
  39         return ptr_list_size((struct ptr_list *)p->users);
  40 }
  41
  42 static int simplify_phi_node(struct instruction *phi, pseudo_t tmp)
  43 {
  44         pseudo_t target = phi->target;
  45         struct pseudo_user *pu;
  46         pseudo_t src;
  47
  48         // verify if this phi can be simplified
  49         FOR_EACH_PTR(phi->phi_list, src) {
  50                 struct instruction *def = src->def;
  51
  52                 if (!def)
  53                         continue;
  54                 if (def->bb == phi->bb)
  55                         return 0;
  56         } END_FOR_EACH_PTR(src);
  57
  58         // no need to make a copy of this one
  59         // -> replace the target pseudo by the tmp
  60         FOR_EACH_PTR(target->users, pu) {
  61                 use_pseudo(pu->insn, tmp, pu->userp);
  62         } END_FOR_EACH_PTR(pu);
  63
  64         phi->bb = NULL;
  65         return 1;
  66 }
  67
  68 static void replace_phi_node(struct instruction *phi)
  69 {
  70         pseudo_t tmp;
  71         pseudo_t p;
  72
  73         tmp = alloc_pseudo(NULL);
  74         tmp->type = phi->target->type;
  75         tmp->ident = phi->target->ident;
  76         tmp->def = NULL;                // defined by all the phisrc
  77
  78         // can we avoid to make of copy?
  79         simplify_phi_node(phi, tmp);
  80
  81         // rewrite all it's phi_src to copy to a new tmp
  82         FOR_EACH_PTR(phi->phi_list, p) {
  83                 struct instruction *def = p->def;
  84                 pseudo_t src;
  85
  86                 if (p == VOID)
  87                         continue;
  88
  89                 assert(def->opcode == OP_PHISOURCE);
  90
  91                 def->opcode = OP_COPY;
  92                 def->target = tmp;
  93
  94                 // can we eliminate the copy?
  95                 src = def->phi_src;
  96                 if (src->type != PSEUDO_REG)
  97                         continue;
  98                 switch (nbr_pseudo_users(src)) {
  99                         struct instruction *insn;
 100                 case 1:
 101                         insn = src->def;
 102                         if (!insn)
 103                                 break;
 104                         insn->target = tmp;
 105                 case 0:
 106                         kill_instruction(def);
 107                         def->bb = NULL;
 108                 }
 109         } END_FOR_EACH_PTR(p);
 110
 111         if (!phi->bb)
 112                 return;
 113
 114         // rewrite the phi node:
 115         //      phi     %rt, ...
 116         // to:
 117         //      copy    %rt, %tmp
 118         phi->opcode = OP_COPY;
 119         use_pseudo(phi, tmp, &phi->src);
 120 }
 121
 122 static void rewrite_phi_bb(struct basic_block *bb)
 123 {
 124         struct instruction *insn;
 125
 126         // Replace all the phi-nodes by copies of a temporary
 127         // (which represent the set of all the %phi that feed them).
 128         // The target pseudo doesn't change.
 129         FOR_EACH_PTR(bb->insns, insn) {
 130                 if (!insn->bb)
 131                         continue;
 132                 if (insn->opcode != OP_PHI)
 133                         continue;
 134                 replace_phi_node(insn);
 135         } END_FOR_EACH_PTR(insn);
 136 }
 137
 138 int unssa(struct entrypoint *ep)
 139 {
 140         struct basic_block *bb;
 141
 142         FOR_EACH_PTR(ep->bbs, bb) {
 143                 rewrite_phi_bb(bb);
 144         } END_FOR_EACH_PTR(bb);
 145
 146         return 0;
 147 }