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 int simplify_phi_node(struct instruction *phi, pseudo_t tmp)
  38 {
  39         pseudo_t target = phi->target;
  40         struct pseudo_user *pu;
  41         pseudo_t src;
  42
  43         // verify if this phi can be simplified
  44         FOR_EACH_PTR(phi->phi_list, src) {
  45                 struct instruction *def = src->def;
  46
  47                 if (!def)
  48                         continue;
  49                 if (def->bb == phi->bb)
  50                         return 0;
  51         } END_FOR_EACH_PTR(src);
  52
  53         // no need to make a copy of this one
  54         // -> replace the target pseudo by the tmp
  55         FOR_EACH_PTR(target->users, pu) {
  56                 use_pseudo(pu->insn, tmp, pu->userp);
  57         } END_FOR_EACH_PTR(pu);
  58
  59         phi->bb = NULL;
  60         return 1;
  61 }
  62
  63 static void replace_phi_node(struct instruction *phi)
  64 {
  65         pseudo_t tmp;
  66         pseudo_t p;
  67
  68         tmp = alloc_pseudo(NULL);
  69         tmp->type = phi->target->type;
  70         tmp->ident = phi->target->ident;
  71         tmp->def = NULL;                // defined by all the phisrc
  72
  73         // can we avoid to make of copy?
  74         simplify_phi_node(phi, tmp);
  75
  76         // rewrite all it's phi_src to copy to a new tmp
  77         FOR_EACH_PTR(phi->phi_list, p) {
  78                 struct instruction *def = p->def;
  79                 pseudo_t src;
  80
  81                 if (p == VOID)
  82                         continue;
  83
  84                 assert(def->opcode == OP_PHISOURCE);
  85
  86                 def->opcode = OP_COPY;
  87                 def->target = tmp;
  88
  89                 // can we eliminate the copy?
  90                 src = def->phi_src;
  91                 if (src->type != PSEUDO_REG)
  92                         continue;
  93                 switch (nbr_users(src)) {
  94                         struct instruction *insn;
  95                 case 1:
  96                         insn = src->def;
  97                         if (!insn)
  98                                 break;
  99                         insn->target = tmp;
 100                 case 0:
 101                         kill_instruction(def);
 102                         def->bb = NULL;
 103                 }
 104         } END_FOR_EACH_PTR(p);
 105
 106         if (!phi->bb)
 107                 return;
 108
 109         // rewrite the phi node:
 110         //      phi     %rt, ...
 111         // to:
 112         //      copy    %rt, %tmp
 113         phi->opcode = OP_COPY;
 114         use_pseudo(phi, tmp, &phi->src);
 115 }
 116
 117 static void rewrite_phi_bb(struct basic_block *bb)
 118 {
 119         struct instruction *insn;
 120
 121         // Replace all the phi-nodes by copies of a temporary
 122         // (which represent the set of all the %phi that feed them).
 123         // The target pseudo doesn't change.
 124         FOR_EACH_PTR(bb->insns, insn) {
 125                 if (!insn->bb)
 126                         continue;
 127                 if (insn->opcode != OP_PHI)
 128                         continue;
 129                 replace_phi_node(insn);
 130         } END_FOR_EACH_PTR(insn);
 131 }
 132
 133 int unssa(struct entrypoint *ep)
 134 {
 135         struct basic_block *bb;
 136
 137         FOR_EACH_PTR(ep->bbs, bb) {
 138                 rewrite_phi_bb(bb);
 139         } END_FOR_EACH_PTR(bb);
 140
 141         return 0;
 142 }