Re: How to eliminate redundant constant move instructions

On Mon, 7 Nov 2011 17:33:29 -0800 (PST), amker <amker.cheng@gmail.com>
wrote:


>On Nov 5, 5:26 am, George Neuner <gneun...@comcast.net> wrote:
>
>> 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.
>
>Yes, I guess it is the variable value tracking. But I think GCC does
>do such work in some passes, at least cse.c. In this pass gcc records
>the constant value if a quantity has a known constant value.


Common subexpression elimination would not help in the case in
question ... the temporaries containing the same values all belong to
different expressions. There is nothing common to find.




>Unfortunately, cse only works on basis of extended basic block.
>Nothing it can do for global cases as reported in mentioned bug.


Yes. But the code in question all was in a single function, so the
range of CSE was not the problem.


The only simple remedy I see - and it's not so simple - would be to
make a pass tracking register values by following constant load and
copy instructions. You need to keep track of register update
locations so that in places where multiple registers contain the same
value, you can identify the "primary" copy - i.e. the register holding
the oldest copy of the value. Then when you see a use of a younger
copy, you rewrite it to use the primary copy instead.


But you have to be careful - a local optimization can't make
assumptions about register contents on entry to a function. You also
have to be careful with registers whose contents may change across
functions calls.


Ultimately, though, the value of such an optimization may be quite
limited. If you successfully eliminate a particular use of a register
in some location, then you may also need to eliminate useless
saves/reload of that register across lower function calls. You may be
able to avoid the useless saves/reloads in the first place by doing
the optimization on the RTL prior to register allocation ... but RTL
has an unlimited numbers of registers, so the bookkeeping is much
easier if you wait until after register allocation. But then you need
to process the lower level functions as well (which may not be
possible if they are in a different compilation unit).




>Also, could you point me some papers of implementation of such
>variable value tracking technique? I googled and found nothing
>about it.
>
>Thanks




A lot of optimizations have fairly obvious implementations (at least a
brute force version) when you think about them and so it can be hard
to find papers that take you step by step. Many discussions of
optimization simply assume you can figure out how to do whatever it is
from the description.


I've never seen any papers regarding this particular register level
optimization, nor have I seen it mentioned in books ... I don't recall
where it was that I learned about it. However, a search on
"redundancy elimination" at http://www.codeopt.com/ turned up a few
interesting looking titles.


George

Return to the comp.compilers page.
Search the comp.compilers archives again.