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 (the same place where the
  14  * phisrc were present).
  15  * Is this a problem?
  16  *
  17  * While very simple this method create a lot more copies that really necessary.
  18  * Ideally, "Sreedhar method III" should be used:
  19  * "Translating Out of Static Single Assignment Form", V. C. Sreedhar, R. D.-C. Ju,
  20  * D. M. Gillies and V. Santhanam.  SAS'99, Vol. 1694 of Lecture Notes in Computer
  21  * Science, Springer-Verlag, pp. 194-210, 1999.
  22  *
  23  * Copyright (C) 2005 Luc Van Oostenryck
  24  */
  25
  26 #include "lib.h"
  27 #include "linearize.h"
  28 #include "allocate.h"
  29 #include "flow.h"
  30 #include <assert.h>
  31
  32
  33 static void remove_phisrc_defines(struct instruction *phisrc)
  34 {
  35         struct instruction *phi;
  36         struct basic_block *bb = phisrc->bb;
  37
  38         FOR_EACH_PTR(phisrc->phi_users, phi) {
  39                 remove_pseudo(&bb->defines, phi->target);
  40         } END_FOR_EACH_PTR(phi);
  41 }
  42
  43 static void replace_phi_node(struct instruction *phi)
  44 {
  45         pseudo_t tmp;
  46
  47         tmp = alloc_pseudo(NULL);
  48         tmp->type = phi->target->type;
  49         tmp->ident = phi->target->ident;
  50         tmp->def = NULL;                // defined by all the phisrc
  51
  52         // update the current liveness
  53         remove_pseudo(&phi->bb->needs, phi->target);
  54         add_pseudo(&phi->bb->needs, tmp);
  55         track_phi_uses(phi);
  56
  57         phi->opcode = OP_COPY;
  58         phi->src = tmp;
  59
  60         // FIXME: free phi->phi_list;
  61 }
  62
  63 static void rewrite_phi_bb(struct basic_block *bb)
  64 {
  65         struct instruction *insn;
  66
  67         // Replace all the phi-nodes by copies of a temporary
  68         // (which represent the set of all the %phi that feed them).
  69         // The target pseudo doesn't change.
  70         FOR_EACH_PTR(bb->insns, insn) {
  71                 if (!insn->bb)
  72                         continue;
  73                 if (insn->opcode != OP_PHI)
  74                         continue;
  75                 replace_phi_node(insn);
  76         } END_FOR_EACH_PTR(insn);
  77 }
  78
  79 static void rewrite_phisrc_bb(struct basic_block *bb)
  80 {
  81         struct instruction *insn;
  82
  83         // Replace all the phisrc by one or several copies to
  84         // the temporaries associated to each phi-node it defines.
  85         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
  86                 struct instruction *phi;
  87                 int i;
  88
  89                 if (!insn->bb)
  90                         continue;
  91                 if (insn->opcode != OP_PHISOURCE)
  92                         continue;
  93
  94                 i = 0;
  95                 FOR_EACH_PTR(insn->phi_users, phi) {
  96                         pseudo_t tmp = phi->src;
  97                         pseudo_t src = insn->phi_src;
  98
  99                         if (i == 0) {   // first phi: we overwrite the phisrc
 100                                 insn->opcode = OP_COPY;
 101                                 insn->target = tmp;
 102                                 insn->src = src;
 103                         } else {
 104                                 struct instruction *copy = __alloc_instruction(0);
 105
 106                                 copy->bb = bb;
 107                                 copy->opcode = OP_COPY;
 108                                 copy->size = insn->size;
 109                                 copy->pos = insn->pos;
 110                                 copy->target = tmp;
 111                                 copy->src = src;
 112
 113                                 INSERT_CURRENT(copy, insn);
 114                         }
 115                         // update the liveness info
 116                         remove_phisrc_defines(insn);
 117                         // FIXME: should really something like add_pseudo_exclusive()
 118                         add_pseudo(&bb->defines, tmp);
 119
 120                         i++;
 121                 } END_FOR_EACH_PTR(phi);
 122
 123         } END_FOR_EACH_PTR_REVERSE(insn);
 124 }
 125
 126 int unssa(struct entrypoint *ep)
 127 {
 128         struct basic_block *bb;
 129
 130         FOR_EACH_PTR(ep->bbs, bb) {
 131                 rewrite_phi_bb(bb);
 132         } END_FOR_EACH_PTR(bb);
 133
 134         FOR_EACH_PTR(ep->bbs, bb) {
 135                 rewrite_phisrc_bb(bb);
 136         } END_FOR_EACH_PTR(bb);
 137
 138         return 0;
 139 }