summaryrefslogtreecommitdiff
path: root/compiler/optimizing/load_store_analysis.h
AgeCommit message (Collapse)Author
2021-06-03Reduce Partial LSE memory usage.Vladimir Marko
Instantiate ExecutionSubgraph only for partial singleton candidates (currently NewInstance, possibly NewArray in the future). This reduces "LSA" allocations. Reserve memory for PartialLoadStoreEliminationHelper members based on the number of partial singletons instead of the number of reference infos. This reduces "LSE" allocations. The peak scoped arena allocation for one compiled method is reduced from MEM: used: 97424004, allocated: 99006568, lost: 1115968 LSA 46015104 LSE 51408900 down to MEM: used: 17000744, allocated: 26713880, lost: 3332496 GVN 17000744 where the LSA+LSE memory use is lower than GVN use. (cherry picked from commit 5c824937bb82adbde857bc99cb03c769c9f68f7b) Test: m test-art-host-gtest Test: testrunner.py --host --optimizing Bug: 33650849 Merged-In: I323b9f144b258f0fab034794770971547ce94b59 Change-Id: If3fc9787fc0dc4a1a33dd5ca0f2dc972998c4da7
2021-05-24Fix ReplacementOrValue() for Partial LSE.Vladimir Marko
Also fix a bad DCHECK() in `FindSubstiute()` and fix the HeapLocationCollector::VisitPredicatedInstanceFieldGet() to use the correct input. (cherry picked from commit 06fb7fa55cca3210f38c92ac7cc7ad525ff30c83) Test: New tests in load_store_elimination_test. Test: m test-art-host-gtest Test: testrunner.py --host --optimizing Bug: 188188275 Merged-In: Ifdace5ddbe1777af2109189013c0557f226d9cc9 Change-Id: If95e67fa0d4e54e6b61f37208986a83bffb9d750
2021-05-13Fix array location aliasing checks in LSE.Vladimir Marko
Test: New tests in load_store_elimination_test. Test: New test in 539-checker-lse. Test: m test-art-host-gtest Test: testrunner.py --host --optimizing Bug: 187487955 Change-Id: Iff66d5406cf1b36c3bebbce1d48117f83bb50553
2021-01-25Revert^4 "Partial Load Store Elimination"Alex Light
This reverts commit 791df7a161ecfa28eb69862a4bc285282463b960. This unreverts commit fc1ce4e8be0d977e3d41699f5ec746d68f63c024. This unreverts commit b8686ce4c93eba7192ed7ef89e7ffd9f3aa6cd07. We incorrectly failed to include PredicatedInstanceFieldGet in a few conditions, including a DCHECK. This caused tests to fail under the read-barrier-table-lookup configuration. Reason for revert: Fixed 2 incorrect checks Bug: 67037140 Test: ./art/test/testrunner/run_build_test_target.py -j70 art-gtest-read-barrier-table-lookup Change-Id: I32b01b29fb32077fb5074e7c77a0226bd1fcaab4
2021-01-24Revert "Revert^2 "Partial Load Store Elimination""Nicolas Geoffray
This reverts commit fc1ce4e8be0d977e3d41699f5ec746d68f63c024. Bug: 67037140 Reason for revert: Fails read-barrier-table-lookup tests. Change-Id: I373867c728789bc14a4370b93a045481167d5f76
2021-01-22Revert^2 "Partial Load Store Elimination"Alex Light
This reverts commit 47ac53100303e7e864b7f6d65f17b23088ccf1d6. There was a bug in LSE where we would incorrectly record the shadow$_monitor_ field as not having a default initial value. This caused partial LSE to be unable to compile the Object.identityHashCode function, causing crashes. This issue was fixed in a parent CL. Also updated all Offsets in LSE_test to be outside of the object header regardless of configuration. Test: ./test.py --host Bug: 67037140 Reason for revert: Fixed issue with shadow$_monitor_ field and offsets Change-Id: I4fb2afff4d410da818db38ed833927dfc0f6be33
2021-01-22Revert "Partial Load Store Elimination"Nicolas Geoffray
This reverts commit b8686ce4c93eba7192ed7ef89e7ffd9f3aa6cd07. Bug: 67037140 Reason for revert: Fails a few tests. Change-Id: Icf0635bffbfbba93bf0a5b854a9582c418198136
2021-01-21Partial Load Store EliminationAlex Light
Add partial load-store elimination to the LSE pass. Partial LSE will move object allocations which only escape along certain execution paths closer to the escape point and allow more values to be eliminated. It does this by creating new predicated load and store instructions that are used when an object has only escaped some of the time. In cases where the object has not escaped a default value will be used. Test: ./test.py --host Test: ./test.py --target Bug: 67037140 Change-Id: Idde67eb59ec90de79747cde17b552eec05b58497
2020-11-18Revert^4 "Partial LSE analysis & store removal"Alex Light
We incorrectly handled merging unknowns in some situations. Specifically in cases where we are unable to materialize loop-phis we could end up with PureUnknowns which could end up hiding stores that need to be kept. In an unrelated issue we were incorrectly considering some values as escapes when live at the point of an invoke. Since SearchPhiPlaceholdersForKeptStores used a more precise notion of escapes we could end up removing stores without being able to replace the values. This reverts commit 2316b3a0779f3721a78681f5c70ed6624ecaebef. This unreverts commit b6837f0350ff66c13582b0e94178dd5ca283ff0a This reverts commit fe270426c8a2a69a8f669339e83b86fbf40e25a1. This unreverts commit bb6cda60e4418c0ab557ea4090e046bed8206763. Bug: 67037140 Bug: 173120044 Reason for revert: Fixed issue causing incorrect store elimination Test: ./test.py --host Test: Boot cuttlefish atest FrameworksServicesTests:com.android.server.job.BackgroundRestrictionsTest#testPowerWhiteList Change-Id: I2ebae9ccfaf5169d551c5019b547589d0fce1dc9
2020-11-14Revert^3 "Partial LSE analysis & store removal"Alex Light
This reverts commit b6837f0350ff66c13582b0e94178dd5ca283ff0a This unreverts commit fe270426c8a2a69a8f669339e83b86fbf40e25a1. This rereverts commit bb6cda60e4418c0ab557ea4090e046bed8206763. Bug: 67037140 Bug: 173120044 Reason for revert: Git-blame seems to point to the CL as cause of b/173120044. Revert during investigation. Change-Id: I46f557ce79c15f07f4e77aacded1926b192754c3
2020-11-13Revert^2 "Partial LSE analysis & store removal"Alex Light
A ScopedArenaAllocator in a single test was accidentally loaded using operator new which is not supported. This caused a memory leak. This reverts commit fe270426c8a2a69a8f669339e83b86fbf40e25a1. This unreverts commit bb6cda60e4418c0ab557ea4090e046bed8206763. Bug: 67037140 Reason for revert: Fixed memory leak in LoadStoreAnalysisTest.PartialEscape test case Test: SANITIZE_HOST=address ASAN_OPTIONS=detect_leaks=0 m test-art-host-gtest-dependencies Run art_compiler_tests Change-Id: I34fa2079df946ae54b8c91fa771a44d56438a719
2020-11-12Revert "Partial LSE analysis & store removal"Nicolas Geoffray
This reverts commit bb6cda60e4418c0ab557ea4090e046bed8206763. Bug: 67037140 Reason for revert: memory leak detected in the test. Change-Id: I81cc2f61494e96964d8be40389eddcd7c66c9266
2020-11-12Partial LSE analysis & store removalAlex Light
This is the first piece of partial LSE for art. This CL adds analysis tools needed to implement partial LSE. More immediately, it improves LSE so that it will remove stores that are provably non-observable based on the location they occur. For example: ``` Foo o = new Foo(); if (xyz) { check(foo); foo.x++; } else { foo.x = 12; } return foo.x; ``` The store of 12 can be removed because the only escape in this method is unreachable and was not executed by the point we reach the store. The main purpose of this CL is to add the analysis tools needed to implement partial Load-Store elimination. Namely it includes tracking of which blocks are escaping and the groups of blocks that we cannot remove allocations from. The actual impact of this change is incredibly minor, being triggered only once in a AOSP code. go/lem shows only minor effects to compile-time and no effect on the compiled code. See go/lem-allight-partial-lse-2 for numbers. Compile time shows an average of 1.4% regression (max regression is 7% with 0.2 noise). This CL adds a new 'reachability' concept to the HGraph. If this has been calculated it allows one to quickly query whether there is any execution path containing two blocks in a given order. This is used to define a notion of sections of graph from which the escape of some allocation is inevitable. Test: art_compiler_tests Test: treehugger Bug: 67037140 Change-Id: I0edc8d6b73f7dd329cb1ea7923080a0abe913ea6
2020-08-21Improved LSE: Replacing loads with Phis.Vladimir Marko
Create "Phi placeholders" for tracking heap values that can merge from different values and try to match existing Phis or create new Phis to replace loads. For Phi placeholders from loop headers we do not know whether they are fed by unknown values through back-edges when processing the loop header, so we delay processing loads that depend on them until we walked the entire graph. We then try to match them with existing instructions (when the location is unchanged in the loop) or Phis or create new Phis if needed. If we find a loop Phi placeholder fed with unknown value from a back-edge, we mark the Phi placeholder unreplaceable and reprocess loads and stores to propagate the unknown value. This can sometimes allow other loads to be replaced. At the end we re-calculate the heap values to find stores that can be eliminated because they write over the same value. Golem results: art-opt-cc arm arm64 x86 x86-64 CaffeineFloat +6.7% +3.0% +5.9% +3.8% KotlinMicroWhen +33.7% +4.8% +1.8% +0.6% art-opt (more noisy than art-opt-cc) CaffeineFloat +4.1% +4.4% +7.8% +10.5% KotlinMicroWhen +33.6% +2.0% +1.8% +1.8% The MoveLiteralColumn benchmark seems to gain significantly (up to 22% on art-opt-cc but under 10% on art-opt) but it is very noisy and the results are therefore unreliable. Insignificant code size changes for aosp_blueline-userdebug: - before: arm boot*.oat: 15303468 arm64 boot*.oat: 18184736 services.odex: 25195944 grep -c pAllocObject boot.arm64.oatdump.txt: 27213 grep -c pAllocArray boot.arm64.oatdump.txt: 3620 - after: arm boot*.oat: 15299524 (-4KiB, -0.03%) arm64 boot*.oat: 18176528 (-8KiB, -0.05%) services.odex: 25191832 (-4KiB, -0.02%) grep -c pAllocObject boot.arm64.oatdump.txt: 27206 (-7) grep -c pAllocArray boot.arm64.oatdump.txt: 3615 (-5) Test: New tests in 530-checker-lse. Test: m test-art-host-gtest Test: testrunner.py --host --optimizing Test: blueline-userdebug boots. Bug: 77906240 Change-Id: Ia9fe0cd3530f9d3941650dfefc00a7f7fd821994
2020-06-08Run LSA as a part of the LSE pass.Vladimir Marko
Make LSA a helper class, not an optimization pass. Move all its allocations to ScopedArenaAllocator to reduce the peak memory usage a little bit. Test: m test-art-host-gtest Test: testrunner.py --host --optimizing Change-Id: I7fc634abe732d22c99005921ffecac5207bcf05f
2019-10-14Revert "Make compiler/optimizing/ symbols hidden."Vladimir Marko
This reverts commit e2727154f25e0db9a5bb92af494d8e47b181dfcf. Reason for revert: Breaks ASAN tests (ODR violation). Bug: 142365358 Change-Id: I38103d74a1297256c81d90872b6902ff1e9ef7a4
2019-10-14Make compiler/optimizing/ symbols hidden.Vladimir Marko
Make symbols in compiler/optimizing hidden by a namespace attribute. The unit intrinsic_objects.{h,cc} is excluded as it is needed by dex2oat. As the symbols are no longer exported, gtests are now linked with the static version of the libartd-compiler library. libart-compiler.so size: - before: arm: 2396152 arm64: 3345280 - after: arm: 2016176 (-371KiB, -15.9%) arm64: 2874480 (-460KiB, -14.1%) Test: m test-art-host-gtest Test: testrunner.py --host --optimizing --jit Bug: 142365358 Change-Id: I1fb04a33351f53f00b389a1642e81a68e40912a8
2018-08-28Use 'final' and 'override' specifiers directly in ART.Roland Levillain
Remove all uses of macros 'FINAL' and 'OVERRIDE' and replace them with 'final' and 'override' specifiers. Remove all definitions of these macros as well, which were located in these files: - libartbase/base/macros.h - test/913-heaps/heaps.cc - test/ti-agent/ti_macros.h ART is now using C++14; the 'final' and 'override' specifiers have been introduced in C++11. Test: mmma art Change-Id: I256c7758155a71a2940ef2574925a44076feeebf
2018-05-15Refactoring LSE/LSA: introduce heap location typeAart Bik
Rationale: This refactoring introduces data types to heap locations. This will allow better type disambiguation in the future. As a first showcase, it already removes rather error-prone "exceptional" code in LSE dealing with array types on null values. Furthermore, many LSA specific details started to "leak" into clients, which is also error-prone. This refactoring moves such details back into just LSA, where it belongs. Test: test-art-host,target Bug: b/77906240 Change-Id: Id327bbe86dde451a942c9c5f9e83054c36241882
2018-04-26Step 1 of 2: conditional passes.Aart Bik
Rationale: The change adds a return value to Run() in preparation of conditional pass execution. The value returned by Run() is best effort, returning false means no optimizations were applied or no useful information was obtained. I filled in a few cases with more exact information, others still just return true. In addition, it integrates inlining as a regular pass, avoiding the ugly "break" into optimizations1 and optimziations2. Bug: b/78171933, b/74026074 Test: test-art-host,target Change-Id: Ia39c5c83c01dcd79841e4b623917d61c754cf075
2017-11-20Refactored optimization passes setup.Aart Bik
Rationale: Refactors the way we set up optimization passes in the compiler into a more centralized approach. The refactoring also found some "holes" in the existing mechanism (missing string lookup in the debugging mechanism, or inablity to set alternative name for optimizations that may repeat). Bug: 64538565 Test: test-art-host test-art-target Change-Id: Ie5e0b70f67ac5acc706db91f64612dff0e561f83
2017-11-10Improvement on array element aliasing analysis.Mingyao Yang
More robust array element aliasing analysis which covers aliasing between all heap locations. Test: run-test on host. Test: 530-checker-lse/load_store_analysis_test.cc cover array index aliasing. Change-Id: Ie0d1696bedb7811c6a4bc0786ef93ca724493de2
2017-11-09Support VecLoad and VecStore in LSA.xueliang.zhong
Test: test-art-host Test: test-art-target Test: load_store_analysis_test Change-Id: I7d819061ec9ea12f86a926566c3845231fce6e26
2017-11-02Fix LSA hunt for original reference bug.xueliang.zhong
Fix a bug in LSA where it doesn't take IntermediateAddress into account during hunting for original reference. In following example, original reference i0 can be transformed by NullCheck, BoundType, IntermediateAddress, etc. i0 NewArray i1 HInstruction(i0) i2 ArrayGet(i1, index) Test: test-art-host Test: test-art-target Test: load_store_analysis_test Test: 706-checker-scheduler Change-Id: I162dd8a86fcd31daee3517357c6af638c950b31b
2017-10-12Use ScopedArenaAllocator in BCE, DCE, LSE, ...Vladimir Marko
... ReferenceTypePropagation and GraphChecker. Define and use a new allocation kind for LoadStoreAnalysis. Memory needed to compile the two most expensive methods for aosp_angler-userdebug boot image: BatteryStats.dumpCheckinLocked() : 19.7MiB -> 19.6MiB (-79KiB) BatteryStats.dumpLocked(): 39.4MiB -> 39.3MiB (-120KiB) Test: m test-art-host-gtest Test: testrunner.py --host --optimizing Bug: 64312607 Change-Id: Ib0cf074ac21ab67d8f8f2efabbdfb84cce9cae8e
2017-10-06ART: Use ScopedArenaAllocator for pass-local data.Vladimir Marko
Passes using local ArenaAllocator were hiding their memory usage from the allocation counting, making it difficult to track down where memory was used. Using ScopedArenaAllocator reveals the memory usage. This changes the HGraph constructor which requires a lot of changes in tests. Refactor these tests to limit the amount of work needed the next time we change that constructor. Test: m test-art-host-gtest Test: testrunner.py --host Test: Build with kArenaAllocatorCountAllocations = true. Bug: 64312607 Change-Id: I34939e4086b500d6e827ff3ef2211d1a421ac91a
2017-09-25ART: Introduce compiler data type.Vladimir Marko
Replace most uses of the runtime's Primitive in compiler with a new class DataType. This prepares for introducing new types, such as Uint8, that the runtime does not need to know about. Test: m test-art-host-gtest Test: testrunner.py --host Bug: 23964345 Change-Id: Iec2ad82454eec678fffcd8279a9746b90feb9b0c
2017-08-28Simplify CreateReferenceInfoForReferenceType() in load-store-analysisMingyao Yang
We now do CreateReferenceInfoForReferenceType() in VisitInstruction() which catches all cases where a reference value is created. Test: run-test on hosts Change-Id: I14ce59ba44558e3e800fc2543f4e190cbb2fd75e
2017-08-03Add VisitNewArray() in lsa.Mingyao Yang
We missed one VisitNewArray() to create reference info right when a NewArray is seen. This may break pre-existence based aliasing analysis since another reference may be wrongly treated as existing before the NewArray. Also doing the same for a few more nodes that have reference values. This is not correctness issue but can open up more opportunities for detecting false aliases. Test: run-test on host. Bug: 64018485 Change-Id: I11f7857ab6b933448e7ba9ab6451d77dfc5c61a7
2017-06-26Improve array index analysis in LSA.xueliang.zhong
This CL improves analysis on array index in load store analysis. Test: m test-art-host Test: m test-art-target Test: m test-art-host-gtest-load_store_analysis_test Change-Id: Id5e5aa8b396c68e082db95809659494107985fa2
2017-05-19Create load store analysis passxueliang.zhong
This CL separates load store analysis from LSE pass. The load and store analysis in LSE pass records information about heap memory accesses for arrays and fields. Such information can also be used in the other optimizations like instruction scheduling pass which can eliminate side-effect dependencies between memory accesses to different locations. Test: m test-art-host Test: m test-art-target Test: m test-art-host-gtest-load_store_analysis_test Test: 530-checker-lse Change-Id: I353a2b9a03b19bfa0e7ef07716d60bd4254c7ea7
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-03 16:21:29 +0000