1 /*
2  * Copyright (C) 2015 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_COMPILER_DEX_GVN_DEAD_CODE_ELIMINATION_H_
18 #define ART_COMPILER_DEX_GVN_DEAD_CODE_ELIMINATION_H_
19 
20 #include "base/arena_object.h"
21 #include "base/scoped_arena_containers.h"
22 #include "global_value_numbering.h"
23 
24 namespace art {
25 
26 class ArenaBitVector;
27 class BasicBlock;
28 class LocalValueNumbering;
29 class MIR;
30 class MIRGraph;
31 
32 /**
33  * @class DeadCodeElimination
34  * @details Eliminate dead code based on the results of global value numbering.
35  * Also get rid of MOVE insns when we can use the source instead of destination
36  * without affecting the vreg values at safepoints; this is useful in methods
37  * with a large number of vregs that frequently move values to and from low vregs
38  * to accommodate insns that can work only with the low 16 or 256 vregs.
39  */
40 class GvnDeadCodeElimination : public DeletableArenaObject<kArenaAllocMisc> {
41  public:
42   GvnDeadCodeElimination(const GlobalValueNumbering* gvn, ScopedArenaAllocator* alloc);
43 
44   // Apply the DCE to a basic block.
45   void Apply(BasicBlock* bb);
46 
47  private:
48   static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue;
49   static constexpr uint16_t kNPos = 0xffffu;
50   static constexpr size_t kMaxNumTopChangesToKill = 2;
51 
52   struct VRegValue {
VRegValueVRegValue53     VRegValue() : value(kNoValue), change(kNPos) { }
54 
55     // Value name as reported by GVN, kNoValue if not available.
56     uint16_t value;
57     // Index of the change in mir_data_ that defined the value, kNPos if initial value for the BB.
58     uint16_t change;
59   };
60 
61   struct MIRData {
MIRDataMIRData62     explicit MIRData(MIR* m)
63         : mir(m), uses_all_vregs(false), must_keep(false), is_move(false), is_move_src(false),
64           has_def(false), wide_def(false),
65           low_def_over_high_word(false), high_def_over_low_word(false), vreg_def(0u),
66           prev_value(), prev_value_high() {
67     }
68 
69     uint16_t PrevChange(int v_reg) const;
70     void SetPrevChange(int v_reg, uint16_t change);
71     void RemovePrevChange(int v_reg, MIRData* prev_data);
72 
73     MIR* mir;
74     bool uses_all_vregs : 1;  // If mir uses all vregs, uses in mir->ssa_rep are irrelevant.
75     bool must_keep : 1;
76     bool is_move : 1;
77     bool is_move_src : 1;
78     bool has_def : 1;
79     bool wide_def : 1;
80     bool low_def_over_high_word : 1;
81     bool high_def_over_low_word : 1;
82     uint16_t vreg_def;
83     VRegValue prev_value;
84     VRegValue prev_value_high;   // For wide defs.
85   };
86 
87   class VRegChains {
88    public:
89     VRegChains(uint32_t num_vregs, ScopedArenaAllocator* alloc);
90 
91     void Reset();
92 
93     void AddMIRWithDef(MIR* mir, int v_reg, bool wide, uint16_t new_value);
94     void AddMIRWithoutDef(MIR* mir);
95     void RemoveLastMIRData();
96     void RemoveTrailingNops();
97 
98     size_t NumMIRs() const;
99     MIRData* GetMIRData(size_t pos);
100     MIRData* LastMIRData();
101 
102     uint32_t NumVRegs() const;
103     void InsertInitialValueHigh(int v_reg, uint16_t value);
104     void UpdateInitialVRegValue(int v_reg, bool wide, const LocalValueNumbering* lvn);
105     uint16_t LastChange(int v_reg);
106     uint16_t CurrentValue(int v_reg);
107 
108     uint16_t FindKillHead(int v_reg, uint16_t cutoff);
109     uint16_t FindFirstChangeAfter(int v_reg, uint16_t change) const;
110     void ReplaceChange(uint16_t old_change, uint16_t new_change);
111     void RemoveChange(uint16_t change);
112     bool IsTopChange(uint16_t change) const;
113     bool IsSRegUsed(uint16_t first_change, uint16_t last_change, int s_reg) const;
114     bool IsVRegUsed(uint16_t first_change, uint16_t last_change, int v_reg,
115                     MIRGraph* mir_graph) const;
116     void RenameSRegUses(uint16_t first_change, uint16_t last_change,
117                         int old_s_reg, int new_s_reg, bool wide);
118     void RenameVRegUses(uint16_t first_change, uint16_t last_change,
119                         int old_s_reg, int old_v_reg, int new_s_reg, int new_v_reg);
120 
121    private:
122     const uint32_t num_vregs_;
123     VRegValue* const vreg_data_;
124     BitVector vreg_high_words_;
125     ScopedArenaVector<MIRData> mir_data_;
126   };
127 
128   void RecordPass();
129   void BackwardPass();
130 
131   void KillMIR(MIRData* data);
132   static void KillMIR(MIR* mir);
133   static void ChangeBinOp2AddrToPlainBinOp(MIR* mir);
134   MIR* CreatePhi(int s_reg);
135   MIR* RenameSRegDefOrCreatePhi(uint16_t def_change, uint16_t last_change, MIR* mir_to_kill);
136 
137   // Update state variables going backwards through a MIR.
138   void BackwardPassProcessLastMIR();
139 
140   uint16_t FindChangesToKill(uint16_t first_change, uint16_t last_change);
141   void BackwardPassTryToKillRevertVRegs();
142   bool BackwardPassTryToKillLastMIR();
143 
144   void RecordPassKillMoveByRenamingSrcDef(uint16_t src_change, uint16_t move_change);
145   void RecordPassTryToKillOverwrittenMoveOrMoveSrc(uint16_t check_change);
146   void RecordPassTryToKillOverwrittenMoveOrMoveSrc();
147   void RecordPassTryToKillLastMIR();
148 
149   bool RecordMIR(MIR* mir);
150 
151   const GlobalValueNumbering* const gvn_;
152   MIRGraph* const mir_graph_;
153 
154   VRegChains vreg_chains_;
155   BasicBlock* bb_;
156   const LocalValueNumbering* lvn_;
157   size_t no_uses_all_since_;  // The change index after the last change with uses_all_vregs set.
158 
159   // Data used when processing MIRs in reverse order.
160   ArenaBitVector* unused_vregs_;              // vregs that are not needed later.
161   ArenaBitVector* vregs_to_kill_;             // vregs that revert to a previous value.
162   uint16_t* kill_heads_;  // For each vreg in vregs_to_kill_, the first change to kill.
163   ScopedArenaVector<uint16_t> changes_to_kill_;
164   ArenaBitVector* dependent_vregs_;
165 };
166 
167 }  // namespace art
168 
169 #endif  // ART_COMPILER_DEX_GVN_DEAD_CODE_ELIMINATION_H_
170