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 <assert.h>
  30
  31 static void replace_phi_node(struct instruction *phi)
  32 {
  33         pseudo_t tmp;
  34
  35         tmp = alloc_pseudo(NULL);
  36         tmp->type = phi->target->type;
  37         tmp->def = NULL;                // defined by all the phisrc
  38
  39         phi->opcode = OP_COPY;
  40         phi->src = tmp;
  41
  42         // FIXME: free phi->phi_list;
  43         // FIXME: remove the %phi from bb->needs
  44         // FIXME: add tmp to bb->needs
  45         // FIXME: same but more tricky for bb->defines
  46 }
  47
  48 static void rewrite_phi_bb(struct basic_block *bb)
  49 {
  50         struct instruction *insn;
  51
  52         // Replace all the phi-nodes by copies of a temporary
  53         // (which represent the set of all the %phi that feed them).
  54         // The target pseudo doesn't change.
  55         FOR_EACH_PTR(bb->insns, insn) {
  56                 if (!insn->bb)
  57                         continue;
  58                 if (insn->opcode != OP_PHI)
  59                         continue;
  60                 replace_phi_node(insn);
  61         } END_FOR_EACH_PTR(insn);
  62 }
  63
  64 static void rewrite_phisrc_bb(struct basic_block *bb)
  65 {
  66         struct instruction *insn;
  67
  68         // Replace all the phisrc by one or several copies to
  69         // the temporaries associated to each phi-node it defines.
  70         FOR_EACH_PTR_REVERSE(bb->insns, insn) {
  71                 struct instruction *phi;
  72                 int i;
  73
  74                 if (!insn->bb)
  75                         continue;
  76                 if (insn->opcode != OP_PHISOURCE)
  77                         continue;
  78
  79                 i = 0;
  80                 FOR_EACH_PTR(insn->phi_users, phi) {
  81                         pseudo_t tmp = phi->src;
  82                         pseudo_t src = insn->phi_src;
  83
  84                         if (i == 0) {   // first phi: we overwrite the phisrc
  85                                 insn->opcode = OP_COPY;
  86                                 insn->target = tmp;
  87                                 insn->src = src;
  88                         } else {
  89                                 struct instruction *copy = __alloc_instruction(0);
  90
  91                                 copy->bb = bb;
  92                                 copy->opcode = OP_COPY;
  93                                 copy->size = insn->size;
  94                                 copy->pos = insn->pos;
  95                                 copy->target = tmp;
  96                                 copy->src = src;
  97
  98                                 INSERT_CURRENT(copy, insn);
  99                         }
 100
 101                         i++;
 102                 } END_FOR_EACH_PTR(phi);
 103
 104         } END_FOR_EACH_PTR_REVERSE(insn);
 105 }
 106
 107 int unssa(struct entrypoint *ep)
 108 {
 109         struct basic_block *bb;
 110
 111         FOR_EACH_PTR(ep->bbs, bb) {
 112                 rewrite_phi_bb(bb);
 113         } END_FOR_EACH_PTR(bb);
 114
 115         FOR_EACH_PTR(ep->bbs, bb) {
 116                 rewrite_phisrc_bb(bb);
 117         } END_FOR_EACH_PTR(bb);
 118
 119         return 0;
 120 }