| 63347bbb6d25b762eaa67c67d78a019d28e94321 |
|
10-May-2016 |
Vladimir Marko <vmarko@google.com> |
Reduce memory usage of SSA Phi elimination and make it faster.
Use an ArenaBitVector instead of an ArenaSet<> that leaks
its allocated memory on clear(). We were also erroneously
using the O(n) helper ContainsElement() for the ArenaSet<>
instead of the O(log n) ArenaSet<>::find() which made the
methods with large number of processed Phis also very slow
to compile in addition to the enormous memory usage.
Bug: 28684584
(cherry picked from commit c9ef168bfabd118d112a054dffe2c27d4d4db4fc)
Change-Id: I6115006259a9f697ea70e31d4478966fc601e24b
|
| a26b3c51bfd97be1100d267f20c46535913e6bb7 |
|
09-May-2016 |
Vladimir Marko <vmarko@google.com> |
Attribute arena allocations previously marked as STL.
Bug: 28603175
Bug: 28684584
(cherry picked from commit 3ea5a97d27468cec846d958c38d0d706ef7ec67e)
Change-Id: I7f1bd22e7710cca74f4b10fd13cb8fa2c3b1b318
|
| 89db4e6e3bd36c6848380af56a858a829af194ad |
|
04-May-2016 |
Nicolas Geoffray <ngeoffray@google.com> |
Do not look at dead phis during SsaRedundantPhiElimination.
Otherwise, we may replace a dead loop phi with its incoming input.
This broke an assumption during liveness analysis in the presence
of irreducible loops.
bug:28256552
(cherry picked from commit 05b3fa02ed8ef62841a92cd96526ba3a06bf1f63)
Change-Id: I297c8fbd9a2414dd852aa932595f7b42d8f1a584
|
| d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6ede |
|
29-Mar-2016 |
Vladimir Marko <vmarko@google.com> |
Use iterators "before" the use node in HUserRecord<>.
Create a new template class IntrusiveForwardList<> that
mimicks std::forward_list<> except that all allocations
are handled externally. This is essentially the same as
boost::intrusive::slist<> but since we're not using Boost
we have to reinvent the wheel.
Use the new container to replace the HUseList and use the
iterators to "before" use nodes in HUserRecord<> to avoid
the extra pointer to the previous node which was used
exclusively for removing nodes from the list. This reduces
the size of the HUseListNode by 25%, 32B to 24B in 64-bit
compiler, 16B to 12B in 32-bit compiler. This translates
directly to overall memory savings for the 64-bit compiler
but due to rounding up of the arena allocations to 8B, we
do not get any improvement in the 32-bit compiler.
Compiling the Nexus 5 boot image with the 64-bit dex2oat
on host this CL reduces the memory used for compiling the
most hungry method, BatteryStats.dumpLocked(), by ~3.3MiB:
Before:
MEM: used: 47829200, allocated: 48769120, lost: 939920
Number of arenas allocated: 345,
Number of allocations: 815492, avg size: 58
...
UseListNode 13744640
...
After:
MEM: used: 44393040, allocated: 45361248, lost: 968208
Number of arenas allocated: 319,
Number of allocations: 815492, avg size: 54
...
UseListNode 10308480
...
Note that while we do not ship the 64-bit dex2oat to the
device, the JIT compilation for 64-bit processes is using
the 64-bit libart-compiler.
Bug: 28173563
Bug: 27856014
(cherry picked from commit 46817b876ab00d6b78905b80ed12b4344c522b6c)
Change-Id: Ifb2d7b357064b003244e92c0d601d81a05e56a7b
|
| 15bd22849ee6a1ffb3fb3630f686c2870bdf1bbc |
|
05-Jan-2016 |
Nicolas Geoffray <ngeoffray@google.com> |
Implement irreducible loop support in optimizing.
So we don't fallback to the interpreter in the presence of
irreducible loops.
Implications:
- A loop pre-header does not necessarily dominate a loop header.
- Non-constant redundant phis will be kept in loop headers, to
satisfy our linear scan register allocation algorithm.
- while-graph optimizations, such as gvn, licm, lse, and dce
need to know when they are dealing with irreducible loops.
Change-Id: I2cea8934ce0b40162d215353497c7f77d6c9137e
|
| 4833f5a1990c76bc2be89504225fb13cca22bedf |
|
16-Dec-2015 |
David Brazdil <dbrazdil@google.com> |
ART: Refactor SsaBuilder for more precise typing info
This reverts commit 68289a531484d26214e09f1eadd9833531a3bc3c.
Now uses Primitive::Is64BitType instead of Primitive::ComponentSize
because it was incorrectly optimized by GCC.
Bug: 26208284
Bug: 24252151
Bug: 24252100
Bug: 22538329
Bug: 25786318
Change-Id: Ib39f3da2b92bc5be5d76f4240a77567d82c6bebe
|
| f5f64efda943000168d34bfe44ccbbadd284e55f |
|
15-Dec-2015 |
Nicolas Geoffray <ngeoffray@google.com> |
Detect phi cycles.
Having reference and non-reference phi equivalent, only happened
for the 0/null constant. To avoid such occurences, we must
detect phi cycles.
bug:25493693
Change-Id: Ie1a8460c3abacca96c299da107fa4407e17dd792
|
| 68289a531484d26214e09f1eadd9833531a3bc3c |
|
16-Dec-2015 |
Alex Light <allight@google.com> |
Revert "ART: Refactor SsaBuilder for more precise typing info"
This reverts commit d9510dfc32349eeb4f2145c801f7ba1d5bccfb12.
Bug: 26208284
Bug: 24252151
Bug: 24252100
Bug: 22538329
Bug: 25786318
Change-Id: I5f491becdf076ff51d437d490405ec4e1586c010
|
| d9510dfc32349eeb4f2145c801f7ba1d5bccfb12 |
|
05-Nov-2015 |
David Brazdil <dbrazdil@google.com> |
ART: Refactor SsaBuilder for more precise typing info
This patch refactors the SsaBuilder to do the following:
1) All phis are constructed live and marked dead if not used or proved
to be conflicting.
2) Primitive type propagation, now not a separate pass, identifies
conflicting types and marks corresponding phis dead.
3) When compiling --debuggable, DeadPhiHandling used to revive phis
which had only environmental uses but did not attempt to resolve
conflicts. This pass was removed as obsolete and is now superseded
by primitive type propagation (identifying conflicting phis) and
SsaDeadPhiEliminiation (keeping phis live if debuggable + env use).
4) Resolving conflicts requires correct primitive type information
on all instructions. This was not the case for ArrayGet instructions
which can have ambiguous types in the bytecode. To this end,
SsaBuilder now runs reference type propagation and types ArrayGets
from the type of the input array.
5) With RTP being run inside the SsaBuilder, it is not necessary to
run it as a separate optimization pass. Optimizations can now assume
that all instructions of type kPrimNot have reference type info after
SsaBuilder (with the exception of NullConstant).
6) Graph now contains a reference type to be assigned to NullConstant.
All reference type instructions therefore have RTI, as now enforced
by the SsaChecker.
Bug: 24252151
Bug: 24252100
Bug: 22538329
Bug: 25786318
Change-Id: I7a3aee1ff66c82d64b4846611c547af17e91d260
|
| 809d70f5b268227dbd59432dc038c74d8351be29 |
|
19-Nov-2015 |
David Brazdil <dbrazdil@google.com> |
ART: Fix wide stores in Optimizing
SsaBuilder::VisitStoreLocal did not take into account the following:
(a) when storing a wide value, the high vreg must be invalidated,
(b) when storing into the high vreg of a wide value, the low vreg
must be invalidated.
Both situations cause overestimation of liveness but only (b) has
implications on correctness. CodeGenerator::EmitEnvironment will skip
the high vreg, causing deoptimizing and try/catch to load a wrong
value for that vreg.
In order to fix this bug, several changes had to be made to the
SsaBuilder:
(1) phis need to be initialized with a type which matches its
inputs' size,
(2) eagerly created loop header phis may end up being undefined
because of their corresponding vregs being invalidated inside
the loop; these are marked dead during input setting,
(3) the entire SSA-building algorithm should never revive an
undefined loop header phi.
Bug: 25677992
Bug: https://code.google.com/p/android/issues/detail?id=194022
Change-Id: Id8a852e38c3f5ff1c2e608b1aafd6d5ac8311e32
|
| 2bd4c5c1b704be8a81d9b7a94b3e828afa2b0963 |
|
04-Nov-2015 |
David Brazdil <dbrazdil@google.com> |
Revert "ART: Implement DeadPhiHandling in PrimitiveTypePropagation"
Crashes on YouTube, need to investigate
This reverts commit 1749e2cfb5c5ed4d6970a09aecf898ca9cdfcb75.
Change-Id: If5f133d55dcc26b8db79a670a48fbd4af7807556
|
| 1749e2cfb5c5ed4d6970a09aecf898ca9cdfcb75 |
|
28-Sep-2015 |
David Brazdil <dbrazdil@google.com> |
ART: Implement DeadPhiHandling in PrimitiveTypePropagation
DeadPhiHandling revives non-conflicting phis with environment uses
but does not properly merge types. To not duplicate code, this patch
modifies PrimitiveTypePropagation to deal with conflicts and thus
replaces DeadPhiHandling altogether.
Bug: 24252151
Bug: 24252100
Change-Id: I198c71d1b8167fc05783a5a24aa9f1e3804acafe
|
| 2aaa4b5532d30c4e65d8892b556400bb61f9dc8c |
|
17-Sep-2015 |
Vladimir Marko <vmarko@google.com> |
Optimizing: Tag more arena allocations.
Replace GrowableArray with ArenaVector and tag arena
allocations with new allocation types.
As part of this, make the register allocator a bit more
efficient, doing bulk insert/erase. Some loops are now
O(n) instead of O(n^2).
Change-Id: Ifac0871ffb34b121cc0447801a2d07eefd308c14
|
| 77b022dfb8e73564b00c4724f7078cb1d5a57a65 |
|
19-Aug-2015 |
David Brazdil <dbrazdil@google.com> |
ART: Revisit users in phi elimination
SSA phi elimination visits phis in post order so that loop phis are
visited after their inputs. This prevents elimination of phis with
other phi inputs, exacerbated by the fact that the SSA builder does
create catch phis even if all inputs are the same (unlike with normal
phis). This patch revisits phi users of eliminated phis until no more
phis can be removed.
Change-Id: I403614dd46a8e6f0a5b9dd9e8ddc8832617521eb
|
| ffee3d33f3ea39aa6031c3d2ff29c4806c8dcc51 |
|
06-Jul-2015 |
David Brazdil <dbrazdil@google.com> |
ART: Build SSA form when try/catch is present
This patch implements support for try/catch in the SsaBuilder.
Values of locals are propagated from throwing sites inside try
blocks to their respective catch blocks and phis ("catch phis")
are created when necessary.
Change-Id: I0736565c2c4ff3f9f0924b6e3a785a50023f875a
|
| 1abb4191a2e56d8dbf518efcaeefb266c1acdf2b |
|
17-Feb-2015 |
David Brazdil <dbrazdil@google.com> |
Optimizing: Speed up HInstruction use removal
Similarly to a previous commit on HEnvironment use removal, this patch
adds links from instructions to their respective inputs' use lists for
contant-time removal at the cost of doubling the size of input lists
(from one pointer per entry to two). Manual testing shows that this
significantly reduces the time required to transform HGraph to SSA
form for some huge methods.
Change-Id: I8dc3e4b0c48a50ac1481eb55c31093b99f4dc29f
|
| d6138ef1ea13d07ae555542f8898b30d89e9ac9a |
|
18-Feb-2015 |
Nicolas Geoffray <ngeoffray@google.com> |
Ensure the graph is correctly typed.
We used to be forgiving because of HIntConstant(0) also being
used for null. We now create a special HNullConstant for such uses.
Also, we need to run the dead phi elimination twice during ssa
building to ensure the correctness.
Change-Id: If479efa3680d3358800aebb1cca692fa2d94f6e5
|
| ed59619b370ef23ffbb25d1d01f615e60a9262b6 |
|
23-Jan-2015 |
David Brazdil <dbrazdil@google.com> |
Optimizing: Speed up HEnvironment use removal
Removal of use records from HEnvironment vregs involved iterating over
potentially large linked lists which made compilation of huge methods
very slow. This patch turns use lists into doubly-linked lists, stores
pointers to the relevant nodes inside HEnvironment and subsequently
turns the removals into constant-time operations.
Change-Id: I0e1d4d782fd624e7b8075af75d4adf0a0634a1ee
|
| 3159674c0863f53cfbc1913d493550221ac47f02 |
|
24-Nov-2014 |
Nicolas Geoffray <ngeoffray@google.com> |
Fix a bug in the type analysis phase of optimizing.
Dex code can lead to the creation of a phi with one
float input and one integer input. Since the SSA builder trusts
the verifier, it assumes that the integer input must be converted
to float. However, when the register is not used afterwards, the
verifier hasn't ensured that. Therefore, the compiler must remove
the phi prior to doing type propagation.
Change-Id: Idcd51c4dccce827c59d1f2b253bc1c919bc07df5
|
| 277ccbd200ea43590dfc06a93ae184a765327ad0 |
|
04-Nov-2014 |
Andreas Gampe <agampe@google.com> |
ART: More warnings
Enable -Wno-conversion-null, -Wredundant-decls and -Wshadow in general,
and -Wunused-but-set-parameter for GCC builds.
Change-Id: I81bbdd762213444673c65d85edae594a523836e5
|
| 102cbed1e52b7c5f09458b44903fe97bb3e14d5f |
|
15-Oct-2014 |
Nicolas Geoffray <ngeoffray@google.com> |
Implement register allocator for floating point registers.
Also:
- Fix misuses of emitting the rex prefix in the x86_64 assembler.
- Fix movaps code generation in the x86_64 assembler.
Change-Id: Ib6dcf6e7c4a9c43368cfc46b02ba50f69ae69cbe
|
| 6b879ddc0959df1cec871f0d41f11cce35a11716 |
|
22-Sep-2014 |
Roland Levillain <rpl@google.com> |
Add loop- and phi-related checks in the optimizing compiler.
- Ensure the pre-header block is first in the list of
predecessors of a loop header.
- Ensure the loop header has only two predecessors and that
only the second one is the back edge.
- Ensure there is only one back edge per loop.
- Ensure the first input of a phi is not itself.
- Ensure the number of phi inputs is the same as the number
of its predecessors.
- Ensure phi input at index I either comes from the Ith
predecessor or from a block that dominates this
predecessor.
Change-Id: I4db5c68cfbc9b74d2d03125753d0143ece625378
|
| 604c6e4764edb2fd244e9f47626868cda5644a7a |
|
17-Sep-2014 |
Nicolas Geoffray <ngeoffray@google.com> |
Ensure the first predecessor of a loop is the pre header.
Note that the check in ssa_phi_elimination.cc was very defensive:
it does not affect the outcome of the algorithm whether the
loop phi takes itself as the first input.
It makes things consistent to always have the pre header as first
input.
Change-Id: Ic86248c1f38af67f7432782f6deefae1f4bf1ab6
|
| 3946844c34ad965515f677084b07d663d70ad1b8 |
|
02-Sep-2014 |
Nicolas Geoffray <ngeoffray@google.com> |
Runtime support for the new stack maps for the opt compiler.
Now most of the methods supported by the compiler can be optimized,
instead of using the baseline.
Change-Id: I80ab36a34913fa4e7dd576c7bf55af63594dc1fa
|
| 3ac17fcce8773388512ce72cb491b202872ca1c1 |
|
07-Aug-2014 |
Nicolas Geoffray <ngeoffray@google.com> |
Fix SsaDeadPhiElimination in the presence of dependent phis.
This fixes the problem of having a dead loop phi taking as back-edge
input a phi that also has this loop phi as input. Walking backwards
does not solve the problem because the loop phi will be visited last.
Most of the time, dex removes dead locals like this.
Change-Id: I797198cf9c15f8faa6585cca157810e23aaa4940
|
| 7dc206a53a42a658f52d5cb0b7e79b47da370c9b |
|
11-Jul-2014 |
Nicolas Geoffray <ngeoffray@google.com> |
Add two phi pruning phases.
Change-Id: Ic4f05e3df96970d78a6938b27cdf9b58ef3849b9
|