blob: 0b4f04100b605e02beea0b52c01535adeb0ce0f5 [file] [log] [blame]
buzbee311ca162013-02-28 15:56:43 -08001/*
2 * Copyright (C) 2011 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 "compiler_internals.h"
18#include "local_value_numbering.h"
Ian Rogers8d3a1172013-06-04 01:13:28 -070019#include "dataflow_iterator-inl.h"
buzbee311ca162013-02-28 15:56:43 -080020
21namespace art {
22
Brian Carlstrom2ce745c2013-07-17 17:44:30 -070023static unsigned int Predecessors(BasicBlock* bb) {
buzbee862a7602013-04-05 10:58:54 -070024 return bb->predecessors->Size();
buzbee311ca162013-02-28 15:56:43 -080025}
26
27/* Setup a constant value for opcodes thare have the DF_SETS_CONST attribute */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -070028void MIRGraph::SetConstant(int32_t ssa_reg, int value) {
buzbee862a7602013-04-05 10:58:54 -070029 is_constant_v_->SetBit(ssa_reg);
buzbee311ca162013-02-28 15:56:43 -080030 constant_values_[ssa_reg] = value;
31}
32
Brian Carlstrom2ce745c2013-07-17 17:44:30 -070033void MIRGraph::SetConstantWide(int ssa_reg, int64_t value) {
buzbee862a7602013-04-05 10:58:54 -070034 is_constant_v_->SetBit(ssa_reg);
buzbee311ca162013-02-28 15:56:43 -080035 constant_values_[ssa_reg] = Low32Bits(value);
36 constant_values_[ssa_reg + 1] = High32Bits(value);
37}
38
Brian Carlstrom2ce745c2013-07-17 17:44:30 -070039void MIRGraph::DoConstantPropogation(BasicBlock* bb) {
buzbee311ca162013-02-28 15:56:43 -080040 MIR* mir;
buzbee311ca162013-02-28 15:56:43 -080041
42 for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
buzbee1fd33462013-03-25 13:40:45 -070043 int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode];
buzbee311ca162013-02-28 15:56:43 -080044
45 DecodedInstruction *d_insn = &mir->dalvikInsn;
46
47 if (!(df_attributes & DF_HAS_DEFS)) continue;
48
49 /* Handle instructions that set up constants directly */
50 if (df_attributes & DF_SETS_CONST) {
51 if (df_attributes & DF_DA) {
52 int32_t vB = static_cast<int32_t>(d_insn->vB);
53 switch (d_insn->opcode) {
54 case Instruction::CONST_4:
55 case Instruction::CONST_16:
56 case Instruction::CONST:
57 SetConstant(mir->ssa_rep->defs[0], vB);
58 break;
59 case Instruction::CONST_HIGH16:
60 SetConstant(mir->ssa_rep->defs[0], vB << 16);
61 break;
62 case Instruction::CONST_WIDE_16:
63 case Instruction::CONST_WIDE_32:
64 SetConstantWide(mir->ssa_rep->defs[0], static_cast<int64_t>(vB));
65 break;
66 case Instruction::CONST_WIDE:
Brian Carlstromb1eba212013-07-17 18:07:19 -070067 SetConstantWide(mir->ssa_rep->defs[0], d_insn->vB_wide);
buzbee311ca162013-02-28 15:56:43 -080068 break;
69 case Instruction::CONST_WIDE_HIGH16:
70 SetConstantWide(mir->ssa_rep->defs[0], static_cast<int64_t>(vB) << 48);
71 break;
72 default:
73 break;
74 }
75 }
76 /* Handle instructions that set up constants directly */
77 } else if (df_attributes & DF_IS_MOVE) {
78 int i;
79
80 for (i = 0; i < mir->ssa_rep->num_uses; i++) {
buzbee862a7602013-04-05 10:58:54 -070081 if (!is_constant_v_->IsBitSet(mir->ssa_rep->uses[i])) break;
buzbee311ca162013-02-28 15:56:43 -080082 }
83 /* Move a register holding a constant to another register */
84 if (i == mir->ssa_rep->num_uses) {
85 SetConstant(mir->ssa_rep->defs[0], constant_values_[mir->ssa_rep->uses[0]]);
86 if (df_attributes & DF_A_WIDE) {
87 SetConstant(mir->ssa_rep->defs[1], constant_values_[mir->ssa_rep->uses[1]]);
88 }
89 }
90 }
91 }
92 /* TODO: implement code to handle arithmetic operations */
buzbee311ca162013-02-28 15:56:43 -080093}
94
Brian Carlstrom2ce745c2013-07-17 17:44:30 -070095void MIRGraph::PropagateConstants() {
buzbee862a7602013-04-05 10:58:54 -070096 is_constant_v_ = new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false);
Mathieu Chartierf6c4b3b2013-08-24 16:11:37 -070097 constant_values_ = static_cast<int*>(arena_->Alloc(sizeof(int) * GetNumSSARegs(),
98 ArenaAllocator::kAllocDFInfo));
buzbee56c71782013-09-05 17:13:19 -070099 AllNodesIterator iter(this);
buzbee311ca162013-02-28 15:56:43 -0800100 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
101 DoConstantPropogation(bb);
102 }
buzbee311ca162013-02-28 15:56:43 -0800103}
104
105/* Advance to next strictly dominated MIR node in an extended basic block */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700106static MIR* AdvanceMIR(BasicBlock** p_bb, MIR* mir) {
buzbee311ca162013-02-28 15:56:43 -0800107 BasicBlock* bb = *p_bb;
108 if (mir != NULL) {
109 mir = mir->next;
110 if (mir == NULL) {
111 bb = bb->fall_through;
112 if ((bb == NULL) || Predecessors(bb) != 1) {
113 mir = NULL;
114 } else {
115 *p_bb = bb;
116 mir = bb->first_mir_insn;
117 }
118 }
119 }
120 return mir;
121}
122
123/*
124 * To be used at an invoke mir. If the logically next mir node represents
125 * a move-result, return it. Else, return NULL. If a move-result exists,
126 * it is required to immediately follow the invoke with no intervening
127 * opcodes or incoming arcs. However, if the result of the invoke is not
128 * used, a move-result may not be present.
129 */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700130MIR* MIRGraph::FindMoveResult(BasicBlock* bb, MIR* mir) {
buzbee311ca162013-02-28 15:56:43 -0800131 BasicBlock* tbb = bb;
132 mir = AdvanceMIR(&tbb, mir);
133 while (mir != NULL) {
134 int opcode = mir->dalvikInsn.opcode;
135 if ((mir->dalvikInsn.opcode == Instruction::MOVE_RESULT) ||
136 (mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) ||
137 (mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_WIDE)) {
138 break;
139 }
140 // Keep going if pseudo op, otherwise terminate
141 if (opcode < kNumPackedOpcodes) {
142 mir = NULL;
143 } else {
144 mir = AdvanceMIR(&tbb, mir);
145 }
146 }
147 return mir;
148}
149
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700150static BasicBlock* NextDominatedBlock(BasicBlock* bb) {
buzbee311ca162013-02-28 15:56:43 -0800151 if (bb->block_type == kDead) {
152 return NULL;
153 }
154 DCHECK((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
155 || (bb->block_type == kExitBlock));
buzbeecbcfaf32013-08-19 07:37:40 -0700156 if (((bb->taken != NULL) && (bb->fall_through == NULL)) &&
157 ((bb->taken->block_type == kDalvikByteCode) || (bb->taken->block_type == kExitBlock))) {
158 // Follow simple unconditional branches.
159 bb = bb->taken;
160 } else {
161 // Follow simple fallthrough
162 bb = (bb->taken != NULL) ? NULL : bb->fall_through;
163 }
buzbee311ca162013-02-28 15:56:43 -0800164 if (bb == NULL || (Predecessors(bb) != 1)) {
165 return NULL;
166 }
167 DCHECK((bb->block_type == kDalvikByteCode) || (bb->block_type == kExitBlock));
168 return bb;
169}
170
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700171static MIR* FindPhi(BasicBlock* bb, int ssa_name) {
buzbee311ca162013-02-28 15:56:43 -0800172 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
173 if (static_cast<int>(mir->dalvikInsn.opcode) == kMirOpPhi) {
174 for (int i = 0; i < mir->ssa_rep->num_uses; i++) {
175 if (mir->ssa_rep->uses[i] == ssa_name) {
176 return mir;
177 }
178 }
179 }
180 }
181 return NULL;
182}
183
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700184static SelectInstructionKind SelectKind(MIR* mir) {
buzbee311ca162013-02-28 15:56:43 -0800185 switch (mir->dalvikInsn.opcode) {
186 case Instruction::MOVE:
187 case Instruction::MOVE_OBJECT:
188 case Instruction::MOVE_16:
189 case Instruction::MOVE_OBJECT_16:
190 case Instruction::MOVE_FROM16:
191 case Instruction::MOVE_OBJECT_FROM16:
192 return kSelectMove;
Brian Carlstrom6f485c62013-07-18 15:35:35 -0700193 case Instruction::CONST:
194 case Instruction::CONST_4:
195 case Instruction::CONST_16:
buzbee311ca162013-02-28 15:56:43 -0800196 return kSelectConst;
Brian Carlstrom6f485c62013-07-18 15:35:35 -0700197 case Instruction::GOTO:
198 case Instruction::GOTO_16:
199 case Instruction::GOTO_32:
buzbee311ca162013-02-28 15:56:43 -0800200 return kSelectGoto;
Brian Carlstrom02c8cc62013-07-18 15:54:44 -0700201 default:
202 return kSelectNone;
buzbee311ca162013-02-28 15:56:43 -0800203 }
buzbee311ca162013-02-28 15:56:43 -0800204}
205
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700206int MIRGraph::GetSSAUseCount(int s_reg) {
buzbee862a7602013-04-05 10:58:54 -0700207 return raw_use_counts_.Get(s_reg);
buzbee311ca162013-02-28 15:56:43 -0800208}
209
210
211/* Do some MIR-level extended basic block optimizations */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700212bool MIRGraph::BasicBlockOpt(BasicBlock* bb) {
buzbee311ca162013-02-28 15:56:43 -0800213 if (bb->block_type == kDead) {
214 return true;
215 }
216 int num_temps = 0;
217 LocalValueNumbering local_valnum(cu_);
218 while (bb != NULL) {
219 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
220 // TUNING: use the returned value number for CSE.
221 local_valnum.GetValueNumber(mir);
222 // Look for interesting opcodes, skip otherwise
223 Instruction::Code opcode = mir->dalvikInsn.opcode;
224 switch (opcode) {
225 case Instruction::CMPL_FLOAT:
226 case Instruction::CMPL_DOUBLE:
227 case Instruction::CMPG_FLOAT:
228 case Instruction::CMPG_DOUBLE:
229 case Instruction::CMP_LONG:
buzbee1fd33462013-03-25 13:40:45 -0700230 if ((cu_->disable_opt & (1 << kBranchFusing)) != 0) {
buzbee311ca162013-02-28 15:56:43 -0800231 // Bitcode doesn't allow this optimization.
232 break;
233 }
234 if (mir->next != NULL) {
235 MIR* mir_next = mir->next;
236 Instruction::Code br_opcode = mir_next->dalvikInsn.opcode;
237 ConditionCode ccode = kCondNv;
Brian Carlstromdf629502013-07-17 22:39:56 -0700238 switch (br_opcode) {
buzbee311ca162013-02-28 15:56:43 -0800239 case Instruction::IF_EQZ:
240 ccode = kCondEq;
241 break;
242 case Instruction::IF_NEZ:
243 ccode = kCondNe;
244 break;
245 case Instruction::IF_LTZ:
246 ccode = kCondLt;
247 break;
248 case Instruction::IF_GEZ:
249 ccode = kCondGe;
250 break;
251 case Instruction::IF_GTZ:
252 ccode = kCondGt;
253 break;
254 case Instruction::IF_LEZ:
255 ccode = kCondLe;
256 break;
257 default:
258 break;
259 }
260 // Make sure result of cmp is used by next insn and nowhere else
261 if ((ccode != kCondNv) &&
262 (mir->ssa_rep->defs[0] == mir_next->ssa_rep->uses[0]) &&
263 (GetSSAUseCount(mir->ssa_rep->defs[0]) == 1)) {
264 mir_next->dalvikInsn.arg[0] = ccode;
Brian Carlstromdf629502013-07-17 22:39:56 -0700265 switch (opcode) {
buzbee311ca162013-02-28 15:56:43 -0800266 case Instruction::CMPL_FLOAT:
267 mir_next->dalvikInsn.opcode =
268 static_cast<Instruction::Code>(kMirOpFusedCmplFloat);
269 break;
270 case Instruction::CMPL_DOUBLE:
271 mir_next->dalvikInsn.opcode =
272 static_cast<Instruction::Code>(kMirOpFusedCmplDouble);
273 break;
274 case Instruction::CMPG_FLOAT:
275 mir_next->dalvikInsn.opcode =
276 static_cast<Instruction::Code>(kMirOpFusedCmpgFloat);
277 break;
278 case Instruction::CMPG_DOUBLE:
279 mir_next->dalvikInsn.opcode =
280 static_cast<Instruction::Code>(kMirOpFusedCmpgDouble);
281 break;
282 case Instruction::CMP_LONG:
283 mir_next->dalvikInsn.opcode =
284 static_cast<Instruction::Code>(kMirOpFusedCmpLong);
285 break;
286 default: LOG(ERROR) << "Unexpected opcode: " << opcode;
287 }
288 mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
289 mir_next->ssa_rep->num_uses = mir->ssa_rep->num_uses;
290 mir_next->ssa_rep->uses = mir->ssa_rep->uses;
291 mir_next->ssa_rep->fp_use = mir->ssa_rep->fp_use;
292 mir_next->ssa_rep->num_defs = 0;
293 mir->ssa_rep->num_uses = 0;
294 mir->ssa_rep->num_defs = 0;
295 }
296 }
297 break;
298 case Instruction::GOTO:
299 case Instruction::GOTO_16:
300 case Instruction::GOTO_32:
301 case Instruction::IF_EQ:
302 case Instruction::IF_NE:
303 case Instruction::IF_LT:
304 case Instruction::IF_GE:
305 case Instruction::IF_GT:
306 case Instruction::IF_LE:
307 case Instruction::IF_EQZ:
308 case Instruction::IF_NEZ:
309 case Instruction::IF_LTZ:
310 case Instruction::IF_GEZ:
311 case Instruction::IF_GTZ:
312 case Instruction::IF_LEZ:
buzbeecbcfaf32013-08-19 07:37:40 -0700313 // If we've got a backwards branch to return, no need to suspend check.
buzbee9329e6d2013-08-19 12:55:10 -0700314 if ((IsBackedge(bb, bb->taken) && bb->taken->dominates_return) ||
315 (IsBackedge(bb, bb->fall_through) && bb->fall_through->dominates_return)) {
buzbee311ca162013-02-28 15:56:43 -0800316 mir->optimization_flags |= MIR_IGNORE_SUSPEND_CHECK;
317 if (cu_->verbose) {
318 LOG(INFO) << "Suppressed suspend check on branch to return at 0x" << std::hex << mir->offset;
319 }
320 }
321 break;
322 default:
323 break;
324 }
325 // Is this the select pattern?
326 // TODO: flesh out support for Mips and X86. NOTE: llvm's select op doesn't quite work here.
327 // TUNING: expand to support IF_xx compare & branches
Ian Rogers41cdd432013-10-11 08:44:13 -0700328 if (false &&
329 !(cu_->compiler_backend == kPortable) && (cu_->instruction_set == kThumb2) &&
buzbee311ca162013-02-28 15:56:43 -0800330 ((mir->dalvikInsn.opcode == Instruction::IF_EQZ) ||
331 (mir->dalvikInsn.opcode == Instruction::IF_NEZ))) {
332 BasicBlock* ft = bb->fall_through;
333 DCHECK(ft != NULL);
334 BasicBlock* ft_ft = ft->fall_through;
335 BasicBlock* ft_tk = ft->taken;
336
337 BasicBlock* tk = bb->taken;
338 DCHECK(tk != NULL);
339 BasicBlock* tk_ft = tk->fall_through;
340 BasicBlock* tk_tk = tk->taken;
341
342 /*
343 * In the select pattern, the taken edge goes to a block that unconditionally
344 * transfers to the rejoin block and the fall_though edge goes to a block that
345 * unconditionally falls through to the rejoin block.
346 */
347 if ((tk_ft == NULL) && (ft_tk == NULL) && (tk_tk == ft_ft) &&
348 (Predecessors(tk) == 1) && (Predecessors(ft) == 1)) {
349 /*
350 * Okay - we have the basic diamond shape. At the very least, we can eliminate the
351 * suspend check on the taken-taken branch back to the join point.
352 */
353 if (SelectKind(tk->last_mir_insn) == kSelectGoto) {
354 tk->last_mir_insn->optimization_flags |= (MIR_IGNORE_SUSPEND_CHECK);
355 }
356 // Are the block bodies something we can handle?
357 if ((ft->first_mir_insn == ft->last_mir_insn) &&
358 (tk->first_mir_insn != tk->last_mir_insn) &&
359 (tk->first_mir_insn->next == tk->last_mir_insn) &&
360 ((SelectKind(ft->first_mir_insn) == kSelectMove) ||
361 (SelectKind(ft->first_mir_insn) == kSelectConst)) &&
362 (SelectKind(ft->first_mir_insn) == SelectKind(tk->first_mir_insn)) &&
363 (SelectKind(tk->last_mir_insn) == kSelectGoto)) {
364 // Almost there. Are the instructions targeting the same vreg?
365 MIR* if_true = tk->first_mir_insn;
366 MIR* if_false = ft->first_mir_insn;
367 // It's possible that the target of the select isn't used - skip those (rare) cases.
368 MIR* phi = FindPhi(tk_tk, if_true->ssa_rep->defs[0]);
369 if ((phi != NULL) && (if_true->dalvikInsn.vA == if_false->dalvikInsn.vA)) {
370 /*
371 * We'll convert the IF_EQZ/IF_NEZ to a SELECT. We need to find the
372 * Phi node in the merge block and delete it (while using the SSA name
373 * of the merge as the target of the SELECT. Delete both taken and
374 * fallthrough blocks, and set fallthrough to merge block.
375 * NOTE: not updating other dataflow info (no longer used at this point).
376 * If this changes, need to update i_dom, etc. here (and in CombineBlocks).
377 */
378 if (opcode == Instruction::IF_NEZ) {
379 // Normalize.
380 MIR* tmp_mir = if_true;
381 if_true = if_false;
382 if_false = tmp_mir;
383 }
384 mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpSelect);
385 bool const_form = (SelectKind(if_true) == kSelectConst);
386 if ((SelectKind(if_true) == kSelectMove)) {
387 if (IsConst(if_true->ssa_rep->uses[0]) &&
388 IsConst(if_false->ssa_rep->uses[0])) {
389 const_form = true;
390 if_true->dalvikInsn.vB = ConstantValue(if_true->ssa_rep->uses[0]);
391 if_false->dalvikInsn.vB = ConstantValue(if_false->ssa_rep->uses[0]);
392 }
393 }
394 if (const_form) {
395 // "true" set val in vB
396 mir->dalvikInsn.vB = if_true->dalvikInsn.vB;
397 // "false" set val in vC
398 mir->dalvikInsn.vC = if_false->dalvikInsn.vB;
399 } else {
400 DCHECK_EQ(SelectKind(if_true), kSelectMove);
401 DCHECK_EQ(SelectKind(if_false), kSelectMove);
buzbee862a7602013-04-05 10:58:54 -0700402 int* src_ssa =
Mathieu Chartierf6c4b3b2013-08-24 16:11:37 -0700403 static_cast<int*>(arena_->Alloc(sizeof(int) * 3, ArenaAllocator::kAllocDFInfo));
buzbee311ca162013-02-28 15:56:43 -0800404 src_ssa[0] = mir->ssa_rep->uses[0];
405 src_ssa[1] = if_true->ssa_rep->uses[0];
406 src_ssa[2] = if_false->ssa_rep->uses[0];
407 mir->ssa_rep->uses = src_ssa;
408 mir->ssa_rep->num_uses = 3;
409 }
410 mir->ssa_rep->num_defs = 1;
buzbee862a7602013-04-05 10:58:54 -0700411 mir->ssa_rep->defs =
Mathieu Chartierf6c4b3b2013-08-24 16:11:37 -0700412 static_cast<int*>(arena_->Alloc(sizeof(int) * 1, ArenaAllocator::kAllocDFInfo));
buzbee862a7602013-04-05 10:58:54 -0700413 mir->ssa_rep->fp_def =
Mathieu Chartierf6c4b3b2013-08-24 16:11:37 -0700414 static_cast<bool*>(arena_->Alloc(sizeof(bool) * 1, ArenaAllocator::kAllocDFInfo));
buzbee311ca162013-02-28 15:56:43 -0800415 mir->ssa_rep->fp_def[0] = if_true->ssa_rep->fp_def[0];
buzbee817e45a2013-05-30 18:59:12 -0700416 // Match type of uses to def.
417 mir->ssa_rep->fp_use =
Mathieu Chartierf6c4b3b2013-08-24 16:11:37 -0700418 static_cast<bool*>(arena_->Alloc(sizeof(bool) * mir->ssa_rep->num_uses,
419 ArenaAllocator::kAllocDFInfo));
buzbee817e45a2013-05-30 18:59:12 -0700420 for (int i = 0; i < mir->ssa_rep->num_uses; i++) {
421 mir->ssa_rep->fp_use[i] = mir->ssa_rep->fp_def[0];
422 }
buzbee311ca162013-02-28 15:56:43 -0800423 /*
424 * There is usually a Phi node in the join block for our two cases. If the
425 * Phi node only contains our two cases as input, we will use the result
426 * SSA name of the Phi node as our select result and delete the Phi. If
427 * the Phi node has more than two operands, we will arbitrarily use the SSA
428 * name of the "true" path, delete the SSA name of the "false" path from the
429 * Phi node (and fix up the incoming arc list).
430 */
431 if (phi->ssa_rep->num_uses == 2) {
432 mir->ssa_rep->defs[0] = phi->ssa_rep->defs[0];
433 phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
434 } else {
435 int dead_def = if_false->ssa_rep->defs[0];
436 int live_def = if_true->ssa_rep->defs[0];
437 mir->ssa_rep->defs[0] = live_def;
438 int* incoming = reinterpret_cast<int*>(phi->dalvikInsn.vB);
439 for (int i = 0; i < phi->ssa_rep->num_uses; i++) {
440 if (phi->ssa_rep->uses[i] == live_def) {
441 incoming[i] = bb->id;
442 }
443 }
444 for (int i = 0; i < phi->ssa_rep->num_uses; i++) {
445 if (phi->ssa_rep->uses[i] == dead_def) {
446 int last_slot = phi->ssa_rep->num_uses - 1;
447 phi->ssa_rep->uses[i] = phi->ssa_rep->uses[last_slot];
448 incoming[i] = incoming[last_slot];
449 }
450 }
451 }
452 phi->ssa_rep->num_uses--;
453 bb->taken = NULL;
454 tk->block_type = kDead;
455 for (MIR* tmir = ft->first_mir_insn; tmir != NULL; tmir = tmir->next) {
456 tmir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
457 }
458 }
459 }
460 }
461 }
462 }
463 bb = NextDominatedBlock(bb);
464 }
465
466 if (num_temps > cu_->num_compiler_temps) {
467 cu_->num_compiler_temps = num_temps;
468 }
469 return true;
470}
471
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700472void MIRGraph::NullCheckEliminationInit(struct BasicBlock* bb) {
buzbee862a7602013-04-05 10:58:54 -0700473 if (bb->data_flow_info != NULL) {
474 bb->data_flow_info->ending_null_check_v =
475 new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false, kBitMapNullCheck);
476 }
buzbee311ca162013-02-28 15:56:43 -0800477}
478
479/* Collect stats on number of checks removed */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700480void MIRGraph::CountChecks(struct BasicBlock* bb) {
buzbee862a7602013-04-05 10:58:54 -0700481 if (bb->data_flow_info != NULL) {
482 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
483 if (mir->ssa_rep == NULL) {
484 continue;
buzbee311ca162013-02-28 15:56:43 -0800485 }
buzbee862a7602013-04-05 10:58:54 -0700486 int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode];
487 if (df_attributes & DF_HAS_NULL_CHKS) {
488 checkstats_->null_checks++;
489 if (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) {
490 checkstats_->null_checks_eliminated++;
491 }
492 }
493 if (df_attributes & DF_HAS_RANGE_CHKS) {
494 checkstats_->range_checks++;
495 if (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) {
496 checkstats_->range_checks_eliminated++;
497 }
buzbee311ca162013-02-28 15:56:43 -0800498 }
499 }
500 }
buzbee311ca162013-02-28 15:56:43 -0800501}
502
503/* Try to make common case the fallthrough path */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700504static bool LayoutBlocks(struct BasicBlock* bb) {
buzbee311ca162013-02-28 15:56:43 -0800505 // TODO: For now, just looking for direct throws. Consider generalizing for profile feedback
506 if (!bb->explicit_throw) {
507 return false;
508 }
509 BasicBlock* walker = bb;
510 while (true) {
511 // Check termination conditions
512 if ((walker->block_type == kEntryBlock) || (Predecessors(walker) != 1)) {
513 break;
514 }
buzbee862a7602013-04-05 10:58:54 -0700515 BasicBlock* prev = walker->predecessors->Get(0);
buzbee311ca162013-02-28 15:56:43 -0800516 if (prev->conditional_branch) {
517 if (prev->fall_through == walker) {
518 // Already done - return
519 break;
520 }
521 DCHECK_EQ(walker, prev->taken);
522 // Got one. Flip it and exit
523 Instruction::Code opcode = prev->last_mir_insn->dalvikInsn.opcode;
524 switch (opcode) {
525 case Instruction::IF_EQ: opcode = Instruction::IF_NE; break;
526 case Instruction::IF_NE: opcode = Instruction::IF_EQ; break;
527 case Instruction::IF_LT: opcode = Instruction::IF_GE; break;
528 case Instruction::IF_GE: opcode = Instruction::IF_LT; break;
529 case Instruction::IF_GT: opcode = Instruction::IF_LE; break;
530 case Instruction::IF_LE: opcode = Instruction::IF_GT; break;
531 case Instruction::IF_EQZ: opcode = Instruction::IF_NEZ; break;
532 case Instruction::IF_NEZ: opcode = Instruction::IF_EQZ; break;
533 case Instruction::IF_LTZ: opcode = Instruction::IF_GEZ; break;
534 case Instruction::IF_GEZ: opcode = Instruction::IF_LTZ; break;
535 case Instruction::IF_GTZ: opcode = Instruction::IF_LEZ; break;
536 case Instruction::IF_LEZ: opcode = Instruction::IF_GTZ; break;
537 default: LOG(FATAL) << "Unexpected opcode " << opcode;
538 }
539 prev->last_mir_insn->dalvikInsn.opcode = opcode;
540 BasicBlock* t_bb = prev->taken;
541 prev->taken = prev->fall_through;
542 prev->fall_through = t_bb;
543 break;
544 }
545 walker = prev;
546 }
547 return false;
548}
549
550/* Combine any basic blocks terminated by instructions that we now know can't throw */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700551bool MIRGraph::CombineBlocks(struct BasicBlock* bb) {
buzbee311ca162013-02-28 15:56:43 -0800552 // Loop here to allow combining a sequence of blocks
553 while (true) {
554 // Check termination conditions
555 if ((bb->first_mir_insn == NULL)
556 || (bb->data_flow_info == NULL)
557 || (bb->block_type == kExceptionHandling)
558 || (bb->block_type == kExitBlock)
559 || (bb->block_type == kDead)
560 || ((bb->taken == NULL) || (bb->taken->block_type != kExceptionHandling))
561 || (bb->successor_block_list.block_list_type != kNotUsed)
562 || (static_cast<int>(bb->last_mir_insn->dalvikInsn.opcode) != kMirOpCheck)) {
563 break;
564 }
565
566 // Test the kMirOpCheck instruction
567 MIR* mir = bb->last_mir_insn;
568 // Grab the attributes from the paired opcode
569 MIR* throw_insn = mir->meta.throw_insn;
buzbee1fd33462013-03-25 13:40:45 -0700570 int df_attributes = oat_data_flow_attributes_[throw_insn->dalvikInsn.opcode];
buzbee311ca162013-02-28 15:56:43 -0800571 bool can_combine = true;
572 if (df_attributes & DF_HAS_NULL_CHKS) {
573 can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0);
574 }
575 if (df_attributes & DF_HAS_RANGE_CHKS) {
576 can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0);
577 }
578 if (!can_combine) {
579 break;
580 }
581 // OK - got one. Combine
582 BasicBlock* bb_next = bb->fall_through;
583 DCHECK(!bb_next->catch_entry);
584 DCHECK_EQ(Predecessors(bb_next), 1U);
585 MIR* t_mir = bb->last_mir_insn->prev;
586 // Overwrite the kOpCheck insn with the paired opcode
587 DCHECK_EQ(bb_next->first_mir_insn, throw_insn);
588 *bb->last_mir_insn = *throw_insn;
589 bb->last_mir_insn->prev = t_mir;
590 // Use the successor info from the next block
591 bb->successor_block_list = bb_next->successor_block_list;
592 // Use the ending block linkage from the next block
593 bb->fall_through = bb_next->fall_through;
594 bb->taken->block_type = kDead; // Kill the unused exception block
595 bb->taken = bb_next->taken;
596 // Include the rest of the instructions
597 bb->last_mir_insn = bb_next->last_mir_insn;
598 /*
599 * If lower-half of pair of blocks to combine contained a return, move the flag
600 * to the newly combined block.
601 */
602 bb->terminated_by_return = bb_next->terminated_by_return;
603
604 /*
605 * NOTE: we aren't updating all dataflow info here. Should either make sure this pass
606 * happens after uses of i_dominated, dom_frontier or update the dataflow info here.
607 */
608
609 // Kill bb_next and remap now-dead id to parent
610 bb_next->block_type = kDead;
buzbee1fd33462013-03-25 13:40:45 -0700611 block_id_map_.Overwrite(bb_next->id, bb->id);
buzbee311ca162013-02-28 15:56:43 -0800612
613 // Now, loop back and see if we can keep going
614 }
615 return false;
616}
617
618/* Eliminate unnecessary null checks for a basic block. */
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700619bool MIRGraph::EliminateNullChecks(struct BasicBlock* bb) {
buzbee311ca162013-02-28 15:56:43 -0800620 if (bb->data_flow_info == NULL) return false;
621
622 /*
623 * Set initial state. Be conservative with catch
624 * blocks and start with no assumptions about null check
625 * status (except for "this").
626 */
627 if ((bb->block_type == kEntryBlock) | bb->catch_entry) {
buzbee862a7602013-04-05 10:58:54 -0700628 temp_ssa_register_v_->ClearAllBits();
buzbee311ca162013-02-28 15:56:43 -0800629 if ((cu_->access_flags & kAccStatic) == 0) {
630 // If non-static method, mark "this" as non-null
631 int this_reg = cu_->num_dalvik_registers - cu_->num_ins;
buzbee862a7602013-04-05 10:58:54 -0700632 temp_ssa_register_v_->SetBit(this_reg);
buzbee311ca162013-02-28 15:56:43 -0800633 }
Ian Rogers22fd6a02013-06-13 15:06:54 -0700634 } else if (bb->predecessors->Size() == 1) {
635 BasicBlock* pred_bb = bb->predecessors->Get(0);
636 temp_ssa_register_v_->Copy(pred_bb->data_flow_info->ending_null_check_v);
637 if (pred_bb->block_type == kDalvikByteCode) {
638 // Check to see if predecessor had an explicit null-check.
639 MIR* last_insn = pred_bb->last_mir_insn;
640 Instruction::Code last_opcode = last_insn->dalvikInsn.opcode;
641 if (last_opcode == Instruction::IF_EQZ) {
642 if (pred_bb->fall_through == bb) {
643 // The fall-through of a block following a IF_EQZ, set the vA of the IF_EQZ to show that
644 // it can't be null.
645 temp_ssa_register_v_->SetBit(last_insn->ssa_rep->uses[0]);
646 }
647 } else if (last_opcode == Instruction::IF_NEZ) {
648 if (pred_bb->taken == bb) {
649 // The taken block following a IF_NEZ, set the vA of the IF_NEZ to show that it can't be
650 // null.
651 temp_ssa_register_v_->SetBit(last_insn->ssa_rep->uses[0]);
652 }
653 }
654 }
buzbee311ca162013-02-28 15:56:43 -0800655 } else {
Ian Rogers22fd6a02013-06-13 15:06:54 -0700656 // Starting state is intersection of all incoming arcs
buzbee862a7602013-04-05 10:58:54 -0700657 GrowableArray<BasicBlock*>::Iterator iter(bb->predecessors);
658 BasicBlock* pred_bb = iter.Next();
buzbee311ca162013-02-28 15:56:43 -0800659 DCHECK(pred_bb != NULL);
buzbee862a7602013-04-05 10:58:54 -0700660 temp_ssa_register_v_->Copy(pred_bb->data_flow_info->ending_null_check_v);
buzbee311ca162013-02-28 15:56:43 -0800661 while (true) {
buzbee862a7602013-04-05 10:58:54 -0700662 pred_bb = iter.Next();
buzbee311ca162013-02-28 15:56:43 -0800663 if (!pred_bb) break;
664 if ((pred_bb->data_flow_info == NULL) ||
665 (pred_bb->data_flow_info->ending_null_check_v == NULL)) {
666 continue;
667 }
buzbee862a7602013-04-05 10:58:54 -0700668 temp_ssa_register_v_->Intersect(pred_bb->data_flow_info->ending_null_check_v);
buzbee311ca162013-02-28 15:56:43 -0800669 }
670 }
671
672 // Walk through the instruction in the block, updating as necessary
673 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
674 if (mir->ssa_rep == NULL) {
675 continue;
676 }
buzbee1fd33462013-03-25 13:40:45 -0700677 int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode];
buzbee311ca162013-02-28 15:56:43 -0800678
679 // Mark target of NEW* as non-null
680 if (df_attributes & DF_NON_NULL_DST) {
buzbee862a7602013-04-05 10:58:54 -0700681 temp_ssa_register_v_->SetBit(mir->ssa_rep->defs[0]);
buzbee311ca162013-02-28 15:56:43 -0800682 }
683
684 // Mark non-null returns from invoke-style NEW*
685 if (df_attributes & DF_NON_NULL_RET) {
686 MIR* next_mir = mir->next;
687 // Next should be an MOVE_RESULT_OBJECT
688 if (next_mir &&
689 next_mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
690 // Mark as null checked
buzbee862a7602013-04-05 10:58:54 -0700691 temp_ssa_register_v_->SetBit(next_mir->ssa_rep->defs[0]);
buzbee311ca162013-02-28 15:56:43 -0800692 } else {
693 if (next_mir) {
694 LOG(WARNING) << "Unexpected opcode following new: " << next_mir->dalvikInsn.opcode;
695 } else if (bb->fall_through) {
696 // Look in next basic block
697 struct BasicBlock* next_bb = bb->fall_through;
698 for (MIR* tmir = next_bb->first_mir_insn; tmir != NULL;
699 tmir =tmir->next) {
700 if (static_cast<int>(tmir->dalvikInsn.opcode) >= static_cast<int>(kMirOpFirst)) {
701 continue;
702 }
703 // First non-pseudo should be MOVE_RESULT_OBJECT
704 if (tmir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
705 // Mark as null checked
buzbee862a7602013-04-05 10:58:54 -0700706 temp_ssa_register_v_->SetBit(tmir->ssa_rep->defs[0]);
buzbee311ca162013-02-28 15:56:43 -0800707 } else {
708 LOG(WARNING) << "Unexpected op after new: " << tmir->dalvikInsn.opcode;
709 }
710 break;
711 }
712 }
713 }
714 }
715
716 /*
717 * Propagate nullcheck state on register copies (including
718 * Phi pseudo copies. For the latter, nullcheck state is
719 * the "and" of all the Phi's operands.
720 */
721 if (df_attributes & (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N)) {
722 int tgt_sreg = mir->ssa_rep->defs[0];
723 int operands = (df_attributes & DF_NULL_TRANSFER_0) ? 1 :
724 mir->ssa_rep->num_uses;
725 bool null_checked = true;
726 for (int i = 0; i < operands; i++) {
buzbee862a7602013-04-05 10:58:54 -0700727 null_checked &= temp_ssa_register_v_->IsBitSet(mir->ssa_rep->uses[i]);
buzbee311ca162013-02-28 15:56:43 -0800728 }
729 if (null_checked) {
buzbee862a7602013-04-05 10:58:54 -0700730 temp_ssa_register_v_->SetBit(tgt_sreg);
buzbee311ca162013-02-28 15:56:43 -0800731 }
732 }
733
734 // Already nullchecked?
735 if ((df_attributes & DF_HAS_NULL_CHKS) && !(mir->optimization_flags & MIR_IGNORE_NULL_CHECK)) {
736 int src_idx;
737 if (df_attributes & DF_NULL_CHK_1) {
738 src_idx = 1;
739 } else if (df_attributes & DF_NULL_CHK_2) {
740 src_idx = 2;
741 } else {
742 src_idx = 0;
743 }
744 int src_sreg = mir->ssa_rep->uses[src_idx];
buzbee862a7602013-04-05 10:58:54 -0700745 if (temp_ssa_register_v_->IsBitSet(src_sreg)) {
buzbee311ca162013-02-28 15:56:43 -0800746 // Eliminate the null check
747 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
748 } else {
749 // Mark s_reg as null-checked
buzbee862a7602013-04-05 10:58:54 -0700750 temp_ssa_register_v_->SetBit(src_sreg);
buzbee311ca162013-02-28 15:56:43 -0800751 }
752 }
753 }
754
755 // Did anything change?
buzbee862a7602013-04-05 10:58:54 -0700756 bool changed = !temp_ssa_register_v_->Equal(bb->data_flow_info->ending_null_check_v);
757 if (changed) {
758 bb->data_flow_info->ending_null_check_v->Copy(temp_ssa_register_v_);
buzbee311ca162013-02-28 15:56:43 -0800759 }
buzbee862a7602013-04-05 10:58:54 -0700760 return changed;
buzbee311ca162013-02-28 15:56:43 -0800761}
762
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700763void MIRGraph::NullCheckElimination() {
buzbee311ca162013-02-28 15:56:43 -0800764 if (!(cu_->disable_opt & (1 << kNullCheckElimination))) {
765 DCHECK(temp_ssa_register_v_ != NULL);
buzbee56c71782013-09-05 17:13:19 -0700766 AllNodesIterator iter(this);
buzbee311ca162013-02-28 15:56:43 -0800767 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
768 NullCheckEliminationInit(bb);
769 }
buzbee56c71782013-09-05 17:13:19 -0700770 RepeatingPreOrderDfsIterator iter2(this);
buzbee311ca162013-02-28 15:56:43 -0800771 bool change = false;
772 for (BasicBlock* bb = iter2.Next(change); bb != NULL; bb = iter2.Next(change)) {
773 change = EliminateNullChecks(bb);
774 }
775 }
776 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
777 DumpCFG("/sdcard/4_post_nce_cfg/", false);
778 }
779}
780
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700781void MIRGraph::BasicBlockCombine() {
buzbee56c71782013-09-05 17:13:19 -0700782 PreOrderDfsIterator iter(this);
buzbee311ca162013-02-28 15:56:43 -0800783 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
784 CombineBlocks(bb);
785 }
786 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
787 DumpCFG("/sdcard/5_post_bbcombine_cfg/", false);
788 }
789}
790
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700791void MIRGraph::CodeLayout() {
buzbee1fd33462013-03-25 13:40:45 -0700792 if (cu_->enable_debug & (1 << kDebugVerifyDataflow)) {
793 VerifyDataflow();
794 }
buzbee56c71782013-09-05 17:13:19 -0700795 AllNodesIterator iter(this);
buzbee311ca162013-02-28 15:56:43 -0800796 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
797 LayoutBlocks(bb);
798 }
799 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
800 DumpCFG("/sdcard/2_post_layout_cfg/", true);
801 }
802}
803
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700804void MIRGraph::DumpCheckStats() {
buzbee311ca162013-02-28 15:56:43 -0800805 Checkstats* stats =
Mathieu Chartierf6c4b3b2013-08-24 16:11:37 -0700806 static_cast<Checkstats*>(arena_->Alloc(sizeof(Checkstats), ArenaAllocator::kAllocDFInfo));
buzbee1fd33462013-03-25 13:40:45 -0700807 checkstats_ = stats;
buzbee56c71782013-09-05 17:13:19 -0700808 AllNodesIterator iter(this);
buzbee311ca162013-02-28 15:56:43 -0800809 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
810 CountChecks(bb);
811 }
812 if (stats->null_checks > 0) {
813 float eliminated = static_cast<float>(stats->null_checks_eliminated);
814 float checks = static_cast<float>(stats->null_checks);
815 LOG(INFO) << "Null Checks: " << PrettyMethod(cu_->method_idx, *cu_->dex_file) << " "
816 << stats->null_checks_eliminated << " of " << stats->null_checks << " -> "
817 << (eliminated/checks) * 100.0 << "%";
818 }
819 if (stats->range_checks > 0) {
820 float eliminated = static_cast<float>(stats->range_checks_eliminated);
821 float checks = static_cast<float>(stats->range_checks);
822 LOG(INFO) << "Range Checks: " << PrettyMethod(cu_->method_idx, *cu_->dex_file) << " "
823 << stats->range_checks_eliminated << " of " << stats->range_checks << " -> "
824 << (eliminated/checks) * 100.0 << "%";
825 }
826}
827
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700828bool MIRGraph::BuildExtendedBBList(struct BasicBlock* bb) {
buzbee311ca162013-02-28 15:56:43 -0800829 if (bb->visited) return false;
830 if (!((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
831 || (bb->block_type == kExitBlock))) {
832 // Ignore special blocks
833 bb->visited = true;
834 return false;
835 }
836 // Must be head of extended basic block.
837 BasicBlock* start_bb = bb;
838 extended_basic_blocks_.push_back(bb);
839 bool terminated_by_return = false;
840 // Visit blocks strictly dominated by this head.
841 while (bb != NULL) {
842 bb->visited = true;
843 terminated_by_return |= bb->terminated_by_return;
844 bb = NextDominatedBlock(bb);
845 }
846 if (terminated_by_return) {
847 // This extended basic block contains a return, so mark all members.
848 bb = start_bb;
849 while (bb != NULL) {
850 bb->dominates_return = true;
851 bb = NextDominatedBlock(bb);
852 }
853 }
Brian Carlstrom7934ac22013-07-26 10:54:15 -0700854 return false; // Not iterative - return value will be ignored
buzbee311ca162013-02-28 15:56:43 -0800855}
856
857
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700858void MIRGraph::BasicBlockOptimization() {
buzbee311ca162013-02-28 15:56:43 -0800859 if (!(cu_->disable_opt & (1 << kBBOpt))) {
buzbee311ca162013-02-28 15:56:43 -0800860 DCHECK_EQ(cu_->num_compiler_temps, 0);
buzbeea5abf702013-04-12 14:39:29 -0700861 ClearAllVisitedFlags();
buzbee56c71782013-09-05 17:13:19 -0700862 PreOrderDfsIterator iter2(this);
buzbee311ca162013-02-28 15:56:43 -0800863 for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) {
864 BuildExtendedBBList(bb);
865 }
866 // Perform extended basic block optimizations.
867 for (unsigned int i = 0; i < extended_basic_blocks_.size(); i++) {
868 BasicBlockOpt(extended_basic_blocks_[i]);
869 }
870 }
871 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
872 DumpCFG("/sdcard/6_post_bbo_cfg/", false);
873 }
874}
875
876} // namespace art