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