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