Home | History | Annotate | Download | only in optimizing
      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