Hi Shi,
Your change to force other aliased chi nodes to live in
DSE::Set_Reqruied_CHI() is fine with me. But I'm not comfortable with
your introduction of the _vse_required_set, which I understand is for
finding more dead stores. More below:
On 07/22/2011 01:50 AM, Hui Shi wrote:
Hi Fred,
Follow your suggestion, if one chi node is live, other aliased chi
nodes in same chi_list should live.
I fix this issue in DSE, could you help review this patch?
Fix is:
1. Add hash_set _vse_requried_set in DSE, record if VER_STAB_ENTRY is
once processed by DSE::Set_Required_VSE.
Each vse entry is an SSA version of an aux entry. Thus, from vse to aux
is a many-to-one mapping. Given a vse, vse->Any_use() already tells me
that this vse has once been required. Why do you have to set up this
_vse_required_set, and using DSE::VSE_required() to check the
information that is given by vse->Any_use()? Should it be an aux set
instead of a vse set?
2. In DSE::Set_Required_CHI
1. If chi node is live, find aliased/non-live, once required chi
nodes in same chi list. If find, force these chi nodes live.
If a chi is non-live, then "once required" must be false. So there is a
contradiction here. If your intention is "aux-once-required", there is
still a problem, because the aux may be found to be required later.
Set last_store be NULL and call set_required_vse.
2. If chi node is not live, find aliased chi nodes live in same
chi list. If find, set current chi node live.
3. Remove previous fix in set_required_mu
VER_STAB_ENTRY is required means this AUX symbol's some version is
really used in program.
Using this information, we can exclude mark some AUX symbol's chi node
live, if this AUX is never used.
This is meaningful in following case,
int foo(int a) {
int t1, t2;
int *p;
if(a){
p = &t1;
}
else {
p = &t2;
}
t1 =3;
*p = 5;
return t2;
}
chi nodes live info after original DSE
I4I4LDID 0 <st 20> T<4,.predef_I4,4>
I4INTCONST 0 (0x0)
I4I4NE
U8LDA 0 <st 4> T<53,anon_ptr.,8>
U8LDA 0 <st 5> T<53,anon_ptr.,8>
U8SELECT
U8STID 0 <st 21> T<53,anon_ptr.,8> {line: 1/6} {freq: 0, ln: 6, col: 0}
I4INTCONST 3 (0x3)
I4STID 0 <st 23> T<4,.predef_I4,4> {line: 1/12} {freq: 0, ln: 12, col:
0} // STMT1
sym9v22 <- chi( sym9v19 ) NOT LIVE // default vsym chi is dead.
this statement is dead
I4INTCONST 5 (0x5)
U8U8LDID 0 <st 21> T<53,anon_ptr.,8>
I4ISTORE 0 T<53,anon_ptr.,8> {line: 1/13} {freq: 0, ln: 13, col: 0}
//STMT2
sym4v24 <- chi( sym4v23 ) NOT LIVE // t1 chi node is dead
sym5v25 <- chi( sym5v15 ) LIVE // t2 chi node is live
sym8v26 <- chi( sym8v18 ) LIVE // return vsym chi ndoe is live
sym9v27 <- chi( sym9v22 ) NOT LIVE // default vsym chi is dead
I4I4LDID 0 <st 25> T<4,.predef_I4,4>
I4STID 1 <st 28> T<4,.predef_I4,4> {line: 1/14} {freq: 0, ln: 14, col: 0}
RETURN {line: 1/14} {freq: 0, ln: 14, col: 0}
mu[ sym8v26 sym8v26 ]
If simply mark alias chi node live, default vsym chi ndoe will live in
STMT2, because it's aliased with t2.
Then follow DU chian, default vsym chi nodes in STMT1 is also live.
Cause STMT1 not dead.
Actually, default vsym will not be requried from return vsym or t2's
DU chain.
So we need allow aliased chi nodes not live exist, if this chi node is
never required in DSE analysis.
I consider default vsym as being live at STMT2, because it aliases with
t2. This will cause STMT1 to be live. I understand by keeping the
default vsym non-live, you can delete STMT1. But my intuition is that
making the default vsym non-live (when in fact it is live) will cause
other bugs.
Fred
Regards
Shi Hui
On Tue, Jul 5, 2011 at 5:16 PM, Fred Chow <frdc...@gmail.com
<mailto:frdc...@gmail.com>> wrote:
Hi Shi,
Your fix by calling CODEMAP rename is OK in its own right. But
this fix is in reality for patching up a bug that was introduced
by copy propagation. We should fix the root cause of the problem,
NOT to patch it so the symptom does not appear.
Basically, the following from your original mail:
STMT1
sym2v4 = chi(sym2v3) NOT LIVE
default_vsym_v4 = chi(default_vsym_v3) LIVE
is already wrong. sym2v aliases with the default vsym. Thus, one
cannot be live while the other is dead.
In looking at the code in opt_dse.cxx, I found that it has
diverged a lot from the version that I'm familiar with. Thus, I'm
not in a position to point out what the root problem is. At least
the version I worked with at PathScale does not have this
problem. I would welcome others to provide input on this.
Fred
On 07/04/2011 07:37 PM, Hui Shi wrote:
Hi Fred,
Thanks for your comments.
The reanming happens only when there are some dead phi/chi nodes
revive in CODEMAP::Iload_folded.
To evaluate how this patch will affect compile-time, I add dump
when this renaming happens.
Tested with SPEC2006 base/peak
Following cases have CODEMAP rename after create CODEMAPE, and
renaming count is seldom consider test's PU count..
447.dealII base/peak rename 20+ times
483.xalancbmk base/peak rename 30+ times
416.gamess peak rename 4 times
458.sjeng base rename 1 time.
So this renaming rarely happens and I think we can afford the
increased compile time.
And from another perspective. Rename_CODEMAP is already used in
other phase like aft CGF optimization,
COMP_UNIT::Fold_lda_iload_istore, etc.
These optimizations and renaming are more likely happen.
One utiIity I hope WOPT can have is CODEMAP rename only rename
somve AUX (give in a table or list). Then rename cost can be
decreased a lot.
For copy propagation issue.
The copy propagation happens in Dead_Store_Elminination,
DSE::Propagate_vsym_bb.
To disable the propagation, need change Dead_Store_Elimination.
If one chi node is live,
all other chi nodes binding to same statment and set_required
should live because they are aliased with each other.
This will also cause compile time isuee, because more live
phi/chi node in codrep.
Another issue is though we fix the copy propgation problem, the
revive logical is still there in CODEMAP::Iload_folded.
There still possible dead phi/chi nodes revive in CODEMAP
creation. So complete fix is rename after create CODEMAP.
The main issue is create_codemap not simply create coderep, it
also perform iload folding may change version.
If iload folding function is totolay peformed in
COMP_UNIT::Fold_lda_iload_istore, it has no problem.
Regards
Shi Hui
On Mon, Jul 4, 2011 at 9:26 PM, Fred Chow <frdc...@gmail.com
<mailto:frdc...@gmail.com>> wrote:
Doing renaming is quite compile-time expensive, because it is
like running the SSA construction algorithm. The problem
your mentioned would not have occurred if sym2v3 has not been
propagated down to STMT3. I don't recall we were doing copy
propagation for chi operands. The overlapped live range was
caused by this bad copy propagation, NOT by the ILOAD folding.
The above copy propagation is bad because sym2v4 is NOT dead,
because it aliases with the default vsym which appears in the
mu of STMT2. So your fix should be in preventing the copy
propagation.
Fred
On 06/29/2011 11:35 PM, Hui Shi wrote:
Could gatekeeper help review this fix?
In SSA::Create_CODEMAP ILOAD folding is performed during
coderep setup.
The problem is iload folding may revive some dead phi/chi node.
For example
STMT1
sym2v4 = chi(sym2v3) NOT LIVE
default_vsym_v4 = chi(default_vsym_v3) LIVE
....
STMT2
ILOAD mu(default_vsym_v4)
...
STMT3
sym2v5 = chi(sym2v3) LIVE // sym2v3 is propagate down from
above dead chi.
default_vsym_v5 = chi(default_vsym_v4)
If sym2v4 may use at STMT2, ILOAD's MU node must on STMT1's
chi list
(because MU node must alias with sym2, otherwise its alias
issue).
And MU node's corresponding CHI node must live on STMT1,
because set_required_mu will set chi node live.
So it's okay for DSE to mark fisrt CHI dead if STMT1 and
STMT3 write same memory location.
1. It will not make STMT1 dead, because the other chi node
is live.
2. ILOAD's MU node's def statment still STMT1
If ILOAD folding transform ILOAD to LDID and LDID's AUX is sym2.
ILOD_FOLDING revives dead chi sym2v4 = chi(sym2v3) without
update the late chi node's opnd.
This introduce overlapped between sym2v3 and sym2v4.
Fix is rename CODEMAP if iload folding revive dead phi/chi node.
OPT_REVISE_SSA::Fold_lda_indirects also rename CODEMAP after
optimization.
Fix is
1. record in htable, if dead chi/phi node is revived in
SSA::Create_CODEMAP.
This only happends when ILOAD_Folding happens and find
corresponding chi/phi is dead.
2. After SSA::Create_CODEMAP, rename coderep if dead chi/phi
node is revive in CODEMAP setup.
Different with fixing in DSE to mark first chi node live,
this fix not affect DSE, so not affect performance.
And this is verified with spec2006.rate on xeon.
Regards
Shi Hui
------------------------------------------------------------------------------
All of the data generated in your IT infrastructure is seriously
valuable.
Why? It contains a definitive record of application performance,
security
threats, fraudulent activity, and more. Splunk takes this data and makes
sense of it. IT sense. And common sense.
http://p.sf.net/sfu/splunk-d2d-c2
_______________________________________________
Open64-devel mailing list
Open64-devel@lists.sourceforge.net
<mailto:Open64-devel@lists.sourceforge.net>
https://lists.sourceforge.net/lists/listinfo/open64-devel
------------------------------------------------------------------------------
Storage Efficiency Calculator
This modeling tool is based on patent-pending intellectual property that
has been used successfully in hundreds of IBM storage optimization engage-
ments, worldwide. Store less, Store more with what you own, Move data to
the right place. Try It Now! http://www.accelacomm.com/jaw/sfnl/114/51427378/
_______________________________________________
Open64-devel mailing list
Open64-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/open64-devel
