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