1 /*
2  * Copyright (C) 2016 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 "cha_guard_optimization.h"
18 
19 namespace art {
20 
21 // Note we can only do CHA guard elimination/motion in a single pass, since
22 // if a guard is not removed, another guard might be removed due to
23 // the existence of the first guard. The first guard should not be further
24 // removed in another pass. For example, due to further optimizations,
25 // a receiver of a guard might turn out to be a parameter value, or defined at
26 // a different site, which makes the guard removable as a result. However
27 // it's not safe to remove the guard in another pass since another guard might
28 // have been removed due to the existence of this guard.
29 //
30 // As a consequence, we decided not to rely on other passes to remove them
31 // (such as GVN or instruction simplifier).
32 
33 class CHAGuardVisitor : HGraphVisitor {
34  public:
CHAGuardVisitor(HGraph * graph)35   explicit CHAGuardVisitor(HGraph* graph)
36       : HGraphVisitor(graph),
37         block_has_cha_guard_(GetGraph()->GetBlocks().size(),
38                              0,
39                              graph->GetAllocator()->Adapter(kArenaAllocCHA)),
40         instruction_iterator_(nullptr) {
41     number_of_guards_to_visit_ = GetGraph()->GetNumberOfCHAGuards();
42     DCHECK_NE(number_of_guards_to_visit_, 0u);
43     // Will recount number of guards during guard optimization.
44     GetGraph()->SetNumberOfCHAGuards(0);
45   }
46 
47   void VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) override;
48 
49   void VisitBasicBlock(HBasicBlock* block) override;
50 
51  private:
52   void RemoveGuard(HShouldDeoptimizeFlag* flag);
53   // Return true if `flag` is removed.
54   bool OptimizeForParameter(HShouldDeoptimizeFlag* flag, HInstruction* receiver);
55   // Return true if `flag` is removed.
56   bool OptimizeWithDominatingGuard(HShouldDeoptimizeFlag* flag, HInstruction* receiver);
57   // Return true if `flag` is hoisted.
58   bool HoistGuard(HShouldDeoptimizeFlag* flag, HInstruction* receiver);
59 
60   // Record if each block has any CHA guard. It's updated during the
61   // reverse post order visit. Use int instead of bool since ArenaVector
62   // does not support bool.
63   ArenaVector<int> block_has_cha_guard_;
64 
65   // The iterator that's being used for this visitor. Need it to manually
66   // advance the iterator due to removing/moving more than one instruction.
67   HInstructionIterator* instruction_iterator_;
68 
69   // Used to short-circuit the pass when there is no more guards left to visit.
70   uint32_t number_of_guards_to_visit_;
71 
72   DISALLOW_COPY_AND_ASSIGN(CHAGuardVisitor);
73 };
74 
VisitBasicBlock(HBasicBlock * block)75 void CHAGuardVisitor::VisitBasicBlock(HBasicBlock* block) {
76   if (number_of_guards_to_visit_ == 0) {
77     return;
78   }
79   // Skip phis, just iterate through instructions.
80   HInstructionIterator it(block->GetInstructions());
81   instruction_iterator_ = &it;
82   for (; !it.Done(); it.Advance()) {
83     DCHECK(it.Current()->IsInBlock());
84     it.Current()->Accept(this);
85   }
86 }
87 
RemoveGuard(HShouldDeoptimizeFlag * flag)88 void CHAGuardVisitor::RemoveGuard(HShouldDeoptimizeFlag* flag) {
89   HBasicBlock* block = flag->GetBlock();
90   HInstruction* compare = flag->GetNext();
91   DCHECK(compare->IsNotEqual());
92   HInstruction* deopt = compare->GetNext();
93   DCHECK(deopt->IsDeoptimize());
94 
95   // Advance instruction iterator first before we remove the guard.
96   // We need to do it twice since we remove three instructions and the
97   // visitor is responsible for advancing it once.
98   instruction_iterator_->Advance();
99   instruction_iterator_->Advance();
100   block->RemoveInstruction(deopt);
101   block->RemoveInstruction(compare);
102   block->RemoveInstruction(flag);
103 }
104 
OptimizeForParameter(HShouldDeoptimizeFlag * flag,HInstruction * receiver)105 bool CHAGuardVisitor::OptimizeForParameter(HShouldDeoptimizeFlag* flag,
106                                            HInstruction* receiver) {
107   // If some compiled code is invalidated by CHA due to class loading, the
108   // compiled code will not be entered anymore. So the very fact that the
109   // compiled code is invoked guarantees that a parameter receiver conforms
110   // to all the CHA devirtualization assumptions made by the compiled code,
111   // since all parameter receivers pre-exist any (potential) invalidation of
112   // the compiled code.
113   //
114   // TODO: allow more cases such as a phi whose inputs are all parameters.
115   if (receiver->IsParameterValue()) {
116     RemoveGuard(flag);
117     return true;
118   }
119   return false;
120 }
121 
OptimizeWithDominatingGuard(HShouldDeoptimizeFlag * flag,HInstruction * receiver)122 bool CHAGuardVisitor::OptimizeWithDominatingGuard(HShouldDeoptimizeFlag* flag,
123                                                   HInstruction* receiver) {
124   // If there is another guard that dominates the current guard, and
125   // that guard is dominated by receiver's definition, then the current
126   // guard can be eliminated, since receiver must pre-exist that other
127   // guard, and passing that guard guarantees that receiver conforms to
128   // all the CHA devirtualization assumptions.
129   HBasicBlock* dominator = flag->GetBlock();
130   HBasicBlock* receiver_def_block = receiver->GetBlock();
131 
132   // Complexity of the following algorithm:
133   // We potentially need to traverse the full dominator chain to receiver_def_block,
134   // plus a (partial) linear search within one block for each guard.
135   // So the worst case for each guard is bounded by the size of the
136   // biggest block plus the depth of the dominating tree.
137 
138   while (dominator != receiver_def_block) {
139     if (block_has_cha_guard_[dominator->GetBlockId()] == 1) {
140       RemoveGuard(flag);
141       return true;
142     }
143     dominator = dominator->GetDominator();
144   }
145 
146   // At this point dominator is the block where receiver is defined.
147   // We do a linear search within dominator to see if there is a guard after
148   // receiver's definition.
149   HInstruction* instruction;
150   if (dominator == flag->GetBlock()) {
151     // Flag and receiver are defined in the same block. Search backward from
152     // the current guard.
153     instruction = flag->GetPrevious();
154   } else {
155     // Search backward from the last instruction of that dominator.
156     instruction = dominator->GetLastInstruction();
157   }
158   while (instruction != receiver) {
159     if (instruction == nullptr) {
160       // receiver must be defined in this block, we didn't find it
161       // in the instruction list, so it must be a Phi.
162       DCHECK(receiver->IsPhi());
163       break;
164     }
165     if (instruction->IsShouldDeoptimizeFlag()) {
166       RemoveGuard(flag);
167       return true;
168     }
169     instruction = instruction->GetPrevious();
170   }
171   return false;
172 }
173 
HoistGuard(HShouldDeoptimizeFlag * flag,HInstruction * receiver)174 bool CHAGuardVisitor::HoistGuard(HShouldDeoptimizeFlag* flag,
175                                  HInstruction* receiver) {
176   // If receiver is loop invariant, we can hoist the guard out of the
177   // loop since passing a guard before entering the loop guarantees that
178   // receiver conforms to all the CHA devirtualization assumptions.
179   // We only hoist guards out of the inner loop since that offers most of the
180   // benefit and it might help remove other guards in the inner loop.
181   HBasicBlock* block = flag->GetBlock();
182   HLoopInformation* loop_info = block->GetLoopInformation();
183   if (loop_info != nullptr &&
184       !loop_info->IsIrreducible() &&
185       loop_info->IsDefinedOutOfTheLoop(receiver)) {
186     HInstruction* compare = flag->GetNext();
187     DCHECK(compare->IsNotEqual());
188     HInstruction* deopt = compare->GetNext();
189     DCHECK(deopt->IsDeoptimize());
190 
191     // Advance instruction iterator first before we move the guard.
192     // We need to do it twice since we move three instructions and the
193     // visitor is responsible for advancing it once.
194     instruction_iterator_->Advance();
195     instruction_iterator_->Advance();
196 
197     HBasicBlock* pre_header = loop_info->GetPreHeader();
198     flag->MoveBefore(pre_header->GetLastInstruction());
199     compare->MoveBefore(pre_header->GetLastInstruction());
200 
201     block->RemoveInstruction(deopt);
202     HInstruction* suspend = loop_info->GetSuspendCheck();
203     // Need a new deoptimize instruction that copies the environment
204     // of the suspend instruction for the loop.
205     HDeoptimize* deoptimize = new (GetGraph()->GetAllocator()) HDeoptimize(
206         GetGraph()->GetAllocator(), compare, DeoptimizationKind::kCHA, suspend->GetDexPc());
207     pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction());
208     deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
209         suspend->GetEnvironment(), loop_info->GetHeader());
210     block_has_cha_guard_[pre_header->GetBlockId()] = 1;
211     GetGraph()->IncrementNumberOfCHAGuards();
212     return true;
213   }
214   return false;
215 }
216 
VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag * flag)217 void CHAGuardVisitor::VisitShouldDeoptimizeFlag(HShouldDeoptimizeFlag* flag) {
218   number_of_guards_to_visit_--;
219   HInstruction* receiver = flag->InputAt(0);
220   // Don't need the receiver anymore.
221   flag->RemoveInputAt(0);
222   if (receiver->IsNullCheck()) {
223     receiver = receiver->InputAt(0);
224   }
225 
226   if (OptimizeForParameter(flag, receiver)) {
227     DCHECK(!flag->IsInBlock());
228     return;
229   }
230   if (OptimizeWithDominatingGuard(flag, receiver)) {
231     DCHECK(!flag->IsInBlock());
232     return;
233   }
234   if (HoistGuard(flag, receiver)) {
235     DCHECK(flag->IsInBlock());
236     return;
237   }
238 
239   // Need to keep the CHA guard in place.
240   block_has_cha_guard_[flag->GetBlock()->GetBlockId()] = 1;
241   GetGraph()->IncrementNumberOfCHAGuards();
242 }
243 
Run()244 bool CHAGuardOptimization::Run() {
245   if (graph_->GetNumberOfCHAGuards() == 0) {
246     return false;
247   }
248   CHAGuardVisitor visitor(graph_);
249   for (HBasicBlock* block : graph_->GetReversePostOrder()) {
250     visitor.VisitBasicBlock(block);
251   }
252   return true;
253 }
254 
255 }  // namespace art
256