Install static library and header files
[smatch.git] / unssa.c
blobcd183132f02bd2cc8499694c41ff4d571dfbedcf
1 /*
2 * UnSSA - translate the SSA back to normal form.
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).
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?
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.
23 * Copyright (C) 2005 Luc Van Oostenryck
26 #include "lib.h"
27 #include "linearize.h"
28 #include "allocate.h"
29 #include <assert.h>
32 static void remove_phisrc_defines(struct instruction *phisrc)
34 struct instruction *phi;
35 struct basic_block *bb = phisrc->bb;
37 FOR_EACH_PTR(phisrc->phi_users, phi) {
38 remove_pseudo(&bb->defines, phi->target);
39 } END_FOR_EACH_PTR(phi);
42 static void replace_phi_node(struct instruction *phi)
44 pseudo_t tmp;
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
51 // update the current liveness
52 remove_pseudo(&phi->bb->needs, phi->target);
53 add_pseudo(&phi->bb->needs, tmp);
55 phi->opcode = OP_COPY;
56 phi->src = tmp;
58 // FIXME: free phi->phi_list;
61 static void rewrite_phi_bb(struct basic_block *bb)
63 struct instruction *insn;
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);
77 static void rewrite_phisrc_bb(struct basic_block *bb)
79 struct instruction *insn;
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;
87 if (!insn->bb)
88 continue;
89 if (insn->opcode != OP_PHISOURCE)
90 continue;
92 i = 0;
93 FOR_EACH_PTR(insn->phi_users, phi) {
94 pseudo_t tmp = phi->src;
95 pseudo_t src = insn->phi_src;
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);
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;
111 INSERT_CURRENT(copy, insn);
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);
118 i++;
119 } END_FOR_EACH_PTR(phi);
121 } END_FOR_EACH_PTR_REVERSE(insn);
124 int unssa(struct entrypoint *ep)
126 struct basic_block *bb;
128 FOR_EACH_PTR(ep->bbs, bb) {
129 rewrite_phi_bb(bb);
130 } END_FOR_EACH_PTR(bb);
132 FOR_EACH_PTR(ep->bbs, bb) {
133 rewrite_phisrc_bb(bb);
134 } END_FOR_EACH_PTR(bb);
136 return 0;