 |
|
| Computers Forum Index » Computer Compilers » Copy propagation optimization... |
|
Page 1 of 1 |
|
| Author |
Message |
| ... |
 Posted: Thu Aug 06, 2009 10:45 am |
|
|
|
Guest
|
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 |
|
|
| Back to top |
|
|
|
| Giridhar S... |
| Posted: Thu Aug 06, 2009 10:33 pm |
|
|
|
Guest
|
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 at (no spam) aol.in> wrote:
Quote: 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.
Thanks and regards,
Kannan |
|
|
| Back to top |
|
|
|
| News Subsystem... |
| Posted: Fri Aug 07, 2009 12:05 pm |
|
|
|
Guest
|
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 at (no spam) 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 at (no spam) aol.in> wrote:
Quote: 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 |
|
|
| Back to top |
|
|
|
| Fernando... |
| Posted: Fri Aug 07, 2009 12:20 pm |
|
|
|
Guest
|
On Aug 6, 3:45 am, rajeshkann... at (no spam) aol.in wrote:
Quote: 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
Hi, Kannan,
the code you wrote looks fine to me. However, I think that is not
really called copy propagation. You would have copy propagation if,
for instance, you had:
gsiVarC = ...
gsiVarB = gsiVarA // this is a copy
gsiVarD = gsiVarC + gsiVarB
- The optimization would yield:
gsiVarC = ...
gsiVarD = gsiVarC + gsiVarA // the result of the copy is used instead.
Going back to your code, notice that once you redefine gsiVarB, it
is like if you had a completely new variable. This issue becomes much
clearer when you have the code in SSA form. In this case, each
variable is define at most once.
Fernando |
|
|
| Back to top |
|
|
|
| kamal... |
| Posted: Tue Aug 25, 2009 11:51 am |
|
|
|
Guest
|
On Aug 7, 5:20 pm, Fernando <prone... at (no spam) gmail.com> wrote:
Quote: On Aug 6, 3:45 am, rajeshkann... at (no spam) aol.in wrote:
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
this is constant propagation, which is a subset of copy propagation.
Quote: 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.
the code you wrote looks fine to me. However, I think that is not
really called copy propagation. You would have copy propagation if,
for instance, you had:
gsiVarC = ...
gsiVarB = gsiVarA // this is a copy
gsiVarD = gsiVarC + gsiVarB
- The optimization would yield:
gsiVarC = ...
gsiVarD = gsiVarC + gsiVarA // the result of the copy is used instead.
this is copy propagation. The OP wanted to know whether this would be
implemented in a compiler by default. The answer is that it depends on
the compiler and the optimization level one opts for. GNU C implements
this at +O1.
http://gcc.gnu.org/onlinedocs/gcc-4.4.1/gcc/Optimize-Options.html#Optimize-Op
tions
regards
-kamal |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Wed Nov 25, 2009 12:31 am
|
|