1 /*
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 "dex/dataflow_iterator-inl.h"
19
20 namespace art {
21
SetFp(int index,bool is_fp)22 bool MIRGraph::SetFp(int index, bool is_fp) {
23 bool change = false;
24 if (is_fp && !reg_location_[index].fp) {
25 reg_location_[index].fp = true;
26 reg_location_[index].defined = true;
27 change = true;
28 }
29 return change;
30 }
31
SetCore(int index,bool is_core)32 bool MIRGraph::SetCore(int index, bool is_core) {
33 bool change = false;
34 if (is_core && !reg_location_[index].defined) {
35 reg_location_[index].core = true;
36 reg_location_[index].defined = true;
37 change = true;
38 }
39 return change;
40 }
41
SetRef(int index,bool is_ref)42 bool MIRGraph::SetRef(int index, bool is_ref) {
43 bool change = false;
44 if (is_ref && !reg_location_[index].defined) {
45 reg_location_[index].ref = true;
46 reg_location_[index].defined = true;
47 change = true;
48 }
49 return change;
50 }
51
SetWide(int index,bool is_wide)52 bool MIRGraph::SetWide(int index, bool is_wide) {
53 bool change = false;
54 if (is_wide && !reg_location_[index].wide) {
55 reg_location_[index].wide = true;
56 change = true;
57 }
58 return change;
59 }
60
SetHigh(int index,bool is_high)61 bool MIRGraph::SetHigh(int index, bool is_high) {
62 bool change = false;
63 if (is_high && !reg_location_[index].high_word) {
64 reg_location_[index].high_word = true;
65 change = true;
66 }
67 return change;
68 }
69
70 /*
71 * Infer types and sizes. We don't need to track change on sizes,
72 * as it doesn't propagate. We're guaranteed at least one pass through
73 * the cfg.
74 */
InferTypeAndSize(BasicBlock * bb)75 bool MIRGraph::InferTypeAndSize(BasicBlock* bb) {
76 MIR *mir;
77 bool changed = false; // Did anything change?
78
79 if (bb->data_flow_info == NULL) return false;
80 if (bb->block_type != kDalvikByteCode && bb->block_type != kEntryBlock)
81 return false;
82
83 for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
84 SSARepresentation *ssa_rep = mir->ssa_rep;
85 if (ssa_rep) {
86 int attrs = oat_data_flow_attributes_[mir->dalvikInsn.opcode];
87
88 // Handle defs
89 if (attrs & DF_DA) {
90 if (attrs & DF_CORE_A) {
91 changed |= SetCore(ssa_rep->defs[0], true);
92 }
93 if (attrs & DF_REF_A) {
94 changed |= SetRef(ssa_rep->defs[0], true);
95 }
96 if (attrs & DF_A_WIDE) {
97 reg_location_[ssa_rep->defs[0]].wide = true;
98 reg_location_[ssa_rep->defs[1]].wide = true;
99 reg_location_[ssa_rep->defs[1]].high_word = true;
100 DCHECK_EQ(SRegToVReg(ssa_rep->defs[0])+1,
101 SRegToVReg(ssa_rep->defs[1]));
102 }
103 }
104
105 // Handles uses
106 int next = 0;
107 if (attrs & DF_UA) {
108 if (attrs & DF_CORE_A) {
109 changed |= SetCore(ssa_rep->uses[next], true);
110 }
111 if (attrs & DF_REF_A) {
112 changed |= SetRef(ssa_rep->uses[next], true);
113 }
114 if (attrs & DF_A_WIDE) {
115 reg_location_[ssa_rep->uses[next]].wide = true;
116 reg_location_[ssa_rep->uses[next + 1]].wide = true;
117 reg_location_[ssa_rep->uses[next + 1]].high_word = true;
118 DCHECK_EQ(SRegToVReg(ssa_rep->uses[next])+1,
119 SRegToVReg(ssa_rep->uses[next + 1]));
120 next += 2;
121 } else {
122 next++;
123 }
124 }
125 if (attrs & DF_UB) {
126 if (attrs & DF_CORE_B) {
127 changed |= SetCore(ssa_rep->uses[next], true);
128 }
129 if (attrs & DF_REF_B) {
130 changed |= SetRef(ssa_rep->uses[next], true);
131 }
132 if (attrs & DF_B_WIDE) {
133 reg_location_[ssa_rep->uses[next]].wide = true;
134 reg_location_[ssa_rep->uses[next + 1]].wide = true;
135 reg_location_[ssa_rep->uses[next + 1]].high_word = true;
136 DCHECK_EQ(SRegToVReg(ssa_rep->uses[next])+1,
137 SRegToVReg(ssa_rep->uses[next + 1]));
138 next += 2;
139 } else {
140 next++;
141 }
142 }
143 if (attrs & DF_UC) {
144 if (attrs & DF_CORE_C) {
145 changed |= SetCore(ssa_rep->uses[next], true);
146 }
147 if (attrs & DF_REF_C) {
148 changed |= SetRef(ssa_rep->uses[next], true);
149 }
150 if (attrs & DF_C_WIDE) {
151 reg_location_[ssa_rep->uses[next]].wide = true;
152 reg_location_[ssa_rep->uses[next + 1]].wide = true;
153 reg_location_[ssa_rep->uses[next + 1]].high_word = true;
154 DCHECK_EQ(SRegToVReg(ssa_rep->uses[next])+1,
155 SRegToVReg(ssa_rep->uses[next + 1]));
156 }
157 }
158
159 // Special-case return handling
160 if ((mir->dalvikInsn.opcode == Instruction::RETURN) ||
161 (mir->dalvikInsn.opcode == Instruction::RETURN_WIDE) ||
162 (mir->dalvikInsn.opcode == Instruction::RETURN_OBJECT)) {
163 switch (cu_->shorty[0]) {
164 case 'I':
165 changed |= SetCore(ssa_rep->uses[0], true);
166 break;
167 case 'J':
168 changed |= SetCore(ssa_rep->uses[0], true);
169 changed |= SetCore(ssa_rep->uses[1], true);
170 reg_location_[ssa_rep->uses[0]].wide = true;
171 reg_location_[ssa_rep->uses[1]].wide = true;
172 reg_location_[ssa_rep->uses[1]].high_word = true;
173 break;
174 case 'F':
175 changed |= SetFp(ssa_rep->uses[0], true);
176 break;
177 case 'D':
178 changed |= SetFp(ssa_rep->uses[0], true);
179 changed |= SetFp(ssa_rep->uses[1], true);
180 reg_location_[ssa_rep->uses[0]].wide = true;
181 reg_location_[ssa_rep->uses[1]].wide = true;
182 reg_location_[ssa_rep->uses[1]].high_word = true;
183 break;
184 case 'L':
185 changed |= SetRef(ssa_rep->uses[0], true);
186 break;
187 default: break;
188 }
189 }
190
191 // Special-case handling for format 35c/3rc invokes
192 Instruction::Code opcode = mir->dalvikInsn.opcode;
193 int flags = (static_cast<int>(opcode) >= kNumPackedOpcodes)
194 ? 0 : Instruction::FlagsOf(mir->dalvikInsn.opcode);
195 if ((flags & Instruction::kInvoke) &&
196 (attrs & (DF_FORMAT_35C | DF_FORMAT_3RC))) {
197 DCHECK_EQ(next, 0);
198 int target_idx = mir->dalvikInsn.vB;
199 const char* shorty = GetShortyFromTargetIdx(target_idx);
200 // Handle result type if floating point
201 if ((shorty[0] == 'F') || (shorty[0] == 'D')) {
202 MIR* move_result_mir = FindMoveResult(bb, mir);
203 // Result might not be used at all, so no move-result
204 if (move_result_mir && (move_result_mir->dalvikInsn.opcode !=
205 Instruction::MOVE_RESULT_OBJECT)) {
206 SSARepresentation* tgt_rep = move_result_mir->ssa_rep;
207 DCHECK(tgt_rep != NULL);
208 tgt_rep->fp_def[0] = true;
209 changed |= SetFp(tgt_rep->defs[0], true);
210 if (shorty[0] == 'D') {
211 tgt_rep->fp_def[1] = true;
212 changed |= SetFp(tgt_rep->defs[1], true);
213 }
214 }
215 }
216 int num_uses = mir->dalvikInsn.vA;
217 // If this is a non-static invoke, mark implicit "this"
218 if (((mir->dalvikInsn.opcode != Instruction::INVOKE_STATIC) &&
219 (mir->dalvikInsn.opcode != Instruction::INVOKE_STATIC_RANGE))) {
220 reg_location_[ssa_rep->uses[next]].defined = true;
221 reg_location_[ssa_rep->uses[next]].ref = true;
222 next++;
223 }
224 uint32_t cpos = 1;
225 if (strlen(shorty) > 1) {
226 for (int i = next; i < num_uses;) {
227 DCHECK_LT(cpos, strlen(shorty));
228 switch (shorty[cpos++]) {
229 case 'D':
230 ssa_rep->fp_use[i] = true;
231 ssa_rep->fp_use[i+1] = true;
232 reg_location_[ssa_rep->uses[i]].wide = true;
233 reg_location_[ssa_rep->uses[i+1]].wide = true;
234 reg_location_[ssa_rep->uses[i+1]].high_word = true;
235 DCHECK_EQ(SRegToVReg(ssa_rep->uses[i])+1, SRegToVReg(ssa_rep->uses[i+1]));
236 i++;
237 break;
238 case 'J':
239 reg_location_[ssa_rep->uses[i]].wide = true;
240 reg_location_[ssa_rep->uses[i+1]].wide = true;
241 reg_location_[ssa_rep->uses[i+1]].high_word = true;
242 DCHECK_EQ(SRegToVReg(ssa_rep->uses[i])+1, SRegToVReg(ssa_rep->uses[i+1]));
243 changed |= SetCore(ssa_rep->uses[i], true);
244 i++;
245 break;
246 case 'F':
247 ssa_rep->fp_use[i] = true;
248 break;
249 case 'L':
250 changed |= SetRef(ssa_rep->uses[i], true);
251 break;
252 default:
253 changed |= SetCore(ssa_rep->uses[i], true);
254 break;
255 }
256 i++;
257 }
258 }
259 }
260
261 for (int i = 0; ssa_rep->fp_use && i< ssa_rep->num_uses; i++) {
262 if (ssa_rep->fp_use[i])
263 changed |= SetFp(ssa_rep->uses[i], true);
264 }
265 for (int i = 0; ssa_rep->fp_def && i< ssa_rep->num_defs; i++) {
266 if (ssa_rep->fp_def[i])
267 changed |= SetFp(ssa_rep->defs[i], true);
268 }
269 // Special-case handling for moves & Phi
270 if (attrs & (DF_IS_MOVE | DF_NULL_TRANSFER_N)) {
271 /*
272 * If any of our inputs or outputs is defined, set all.
273 * Some ugliness related to Phi nodes and wide values.
274 * The Phi set will include all low words or all high
275 * words, so we have to treat them specially.
276 */
277 bool is_phi = (static_cast<int>(mir->dalvikInsn.opcode) ==
278 kMirOpPhi);
279 RegLocation rl_temp = reg_location_[ssa_rep->defs[0]];
280 bool defined_fp = rl_temp.defined && rl_temp.fp;
281 bool defined_core = rl_temp.defined && rl_temp.core;
282 bool defined_ref = rl_temp.defined && rl_temp.ref;
283 bool is_wide = rl_temp.wide || ((attrs & DF_A_WIDE) != 0);
284 bool is_high = is_phi && rl_temp.wide && rl_temp.high_word;
285 for (int i = 0; i < ssa_rep->num_uses; i++) {
286 rl_temp = reg_location_[ssa_rep->uses[i]];
287 defined_fp |= rl_temp.defined && rl_temp.fp;
288 defined_core |= rl_temp.defined && rl_temp.core;
289 defined_ref |= rl_temp.defined && rl_temp.ref;
290 is_wide |= rl_temp.wide;
291 is_high |= is_phi && rl_temp.wide && rl_temp.high_word;
292 }
293 /*
294 * We don't normally expect to see a Dalvik register definition used both as a
295 * floating point and core value, though technically it could happen with constants.
296 * Until we have proper typing, detect this situation and disable register promotion
297 * (which relies on the distinction between core a fp usages).
298 */
299 if ((defined_fp && (defined_core | defined_ref)) &&
300 ((cu_->disable_opt & (1 << kPromoteRegs)) == 0)) {
301 LOG(WARNING) << PrettyMethod(cu_->method_idx, *cu_->dex_file)
302 << " op at block " << bb->id
303 << " has both fp and core/ref uses for same def.";
304 cu_->disable_opt |= (1 << kPromoteRegs);
305 }
306 changed |= SetFp(ssa_rep->defs[0], defined_fp);
307 changed |= SetCore(ssa_rep->defs[0], defined_core);
308 changed |= SetRef(ssa_rep->defs[0], defined_ref);
309 changed |= SetWide(ssa_rep->defs[0], is_wide);
310 changed |= SetHigh(ssa_rep->defs[0], is_high);
311 if (attrs & DF_A_WIDE) {
312 changed |= SetWide(ssa_rep->defs[1], true);
313 changed |= SetHigh(ssa_rep->defs[1], true);
314 }
315 for (int i = 0; i < ssa_rep->num_uses; i++) {
316 changed |= SetFp(ssa_rep->uses[i], defined_fp);
317 changed |= SetCore(ssa_rep->uses[i], defined_core);
318 changed |= SetRef(ssa_rep->uses[i], defined_ref);
319 changed |= SetWide(ssa_rep->uses[i], is_wide);
320 changed |= SetHigh(ssa_rep->uses[i], is_high);
321 }
322 if (attrs & DF_A_WIDE) {
323 DCHECK_EQ(ssa_rep->num_uses, 2);
324 changed |= SetWide(ssa_rep->uses[1], true);
325 changed |= SetHigh(ssa_rep->uses[1], true);
326 }
327 }
328 }
329 }
330 return changed;
331 }
332
333 static const char* storage_name[] = {" Frame ", "PhysReg", " Spill "};
334
DumpRegLocTable(RegLocation * table,int count)335 void MIRGraph::DumpRegLocTable(RegLocation* table, int count) {
336 // FIXME: Quick-specific. Move to Quick (and make a generic version for MIRGraph?
337 Mir2Lir* cg = static_cast<Mir2Lir*>(cu_->cg.get());
338 if (cg != NULL) {
339 for (int i = 0; i < count; i++) {
340 LOG(INFO) << StringPrintf("Loc[%02d] : %s, %c %c %c %c %c %c %c%d %c%d S%d",
341 table[i].orig_sreg, storage_name[table[i].location],
342 table[i].wide ? 'W' : 'N', table[i].defined ? 'D' : 'U',
343 table[i].fp ? 'F' : table[i].ref ? 'R' :'C',
344 table[i].is_const ? 'c' : 'n',
345 table[i].high_word ? 'H' : 'L', table[i].home ? 'h' : 't',
346 cg->IsFpReg(table[i].low_reg) ? 's' : 'r',
347 table[i].low_reg & cg->FpRegMask(),
348 cg->IsFpReg(table[i].high_reg) ? 's' : 'r',
349 table[i].high_reg & cg->FpRegMask(), table[i].s_reg_low);
350 }
351 } else {
352 // Either pre-regalloc or Portable.
353 for (int i = 0; i < count; i++) {
354 LOG(INFO) << StringPrintf("Loc[%02d] : %s, %c %c %c %c %c %c S%d",
355 table[i].orig_sreg, storage_name[table[i].location],
356 table[i].wide ? 'W' : 'N', table[i].defined ? 'D' : 'U',
357 table[i].fp ? 'F' : table[i].ref ? 'R' :'C',
358 table[i].is_const ? 'c' : 'n',
359 table[i].high_word ? 'H' : 'L', table[i].home ? 'h' : 't',
360 table[i].s_reg_low);
361 }
362 }
363 }
364
365 static const RegLocation fresh_loc = {kLocDalvikFrame, 0, 0, 0, 0, 0, 0, 0, 0,
366 INVALID_REG, INVALID_REG, INVALID_SREG,
367 INVALID_SREG};
368
369 /*
370 * Simple register allocation. Some Dalvik virtual registers may
371 * be promoted to physical registers. Most of the work for temp
372 * allocation is done on the fly. We also do some initialization and
373 * type inference here.
374 */
BuildRegLocations()375 void MIRGraph::BuildRegLocations() {
376 /* Allocate the location map */
377 RegLocation* loc = static_cast<RegLocation*>(arena_->Alloc(GetNumSSARegs() * sizeof(*loc),
378 ArenaAllocator::kAllocRegAlloc));
379 for (int i = 0; i < GetNumSSARegs(); i++) {
380 loc[i] = fresh_loc;
381 loc[i].s_reg_low = i;
382 loc[i].is_const = is_constant_v_->IsBitSet(i);
383 }
384
385 /* Patch up the locations for Method* and the compiler temps */
386 loc[method_sreg_].location = kLocCompilerTemp;
387 loc[method_sreg_].defined = true;
388 for (int i = 0; i < cu_->num_compiler_temps; i++) {
389 CompilerTemp* ct = compiler_temps_.Get(i);
390 loc[ct->s_reg].location = kLocCompilerTemp;
391 loc[ct->s_reg].defined = true;
392 }
393
394 reg_location_ = loc;
395
396 int num_regs = cu_->num_dalvik_registers;
397
398 /* Add types of incoming arguments based on signature */
399 int num_ins = cu_->num_ins;
400 if (num_ins > 0) {
401 int s_reg = num_regs - num_ins;
402 if ((cu_->access_flags & kAccStatic) == 0) {
403 // For non-static, skip past "this"
404 reg_location_[s_reg].defined = true;
405 reg_location_[s_reg].ref = true;
406 s_reg++;
407 }
408 const char* shorty = cu_->shorty;
409 int shorty_len = strlen(shorty);
410 for (int i = 1; i < shorty_len; i++) {
411 switch (shorty[i]) {
412 case 'D':
413 reg_location_[s_reg].wide = true;
414 reg_location_[s_reg+1].high_word = true;
415 reg_location_[s_reg+1].fp = true;
416 DCHECK_EQ(SRegToVReg(s_reg)+1, SRegToVReg(s_reg+1));
417 reg_location_[s_reg].fp = true;
418 reg_location_[s_reg].defined = true;
419 s_reg++;
420 break;
421 case 'J':
422 reg_location_[s_reg].wide = true;
423 reg_location_[s_reg+1].high_word = true;
424 DCHECK_EQ(SRegToVReg(s_reg)+1, SRegToVReg(s_reg+1));
425 reg_location_[s_reg].core = true;
426 reg_location_[s_reg].defined = true;
427 s_reg++;
428 break;
429 case 'F':
430 reg_location_[s_reg].fp = true;
431 reg_location_[s_reg].defined = true;
432 break;
433 case 'L':
434 reg_location_[s_reg].ref = true;
435 reg_location_[s_reg].defined = true;
436 break;
437 default:
438 reg_location_[s_reg].core = true;
439 reg_location_[s_reg].defined = true;
440 break;
441 }
442 s_reg++;
443 }
444 }
445
446 /* Do type & size inference pass */
447 PreOrderDfsIterator iter(this, true /* iterative */);
448 bool change = false;
449 for (BasicBlock* bb = iter.Next(false); bb != NULL; bb = iter.Next(change)) {
450 change = InferTypeAndSize(bb);
451 }
452
453 /*
454 * Set the s_reg_low field to refer to the pre-SSA name of the
455 * base Dalvik virtual register. Once we add a better register
456 * allocator, remove this remapping.
457 */
458 for (int i = 0; i < GetNumSSARegs(); i++) {
459 if (reg_location_[i].location != kLocCompilerTemp) {
460 int orig_sreg = reg_location_[i].s_reg_low;
461 reg_location_[i].orig_sreg = orig_sreg;
462 reg_location_[i].s_reg_low = SRegToVReg(orig_sreg);
463 }
464 }
465 }
466
467 } // namespace art
468