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