History log of /art/compiler/dex/local_value_numbering.cc
Revision Date Author Comments
41b175aba41c9365a1c53b8a1afbd17129c87c14 19-May-2015 Vladimir Marko <vmarko@google.com> ART: Clean up arm64 kNumberOfXRegisters usage.

Avoid undefined behavior for arm64 stemming from 1u << 32 in
loops with upper bound kNumberOfXRegisters.

Create iterators for enumerating bits in an integer either
from high to low or from low to high and use them for
<arch>Context::FillCalleeSaves() on all architectures.

Refactor runtime/utils.{h,cc} by moving all bit-fiddling
functions to runtime/base/bit_utils.{h,cc} (together with
the new bit iterators) and all time-related functions to
runtime/base/time_utils.{h,cc}. Improve test coverage and
fix some corner cases for the bit-fiddling functions.

Bug: 13925192

(cherry picked from commit 80afd02024d20e60b197d3adfbb43cc303cf29e0)

Change-Id: I905257a21de90b5860ebe1e39563758f721eab82
c6e7845740b3e29d942d2892e465762afda37058 24-Apr-2015 Vladimir Marko <vmarko@google.com> Quick: Rely on inferred types in GVN/LVN/DCE.

Fix LVN::GetEndingVregValueNumberImpl() to check whether
the requested wideness matches the SSA register type as
recorded in MIRGraph::reg_location_.

Add DCHECKs that the wideness matches when getting/setting
sreg values, update Phi handling in LVN/DCE to use the type
from MIRGraph::reg_location_ instead of determining it from
the sreg value maps which would now trigger the DCHECKs.
Update tests to initialize MIRGraph::reg_location_.

Reenable DCE.

Bug: 20572509

(cherry picked from commit a5e69e87c630c08c0de1740427e60d531ce851b9)

Change-Id: Ieb97ac9e3672b977e36fd7f369a975bae7d5271e
a5e69e87c630c08c0de1740427e60d531ce851b9 24-Apr-2015 Vladimir Marko <vmarko@google.com> Quick: Rely on inferred types in GVN/LVN/DCE.

Fix LVN::GetEndingVregValueNumberImpl() to check whether
the requested wideness matches the SSA register type as
recorded in MIRGraph::reg_location_.

Add DCHECKs that the wideness matches when getting/setting
sreg values, update Phi handling in LVN/DCE to use the type
from MIRGraph::reg_location_ instead of determining it from
the sreg value maps which would now trigger the DCHECKs.
Update tests to initialize MIRGraph::reg_location_.

Reenable DCE.

Bug: 20572509
Change-Id: I1a4d4e32cd57807ca8b56d2f3ed5e1288660b82e
ca71458862be8505330b7fd5649a062f31d143dc 04-Apr-2015 Andreas Gampe <agampe@google.com> ART: Add Clang's -Wused-but-marked-unused

Add detection of wrong unused annotations. Fix our codebase.

Change-Id: I85cc20f2eac71c1ec6c5c7cd6efb08454a629634
22fe45de11ed7afdf21400d2de3abd23f3a62800 18-Mar-2015 Vladimir Marko <vmarko@google.com> Quick: Eliminate check-cast guaranteed by instance-of.

Eliminate check-cast if the result of an instance-of with
the very same type on the same value is used to branch to
the check-cast's block or a dominator of it.

Note that there already exists a verifier-based elimination
of check-cast but it excludes check-cast on interfaces. This
new optimization works for interface types and, since it's
GVN-based, it can better recognize when the same reference
is used for instance-of and check-cast.

Change-Id: Ib315199805099d1cb0534bb4a90dc51baa409685
22c7f5bc70d0c8f3e5915b7fb98c9f9930cfdff0 18-Feb-2015 Vladimir Marko <vmarko@google.com> Distinguish FP and integral constants in LVN.

Change-Id: I31a58ff19fb95a2f56420359e50332c1dce6cbc7
7a01dc2107d4255b445c32867d15d45fcebb3acd 02-Jan-2015 Vladimir Marko <vmarko@google.com> Dead code elimination based on GVN results.

Change-Id: I5b77411a8f088f0b561da14b123cf6b0501c9db5
47d2e48092717f2439b41d36430b5e1da9f8915e 06-Feb-2015 Serguei Katkov <serguei.i.katkov@intel.com> LVN handles const-wide/32 incorrectly

Redundant shift to 16 bit should be eliminated otherwise any
32 bit shift of 32 bit constant will result in 0.

Change-Id: I4969b54357bc2d9a836e89dd7919199fff966684
Signed-off-by: Serguei Katkov <serguei.i.katkov@intel.com>
743b98cd3d7db1cfd6b3d7f7795e8abd9d07a42d 24-Nov-2014 Vladimir Marko <vmarko@google.com> Skip null check in MarkGCCard() for known non-null values.

Use GVN's knowledge of non-null values to set a new MIR flag
for IPUT/SPUT/APUT to skip the value null check.

Change-Id: I97a8d1447acb530c9bbbf7b362add366d1486ee1
321b987ef037c44c0ed4e0e82661c88959a6239f 24-Nov-2014 Vladimir Marko <vmarko@google.com> Further cleanup using dex_instruction_utils.h.

Change-Id: I85aa9e7d744b37ee3d2531c50470cd3fa87dc864
e0951144d71a4791a5319ec507d84fce373018e0 14-Nov-2014 Razvan A Lupusoru <razvan.a.lupusoru@intel.com> ART: Add div-zero check elimination to LVN/GVN

GVN has been updated to also consider div/rem zero check elimination.
This means that whenever a divisor is used in two sequential divisions,
the second division will surely not throw exception.

The algorithm has been updated to work on global level by considering
splits and merges. Obviously, if "div_zero" checked on one path but
not the other, at merge point consider that division has not been
eliminated.

One big deficiency of this algorithm is that it does not consider
literals in the divisor. Namely, in cases where the operand is a literal
or a constant (literal created by another bytecode), it does not mark as
divide by zero checked. However, in reality this is not an issue
because none of the backends generate the divide by zero check when
the constant value is known.

Issue: CAR-868
Category: device enablement
Domain: AOSP.ART-ME
Origin: internal
Upstream-Candidate: yes
Change-Id: I617569055c73a45e13e2a83392b99b48f4e33362
Signed-off-by: Razvan A Lupusoru <razvan.a.lupusoru@intel.com>
af6925b7fe5dc5a3c8d52ee3370e86e75400f873 31-Oct-2014 Vladimir Marko <vmarko@google.com> Rewrite GVN's field id and field type handling.

Create a helper unit for dex insn classification and cache
dex field type (as encoded in the insn) in the MirFieldInfo.
Use this for cleanup and a few additional DCHECKs.

Change the GVN's field id to match the field lowering info
index (MIR::meta::{i,s}field_lowering_info), except where
multiple indexes refer to the same field and we use the
lowest of the applicable indexes. Use the MirMethodInfo from
MIRGraph to retrieve field type for GVN using this index.
This slightly reduces GVN compilation time and prepares for
further compilation time improvements.

Change-Id: I1b1247cdb8e8b6897254e2180f3230f10159bed5
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
6a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866f 31-Oct-2014 Ian Rogers <irogers@google.com> Remove -Wno-unused-parameter and -Wno-sign-promo from base cflags.

Fix associated errors about unused paramenters and implict sign conversions.
For sign conversion this was largely in the area of enums, so add ostream
operators for the effected enums and fix tools/generate-operator-out.py.
Tidy arena allocation code and arena allocated data types, rather than fixing
new and delete operators.
Remove dead code.

Change-Id: I5b433e722d2f75baacfacae4d32aef4a828bfe1b
66c6d7bdfdd535e6ecf4461bba3804f1a7794fcd 16-Oct-2014 Vladimir Marko <vmarko@google.com> Rewrite class initialization check elimination.

Split the notion of type being in dex cache away from the
class being initialized. Include static invokes in the class
initialization elimination pass.

Change-Id: Ie3760d8fd55b987f9507f32ef51456a57d79e3fb
a4426cff8a81e6af05aa8cc44c162110ccf2d397 22-Oct-2014 Vladimir Marko <vmarko@google.com> Quick: Fix wide Phi detection in GVN, clean up INVOKEs.

The detection of a wide Phi has been incorrectly looking at
the current LVN's wide sreg value map but we only intersect
live values and thus very often lose the information. This
results in failure to identify identical values, i.e.
potential missed optimizations. It also caused the bloating
of the global value map with values we would not use.

Rewrite the wide Phi detection to use the first merged LVN's
notion of wide sreg. For this to work we also need to use
the method's shorty to mark wide arguments.

Also clean up INVOKEs' processing to avoid another source
of bloating the global value map.

Bug: 16398693
Change-Id: I76718af7d62a8c6883ef43e4f47058f7eaf479e1
415ac88a6471792a28cf2b457fe4ba9dc099396e 30-Sep-2014 Vladimir Marko <vmarko@google.com> Quick: In GVN, apply modifications early if outside loop.

To improve GVN performance, apply modifications to blocks
outside loops during the initial convergence phase. During
the post processing phase, apply modifications only to the
blocks belonging to loops.

Also clean up the check whether to run the LVN and add the
capability to limit the maximum number of nested loops we
allow the GVN to process.

Change-Id: Ie7f1254f91a442397c06a325d5d314d8f58e5012
a78e66a2c0fb1ce75e3a4edaf0d70c0d1647dbad 16-Oct-2014 Vladimir Marko <vmarko@google.com> Quick: Handle kMirOpNullCheck in LVN/GVN.

Change-Id: I0274e98cc61ccd1dbe0bd3e50deeb7d62bd1cb22
fc787ecd91127b2c8458afd94e5148e2ae51a1f5 10-Oct-2014 Ian Rogers <irogers@google.com> Enable -Wimplicit-fallthrough.

Falling through switch cases on a clang build must now annotate the fallthrough
with the FALLTHROUGH_INTENDED macro.
Bug: 17731372

Change-Id: I836451cd5f96b01d1ababdbf9eef677fe8fa8324
ff0ac4772d489d8780bbb6bb271dc6d5333cca7c 02-Oct-2014 Vladimir Marko <vmarko@google.com> Remove all uses of MIR_INLINED.

They are not needed since
https://android-review.googlesource.com/103763

Change-Id: I1dffe5e219db615be9d9aaceb72ad9bd7c69b58e
fa23645319cca1f1c4a7c208f931820f6783b1a4 29-Sep-2014 Vladimir Marko <vmarko@google.com> Quick: Fix LVN/GVN handling of acquire operations.

Acquire operations, i.e. MONITOR_ENTER and volatile GETs,
change the thread's view of the memory, so subsequent loads
must get new value names in LVN/GVN. Release operations do
not affect this thread's view of the memory, they the only
push the modifications for other threads to see.

Bug: 17689750
Change-Id: I9442d89b1d2c5252b99b02851b71bb85f871d734
fb0ea2df9a52e5db18e1aa85da282938bbd92f2e 29-Jul-2014 Jean Christophe Beyler <jean.christophe.beyler@intel.com> ART: Extending FlagsOf

Modified FlagsOf to handle extended flags.

Change-Id: I9e47e0c42816136b2b53512c914200dd9dd11376
Signed-off-by: Jean Christophe Beyler <jean.christophe.beyler@intel.com>
2d2365cdaa54583b47c18a6506ccd0fd723ab6d0 19-Aug-2014 Vladimir Marko <vmarko@google.com> Improve GVN performance when merging null-checked values.

And ignore the limit on maximum number of processed basic
blocks once the GVN has actually converged and we're just
applying optimizations.

Bug: 16398693
Change-Id: Ie5aa0386ea4e0e9ae2bbf13963e2424e1713b22f
07206af370746e6d7cf528e655b4854e7a865cfa 29-Jul-2014 Vladimir Marko <vmarko@google.com> Reduce time and memory usage of GVN.

Filter out dead sregs in GVN. Reclaim memory after each LVN
in the GVN modification phase.

Bug: 16398693

(cherry picked from commit b19955d3c8fbd9588f7e17299e559d02938154b6)

Change-Id: I33c7912258a768b4c99d787056979fbc3b023b3b
b19955d3c8fbd9588f7e17299e559d02938154b6 29-Jul-2014 Vladimir Marko <vmarko@google.com> Reduce time and memory usage of GVN.

Filter out dead sregs in GVN. Reclaim memory after each LVN
in the GVN modification phase.

Bug: 16398693
Change-Id: I8c88c3009663754e1b66c0ef3f62c3b93276e385
1fd4821f6b3ac57a44c2ce91025686da4641d197 10-Jul-2014 Vladimir Marko <vmarko@google.com> Rewrite topological sort order and improve GVN.

Rewrite the topological sort order to include a full loop
before the blocks that go after the loop. Add a new iterator
class LoopRepeatingTopologicalSortIterator that differs from
the RepeatingTopologicalSortIterator by repeating only loops
and repeating them early. It returns to the loop head if the
head needs recalculation when we reach the end of the loop.

In GVN, use the new loop-repeating topological sort iterator
and for a loop head merge only the preceding blocks' LVNs
if we're not currently recalculating this loop.

Also fix LocalValueNumbering::InPlaceIntersectMaps() which
was keeping only the last element of the intersection, avoid
some unnecessary processing during LVN merge and add some
missing braces to MIRGraph::InferTypeAndSize().

Bug: 16398693

(cherry picked from 55fff044d3a4f7196098e25bab1dad106d9b54a2)

Change-Id: Id7bcd99c8abed1b7500b9ef723313d4c5fc6f1e8
55fff044d3a4f7196098e25bab1dad106d9b54a2 10-Jul-2014 Vladimir Marko <vmarko@google.com> Rewrite topological sort order and improve GVN.

Rewrite the topological sort order to include a full loop
before the blocks that go after the loop. Add a new iterator
class LoopRepeatingTopologicalSortIterator that differs from
the RepeatingTopologicalSortIterator by repeating only loops
and repeating them early. It returns to the loop head if the
head needs recalculation when we reach the end of the loop.

In GVN, use the new loop-repeating topological sort iterator
and for a loop head merge only the preceding blocks' LVNs
if we're not currently recalculating this loop.

Also fix LocalValueNumbering::InPlaceIntersectMaps() which
was keeping only the last element of the intersection, avoid
some unnecessary processing during LVN merge and add some
missing braces to MIRGraph::InferTypeAndSize().

Bug: 16398693
Change-Id: I4e10d4acb626a5b8a28ec0de106a7b37f9cbca32
acb4eb12108d5890bf722bed91f2e80708af0c75 17-Jul-2014 Vladimir Marko <vmarko@google.com> Fix GVN to handle normal paths leading to catch entry.

When the catch block is empty, the catch entry is actually
the normal path block after the try block. Fix the LVN
merge for catch entries that didn't expect it during GVN.

Bug: 16360024

(cherry-picked from 11ca61259be6ec8e03eaff1e98905232728b3d45)

Change-Id: Ifc771edfec702ab2f0ff50bf7f8e69c846d13a46
11ca61259be6ec8e03eaff1e98905232728b3d45 17-Jul-2014 Vladimir Marko <vmarko@google.com> Fix GVN to handle normal paths leading to catch entry.

When the catch block is empty, the catch entry is actually
the normal path block after the try block. Fix the LVN
merge for catch entries that didn't expect it during GVN.

Bug: 16360024
Change-Id: I9adfc3445245d3fa3c4809d4df1b7b76fbef5ff2
95a059793c4c194f026afc74c713cc295d75d91a 30-May-2014 Vladimir Marko <vmarko@google.com> Global Value Numbering.

Implement the Global Value Numbering for optimization
purposes. Use it for the null check and range check
elimination as the LVN used to do.

The order of evaluation of basic blocks needs improving as
we currently fail to recognize some obviously identical
values in methods with more than one loop. (There are three
disabled tests that check this. This is just a missed
optimization, not a correctness issue.)

Change-Id: I0d0ce16b2495b5a3b17ad1b2b32931cd69f5a25a
f418f3227e0001c8d75257ceff0c248cc406d81a 09-Jul-2014 Vladimir Marko <vmarko@google.com> Handle potential <clinit>() correctly in LVN.

Bug: 16177324
Change-Id: I727ab6ce9aa9a608fe570cf391a6b732a12a8655
ffddfdf6fec0b9d98a692e27242eecb15af5ead2 03-Jun-2014 Tim Murray <timmurray@google.com> DO NOT MERGE

Merge ART from AOSP to lmp-preview-dev.

Change-Id: I0f578733a4b8756fd780d4a052ad69b746f687a9
2ac01fc279e8397beacf90302b0f215040eb78fa 22-May-2014 Vladimir Marko <vmarko@google.com> Improve tracking of memory locations in LVN.

Rewrite the tracking of values stored in memory to allow
recognizing the same value after storing it in memory and
loading it back to vreg. Drop reliance on value name
ordering for memory versioning in preparation for GVN.

Also fix a few minor issues in LVN.

Change-Id: Ifabe2d47d669d9ec43942cea6fd157e41af77ec8
b3e527b2a9ee28ecaba2045f4415b00c8b395039 04-Apr-2014 Vladimir Marko <vmarko@google.com> Clean up special method inlining.

Mark inlined getter/setter INVOKEs as NOP to allow implicit
null checks (SIGSEGV-based) rather than the explicit checks
in GenInvoke().

Avoid inlining wide setter and returning wide argument if
the wide source is not in consecutive dalvik registers in
INVOKE. This is valid dalvik bytecode and we should treat it
correctly even if we're currently unaware of any tools that
would generate such INVOKEs.

Remove bogus MIR_INLINED checks from LVN.

Change-Id: I7e75a832fcf9bd0550e21b1c8b3813c6166197dd
ee40aa4650d7d000335ccfcb2fbb742acfb1f1c3 24-Mar-2014 nikolay serdjuk <nikolay.y.serdjuk@intel.com> An argument is handled incorrectly for add-int/lit8 during optimization phase

Dalvik instruction 'add-int/lit8' stores a constant in the third parameter.
But during optimization phase the compiler reads the constant from the
second parameter. This is incorrect because it leads to wrong decision that
no array bound checks are needed in our test case. As a consequence it
fails with SIGSEGV because of accessing elements which are beyond the bounds.

Change-Id: I653892514934046d31a9e4d206d9d95ebb6267ab
Signed-off-by: nikolay serdjuk <nikolay.y.serdjuk@intel.com>
9820b7c1dc70e75ad405b9e6e63578fa9fe94e94 02-Jan-2014 Vladimir Marko <vmarko@google.com> Early inlining of simple methods.

Inlining "special" methods: empty methods, methods returning
constants or their arguments, simple getters and setters.

Bug: 8164439
Change-Id: I8c7fa9c14351fbb2470000b378a22974daaef236
be0e546730e532ef0987cd4bde2c6f5a1b14dd2a 26-Feb-2014 Vladimir Marko <vmarko@google.com> Cache field lowering info in mir_graph.

Change-Id: I9f9d76e3ae6c31e88bdf3f59820d31a625da020f
9c86a0279aaf953377aa9e2277592e68bf814989 21-Feb-2014 Ian Rogers <irogers@google.com> Revert "Annotate used fields."

This reverts commit 7f6cf56942c8469958b273ea968db253051c5b05.

Change-Id: Ic389a194c3404ecb5bb563a405bf4a0d6336ea0d
f59f18b2bd5432bb083205680c69fe64aaf60f39 17-Feb-2014 Vladimir Marko <vmarko@google.com> Fix and rewrite local value numbering.

Fix memory versioning to take aliasing and method calls
into account. Use more instructions for the null check
elimination. Return the local value name of the register
defined by the instruction if applicable.

Change-Id: I4560bc680ae1ad553a7a00fa092c937e3da9fbbe
4376c87eb45b287fad77a16738e76ba28956ab7d 23-Jan-2014 Vladimir Marko <vmarko@google.com> Remove the link from dalvik instruction back to kMirOpCheck.

Free the MIR::meta for another use on PUT/GET instructions.

Change-Id: Ic5a5cc5026e2076031d7b8ce7f2b36c185bfc93a
c6dbf900f797aa7461d50dc4e6a996f067b97203 24-Jan-2014 Ian Rogers <irogers@google.com> Revert "Remove the link from dalvik instruction back to kMirOpCheck."

This reverts commit 8a3e7e769de02b5b412163cf70da9b9fbaf3b848.

Change-Id: I03a0d6180c350569b39cee2ea194903dbdfca963
8a3e7e769de02b5b412163cf70da9b9fbaf3b848 23-Jan-2014 Vladimir Marko <vmarko@google.com> Remove the link from dalvik instruction back to kMirOpCheck.

Free the MIR::meta for another use on PUT/GET instructions.

Change-Id: I39ee5122227f449212cf6960e11b9561b8a6de7b
17189ac098b2f156713db1821b49db7b2f018bbe 08-Nov-2013 buzbee <buzbee@google.com> Quick compiler compile-time/memory use improvement

This CL delivers a surprisingly large reduction in compile time,
as well as a significant reduction in memory usage by conditionally
removing a CFG construction feature introduced to support LLVM
bitcode generation.

In short, bitcode requires all potential exception edges to be
explicitly present in the CFG. The Quick compiler (based on the
old JIT), can ignore, at least for the purposes of dataflow
analysis, potential throw points that do not have a corresponding
catch block.

To support LLVM, we create a target basic block for every
potentially throwing instruction to give us a destination for
the exception edge. Then, following the check elimination pass,
we remove blocks whose edges have gone away.

However, if we're not using LLVM, we can skip the creation of
those things in the first place. The savings are significant.

Single-threaded compilation time on the host looks to be reduced
by something in the vicinity of 10%. We create roughly 60% fewer
basic blocks (and, importantly, the creation of fewer basic
block nodes has a multiplying effect on memory use reduction
because it results in fewer dataflow bitmaps).

Some basic block redution stats:

boot: 2325802 before, 844846 after.
Phonesky: 485472 before, 156014 after.
PlusOne: 806232 before, 243156 after.
Thinkfree: 864498 before, 264858 after.

Another nice side effect of this change is giving the basic
block optimization pass generally larger scope.

For arena memusage in the boot class path (compiled on the host):

Average Max
Before: 50,863 88,017,820
After: 41,964 4,914,208

The huge reduction in max arena memory usage is due to the
collapsing of a large initialization method. Specifically, with complete
exception edges org.ccil.cowan.tagsoup.Scheme requires 13,802
basic blocks. With exception edges collapsed, it requires 4.

This change also caused 2 latent bugs to surface.

1) The dex parsing code did not expect that the target of a switch statement
could reside in the middle of the same basic block ended by that same switch
statement.

2) The x86 backend introduced a 5-operand LIR instruction for indexed memops.
However, there was no corresponding change to the use/def mask creation code.
Thus, the 5th operand was never included in the use/def mask. This allowed
the instruction scheduling code to incorrectly move a use above a definition.
We didn't see this before because the affected x86 instructions were only used
for aget/aput, and prior to this CL those Dalvik opcodes caused a basic
block break because of the implied exception edge - which prevented the code
motion.

And finally, also included is some minor tuning of register use weighting.

Change-Id: I3f2cab7136dba2bded71e9e33b452b95e8fffc0e
0cd7ec2dcd8d7ba30bf3ca420b40dac52849876c 18-Jul-2013 Brian Carlstrom <bdc@google.com> Fix cpplint whitespace/blank_line issues

Change-Id: Ice937e95e23dd622c17054551d4ae4cebd0ef8a2
2ce745c06271d5223d57dbf08117b20d5b60694a 18-Jul-2013 Brian Carlstrom <bdc@google.com> Fix cpplint whitespace/braces issues

Change-Id: Ide80939faf8e8690d8842dde8133902ac725ed1a
7940e44f4517de5e2634a7e07d58d0fb26160513 12-Jul-2013 Brian Carlstrom <bdc@google.com> Create separate Android.mk for main build targets

The runtime, compiler, dex2oat, and oatdump now are in seperate trees
to prevent dependency creep. They can now be individually built
without rebuilding the rest of the art projects. dalvikvm and jdwpspy
were already this way. Builds in the art directory should behave as
before, building everything including tests.

Change-Id: Ic6b1151e5ed0f823c3dd301afd2b13eb2d8feb81