| 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
|
| 358af839c60db9e178f0b0bb9d430711c071b82a |
|
24-Feb-2016 |
Aart Bik <ajcbik@google.com> |
Recognize for (int i = 0; i != x.length; i++) loops
Rationale:
Idiom occurs in real-life and is very straightforwardly
recognized by existing induction/range machinery.
Change-Id: I965a16e9de72f3523ea5023d30ed1c4e47ed5010
|
| 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
|
| 1fc3afb76dbed78d255db276381df6036db2ee98 |
|
02-Feb-2016 |
Aart Bik <ajcbik@google.com> |
Minor improvement on static BCE analysis.
Rationale:
Avoid testing initial range if nothing is known.
Change-Id: I22646a5fd6e4481245d1a2f57891d2805550489f
|
| 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
|
| 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
|
| 4a34277c55279ba57ab361f7580db846a201d9b1 |
|
30-Nov-2015 |
Aart Bik <ajcbik@google.com> |
Dynamic BCE (based on induction range analysis)
Rationale:
A rewritten dynamic BCE that uses induction variable analysis
to generate the run-time tests before a loop in order to
eliminate bounds-checks from its body. This CL removes now
obsoleted induction related code inside the BCE module.
Also, the dynamic test generation is placed more strategically,
since we missed a few cases where static analysis does better.
Most significant performance improvements (filtering noise) is about:
Linpack +20%
LU > +10%
Change-Id: I03d7631857154b6a131b132f26a2dc568af1b3a1
|
| d59c70627cc42878cc30b46bd29ff497b4483b22 |
|
21-Nov-2015 |
Aart Bik <ajcbik@google.com> |
Revert "Dynamic BCE (based on induction range analysis)"
This reverts commit 0b5849be045c5683d4a6b6b6c306abadba5f0fcc.
Change-Id: Id33f5da42bbdfb1aff7e2281417c8a7aa492df05
Rationale: so close :-( but bullhead-userdebug (linux) build in git_mnc-dr-dev-plus-aosp reported a breakage with a type inconsistency (long vs int in probably the codegen of dynamic bce); no time to investigate and fix this fully before my trip, so rolling back for now
|
| 0b5849be045c5683d4a6b6b6c306abadba5f0fcc |
|
19-Oct-2015 |
Aart Bik <ajcbik@google.com> |
Dynamic BCE (based on induction range analysis)
Rationale: A rewritten dynamic BCE that uses induction variable analysis
to generate the run-time tests before a loop in order to
eliminate bounds-checks from its body. This CL removes now
obsoleted induction related code inside the BCE module.
Also, the dynamic test generation is placed more strategically,
since we missed a few cases where static analysis does better.
Most significant performance improvements (after filtering noise) is about:
Linpack +20%
LU > +10%
Change-Id: I4e7b8bab0288beff6f98a14856e3536103d32742
|
| 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
|
| 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
|
| 22af3bee34d0ab1a4bd186c71ccab00366882259 |
|
10-Sep-2015 |
Aart Bik <ajcbik@google.com> |
Use induction variable range analysis in BCE (statically).
Rationale: Finally! After lots of very large CLs, now a small CL
that uses the new induction variable analysis in BCE
(statically, using this dynamically with de-opt is TBD).
Despite its relative small size, be aware though,
since the CL introduces a new phase to the compiler.
Change-Id: If5555a173fd5d55d147c63138ef51fc296fa1414
|
| 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
|