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