forked from jatovm/jato
-
Notifications
You must be signed in to change notification settings - Fork 2
/
dce.c
125 lines (102 loc) · 2.58 KB
/
dce.c
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
/*
* Copyright (c) 2011 Ana Farcasi
*
* This file is released under the 2-clause BSD license. Please refer to the
* file LICENSE for details.
*
*/
#include "jit/compilation-unit.h"
#include "jit/compiler.h"
#include "jit/instruction.h"
#include "jit/ssa.h"
#include "jit/vars.h"
#include "lib/radix-tree.h"
#include "vm/stdlib.h"
#include <stdio.h>
static struct dce *alloc_dce_element(struct var_info *var)
{
struct dce *dce_element;
dce_element = malloc(sizeof(struct dce));
if (!dce_element)
return NULL;
dce_element->var = var;
dce_element->next = NULL;
return dce_element;
}
static void insert_list(struct dce *dce_element, struct dce **list)
{
if (*list != NULL){
dce_element->next = *list;
*list = dce_element;
} else
*list = dce_element;
}
/*
* This function implements dead code elimination. For more
* details on the algorithm used here, check "Modern Compiler
* Implementation in Java" by Andrew W. Appel, section 19.3.
*/
int dce(struct compilation_unit *cu)
{
struct live_interval *it;
struct var_info *var;
struct dce *dce_element, *list;
struct use_position *use;
struct insn *def_insn;
bool used;
list = NULL;
for_each_variable(var, cu->ssa_var_infos) {
it = var->interval;
if (!interval_has_fixed_reg(it)) {
dce_element = alloc_dce_element(var);
insert_list(dce_element, &list);
}
}
while (list) {
dce_element = list;
it = dce_element->var->interval;
used = false;
def_insn = NULL;
list_for_each_entry(use, &it->use_positions, use_pos_list) {
if (insn_vreg_use(use, it->var_info)) {
used = true;
break;
}
if (insn_vreg_def(use, it->var_info)) {
def_insn = use->insn;
}
}
list = dce_element->next;
free(dce_element);
if (!used) {
unsigned long nr_par, nr_uses;
struct use_position **reg_uses;
if (!def_insn)
continue;
nr_par = nr_srcs_phi(def_insn) + MAX_REG_OPERANDS;
reg_uses = malloc(nr_par * sizeof(struct use_position *));
if (!reg_uses)
return warn("out of memory"), -EINVAL;
nr_uses = insn_uses_reg(def_insn, reg_uses);
for (unsigned long i = 0; i < nr_uses; i++) {
struct use_position *this_use = reg_uses[i];
if (!interval_has_fixed_reg(this_use->interval)) {
dce_element =
alloc_dce_element(this_use->
interval->
var_info);
insert_list(dce_element, &list);
}
}
free(reg_uses);
list_del(&def_insn->insn_list_node);
if (insn_use_def(def_insn))
hash_map_remove(cu->insn_add_ons, def_insn);
if (insn_is_phi(def_insn))
free_ssa_insn(def_insn);
else
free_insn(def_insn);
}
}
return 0;
}