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
|
/*
* Copyright (C) 2015 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ART_COMPILER_DEX_GVN_DEAD_CODE_ELIMINATION_H_
#define ART_COMPILER_DEX_GVN_DEAD_CODE_ELIMINATION_H_
#include "base/arena_object.h"
#include "base/scoped_arena_containers.h"
#include "global_value_numbering.h"
namespace art {
class ArenaBitVector;
class BasicBlock;
class LocalValueNumbering;
class MIR;
class MIRGraph;
/**
* @class DeadCodeElimination
* @details Eliminate dead code based on the results of global value numbering.
* Also get rid of MOVE insns when we can use the source instead of destination
* without affecting the vreg values at safepoints; this is useful in methods
* with a large number of vregs that frequently move values to and from low vregs
* to accommodate insns that can work only with the low 16 or 256 vregs.
*/
class GvnDeadCodeElimination : public DeletableArenaObject<kArenaAllocMisc> {
public:
GvnDeadCodeElimination(const GlobalValueNumbering* gvn, ScopedArenaAllocator* alloc);
// Apply the DCE to a basic block.
void Apply(BasicBlock* bb);
private:
static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue;
static constexpr uint16_t kNPos = 0xffffu;
static constexpr size_t kMaxNumTopChangesToKill = 2;
struct VRegValue {
VRegValue() : value(kNoValue), change(kNPos) { }
// Value name as reported by GVN, kNoValue if not available.
uint16_t value;
// Index of the change in mir_data_ that defined the value, kNPos if initial value for the BB.
uint16_t change;
};
struct MIRData {
explicit MIRData(MIR* m)
: mir(m), uses_all_vregs(false), must_keep(false), is_move(false), is_move_src(false),
has_def(false), wide_def(false),
low_def_over_high_word(false), high_def_over_low_word(false), vreg_def(0u),
prev_value(), prev_value_high() {
}
uint16_t PrevChange(int v_reg) const;
void SetPrevChange(int v_reg, uint16_t change);
void RemovePrevChange(int v_reg, MIRData* prev_data);
MIR* mir;
bool uses_all_vregs : 1; // If mir uses all vregs, uses in mir->ssa_rep are irrelevant.
bool must_keep : 1;
bool is_move : 1;
bool is_move_src : 1;
bool has_def : 1;
bool wide_def : 1;
bool low_def_over_high_word : 1;
bool high_def_over_low_word : 1;
uint16_t vreg_def;
VRegValue prev_value;
VRegValue prev_value_high; // For wide defs.
};
class VRegChains {
public:
VRegChains(uint32_t num_vregs, ScopedArenaAllocator* alloc);
void Reset();
void AddMIRWithDef(MIR* mir, int v_reg, bool wide, uint16_t new_value);
void AddMIRWithoutDef(MIR* mir);
void RemoveLastMIRData();
void RemoveTrailingNops();
size_t NumMIRs() const;
MIRData* GetMIRData(size_t pos);
MIRData* LastMIRData();
uint32_t NumVRegs() const;
void InsertInitialValueHigh(int v_reg, uint16_t value);
void UpdateInitialVRegValue(int v_reg, bool wide, const LocalValueNumbering* lvn);
uint16_t LastChange(int v_reg);
uint16_t CurrentValue(int v_reg);
uint16_t FindKillHead(int v_reg, uint16_t cutoff);
uint16_t FindFirstChangeAfter(int v_reg, uint16_t change) const;
void ReplaceChange(uint16_t old_change, uint16_t new_change);
void RemoveChange(uint16_t change);
bool IsTopChange(uint16_t change) const;
bool IsSRegUsed(uint16_t first_change, uint16_t last_change, int s_reg) const;
void RenameSRegUses(uint16_t first_change, uint16_t last_change,
int old_s_reg, int new_s_reg, bool wide);
void RenameVRegUses(uint16_t first_change, uint16_t last_change,
int old_s_reg, int old_v_reg, int new_s_reg, int new_v_reg);
private:
const uint32_t num_vregs_;
VRegValue* const vreg_data_;
ScopedArenaVector<MIRData> mir_data_;
};
void RecordPass();
void BackwardPass();
void KillMIR(MIRData* data);
static void KillMIR(MIR* mir);
static void ChangeBinOp2AddrToPlainBinOp(MIR* mir);
MIR* CreatePhi(int s_reg);
MIR* RenameSRegDefOrCreatePhi(uint16_t def_change, uint16_t last_change, MIR* mir_to_kill);
// Update state variables going backwards through a MIR.
void BackwardPassProcessLastMIR();
uint16_t FindChangesToKill(uint16_t first_change, uint16_t last_change);
void BackwardPassTryToKillRevertVRegs();
bool BackwardPassTryToKillLastMIR();
void RecordPassKillMoveByRenamingSrcDef(uint16_t src_change, uint16_t move_change);
void RecordPassTryToKillOverwrittenMoveOrMoveSrc(uint16_t check_change);
void RecordPassTryToKillOverwrittenMoveOrMoveSrc();
void RecordPassTryToKillLastMIR();
bool RecordMIR(MIR* mir);
const GlobalValueNumbering* const gvn_;
MIRGraph* const mir_graph_;
VRegChains vreg_chains_;
BasicBlock* bb_;
const LocalValueNumbering* lvn_;
size_t no_uses_all_since_; // The change index after the last change with uses_all_vregs set.
// Data used when processing MIRs in reverse order.
ArenaBitVector* unused_vregs_; // vregs that are not needed later.
ArenaBitVector* vregs_to_kill_; // vregs that revert to a previous value.
uint16_t* kill_heads_; // For each vreg in vregs_to_kill_, the first change to kill.
ScopedArenaVector<uint16_t> changes_to_kill_;
ArenaBitVector* dependent_vregs_;
};
} // namespace art
#endif // ART_COMPILER_DEX_GVN_DEAD_CODE_ELIMINATION_H_
|
