1 /* 2 * Copyright (C) 2017 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 "constructor_fence_redundancy_elimination.h" 18 19 #include "base/arena_allocator.h" 20 #include "base/scoped_arena_allocator.h" 21 #include "base/scoped_arena_containers.h" 22 23 namespace art { 24 25 static constexpr bool kCfreLogFenceInputCount = false; 26 27 // TODO: refactor this code by reusing escape analysis. 28 class CFREVisitor : public HGraphVisitor { 29 public: 30 CFREVisitor(HGraph* graph, OptimizingCompilerStats* stats) 31 : HGraphVisitor(graph), 32 scoped_allocator_(graph->GetArenaStack()), 33 candidate_fences_(scoped_allocator_.Adapter(kArenaAllocCFRE)), 34 candidate_fence_targets_(scoped_allocator_.Adapter(kArenaAllocCFRE)), 35 stats_(stats) {} 36 37 void VisitBasicBlock(HBasicBlock* block) override { 38 // Visit all instructions in block. 39 HGraphVisitor::VisitBasicBlock(block); 40 41 // If there were any unmerged fences left, merge them together, 42 // the objects are considered 'published' at the end of the block. 43 MergeCandidateFences(); 44 } 45 46 void VisitConstructorFence(HConstructorFence* constructor_fence) override { 47 candidate_fences_.push_back(constructor_fence); 48 49 for (size_t input_idx = 0; input_idx < constructor_fence->InputCount(); ++input_idx) { 50 candidate_fence_targets_.insert(constructor_fence->InputAt(input_idx)); 51 } 52 } 53 54 void VisitBoundType(HBoundType* bound_type) override { 55 VisitAlias(bound_type); 56 } 57 58 void VisitNullCheck(HNullCheck* null_check) override { 59 VisitAlias(null_check); 60 } 61 62 void VisitSelect(HSelect* select) override { 63 VisitAlias(select); 64 } 65 66 void VisitInstanceFieldSet(HInstanceFieldSet* instruction) override { 67 HInstruction* value = instruction->InputAt(1); 68 VisitSetLocation(instruction, value); 69 } 70 71 void VisitStaticFieldSet(HStaticFieldSet* instruction) override { 72 HInstruction* value = instruction->InputAt(1); 73 VisitSetLocation(instruction, value); 74 } 75 76 void VisitArraySet(HArraySet* instruction) override { 77 HInstruction* value = instruction->InputAt(2); 78 VisitSetLocation(instruction, value); 79 } 80 81 void VisitDeoptimize(HDeoptimize* instruction ATTRIBUTE_UNUSED) override { 82 // Pessimize: Merge all fences. 83 MergeCandidateFences(); 84 } 85 86 void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) override { 87 HandleInvoke(invoke); 88 } 89 90 void VisitInvokeVirtual(HInvokeVirtual* invoke) override { 91 HandleInvoke(invoke); 92 } 93 94 void VisitInvokeInterface(HInvokeInterface* invoke) override { 95 HandleInvoke(invoke); 96 } 97 98 void VisitInvokeUnresolved(HInvokeUnresolved* invoke) override { 99 HandleInvoke(invoke); 100 } 101 102 void VisitInvokePolymorphic(HInvokePolymorphic* invoke) override { 103 HandleInvoke(invoke); 104 } 105 106 void VisitClinitCheck(HClinitCheck* clinit) override { 107 HandleInvoke(clinit); 108 } 109 110 void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instruction) override { 111 // Conservatively treat it as an invocation. 112 HandleInvoke(instruction); 113 } 114 115 void VisitUnresolvedInstanceFieldSet(HUnresolvedInstanceFieldSet* instruction) override { 116 // Conservatively treat it as an invocation. 117 HandleInvoke(instruction); 118 } 119 120 void VisitUnresolvedStaticFieldGet(HUnresolvedStaticFieldGet* instruction) override { 121 // Conservatively treat it as an invocation. 122 HandleInvoke(instruction); 123 } 124 125 void VisitUnresolvedStaticFieldSet(HUnresolvedStaticFieldSet* instruction) override { 126 // Conservatively treat it as an invocation. 127 HandleInvoke(instruction); 128 } 129 130 private: 131 void HandleInvoke(HInstruction* invoke) { 132 // An object is considered "published" if it escapes into an invoke as any of the parameters. 133 if (HasInterestingPublishTargetAsInput(invoke)) { 134 MergeCandidateFences(); 135 } 136 } 137 138 // Called by any instruction visitor that may create an alias. 139 // These instructions may create an alias: 140 // - BoundType 141 // - NullCheck 142 // - Select 143 // 144 // These also create an alias, but are not handled by this function: 145 // - Phi: propagates values across blocks, but we always merge at the end of a block. 146 // - Invoke: this is handled by HandleInvoke. 147 void VisitAlias(HInstruction* aliasing_inst) { 148 // An object is considered "published" if it becomes aliased by other instructions. 149 if (HasInterestingPublishTargetAsInput(aliasing_inst)) { 150 // Note that constructing a "NullCheck" for new-instance, new-array, 151 // or a 'this' (receiver) reference is impossible. 152 // 153 // If by some reason we actually encounter such a NullCheck(FenceTarget), 154 // we LOG(WARNING). 155 if (UNLIKELY(aliasing_inst->IsNullCheck())) { 156 LOG(kIsDebugBuild ? FATAL : WARNING) 157 << "Unexpected instruction: NullCheck; should not be legal in graph"; 158 // We then do a best-effort to handle this case. 159 } 160 MergeCandidateFences(); 161 } 162 } 163 164 void VisitSetLocation(HInstruction* inst ATTRIBUTE_UNUSED, HInstruction* store_input) { 165 // An object is considered "published" if it's stored onto the heap. 166 // Sidenote: A later "LSE" pass can still remove the fence if it proves the 167 // object doesn't actually escape. 168 if (IsInterestingPublishTarget(store_input)) { 169 // Merge all constructor fences that we've seen since 170 // the last interesting store (or since the beginning). 171 MergeCandidateFences(); 172 } 173 } 174 175 bool HasInterestingPublishTargetAsInput(HInstruction* inst) { 176 for (size_t input_count = 0; input_count < inst->InputCount(); ++input_count) { 177 if (IsInterestingPublishTarget(inst->InputAt(input_count))) { 178 return true; 179 } 180 } 181 182 return false; 183 } 184 185 // Merges all the existing fences we've seen so far into the last-most fence. 186 // 187 // This resets the list of candidate fences and their targets back to {}. 188 void MergeCandidateFences() { 189 if (candidate_fences_.empty()) { 190 // Nothing to do, need 1+ fences to merge. 191 return; 192 } 193 194 // The merge target is always the "last" candidate fence. 195 HConstructorFence* merge_target = candidate_fences_[candidate_fences_.size() - 1]; 196 197 for (HConstructorFence* fence : candidate_fences_) { 198 MaybeMerge(merge_target, fence); 199 } 200 201 if (kCfreLogFenceInputCount) { 202 LOG(INFO) << "CFRE-MergeCandidateFences: Post-merge fence input count " 203 << merge_target->InputCount(); 204 } 205 206 // Each merge acts as a cut-off point. The optimization is reset completely. 207 // In theory, we could push the fence as far as its publish, but in practice 208 // there is no benefit to this extra complexity unless we also reordered 209 // the stores to come later. 210 candidate_fences_.clear(); 211 candidate_fence_targets_.clear(); 212 } 213 214 // A publishing 'store' is only interesting if the value being stored 215 // is one of the fence `targets` in `candidate_fences`. 216 bool IsInterestingPublishTarget(HInstruction* store_input) const { 217 return candidate_fence_targets_.find(store_input) != candidate_fence_targets_.end(); 218 } 219 220 void MaybeMerge(HConstructorFence* target, HConstructorFence* src) { 221 if (target == src) { 222 return; // Don't merge a fence into itself. 223 // This is mostly for stats-purposes, we don't want to count merge(x,x) 224 // as removing a fence because it's a no-op. 225 } 226 227 target->Merge(src); 228 229 MaybeRecordStat(stats_, MethodCompilationStat::kConstructorFenceRemovedCFRE); 230 } 231 232 // Phase-local heap memory allocator for CFRE optimizer. 233 ScopedArenaAllocator scoped_allocator_; 234 235 // Set of constructor fences that we've seen in the current block. 236 // Each constructor fences acts as a guard for one or more `targets`. 237 // There exist no stores to any `targets` between any of these fences. 238 // 239 // Fences are in succession order (e.g. fence[i] succeeds fence[i-1] 240 // within the same basic block). 241 ScopedArenaVector<HConstructorFence*> candidate_fences_; 242 243 // Stores a set of the fence targets, to allow faster lookup of whether 244 // a detected publish is a target of one of the candidate fences. 245 ScopedArenaHashSet<HInstruction*> candidate_fence_targets_; 246 247 // Used to record stats about the optimization. 248 OptimizingCompilerStats* const stats_; 249 250 DISALLOW_COPY_AND_ASSIGN(CFREVisitor); 251 }; 252 253 bool ConstructorFenceRedundancyElimination::Run() { 254 CFREVisitor cfre_visitor(graph_, stats_); 255 256 // Arbitrarily visit in reverse-post order. 257 // The exact block visit order does not matter, as the algorithm 258 // only operates on a single block at a time. 259 cfre_visitor.VisitReversePostOrder(); 260 return true; 261 } 262 263 } // namespace art 264