1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
/*
* UnSSA - translate the SSA back to normal form.
*
* For now it's done by replacing to set of copies:
* 1) For each phi-node, replace all their phisrc by copies to a common
* temporary.
* 2) Replace all the phi-nodes by copies of the temporaries to the phi-node target.
* This is node to preserve the semantic of the phi-node (they should all "execute"
* simultaneously on entry in the basic block in which they belong).
*
* This is similar to the "Sreedhar method I" except that the copies to the
* temporaries are not placed at the end of the predecessor basic blocks, but
* at the place where the phi-node operands are defined (the same place where the
* phisrc were present).
* Is this a problem?
*
* While very simple this method create a lot more copies that really necessary.
* Ideally, "Sreedhar method III" should be used:
* "Translating Out of Static Single Assignment Form", V. C. Sreedhar, R. D.-C. Ju,
* D. M. Gillies and V. Santhanam. SAS'99, Vol. 1694 of Lecture Notes in Computer
* Science, Springer-Verlag, pp. 194-210, 1999.
*
* Copyright (C) 2005 Luc Van Oostenryck
*/
#include "lib.h"
#include "linearize.h"
#include "allocate.h"
#include "flow.h"
#include <assert.h>
static void remove_phisrc_defines(struct instruction *phisrc)
{
struct instruction *phi;
struct basic_block *bb = phisrc->bb;
FOR_EACH_PTR(phisrc->phi_users, phi) {
remove_pseudo(&bb->defines, phi->target);
} END_FOR_EACH_PTR(phi);
}
static void replace_phi_node(struct instruction *phi)
{
pseudo_t tmp;
tmp = alloc_pseudo(NULL);
tmp->type = phi->target->type;
tmp->ident = phi->target->ident;
tmp->def = NULL; // defined by all the phisrc
// update the current liveness
remove_pseudo(&phi->bb->needs, phi->target);
add_pseudo(&phi->bb->needs, tmp);
track_phi_uses(phi);
phi->opcode = OP_COPY;
use_pseudo(phi, tmp, &phi->src);
// FIXME: free phi->phi_list;
}
static void rewrite_phi_bb(struct basic_block *bb)
{
struct instruction *insn;
// Replace all the phi-nodes by copies of a temporary
// (which represent the set of all the %phi that feed them).
// The target pseudo doesn't change.
FOR_EACH_PTR(bb->insns, insn) {
if (!insn->bb)
continue;
if (insn->opcode != OP_PHI)
continue;
replace_phi_node(insn);
} END_FOR_EACH_PTR(insn);
}
static void rewrite_phisrc_bb(struct basic_block *bb)
{
struct instruction *insn;
// Replace all the phisrc by one or several copies to
// the temporaries associated to each phi-node it defines.
FOR_EACH_PTR_REVERSE(bb->insns, insn) {
struct instruction *phi;
int i;
if (!insn->bb)
continue;
if (insn->opcode != OP_PHISOURCE)
continue;
i = 0;
FOR_EACH_PTR(insn->phi_users, phi) {
pseudo_t tmp = phi->src;
pseudo_t src = insn->phi_src;
if (i == 0) { // first phi: we overwrite the phisrc
insn->opcode = OP_COPY;
insn->target = tmp;
insn->src = src;
} else {
struct instruction *copy = __alloc_instruction(0);
copy->bb = bb;
copy->opcode = OP_COPY;
copy->size = insn->size;
copy->pos = insn->pos;
copy->target = tmp;
copy->src = src;
INSERT_CURRENT(copy, insn);
}
// update the liveness info
remove_phisrc_defines(insn);
// FIXME: should really something like add_pseudo_exclusive()
add_pseudo(&bb->defines, tmp);
i++;
} END_FOR_EACH_PTR(phi);
} END_FOR_EACH_PTR_REVERSE(insn);
}
int unssa(struct entrypoint *ep)
{
struct basic_block *bb;
FOR_EACH_PTR(ep->bbs, bb) {
rewrite_phi_bb(bb);
} END_FOR_EACH_PTR(bb);
FOR_EACH_PTR(ep->bbs, bb) {
rewrite_phisrc_bb(bb);
} END_FOR_EACH_PTR(bb);
return 0;
}
|
