FirstFitLocalCombiningAllocator.java revision f6c387128427e121477c1b32ad35cdcaa5101ba3
1/* 2 * Copyright (C) 2007 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 17package com.android.dx.ssa.back; 18 19import com.android.dx.rop.code.*; 20import com.android.dx.rop.cst.CstInteger; 21import com.android.dx.ssa.InterferenceRegisterMapper; 22import com.android.dx.ssa.RegisterMapper; 23import com.android.dx.ssa.SsaInsn; 24import com.android.dx.ssa.SsaMethod; 25import com.android.dx.ssa.NormalSsaInsn; 26import com.android.dx.ssa.PhiInsn; 27import com.android.dx.ssa.Optimizer; 28import com.android.dx.ssa.SsaBasicBlock; 29import com.android.dx.util.IntSet; 30import com.android.dx.util.IntIterator; 31 32import java.util.ArrayList; 33import java.util.BitSet; 34import java.util.Map; 35import java.util.TreeMap; 36 37/** 38 * Allocates registers in a first-fit fashion, with the bottom reserved for 39 * method parameters and all SSAregisters representing the same local variable 40 * kept together if possible. 41 */ 42public class FirstFitLocalCombiningAllocator extends RegisterAllocator { 43 private static final boolean DEBUG = false; 44 45 /** maps local variable to a list of associated SSA registers*/ 46 private final Map<LocalItem, ArrayList<RegisterSpec>> localVariables; 47 48 /** list of move-result-pesudo instructions seen in this method */ 49 private final ArrayList<NormalSsaInsn> moveResultPseudoInsns; 50 51 /** list of invoke-range instructions seen in this method */ 52 private final ArrayList<NormalSsaInsn> invokeRangeInsns; 53 54 /** indexed by SSA reg; the set of SSA regs we've mapped */ 55 private final BitSet ssaRegsMapped; 56 57 /** Register mapper which will be our result */ 58 private final InterferenceRegisterMapper mapper; 59 60 /** end of rop registers range (starting at 0) reserved for parameters. */ 61 private final int paramRangeEnd; 62 63 /** set of Rop registers reserved for parameters or local variables. */ 64 private final BitSet reservedRopRegs; 65 66 /** set of Rop registers that have been used by anything.*/ 67 private final BitSet usedRopRegs; 68 69 /** true if converter should take steps to minimize rop-form registers*/ 70 private final boolean minimizeRegisters; 71 72 73 /** 74 * Constructs instance. 75 * 76 * @param ssaMeth non-null; method to process 77 * @param interference non-null interference graph for SSA registers 78 * @param minimizeRegisters true if converter should take steps to 79 * minimize rop-form registers 80 */ 81 public FirstFitLocalCombiningAllocator( 82 final SsaMethod ssaMeth, InterferenceGraph interference, 83 boolean minimizeRegisters) { 84 super(ssaMeth, interference); 85 86 ssaRegsMapped = new BitSet(ssaMeth.getRegCount()); 87 88 mapper = new InterferenceRegisterMapper( 89 interference, ssaMeth.getRegCount()); 90 91 this.minimizeRegisters = minimizeRegisters; 92 93 /* 94 * Reserve space for the params at the bottom of the register 95 * space. Later, we'll flip the params to the end of the register 96 * space. 97 */ 98 99 paramRangeEnd = ssaMeth.getParamWidth(); 100 101 reservedRopRegs = new BitSet(paramRangeEnd * 2); 102 reservedRopRegs.set(0, paramRangeEnd); 103 usedRopRegs = new BitSet(paramRangeEnd * 2); 104 localVariables = new TreeMap<LocalItem, ArrayList<RegisterSpec>>(); 105 moveResultPseudoInsns = new ArrayList<NormalSsaInsn>(); 106 invokeRangeInsns = new ArrayList<NormalSsaInsn>(); 107 } 108 109 /** {@inheritDoc} */ 110 @Override 111 public boolean wantsParamsMovedHigh() { 112 return true; 113 } 114 115 /** {@inheritDoc} */ 116 @Override 117 public RegisterMapper allocateRegisters() { 118 119 analyzeInstructions(); 120 121 if (DEBUG) { 122 printLocalVars(); 123 } 124 125 if(DEBUG) System.out.println("--->Mapping local-associated params"); 126 handleLocalAssociatedParams(); 127 128 if(DEBUG) System.out.println("--->Mapping other params"); 129 handleUnassociatedParameters(); 130 131 if(DEBUG) System.out.println("--->Mapping invoke-range"); 132 handleInvokeRangeInsns(); 133 134 if(DEBUG) System.out.println("--->Mapping local-associated non-params"); 135 handleLocalAssociatedOther(); 136 137 if(DEBUG) System.out.println("--->Mapping check-cast results"); 138 handleCheckCastResults(); 139 140 if(DEBUG) System.out.println("--->Mapping others"); 141 handleNormalUnassociated(); 142 143 return mapper; 144 } 145 146 /** 147 * Dumps local variable table to stdout for debugging. 148 */ 149 private void printLocalVars() { 150 System.out.println("Printing local vars"); 151 for (Map.Entry<LocalItem, ArrayList<RegisterSpec>> e: 152 localVariables.entrySet()) { 153 StringBuilder regs = new StringBuilder(); 154 155 regs.append('{'); 156 regs.append(' '); 157 for(RegisterSpec reg: e.getValue()) { 158 regs.append('v'); 159 regs.append(reg.getReg()); 160 regs.append(' '); 161 } 162 regs.append('}'); 163 System.out.printf("Local: %s Registers: %s\n", e.getKey(), regs); 164 } 165 } 166 167 /** 168 * Maps all local-associated parameters to Rop registers. 169 */ 170 private void handleLocalAssociatedParams() { 171 for (ArrayList<RegisterSpec> ssaRegs: localVariables.values()) { 172 int sz = ssaRegs.size(); 173 int paramIndex = -1; 174 int paramCategory = 0; 175 176 // First, find out if this local variable is a parameter 177 for (int i = 0 ; i < sz ; i++) { 178 RegisterSpec ssaSpec = ssaRegs.get(i); 179 int ssaReg = ssaSpec.getReg(); 180 181 paramIndex = getParameterIndexForReg(ssaReg); 182 183 if (paramIndex >= 0) { 184 paramCategory = ssaSpec.getCategory(); 185 addMapping(ssaSpec, paramIndex); 186 break; 187 } 188 } 189 190 if (paramIndex < 0) { 191 // this local wasn't a parameter 192 continue; 193 } 194 195 // Any remaining local-associated registers will be mapped later 196 tryMapRegs(ssaRegs, paramIndex, paramCategory, true); 197 } 198 } 199 200 /** 201 * Gets the parameter index for SSA registers that are method parameters. 202 * -1 is returned for non-parameter registers. 203 * 204 * @param ssaReg >=0 SSA register to look up 205 * @return parameter index or -1 if not a parameter 206 */ 207 private int getParameterIndexForReg(int ssaReg) { 208 SsaInsn defInsn = ssaMeth.getDefinitionForRegister(ssaReg); 209 if (defInsn == null) { 210 return -1; 211 } 212 213 Rop opcode = defInsn.getOpcode(); 214 215 // opcode == null for phi insns 216 if (opcode != null && opcode.getOpcode() == RegOps.MOVE_PARAM) { 217 CstInsn origInsn = (CstInsn) defInsn.getOriginalRopInsn(); 218 return ((CstInteger) origInsn.getConstant()).getValue(); 219 } 220 221 return -1; 222 } 223 224 /** 225 * Maps all local-associated registers that are not parameters. Tries to 226 * find an unreserved range that's wide enough for all of the SSA registers, 227 * and then tries to map them all to that range. If not all fit, 228 * a new range is tried until all registers have been fit. 229 */ 230 private void handleLocalAssociatedOther() { 231 for (ArrayList<RegisterSpec> specs: localVariables.values()) { 232 int ropReg = 0; 233 234 boolean done; 235 do { 236 int maxCategory = 1; 237 238 // compute max category for remaining unmapped registers 239 int sz = specs.size(); 240 for (int i = 0; i < sz; i++) { 241 RegisterSpec ssaSpec = specs.get(i); 242 int category = ssaSpec.getCategory(); 243 if (!ssaRegsMapped.get(ssaSpec.getReg()) 244 && category > maxCategory) { 245 maxCategory = category; 246 } 247 } 248 249 ropReg = findRopRegForLocal(ropReg, maxCategory); 250 251 done = tryMapRegs(specs, ropReg, maxCategory, true); 252 253 // Increment for next call to findNext 254 ropReg++; 255 } while (!done); 256 } 257 } 258 259 /** 260 * Tries to map a list of SSA registers into the a rop reg, marking 261 * used rop space as reserved. SSA registers that don't fit are left 262 * unmapped. 263 * 264 * @param specs non-null; SSA registers to attempt to map 265 * @param ropReg >=0 rop register to map to 266 * @param maxAllowedCategory 1 or 2, maximum category allowed in mapping. 267 * @param markReserved do so if true 268 * @return true if all registers wew mapped, false if some remain unmapped. 269 */ 270 private boolean tryMapRegs( 271 ArrayList<RegisterSpec> specs, int ropReg, 272 int maxAllowedCategory, boolean markReserved) { 273 boolean remaining = false; 274 for(RegisterSpec spec: specs) { 275 if (ssaRegsMapped.get(spec.getReg())) { 276 continue; 277 } 278 279 boolean succeeded; 280 succeeded = tryMapReg(spec, ropReg, maxAllowedCategory); 281 remaining = !succeeded || remaining; 282 if (succeeded && markReserved) { 283 // This only needs to be called once really with 284 // the widest category used, but <shrug> 285 markReserved(ropReg, spec.getCategory()); 286 } 287 } 288 return !remaining; 289 } 290 291 /** 292 * Tries to map an SSA register to a rop register. 293 * 294 * @param ssaSpec non-null; SSA register 295 * @param ropReg >=0 rop register 296 * @param maxAllowedCategory 1 or 2, the maximum category that the SSA 297 * register is allowed to be. 298 * @return true if map succeeded, false if not. 299 */ 300 private boolean tryMapReg(RegisterSpec ssaSpec, int ropReg, 301 int maxAllowedCategory) { 302 if (ssaSpec.getCategory() <= maxAllowedCategory 303 && !ssaRegsMapped.get(ssaSpec.getReg()) 304 && canMapReg(ssaSpec, ropReg)) { 305 addMapping(ssaSpec, ropReg); 306 return true; 307 } 308 309 return false; 310 } 311 312 /** 313 * Marks a range of Rop registers as "reserved for a local variable" 314 * 315 * @param ropReg >= 0 rop register to reserve 316 * @param category > 0 width to reserve 317 */ 318 private void markReserved(int ropReg, int category) { 319 reservedRopRegs.set(ropReg, ropReg + category, true); 320 } 321 322 /** 323 * Checks to see if any Rop registers in the specified range are reserved 324 * for local variables or parameters 325 * 326 * @param ropRangeStart >= 0 lowest Rop register 327 * @param width > 0 number of Rop registers in range. 328 * @return true if any register in range is marked reserved 329 */ 330 private boolean rangeContainsReserved(int ropRangeStart, int width) { 331 for (int i = ropRangeStart; i < (ropRangeStart + width); i++) { 332 if (reservedRopRegs.get(i)) { 333 return true; 334 } 335 } 336 return false; 337 } 338 339 /** 340 * Returns true if given rop register represents the "this" pointer 341 * for a non-static method 342 * 343 * @param startReg rop register 344 * @return true if the "this" pointer is located here. 345 */ 346 private boolean isThisPointerReg(int startReg) { 347 // "this" is always the first parameter 348 return startReg == 0 && !ssaMeth.isStatic(); 349 } 350 351 /** 352 * Finds a range of unreserved Rop registers. 353 * 354 * @param startReg >= 0; a Rop register to start the search at 355 * @param width > 0; the width, in registers, required. 356 * @return >= 0; start of available register range. 357 */ 358 private int findNextUnreservedRopReg(int startReg, int width) { 359 if (minimizeRegisters && !isThisPointerReg(startReg)) { 360 return startReg; 361 } 362 363 int reg; 364 365 reg = reservedRopRegs.nextClearBit(startReg); 366 367 while (true) { 368 int i = 1; 369 370 while (i < width && !reservedRopRegs.get(reg + i)) { 371 i++; 372 } 373 374 if (i == width) { 375 return reg; 376 } 377 378 reg = reservedRopRegs.nextClearBit(reg + i); 379 } 380 } 381 382 /** 383 * Finds a range of rop regs that can be used for local variables. 384 * If <code>MIX_LOCALS_AND_OTHER</code> is false, this means any 385 * rop register that has not yet been used. 386 * 387 * @param startReg >= 0; a Rop register to start the search at 388 * @param width > 0; the width, in registers, required. 389 * @return >= 0; start of available register range. 390 */ 391 private int findRopRegForLocal(int startReg, int width) { 392 if (minimizeRegisters && !isThisPointerReg(startReg)) { 393 return startReg; 394 } 395 396 int reg; 397 398 reg = usedRopRegs.nextClearBit(startReg); 399 400 while (true) { 401 int i = 1; 402 403 while (i < width && !usedRopRegs.get(reg + i)) { 404 i++; 405 } 406 407 if (i == width) { 408 return reg; 409 } 410 411 reg = usedRopRegs.nextClearBit(reg + i); 412 } 413 } 414 415 /** 416 * Maps any parameter that isn't local-associated, which can happen 417 * in the case where there is no java debug info. 418 */ 419 private void handleUnassociatedParameters() { 420 int szSsaRegs = ssaMeth.getRegCount(); 421 for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) { 422 if (ssaRegsMapped.get(ssaReg)) { 423 // We already did this one above 424 continue; 425 } 426 427 int paramIndex = getParameterIndexForReg(ssaReg); 428 429 RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg); 430 if (paramIndex >= 0) { 431 addMapping(ssaSpec, paramIndex); 432 } 433 } 434 } 435 436 /** 437 * Handles all insns that want a register range for their sources. 438 */ 439 private void handleInvokeRangeInsns() { 440 for(NormalSsaInsn insn: invokeRangeInsns) { 441 adjustAndMapSourceRangeRange(insn); 442 } 443 } 444 445 /** 446 * Handles check cast results to reuse the same source register if possible 447 */ 448 private void handleCheckCastResults() { 449 for (NormalSsaInsn insn : moveResultPseudoInsns) { 450 RegisterSpec moveRegSpec = insn.getResult(); 451 int moveReg = moveRegSpec.getReg(); 452 BitSet predBlocks = insn.getBlock().getPredecessors(); 453 454 // Expect one predecessor block only 455 if (predBlocks.cardinality() != 1) { 456 continue; 457 } 458 459 SsaBasicBlock predBlock = 460 ssaMeth.getBlocks().get(predBlocks.nextSetBit(0)); 461 ArrayList<SsaInsn> insnList = predBlock.getInsns(); 462 463 /** 464 * If the predecessor block has a check-cast, it will be the last 465 * instruction 466 */ 467 SsaInsn checkCastInsn = insnList.get(insnList.size() - 1); 468 if (checkCastInsn.getOpcode().getOpcode() != RegOps.CHECK_CAST) { 469 continue; 470 } 471 472 RegisterSpec checkRegSpec = checkCastInsn.getSources().get(0); 473 int checkReg = checkRegSpec.getReg(); 474 475 // Assume none of the register is mapped yet 476 int ropReg = 0; 477 478 /** 479 * See if either register is already mapped. Most likely the move 480 * result will be mapped already since the cast result is stored 481 * in a local variable. 482 */ 483 if (ssaRegsMapped.get(moveReg)) { 484 ropReg = mapper.oldToNew(moveReg); 485 } else if (ssaRegsMapped.get(checkReg)) { 486 ropReg = mapper.oldToNew(checkReg); 487 } 488 489 ArrayList<RegisterSpec> ssaRegs = new ArrayList<RegisterSpec>(2); 490 ssaRegs.add(moveRegSpec); 491 ssaRegs.add(checkRegSpec); 492 int category = checkRegSpec.getCategory(); 493 494 while (!tryMapRegs(ssaRegs, ropReg, category, false)) { 495 ropReg = findNextUnreservedRopReg(ropReg + 1, category); 496 } 497 } 498 } 499 500 /** 501 * Maps all non-parameter, non-local variable 502 * registers. 503 */ 504 private void handleNormalUnassociated() { 505 int szSsaRegs = ssaMeth.getRegCount(); 506 for (int ssaReg = 0; ssaReg < szSsaRegs; ssaReg++) { 507 if (ssaRegsMapped.get(ssaReg)) { 508 // We already did this one 509 continue; 510 } 511 512 RegisterSpec ssaSpec = getDefinitionSpecForSsaReg(ssaReg); 513 514 if (ssaSpec == null) continue; 515 516 int category = ssaSpec.getCategory(); 517 // Find a rop reg that does not interfere 518 int ropReg = findNextUnreservedRopReg(0, category); 519 while (!canMapReg(ssaSpec, ropReg)) { 520 ropReg = findNextUnreservedRopReg(ropReg + 1, category); 521 } 522 523 addMapping(ssaSpec, ropReg); 524 } 525 } 526 527 /** 528 * Checks to see if <code>ssaSpec</code> can be mapped to 529 * <code>ropReg</code>. Checks interference graph and ensures 530 * the range does not cross the parameter range. 531 * 532 * @param ssaSpec non-null; SSA spec 533 * @param ropReg prosepctive new-namespace reg 534 * @return true if mapping is possible 535 */ 536 private boolean canMapReg(RegisterSpec ssaSpec, int ropReg) { 537 int category = ssaSpec.getCategory(); 538 return !(spansParamRange(ropReg, category) 539 || mapper.interferes(ssaSpec, ropReg)); 540 } 541 542 /** 543 * Returns true if the specified Rop register + category 544 * will cross the boundry between the lower <code>paramWidth</code> 545 * registers reserved for method params and the upper registers. We cannot 546 * allocate a register that spans the param block and the normal block, 547 * because we will be moving the param block to high registers later. 548 * 549 * @param ssaReg register in new namespace 550 * @param category width that the register will have 551 * @return true in the case noted above. 552 */ 553 private boolean spansParamRange(int ssaReg, int category) { 554 return ((ssaReg < paramRangeEnd) 555 && ((ssaReg + category) > paramRangeEnd)); 556 } 557 558 /** 559 * Analyze each instruction and find out all the local variable assignments 560 * and move-result-pseudo/invoke-range instrucitons. 561 */ 562 private void analyzeInstructions() { 563 ssaMeth.forEachInsn(new SsaInsn.Visitor() { 564 565 /** {@inheritDoc} */ 566 public void visitMoveInsn(NormalSsaInsn insn) { 567 processInsn(insn); 568 } 569 570 /** {@inheritDoc} */ 571 public void visitPhiInsn(PhiInsn insn) { 572 processInsn(insn); 573 } 574 575 /** {@inheritDoc} */ 576 public void visitNonMoveInsn(NormalSsaInsn insn) { 577 processInsn(insn); 578 } 579 580 /** 581 * This method collects three types of instructions: 582 * 1) Adds a local variable assignment to the 583 * <code>localVariables</code> map. 584 * 2) Add move-result-pseudo to the 585 * <code>moveResultPseudoInsns</code> list. 586 * 3) Add invoke-range to the 587 * <code>invokeRangeInsns</code> list. 588 * 589 * @param insn non-null; insn that may represent a local variable 590 * assignment. 591 */ 592 private void processInsn(SsaInsn insn) { 593 RegisterSpec assignment; 594 assignment = insn.getLocalAssignment(); 595 596 if (assignment != null) { 597 LocalItem local = assignment.getLocalItem(); 598 599 ArrayList<RegisterSpec> regList = localVariables.get(local); 600 601 if (regList == null) { 602 regList = new ArrayList<RegisterSpec>(); 603 localVariables.put(local, regList); 604 } 605 606 regList.add(assignment); 607 } 608 609 if (insn instanceof NormalSsaInsn) { 610 if (insn.getOpcode().getOpcode() == 611 RegOps.MOVE_RESULT_PSEUDO) { 612 moveResultPseudoInsns.add((NormalSsaInsn) insn); 613 } else if (Optimizer.getAdvice().requiresSourcesInOrder( 614 insn.getOriginalRopInsn().getOpcode(), 615 insn.getSources())) { 616 invokeRangeInsns.add((NormalSsaInsn) insn); 617 } 618 } 619 620 } 621 }); 622 } 623 624 /** 625 * Adds a mapping from an SSA register to a Rop register. <code> 626 * canMapReg</code> should have already been called. 627 * 628 * @param ssaSpec non-null; SSA register to map from 629 * @param ropReg >=0; Rop register to map to 630 */ 631 private void addMapping(RegisterSpec ssaSpec, int ropReg) { 632 int ssaReg = ssaSpec.getReg(); 633 634 // An assertion 635 if (ssaRegsMapped.get(ssaReg) || !canMapReg(ssaSpec, ropReg)) { 636 throw new RuntimeException( 637 "attempt to add invalid register mapping"); 638 } 639 640 if (DEBUG) { 641 System.out.printf("Add mapping s%d -> v%d c:%d\n", 642 ssaSpec.getReg(), ropReg, ssaSpec.getCategory()); 643 644 } 645 646 int category = ssaSpec.getCategory(); 647 mapper.addMapping(ssaSpec.getReg(), ropReg, category); 648 ssaRegsMapped.set(ssaReg); 649 usedRopRegs.set(ropReg, ropReg + category); 650 } 651 652 653 /** 654 * Maps the source registers of the specified instruction such that they 655 * will fall in a contiguous range in Rop form. Moves are inserted as 656 * necessary to allow the range to be allocated. 657 * 658 * @param insn non-null; insn whos sources to process 659 */ 660 private void adjustAndMapSourceRangeRange(NormalSsaInsn insn) { 661 int newRegStart; 662 663 newRegStart = findRangeAndAdjust(insn); 664 665 RegisterSpecList sources = insn.getSources(); 666 int szSources = sources.size(); 667 int nextRopReg = newRegStart; 668 for (int i = 0; i < szSources; i++) { 669 RegisterSpec source = sources.get(i); 670 int sourceReg = source.getReg(); 671 int category = source.getCategory(); 672 int curRopReg = nextRopReg; 673 nextRopReg += category; 674 675 if (ssaRegsMapped.get(sourceReg)) { 676 continue; 677 } 678 679 LocalItem localItem = getLocalItemForReg(sourceReg); 680 addMapping(source, curRopReg); 681 682 if (localItem != null) { 683 markReserved(curRopReg, category); 684 ArrayList<RegisterSpec> similarRegisters 685 = localVariables.get(localItem); 686 687 int szSimilar = similarRegisters.size(); 688 689 // Try to map all SSA registers also associated with this local 690 for (int j = 0; j < szSimilar; j++) { 691 RegisterSpec similarSpec = similarRegisters.get(j); 692 int similarReg = similarSpec.getReg(); 693 694 // ...and don't map anything that's also a source... 695 if (-1 != sources.indexOfRegister(similarReg)) { 696 continue; 697 } 698 699 // Registers left unmapped will get handled later 700 tryMapReg(similarSpec, curRopReg, category); 701 } 702 } 703 } 704 } 705 706 /** 707 * Find a contiguous rop register range that fits the specified 708 * instruction's sources. First, try to center the range around 709 * sources that have already been mapped to Rop registers. If that fails, 710 * just find a new contiguous range that doesn't interfere. 711 712 * @param insn non-null; the insn whose sources need to fit. Must be 713 * last insn in basic block. 714 * @return >= 0 rop register of start of range 715 */ 716 private int findRangeAndAdjust(NormalSsaInsn insn) { 717 RegisterSpecList sources = insn.getSources(); 718 int szSources = sources.size(); 719 // the category for each source index 720 int categoriesForIndex[] = new int[szSources]; 721 int rangeLength = 0; 722 723 // Compute rangeLength and categoriesForIndex 724 for (int i = 0; i < szSources; i++) { 725 int category = sources.get(i).getCategory(); 726 categoriesForIndex[i] = category; 727 rangeLength += categoriesForIndex[i]; 728 } 729 730 // The highest score of fits tried so far 731 int maxScore = Integer.MIN_VALUE; 732 // the high scoring range's start 733 int resultRangeStart = -1; 734 // by source index: set of sources needing moves in high scoring plan 735 BitSet resultMovesRequired = null; 736 737 /* 738 * First, go through each source that's already been mapped. Try 739 * to center the range around the Rop register this source is mapped 740 * to. 741 */ 742 int rangeStartOffset = 0; 743 for (int i = 0; i < szSources; i++) { 744 int ssaCenterReg = sources.get(i).getReg(); 745 746 if (i != 0) { 747 rangeStartOffset -= categoriesForIndex[i - 1]; 748 } 749 if (!ssaRegsMapped.get(ssaCenterReg)) { 750 continue; 751 } 752 753 int rangeStart = mapper.oldToNew(ssaCenterReg) + rangeStartOffset; 754 755 if (rangeStart < 0 || spansParamRange(rangeStart, rangeLength)) { 756 continue; 757 } 758 759 BitSet curMovesRequired = new BitSet(szSources); 760 761 int fitWidth 762 = fitPlanForRange(rangeStart, insn, categoriesForIndex, 763 curMovesRequired); 764 765 if (fitWidth < 0) { 766 continue; 767 } 768 769 int score = fitWidth - curMovesRequired.cardinality(); 770 771 if (score > maxScore) { 772 maxScore = score; 773 resultRangeStart = rangeStart; 774 resultMovesRequired = curMovesRequired; 775 } 776 777 if (fitWidth == rangeLength) { 778 // We can't do any better than this, so stop here 779 break; 780 } 781 } 782 783 /* 784 * If we were unable to find a plan for a fit centered around 785 * an already-mapped source, just try to find a range of 786 * registers we can move the range into. 787 */ 788 789 if (resultRangeStart == -1) { 790 resultMovesRequired = new BitSet(szSources); 791 792 resultRangeStart = findAnyFittingRange(insn, rangeLength, 793 categoriesForIndex, resultMovesRequired); 794 } 795 796 /* 797 * Now, insert any moves required 798 */ 799 800 for (int i = resultMovesRequired.nextSetBit(0); i >= 0 801 ; i = resultMovesRequired.nextSetBit(i+1)) { 802 insn.changeOneSource(i, 803 insertMoveBefore(insn, sources.get(i))); 804 } 805 806 return resultRangeStart; 807 } 808 809 /** 810 * Finds an unreserved range that will fit the sources of the 811 * specified instruction. Does not bother trying to center the range 812 * around an already-mapped source register; 813 * 814 * @param insn non-null; insn to build range for 815 * @param rangeLength >=0 length required in register units. 816 * @param categoriesForIndex non-null; indexed by source index; 817 * the category for each source. 818 * @param outMovesRequired non-null; an output parameter indexed by 819 * source index that will contain the set of sources which need 820 * moves inserted. 821 * @return the rop register that starts the fitting range. 822 */ 823 private int findAnyFittingRange(NormalSsaInsn insn, int rangeLength, 824 int[] categoriesForIndex, BitSet outMovesRequired) { 825 int rangeStart = 0; 826 while (true) { 827 rangeStart = findNextUnreservedRopReg(rangeStart, rangeLength); 828 int fitWidth 829 = fitPlanForRange(rangeStart, insn, 830 categoriesForIndex, outMovesRequired); 831 832 if (fitWidth >= 0) { 833 break; 834 } 835 rangeStart++; 836 outMovesRequired.clear(); 837 } 838 return rangeStart; 839 } 840 841 /** 842 * Attempts to build a plan for fitting a range of sources into rop 843 * registers. 844 * 845 * @param ropReg >=0 rop reg that begins range 846 * @param insn non-null; insn to plan range for 847 * @param categoriesForIndex non-null; indexed by source index; 848 * the category for each source. 849 * @param outMovesRequired non-null; an output parameter indexed by 850 * source index that will contain the set of sources which need 851 * moves inserted. 852 * @return the width of the fit that that does not involve added moves or 853 * -1 if "no fit possible" 854 */ 855 private int fitPlanForRange(int ropReg, NormalSsaInsn insn, 856 int[] categoriesForIndex, BitSet outMovesRequired) { 857 RegisterSpecList sources = insn.getSources(); 858 int szSources = sources.size(); 859 int fitWidth = 0; 860 IntSet liveOut = insn.getBlock().getLiveOutRegs(); 861 RegisterSpecList liveOutSpecs = ssaSetToSpecs(liveOut); 862 863 // An SSA reg may only be mapped into a range once 864 BitSet seen = new BitSet(ssaMeth.getRegCount()); 865 866 for (int i = 0; i < szSources ; i++) { 867 RegisterSpec ssaSpec = sources.get(i); 868 int ssaReg = ssaSpec.getReg(); 869 int category = categoriesForIndex[i]; 870 871 if (i != 0) { 872 ropReg += categoriesForIndex[i-1]; 873 } 874 875 if (ssaRegsMapped.get(ssaReg) 876 && mapper.oldToNew(ssaReg) == ropReg) { 877 // A register already mapped appropriately 878 fitWidth += category; 879 } else if (rangeContainsReserved(ropReg, category)) { 880 fitWidth = -1; 881 break; 882 } else if (!ssaRegsMapped.get(ssaReg) 883 && canMapReg(ssaSpec, ropReg) 884 && !seen.get(ssaReg)) { 885 // A register that can be mapped appropriately 886 fitWidth += category; 887 } else if (!mapper.areAnyPinned(liveOutSpecs, ropReg, category) 888 && !mapper.areAnyPinned(sources, ropReg, category)) { 889 /* 890 * A source that can be moved 891 * We can insert a move as long as: 892 * 893 * - no SSA register pinned to the desired rop reg 894 * is live out on the block 895 * - no SSA register pinned to desired rop reg is 896 * a source of this insn (since this may require 897 * overlapping moves, which we can't presently handle) 898 */ 899 900 outMovesRequired.set(i); 901 } else { 902 fitWidth = -1; 903 break; 904 } 905 906 seen.set(ssaReg); 907 } 908 return fitWidth; 909 } 910 911 /** 912 * Converts a bit set of SSA registers into a RegisterSpecList containing 913 * the definition specs of all the registers. 914 * 915 * @param ssaSet non-null; set of SSA registers 916 * @return list of RegisterSpecs as noted above 917 */ 918 RegisterSpecList ssaSetToSpecs(IntSet ssaSet) { 919 RegisterSpecList result = new RegisterSpecList(ssaSet.elements()); 920 921 IntIterator iter = ssaSet.iterator(); 922 923 int i = 0; 924 while (iter.hasNext()) { 925 result.set(i++, getDefinitionSpecForSsaReg(iter.next())); 926 } 927 928 return result; 929 } 930 931 /** 932 * Gets a local item associated with an ssa register, if one exists 933 * 934 * @param ssaReg >= 0 SSA register 935 * @return null-ok; associated local item or null 936 */ 937 private LocalItem getLocalItemForReg(int ssaReg) { 938 for(Map.Entry<LocalItem, ArrayList<RegisterSpec>> entry: 939 localVariables.entrySet()) { 940 941 for (RegisterSpec spec: entry.getValue()) { 942 if (spec.getReg() == ssaReg) { 943 return entry.getKey(); 944 } 945 } 946 } 947 948 return null; 949 } 950} 951