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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
#ifndef SSA_H
#define SSA_H
#include "const.h"
#include "semantics.h"
typedef struct CInst CInst;
typedef CInst *CInst_t;
typedef struct CRange CRange;
typedef struct CRange *CRange_t;
struct CRange {
int l, r; /* [l, r) */
CRange_t next;
};
typedef struct COpr COpr;
typedef COpr *COpr_t;
struct COpr {
enum {
VAR,
TMP,
IMM,
IMMS,
IMMF
} kind;
union {
CVar_t var;
CSList_t cstr;
char *str;
int imm;
} info;
int sub;
int dep;
int reg; /* -1 for spilled, -2 for discarded */
int begin, end; /* for reg allocation */
int mod;
CType_t type;
CInst_t def;
CRange_t range;
COpr_t par; /* union-find */
COpr_t cval;
COpr_t spill; /* check this reference if spilled */
COpr_t same; /* for common exp elimination */
};
typedef struct COList COList;
typedef COList *COList_t;
struct COList {
COpr_t opr;
COList_t next, prev;
};
void colist_remove(COList_t node);
struct CInst {
enum OpCode {
BEQ = 0, /* conditional jump */
BNE = 1,
GOTO, /* unconditional jump */
ARR, /* displacement */
PUSH, /* push to stack top */
CALL, /* call function */
RET, /* return */
WARR,
MOVE,
LOAD, /* load from memory */
ADDR, /* get address */
MUL, DIV, MOD, ADD, SUB,
SHL, SHR, AND, XOR, OR, NOR,
EQ, NE, LT, GT, LE, GE,
NEG
} op;
COpr_t dest, src1, src2;
CInst_t next, prev;
CType_t wtype; /* for WARR */
int id;
int is_def;
int bret; /* for CALL */
int offset; /* for PUSH */
};
typedef struct CPhi CPhi;
typedef CPhi *CPhi_t;
struct CPhi {
COpr_t dest;
COpr_t *oprs;
CPhi_t next, prev;
};
typedef struct CBlock CBlock;
typedef CBlock *CBlock_t;
struct CBlock {
CPhi_t phis;
CInst_t insts; /* instructions */
CBlock_t next, prev;
int id;
int ref; /* if referenced by any gotos */
int pred; /* the number of predecessors */
int first, last;
};
typedef struct CBList CBList;
typedef CBList *CBList_t;
struct CBList {
CBlock_t cblk;
CBList_t next;
};
CBlock_t cblock_create(int inc);
void cblock_append(CBlock_t cblk, CInst_t inst);
void cblock_pappend(CBlock_t cblk, CPhi_t phi);
CInst_t cblock_getback(CBlock_t cblk);
int cblock_isempty(CBlock_t cblk);
typedef struct CEdge CEdge;
typedef struct CGraph {
struct CEdge {
CBlock *to;
CEdge *next;
} *head[MAX_BLOCK], *rhead[MAX_BLOCK];
} CGraph;
typedef struct CPNode CPNode;
typedef struct CPSet {
struct CPNode {
long key;
CPNode *next;
} *head[MAX_TABLE_SIZE];
} CPSet;
typedef CPSet *CPSet_t;
CPSet_t cpset_create(void);
int cpset_insert(CPSet_t cps, long key);
int cpset_belongs(CPSet_t cps, long key);
void cpset_destroy(CPSet_t cps);
typedef struct CInterv {
COpr_t opr;
CRange_t range;
} CInterv;
typedef struct CENode CENode;
typedef struct CExpMap {
struct CENode {
CInst_t exp;
CENode *next;
} *head[MAX_TABLE_SIZE];
} CExpMap;
typedef CExpMap *CExpMap_t;
CExpMap_t cexpmap_create(void);
unsigned int cexpmap_hash(CInst_t exp);
int cexpmap_comp(CInst_t exp1, CInst_t exp2);
void cexpmap_insert(CExpMap_t cem, CInst_t exp);
CInst_t cexpmap_lookup(CExpMap_t cem, CInst_t exp);
void cexpmap_clear(CExpMap_t cem);
void cexpmap_destroy(CExpMap_t cem);
void ssa_generate(void);
COpr_t cinterv_repr(COpr_t opr);
void cinst_print(FILE *stream, CInst_t inst);
int overlap_with_beg(COpr_t i, int beg);
extern int gbbase;
extern CBlock_t entry;
extern COList_t defs;
extern CType_t func;
extern const int avail_regs[];
extern const int MAX_AVAIL_REGS;
#endif
|