Added polynomial induction variables analysis. With tests.

Rationale:
Information on polynomial sequences is nice to further enhance
BCE and last-value assignment. In this case, this CL enables more
loop optimizations for benchpress' Sum (80 x speedup). Also
changed rem-based geometric induction to wrap-around induction.

Test: test-art-host

Change-Id: Ie4d2659edefb814edda2c971c1f70ba400c31111

Merge "Added geometric induction variables analysis."

Merge "Revert "Re-enable libcore test WeakHashMapTest#test_keySet.""

Merge "Fix two tests after vdex change."

Fix two tests after vdex change.

- Clear entries of verification results, to avoid hitting a
  DCHECK while running verifier_deps_test
- Backlist 629-vdex-speed for relocate-npatchoat, as the test
  needs compiled code.

test: verifier_deps_test, 629-vdex-speed
bug: 30937355
Change-Id: I9788599dafcbfe63522c58f85692601466d191db

Merge "Mterp/arm: Add CFI directives."

Revert "Re-enable libcore test WeakHashMapTest#test_keySet."

This reverts commit d3a36fd9d99857da60777ddcf3b10058402e0915.

Reverting as the test still fails on the ART Buildbot.

Bug: 25437292
Change-Id: Id8bf59bac2d81554d5a50757ce25255ec99155ec

Merge "Update Jack options to enable invoke-polymorphic"

Merge "ARM: VIXL32: Clean usage of scopes."

Merge "ARM: VIXL32: Implement Invoke, LoadClass, LoadString dispatch."

Merge "Create empty VerifiedMethod after vdex verification."

Added geometric induction variables analysis.

Rationale:
Information on geometric and polynomial (coming soon) sequences
are nice to have to further enhance BCE and last-value assignment.

Test: test-art-host
Change-Id: Ib5e2998c3eb1009def6fd00b82935da7c3ba7c6e

Merge "Address comments I missed on a previous CL"

Merge "Dump more debug info for b/33006388."

Merge "ART: Clean up Thread"

Address comments I missed on a previous CL

I accidentally missed some comments on
android-review.googlesource.com/c/305518 when I submitted it. This
addresses those comments.

Test: mma -j40 test-art-host
Change-Id: Icd8ff65dee1730d10489f25e75bddbd455c68413

Mterp/arm: Add CFI directives.

Includes reworking of float_to_long and double_to_long to
elminate frame (as suggested by vmarko).

Test: m ART_TEST_INTERPRETER=true test-art-target (in progress)
Bug: 31456348
Change-Id: Ic4e985b977f76c4df926559b187d92d969206514

Merge "ART: Weaken boot classpath initialization check"

ARM: VIXL32: Clean usage of scopes.

Use scopes in more places where they are semantically required.
There are still places where we should use scopes, but do not yet.
Those are marked with new `TODO` comments. Practically everything
works fine (see comments for details), but we eventually should fix
it.

Test: ART_USE_VIXL_ARM_BACKEND=true m test-art-host
Test: ART_USE_VIXL_ARM_BACKEND=true m test-art-target

Change-Id: I5bdc710d32f0b9476eee92b31f2ff9d874e26f63

Create empty VerifiedMethod after vdex verification.

The compiler and quicken require the existence of a
VerifiedMethod for compiling a method.

This fixes the regression of not doing any compilation when
passed --input-vdex.

Test: 629-vdex-speed

Change-Id: Ie65578eadd09099df1c1a403d96c15e5da78a901

ARM: VIXL32: Implement Invoke, LoadClass, LoadString dispatch.

Implemented dispatch optimizations for InvokeStaticOrDirect,
LoadClass, LoadString (excluding cases that use Literals).
Performed a cleanup of VIXL backend.

Test: export ART_USE_VIXL_ARM_BACKEND=true && \
      mma test-art-host dist && mma test-art-target dist

Change-Id: Ib37a6b7e7657196b13caec999d190be747857c1d

Merge "Re-enable libcore test WeakHashMapTest#test_keySet."

Merge "Don't use an internal timeout, rely on the test harness one."

Merge "Set the root table size when allocating."

Merge "Set the location checksum in vdex."

Set the root table size when allocating.

In order to deallocate it at any point.

test: ART_TEST_JIT=true m test-art-host-run-test-jit
Change-Id: I36574fd1a34c9d67800a164fa801db7a17c827bf

Don't use an internal timeout, rely on the test harness one.

test: 522-checker-regression-monitor-exit
Change-Id: Ida2ebd609f2902908476f1061459838f0c181f1a

Merge "Disable test 080 for GSS"

Disable test 080 for GSS

Failing due to space sizing.

Test: test-art-host-run-test ART_DEFAULT_GC_TYPE=GSS ART_USE_TLAB=true ART_TEST_OPTIMIZING=true ART_TEST_INTERPRETER=true ART_TEST_JIT=true ART_USE_READ_BARRIER=false

Change-Id: I7a899395b547f3c49b7edba3500e18674aecda24

Merge "Cleanup of redefinition testing"

Dump more debug info for b/33006388.

Bug: 33006388
Bug: 12687968
Test: test-art-host with CC.
Change-Id: Id9d67bc603c6ff7bc8e346e181e3e09ffbda43b3

ART: Clean up Thread

Move debug code to .cc, simplify includes.

Test: m test-art-host
Change-Id: I5e66a54223a8f965a46fb14021d0e29aa2496ed1

Merge "ART: Clean up ClassLinker"

Merge "Add more detail to rosalloc fragmentation OOME"

Cleanup of redefinition testing

Move redefine logic into a single common function and perform some
other cleanup.

Test: mma -j40 test-art-host
Change-Id: I8618bda4f392b683ce198374066e356b87578e7b

ART: Clean up ClassLinker

Try to clean up and simplify ClassLinker.

Move dex_lock to Locks. Remove dead code. Move single-use
code to user. Hide implementation details from header.

Test: m test-art-host
Change-Id: I58150fa9c2a9524f8304370270c2197d655cb3a8

Add more detail to rosalloc fragmentation OOME

Also include total number of free page bytes, space footprint, and
space max capacity.

Sample output:
Throwing OutOfMemoryError "Failed to allocate a 7012 byte allocation
with 103464 free bytes and 101KB until OOM; failed due to
fragmentation (required continguous free 8192 bytes, largest
contiguous free 4096 bytes, total free pages 4096 bytes, space
footprint 268435456 bytes, space max capacity 268435456 bytes)

Added a basic test to ensure the allocator coalesces properly.

Bug: 32997082

Test: test-art-host

Change-Id: I642b6ad34b98f6d98c10f242a6f6e926e0b42acc

Merge "ART: Fix typo in IsCallerSave"

ART: Fix typo in IsCallerSave

Correctly refer to floating point registers, if necessary. This
ensures that we correctly start allocating caller-save FPRs.

Bug: 31275200
Test: ART_TEST_OPTIMIZING_GRAPH_COLOR=true m test-art-host
Change-Id: I420b66f0a000636e8370c739003de3cf53af3e30

Merge "ART: Delete unnecessary ScopedObjectAccess"

Merge "ART: Add verifier support for invoke-polymorphic."

ART: Add verifier support for invoke-polymorphic.

Change-Id: I1e1860cad80db46320c3ef5a9eaceb7529ea68d7
Bug: 30550796,33099829,33191712
Test: make test-art-host

ART: Delete unnecessary ScopedObjectAccess

This isn't protecting or serializing anything. Reduces
dex2oatd compile time.

Test: m test-art-host
Change-Id: I8e6d1579578740b526070ba784b81bd0590e84b1

Merge "Fix PACKED for jvalue"

Merge "Class Hierarchy Analysis (CHA)"

Fix PACKED for jvalue

Make it only as packed as alignof(mirror::Object*).

Bug: 31532493

Test: mm test-art-host

Change-Id: I242c549bcc9203d3173f204264b0dc2f2f8e3441

Merge "ART: Cache sections for sanity check"

Set the location checksum in vdex.

The checksum we check against at runtime isn't the dex checksum
if we are compiling a jar/apk, but the crc32 of the entry.

This is to optimize the check at startup and avoid reading the
contents of the zip file.

Because with vdex we do not want to open the zip file, (the test
has been done already in getDexOptNeeded), and cannot rely
on the .oat file for fetching it, put the location checksum in
the vdex directly.

Note for later refactorings: the dex checksum location is now
in the vdex file, but also in the oat file. This can be revisited
after we eventually cleanup OatDexFile.

Test: 629-vdex
bug: 30937355
Change-Id: I7af8ca63b889370c660d694dd4eb95e78f566a1c

Merge "Add LoadString kind of kJitTableAddress for dump-cfg."

ART: Cache sections for sanity check

Cache image sections for ArtMethod image sanity checks. Reduces
executed instructions in debug builds.

$ perf stat -e instructions:u -B dex2oatd ... HelloWorld.dex
Before: 36,024,262,237      instructions:u
After:  20,351,917,735      instructions:u

Test: m test-art-host
Change-Id: I96e5c04483cf40800f0f336a49d7d33e7b967f07

Class Hierarchy Analysis (CHA)

The class linker now tracks whether a method has a single implementation
and if so, the JIT compiler will try to devirtualize a virtual call for
the method into a direct call. If the single-implementation assumption
is violated due to additional class linking, compiled code that makes the
assumption is invalidated. Deoptimization is triggered for compiled code
live on stack. Instead of patching return pc's on stack, a CHA guard is
added which checks a hidden should_deoptimize flag for deoptimization.
This approach limits the number of deoptimization points.

This CL does not devirtualize abstract/interface method invocation.

Slides on CHA:
https://docs.google.com/a/google.com/presentation/d/1Ax6cabP1vM44aLOaJU3B26n5fTE9w5YU-1CRevIDsBc/edit?usp=sharing

Change-Id: I18bf716a601b6413b46312e925a6ad9e4008efa4
Test: ART_TEST_JIT=true m test-art-host/target-run-test test-art-host-gtest

Merge "Change Dex2oatLayoutTest to generate profile itself."

Merge "Revert "Make sure that const-class linkage is preserved, try again.""

Revert "Make sure that const-class linkage is preserved, try again."

Reverting due to test failures as expected.

Bug: 30627598
Bug: 33231647

This reverts commit cb5ab35980a86b05586c402924d2e7ca9df25758.
Squashed revert "Additional debug logging for bug 33231647."
    This reverts commit 00a441033db28d243fc33692d30eb2755fa81728.

Change-Id: I0c0ee1f70d47540fec99f8a797ce13571c16147c

ART: Weaken boot classpath initialization check

Only abort in debug builds. Warn in non-debug mode.

Bug: 33265291
Test: m test-art-host
Change-Id: I288303cd7790a8b796f8b0717170861ea65e1f8c

Merge "Additional debug logging for bug 33231647."

Additional debug logging for bug 33231647.

Bug: 33231647
Test: m test-art-host
Change-Id: I5847ce92be5f588852e04ff44fe6eca19f363b93

Merge "Mterp/arm64: Add CFI directives."

Mterp/arm64: Add CFI directives.

Also add two bug 31975598 workarounds to arm64 entrypoints.

Test: m ART_TEST_INTERPRETER=true test-art-target
Bug: 31456348
Bug: 31975598
Change-Id: Ibf64160cf3b3f1ef644ff8f051ab7dc89643acf3

Merge "Make sure that const-class linkage is preserved, try again."

Make sure that const-class linkage is preserved, try again.

This CL causes occasional test failures on the build servers
which we were not able to reproduce locally. So we add some
some additional debug output to help pinpoint the cause.

Bug: 30627598
Bug: 33231647
Test: m test-art-host

This reverts commit 171cf811a1cdf8b1cbc5151505d8630741ce4cf3.

Change-Id: Id56a3f0e86e8212fd547e09c61794401bff47fb0

Update Jack options to enable invoke-polymorphic

Test: m -j32 test-art-host

(cherry picked from commit 39f502e67b9c6ac7e31e079ecbdf4252765a71bd)

Change-Id: I756006ed1b8f77b8f50508fe1db0a97a652ce208

Merge "ARM: VIXL32: A couple of fixes to have more tests passing."

Merge "Remove the fast path in art_quick_resolve_string."

Merge "Move compiled methods to use AtomicMethodRefMap"

Merge "Optimizations around escape analysis. With tests."

Merge "Infrastructure for obsolete methods"

Add LoadString kind of kJitTableAddress for dump-cfg.

Test: manual

Change-Id: Ifcae7b26f666930766635d8b3ed7a495494cddf7

Optimizations around escape analysis. With tests.

Details:
(1) added new intrinsics
(2) implemented optimizations
      more !can be null information
      more null check removals
      replace return-this uses with incoming parameter
      remove dead StringBuffer/Builder calls (with escape analysis)
(3) Fixed exposed bug in CanBeMoved()

Performance gain:
This improves CafeineString by about 360%
(removes null check from first loop, eliminates second loop completely)

Test: test-art-host

Change-Id: Iaf16a1b9cab6a7386f43d71c6b51dd59600e81c1

Move compiled methods to use AtomicMethodRefMap

Use AtomicMethodRefMap to avoid locking and map costs.

Native RAM usage for interpret-only compile FB:
71270192B -> 64117168B

Perf:
CompilerDriver::GetCompiledMethod: 0.88% -> 0.04%
Mutex::ExclusiveLock: 1.55% -> 1.05%

Bug: 32641252

Test: test-art-host-run-test

Change-Id: I146e7bf2f3328b4fa84f2cc19d591f4da82dccfc

Merge "Revert "Revert CC related changes.""

Merge "Add release fence after copying object"

Merge "Add atomic method reference map"

Add atomic method reference map

Less RAM usage and faster than using a normal map with
MethodReference. Speed is faster by avoiding locking and tree
traversal. RAM usage is lower since the map usually had a value
for most method references.

Plan on using for marking methods for dex2dex, storing compiled
methods. Also use the new map for VerifiedMethods (refactoring).

Added test.

Bug: 32641252

Test: test-art-host-run-test

Change-Id: I46268031b8e0daf9be3597145cf6ecf579a039e2

Revert "Revert CC related changes."

Disable entrypoint switching in ResetQuickAllocEntryPointsForThread
instead of callers. Fixes bug where instrumentation would switch
to non CC entrypoints for non X86_64 architectures causing aborts.

Bug: 31018974

Test: test-art-host
Test: test/run-test 099

This reverts commit 96172e0172c5fca6e9a5ad4b857a24d8c7b064e5.

Change-Id: If206694ae35ff4446c6a8a97bfbcbf2dac35e3f9

Change Dex2oatLayoutTest to generate profile itself.

Changed from a pre-generated base64 profile. This makes the test work
even if the dex file differs due to Jack changes.

Bug: 33091768
Test: mm test-art-host-gtest-dex2oat_test

Change-Id: I22b8c20ae1ab57efe66684ba38f5c128e6c089fd

Infrastructure for obsolete methods

This adds some of the structures and functions needed to eventually
support obsolete methods. Specifically this adds the code to create
and iterate through the obsolete dex-cache maps of classes and
re-organizes the redefinition code to be more sensible and extensible.

Bug: 32369913
Test: ./test/run-test --host 902
Test: mma -j40 test-art-host

Change-Id: I93d60fa66e7512e8b059cdf42af8a56e93ef4bd7

Merge "ART: Add dex::StringIndex"

Add release fence after copying object

Try to ensure that the field CAS in ConcurrentCopying::Process will
never reorder before the object copy.

May fix a bug where null classes are seen.

Test: test-art-host CC

Bug: 33210571
Change-Id: I71ab937b7ca60c88c5f69698731edac6a8f2e91a

ARM: VIXL32: A couple of fixes to have more tests passing.

Fix 103-string-append, CheckCast visitor, stop interpretting
boot.oat, port Floating point compare optimization.

Test: ART_USE_VIXL_ARM_BACKEND=true m test-art-host
Test: ART_USE_VIXL_ARM_BACKEND=true m test-art-target
Change-Id: I7e06f9bc1ec60a850a8fc4ef7a344b9cfc736033

Merge "Do not call IsMarked on null."

Merge "ART: Remove duplicate StackVisitor method."

Do not call IsMarked on null.

The concurrent collector checks it.

Test: ART_TEST_JIT=true test-art-host-run-test-jit
Change-Id: I02c2462ce1d8f3092f0b2f52f8b6dede8ff4a339

Merge "ARM: VIXL32: Implement HClassTableGet Visitor."

Merge "ARM: VIXL32: Fix some test failures."

Merge "Don't call realpath on a file that may not exist."

Merge "Move inline caches GC handling in JitCodeCache."

Merge "Revert CC related changes."

Don't call realpath on a file that may not exist.

Otherwise realpath prints an error message.

bug: 25658944
Change-Id: I63145c3d955e088e53708d8c6add945e6eab6654

Revert CC related changes.

Revert: "X86_64: Add allocation entrypoint switching for CC is_marking"
Revert: "Fix mips build in InitEntryPoints"
Revert: "Fix mac build in ResetQuickAllocEntryPoints"

Test: test-art-target-run-test
Change-Id: If38d44edf8c5def5c4d8c9419e4af0cd8d3be724

Merge "Don't use ashmen when kIsTargetLinux is set."

Merge "Improve invalid object logging"

ART: Remove duplicate StackVisitor method.

Remove method that is the same as the older IsShadowFrame and only
used in tests.

Test: m ART_TEST_JIT=true ART_TEST_INTERPRETER=true test-art-host-run-test-454-get-vreg
Test: m ART_TEST_JIT=true ART_TEST_INTERPRETER=true test-art-host-run-test-457-regs
Test: m ART_TEST_JIT=true ART_TEST_INTERPRETER=true test-art-host-run-test-570-checker-osr
Change-Id: Id222d25d5345790b6c500ec8120880a3b9d79986

Merge "Added support for android root in dexfuzz."

Merge "Fix mips build in InitEntryPoints"

Fix mips build in InitEntryPoints

Added missing arg.

Test: Untested
Change-Id: I7bd25203eee92d0424f03ee9fdb9e7079d05d23c

Don't use ashmen when kIsTargetLinux is set.

Test: get JIT enabled when running ART.
Change-Id: Ic1c351601d8e85ba6597c3b400fa0094e070a56a

Merge "Fix mac build in ResetQuickAllocEntryPoints"

Fix mac build in ResetQuickAllocEntryPoints

Unused arg warning.

Test: None

Change-Id: I5b147b1a584b96ad5457c9fee36f3edb0498cecf

Merge "ARM: Fix JNI MacroAssembler after VIXL update."