vm/compiler/codegen/mips/LocalOptimizations.cpp

   1 /*
   2  * Copyright (C) 2009 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
  17 #include "Dalvik.h"
  18 #include "vm/compiler/CompilerInternals.h"
  19 #include "MipsLIR.h"
  20 #include "Codegen.h"
  21
  22 #define DEBUG_OPT(X)
  23
  24 /* Check RAW, WAR, and WAR dependency on the register operands */
  25 #define CHECK_REG_DEP(use, def, check) ((def & check->useMask) || \
  26                                         ((use | def) & check->defMask))
  27
  28 /* Scheduler heuristics */
  29 #define MAX_HOIST_DISTANCE 20
  30 #define LDLD_DISTANCE 4
  31 #define LD_LATENCY 2
  32
  33 static inline bool isDalvikRegisterClobbered(MipsLIR *lir1, MipsLIR *lir2)
  34 {
  35     int reg1Lo = DECODE_ALIAS_INFO_REG(lir1->aliasInfo);
  36     int reg1Hi = reg1Lo + DECODE_ALIAS_INFO_WIDE(lir1->aliasInfo);
  37     int reg2Lo = DECODE_ALIAS_INFO_REG(lir2->aliasInfo);
  38     int reg2Hi = reg2Lo + DECODE_ALIAS_INFO_WIDE(lir2->aliasInfo);
  39
  40     return (reg1Lo == reg2Lo) || (reg1Lo == reg2Hi) || (reg1Hi == reg2Lo);
  41 }
  42
  43 #if 0
  44 /* Debugging utility routine */
  45 static void dumpDependentInsnPair(MipsLIR *thisLIR, MipsLIR *checkLIR,
  46                                   const char *optimization)
  47 {
  48     LOGD("************ %s ************", optimization);
  49     dvmDumpLIRInsn((LIR *) thisLIR, 0);
  50     dvmDumpLIRInsn((LIR *) checkLIR, 0);
  51 }
  52 #endif
  53
  54 /* Convert a more expensive instruction (ie load) into a move */
  55 static void convertMemOpIntoMove(CompilationUnit *cUnit, MipsLIR *origLIR,
  56                                  int dest, int src)
  57 {
  58     /* Insert a move to replace the load */
  59     MipsLIR *moveLIR;
  60     moveLIR = dvmCompilerRegCopyNoInsert( cUnit, dest, src);
  61     /*
  62      * Insert the converted instruction after the original since the
  63      * optimization is scannng in the top-down order and the new instruction
  64      * will need to be re-checked (eg the new dest clobbers the src used in
  65      * thisLIR).
  66      */
  67     dvmCompilerInsertLIRAfter((LIR *) origLIR, (LIR *) moveLIR);
  68 }
  69
  70 /*
  71  * Perform a pass of top-down walk, from the second-last instruction in the
  72  * superblock, to eliminate redundant loads and stores.
  73  *
  74  * An earlier load can eliminate a later load iff
  75  *   1) They are must-aliases
  76  *   2) The native register is not clobbered in between
  77  *   3) The memory location is not written to in between
  78  *
  79  * An earlier store can eliminate a later load iff
  80  *   1) They are must-aliases
  81  *   2) The native register is not clobbered in between
  82  *   3) The memory location is not written to in between
  83  *
  84  * A later store can be eliminated by an earlier store iff
  85  *   1) They are must-aliases
  86  *   2) The memory location is not written to in between
  87  */
  88 static void applyLoadStoreElimination(CompilationUnit *cUnit,
  89                                       MipsLIR *headLIR,
  90                                       MipsLIR *tailLIR)
  91 {
  92     MipsLIR *thisLIR;
  93
  94     if (headLIR == tailLIR) return;
  95
  96     for (thisLIR = PREV_LIR(tailLIR);
  97          thisLIR != headLIR;
  98          thisLIR = PREV_LIR(thisLIR)) {
  99         int sinkDistance = 0;
 100
 101         /* Skip non-interesting instructions */
 102         if ((thisLIR->flags.isNop == true) ||
 103             isPseudoOpCode(thisLIR->opcode) ||
 104             !(EncodingMap[thisLIR->opcode].flags & (IS_LOAD | IS_STORE))) {
 105             continue;
 106         }
 107
 108         int nativeRegId = thisLIR->operands[0];
 109         bool isThisLIRLoad = EncodingMap[thisLIR->opcode].flags & IS_LOAD;
 110         MipsLIR *checkLIR;
 111         /* Use the mem mask to determine the rough memory location */
 112         u8 thisMemMask = (thisLIR->useMask | thisLIR->defMask) & ENCODE_MEM;
 113
 114         /*
 115          * Currently only eliminate redundant ld/st for constant and Dalvik
 116          * register accesses.
 117          */
 118         if (!(thisMemMask & (ENCODE_LITERAL | ENCODE_DALVIK_REG))) continue;
 119
 120         /*
 121          * Add r15 (pc) to the resource mask to prevent this instruction
 122          * from sinking past branch instructions. Also take out the memory
 123          * region bits since stopMask is used to check data/control
 124          * dependencies.
 125          */
 126         u8 stopUseRegMask = (ENCODE_REG_PC | thisLIR->useMask) &
 127                             ~ENCODE_MEM;
 128         u8 stopDefRegMask = thisLIR->defMask & ~ENCODE_MEM;
 129
 130         for (checkLIR = NEXT_LIR(thisLIR);
 131              checkLIR != tailLIR;
 132              checkLIR = NEXT_LIR(checkLIR)) {
 133
 134             /*
 135              * Skip already dead instructions (whose dataflow information is
 136              * outdated and misleading).
 137              */
 138             if (checkLIR->flags.isNop) continue;
 139
 140             u8 checkMemMask = (checkLIR->useMask | checkLIR->defMask) &
 141                               ENCODE_MEM;
 142             u8 aliasCondition = thisMemMask & checkMemMask;
 143             bool stopHere = false;
 144
 145             /*
 146              * Potential aliases seen - check the alias relations
 147              */
 148             if (checkMemMask != ENCODE_MEM && aliasCondition != 0) {
 149                 bool isCheckLIRLoad = EncodingMap[checkLIR->opcode].flags &
 150                                       IS_LOAD;
 151                 if  (aliasCondition == ENCODE_LITERAL) {
 152                     /*
 153                      * Should only see literal loads in the instruction
 154                      * stream.
 155                      */
 156                     assert(!(EncodingMap[checkLIR->opcode].flags &
 157                              IS_STORE));
 158                     /* Same value && same register type */
 159                     if (checkLIR->aliasInfo == thisLIR->aliasInfo &&
 160                         REGTYPE(checkLIR->operands[0]) == REGTYPE(nativeRegId)){
 161                         /*
 162                          * Different destination register - insert
 163                          * a move
 164                          */
 165                         if (checkLIR->operands[0] != nativeRegId) {
 166                             convertMemOpIntoMove(cUnit, checkLIR,
 167                                                  checkLIR->operands[0],
 168                                                  nativeRegId);
 169                         }
 170                         checkLIR->flags.isNop = true;
 171                     }
 172                 } else if (aliasCondition == ENCODE_DALVIK_REG) {
 173                     /* Must alias */
 174                     if (checkLIR->aliasInfo == thisLIR->aliasInfo) {
 175                         /* Only optimize compatible registers */
 176                         bool regCompatible =
 177                             REGTYPE(checkLIR->operands[0]) ==
 178                             REGTYPE(nativeRegId);
 179                         if ((isThisLIRLoad && isCheckLIRLoad) ||
 180                             (!isThisLIRLoad && isCheckLIRLoad)) {
 181                             /* RAR or RAW */
 182                             if (regCompatible) {
 183                                 /*
 184                                  * Different destination register -
 185                                  * insert a move
 186                                  */
 187                                 if (checkLIR->operands[0] !=
 188                                     nativeRegId) {
 189                                     convertMemOpIntoMove(cUnit,
 190                                                  checkLIR,
 191                                                  checkLIR->operands[0],
 192                                                  nativeRegId);
 193                                 }
 194                                 checkLIR->flags.isNop = true;
 195                             } else {
 196                                 /*
 197                                  * Destinaions are of different types -
 198                                  * something complicated going on so
 199                                  * stop looking now.
 200                                  */
 201                                 stopHere = true;
 202                             }
 203                         } else if (isThisLIRLoad && !isCheckLIRLoad) {
 204                             /* WAR - register value is killed */
 205                             stopHere = true;
 206                         } else if (!isThisLIRLoad && !isCheckLIRLoad) {
 207                             /* WAW - nuke the earlier store */
 208                             thisLIR->flags.isNop = true;
 209                             stopHere = true;
 210                         }
 211                     /* Partial overlap */
 212                     } else if (isDalvikRegisterClobbered(thisLIR, checkLIR)) {
 213                         /*
 214                          * It is actually ok to continue if checkLIR
 215                          * is a read. But it is hard to make a test
 216                          * case for this so we just stop here to be
 217                          * conservative.
 218                          */
 219                         stopHere = true;
 220                     }
 221                 }
 222                 /* Memory content may be updated. Stop looking now. */
 223                 if (stopHere) {
 224                     break;
 225                 /* The checkLIR has been transformed - check the next one */
 226                 } else if (checkLIR->flags.isNop) {
 227                     continue;
 228                 }
 229             }
 230
 231
 232             /*
 233              * this and check LIRs have no memory dependency. Now check if
 234              * their register operands have any RAW, WAR, and WAW
 235              * dependencies. If so, stop looking.
 236              */
 237             if (stopHere == false) {
 238                 stopHere = CHECK_REG_DEP(stopUseRegMask, stopDefRegMask,
 239                                          checkLIR);
 240             }
 241
 242             if (stopHere == true) {
 243                 DEBUG_OPT(dumpDependentInsnPair(thisLIR, checkLIR,
 244                                                 "REG CLOBBERED"));
 245                 /* Only sink store instructions */
 246                 if (sinkDistance && !isThisLIRLoad) {
 247                     MipsLIR *newStoreLIR =
 248                         (MipsLIR *) dvmCompilerNew(sizeof(MipsLIR), true);
 249                     *newStoreLIR = *thisLIR;
 250                     /*
 251                      * Stop point found - insert *before* the checkLIR
 252                      * since the instruction list is scanned in the
 253                      * top-down order.
 254                      */
 255                     dvmCompilerInsertLIRBefore((LIR *) checkLIR,
 256                                                (LIR *) newStoreLIR);
 257                     thisLIR->flags.isNop = true;
 258                 }
 259                 break;
 260             } else if (!checkLIR->flags.isNop) {
 261                 sinkDistance++;
 262             }
 263         }
 264     }
 265 }
 266
 267 /*
 268  * Perform a pass of bottom-up walk, from the second instruction in the
 269  * superblock, to try to hoist loads to earlier slots.
 270  */
 271 static void applyLoadHoisting(CompilationUnit *cUnit,
 272                               MipsLIR *headLIR,
 273                               MipsLIR *tailLIR)
 274 {
 275     MipsLIR *thisLIR, *checkLIR;
 276     /*
 277      * Store the list of independent instructions that can be hoisted past.
 278      * Will decide the best place to insert later.
 279      */
 280     MipsLIR *prevInstList[MAX_HOIST_DISTANCE];
 281
 282     /* Empty block */
 283     if (headLIR == tailLIR) return;
 284
 285     /* Start from the second instruction */
 286     for (thisLIR = NEXT_LIR(headLIR);
 287          thisLIR != tailLIR;
 288          thisLIR = NEXT_LIR(thisLIR)) {
 289
 290         /* Skip non-interesting instructions */
 291         if ((thisLIR->flags.isNop == true) ||
 292             isPseudoOpCode(thisLIR->opcode) ||
 293             !(EncodingMap[thisLIR->opcode].flags & IS_LOAD)) {
 294             continue;
 295         }
 296
 297         u8 stopUseAllMask = thisLIR->useMask;
 298
 299         /*
 300          * Branches for null/range checks are marked with the true resource
 301          * bits, and loads to Dalvik registers, constant pools, and non-alias
 302          * locations are safe to be hoisted. So only mark the heap references
 303          * conservatively here.
 304          */
 305         if (stopUseAllMask & ENCODE_HEAP_REF) {
 306             stopUseAllMask |= ENCODE_REG_PC;
 307         }
 308
 309         /* Similar as above, but just check for pure register dependency */
 310         u8 stopUseRegMask = stopUseAllMask & ~ENCODE_MEM;
 311         u8 stopDefRegMask = thisLIR->defMask & ~ENCODE_MEM;
 312
 313         int nextSlot = 0;
 314         bool stopHere = false;
 315
 316         /* Try to hoist the load to a good spot */
 317         for (checkLIR = PREV_LIR(thisLIR);
 318              checkLIR != headLIR;
 319              checkLIR = PREV_LIR(checkLIR)) {
 320
 321             /*
 322              * Skip already dead instructions (whose dataflow information is
 323              * outdated and misleading).
 324              */
 325             if (checkLIR->flags.isNop) continue;
 326
 327             u8 checkMemMask = checkLIR->defMask & ENCODE_MEM;
 328             u8 aliasCondition = stopUseAllMask & checkMemMask;
 329             stopHere = false;
 330
 331             /* Potential WAR alias seen - check the exact relation */
 332             if (checkMemMask != ENCODE_MEM && aliasCondition != 0) {
 333                 /* We can fully disambiguate Dalvik references */
 334                 if (aliasCondition == ENCODE_DALVIK_REG) {
 335                     /* Must alias or partually overlap */
 336                     if ((checkLIR->aliasInfo == thisLIR->aliasInfo) ||
 337                         isDalvikRegisterClobbered(thisLIR, checkLIR)) {
 338                         stopHere = true;
 339                     }
 340                 /* Conservatively treat all heap refs as may-alias */
 341                 } else {
 342                     assert(aliasCondition == ENCODE_HEAP_REF);
 343                     stopHere = true;
 344                 }
 345                 /* Memory content may be updated. Stop looking now. */
 346                 if (stopHere) {
 347                     prevInstList[nextSlot++] = checkLIR;
 348                     break;
 349                 }
 350             }
 351
 352             if (stopHere == false) {
 353                 stopHere = CHECK_REG_DEP(stopUseRegMask, stopDefRegMask,
 354                                          checkLIR);
 355             }
 356
 357             /*
 358              * Store the dependent or non-pseudo/indepedent instruction to the
 359              * list.
 360              */
 361             if (stopHere || !isPseudoOpCode(checkLIR->opcode)) {
 362                 prevInstList[nextSlot++] = checkLIR;
 363                 if (nextSlot == MAX_HOIST_DISTANCE) break;
 364             }
 365
 366             /* Found a new place to put the load - move it here */
 367             if (stopHere == true) {
 368                 DEBUG_OPT(dumpDependentInsnPair(checkLIR, thisLIR
 369                                                 "HOIST STOP"));
 370                 break;
 371             }
 372         }
 373
 374         /*
 375          * Reached the top - use headLIR as the dependent marker as all labels
 376          * are barriers.
 377          */
 378         if (stopHere == false && nextSlot < MAX_HOIST_DISTANCE) {
 379             prevInstList[nextSlot++] = headLIR;
 380         }
 381
 382         /*
 383          * At least one independent instruction is found. Scan in the reversed
 384          * direction to find a beneficial slot.
 385          */
 386         if (nextSlot >= 2) {
 387             int firstSlot = nextSlot - 2;
 388             int slot;
 389             MipsLIR *depLIR = prevInstList[nextSlot-1];
 390             /* If there is ld-ld dependency, wait LDLD_DISTANCE cycles */
 391             if (!isPseudoOpCode(depLIR->opcode) &&
 392                 (EncodingMap[depLIR->opcode].flags & IS_LOAD)) {
 393                 firstSlot -= LDLD_DISTANCE;
 394             }
 395             /*
 396              * Make sure we check slot >= 0 since firstSlot may be negative
 397              * when the loop is first entered.
 398              */
 399             for (slot = firstSlot; slot >= 0; slot--) {
 400                 MipsLIR *curLIR = prevInstList[slot];
 401                 MipsLIR *prevLIR = prevInstList[slot+1];
 402
 403                 /* Check the highest instruction */
 404                 if (prevLIR->defMask == ENCODE_ALL) {
 405                     /*
 406                      * If the first instruction is a load, don't hoist anything
 407                      * above it since it is unlikely to be beneficial.
 408                      */
 409                     if (EncodingMap[curLIR->opcode].flags & IS_LOAD) continue;
 410                     /*
 411                      * If the remaining number of slots is less than LD_LATENCY,
 412                      * insert the hoisted load here.
 413                      */
 414                     if (slot < LD_LATENCY) break;
 415                 }
 416
 417                 /*
 418                  * NOTE: now prevLIR is guaranteed to be a non-pseudo
 419                  * instruction (ie accessing EncodingMap[prevLIR->opcode] is
 420                  * safe).
 421                  *
 422                  * Try to find two instructions with load/use dependency until
 423                  * the remaining instructions are less than LD_LATENCY.
 424                  */
 425                 if (((curLIR->useMask & prevLIR->defMask) &&
 426                      (EncodingMap[prevLIR->opcode].flags & IS_LOAD)) ||
 427                     (slot < LD_LATENCY)) {
 428                     break;
 429                 }
 430             }
 431
 432             /* Found a slot to hoist to */
 433             if (slot >= 0) {
 434                 MipsLIR *curLIR = prevInstList[slot];
 435                 MipsLIR *newLoadLIR = (MipsLIR *) dvmCompilerNew(sizeof(MipsLIR),
 436                                                                true);
 437                 *newLoadLIR = *thisLIR;
 438                 /*
 439                  * Insertion is guaranteed to succeed since checkLIR
 440                  * is never the first LIR on the list
 441                  */
 442                 dvmCompilerInsertLIRBefore((LIR *) curLIR,
 443                                            (LIR *) newLoadLIR);
 444                 thisLIR->flags.isNop = true;
 445             }
 446         }
 447     }
 448 }
 449
 450 void dvmCompilerApplyLocalOptimizations(CompilationUnit *cUnit, LIR *headLIR,
 451                                         LIR *tailLIR)
 452 {
 453     if (!(gDvmJit.disableOpt & (1 << kLoadStoreElimination))) {
 454         applyLoadStoreElimination(cUnit, (MipsLIR *) headLIR,
 455                                   (MipsLIR *) tailLIR);
 456     }
 457     if (!(gDvmJit.disableOpt & (1 << kLoadHoisting))) {
 458         applyLoadHoisting(cUnit, (MipsLIR *) headLIR, (MipsLIR *) tailLIR);
 459     }
 460 }