• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/macros.h"
21 #include "compiler_internals.h"
22 #include "utils/scoped_arena_containers.h"
23 
24 namespace art {
25 
26 class LocalValueNumbering;
27 class MirFieldInfo;
28 
29 class GlobalValueNumbering {
30  public:
31   GlobalValueNumbering(CompilationUnit* cu, ScopedArenaAllocator* allocator);
32   ~GlobalValueNumbering();
33 
34   // Prepare LVN for the basic block.
35   LocalValueNumbering* PrepareBasicBlock(BasicBlock* bb,
36                                          ScopedArenaAllocator* allocator = nullptr);
37 
38   // Finish processing the basic block.
39   bool FinishBasicBlock(BasicBlock* bb);
40 
41   // Checks that the value names didn't overflow.
Good()42   bool Good() const {
43     return last_value_ < kNoValue;
44   }
45 
46   // Allow modifications.
AllowModifications()47   void AllowModifications() {
48     DCHECK(Good());
49     modifications_allowed_ = true;
50   }
51 
CanModify()52   bool CanModify() const {
53     // TODO: DCHECK(Good()), see AllowModifications() and NewValueName().
54     return modifications_allowed_ && Good();
55   }
56 
57   // GlobalValueNumbering should be allocated on the ArenaStack (or the native stack).
new(size_t size,ScopedArenaAllocator * allocator)58   static void* operator new(size_t size, ScopedArenaAllocator* allocator) {
59     return allocator->Alloc(sizeof(GlobalValueNumbering), kArenaAllocMisc);
60   }
61 
62   // Allow delete-expression to destroy a GlobalValueNumbering object without deallocation.
delete(void * ptr)63   static void operator delete(void* ptr) { UNUSED(ptr); }
64 
65  private:
66   static constexpr uint16_t kNoValue = 0xffffu;
67 
68   // Allocate a new value name.
NewValueName()69   uint16_t NewValueName() {
70     // TODO: No new values should be needed once we allow modifications.
71     // DCHECK(!modifications_allowed_);
72     ++last_value_;
73     return last_value_;
74   }
75 
76   // Key is concatenation of opcode, operand1, operand2 and modifier, value is value name.
77   typedef ScopedArenaSafeMap<uint64_t, uint16_t> ValueMap;
78 
BuildKey(uint16_t op,uint16_t operand1,uint16_t operand2,uint16_t modifier)79   static uint64_t BuildKey(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
80     return (static_cast<uint64_t>(op) << 48 | static_cast<uint64_t>(operand1) << 32 |
81             static_cast<uint64_t>(operand2) << 16 | static_cast<uint64_t>(modifier));
82   };
83 
84   // Look up a value in the global value map, adding a new entry if there was none before.
LookupValue(uint16_t op,uint16_t operand1,uint16_t operand2,uint16_t modifier)85   uint16_t LookupValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier) {
86     uint16_t res;
87     uint64_t key = BuildKey(op, operand1, operand2, modifier);
88     ValueMap::iterator lb = global_value_map_.lower_bound(key);
89     if (lb != global_value_map_.end() && lb->first == key) {
90       res = lb->second;
91     } else {
92       res = NewValueName();
93       global_value_map_.PutBefore(lb, key, res);
94     }
95     return res;
96   };
97 
98   // Check if the exact value is stored in the global value map.
HasValue(uint16_t op,uint16_t operand1,uint16_t operand2,uint16_t modifier,uint16_t value)99   bool HasValue(uint16_t op, uint16_t operand1, uint16_t operand2, uint16_t modifier,
100                 uint16_t value) const {
101     DCHECK(value != 0u || !Good());
102     DCHECK_LE(value, last_value_);
103     // This is equivalent to value == LookupValue(op, operand1, operand2, modifier)
104     // except that it doesn't add an entry to the global value map if it's not there.
105     uint64_t key = BuildKey(op, operand1, operand2, modifier);
106     ValueMap::const_iterator it = global_value_map_.find(key);
107     return (it != global_value_map_.end() && it->second == value);
108   };
109 
110   // FieldReference represents a unique resolved field.
111   struct FieldReference {
112     const DexFile* dex_file;
113     uint16_t field_idx;
114     uint16_t type;  // See comments for LocalValueNumbering::kFieldTypeCount.
115   };
116 
117   struct FieldReferenceComparator {
operatorFieldReferenceComparator118     bool operator()(const FieldReference& lhs, const FieldReference& rhs) const {
119       if (lhs.field_idx != rhs.field_idx) {
120         return lhs.field_idx < rhs.field_idx;
121       }
122       // If the field_idx and dex_file match, the type must also match.
123       DCHECK(lhs.dex_file != rhs.dex_file || lhs.type == rhs.type);
124       return lhs.dex_file < rhs.dex_file;
125     }
126   };
127 
128   // Maps field key to field id for resolved fields.
129   typedef ScopedArenaSafeMap<FieldReference, uint32_t, FieldReferenceComparator> FieldIndexMap;
130 
131   // Get a field id.
132   uint16_t GetFieldId(const MirFieldInfo& field_info, uint16_t type);
133 
134   // Get a field type based on field id.
GetFieldType(uint16_t field_id)135   uint16_t GetFieldType(uint16_t field_id) {
136     DCHECK_LT(field_id, field_index_reverse_map_.size());
137     return field_index_reverse_map_[field_id]->first.type;
138   }
139 
140   struct ArrayLocation {
141     uint16_t base;
142     uint16_t index;
143   };
144 
145   struct ArrayLocationComparator {
operatorArrayLocationComparator146     bool operator()(const ArrayLocation& lhs, const ArrayLocation& rhs) const {
147       if (lhs.base != rhs.base) {
148         return lhs.base < rhs.base;
149       }
150       return lhs.index < rhs.index;
151     }
152   };
153 
154   typedef ScopedArenaSafeMap<ArrayLocation, uint16_t, ArrayLocationComparator> ArrayLocationMap;
155 
156   // Get an array location.
157   uint16_t GetArrayLocation(uint16_t base, uint16_t index);
158 
159   // Get the array base from an array location.
GetArrayLocationBase(uint16_t location)160   uint16_t GetArrayLocationBase(uint16_t location) const {
161     return array_location_reverse_map_[location]->first.base;
162   }
163 
164   // Get the array index from an array location.
GetArrayLocationIndex(uint16_t location)165   uint16_t GetArrayLocationIndex(uint16_t location) const {
166     return array_location_reverse_map_[location]->first.index;
167   }
168 
169   // A set of value names.
170   typedef ScopedArenaSet<uint16_t> ValueNameSet;
171 
172   // A map from a set of references to the set id.
173   typedef ScopedArenaSafeMap<ValueNameSet, uint16_t> RefSetIdMap;
174 
GetRefSetId(const ValueNameSet & ref_set)175   uint16_t GetRefSetId(const ValueNameSet& ref_set) {
176     uint16_t res = kNoValue;
177     auto lb = ref_set_map_.lower_bound(ref_set);
178     if (lb != ref_set_map_.end() && !ref_set_map_.key_comp()(ref_set, lb->first)) {
179       res = lb->second;
180     } else {
181       res = NewValueName();
182       ref_set_map_.PutBefore(lb, ref_set, res);
183     }
184     return res;
185   }
186 
GetBasicBlock(uint16_t bb_id)187   const BasicBlock* GetBasicBlock(uint16_t bb_id) const {
188     return mir_graph_->GetBasicBlock(bb_id);
189   }
190 
191   static bool HasNullCheckLastInsn(const BasicBlock* pred_bb, BasicBlockId succ_id);
192 
193   bool NullCheckedInAllPredecessors(const ScopedArenaVector<uint16_t>& merge_names) const;
194 
GetCompilationUnit()195   CompilationUnit* GetCompilationUnit() const {
196     return cu_;
197   }
198 
GetMirGraph()199   MIRGraph* GetMirGraph() const {
200     return mir_graph_;
201   }
202 
Allocator()203   ScopedArenaAllocator* Allocator() const {
204     return allocator_;
205   }
206 
207   CompilationUnit* const cu_;
208   MIRGraph* mir_graph_;
209   ScopedArenaAllocator* const allocator_;
210 
211   // The number of BBs that we need to process grows exponentially with the number
212   // of nested loops. Don't allow excessive processing for too many nested loops or
213   // otherwise expensive methods.
214   static constexpr uint32_t kMaxBbsToProcessMultiplyFactor = 20u;
215 
216   uint32_t bbs_processed_;
217   uint32_t max_bbs_to_process_;
218 
219   // We have 32-bit last_value_ so that we can detect when we run out of value names, see Good().
220   // We usually don't check Good() until the end of LVN unless we're about to modify code.
221   uint32_t last_value_;
222 
223   // Marks whether code modifications are allowed. The initial GVN is done without code
224   // modifications to settle the value names. Afterwards, we allow modifications and rerun
225   // LVN once for each BasicBlock.
226   bool modifications_allowed_;
227 
228   ValueMap global_value_map_;
229   FieldIndexMap field_index_map_;
230   ScopedArenaVector<const FieldIndexMap::value_type*> field_index_reverse_map_;
231   ArrayLocationMap array_location_map_;
232   ScopedArenaVector<const ArrayLocationMap::value_type*> array_location_reverse_map_;
233   RefSetIdMap ref_set_map_;
234 
235   ScopedArenaVector<const LocalValueNumbering*> lvns_;        // Owning.
236   std::unique_ptr<LocalValueNumbering> work_lvn_;
237   ScopedArenaVector<const LocalValueNumbering*> merge_lvns_;  // Not owning.
238 
239   friend class LocalValueNumbering;
240 
241   DISALLOW_COPY_AND_ASSIGN(GlobalValueNumbering);
242 };
243 
244 }  // namespace art
245 
246 #endif  // ART_COMPILER_DEX_GLOBAL_VALUE_NUMBERING_H_
247