| 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
|
| 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
|
| 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
|
| 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
|
| 5233f93ee336b3581ccdb993ff6342c52fec34b0 |
|
29-Sep-2015 |
Vladimir Marko <vmarko@google.com> |
Optimizing: Tag even more arena allocations.
Tag previously "Misc" arena allocations with more specific
allocation types. Move some native heap allocations to the
arena in BCE.
Bug: 23736311
Change-Id: If8ef15a8b614dc3314bdfb35caa23862c9d4d25c
|
| f475bee067ae0f6dd2a022c823c642265f97b065 |
|
16-Sep-2015 |
Aart Bik <ajcbik@google.com> |
Various improvements in finding induction variables.
Rationale:
(1) Analyze multi-way phis (requested by Nicolas, Igor, and Mingyao).
(2) Analyze trip count for restricted != loops
(3) Added unit test for public API of range analysis (static methods
were already well-tested).
Change-Id: I9285d22d3bb927f141204cc4697ea6fe5120994d
|
| 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
|
| 471a2034171346dda4539b985b95aa6370531171 |
|
05-Sep-2015 |
Aart Bik <ajcbik@google.com> |
Simplify loop invariant operations during induction analysis.
Rationale:
Saves some memory for nodes that are not really required, and
yields slightly more readable debugging strings.
Change-Id: I95b64b48869699137b5d49e26eb20091e264de7a
|
| e609b7cf9996389e6e693f149489737436172a2c |
|
27-Aug-2015 |
Aart Bik <ajcbik@google.com> |
Further development of induction variable analysis.
Various improvements:
(1) Introduced period sequences.
(2) Extended all transfer functions to deal with all cases;
also refactored these to read more compactly.
(3) Improved debugging output for constants for readability.
(4) Used direct pointer in mappings for clarify.
(5) Several induction info "constructors" for readability.
(6) Various other changes suggested in earlier code reviews.
Change-Id: I9d5381f1676b63d30cea6f5e304d4b7bda7acb96
|
| 30efb4e00c2a9aa318d44486b5eacaa7178d20ef |
|
30-Jul-2015 |
Aart Bik <ajcbik@google.com> |
Induction variable analysis (with unit tests).
Rationale:
Induction variable analysis forms the basis of a wide
variety of compiler optimizations. This implementation
finds induction variables using the elegant SSA-based
algorithm defined by [Gerlek et al.].
Change-Id: I79b8dce33ffb8b283c179699a8dff5bd196f75b2
|