vm/analysis/Optimize.cpp

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