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