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