optimize: only write to state when clearing optimizer data

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.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
optimize: track nonzero bits of registers

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.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
optimize: optimize using nonzero bits

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>
tcg-i386: use LEA for 3-operand 64-bit addition

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
tcg: support spilling a constant directly to memory

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
tcg-i386: support spilling a constant directly to memory

Spilling temporaries is a very frequent operation (up to 5% of the generated
assembly instructions are spill) and can be sped up a lot for i386.  The
generic TCG support in the previous patch is put to use here, using the
"mov Ev, Iz" encoding to avoid allocating a register for signed 32-bit
vlaues.  This saves a register and 1 or 2 bytes, for a 3-4% speedup.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
optimize: rewrite find_better_copy

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
optimize: prefer globals that have been written to

This will remove loads from env.  Code size improves only by ~0.5%, but
speedups can be as good as 10%.

Example:

input assembly:

 add    $0x8,%rbp
 cmp    %r12,%rbp

before

 movi_i64 tmp12,$0x8
 add_i64 rbp,rbp,tmp12              mov    0x28(%r14),%rbp
                                    add    $0x8,%rbp
 mov_i64 cc_dst,rbp                 mov    %rbp,%rbx
 mov_i64 cc_src,r12                 mov    0x60(%r14),%rbx
 sub_i64 cc_dst,rbp,r12             mov    %rbp,%r12
                                    mov    0x60(%r14),%r13
                                    sub    %r13,%r12
 add_i64 tmp0,cc_dst,cc_src         lea    (%r12,%rbx,1),%r15

After:

 movi_i64 tmp12,$0x8
 add_i64 rbp,rbp,tmp12              mov    0x28(%r14),%rbp
                                    add    $0x8,%rbp
 mov_i64 cc_dst,rbp                 mov    %rbp,%rbx
 mov_i64 cc_src,r12                 mov    0x60(%r14),%r12
 sub_i64 cc_dst,cc_dst,cc_src       sub    %r12,%rbx
 add_i64 tmp0,cc_dst,cc_src         lea    (%rbx,%r12,1),%r13

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
i386: use gen_op for cmps/scas

Replace low-level ops with a higher-level "cmp %al, (A0)" in the case
of scas, and "cmp T0, (A0)" in the case of cmps.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
i386: add arguments to gen_op_update1_cc and gen_op_update2_cc

Right now these are always T0 and T1, but this will change.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
i386: update CC_SRC before doing the operation

This is a requirement for the next patch, for the case where T0 and T1
are the same register.  CC_SRC has to be updated before the source is
clobbered.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
i386: avoid cpu_T[] in gen_op

Pass the register directly for the second operand, and skip the move to T0
inside gen_op for the first.  This enables more peephole optimization in
gen_op.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
i386: move xor reg, reg optimization to gen_op

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
i386: optimize sbb reg, reg

The most common occurrence of sbb is just "splatting" the carry flag
all over the destination register.  This does not need to go to
CC_OP_DYNAMIC, and also the computation of the flags is much simpler.

If the op were CC_OP_SUBx, we know CC_DST is 0 hence src1 = src2 = CC_SRC.

    cf = 0 = CC_DST & 0x1
    af = 0 = CC_DST & 0x10
    zf = 1 = ~CC_DST & 0x40
    sf = 0 = CC_DST & 0x80

If the op were CC_OP_SBBx, we know CC_DST is -1 hence again src1 = src2 =
CC_SRC:

    cf = 1 = CC_DST & 0x1
    af = 1 = CC_DST & 0x10
    zf = 0 = ~CC_DST & 0x40
    sf = 1 = CC_DST & 0x80

And in both cases:

    pf = 1
    of = lshift((src1 ^ CC_DST), 12 - DATA_BITS) & CC_O;

Hence a new CC_OP is added that performs the above computation.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>