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