vm/analysis/Optimize.c

   1 /*
   2  * Copyright (C) 2008 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 /*
  18  * Perform some simple bytecode optimizations, chiefly "quickening" of
  19  * opcodes.
  20  */
  21 #include "Dalvik.h"
  22 #include "libdex/InstrUtils.h"
  23
  24 #include <zlib.h>
  25
  26 #include <stdlib.h>
  27
  28 /*
  29  * Virtual/direct calls to "method" are replaced with an execute-inline
  30  * instruction with index "idx".
  31  */
  32 struct InlineSub {
  33     Method* method;
  34     int     inlineIdx;
  35 };
  36
  37
  38 /* fwd */
  39 static void optimizeMethod(Method* method, bool essentialOnly);
  40 static bool rewriteInstField(Method* method, u2* insns, OpCode quickOpc,
  41     OpCode volatileOpc);
  42 static bool rewriteStaticField(Method* method, u2* insns, OpCode volatileOpc);
  43 static bool rewriteVirtualInvoke(Method* method, u2* insns, OpCode newOpc);
  44 static bool rewriteEmptyDirectInvoke(Method* method, u2* insns);
  45 static bool rewriteExecuteInline(Method* method, u2* insns,
  46     MethodType methodType);
  47 static bool rewriteExecuteInlineRange(Method* method, u2* insns,
  48     MethodType methodType);
  49
  50
  51 /*
  52  * Create a table of inline substitutions.
  53  *
  54  * TODO: this is currently just a linear array.  We will want to put this
  55  * into a hash table as the list size increases.
  56  */
  57 InlineSub* dvmCreateInlineSubsTable(void)
  58 {
  59     const InlineOperation* ops = dvmGetInlineOpsTable();
  60     const int count = dvmGetInlineOpsTableLength();
  61     InlineSub* table;
  62     Method* method;
  63     ClassObject* clazz;
  64     int i, tableIndex;
  65
  66     /*
  67      * Allocate for optimism: one slot per entry, plus an end-of-list marker.
  68      */
  69     table = malloc(sizeof(InlineSub) * (count+1));
  70
  71     tableIndex = 0;
  72     for (i = 0; i < count; i++) {
  73         clazz = dvmFindClassNoInit(ops[i].classDescriptor, NULL);
  74         if (clazz == NULL) {
  75             LOGV("DexOpt: can't inline for class '%s': not found\n",
  76                 ops[i].classDescriptor);
  77             dvmClearOptException(dvmThreadSelf());
  78         } else {
  79             /*
  80              * Method could be virtual or direct.  Try both.  Don't use
  81              * the "hier" versions.
  82              */
  83             method = dvmFindDirectMethodByDescriptor(clazz, ops[i].methodName,
  84                         ops[i].methodSignature);
  85             if (method == NULL)
  86                 method = dvmFindVirtualMethodByDescriptor(clazz, ops[i].methodName,
  87                         ops[i].methodSignature);
  88             if (method == NULL) {
  89                 LOGW("DexOpt: can't inline %s.%s %s: method not found\n",
  90                     ops[i].classDescriptor, ops[i].methodName,
  91                     ops[i].methodSignature);
  92             } else {
  93                 if (!dvmIsFinalClass(clazz) && !dvmIsFinalMethod(method)) {
  94                     LOGW("DexOpt: WARNING: inline op on non-final class/method "
  95                          "%s.%s\n",
  96                         clazz->descriptor, method->name);
  97                     /* fail? */
  98                 }
  99                 if (dvmIsSynchronizedMethod(method) ||
 100                     dvmIsDeclaredSynchronizedMethod(method))
 101                 {
 102                     LOGW("DexOpt: WARNING: inline op on synchronized method "
 103                          "%s.%s\n",
 104                         clazz->descriptor, method->name);
 105                     /* fail? */
 106                 }
 107
 108                 table[tableIndex].method = method;
 109                 table[tableIndex].inlineIdx = i;
 110                 tableIndex++;
 111
 112                 LOGV("DexOpt: will inline %d: %s.%s %s\n", i,
 113                     ops[i].classDescriptor, ops[i].methodName,
 114                     ops[i].methodSignature);
 115             }
 116         }
 117     }
 118
 119     /* mark end of table */
 120     table[tableIndex].method = NULL;
 121     LOGV("DexOpt: inline table has %d entries\n", tableIndex);
 122
 123     return table;
 124 }
 125
 126 /*
 127  * Release inline sub data structure.
 128  */
 129 void dvmFreeInlineSubsTable(InlineSub* inlineSubs)
 130 {
 131     free(inlineSubs);
 132 }
 133
 134
 135 /*
 136  * Optimize the specified class.
 137  *
 138  * If "essentialOnly" is true, we only do essential optimizations.  For
 139  * example, accesses to volatile 64-bit fields must be replaced with
 140  * "-wide-volatile" instructions or the program could behave incorrectly.
 141  * (Skipping non-essential optimizations makes us a little bit faster, and
 142  * more importantly avoids dirtying DEX pages.)
 143  */
 144 void dvmOptimizeClass(ClassObject* clazz, bool essentialOnly)
 145 {
 146     int i;
 147
 148     for (i = 0; i < clazz->directMethodCount; i++) {
 149         optimizeMethod(&clazz->directMethods[i], essentialOnly);
 150     }
 151     for (i = 0; i < clazz->virtualMethodCount; i++) {
 152         optimizeMethod(&clazz->virtualMethods[i], essentialOnly);
 153     }
 154 }
 155
 156 /*
 157  * Optimize instructions in a method.
 158  *
 159  * This does a single pass through the code, examining each instruction.
 160  *
 161  * This is not expected to fail if the class was successfully verified.
 162  * The only significant failure modes occur when an "essential" update fails,
 163  * but we can't generally identify those: if we can't look up a field,
 164  * we can't know if the field access was supposed to be handled as volatile.
 165  *
 166  * Instead, we give it our best effort, and hope for the best.  For 100%
 167  * reliability, only optimize a class after verification succeeds.
 168  */
 169 static void optimizeMethod(Method* method, bool essentialOnly)
 170 {
 171     u4 insnsSize;
 172     u2* insns;
 173     u2 inst;
 174
 175     if (!gDvm.optimizing && !essentialOnly) {
 176         /* unexpected; will force copy-on-write of a lot of pages */
 177         LOGD("NOTE: doing full bytecode optimization outside dexopt\n");
 178     }
 179
 180     if (dvmIsNativeMethod(method) || dvmIsAbstractMethod(method))
 181         return;
 182
 183     insns = (u2*) method->insns;
 184     assert(insns != NULL);
 185     insnsSize = dvmGetMethodInsnsSize(method);
 186
 187     while (insnsSize > 0) {
 188         OpCode quickOpc, volatileOpc = OP_NOP;
 189         int width;
 190         bool notMatched = false;
 191
 192         inst = *insns & 0xff;
 193
 194         switch (inst) {
 195         case OP_IGET:
 196         case OP_IGET_BOOLEAN:
 197         case OP_IGET_BYTE:
 198         case OP_IGET_CHAR:
 199         case OP_IGET_SHORT:
 200             quickOpc = OP_IGET_QUICK;
 201             if (ANDROID_SMP != 0)
 202                 volatileOpc = OP_IGET_VOLATILE;
 203             goto rewrite_inst_field;
 204         case OP_IGET_WIDE:
 205             quickOpc = OP_IGET_WIDE_QUICK;
 206             volatileOpc = OP_IGET_WIDE_VOLATILE;
 207             goto rewrite_inst_field;
 208         case OP_IGET_OBJECT:
 209             quickOpc = OP_IGET_OBJECT_QUICK;
 210             if (ANDROID_SMP != 0)
 211                 volatileOpc = OP_IGET_OBJECT_VOLATILE;
 212             goto rewrite_inst_field;
 213         case OP_IPUT:
 214         case OP_IPUT_BOOLEAN:
 215         case OP_IPUT_BYTE:
 216         case OP_IPUT_CHAR:
 217         case OP_IPUT_SHORT:
 218             quickOpc = OP_IPUT_QUICK;
 219             if (ANDROID_SMP != 0)
 220                 volatileOpc = OP_IPUT_VOLATILE;
 221             goto rewrite_inst_field;
 222         case OP_IPUT_WIDE:
 223             quickOpc = OP_IPUT_WIDE_QUICK;
 224             volatileOpc = OP_IPUT_WIDE_VOLATILE;
 225             goto rewrite_inst_field;
 226         case OP_IPUT_OBJECT:
 227             quickOpc = OP_IPUT_OBJECT_QUICK;
 228             if (ANDROID_SMP != 0)
 229                 volatileOpc = OP_IPUT_OBJECT_VOLATILE;
 230 rewrite_inst_field:
 231             if (essentialOnly)
 232                 quickOpc = OP_NOP;
 233             if (quickOpc != OP_NOP || volatileOpc != OP_NOP)
 234                 rewriteInstField(method, insns, quickOpc, volatileOpc);
 235             break;
 236
 237 #if ANDROID_SMP != 0
 238         case OP_SGET:
 239         case OP_SGET_BOOLEAN:
 240         case OP_SGET_BYTE:
 241         case OP_SGET_CHAR:
 242         case OP_SGET_SHORT:
 243             volatileOpc = OP_SGET_VOLATILE;
 244             goto rewrite_static_field;
 245         case OP_SGET_OBJECT:
 246             volatileOpc = OP_SGET_OBJECT_VOLATILE;
 247             goto rewrite_static_field;
 248         case OP_SPUT:
 249         case OP_SPUT_BOOLEAN:
 250         case OP_SPUT_BYTE:
 251         case OP_SPUT_CHAR:
 252         case OP_SPUT_SHORT:
 253             volatileOpc = OP_SPUT_VOLATILE;
 254             goto rewrite_static_field;
 255         case OP_SPUT_OBJECT:
 256             volatileOpc = OP_SPUT_OBJECT_VOLATILE;
 257             goto rewrite_static_field;
 258 #endif
 259         case OP_SGET_WIDE:
 260             volatileOpc = OP_SGET_WIDE_VOLATILE;
 261             goto rewrite_static_field;
 262         case OP_SPUT_WIDE:
 263             volatileOpc = OP_SPUT_WIDE_VOLATILE;
 264 rewrite_static_field:
 265             rewriteStaticField(method, insns, volatileOpc);
 266             break;
 267
 268         default:
 269             /* not one of the "essential" replacements; check for more */
 270             notMatched = true;
 271         }
 272
 273         if (notMatched && !essentialOnly) {
 274             switch (inst) {
 275             case OP_INVOKE_VIRTUAL:
 276                 if (!rewriteExecuteInline(method, insns, METHOD_VIRTUAL)) {
 277                     rewriteVirtualInvoke(method, insns,
 278                             OP_INVOKE_VIRTUAL_QUICK);
 279                 }
 280                 break;
 281             case OP_INVOKE_VIRTUAL_RANGE:
 282                 if (!rewriteExecuteInlineRange(method, insns, METHOD_VIRTUAL)) {
 283                     rewriteVirtualInvoke(method, insns,
 284                             OP_INVOKE_VIRTUAL_QUICK_RANGE);
 285                 }
 286                 break;
 287             case OP_INVOKE_SUPER:
 288                 rewriteVirtualInvoke(method, insns, OP_INVOKE_SUPER_QUICK);
 289                 break;
 290             case OP_INVOKE_SUPER_RANGE:
 291                 rewriteVirtualInvoke(method, insns, OP_INVOKE_SUPER_QUICK_RANGE);
 292                 break;
 293
 294             case OP_INVOKE_DIRECT:
 295                 if (!rewriteExecuteInline(method, insns, METHOD_DIRECT)) {
 296                     rewriteEmptyDirectInvoke(method, insns);
 297                 }
 298                 break;
 299             case OP_INVOKE_DIRECT_RANGE:
 300                 rewriteExecuteInlineRange(method, insns, METHOD_DIRECT);
 301                 break;
 302
 303             case OP_INVOKE_STATIC:
 304                 rewriteExecuteInline(method, insns, METHOD_STATIC);
 305                 break;
 306             case OP_INVOKE_STATIC_RANGE:
 307                 rewriteExecuteInlineRange(method, insns, METHOD_STATIC);
 308                 break;
 309
 310             default:
 311                 /* nothing to do for this instruction */
 312                 ;
 313             }
 314         }
 315
 316         width = dexGetInstrOrTableWidthAbs(gDvm.instrWidth, insns);
 317         assert(width > 0);
 318
 319         insns += width;
 320         insnsSize -= width;
 321     }
 322
 323     assert(insnsSize == 0);
 324 }
 325
 326 /*
 327  * Update a 16-bit code unit in "meth".
 328  */
 329 static inline void updateCode(const Method* meth, u2* ptr, u2 newVal)
 330 {
 331     if (gDvm.optimizing) {
 332         /* dexopt time, alter the output directly */
 333         *ptr = newVal;
 334     } else {
 335         /* runtime, toggle the page read/write status */
 336         dvmDexChangeDex2(meth->clazz->pDvmDex, ptr, newVal);
 337     }
 338 }
 339
 340 /*
 341  * If "referrer" and "resClass" don't come from the same DEX file, and
 342  * the DEX we're working on is not destined for the bootstrap class path,
 343  * tweak the class loader so package-access checks work correctly.
 344  *
 345  * Only do this if we're doing pre-verification or optimization.
 346  */
 347 static void tweakLoader(ClassObject* referrer, ClassObject* resClass)
 348 {
 349     if (!gDvm.optimizing)
 350         return;
 351     assert(referrer->classLoader == NULL);
 352     assert(resClass->classLoader == NULL);
 353
 354     if (!gDvm.optimizingBootstrapClass) {
 355         /* class loader for an array class comes from element type */
 356         if (dvmIsArrayClass(resClass))
 357             resClass = resClass->elementClass;
 358         if (referrer->pDvmDex != resClass->pDvmDex)
 359             resClass->classLoader = (Object*) 0xdead3333;
 360     }
 361 }
 362
 363 /*
 364  * Undo the effects of tweakLoader.
 365  */
 366 static void untweakLoader(ClassObject* referrer, ClassObject* resClass)
 367 {
 368     if (!gDvm.optimizing || gDvm.optimizingBootstrapClass)
 369         return;
 370
 371     if (dvmIsArrayClass(resClass))
 372         resClass = resClass->elementClass;
 373     resClass->classLoader = NULL;
 374 }
 375
 376
 377 /*
 378  * Alternate version of dvmResolveClass for use with verification and
 379  * optimization.  Performs access checks on every resolve, and refuses
 380  * to acknowledge the existence of classes defined in more than one DEX
 381  * file.
 382  *
 383  * Exceptions caused by failures are cleared before returning.
 384  *
 385  * On failure, returns NULL, and sets *pFailure if pFailure is not NULL.
 386  */
 387 ClassObject* dvmOptResolveClass(ClassObject* referrer, u4 classIdx,
 388     VerifyError* pFailure)
 389 {
 390     DvmDex* pDvmDex = referrer->pDvmDex;
 391     ClassObject* resClass;
 392
 393     /*
 394      * Check the table first.  If not there, do the lookup by name.
 395      */
 396     resClass = dvmDexGetResolvedClass(pDvmDex, classIdx);
 397     if (resClass == NULL) {
 398         const char* className = dexStringByTypeIdx(pDvmDex->pDexFile, classIdx);
 399         if (className[0] != '\0' && className[1] == '\0') {
 400             /* primitive type */
 401             resClass = dvmFindPrimitiveClass(className[0]);
 402         } else {
 403             resClass = dvmFindClassNoInit(className, referrer->classLoader);
 404         }
 405         if (resClass == NULL) {
 406             /* not found, exception should be raised */
 407             LOGV("DexOpt: class %d (%s) not found\n",
 408                 classIdx,
 409                 dexStringByTypeIdx(pDvmDex->pDexFile, classIdx));
 410             if (pFailure != NULL) {
 411                 /* dig through the wrappers to find the original failure */
 412                 Object* excep = dvmGetException(dvmThreadSelf());
 413                 while (true) {
 414                     Object* cause = dvmGetExceptionCause(excep);
 415                     if (cause == NULL)
 416                         break;
 417                     excep = cause;
 418                 }
 419                 if (strcmp(excep->clazz->descriptor,
 420                     "Ljava/lang/IncompatibleClassChangeError;") == 0)
 421                 {
 422                     *pFailure = VERIFY_ERROR_CLASS_CHANGE;
 423                 } else {
 424                     *pFailure = VERIFY_ERROR_NO_CLASS;
 425                 }
 426             }
 427             dvmClearOptException(dvmThreadSelf());
 428             return NULL;
 429         }
 430
 431         /*
 432          * Add it to the resolved table so we're faster on the next lookup.
 433          */
 434         dvmDexSetResolvedClass(pDvmDex, classIdx, resClass);
 435     }
 436
 437     /* multiple definitions? */
 438     if (IS_CLASS_FLAG_SET(resClass, CLASS_MULTIPLE_DEFS)) {
 439         LOGI("DexOpt: not resolving ambiguous class '%s'\n",
 440             resClass->descriptor);
 441         if (pFailure != NULL)
 442             *pFailure = VERIFY_ERROR_NO_CLASS;
 443         return NULL;
 444     }
 445
 446     /* access allowed? */
 447     tweakLoader(referrer, resClass);
 448     bool allowed = dvmCheckClassAccess(referrer, resClass);
 449     untweakLoader(referrer, resClass);
 450     if (!allowed) {
 451         LOGW("DexOpt: resolve class illegal access: %s -> %s\n",
 452             referrer->descriptor, resClass->descriptor);
 453         if (pFailure != NULL)
 454             *pFailure = VERIFY_ERROR_ACCESS_CLASS;
 455         return NULL;
 456     }
 457
 458     return resClass;
 459 }
 460
 461 /*
 462  * Alternate version of dvmResolveInstField().
 463  *
 464  * On failure, returns NULL, and sets *pFailure if pFailure is not NULL.
 465  */
 466 InstField* dvmOptResolveInstField(ClassObject* referrer, u4 ifieldIdx,
 467     VerifyError* pFailure)
 468 {
 469     DvmDex* pDvmDex = referrer->pDvmDex;
 470     InstField* resField;
 471
 472     resField = (InstField*) dvmDexGetResolvedField(pDvmDex, ifieldIdx);
 473     if (resField == NULL) {
 474         const DexFieldId* pFieldId;
 475         ClassObject* resClass;
 476
 477         pFieldId = dexGetFieldId(pDvmDex->pDexFile, ifieldIdx);
 478
 479         /*
 480          * Find the field's class.
 481          */
 482         resClass = dvmOptResolveClass(referrer, pFieldId->classIdx, pFailure);
 483         if (resClass == NULL) {
 484             //dvmClearOptException(dvmThreadSelf());
 485             assert(!dvmCheckException(dvmThreadSelf()));
 486             if (pFailure != NULL) { assert(!VERIFY_OK(*pFailure)); }
 487             return NULL;
 488         }
 489
 490         resField = (InstField*)dvmFindFieldHier(resClass,
 491             dexStringById(pDvmDex->pDexFile, pFieldId->nameIdx),
 492             dexStringByTypeIdx(pDvmDex->pDexFile, pFieldId->typeIdx));
 493         if (resField == NULL) {
 494             LOGD("DexOpt: couldn't find field %s.%s\n",
 495                 resClass->descriptor,
 496                 dexStringById(pDvmDex->pDexFile, pFieldId->nameIdx));
 497             if (pFailure != NULL)
 498                 *pFailure = VERIFY_ERROR_NO_FIELD;
 499             return NULL;
 500         }
 501         if (dvmIsStaticField(&resField->field)) {
 502             LOGD("DexOpt: wanted instance, got static for field %s.%s\n",
 503                 resClass->descriptor,
 504                 dexStringById(pDvmDex->pDexFile, pFieldId->nameIdx));
 505             if (pFailure != NULL)
 506                 *pFailure = VERIFY_ERROR_CLASS_CHANGE;
 507             return NULL;
 508         }
 509
 510         /*
 511          * Add it to the resolved table so we're faster on the next lookup.
 512          */
 513         dvmDexSetResolvedField(pDvmDex, ifieldIdx, (Field*) resField);
 514     }
 515
 516     /* access allowed? */
 517     tweakLoader(referrer, resField->field.clazz);
 518     bool allowed = dvmCheckFieldAccess(referrer, (Field*)resField);
 519     untweakLoader(referrer, resField->field.clazz);
 520     if (!allowed) {
 521         LOGI("DexOpt: access denied from %s to field %s.%s\n",
 522             referrer->descriptor, resField->field.clazz->descriptor,
 523             resField->field.name);
 524         if (pFailure != NULL)
 525             *pFailure = VERIFY_ERROR_ACCESS_FIELD;
 526         return NULL;
 527     }
 528
 529     return resField;
 530 }
 531
 532 /*
 533  * Alternate version of dvmResolveStaticField().
 534  *
 535  * Does not force initialization of the resolved field's class.
 536  *
 537  * On failure, returns NULL, and sets *pFailure if pFailure is not NULL.
 538  */
 539 StaticField* dvmOptResolveStaticField(ClassObject* referrer, u4 sfieldIdx,
 540     VerifyError* pFailure)
 541 {
 542     DvmDex* pDvmDex = referrer->pDvmDex;
 543     StaticField* resField;
 544
 545     resField = (StaticField*)dvmDexGetResolvedField(pDvmDex, sfieldIdx);
 546     if (resField == NULL) {
 547         const DexFieldId* pFieldId;
 548         ClassObject* resClass;
 549
 550         pFieldId = dexGetFieldId(pDvmDex->pDexFile, sfieldIdx);
 551
 552         /*
 553          * Find the field's class.
 554          */
 555         resClass = dvmOptResolveClass(referrer, pFieldId->classIdx, pFailure);
 556         if (resClass == NULL) {
 557             //dvmClearOptException(dvmThreadSelf());
 558             assert(!dvmCheckException(dvmThreadSelf()));
 559             if (pFailure != NULL) { assert(!VERIFY_OK(*pFailure)); }
 560             return NULL;
 561         }
 562
 563         resField = (StaticField*)dvmFindFieldHier(resClass,
 564                     dexStringById(pDvmDex->pDexFile, pFieldId->nameIdx),
 565                     dexStringByTypeIdx(pDvmDex->pDexFile, pFieldId->typeIdx));
 566         if (resField == NULL) {
 567             LOGD("DexOpt: couldn't find static field\n");
 568             if (pFailure != NULL)
 569                 *pFailure = VERIFY_ERROR_NO_FIELD;
 570             return NULL;
 571         }
 572         if (!dvmIsStaticField(&resField->field)) {
 573             LOGD("DexOpt: wanted static, got instance for field %s.%s\n",
 574                 resClass->descriptor,
 575                 dexStringById(pDvmDex->pDexFile, pFieldId->nameIdx));
 576             if (pFailure != NULL)
 577                 *pFailure = VERIFY_ERROR_CLASS_CHANGE;
 578             return NULL;
 579         }
 580
 581         /*
 582          * Add it to the resolved table so we're faster on the next lookup.
 583          *
 584          * We can only do this if we're in "dexopt", because the presence
 585          * of a valid value in the resolution table implies that the class
 586          * containing the static field has been initialized.
 587          */
 588         if (gDvm.optimizing)
 589             dvmDexSetResolvedField(pDvmDex, sfieldIdx, (Field*) resField);
 590     }
 591
 592     /* access allowed? */
 593     tweakLoader(referrer, resField->field.clazz);
 594     bool allowed = dvmCheckFieldAccess(referrer, (Field*)resField);
 595     untweakLoader(referrer, resField->field.clazz);
 596     if (!allowed) {
 597         LOGI("DexOpt: access denied from %s to field %s.%s\n",
 598             referrer->descriptor, resField->field.clazz->descriptor,
 599             resField->field.name);
 600         if (pFailure != NULL)
 601             *pFailure = VERIFY_ERROR_ACCESS_FIELD;
 602         return NULL;
 603     }
 604
 605     return resField;
 606 }
 607
 608
 609 /*
 610  * Rewrite an iget/iput instruction.  These all have the form:
 611  *   op vA, vB, field@CCCC
 612  *
 613  * Where vA holds the value, vB holds the object reference, and CCCC is
 614  * the field reference constant pool offset.  For a non-volatile field,
 615  * we want to replace the opcode with "quickOpc" and replace CCCC with
 616  * the byte offset from the start of the object.  For a volatile field,
 617  * we just want to replace the opcode with "volatileOpc".
 618  *
 619  * If "volatileOpc" is OP_NOP we don't check to see if it's a volatile
 620  * field.  If "quickOpc" is OP_NOP, and this is a non-volatile field,
 621  * we don't do anything.
 622  *
 623  * "method" is the referring method.
 624  */
 625 static bool rewriteInstField(Method* method, u2* insns, OpCode quickOpc,
 626     OpCode volatileOpc)
 627 {
 628     ClassObject* clazz = method->clazz;
 629     u2 fieldIdx = insns[1];
 630     InstField* instField;
 631
 632     instField = dvmOptResolveInstField(clazz, fieldIdx, NULL);
 633     if (instField == NULL) {
 634         LOGI("DexOpt: unable to optimize instance field ref "
 635              "0x%04x at 0x%02x in %s.%s\n",
 636             fieldIdx, (int) (insns - method->insns), clazz->descriptor,
 637             method->name);
 638         return false;
 639     }
 640
 641     if (instField->byteOffset >= 65536) {
 642         LOGI("DexOpt: field offset exceeds 64K (%d)\n", instField->byteOffset);
 643         return false;
 644     }
 645
 646     if (volatileOpc != OP_NOP && dvmIsVolatileField(&instField->field)) {
 647         updateCode(method, insns, (insns[0] & 0xff00) | (u2) volatileOpc);
 648         LOGV("DexOpt: rewrote ifield access %s.%s --> volatile\n",
 649             instField->field.clazz->descriptor, instField->field.name);
 650     } else if (quickOpc != OP_NOP) {
 651         updateCode(method, insns, (insns[0] & 0xff00) | (u2) quickOpc);
 652         updateCode(method, insns+1, (u2) instField->byteOffset);
 653         LOGV("DexOpt: rewrote ifield access %s.%s --> %d\n",
 654             instField->field.clazz->descriptor, instField->field.name,
 655             instField->byteOffset);
 656     } else {
 657         LOGV("DexOpt: no rewrite of ifield access %s.%s\n",
 658             instField->field.clazz->descriptor, instField->field.name);
 659     }
 660
 661     return true;
 662 }
 663
 664 /*
 665  * Rewrite an sget/sput instruction.  These all have the form:
 666  *   op vAA, field@BBBB
 667  *
 668  * Where vAA holds the value, and BBBB is the field reference constant
 669  * pool offset.  There is no "quick" form of static field accesses, so
 670  * this is only useful for volatile fields.
 671  *
 672  * "method" is the referring method.
 673  */
 674 static bool rewriteStaticField(Method* method, u2* insns, OpCode volatileOpc)
 675 {
 676     ClassObject* clazz = method->clazz;
 677     u2 fieldIdx = insns[1];
 678     StaticField* staticField;
 679
 680     assert(volatileOpc != OP_NOP);
 681
 682     staticField = dvmOptResolveStaticField(clazz, fieldIdx, NULL);
 683     if (staticField == NULL) {
 684         LOGI("DexOpt: unable to optimize static field ref "
 685              "0x%04x at 0x%02x in %s.%s\n",
 686             fieldIdx, (int) (insns - method->insns), clazz->descriptor,
 687             method->name);
 688         return false;
 689     }
 690
 691     if (dvmIsVolatileField(&staticField->field)) {
 692         updateCode(method, insns, (insns[0] & 0xff00) | (u2) volatileOpc);
 693         LOGV("DexOpt: rewrote sfield access %s.%s --> volatile\n",
 694             staticField->field.clazz->descriptor, staticField->field.name);
 695     }
 696
 697     return true;
 698 }
 699
 700 /*
 701  * Alternate version of dvmResolveMethod().
 702  *
 703  * Doesn't throw exceptions, and checks access on every lookup.
 704  *
 705  * On failure, returns NULL, and sets *pFailure if pFailure is not NULL.
 706  */
 707 Method* dvmOptResolveMethod(ClassObject* referrer, u4 methodIdx,
 708     MethodType methodType, VerifyError* pFailure)
 709 {
 710     DvmDex* pDvmDex = referrer->pDvmDex;
 711     Method* resMethod;
 712
 713     assert(methodType == METHOD_DIRECT ||
 714            methodType == METHOD_VIRTUAL ||
 715            methodType == METHOD_STATIC);
 716
 717     LOGVV("--- resolving method %u (referrer=%s)\n", methodIdx,
 718         referrer->descriptor);
 719
 720     resMethod = dvmDexGetResolvedMethod(pDvmDex, methodIdx);
 721     if (resMethod == NULL) {
 722         const DexMethodId* pMethodId;
 723         ClassObject* resClass;
 724
 725         pMethodId = dexGetMethodId(pDvmDex->pDexFile, methodIdx);
 726
 727         resClass = dvmOptResolveClass(referrer, pMethodId->classIdx, pFailure);
 728         if (resClass == NULL) {
 729             /*
 730              * Can't find the class that the method is a part of, or don't
 731              * have permission to access the class.
 732              */
 733             LOGV("DexOpt: can't find called method's class (?.%s)\n",
 734                 dexStringById(pDvmDex->pDexFile, pMethodId->nameIdx));
 735             if (pFailure != NULL) { assert(!VERIFY_OK(*pFailure)); }
 736             return NULL;
 737         }
 738         if (dvmIsInterfaceClass(resClass)) {
 739             /* method is part of an interface; this is wrong method for that */
 740             LOGW("DexOpt: method is in an interface\n");
 741             if (pFailure != NULL)
 742                 *pFailure = VERIFY_ERROR_GENERIC;
 743             return NULL;
 744         }
 745
 746         /*
 747          * We need to chase up the class hierarchy to find methods defined
 748          * in super-classes.  (We only want to check the current class
 749          * if we're looking for a constructor.)
 750          */
 751         DexProto proto;
 752         dexProtoSetFromMethodId(&proto, pDvmDex->pDexFile, pMethodId);
 753
 754         if (methodType == METHOD_DIRECT) {
 755             resMethod = dvmFindDirectMethod(resClass,
 756                 dexStringById(pDvmDex->pDexFile, pMethodId->nameIdx), &proto);
 757         } else {
 758             /* METHOD_STATIC or METHOD_VIRTUAL */
 759             resMethod = dvmFindMethodHier(resClass,
 760                 dexStringById(pDvmDex->pDexFile, pMethodId->nameIdx), &proto);
 761         }
 762
 763         if (resMethod == NULL) {
 764             LOGV("DexOpt: couldn't find method '%s'\n",
 765                 dexStringById(pDvmDex->pDexFile, pMethodId->nameIdx));
 766             if (pFailure != NULL)
 767                 *pFailure = VERIFY_ERROR_NO_METHOD;
 768             return NULL;
 769         }
 770         if (methodType == METHOD_STATIC) {
 771             if (!dvmIsStaticMethod(resMethod)) {
 772                 LOGD("DexOpt: wanted static, got instance for method %s.%s\n",
 773                     resClass->descriptor, resMethod->name);
 774                 if (pFailure != NULL)
 775                     *pFailure = VERIFY_ERROR_CLASS_CHANGE;
 776                 return NULL;
 777             }
 778         } else if (methodType == METHOD_VIRTUAL) {
 779             if (dvmIsStaticMethod(resMethod)) {
 780                 LOGD("DexOpt: wanted instance, got static for method %s.%s\n",
 781                     resClass->descriptor, resMethod->name);
 782                 if (pFailure != NULL)
 783                     *pFailure = VERIFY_ERROR_CLASS_CHANGE;
 784                 return NULL;
 785             }
 786         }
 787
 788         /* see if this is a pure-abstract method */
 789         if (dvmIsAbstractMethod(resMethod) && !dvmIsAbstractClass(resClass)) {
 790             LOGW("DexOpt: pure-abstract method '%s' in %s\n",
 791                 dexStringById(pDvmDex->pDexFile, pMethodId->nameIdx),
 792                 resClass->descriptor);
 793             if (pFailure != NULL)
 794                 *pFailure = VERIFY_ERROR_GENERIC;
 795             return NULL;
 796         }
 797
 798         /*
 799          * Add it to the resolved table so we're faster on the next lookup.
 800          *
 801          * We can only do this for static methods if we're not in "dexopt",
 802          * because the presence of a valid value in the resolution table
 803          * implies that the class containing the static field has been
 804          * initialized.
 805          */
 806         if (methodType != METHOD_STATIC || gDvm.optimizing)
 807             dvmDexSetResolvedMethod(pDvmDex, methodIdx, resMethod);
 808     }
 809
 810     LOGVV("--- found method %d (%s.%s)\n",
 811         methodIdx, resMethod->clazz->descriptor, resMethod->name);
 812
 813     /* access allowed? */
 814     tweakLoader(referrer, resMethod->clazz);
 815     bool allowed = dvmCheckMethodAccess(referrer, resMethod);
 816     untweakLoader(referrer, resMethod->clazz);
 817     if (!allowed) {
 818         IF_LOGI() {
 819             char* desc = dexProtoCopyMethodDescriptor(&resMethod->prototype);
 820             LOGI("DexOpt: illegal method access (call %s.%s %s from %s)\n",
 821                 resMethod->clazz->descriptor, resMethod->name, desc,
 822                 referrer->descriptor);
 823             free(desc);
 824         }
 825         if (pFailure != NULL)
 826             *pFailure = VERIFY_ERROR_ACCESS_METHOD;
 827         return NULL;
 828     }
 829
 830     return resMethod;
 831 }
 832
 833 /*
 834  * Rewrite invoke-virtual, invoke-virtual/range, invoke-super, and
 835  * invoke-super/range.  These all have the form:
 836  *   op vAA, meth@BBBB, reg stuff @CCCC
 837  *
 838  * We want to replace the method constant pool index BBBB with the
 839  * vtable index.
 840  */
 841 static bool rewriteVirtualInvoke(Method* method, u2* insns, OpCode newOpc)
 842 {
 843     ClassObject* clazz = method->clazz;
 844     Method* baseMethod;
 845     u2 methodIdx = insns[1];
 846
 847     baseMethod = dvmOptResolveMethod(clazz, methodIdx, METHOD_VIRTUAL, NULL);
 848     if (baseMethod == NULL) {
 849         LOGD("DexOpt: unable to optimize virt call 0x%04x at 0x%02x in %s.%s\n",
 850             methodIdx,
 851             (int) (insns - method->insns), clazz->descriptor,
 852             method->name);
 853         return false;
 854     }
 855
 856     assert((insns[0] & 0xff) == OP_INVOKE_VIRTUAL ||
 857            (insns[0] & 0xff) == OP_INVOKE_VIRTUAL_RANGE ||
 858            (insns[0] & 0xff) == OP_INVOKE_SUPER ||
 859            (insns[0] & 0xff) == OP_INVOKE_SUPER_RANGE);
 860
 861     /*
 862      * Note: Method->methodIndex is a u2 and is range checked during the
 863      * initial load.
 864      */
 865     updateCode(method, insns, (insns[0] & 0xff00) | (u2) newOpc);
 866     updateCode(method, insns+1, baseMethod->methodIndex);
 867
 868     //LOGI("DexOpt: rewrote call to %s.%s --> %s.%s\n",
 869     //    method->clazz->descriptor, method->name,
 870     //    baseMethod->clazz->descriptor, baseMethod->name);
 871
 872     return true;
 873 }
 874
 875 /*
 876  * Rewrite invoke-direct, which has the form:
 877  *   op vAA, meth@BBBB, reg stuff @CCCC
 878  *
 879  * There isn't a lot we can do to make this faster, but in some situations
 880  * we can make it go away entirely.
 881  *
 882  * This must only be used when the invoked method does nothing and has
 883  * no return value (the latter being very important for verification).
 884  */
 885 static bool rewriteEmptyDirectInvoke(Method* method, u2* insns)
 886 {
 887     ClassObject* clazz = method->clazz;
 888     Method* calledMethod;
 889     u2 methodIdx = insns[1];
 890
 891     calledMethod = dvmOptResolveMethod(clazz, methodIdx, METHOD_DIRECT, NULL);
 892     if (calledMethod == NULL) {
 893         LOGD("DexOpt: unable to opt direct call 0x%04x at 0x%02x in %s.%s\n",
 894             methodIdx,
 895             (int) (insns - method->insns), clazz->descriptor,
 896             method->name);
 897         return false;
 898     }
 899
 900     /* TODO: verify that java.lang.Object() is actually empty! */
 901     if (calledMethod->clazz == gDvm.classJavaLangObject &&
 902         dvmCompareNameDescriptorAndMethod("<init>", "()V", calledMethod) == 0)
 903     {
 904         /*
 905          * Replace with "empty" instruction.  DO NOT disturb anything
 906          * else about it, as we want it to function the same as
 907          * OP_INVOKE_DIRECT when debugging is enabled.
 908          */
 909         assert((insns[0] & 0xff) == OP_INVOKE_DIRECT);
 910         updateCode(method, insns,
 911             (insns[0] & 0xff00) | (u2) OP_INVOKE_DIRECT_EMPTY);
 912
 913         //LOGI("DexOpt: marked-empty call to %s.%s --> %s.%s\n",
 914         //    method->clazz->descriptor, method->name,
 915         //    calledMethod->clazz->descriptor, calledMethod->name);
 916     }
 917
 918     return true;
 919 }
 920
 921 /*
 922  * Resolve an interface method reference.
 923  *
 924  * No method access check here -- interface methods are always public.
 925  *
 926  * Returns NULL if the method was not found.  Does not throw an exception.
 927  */
 928 Method* dvmOptResolveInterfaceMethod(ClassObject* referrer, u4 methodIdx)
 929 {
 930     DvmDex* pDvmDex = referrer->pDvmDex;
 931     Method* resMethod;
 932     int i;
 933
 934     LOGVV("--- resolving interface method %d (referrer=%s)\n",
 935         methodIdx, referrer->descriptor);
 936
 937     resMethod = dvmDexGetResolvedMethod(pDvmDex, methodIdx);
 938     if (resMethod == NULL) {
 939         const DexMethodId* pMethodId;
 940         ClassObject* resClass;
 941
 942         pMethodId = dexGetMethodId(pDvmDex->pDexFile, methodIdx);
 943
 944         resClass = dvmOptResolveClass(referrer, pMethodId->classIdx, NULL);
 945         if (resClass == NULL) {
 946             /* can't find the class that the method is a part of */
 947             dvmClearOptException(dvmThreadSelf());
 948             return NULL;
 949         }
 950         if (!dvmIsInterfaceClass(resClass)) {
 951             /* whoops */
 952             LOGI("Interface method not part of interface class\n");
 953             return NULL;
 954         }
 955
 956         const char* methodName =
 957             dexStringById(pDvmDex->pDexFile, pMethodId->nameIdx);
 958         DexProto proto;
 959         dexProtoSetFromMethodId(&proto, pDvmDex->pDexFile, pMethodId);
 960
 961         LOGVV("+++ looking for '%s' '%s' in resClass='%s'\n",
 962             methodName, methodSig, resClass->descriptor);
 963         resMethod = dvmFindVirtualMethod(resClass, methodName, &proto);
 964         if (resMethod == NULL) {
 965             /* scan superinterfaces and superclass interfaces */
 966             LOGVV("+++ did not resolve immediately\n");
 967             for (i = 0; i < resClass->iftableCount; i++) {
 968                 resMethod = dvmFindVirtualMethod(resClass->iftable[i].clazz,
 969                                 methodName, &proto);
 970                 if (resMethod != NULL)
 971                     break;
 972             }
 973
 974             if (resMethod == NULL) {
 975                 LOGVV("+++ unable to resolve method %s\n", methodName);
 976                 return NULL;
 977             }
 978         } else {
 979             LOGVV("+++ resolved immediately: %s (%s %d)\n", resMethod->name,
 980                 resMethod->clazz->descriptor, (u4) resMethod->methodIndex);
 981         }
 982
 983         /* we're expecting this to be abstract */
 984         if (!dvmIsAbstractMethod(resMethod)) {
 985             char* desc = dexProtoCopyMethodDescriptor(&resMethod->prototype);
 986             LOGW("Found non-abstract interface method %s.%s %s\n",
 987                 resMethod->clazz->descriptor, resMethod->name, desc);
 988             free(desc);
 989             return NULL;
 990         }
 991
 992         /*
 993          * Add it to the resolved table so we're faster on the next lookup.
 994          */
 995         dvmDexSetResolvedMethod(pDvmDex, methodIdx, resMethod);
 996     }
 997
 998     LOGVV("--- found interface method %d (%s.%s)\n",
 999         methodIdx, resMethod->clazz->descriptor, resMethod->name);
1000
1001     /* interface methods are always public; no need to check access */
1002
1003     return resMethod;
1004 }
1005
1006 /*
1007  * See if the method being called can be rewritten as an inline operation.
1008  * Works for invoke-virtual, invoke-direct, and invoke-static.
1009  *
1010  * Returns "true" if we replace it.
1011  */
1012 static bool rewriteExecuteInline(Method* method, u2* insns,
1013     MethodType methodType)
1014 {
1015     const InlineSub* inlineSubs = gDvm.inlineSubs;
1016     ClassObject* clazz = method->clazz;
1017     Method* calledMethod;
1018     u2 methodIdx = insns[1];
1019
1020     //return false;
1021
1022     calledMethod = dvmOptResolveMethod(clazz, methodIdx, methodType, NULL);
1023     if (calledMethod == NULL) {
1024         LOGV("+++ DexOpt inline: can't find %d\n", methodIdx);
1025         return false;
1026     }
1027
1028     while (inlineSubs->method != NULL) {
1029         /*
1030         if (extra) {
1031             LOGI("comparing %p vs %p %s.%s %s\n",
1032                 inlineSubs->method, calledMethod,
1033                 inlineSubs->method->clazz->descriptor,
1034                 inlineSubs->method->name,
1035                 inlineSubs->method->signature);
1036         }
1037         */
1038         if (inlineSubs->method == calledMethod) {
1039             assert((insns[0] & 0xff) == OP_INVOKE_DIRECT ||
1040                    (insns[0] & 0xff) == OP_INVOKE_STATIC ||
1041                    (insns[0] & 0xff) == OP_INVOKE_VIRTUAL);
1042             updateCode(method, insns,
1043                 (insns[0] & 0xff00) | (u2) OP_EXECUTE_INLINE);
1044             updateCode(method, insns+1, (u2) inlineSubs->inlineIdx);
1045
1046             //LOGI("DexOpt: execute-inline %s.%s --> %s.%s\n",
1047             //    method->clazz->descriptor, method->name,
1048             //    calledMethod->clazz->descriptor, calledMethod->name);
1049             return true;
1050         }
1051
1052         inlineSubs++;
1053     }
1054
1055     return false;
1056 }
1057
1058 /*
1059  * See if the method being called can be rewritten as an inline operation.
1060  * Works for invoke-virtual/range, invoke-direct/range, and invoke-static/range.
1061  *
1062  * Returns "true" if we replace it.
1063  */
1064 static bool rewriteExecuteInlineRange(Method* method, u2* insns,
1065     MethodType methodType)
1066 {
1067     const InlineSub* inlineSubs = gDvm.inlineSubs;
1068     ClassObject* clazz = method->clazz;
1069     Method* calledMethod;
1070     u2 methodIdx = insns[1];
1071
1072     calledMethod = dvmOptResolveMethod(clazz, methodIdx, methodType, NULL);
1073     if (calledMethod == NULL) {
1074         LOGV("+++ DexOpt inline/range: can't find %d\n", methodIdx);
1075         return false;
1076     }
1077
1078     while (inlineSubs->method != NULL) {
1079         if (inlineSubs->method == calledMethod) {
1080             assert((insns[0] & 0xff) == OP_INVOKE_DIRECT_RANGE ||
1081                    (insns[0] & 0xff) == OP_INVOKE_STATIC_RANGE ||
1082                    (insns[0] & 0xff) == OP_INVOKE_VIRTUAL_RANGE);
1083             updateCode(method, insns,
1084                 (insns[0] & 0xff00) | (u2) OP_EXECUTE_INLINE_RANGE);
1085             updateCode(method, insns+1, (u2) inlineSubs->inlineIdx);
1086
1087             //LOGI("DexOpt: execute-inline/range %s.%s --> %s.%s\n",
1088             //    method->clazz->descriptor, method->name,
1089             //    calledMethod->clazz->descriptor, calledMethod->name);
1090             return true;
1091         }
1092
1093         inlineSubs++;
1094     }
1095
1096     return false;
1097 }