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