| 0d345cf8db01f40db250f80de5104e0df24234fa |
|
16-Mar-2016 |
Aart Bik <ajcbik@google.com> |
Generalize induction and range analysis across type conversions.
Rationale:
This changelist implements allowing narrowing conversions within
inductions and loop control. More induction and loops recognized,
more bounds eliminated. We all win. The basic idea is pretty simple
(record type with detected induction) but one has to get all the
details right, as illustrated by the many new unit tests.
BUG=27151098
Change-Id: I254020bfa5fa623799b31bbbb5ccc97d4d5a0100
|
| 97412c92afb3f6630c4f0eafe6d6161862bfb4c1 |
|
20-Feb-2016 |
Aart Bik <ajcbik@google.com> |
Use range analysis for better trip count analysis
Rationale:
Marking more loops as always-taken avoids generating
unnecessary new top tests while marking more loops
are non-infinite enables more optimizations. This
CL helps with these improvements. Also, some more
code is shared between induction and range analysis
and a bug with refining ranges has been fixed.
Bug: 27151190
Change-Id: Iecc0d7f32ae4779ee5424cda9dcc20816220935e
|
| badd826664896d4a9628a5a89b78016894aa414b |
|
02-Feb-2016 |
David Brazdil <dbrazdil@google.com> |
ART: Run SsaBuilder from HGraphBuilder
First step towards merging the two passes, which will later result in
HGraphBuilder directly producing SSA form. This CL mostly just updates
tests broken by not being able to inspect the pre-SSA form.
Using HLocals outside the HGraphBuilder is now deprecated.
Bug: 27150508
Change-Id: I00fb6050580f409dcc5aa5b5aa3a536d6e8d759e
|
| 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
|
| 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
|
| 7d57d7f2f0328241ff07c43a93edadbc1a6697c6 |
|
09-Dec-2015 |
Aart Bik <ajcbik@google.com> |
Various induction/range analysis improvements.
Rationale: this change list improves analysis of triangular loops
both by changing loop order for induction analysis
(enabling range analysis in inner loops) and by
some symbolic improvements during range analysis;
also, a mul/div bug has been fixed (with pass/fail
unit tests); lastly this change list prepares some
follow up optimizations.
Change-Id: I84a03e848405009541c3fa8e3d3c2f430e100087
|
| 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
|
| b738d4f477a9b6f4c4f69153f9077f1559d2bca1 |
|
03-Dec-2015 |
Aart Bik <ajcbik@google.com> |
Step-wise improvement of range analysis with outer loop induction.
Rationale: Using a step-wise approach (rather than expanding all ranges
at once) increases the opportunities for statically removing
bound checks, as demonstrated by the new checker tests.
Change-Id: Icbfd9406523a069e1fb7508546ea94f896e5a255
|
| db51efb3617d15f1cd9e5ff0cc2d934777014e9a |
|
06-Nov-2015 |
David Brazdil <dbrazdil@google.com> |
ART: Fix critical edge splitting under try/catch
A critical edge would not be split if the predecessor ends with
TryBoundary. This would eventually trip liveness analysis because
a back edge block would have smaller liveness position than a nested
loop.
Another implication of this change is that an edge between a loop's
pre-header ending with TryBoundary and the header will be split,
guaranteeing that a pre-header always has just one successor.
Bug: 25493695
Bug: 25454012
Change-Id: I5a13b8bb74509b48f5d628906f7158af007f99ae
|
| 389b3dbf5c5390056ff4dacac464219853dd3cda |
|
28-Oct-2015 |
Aart Bik <ajcbik@google.com> |
Finalized all components of range analysis needed for dynamic bce.
Rationale: added ability to generate taken-test, prompt back need
for finite-test; cleaned up the API now that bounds
check needs are all known.
Change-Id: I3d09b249965d1a980c09381240de175ca4b2e455
|
| 22f058726d35dd8f40b3763649e61740b3d22535 |
|
27-Oct-2015 |
Aart Bik <ajcbik@google.com> |
Generate taken-test during trip-count analysis.
Rationale: for loops that may not be taken, this taken-test
can be used by clients of the induction variable
analysis to ensure trip-count evaluation is valid.
Change-Id: Ia64749e2389b7224e69d6a49bb604b1964c11068
|
| 27cfad0d14669ea00333f74bbde9ad923fee70ff |
|
20-Oct-2015 |
Calin Juravle <calin@google.com> |
Fix induction_var_range_test.
Change-Id: I43101c5e35f4c516ea4ba3137631508f12703412
|
| aec3cce52009afe436a6db0280d6d5aee9b8d4d4 |
|
15-Oct-2015 |
Aart Bik <ajcbik@google.com> |
Added ability to generate induction range code.
Rationale: used by dynamic BCE (done in another CL).
Change-Id: Ia6ce75da57b5298fba74622822ae0bae69c74188
|
| 9401f5397128ddc8dc36de923dd5e6bd4e4b5be4 |
|
29-Sep-2015 |
Aart Bik <ajcbik@google.com> |
Implemented trip-count safety information.
As shown in the induction analysis presentation, trip-counts need to
deal with potential taken/not-taken situations (so that trip-count
is either valid in the full loop or just in the loop-body proper)
and potential finite/infinite situations (the latter can still be
analyzed but may need to run-time test later to guard against the
infinite conditions). This CL provides that information.
Change-Id: I0445d8e836b80a3614af217ce3e39d766e77b986
|
| cd26feb7e9f9eb36af9453f3cdb55cfc4e6e5ec4 |
|
24-Sep-2015 |
Aart Bik <ajcbik@google.com> |
Minor cleanup in range analysis.
(1) replaced min/max macro as previously required.
(2) removed some redundant code by merging min/max into one.
Change-Id: I610879a06d550346bfac7e6e12ec0299ba226a37
|
| b3365e0c4cda4f8f19284d2d418db158ab78d810 |
|
21-Sep-2015 |
Aart Bik <ajcbik@google.com> |
Various improvements in range analysis.
Rationale:
Using min/max values for "unknowns" is a bit wasteful,
since it eliminates two useful values. Replaced this
with additional boolean to make cases more accurate.
Added few cases to handle examples found in real-life.
Change-Id: I211f8d9a28b1ae79abdb55fb4569716f21d8043b
|
| d14c59564870c910bdc823081f0ed1101f599231 |
|
09-Sep-2015 |
Aart Bik <ajcbik@google.com> |
Induction variable range analysis.
Rationale: by computing an upper bound on the trip count of each
loop after induction var analysis has completed, a
simple range analysis yields lower and upper bounds on
all induced expressions in a loop; this analysis
plugs directly into BCE (follow-up CL).
Change-Id: I46a3fe48721ca372547199b39a3498c47992597d
|