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 20namespace art { 21 22bool 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 32bool 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 42bool 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 52bool 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 61bool 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 */ 75bool 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 333static const char* storage_name[] = {" Frame ", "PhysReg", " Spill "}; 334 335void 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 365static 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 */ 375void 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