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