summaryrefslogtreecommitdiff
path: root/tcg/optimize.c
AgeCommit message (Collapse)AuthorFilesLines
2013-12-02misc: Use new rotate functionsStefan Weil1-8/+4
Signed-off-by: Stefan Weil <sw@weilnetz.de> (cherry picked from commit 3df2b8fde949be86d8a78923c992fdd698d4ea4c) Signed-off-by: Michael Roth <mdroth@linux.vnet.ibm.com>
2013-05-09tcg/optimize: fix setcond2 optimizationAurelien Jarno1-0/+1
When setcond2 is rewritten into setcond, the state of the destination temp should be reset, so that a copy of the previous value is not used instead of the result. Reported-by: Michael Tokarev <mjt@tls.msk.ru> Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2013-03-23tcg-optimize: Fold sub r,0,x to neg r,xRichard Henderson1-1/+33
Cc: Blue Swirl <blauwirbel@gmail.com> Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2013-02-23tcg: Add signed multiword multiplication operationsRichard Henderson1-0/+1
Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2013-02-23tcg: Add 64-bit multiword arithmetic operationsRichard Henderson1-2/+2
Matching the 32-bit multiword arithmetic that we already have. Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2013-01-19optimize: optimize using nonzero bitsPaolo Bonzini1-2/+28
This adds two optimizations using the non-zero bit mask. In some cases involving shifts or ANDs the value can become zero, and can thus be optimized to a move of zero. Second, useless zero-extension or an AND with constant can be detected that would only zero bits that are already zero. The main advantage of this optimization is that it turns zero-extensions into moves, thus enabling much better copy propagation (around 1% code reduction). Here is for example a "test $0xff0000,%ecx + je" before optimization: mov_i64 tmp0,rcx movi_i64 tmp1,$0xff0000 discard cc_src and_i64 cc_dst,tmp0,tmp1 movi_i32 cc_op,$0x1c ext32u_i64 tmp0,cc_dst movi_i64 tmp12,$0x0 brcond_i64 tmp0,tmp12,eq,$0x0 and after (without patch on the left, with on the right): movi_i64 tmp1,$0xff0000 movi_i64 tmp1,$0xff0000 discard cc_src discard cc_src and_i64 cc_dst,rcx,tmp1 and_i64 cc_dst,rcx,tmp1 movi_i32 cc_op,$0x1c movi_i32 cc_op,$0x1c ext32u_i64 tmp0,cc_dst movi_i64 tmp12,$0x0 movi_i64 tmp12,$0x0 brcond_i64 tmp0,tmp12,eq,$0x0 brcond_i64 cc_dst,tmp12,eq,$0x0 Other similar cases: "test %eax, %eax + jne" where eax is already 32-bit (after optimization, without patch on the left, with on the right): discard cc_src discard cc_src mov_i64 cc_dst,rax mov_i64 cc_dst,rax movi_i32 cc_op,$0x1c movi_i32 cc_op,$0x1c ext32u_i64 tmp0,cc_dst movi_i64 tmp12,$0x0 movi_i64 tmp12,$0x0 brcond_i64 tmp0,tmp12,ne,$0x0 brcond_i64 rax,tmp12,ne,$0x0 "test $0x1, %dl + je": movi_i64 tmp1,$0x1 movi_i64 tmp1,$0x1 discard cc_src discard cc_src and_i64 cc_dst,rdx,tmp1 and_i64 cc_dst,rdx,tmp1 movi_i32 cc_op,$0x1a movi_i32 cc_op,$0x1a ext8u_i64 tmp0,cc_dst movi_i64 tmp12,$0x0 movi_i64 tmp12,$0x0 brcond_i64 tmp0,tmp12,eq,$0x0 brcond_i64 cc_dst,tmp12,eq,$0x0 In some cases TCG even outsmarts GCC. :) Here the input code has "and $0x2,%eax + movslq %eax,%rbx + test %rbx, %rbx" and the optimizer, thanks to copy propagation, does the following: movi_i64 tmp12,$0x2 movi_i64 tmp12,$0x2 and_i64 rax,rax,tmp12 and_i64 rax,rax,tmp12 mov_i64 cc_dst,rax mov_i64 cc_dst,rax ext32s_i64 tmp0,rax -> nop mov_i64 rbx,tmp0 -> mov_i64 rbx,cc_dst and_i64 cc_dst,rbx,rbx -> nop Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2013-01-19optimize: track nonzero bits of registersPaolo Bonzini1-22/+110
Add a "mask" field to the tcg_temp_info struct. A bit that is zero in "mask" will always be zero in the corresponding temporary. Zero bits in the mask can be produced from moves of immediates, zero-extensions, ANDs with constants, shifts; they can then be be propagated by logical operations, shifts, sign-extensions, negations, deposit operations, and conditional moves. Other operations will just reset the mask to all-ones, i.e. unknown. [rth: s/target_ulong/tcg_target_ulong/] Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2013-01-19optimize: only write to state when clearing optimizer dataPaolo Bonzini1-5/+14
The next patch will add to the TCG optimizer a field that should be non-zero in the default case. Thus, replace the memset of the temps array with a loop. Only the state field has to be up-to-date, because others are not used except if the state is TCG_TEMP_COPY or TCG_TEMP_CONST. [rth: Extracted the loop to a function.] Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2012-11-17TCG: Use gen_opc_buf from context instead of global variable.Evgeny Voevodin1-31/+31
Signed-off-by: Evgeny Voevodin <e.voevodin@samsung.com> Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2012-10-28tcg: rework TCG helper flagsAurelien Jarno1-1/+2
The current helper flags, TCG_CALL_CONST and TCG_CALL_PURE might be confusing and doesn't provide enough granularity for some helpers (FP helpers for example). This patch changes them into the following helpers flags: - TCG_CALL_NO_READ_GLOBALS means that the helper does not read globals, either directly or via an exception. They will not be saved to their canonical location before calling the helper. - TCG_CALL_NO_WRITE_GLOBALS means that the helper does not modify any globals. They will only be saved to their canonical locations before calling helpers, but they won't be reloaded afterwise. - TCG_CALL_NO_SIDE_EFFECTS means that the call to the function is removed if the return value is not used. It provides convenience flags, to avoid helper definitions longer than 80 characters. It also provides compatibility flags, and updates the documentation. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-10-17tcg: Optimize mulu2Richard Henderson1-0/+26
Like add2, do operand ordering, constant folding, and dead operand elimination. The latter happens about 15% of all mulu2 during an x86_64 bios boot. Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-10-17tcg: Constant fold add2 and sub2Richard Henderson1-0/+35
Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-10-17tcg: Do constant folding on double-word comparisonsRichard Henderson1-21/+72
Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-10-17tcg: Split out subroutines from do_constant_folding_condRichard Henderson1-71/+81
We can re-use these for implementing double-word folding. Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-10-17tcg: Optimize double-word comparisons against zeroRichard Henderson1-0/+39
Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-10-17tcg: Use common code when failing to optimizeRichard Henderson1-59/+32
This saves a whole lot of repetitive code sequences. Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-10-17tcg: Swap commutative double-word comparisonsRichard Henderson1-0/+26
Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-10-17tcg: Canonicalize add2 operand orderingRichard Henderson1-0/+5
Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-10-17tcg: Split out swap_commutative as a subroutineRichard Henderson1-32/+24
Reduces code duplication and prefers movcond d, c1, c2, const, s to movcond d, c1, c2, s, const It also prefers add r, r, c over add r, c, r when both inputs are known constants. This doesn't matter for true add, as we will fully constant fold that. But it matters for a follow-on patch using this routine for add2 which may not be fully foldable. Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-10-06tcg: Add TCG_COND_NEVER, TCG_COND_ALWAYSRichard Henderson1-0/+6
There are several cases that can be handled easier inside both translators and code generators if we have out-of-band values for conditions. It's easy enough to handle ALWAYS and NEVER in the natural way inside the tcg middle-end. Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-22tcg/optimize: add constant folding for depositAurelien Jarno1-0/+20
Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-22tcg/optimize: prefer the "op a, a, b" form for commutative opsAurelien Jarno1-1/+4
The "op a, a, b" form is better handled on non-RISC host than the "op a, b, a" form, so swap the arguments to this form when possible, and when b is not a constant. This reduces the number of generated instructions by a tiny bit. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-22tcg/optimize: further optimize brcond/movcond/setcondAurelien Jarno1-51/+76
When both argument of brcond/movcond/setcond are the same or when one of the two values is a constant equal to zero, it's possible to do further optimizations. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-22tcg/optimize: optimize "op r, a, a => movi r, 0"Aurelien Jarno1-0/+16
Now that it's possible to detect copies, we can optimize the case the "op r, a, a => movi r, 0". This helps in the computation of overflow flags when one of the two args is 0. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-22tcg/optimize: optimize "op r, a, a => mov r, a"Aurelien Jarno1-1/+1
Now that we can easily detect all copies, we can optimize the "op r, a, a => mov r, a" case a bit more. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-22tcg/optimize: do copy propagation for all operationsAurelien Jarno1-2/+9
It is possible to due copy propagation for all operations, even the one that have side effects or clobber arguments (it only concerns input arguments). That said, the call operation should be handled differently due to the variable number of arguments. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-22tcg/optimize: rework copy progagationAurelien Jarno1-75/+92
The copy propagation pass tries to keep track what is a copy of what and what has copy of what, and in addition it keep a circular list of of all the copies. Unfortunately this doesn't fully work: a mov from a temp which has a state "COPY" changed it into a state "HAS_COPY". Later when this temp is used again, it is considered has not having copy and thus no propagation is done. This patch fixes that by removing the hiearchy between copies, and thus only keeping a "COPY" state both meaning "is a copy" and "has a copy". The decision of which copy to use is deferred to the actual temp replacement. At this stage there is not one best choice to do, but only better choices than others. For doing the best choice the operation would have to be parsed in reversed to know if a temp is going to be used later or not. That what is done by the liveness analysis. At this stage it is known that globals will be always live, that local temps will be dead at the end of the translation block, and that the temps will be dead at the end of the basic block. This means that this stage should try to replace temps by local temps or globals and local temps by globals. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-22tcg/optimize: check types in copy propagationAurelien Jarno1-10/+8
The copy propagation doesn't check the types of the temps during copy propagation. However TCG is using the mov_i32 for the i64 to i32 conversion and thus the two are not equivalent. With this patch tcg_opt_gen_mov() doesn't consider two temps of different type as copies anymore. So far it seems the optimization was not aggressive enough to trigger this bug, but it will be triggered later in this series once the copy propagation is improved. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-22tcg/optimize: remove TCG_TEMP_ANYAurelien Jarno1-6/+5
TCG_TEMP_ANY has no different meaning than TCG_TEMP_UNDEF, so use the later instead. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-21tcg: Optimize two-address commutative operationsRichard Henderson1-1/+14
While swapping constants to the second operand, swap sources matching destinations to the first operand. Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-21tcg: Optimize movcond for constant comparisonsRichard Henderson1-0/+40
Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-19tcg/optimize: fix end of basic block detectionAurelien Jarno1-13/+9
Commit e31b0a7c050711884ad570fe73df806520953618 fixed copy propagation on 32-bit host by restricting the copy between different types. This was the wrong fix. The real problem is that the all temps states should be reset at the end of a basic block. This was done by adding such operations in the switch, but brcond2 was forgotten (that's why the crash was only observed on 32-bit hosts). Fix that by looking at the TCG_OPF_BB_END instead. We need to keep the case for op_set_label as temps might be modified through another path. Cc: Blue Swirl <blauwirbel@gmail.com> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-19revert "TCG: fix copy propagation"Aurelien Jarno1-9/+6
Given the copy propagation breakage on 32-bit hosts has been fixed commit e31b0a7c050711884ad570fe73df806520953618 can be reverted. Cc: Blue Swirl <blauwirbel@gmail.com> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-11tcg/optimize: fix if/else/break coding styleAurelien Jarno1-23/+11
optimizer.c contains some cases were the break is appearing in both the if and the else parts. Fix that by moving it to the outer part. Also move some common code there. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-11tcg/optimize: add constant folding for brcondAurelien Jarno1-1/+26
Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-11tcg/optimize: add constant folding for setcondAurelien Jarno1-0/+81
Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-11tcg/optimize: swap brcond/setcond arguments when possibleAurelien Jarno1-0/+18
brcond and setcond ops are not commutative, but it's easy to compute the new condition after swapping the arguments. Try to always put the constant argument in second position like for commutative ops, to help backends to generate better code. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-11tcg/optimize: simplify shift/rot r, 0, a => movi r, 0 casesAurelien Jarno1-0/+20
shift/rot r, 0, a is equivalent to movi r, 0. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-11tcg/optimize: simplify and r, a, 0 casesAurelien Jarno1-0/+1
and r, a, 0 is equivalent to a movi r, 0. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-11tcg/optimize: simplify or/xor r, a, 0 casesAurelien Jarno1-0/+2
or/xor r, a, 0 is equivalent to a mov r, a. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2012-09-11tcg/optimize: split expression simplificationAurelien Jarno1-1/+13
Split expression simplification in multiple parts so that a given op can appear multiple times. This patch should not change anything. Reviewed-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Aurelien Jarno <aurelien@aurel32.net>
2011-08-28TCG: improve optimizer debuggingBlue Swirl1-6/+9
Use enum TCGOpcode instead of plain old int so that the name of current op can be seen in GDB. Add a default case to switch so that GCC does not complain about unhandled enum cases. Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2011-08-21tcg: Constant fold neg, andc, orc, eqv, nand, nor.Richard Henderson1-0/+27
Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2011-08-21tcg: Always define all of the TCGOpcode enum members.Richard Henderson1-134/+22
By always defining these symbols, we can eliminate a lot of ifdefs. To allow this to be checked reliably, the semantics of the TCG_TARGET_HAS_* macros must be changed from def/undef to true/false. This allows even more ifdefs to be removed, converting them into C if statements. Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2011-08-21tcg: Add and use TCG_OPF_64BIT.Richard Henderson1-74/+3
This allows the simplification of the op_bits function from tcg/optimize.c. Signed-off-by: Richard Henderson <rth@twiddle.net> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2011-08-07TCG: fix copy propagationBlue Swirl1-6/+9
Copy propagation introduced in 22613af4a6d9602001e6d0e7b6d98aa40aa018dc considered only global registers. However, register temps and stack allocated locals must be handled differently because register temps don't survive across brcond. Fix by propagating only within same class of temps. Tested-by: Stefan Weil <weil@mail.berlios.de> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2011-07-30TCG: fix breakage by previous patchBlue Swirl1-7/+12
Fix incorrect logic and typos in previous commit 1bfd07bdfe56cea43dbe258dcb161e46b0ee29b7. Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2011-07-30TCG: fix breakage on some RISC hostsBlue Swirl1-13/+115
Fix breakage by a640f03178c22355a158fa9378e4f8bfa4f517a6 and 55c0975c5b358e948b9ae7bd7b07eff92508e756. Some TCG targets don't implement all TCG ops, so make optimizing those conditional. Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2011-07-30Do constant folding for unary operations.Kirill Batuzov1-0/+59
Perform constant folding for NOT and EXT{8,16,32}{S,U} operations. Signed-off-by: Kirill Batuzov <batuzovk@ispras.ru> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2011-07-30Do constant folding for shift operations.Kirill Batuzov1-0/+72
Perform constant forlding for SHR, SHL, SAR, ROTR, ROTL operations. Signed-off-by: Kirill Batuzov <batuzovk@ispras.ru> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
generated by cgit v1.2.1 (git 2.18.0) at 2024-06-22 22:04:07 +0000