Re: Copy propagation optimization

Thank you for your answer.


By the way, i think i need to ask in another level.


Doubt #1:
---------


(snip)


What you're describing has nothing to do with copy propagation


(snip end)


Do you mean that copy propagation is only to dealt with the variables
and not with result of expressions like below?


(snip)


gsiVarA = gsiVarB + gsiVarC;


gsiVarB = 1 ; // One of expression's operand is redefined


gsiVarD = gsiVarA ; // Statement-B, The expression's result can be used.


(snip end)


Doubt #2:
---------


As explained, the compiler can perform such optimization in register
allocation. But why cannot it perform in intermediate level itself.


For example, if the compiler is developed with DAG (Direct Acyclic
Graph) as intermediate representation, such optimization can be
performed while processing DAG node itself. Am i right?




Doubt #3:
---------


The optimization explained is performed even though the operand of
expression is redefined before its usage. Is it safe in all cases even
involving pointers?




Doubt #4:
---------


Consider the below test program


(snip)


int gsiVarA, gsiVarB = 0, gsiVarD, gsiVarC;


int *gsiPtr;


void vfnTestGlobalPointer()
{
        int lsiVarA;


        gsiPtr = &lsiVarA ;


        lsiVarA = gsiVarB + gsiVarC;


        gsiVarB = 1 ;


        gsiVarD = lsiVarA;
}


(snip end)


For the above test program, cl compiler generates the below assembly


Command line option: Default


(snip)


; Line 6
                push ebp
                mov ebp, esp
                push ecx
; Line 9
                lea eax, DWORD PTR _lsiVarA$[ebp]
                mov DWORD PTR _gsiPtr, eax
; Line 11
                mov ecx, DWORD PTR _gsiVarB
                add ecx, DWORD PTR _gsiVarC
                mov DWORD PTR _lsiVarA$[ebp], ecx ;; <== (A)
; Line 13
                mov DWORD PTR _gsiVarB, 1
; Line 15
                mov edx, DWORD PTR _lsiVarA$[ebp] ;; <== (B)
                mov DWORD PTR _gsiVarD, edx
; Line 16
                mov esp, ebp
                pop ebp
                ret 0


(snip end)


As seen in the above marked instruction (B), the result of expression
is not reused.


In the marked instruction (A), the expression is computed. But in the
marked instruction (B), the variable "lsiVarA" is again taken in move
instruction instead of previous result.


As discussed, is the above code unoptimal?


Thanks and regards,
Kannan


-----Original Message-----
From: Giridhar S <thisisgiri@gmail.com>
Sent: Fri, 7 Aug 2009 12:03 am
Subject: Re: Copy propagation optimization


What you're describing has nothing to do with copy propagation - but
it's related to register allocation. It is very likely that most
compilers today will do what you're expecting, by default, even
without any optimization turned on. The span of instructions from the
point where gsiVarA is defined to the point where gsiVarA is last used
(let's assume statement B is the last use) defines the live range of
the variable - and the compiler tries very hard to ensure that every
variable lives in a register for the duration of it's live-range, in
order to avoid multiple trips to memory.


Of course, if the register pressure is very high within the live range
of the variable, the compiler maybe forced to spill the register to
memory and reload it upon next use - and this varies based on the
register allocation/spilling algorithm used by the compiler and a
bunch of other related issues.


HTH,


On Thu, Aug 6, 2009 at 2:45 AM, <rajeshkannanb@aol.in> wrote:
> Dear all,
>
> Please clarify my doubt regarding copy propagation optimization.
>
> (snip)
>
> gsiVarA = gsiVarB + gsiVarC;
>
> gsiVarB = 1 ; // One of expression's operand
> is
> redefined
>
> gsiVarD = gsiVarA ; // Statement-B
>
> (snip end)
>
> As shown in the above snip, can the compiler use the result of
> expression
> (gsiVarB + gsiVarC) in Statement B instead of gsiVarA.
>
> I expect the below result
>
> (snip)
>
> gsiVarA = gsiVarB + gsiVarC;
>
> load R1, gsiVarB
> load R2, gsiVarC
> Add R1, R2
> Store R1, R3
>
> .... // gsiVarB is redefined.
> ....
>
> gsiVarD = gsiVarA ; // Statement-B
>
> Store R1, gsiVarD // Result of expression is used.
>
> (snip end)
>
> Please clarify whether the compiler can perform the above
optimization.
>
> Thanks and regards,
> Kannan
>






________________________________________________________________________
You are invited to Get a Free AOL Email ID. - http://webmail.aol.in

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