1/*
2 * Copyright (C) 2014 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_GLOBAL_VALUE_NUMBERING_H_
18#define ART_COMPILER_DEX_GLOBAL_VALUE_NUMBERING_H_
19
20#include "base/arena_object.h"
21#include "base/logging.h"
22#include "base/macros.h"
23#include "mir_graph.h"
24#include "compiler_ir.h"
25#include "dex_flags.h"
26
27namespace art {
28
29class LocalValueNumbering;
30class MirFieldInfo;
31
32class GlobalValueNumbering : public DeletableArenaObject<kArenaAllocMisc> {
33 public:
34  static constexpr uint16_t kNoValue = 0xffffu;
35  static constexpr uint16_t kNullValue = 1u;
36
37  enum Mode {
38    kModeGvn,
39    kModeGvnPostProcessing,
40    kModeLvn
41  };
42
43  static bool Skip(CompilationUnit* cu) {
44    return (cu->disable_opt & (1u << kGlobalValueNumbering)) != 0u ||
45        cu->mir_graph->GetMaxNestedLoops() > kMaxAllowedNestedLoops;
46  }
47
48  // Instance and static field id map is held by MIRGraph to avoid multiple recalculations
49  // when doing LVN.
50  template <typename Container>  // Container of MirIFieldLoweringInfo or MirSFieldLoweringInfo.
51  static uint16_t* PrepareGvnFieldIds(ScopedArenaAllocator* allocator,
52                                      const Container& field_infos);
53
54  GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator, Mode mode);
55  ~GlobalValueNumbering();
56
57  CompilationUnit* GetCompilationUnit() const {
58    return cu_;
59  }
60
61  MIRGraph* GetMirGraph() const {
62    return mir_graph_;
63  }
64
65  // Prepare LVN for the basic block.
66  LocalValueNumbering* PrepareBasicBlock(BasicBlock* bb,
67                                         ScopedArenaAllocator* allocator = nullptr);
68
69  // Finish processing the basic block.
70  bool FinishBasicBlock(BasicBlock* bb);
71
72  // Checks that the value names didn't overflow.
73  bool Good() const {
74    return last_value_ < kNoValue;
75  }
76
77  // Allow modifications.
78  void StartPostProcessing();
79
80  bool CanModify() const {
81    return modifications_allowed_ && Good();
82  }
83
84  // Retrieve the LVN with GVN results for a given BasicBlock.
85  const LocalValueNumbering* GetLvn(BasicBlockId bb_id) const;
86
87 private:
88  // Allocate a new value name.
89  uint16_t NewValueName();
90
91  // Key is concatenation of opcode, operand1, operand2 and modifier, value is value name.
92  typedef ScopedArenaSafeMap<uint64_t, uint16_t> ValueMap;
93
94  static uint64_t BuildKey(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
95    return (static_cast<uint64_t>(op) << 48 | static_cast<uint64_t>(operand1) << 32 |
96            static_cast<uint64_t>(operand2) << 16 | static_cast<uint64_t>(modifier));
97  }
98
99  // Look up a value in the global value map, adding a new entry if there was none before.
100  uint16_t LookupValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
101    uint16_t res;
102    uint64_t key = BuildKey(op, operand1, operand2, modifier);
103    auto lb = global_value_map_.lower_bound(key);
104    if (lb != global_value_map_.end() && lb->first == key) {
105      res = lb->second;
106    } else {
107      res = NewValueName();
108      global_value_map_.PutBefore(lb, key, res);
109    }
110    return res;
111  }
112
113  // Look up a value in the global value map, don't add a new entry if there was none before.
114  uint16_t FindValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) const {
115    uint16_t res;
116    uint64_t key = BuildKey(op, operand1, operand2, modifier);
117    auto lb = global_value_map_.lower_bound(key);
118    if (lb != global_value_map_.end() && lb->first == key) {
119      res = lb->second;
120    } else {
121      res = kNoValue;
122    }
123    return res;
124  }
125
126  // Get an instance field id.
127  uint16_t GetIFieldId(MIR* mir) {
128    return GetMirGraph()->GetGvnIFieldId(mir);
129  }
130
131  // Get a static field id.
132  uint16_t GetSFieldId(MIR* mir) {
133    return GetMirGraph()->GetGvnSFieldId(mir);
134  }
135
136  // Get an instance field type based on field id.
137  uint16_t GetIFieldType(uint16_t field_id) {
138    return static_cast<uint16_t>(GetMirGraph()->GetIFieldLoweringInfo(field_id).MemAccessType());
139  }
140
141  // Get a static field type based on field id.
142  uint16_t GetSFieldType(uint16_t field_id) {
143    return static_cast<uint16_t>(GetMirGraph()->GetSFieldLoweringInfo(field_id).MemAccessType());
144  }
145
146  struct ArrayLocation {
147    uint16_t base;
148    uint16_t index;
149  };
150
151  struct ArrayLocationComparator {
152    bool operator()(const ArrayLocation& lhs, const ArrayLocation& rhs) const {
153      if (lhs.base != rhs.base) {
154        return lhs.base < rhs.base;
155      }
156      return lhs.index < rhs.index;
157    }
158  };
159
160  typedef ScopedArenaSafeMap<ArrayLocation, uint16_t, ArrayLocationComparator> ArrayLocationMap;
161
162  // Get an array location.
163  uint16_t GetArrayLocation(uint16_t base, uint16_t index);
164
165  // Get the array base from an array location.
166  uint16_t GetArrayLocationBase(uint16_t location) const {
167    return array_location_reverse_map_[location]->first.base;
168  }
169
170  // Get the array index from an array location.
171  uint16_t GetArrayLocationIndex(uint16_t location) const {
172    return array_location_reverse_map_[location]->first.index;
173  }
174
175  // A set of value names.
176  typedef ScopedArenaSet<uint16_t> ValueNameSet;
177
178  // A map from a set of references to the set id.
179  typedef ScopedArenaSafeMap<ValueNameSet, uint16_t> RefSetIdMap;
180
181  uint16_t GetRefSetId(const ValueNameSet& ref_set) {
182    uint16_t res = kNoValue;
183    auto lb = ref_set_map_.lower_bound(ref_set);
184    if (lb != ref_set_map_.end() && !ref_set_map_.key_comp()(ref_set, lb->first)) {
185      res = lb->second;
186    } else {
187      res = NewValueName();
188      ref_set_map_.PutBefore(lb, ref_set, res);
189    }
190    return res;
191  }
192
193  const BasicBlock* GetBasicBlock(uint16_t bb_id) const {
194    return mir_graph_->GetBasicBlock(bb_id);
195  }
196
197  static bool HasNullCheckLastInsn(const BasicBlock* pred_bb, BasicBlockId succ_id) {
198    return pred_bb->BranchesToSuccessorOnlyIfNotZero(succ_id);
199  }
200
201  bool NullCheckedInAllPredecessors(const ScopedArenaVector<uint16_t>& merge_names) const;
202
203  bool DivZeroCheckedInAllPredecessors(const ScopedArenaVector<uint16_t>& merge_names) const;
204
205  bool IsBlockEnteredOnTrue(uint16_t cond, BasicBlockId bb_id);
206  bool IsTrueInBlock(uint16_t cond, BasicBlockId bb_id);
207
208  ScopedArenaAllocator* Allocator() const {
209    return allocator_;
210  }
211
212  CompilationUnit* const cu_;
213  MIRGraph* const mir_graph_;
214  ScopedArenaAllocator* const allocator_;
215
216  // The maximum number of nested loops that we accept for GVN.
217  static constexpr size_t kMaxAllowedNestedLoops = 6u;
218
219  // The number of BBs that we need to process grows exponentially with the number
220  // of nested loops. Don't allow excessive processing for too many nested loops or
221  // otherwise expensive methods.
222  static constexpr uint32_t kMaxBbsToProcessMultiplyFactor = 20u;
223
224  uint32_t bbs_processed_;
225  uint32_t max_bbs_to_process_;  // Doesn't apply after the main GVN has converged.
226
227  // We have 32-bit last_value_ so that we can detect when we run out of value names, see Good().
228  // We usually don't check Good() until the end of LVN unless we're about to modify code.
229  uint32_t last_value_;
230
231  // Marks whether code modifications are allowed. The initial GVN is done without code
232  // modifications to settle the value names. Afterwards, we allow modifications and rerun
233  // LVN once for each BasicBlock.
234  bool modifications_allowed_;
235
236  // Specifies the mode of operation.
237  Mode mode_;
238
239  ValueMap global_value_map_;
240  ArrayLocationMap array_location_map_;
241  ScopedArenaVector<const ArrayLocationMap::value_type*> array_location_reverse_map_;
242  RefSetIdMap ref_set_map_;
243
244  ScopedArenaVector<const LocalValueNumbering*> lvns_;        // Owning.
245  std::unique_ptr<LocalValueNumbering> work_lvn_;
246  ScopedArenaVector<const LocalValueNumbering*> merge_lvns_;  // Not owning.
247
248  friend class LocalValueNumbering;
249  friend class GlobalValueNumberingTest;
250
251  DISALLOW_COPY_AND_ASSIGN(GlobalValueNumbering);
252};
253std::ostream& operator<<(std::ostream& os, const GlobalValueNumbering::Mode& rhs);
254
255inline const LocalValueNumbering* GlobalValueNumbering::GetLvn(BasicBlockId bb_id) const {
256  DCHECK_EQ(mode_, kModeGvnPostProcessing);
257  DCHECK_LT(bb_id, lvns_.size());
258  DCHECK(lvns_[bb_id] != nullptr);
259  return lvns_[bb_id];
260}
261
262inline void GlobalValueNumbering::StartPostProcessing() {
263  DCHECK(Good());
264  DCHECK_EQ(mode_, kModeGvn);
265  mode_ = kModeGvnPostProcessing;
266}
267
268inline uint16_t GlobalValueNumbering::NewValueName() {
269  DCHECK_NE(mode_, kModeGvnPostProcessing);
270  ++last_value_;
271  return last_value_;
272}
273
274template <typename Container>  // Container of MirIFieldLoweringInfo or MirSFieldLoweringInfo.
275uint16_t* GlobalValueNumbering::PrepareGvnFieldIds(ScopedArenaAllocator* allocator,
276                                                   const Container& field_infos) {
277  size_t size = field_infos.size();
278  uint16_t* field_ids = allocator->AllocArray<uint16_t>(size, kArenaAllocMisc);
279  for (size_t i = 0u; i != size; ++i) {
280    size_t idx = i;
281    const MirFieldInfo& cur_info = field_infos[i];
282    if (cur_info.IsResolved()) {
283      for (size_t j = 0; j != i; ++j) {
284        const MirFieldInfo& prev_info = field_infos[j];
285        if (prev_info.IsResolved() &&
286            prev_info.DeclaringDexFile() == cur_info.DeclaringDexFile() &&
287            prev_info.DeclaringFieldIndex() == cur_info.DeclaringFieldIndex()) {
288          DCHECK_EQ(cur_info.MemAccessType(), prev_info.MemAccessType());
289          idx = j;
290          break;
291        }
292      }
293    }
294    field_ids[i] = idx;
295  }
296  return field_ids;
297}
298
299}  // namespace art
300
301#endif  // ART_COMPILER_DEX_GLOBAL_VALUE_NUMBERING_H_
302