stored_conditons: store the chunk as well as the var_sym_list
[smatch.git] / unssa.c
blob382095d7fb2214b4ae324d6bbfff8a95e3ff6466
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 "flow.h"
30 #include <assert.h>
33 static void remove_phisrc_defines(struct instruction *phisrc)
35 struct instruction *phi;
36 struct basic_block *bb = phisrc->bb;
38 FOR_EACH_PTR(phisrc->phi_users, phi) {
39 remove_pseudo(&bb->defines, phi->target);
40 } END_FOR_EACH_PTR(phi);
43 static void replace_phi_node(struct instruction *phi)
45 pseudo_t tmp;
47 tmp = alloc_pseudo(NULL);
48 tmp->type = phi->target->type;
49 tmp->ident = phi->target->ident;
50 tmp->def = NULL; // defined by all the phisrc
52 // update the current liveness
53 remove_pseudo(&phi->bb->needs, phi->target);
54 add_pseudo(&phi->bb->needs, tmp);
55 track_phi_uses(phi);
57 phi->opcode = OP_COPY;
58 use_pseudo(phi, tmp, &phi->src);
60 // FIXME: free phi->phi_list;
63 static void rewrite_phi_bb(struct basic_block *bb)
65 struct instruction *insn;
67 // Replace all the phi-nodes by copies of a temporary
68 // (which represent the set of all the %phi that feed them).
69 // The target pseudo doesn't change.
70 FOR_EACH_PTR(bb->insns, insn) {
71 if (!insn->bb)
72 continue;
73 if (insn->opcode != OP_PHI)
74 continue;
75 replace_phi_node(insn);
76 } END_FOR_EACH_PTR(insn);
79 static void rewrite_phisrc_bb(struct basic_block *bb)
81 struct instruction *insn;
83 // Replace all the phisrc by one or several copies to
84 // the temporaries associated to each phi-node it defines.
85 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
86 struct instruction *phi;
87 int i;
89 if (!insn->bb)
90 continue;
91 if (insn->opcode != OP_PHISOURCE)
92 continue;
94 i = 0;
95 FOR_EACH_PTR(insn->phi_users, phi) {
96 pseudo_t tmp = phi->src;
97 pseudo_t src = insn->phi_src;
99 if (i == 0) { // first phi: we overwrite the phisrc
100 insn->opcode = OP_COPY;
101 insn->target = tmp;
102 insn->src = src;
103 } else {
104 struct instruction *copy = __alloc_instruction(0);
106 copy->bb = bb;
107 copy->opcode = OP_COPY;
108 copy->size = insn->size;
109 copy->pos = insn->pos;
110 copy->target = tmp;
111 copy->src = src;
113 INSERT_CURRENT(copy, insn);
115 // update the liveness info
116 remove_phisrc_defines(insn);
117 // FIXME: should really something like add_pseudo_exclusive()
118 add_pseudo(&bb->defines, tmp);
120 i++;
121 } END_FOR_EACH_PTR(phi);
123 } END_FOR_EACH_PTR_REVERSE(insn);
126 int unssa(struct entrypoint *ep)
128 struct basic_block *bb;
130 FOR_EACH_PTR(ep->bbs, bb) {
131 rewrite_phi_bb(bb);
132 } END_FOR_EACH_PTR(bb);
134 FOR_EACH_PTR(ep->bbs, bb) {
135 rewrite_phisrc_bb(bb);
136 } END_FOR_EACH_PTR(bb);
138 return 0;