Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 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 | #include "load_store_elimination.h" |
Aart Bik | 96fd51d | 2016-11-28 11:22:35 -0800 | [diff] [blame] | 18 | |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 19 | #include "base/array_ref.h" |
| 20 | #include "base/scoped_arena_allocator.h" |
| 21 | #include "base/scoped_arena_containers.h" |
Aart Bik | 96fd51d | 2016-11-28 11:22:35 -0800 | [diff] [blame] | 22 | #include "escape.h" |
Andreas Gampe | 8cf9cb3 | 2017-07-19 09:28:38 -0700 | [diff] [blame] | 23 | #include "load_store_analysis.h" |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 24 | #include "side_effects_analysis.h" |
| 25 | |
| 26 | #include <iostream> |
| 27 | |
| 28 | namespace art { |
| 29 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 30 | // An unknown heap value. Loads with such a value in the heap location cannot be eliminated. |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 31 | // A heap location can be set to kUnknownHeapValue when: |
| 32 | // - initially set a value. |
| 33 | // - killed due to aliasing, merging, invocation, or loop side effects. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 34 | static HInstruction* const kUnknownHeapValue = |
| 35 | reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-1)); |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 36 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 37 | // Default heap value after an allocation. |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 38 | // A heap location can be set to that value right after an allocation. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 39 | static HInstruction* const kDefaultHeapValue = |
| 40 | reinterpret_cast<HInstruction*>(static_cast<uintptr_t>(-2)); |
| 41 | |
Mingyao Yang | c62b7ec | 2017-10-25 16:42:15 -0700 | [diff] [blame] | 42 | // Use HGraphDelegateVisitor for which all VisitInvokeXXX() delegate to VisitInvoke(). |
| 43 | class LSEVisitor : public HGraphDelegateVisitor { |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 44 | public: |
| 45 | LSEVisitor(HGraph* graph, |
| 46 | const HeapLocationCollector& heap_locations_collector, |
Igor Murashkin | 6ef4567 | 2017-08-08 13:59:55 -0700 | [diff] [blame] | 47 | const SideEffectsAnalysis& side_effects, |
| 48 | OptimizingCompilerStats* stats) |
Mingyao Yang | c62b7ec | 2017-10-25 16:42:15 -0700 | [diff] [blame] | 49 | : HGraphDelegateVisitor(graph, stats), |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 50 | heap_location_collector_(heap_locations_collector), |
| 51 | side_effects_(side_effects), |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 52 | allocator_(graph->GetArenaStack()), |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 53 | heap_values_for_(graph->GetBlocks().size(), |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 54 | ScopedArenaVector<HInstruction*>(heap_locations_collector. |
| 55 | GetNumberOfHeapLocations(), |
| 56 | kUnknownHeapValue, |
| 57 | allocator_.Adapter(kArenaAllocLSE)), |
| 58 | allocator_.Adapter(kArenaAllocLSE)), |
| 59 | removed_loads_(allocator_.Adapter(kArenaAllocLSE)), |
| 60 | substitute_instructions_for_loads_(allocator_.Adapter(kArenaAllocLSE)), |
| 61 | possibly_removed_stores_(allocator_.Adapter(kArenaAllocLSE)), |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 62 | singleton_new_instances_(allocator_.Adapter(kArenaAllocLSE)), |
| 63 | singleton_new_arrays_(allocator_.Adapter(kArenaAllocLSE)) { |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 64 | } |
| 65 | |
| 66 | void VisitBasicBlock(HBasicBlock* block) OVERRIDE { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 67 | // Populate the heap_values array for this block. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 68 | // TODO: try to reuse the heap_values array from one predecessor if possible. |
| 69 | if (block->IsLoopHeader()) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 70 | HandleLoopSideEffects(block); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 71 | } else { |
| 72 | MergePredecessorValues(block); |
| 73 | } |
| 74 | HGraphVisitor::VisitBasicBlock(block); |
| 75 | } |
| 76 | |
Vladimir Marko | 94539fd | 2017-11-15 17:52:46 +0000 | [diff] [blame] | 77 | HTypeConversion* AddTypeConversionIfNecessary(HInstruction* instruction, |
| 78 | HInstruction* value, |
| 79 | DataType::Type expected_type) { |
| 80 | HTypeConversion* type_conversion = nullptr; |
| 81 | // Should never add type conversion into boolean value. |
| 82 | if (expected_type != DataType::Type::kBool && |
| 83 | !DataType::IsTypeConversionImplicit(value->GetType(), expected_type)) { |
| 84 | type_conversion = new (GetGraph()->GetAllocator()) HTypeConversion( |
| 85 | expected_type, value, instruction->GetDexPc()); |
| 86 | instruction->GetBlock()->InsertInstructionBefore(type_conversion, instruction); |
| 87 | } |
| 88 | return type_conversion; |
| 89 | } |
| 90 | |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 91 | // Find an instruction's substitute if it should be removed. |
Mingyao Yang | 206070c | 2017-11-29 23:01:58 -0800 | [diff] [blame] | 92 | // Return the same instruction if it should not be removed. |
| 93 | HInstruction* FindSubstitute(HInstruction* instruction) { |
| 94 | size_t size = removed_loads_.size(); |
| 95 | for (size_t i = 0; i < size; i++) { |
| 96 | if (removed_loads_[i] == instruction) { |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 97 | return substitute_instructions_for_loads_[i]; |
Mingyao Yang | 206070c | 2017-11-29 23:01:58 -0800 | [diff] [blame] | 98 | } |
| 99 | } |
| 100 | return instruction; |
| 101 | } |
| 102 | |
Vladimir Marko | 94539fd | 2017-11-15 17:52:46 +0000 | [diff] [blame] | 103 | void AddRemovedLoad(HInstruction* load, HInstruction* heap_value) { |
| 104 | DCHECK_EQ(FindSubstitute(heap_value), heap_value) << |
| 105 | "Unexpected heap_value that has a substitute " << heap_value->DebugName(); |
| 106 | removed_loads_.push_back(load); |
| 107 | substitute_instructions_for_loads_.push_back(heap_value); |
| 108 | } |
| 109 | |
| 110 | // Scan the list of removed loads to see if we can reuse `type_conversion`, if |
| 111 | // the other removed load has the same substitute and type and is dominated |
| 112 | // by `type_conversioni`. |
| 113 | void TryToReuseTypeConversion(HInstruction* type_conversion, size_t index) { |
| 114 | size_t size = removed_loads_.size(); |
| 115 | HInstruction* load = removed_loads_[index]; |
| 116 | HInstruction* substitute = substitute_instructions_for_loads_[index]; |
| 117 | for (size_t j = index + 1; j < size; j++) { |
| 118 | HInstruction* load2 = removed_loads_[j]; |
| 119 | HInstruction* substitute2 = substitute_instructions_for_loads_[j]; |
| 120 | if (load2 == nullptr) { |
| 121 | DCHECK(substitute2->IsTypeConversion()); |
| 122 | continue; |
| 123 | } |
| 124 | DCHECK(load2->IsInstanceFieldGet() || |
| 125 | load2->IsStaticFieldGet() || |
| 126 | load2->IsArrayGet()); |
| 127 | DCHECK(substitute2 != nullptr); |
| 128 | if (substitute2 == substitute && |
| 129 | load2->GetType() == load->GetType() && |
| 130 | type_conversion->GetBlock()->Dominates(load2->GetBlock()) && |
| 131 | // Don't share across irreducible loop headers. |
| 132 | // TODO: can be more fine-grained than this by testing each dominator. |
| 133 | (load2->GetBlock() == type_conversion->GetBlock() || |
| 134 | !GetGraph()->HasIrreducibleLoops())) { |
| 135 | // The removed_loads_ are added in reverse post order. |
| 136 | DCHECK(type_conversion->StrictlyDominates(load2)); |
| 137 | load2->ReplaceWith(type_conversion); |
| 138 | load2->GetBlock()->RemoveInstruction(load2); |
| 139 | removed_loads_[j] = nullptr; |
| 140 | substitute_instructions_for_loads_[j] = type_conversion; |
| 141 | } |
| 142 | } |
| 143 | } |
| 144 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 145 | // Remove recorded instructions that should be eliminated. |
| 146 | void RemoveInstructions() { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 147 | size_t size = removed_loads_.size(); |
| 148 | DCHECK_EQ(size, substitute_instructions_for_loads_.size()); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 149 | for (size_t i = 0; i < size; i++) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 150 | HInstruction* load = removed_loads_[i]; |
Vladimir Marko | 94539fd | 2017-11-15 17:52:46 +0000 | [diff] [blame] | 151 | if (load == nullptr) { |
| 152 | // The load has been handled in the scan for type conversion below. |
| 153 | DCHECK(substitute_instructions_for_loads_[i]->IsTypeConversion()); |
| 154 | continue; |
| 155 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 156 | DCHECK(load->IsInstanceFieldGet() || |
| 157 | load->IsStaticFieldGet() || |
Nicolas Geoffray | 8c4ddb2 | 2017-11-13 11:49:53 +0000 | [diff] [blame] | 158 | load->IsArrayGet()); |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 159 | HInstruction* substitute = substitute_instructions_for_loads_[i]; |
| 160 | DCHECK(substitute != nullptr); |
Mingyao Yang | 206070c | 2017-11-29 23:01:58 -0800 | [diff] [blame] | 161 | // We proactively retrieve the substitute for a removed load, so |
| 162 | // a load that has a substitute should not be observed as a heap |
| 163 | // location value. |
| 164 | DCHECK_EQ(FindSubstitute(substitute), substitute); |
Vladimir Marko | 94539fd | 2017-11-15 17:52:46 +0000 | [diff] [blame] | 165 | |
| 166 | // The load expects to load the heap value as type load->GetType(). |
| 167 | // However the tracked heap value may not be of that type. An explicit |
| 168 | // type conversion may be needed. |
| 169 | // There are actually three types involved here: |
| 170 | // (1) tracked heap value's type (type A) |
| 171 | // (2) heap location (field or element)'s type (type B) |
| 172 | // (3) load's type (type C) |
| 173 | // We guarantee that type A stored as type B and then fetched out as |
| 174 | // type C is the same as casting from type A to type C directly, since |
| 175 | // type B and type C will have the same size which is guarenteed in |
| 176 | // HInstanceFieldGet/HStaticFieldGet/HArrayGet's SetType(). |
| 177 | // So we only need one type conversion from type A to type C. |
| 178 | HTypeConversion* type_conversion = AddTypeConversionIfNecessary( |
| 179 | load, substitute, load->GetType()); |
| 180 | if (type_conversion != nullptr) { |
| 181 | TryToReuseTypeConversion(type_conversion, i); |
| 182 | load->ReplaceWith(type_conversion); |
| 183 | substitute_instructions_for_loads_[i] = type_conversion; |
| 184 | } else { |
| 185 | load->ReplaceWith(substitute); |
| 186 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 187 | load->GetBlock()->RemoveInstruction(load); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 188 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 189 | |
| 190 | // At this point, stores in possibly_removed_stores_ can be safely removed. |
Mingyao Yang | 8697490 | 2017-03-01 14:03:51 -0800 | [diff] [blame] | 191 | for (HInstruction* store : possibly_removed_stores_) { |
Nicolas Geoffray | 8c4ddb2 | 2017-11-13 11:49:53 +0000 | [diff] [blame] | 192 | DCHECK(store->IsInstanceFieldSet() || store->IsStaticFieldSet() || store->IsArraySet()); |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 193 | store->GetBlock()->RemoveInstruction(store); |
| 194 | } |
| 195 | |
Igor Murashkin | d01745e | 2017-04-05 16:40:31 -0700 | [diff] [blame] | 196 | // Eliminate singleton-classified instructions: |
| 197 | // * - Constructor fences (they never escape this thread). |
| 198 | // * - Allocations (if they are unused). |
Mingyao Yang | 8697490 | 2017-03-01 14:03:51 -0800 | [diff] [blame] | 199 | for (HInstruction* new_instance : singleton_new_instances_) { |
Igor Murashkin | 6ef4567 | 2017-08-08 13:59:55 -0700 | [diff] [blame] | 200 | size_t removed = HConstructorFence::RemoveConstructorFences(new_instance); |
| 201 | MaybeRecordStat(stats_, |
| 202 | MethodCompilationStat::kConstructorFenceRemovedLSE, |
| 203 | removed); |
Igor Murashkin | d01745e | 2017-04-05 16:40:31 -0700 | [diff] [blame] | 204 | |
Mingyao Yang | 062157f | 2016-03-02 10:15:36 -0800 | [diff] [blame] | 205 | if (!new_instance->HasNonEnvironmentUses()) { |
| 206 | new_instance->RemoveEnvironmentUsers(); |
| 207 | new_instance->GetBlock()->RemoveInstruction(new_instance); |
| 208 | } |
| 209 | } |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 210 | for (HInstruction* new_array : singleton_new_arrays_) { |
| 211 | size_t removed = HConstructorFence::RemoveConstructorFences(new_array); |
| 212 | MaybeRecordStat(stats_, |
| 213 | MethodCompilationStat::kConstructorFenceRemovedLSE, |
| 214 | removed); |
| 215 | |
| 216 | if (!new_array->HasNonEnvironmentUses()) { |
| 217 | new_array->RemoveEnvironmentUsers(); |
| 218 | new_array->GetBlock()->RemoveInstruction(new_array); |
| 219 | } |
| 220 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 221 | } |
| 222 | |
| 223 | private: |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 224 | // If heap_values[index] is an instance field store, need to keep the store. |
| 225 | // This is necessary if a heap value is killed due to merging, or loop side |
| 226 | // effects (which is essentially merging also), since a load later from the |
| 227 | // location won't be eliminated. |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 228 | void KeepIfIsStore(HInstruction* heap_value) { |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 229 | if (heap_value == kDefaultHeapValue || |
| 230 | heap_value == kUnknownHeapValue || |
| 231 | !(heap_value->IsInstanceFieldSet() || heap_value->IsArraySet())) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 232 | return; |
| 233 | } |
| 234 | auto idx = std::find(possibly_removed_stores_.begin(), |
| 235 | possibly_removed_stores_.end(), heap_value); |
| 236 | if (idx != possibly_removed_stores_.end()) { |
| 237 | // Make sure the store is kept. |
| 238 | possibly_removed_stores_.erase(idx); |
| 239 | } |
| 240 | } |
| 241 | |
| 242 | void HandleLoopSideEffects(HBasicBlock* block) { |
| 243 | DCHECK(block->IsLoopHeader()); |
| 244 | int block_id = block->GetBlockId(); |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 245 | ScopedArenaVector<HInstruction*>& heap_values = heap_values_for_[block_id]; |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 246 | |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 247 | // Don't eliminate loads in irreducible loops. This is safe for singletons, because |
| 248 | // they are always used by the non-eliminated loop-phi. |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 249 | if (block->GetLoopInformation()->IsIrreducible()) { |
| 250 | if (kIsDebugBuild) { |
| 251 | for (size_t i = 0; i < heap_values.size(); i++) { |
| 252 | DCHECK_EQ(heap_values[i], kUnknownHeapValue); |
| 253 | } |
| 254 | } |
| 255 | return; |
| 256 | } |
| 257 | |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 258 | HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); |
| 259 | ScopedArenaVector<HInstruction*>& pre_header_heap_values = |
| 260 | heap_values_for_[pre_header->GetBlockId()]; |
| 261 | |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 262 | // Inherit the values from pre-header. |
| 263 | for (size_t i = 0; i < heap_values.size(); i++) { |
| 264 | heap_values[i] = pre_header_heap_values[i]; |
| 265 | } |
| 266 | |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 267 | // We do a single pass in reverse post order. For loops, use the side effects as a hint |
| 268 | // to see if the heap values should be killed. |
| 269 | if (side_effects_.GetLoopEffects(block).DoesAnyWrite()) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 270 | for (size_t i = 0; i < heap_values.size(); i++) { |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 271 | HeapLocation* location = heap_location_collector_.GetHeapLocation(i); |
| 272 | ReferenceInfo* ref_info = location->GetReferenceInfo(); |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 273 | if (ref_info->IsSingletonAndRemovable() && |
| 274 | !location->IsValueKilledByLoopSideEffects()) { |
| 275 | // A removable singleton's field that's not stored into inside a loop is |
Mingyao Yang | eb2d2d346e | 2017-03-02 13:26:17 -0800 | [diff] [blame] | 276 | // invariant throughout the loop. Nothing to do. |
Mingyao Yang | eb2d2d346e | 2017-03-02 13:26:17 -0800 | [diff] [blame] | 277 | } else { |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 278 | // heap value is killed by loop side effects (stored into directly, or |
| 279 | // due to aliasing). Or the heap value may be needed after method return |
| 280 | // or deoptimization. |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 281 | KeepIfIsStore(pre_header_heap_values[i]); |
| 282 | heap_values[i] = kUnknownHeapValue; |
Mingyao Yang | 803cbb9 | 2015-12-01 12:24:36 -0800 | [diff] [blame] | 283 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 284 | } |
| 285 | } |
| 286 | } |
| 287 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 288 | void MergePredecessorValues(HBasicBlock* block) { |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 289 | ArrayRef<HBasicBlock* const> predecessors(block->GetPredecessors()); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 290 | if (predecessors.size() == 0) { |
| 291 | return; |
| 292 | } |
Mingyao Yang | 46721ef | 2017-10-05 14:45:17 -0700 | [diff] [blame] | 293 | if (block->IsExitBlock()) { |
| 294 | // Exit block doesn't really merge values since the control flow ends in |
| 295 | // its predecessors. Each predecessor needs to make sure stores are kept |
| 296 | // if necessary. |
| 297 | return; |
| 298 | } |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 299 | |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 300 | ScopedArenaVector<HInstruction*>& heap_values = heap_values_for_[block->GetBlockId()]; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 301 | for (size_t i = 0; i < heap_values.size(); i++) { |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 302 | HInstruction* merged_value = nullptr; |
| 303 | // Whether merged_value is a result that's merged from all predecessors. |
| 304 | bool from_all_predecessors = true; |
| 305 | ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); |
| 306 | HInstruction* singleton_ref = nullptr; |
Mingyao Yang | eb2d2d346e | 2017-03-02 13:26:17 -0800 | [diff] [blame] | 307 | if (ref_info->IsSingleton()) { |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 308 | // We do more analysis of liveness when merging heap values for such |
| 309 | // cases since stores into such references may potentially be eliminated. |
| 310 | singleton_ref = ref_info->GetReference(); |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 311 | } |
| 312 | |
| 313 | for (HBasicBlock* predecessor : predecessors) { |
| 314 | HInstruction* pred_value = heap_values_for_[predecessor->GetBlockId()][i]; |
| 315 | if ((singleton_ref != nullptr) && |
| 316 | !singleton_ref->GetBlock()->Dominates(predecessor)) { |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 317 | // singleton_ref is not live in this predecessor. Skip this predecessor since |
| 318 | // it does not really have the location. |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 319 | DCHECK_EQ(pred_value, kUnknownHeapValue); |
| 320 | from_all_predecessors = false; |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 321 | continue; |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 322 | } |
| 323 | if (merged_value == nullptr) { |
| 324 | // First seen heap value. |
| 325 | merged_value = pred_value; |
| 326 | } else if (pred_value != merged_value) { |
| 327 | // There are conflicting values. |
| 328 | merged_value = kUnknownHeapValue; |
| 329 | break; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 330 | } |
| 331 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 332 | |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 333 | if (ref_info->IsSingleton()) { |
| 334 | if (ref_info->IsSingletonAndNonRemovable() || |
| 335 | (merged_value == kUnknownHeapValue && |
| 336 | !block->IsSingleReturnOrReturnVoidAllowingPhis())) { |
| 337 | // The heap value may be needed after method return or deoptimization, |
| 338 | // or there are conflicting heap values from different predecessors and |
| 339 | // this block is not a single return, |
| 340 | // keep the last store in each predecessor since future loads may not |
| 341 | // be eliminated. |
Mingyao Yang | 46721ef | 2017-10-05 14:45:17 -0700 | [diff] [blame] | 342 | for (HBasicBlock* predecessor : predecessors) { |
| 343 | ScopedArenaVector<HInstruction*>& pred_values = |
| 344 | heap_values_for_[predecessor->GetBlockId()]; |
| 345 | KeepIfIsStore(pred_values[i]); |
| 346 | } |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 347 | } |
Mingyao Yang | 46721ef | 2017-10-05 14:45:17 -0700 | [diff] [blame] | 348 | } else { |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 349 | // Currenctly we don't eliminate stores to non-singletons. |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 350 | } |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 351 | |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 352 | if ((merged_value == nullptr) || !from_all_predecessors) { |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 353 | DCHECK(singleton_ref != nullptr); |
| 354 | DCHECK((singleton_ref->GetBlock() == block) || |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 355 | !singleton_ref->GetBlock()->Dominates(block)); |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 356 | // singleton_ref is not defined before block or defined only in some of its |
| 357 | // predecessors, so block doesn't really have the location at its entry. |
| 358 | heap_values[i] = kUnknownHeapValue; |
Mingyao Yang | aec4e73 | 2018-01-08 13:11:35 -0800 | [diff] [blame] | 359 | } else { |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 360 | heap_values[i] = merged_value; |
Mingyao Yang | 58d9bfc | 2016-11-01 13:31:58 -0700 | [diff] [blame] | 361 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 362 | } |
| 363 | } |
| 364 | |
| 365 | // `instruction` is being removed. Try to see if the null check on it |
| 366 | // can be removed. This can happen if the same value is set in two branches |
| 367 | // but not in dominators. Such as: |
| 368 | // int[] a = foo(); |
| 369 | // if () { |
| 370 | // a[0] = 2; |
| 371 | // } else { |
| 372 | // a[0] = 2; |
| 373 | // } |
| 374 | // // a[0] can now be replaced with constant 2, and the null check on it can be removed. |
| 375 | void TryRemovingNullCheck(HInstruction* instruction) { |
| 376 | HInstruction* prev = instruction->GetPrevious(); |
| 377 | if ((prev != nullptr) && prev->IsNullCheck() && (prev == instruction->InputAt(0))) { |
| 378 | // Previous instruction is a null check for this instruction. Remove the null check. |
| 379 | prev->ReplaceWith(prev->InputAt(0)); |
| 380 | prev->GetBlock()->RemoveInstruction(prev); |
| 381 | } |
| 382 | } |
| 383 | |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 384 | HInstruction* GetDefaultValue(DataType::Type type) { |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 385 | switch (type) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 386 | case DataType::Type::kReference: |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 387 | return GetGraph()->GetNullConstant(); |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 388 | case DataType::Type::kBool: |
Vladimir Marko | d5d2f2c | 2017-09-26 12:37:26 +0100 | [diff] [blame] | 389 | case DataType::Type::kUint8: |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 390 | case DataType::Type::kInt8: |
| 391 | case DataType::Type::kUint16: |
| 392 | case DataType::Type::kInt16: |
| 393 | case DataType::Type::kInt32: |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 394 | return GetGraph()->GetIntConstant(0); |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 395 | case DataType::Type::kInt64: |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 396 | return GetGraph()->GetLongConstant(0); |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 397 | case DataType::Type::kFloat32: |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 398 | return GetGraph()->GetFloatConstant(0); |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 399 | case DataType::Type::kFloat64: |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 400 | return GetGraph()->GetDoubleConstant(0); |
| 401 | default: |
| 402 | UNREACHABLE(); |
| 403 | } |
| 404 | } |
| 405 | |
| 406 | void VisitGetLocation(HInstruction* instruction, |
| 407 | HInstruction* ref, |
| 408 | size_t offset, |
| 409 | HInstruction* index, |
xueliang.zhong | b50b16a | 2017-09-19 17:43:29 +0100 | [diff] [blame] | 410 | size_t vector_length, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 411 | int16_t declaring_class_def_index) { |
xueliang.zhong | c239a2b | 2017-04-27 15:31:37 +0100 | [diff] [blame] | 412 | HInstruction* original_ref = heap_location_collector_.HuntForOriginalReference(ref); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 413 | ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); |
| 414 | size_t idx = heap_location_collector_.FindHeapLocationIndex( |
xueliang.zhong | b50b16a | 2017-09-19 17:43:29 +0100 | [diff] [blame] | 415 | ref_info, offset, index, vector_length, declaring_class_def_index); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 416 | DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 417 | ScopedArenaVector<HInstruction*>& heap_values = |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 418 | heap_values_for_[instruction->GetBlock()->GetBlockId()]; |
| 419 | HInstruction* heap_value = heap_values[idx]; |
| 420 | if (heap_value == kDefaultHeapValue) { |
| 421 | HInstruction* constant = GetDefaultValue(instruction->GetType()); |
Vladimir Marko | 94539fd | 2017-11-15 17:52:46 +0000 | [diff] [blame] | 422 | AddRemovedLoad(instruction, constant); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 423 | heap_values[idx] = constant; |
| 424 | return; |
| 425 | } |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 426 | if (heap_value != kUnknownHeapValue) { |
| 427 | if (heap_value->IsInstanceFieldSet() || heap_value->IsArraySet()) { |
| 428 | HInstruction* store = heap_value; |
| 429 | // This load must be from a singleton since it's from the same |
| 430 | // field/element that a "removed" store puts the value. That store |
| 431 | // must be to a singleton's field/element. |
| 432 | DCHECK(ref_info->IsSingleton()); |
| 433 | // Get the real heap value of the store. |
| 434 | heap_value = heap_value->IsInstanceFieldSet() ? store->InputAt(1) : store->InputAt(2); |
| 435 | // heap_value may already have a substitute. |
| 436 | heap_value = FindSubstitute(heap_value); |
| 437 | } |
| 438 | } |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 439 | if (heap_value == kUnknownHeapValue) { |
| 440 | // Load isn't eliminated. Put the load as the value into the HeapLocation. |
| 441 | // This acts like GVN but with better aliasing analysis. |
| 442 | heap_values[idx] = instruction; |
| 443 | } else { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 444 | if (DataType::Kind(heap_value->GetType()) != DataType::Kind(instruction->GetType())) { |
Nicolas Geoffray | 0397163 | 2016-03-17 10:44:24 +0000 | [diff] [blame] | 445 | // The only situation where the same heap location has different type is when |
Nicolas Geoffray | 65fef30 | 2016-05-04 14:00:12 +0100 | [diff] [blame] | 446 | // we do an array get on an instruction that originates from the null constant |
| 447 | // (the null could be behind a field access, an array access, a null check or |
| 448 | // a bound type). |
| 449 | // In order to stay properly typed on primitive types, we do not eliminate |
| 450 | // the array gets. |
Nicolas Geoffray | 0397163 | 2016-03-17 10:44:24 +0000 | [diff] [blame] | 451 | if (kIsDebugBuild) { |
| 452 | DCHECK(heap_value->IsArrayGet()) << heap_value->DebugName(); |
| 453 | DCHECK(instruction->IsArrayGet()) << instruction->DebugName(); |
Nicolas Geoffray | 0397163 | 2016-03-17 10:44:24 +0000 | [diff] [blame] | 454 | } |
| 455 | return; |
| 456 | } |
Vladimir Marko | 94539fd | 2017-11-15 17:52:46 +0000 | [diff] [blame] | 457 | AddRemovedLoad(instruction, heap_value); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 458 | TryRemovingNullCheck(instruction); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 459 | } |
| 460 | } |
| 461 | |
| 462 | bool Equal(HInstruction* heap_value, HInstruction* value) { |
| 463 | if (heap_value == value) { |
| 464 | return true; |
| 465 | } |
| 466 | if (heap_value == kDefaultHeapValue && GetDefaultValue(value->GetType()) == value) { |
| 467 | return true; |
| 468 | } |
| 469 | return false; |
| 470 | } |
| 471 | |
| 472 | void VisitSetLocation(HInstruction* instruction, |
| 473 | HInstruction* ref, |
| 474 | size_t offset, |
| 475 | HInstruction* index, |
xueliang.zhong | b50b16a | 2017-09-19 17:43:29 +0100 | [diff] [blame] | 476 | size_t vector_length, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 477 | int16_t declaring_class_def_index, |
| 478 | HInstruction* value) { |
Mingyao Yang | 206070c | 2017-11-29 23:01:58 -0800 | [diff] [blame] | 479 | // value may already have a substitute. |
| 480 | value = FindSubstitute(value); |
xueliang.zhong | c239a2b | 2017-04-27 15:31:37 +0100 | [diff] [blame] | 481 | HInstruction* original_ref = heap_location_collector_.HuntForOriginalReference(ref); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 482 | ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(original_ref); |
| 483 | size_t idx = heap_location_collector_.FindHeapLocationIndex( |
xueliang.zhong | b50b16a | 2017-09-19 17:43:29 +0100 | [diff] [blame] | 484 | ref_info, offset, index, vector_length, declaring_class_def_index); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 485 | DCHECK_NE(idx, HeapLocationCollector::kHeapLocationNotFound); |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 486 | ScopedArenaVector<HInstruction*>& heap_values = |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 487 | heap_values_for_[instruction->GetBlock()->GetBlockId()]; |
| 488 | HInstruction* heap_value = heap_values[idx]; |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 489 | bool same_value = false; |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 490 | bool possibly_redundant = false; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 491 | if (Equal(heap_value, value)) { |
| 492 | // Store into the heap location with the same value. |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 493 | same_value = true; |
| 494 | } else if (index != nullptr && |
| 495 | heap_location_collector_.GetHeapLocation(idx)->HasAliasedLocations()) { |
| 496 | // For array element, don't eliminate stores if the location can be aliased |
| 497 | // (due to either ref or index aliasing). |
| 498 | } else if (ref_info->IsSingleton()) { |
| 499 | // Store into a field/element of a singleton. The value cannot be killed due to |
| 500 | // aliasing/invocation. It can be redundant since future loads can |
| 501 | // directly get the value set by this instruction. The value can still be killed due to |
| 502 | // merging or loop side effects. Stores whose values are killed due to merging/loop side |
| 503 | // effects later will be removed from possibly_removed_stores_ when that is detected. |
| 504 | // Stores whose values may be needed after method return or deoptimization |
| 505 | // are also removed from possibly_removed_stores_ when that is detected. |
| 506 | possibly_redundant = true; |
Mingyao Yang | 025c1a6 | 2017-10-30 11:19:57 -0700 | [diff] [blame] | 507 | HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation(); |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 508 | if (loop_info != nullptr) { |
| 509 | // instruction is a store in the loop so the loop must does write. |
Mingyao Yang | 025c1a6 | 2017-10-30 11:19:57 -0700 | [diff] [blame] | 510 | DCHECK(side_effects_.GetLoopEffects(loop_info->GetHeader()).DoesAnyWrite()); |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 511 | |
| 512 | if (loop_info->IsDefinedOutOfTheLoop(original_ref)) { |
| 513 | DCHECK(original_ref->GetBlock()->Dominates(loop_info->GetPreHeader())); |
Mingyao Yang | aec4e73 | 2018-01-08 13:11:35 -0800 | [diff] [blame] | 514 | // Keep the store since its value may be needed at the loop header. |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 515 | possibly_redundant = false; |
| 516 | } else { |
| 517 | // The singleton is created inside the loop. Value stored to it isn't needed at |
| 518 | // the loop header. This is true for outer loops also. |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 519 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 520 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 521 | } |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 522 | if (same_value || possibly_redundant) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 523 | possibly_removed_stores_.push_back(instruction); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 524 | } |
Mingyao Yang | e9d6e60 | 2015-10-23 17:08:42 -0700 | [diff] [blame] | 525 | |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 526 | if (!same_value) { |
| 527 | if (possibly_redundant) { |
| 528 | DCHECK(instruction->IsInstanceFieldSet() || instruction->IsArraySet()); |
| 529 | // Put the store as the heap value. If the value is loaded from heap |
| 530 | // by a load later, this store isn't really redundant. |
| 531 | heap_values[idx] = instruction; |
| 532 | } else { |
| 533 | heap_values[idx] = value; |
| 534 | } |
| 535 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 536 | // This store may kill values in other heap locations due to aliasing. |
| 537 | for (size_t i = 0; i < heap_values.size(); i++) { |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 538 | if (i == idx) { |
| 539 | continue; |
| 540 | } |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 541 | if (heap_values[i] == value) { |
Nicolas Geoffray | 8c4ddb2 | 2017-11-13 11:49:53 +0000 | [diff] [blame] | 542 | // Same value should be kept even if aliasing happens. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 543 | continue; |
| 544 | } |
| 545 | if (heap_values[i] == kUnknownHeapValue) { |
| 546 | // Value is already unknown, no need for aliasing check. |
| 547 | continue; |
| 548 | } |
| 549 | if (heap_location_collector_.MayAlias(i, idx)) { |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 550 | // Kill heap locations that may alias. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 551 | heap_values[i] = kUnknownHeapValue; |
| 552 | } |
| 553 | } |
| 554 | } |
| 555 | |
| 556 | void VisitInstanceFieldGet(HInstanceFieldGet* instruction) OVERRIDE { |
| 557 | HInstruction* obj = instruction->InputAt(0); |
| 558 | size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); |
| 559 | int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); |
xueliang.zhong | b50b16a | 2017-09-19 17:43:29 +0100 | [diff] [blame] | 560 | VisitGetLocation(instruction, |
| 561 | obj, |
| 562 | offset, |
| 563 | nullptr, |
| 564 | HeapLocation::kScalar, |
| 565 | declaring_class_def_index); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 566 | } |
| 567 | |
| 568 | void VisitInstanceFieldSet(HInstanceFieldSet* instruction) OVERRIDE { |
| 569 | HInstruction* obj = instruction->InputAt(0); |
| 570 | size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); |
| 571 | int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); |
| 572 | HInstruction* value = instruction->InputAt(1); |
xueliang.zhong | b50b16a | 2017-09-19 17:43:29 +0100 | [diff] [blame] | 573 | VisitSetLocation(instruction, |
| 574 | obj, |
| 575 | offset, |
| 576 | nullptr, |
| 577 | HeapLocation::kScalar, |
| 578 | declaring_class_def_index, |
| 579 | value); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 580 | } |
| 581 | |
| 582 | void VisitStaticFieldGet(HStaticFieldGet* instruction) OVERRIDE { |
| 583 | HInstruction* cls = instruction->InputAt(0); |
| 584 | size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); |
| 585 | int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); |
xueliang.zhong | b50b16a | 2017-09-19 17:43:29 +0100 | [diff] [blame] | 586 | VisitGetLocation(instruction, |
| 587 | cls, |
| 588 | offset, |
| 589 | nullptr, |
| 590 | HeapLocation::kScalar, |
| 591 | declaring_class_def_index); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 592 | } |
| 593 | |
| 594 | void VisitStaticFieldSet(HStaticFieldSet* instruction) OVERRIDE { |
| 595 | HInstruction* cls = instruction->InputAt(0); |
| 596 | size_t offset = instruction->GetFieldInfo().GetFieldOffset().SizeValue(); |
| 597 | int16_t declaring_class_def_index = instruction->GetFieldInfo().GetDeclaringClassDefIndex(); |
| 598 | HInstruction* value = instruction->InputAt(1); |
xueliang.zhong | b50b16a | 2017-09-19 17:43:29 +0100 | [diff] [blame] | 599 | VisitSetLocation(instruction, |
| 600 | cls, |
| 601 | offset, |
| 602 | nullptr, |
| 603 | HeapLocation::kScalar, |
| 604 | declaring_class_def_index, |
| 605 | value); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 606 | } |
| 607 | |
| 608 | void VisitArrayGet(HArrayGet* instruction) OVERRIDE { |
| 609 | HInstruction* array = instruction->InputAt(0); |
| 610 | HInstruction* index = instruction->InputAt(1); |
| 611 | VisitGetLocation(instruction, |
| 612 | array, |
| 613 | HeapLocation::kInvalidFieldOffset, |
| 614 | index, |
xueliang.zhong | b50b16a | 2017-09-19 17:43:29 +0100 | [diff] [blame] | 615 | HeapLocation::kScalar, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 616 | HeapLocation::kDeclaringClassDefIndexForArrays); |
| 617 | } |
| 618 | |
| 619 | void VisitArraySet(HArraySet* instruction) OVERRIDE { |
| 620 | HInstruction* array = instruction->InputAt(0); |
| 621 | HInstruction* index = instruction->InputAt(1); |
| 622 | HInstruction* value = instruction->InputAt(2); |
| 623 | VisitSetLocation(instruction, |
| 624 | array, |
| 625 | HeapLocation::kInvalidFieldOffset, |
| 626 | index, |
xueliang.zhong | b50b16a | 2017-09-19 17:43:29 +0100 | [diff] [blame] | 627 | HeapLocation::kScalar, |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 628 | HeapLocation::kDeclaringClassDefIndexForArrays, |
| 629 | value); |
| 630 | } |
| 631 | |
Mingyao Yang | eb2d2d346e | 2017-03-02 13:26:17 -0800 | [diff] [blame] | 632 | void VisitDeoptimize(HDeoptimize* instruction) { |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 633 | const ScopedArenaVector<HInstruction*>& heap_values = |
Mingyao Yang | eb2d2d346e | 2017-03-02 13:26:17 -0800 | [diff] [blame] | 634 | heap_values_for_[instruction->GetBlock()->GetBlockId()]; |
| 635 | for (HInstruction* heap_value : heap_values) { |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 636 | // Filter out fake instructions before checking instruction kind below. |
| 637 | if (heap_value == kUnknownHeapValue || heap_value == kDefaultHeapValue) { |
| 638 | continue; |
| 639 | } |
Mingyao Yang | eb2d2d346e | 2017-03-02 13:26:17 -0800 | [diff] [blame] | 640 | // A store is kept as the heap value for possibly removed stores. |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 641 | if (heap_value->IsInstanceFieldSet() || heap_value->IsArraySet()) { |
| 642 | // Check whether the reference for a store is used by an environment local of |
| 643 | // HDeoptimize. |
Mingyao Yang | eb2d2d346e | 2017-03-02 13:26:17 -0800 | [diff] [blame] | 644 | HInstruction* reference = heap_value->InputAt(0); |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 645 | DCHECK(heap_location_collector_.FindReferenceInfoOf(reference)->IsSingleton()); |
| 646 | for (const HUseListNode<HEnvironment*>& use : reference->GetEnvUses()) { |
| 647 | HEnvironment* user = use.GetUser(); |
| 648 | if (user->GetHolder() == instruction) { |
| 649 | // The singleton for the store is visible at this deoptimization |
| 650 | // point. Need to keep the store so that the heap value is |
| 651 | // seen by the interpreter. |
Mingyao Yang | eb2d2d346e | 2017-03-02 13:26:17 -0800 | [diff] [blame] | 652 | KeepIfIsStore(heap_value); |
| 653 | } |
| 654 | } |
| 655 | } |
| 656 | } |
| 657 | } |
| 658 | |
Mingyao Yang | 46721ef | 2017-10-05 14:45:17 -0700 | [diff] [blame] | 659 | // Keep necessary stores before exiting a method via return/throw. |
| 660 | void HandleExit(HBasicBlock* block) { |
| 661 | const ScopedArenaVector<HInstruction*>& heap_values = |
| 662 | heap_values_for_[block->GetBlockId()]; |
| 663 | for (size_t i = 0; i < heap_values.size(); i++) { |
| 664 | HInstruction* heap_value = heap_values[i]; |
| 665 | ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); |
| 666 | if (!ref_info->IsSingletonAndRemovable()) { |
| 667 | KeepIfIsStore(heap_value); |
| 668 | } |
| 669 | } |
| 670 | } |
| 671 | |
| 672 | void VisitReturn(HReturn* instruction) OVERRIDE { |
| 673 | HandleExit(instruction->GetBlock()); |
| 674 | } |
| 675 | |
| 676 | void VisitReturnVoid(HReturnVoid* return_void) OVERRIDE { |
| 677 | HandleExit(return_void->GetBlock()); |
| 678 | } |
| 679 | |
| 680 | void VisitThrow(HThrow* throw_instruction) OVERRIDE { |
| 681 | HandleExit(throw_instruction->GetBlock()); |
| 682 | } |
| 683 | |
Mingyao Yang | 293f1c0 | 2017-11-08 15:22:17 -0800 | [diff] [blame] | 684 | void HandleInvoke(HInstruction* instruction) { |
| 685 | SideEffects side_effects = instruction->GetSideEffects(); |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 686 | ScopedArenaVector<HInstruction*>& heap_values = |
Mingyao Yang | 293f1c0 | 2017-11-08 15:22:17 -0800 | [diff] [blame] | 687 | heap_values_for_[instruction->GetBlock()->GetBlockId()]; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 688 | for (size_t i = 0; i < heap_values.size(); i++) { |
| 689 | ReferenceInfo* ref_info = heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo(); |
| 690 | if (ref_info->IsSingleton()) { |
| 691 | // Singleton references cannot be seen by the callee. |
| 692 | } else { |
Mingyao Yang | 293f1c0 | 2017-11-08 15:22:17 -0800 | [diff] [blame] | 693 | if (side_effects.DoesAnyRead()) { |
| 694 | KeepIfIsStore(heap_values[i]); |
| 695 | } |
| 696 | if (side_effects.DoesAnyWrite()) { |
| 697 | heap_values[i] = kUnknownHeapValue; |
| 698 | } |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 699 | } |
| 700 | } |
| 701 | } |
| 702 | |
Mingyao Yang | c62b7ec | 2017-10-25 16:42:15 -0700 | [diff] [blame] | 703 | void VisitInvoke(HInvoke* invoke) OVERRIDE { |
Orion Hodson | ac14139 | 2017-01-13 11:53:47 +0000 | [diff] [blame] | 704 | HandleInvoke(invoke); |
| 705 | } |
| 706 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 707 | void VisitClinitCheck(HClinitCheck* clinit) OVERRIDE { |
| 708 | HandleInvoke(clinit); |
| 709 | } |
| 710 | |
| 711 | void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instruction) OVERRIDE { |
| 712 | // Conservatively treat it as an invocation. |
| 713 | HandleInvoke(instruction); |
| 714 | } |
| 715 | |
| 716 | void VisitUnresolvedInstanceFieldSet(HUnresolvedInstanceFieldSet* instruction) OVERRIDE { |
| 717 | // Conservatively treat it as an invocation. |
| 718 | HandleInvoke(instruction); |
| 719 | } |
| 720 | |
| 721 | void VisitUnresolvedStaticFieldGet(HUnresolvedStaticFieldGet* instruction) OVERRIDE { |
| 722 | // Conservatively treat it as an invocation. |
| 723 | HandleInvoke(instruction); |
| 724 | } |
| 725 | |
| 726 | void VisitUnresolvedStaticFieldSet(HUnresolvedStaticFieldSet* instruction) OVERRIDE { |
| 727 | // Conservatively treat it as an invocation. |
| 728 | HandleInvoke(instruction); |
| 729 | } |
| 730 | |
| 731 | void VisitNewInstance(HNewInstance* new_instance) OVERRIDE { |
| 732 | ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_instance); |
| 733 | if (ref_info == nullptr) { |
| 734 | // new_instance isn't used for field accesses. No need to process it. |
| 735 | return; |
| 736 | } |
Mingyao Yang | 025c1a6 | 2017-10-30 11:19:57 -0700 | [diff] [blame] | 737 | if (ref_info->IsSingletonAndRemovable() && !new_instance->NeedsChecks()) { |
| 738 | DCHECK(!new_instance->IsFinalizable()); |
Mingyao Yang | 062157f | 2016-03-02 10:15:36 -0800 | [diff] [blame] | 739 | singleton_new_instances_.push_back(new_instance); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 740 | } |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 741 | ScopedArenaVector<HInstruction*>& heap_values = |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 742 | heap_values_for_[new_instance->GetBlock()->GetBlockId()]; |
| 743 | for (size_t i = 0; i < heap_values.size(); i++) { |
| 744 | HInstruction* ref = |
| 745 | heap_location_collector_.GetHeapLocation(i)->GetReferenceInfo()->GetReference(); |
| 746 | size_t offset = heap_location_collector_.GetHeapLocation(i)->GetOffset(); |
| 747 | if (ref == new_instance && offset >= mirror::kObjectHeaderSize) { |
| 748 | // Instance fields except the header fields are set to default heap values. |
| 749 | heap_values[i] = kDefaultHeapValue; |
| 750 | } |
| 751 | } |
| 752 | } |
| 753 | |
Mingyao Yang | 8697490 | 2017-03-01 14:03:51 -0800 | [diff] [blame] | 754 | void VisitNewArray(HNewArray* new_array) OVERRIDE { |
| 755 | ReferenceInfo* ref_info = heap_location_collector_.FindReferenceInfoOf(new_array); |
| 756 | if (ref_info == nullptr) { |
| 757 | // new_array isn't used for array accesses. No need to process it. |
| 758 | return; |
| 759 | } |
| 760 | if (ref_info->IsSingletonAndRemovable()) { |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 761 | singleton_new_arrays_.push_back(new_array); |
Mingyao Yang | 8697490 | 2017-03-01 14:03:51 -0800 | [diff] [blame] | 762 | } |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 763 | ScopedArenaVector<HInstruction*>& heap_values = |
Mingyao Yang | 8697490 | 2017-03-01 14:03:51 -0800 | [diff] [blame] | 764 | heap_values_for_[new_array->GetBlock()->GetBlockId()]; |
| 765 | for (size_t i = 0; i < heap_values.size(); i++) { |
| 766 | HeapLocation* location = heap_location_collector_.GetHeapLocation(i); |
| 767 | HInstruction* ref = location->GetReferenceInfo()->GetReference(); |
| 768 | if (ref == new_array && location->GetIndex() != nullptr) { |
| 769 | // Array elements are set to default heap values. |
| 770 | heap_values[i] = kDefaultHeapValue; |
| 771 | } |
| 772 | } |
| 773 | } |
| 774 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 775 | const HeapLocationCollector& heap_location_collector_; |
| 776 | const SideEffectsAnalysis& side_effects_; |
| 777 | |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 778 | // Use local allocator for allocating memory. |
| 779 | ScopedArenaAllocator allocator_; |
| 780 | |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 781 | // One array of heap values for each block. |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 782 | ScopedArenaVector<ScopedArenaVector<HInstruction*>> heap_values_for_; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 783 | |
| 784 | // We record the instructions that should be eliminated but may be |
| 785 | // used by heap locations. They'll be removed in the end. |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 786 | ScopedArenaVector<HInstruction*> removed_loads_; |
| 787 | ScopedArenaVector<HInstruction*> substitute_instructions_for_loads_; |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 788 | |
| 789 | // Stores in this list may be removed from the list later when it's |
| 790 | // found that the store cannot be eliminated. |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 791 | ScopedArenaVector<HInstruction*> possibly_removed_stores_; |
Mingyao Yang | fb8464a | 2015-11-02 10:56:59 -0800 | [diff] [blame] | 792 | |
Vladimir Marko | 009d166 | 2017-10-10 13:21:15 +0100 | [diff] [blame] | 793 | ScopedArenaVector<HInstruction*> singleton_new_instances_; |
Nicolas Geoffray | e97949e | 2018-01-25 10:42:01 +0000 | [diff] [blame^] | 794 | ScopedArenaVector<HInstruction*> singleton_new_arrays_; |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 795 | |
| 796 | DISALLOW_COPY_AND_ASSIGN(LSEVisitor); |
| 797 | }; |
| 798 | |
| 799 | void LoadStoreElimination::Run() { |
David Brazdil | 8993caf | 2015-12-07 10:04:40 +0000 | [diff] [blame] | 800 | if (graph_->IsDebuggable() || graph_->HasTryCatch()) { |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 801 | // Debugger may set heap values or trigger deoptimization of callers. |
David Brazdil | 8993caf | 2015-12-07 10:04:40 +0000 | [diff] [blame] | 802 | // Try/catch support not implemented yet. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 803 | // Skip this optimization. |
| 804 | return; |
| 805 | } |
xueliang.zhong | c239a2b | 2017-04-27 15:31:37 +0100 | [diff] [blame] | 806 | const HeapLocationCollector& heap_location_collector = lsa_.GetHeapLocationCollector(); |
| 807 | if (heap_location_collector.GetNumberOfHeapLocations() == 0) { |
| 808 | // No HeapLocation information from LSA, skip this optimization. |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 809 | return; |
| 810 | } |
xueliang.zhong | c239a2b | 2017-04-27 15:31:37 +0100 | [diff] [blame] | 811 | |
Nicolas Geoffray | 8c4ddb2 | 2017-11-13 11:49:53 +0000 | [diff] [blame] | 812 | // TODO: analyze VecLoad/VecStore better. |
| 813 | if (graph_->HasSIMD()) { |
| 814 | return; |
| 815 | } |
| 816 | |
Igor Murashkin | 6ef4567 | 2017-08-08 13:59:55 -0700 | [diff] [blame] | 817 | LSEVisitor lse_visitor(graph_, heap_location_collector, side_effects_, stats_); |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 818 | for (HBasicBlock* block : graph_->GetReversePostOrder()) { |
| 819 | lse_visitor.VisitBasicBlock(block); |
Mingyao Yang | 8df69d4 | 2015-10-22 15:40:58 -0700 | [diff] [blame] | 820 | } |
| 821 | lse_visitor.RemoveInstructions(); |
| 822 | } |
| 823 | |
| 824 | } // namespace art |