Re: How to eliminate redundant constant move instructions

From	George Neuner <gneuner2@comcast.net>
Newsgroups	comp.compilers
Subject	Re: How to eliminate redundant constant move instructions
Date	2011-11-04 17:26 -0400
Organization	A noiseless patient Spider
Message-ID	<11-11-025@comp.compilers> (permalink)
References	<11-10-019@comp.compilers> <11-11-004@comp.compilers> <11-11-009@comp.compilers>

Show all headers | View raw

On Tue, 1 Nov 2011 19:21:54 -0700 (PDT), amker <can.finner@gmail.com>
wrote:

>On Nov 2, 2:32 am, George Neuner <gneun...@comcast.net> wrote:
>> On Mon, 31 Oct 2011 17:53:46 +0800, "Amker.Cheng" <amker.ch...@gmail.com> wrote:
>> >I found following intermediate codes are generated in gcc
>>
>> >rx <- 0
>> >...
>> >use rx
>> >...
>> >ry <- 0
>> >use ry
>> >...
>>
>>
>... the test case showed at:
>http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44025
>which is actually a reported gcc bug.

Ok.  That bug was reported for ARM7 thumb code.  I'm not familiar with
ARM assembler (had to look up the instructions), but I do see that R0
already holds the proper value when R3 is loaded - which I presume is
what you are talking about.

But I don't necessarily agree that it is a bug.  It's definitely not
optimal code, but R0 and R3 represent different temporary variables,
so it's hard to see how any of value numbering, constant propagation
or register allocation is at fault.

>> GCC doesn't really perform a separate constant propagation
>> optimization ... instead it generically tracks use of values to (try
>> to) minimize redundant loads.  There is a separate optimization,
>> -fcprop-register, which is a peephole pass that eliminates redundant
>> register moves (introduced by other optimizations), but that is
>> performed after register allocation.
>
>Yes, I have noticed this pass. Seems it can solve the problem if I
>can:
>1, extend the pass in value numbering way, at least for const values.
>2, extend the pass in global data analysis way.

Yes.  But value numbering doesn't know or care what specific value is
in the register - it cares only whether the value in the register
might have been changed between read uses.

Variable value tracking is the related technique used for constant
propagation.  However what you are after is variable equivalence
testing - I don't think GCC even tries to do this.

>> You might be asking "if the value already is in a register, why not
>> just use it rather than load a second register?"  The answer to that
>> likely is a scheduling issue which depends on the use of the first
>> register.  You have to remember that many CPUs can execute multiple
>> instructions in parallel, and those parallel instruction streams may
>> be executed out of order with respect to a program listing.
>>
>> On most CPUs loading an immediate constant is as cheap as a register
>> move.  Also, loading a constant ties up only the target register
>> whereas a move ties up both target and source registers.
>
>Yes, This is the point I missed. So even if the codes are optimized into:
>
>rx <- 0
>...
>use rx
>...
>use rx
>
>It might be worse than original codes considering out-of-order and
>parallel execution.  In this way, how should I know for sure which case
>is better?

You can't know without trying it.  If the target CPU is known, the
compiler could simulate execution of the code sequence to try out
logically equivalent approaches.  But most CPU manufacturers don't
even publish instruction times any more - never mind providing enough
information to accurately simulate the chip (emulation is not
simulation).

George

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How to eliminate redundant constant move instructions "Amker.Cheng" <amker.cheng@gmail.com> - 2011-10-31 17:53 +0800
  Re: How to eliminate redundant constant move instructions Kaz Kylheku <kaz@kylheku.com> - 2011-10-31 17:08 +0000
    Re: How to eliminate redundant constant move instructions amker <can.finner@gmail.com> - 2011-11-01 19:01 -0700
    Re: How to eliminate redundant constant move instructions mac <acolvin@efunct.com> - 2011-11-03 02:20 +0000
  Re: How to eliminate redundant constant move instructions George Neuner <gneuner2@comcast.net> - 2011-11-01 14:32 -0400
    Re: How to eliminate redundant constant move instructions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2011-11-01 22:35 +0000
      Re: How to eliminate redundant constant move instructions amker <can.finner@gmail.com> - 2011-11-01 19:35 -0700
      Re: How to eliminate redundant constant move instructions amker <amker.cheng@gmail.com> - 2011-11-01 21:04 -0700
      Re: How to eliminate redundant constant move instructions George Neuner <gneuner2@comcast.net> - 2011-11-02 12:38 -0400
        Re: How to eliminate redundant constant move instructions Kaz Kylheku <kaz@kylheku.com> - 2011-11-03 03:20 +0000
          Re: How to eliminate redundant constant move instructions George Neuner <gneuner2@comcast.net> - 2011-11-04 13:27 -0400
            Re: How to eliminate redundant constant move instructions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2011-11-04 21:19 +0000
        Re: How to eliminate redundant constant move instructions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2011-11-03 03:32 +0000
    Re: How to eliminate redundant constant move instructions amker <can.finner@gmail.com> - 2011-11-01 19:21 -0700
      Re: How to eliminate redundant constant move instructions George Neuner <gneuner2@comcast.net> - 2011-11-04 17:26 -0400
        Re: How to eliminate redundant constant move instructions amker <amker.cheng@gmail.com> - 2011-11-07 17:33 -0800
          Re: How to eliminate redundant constant move instructions Wei-Jen Chen <chenwj@cs.NCTU.edu.tw> - 2011-11-10 08:04 +0000
          Re: How to eliminate redundant constant move instructions George Neuner <gneuner2@comcast.net> - 2011-11-10 18:18 -0500
    Re: How to eliminate redundant constant move instructions amker <amker.cheng@gmail.com> - 2011-11-01 20:58 -0700

csiph-web