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 struct instruction *alloc_copy_insn(struct instruction *phisrc)
  32 {
  33         struct instruction *insn = __alloc_instruction(0);
  34         insn->opcode = OP_COPY;
  35         insn->size = phisrc->size;
  36         insn->pos = phisrc->pos;
  37         return insn;
  38 }
  39
  40 // Is there a better way to do this ???
  41 static void insert_insn_before(struct instruction *old, struct instruction *new)
  42 {
  43         struct instruction *insn;
  44
  45         FOR_EACH_PTR_REVERSE(old->bb->insns, insn) {
  46                 if (insn == old)
  47                         INSERT_CURRENT(new, insn);
  48         }
  49         END_FOR_EACH_PTR_REVERSE(insn);
  50 }
  51
  52 static void insert_copy(struct instruction *phisrc, pseudo_t tmp)
  53 {
  54         struct instruction *cpy;
  55
  56         assert(phisrc->opcode == OP_PHISOURCE);
  57
  58         cpy =  alloc_copy_insn(phisrc);
  59         cpy->target = tmp;
  60         cpy->src = phisrc->phi_src;
  61         cpy->bb = phisrc->bb;
  62         insert_insn_before(phisrc, cpy);
  63 }
  64
  65 static void copy_phi_args(struct instruction *phi, struct pseudo_list **list)
  66 {
  67         pseudo_t tmp, orig = phi->target;
  68         pseudo_t phisrc;
  69
  70         tmp = alloc_pseudo(NULL);
  71         tmp->type = orig->type;
  72         tmp->def = phi;                 // wrongly set to the phi-node !!!
  73                                         // but used later
  74         add_pseudo(list, tmp);
  75
  76         FOR_EACH_PTR(phi->phi_list, phisrc) {
  77                 if (!phisrc->def)
  78                         continue;
  79                 insert_copy(phisrc->def, tmp);
  80         } END_FOR_EACH_PTR(phisrc);
  81 }
  82
  83 static void unssa_bb(struct basic_block *bb)
  84 {
  85         struct pseudo_list *list = NULL;
  86         struct pseudo *tmp;
  87         struct instruction *insn;
  88
  89         // copy all the phi nodes arguments to a new temporary pseudo
  90         FOR_EACH_PTR(bb->insns, insn) {
  91                 if (insn->opcode != OP_PHI)
  92                         continue;
  93                 copy_phi_args(insn, &list);
  94         } END_FOR_EACH_PTR(insn);
  95
  96         // now replace all the phi nodes themselves by copies of the
  97         // temporaries to the phi nodes targets
  98         FOR_EACH_PTR(list, tmp) {
  99                 struct instruction *phi = tmp->def;
 100
 101                 phi->opcode = OP_COPY;
 102                 phi->src = tmp;
 103         } END_FOR_EACH_PTR(tmp);
 104         free_ptr_list(&list);
 105 }
 106
 107 int unssa(struct entrypoint *ep)
 108 {
 109         struct basic_block *bb;
 110
 111         FOR_EACH_PTR(ep->bbs, bb) {
 112                 unssa_bb(bb);
 113         } END_FOR_EACH_PTR(bb);
 114
 115         return 0;
 116 }