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