TempDescriptor refVar = refVarItr.next();
s = get( refVar );
- if( s != null ) { s.remove( vst ); }
+ if( s != null ) {
+ s.remove( vst );
+ if( s.isEmpty() ) {
+ var2vst.remove( refVar );
+ }
+ }
s = get( vst.getSESE(), refVar );
- if( s != null ) { s.remove( vst ); }
+ if( s != null ) {
+ s.remove( vst );
+ if( s.isEmpty() ) {
+ sv2vst.remove( new SVKey( vst.getSESE(), refVar ) );
+ }
+ }
}
}
removePrivate( vst );
}
- refVars.remove( refVar );
+ sv2vst.remove( new SVKey( vst.getSESE(), refVar ) );
+
+ refVars.remove( refVar );
}
- var2vst.remove( refVar );
+ var2vst.remove( refVar );
}
// any curr tokens increase age by 1
public void age( FlatSESEEnterNode curr ) {
+ Set<VariableSourceToken> forRemoval =
+ new HashSet<VariableSourceToken>();
+
+ Set<VariableSourceToken> forAddition =
+ new HashSet<VariableSourceToken>();
+
Iterator<VariableSourceToken> itr = trueSet.iterator();
while( itr.hasNext() ) {
VariableSourceToken vst = itr.next();
if( vst.getSESE().equals( curr ) ) {
- Integer newAge = vst.getAge()+1;
- if( newAge > MAX_AGE ) {
- newAge = MAX_AGE;
- }
+ // only age if the token isn't already the maximum age
+ if( vst.getAge() < MAX_AGE ) {
- remove( vst );
-
- add( new VariableSourceToken( vst.getRefVars(),
- curr,
- newAge,
- vst.getAddrVar()
- )
- );
+ forRemoval.add( vst );
+
+ forAddition.add( new VariableSourceToken( vst.getRefVars(),
+ curr,
+ vst.getAge() + 1,
+ vst.getAddrVar()
+ )
+ );
+ }
}
}
+ itr = forRemoval.iterator();
+ while( itr.hasNext() ) {
+ VariableSourceToken vst = itr.next();
+ remove( vst );
+ }
+
+ itr = forRemoval.iterator();
+ while( itr.hasNext() ) {
+ VariableSourceToken vst = itr.next();
+ add( vst );
+ }
+
assertConsistency();
}
if( childItr.hasNext() ) {
FlatSESEEnterNode child = childItr.next();
+ // set of VSTs for removal
+ HashSet<VariableSourceToken> removalSet=new HashSet<VariableSourceToken>();
+ // set of VSTs for additon
+ HashSet<VariableSourceToken> additionSet=new HashSet<VariableSourceToken>();
+
Iterator<VariableSourceToken> vstItr = get( child ).iterator();
while( vstItr.hasNext() ) {
VariableSourceToken vst = vstItr.next();
-
+ removalSet.add(vst);
+ additionSet.add(new VariableSourceToken( vst.getRefVars(),
+ curr,
+ new Integer( 0 ),
+ vst.getAddrVar()
+ ));
+ }
+
+ // remove( eah item in forremoval )
+ vstItr = removalSet.iterator();
+ while( vstItr.hasNext() ) {
+ VariableSourceToken vst = vstItr.next();
remove( vst );
-
- add( new VariableSourceToken( vst.getRefVars(),
- curr,
- new Integer( 0 ),
- vst.getAddrVar()
- )
- );
+ }
+ // add( each ite inm for additon _
+ vstItr = additionSet.iterator();
+ while( vstItr.hasNext() ) {
+ VariableSourceToken vst = vstItr.next();
+ add( vst );
}
}
}
- // if we can get a value from the current SESE and the parent
- // or a sibling, just getting from the current SESE suffices now
- // return a set of temps that are virtually read
- public Set<TempDescriptor> removeParentAndSiblingTokens( FlatSESEEnterNode curr,
- Set<TempDescriptor> liveIn ) {
-
- HashSet<TempDescriptor> virtualLiveIn = new HashSet<TempDescriptor>();
-
- FlatSESEEnterNode parent = curr.getParent();
+ // this method is called at the SESE exit of SESE 'curr'
+ // if the sources for a variable written by curr can also
+ // come from curr's parent or curr's siblings then we're not
+ // sure that curr will actually modify the variable. There are
+ // many ways to handle this, but for now, mark the variable as
+ // virtually read so curr insists on having ownership of it
+ // whether it ends up writing to it or not. It will always, then,
+ // appear in curr's out-set.
+ public Set<TempDescriptor>
+ calcVirtReadsAndPruneParentAndSiblingTokens( FlatSESEEnterNode exiter,
+ Set<TempDescriptor> liveVars ) {
+
+ Set<TempDescriptor> virtReadSet = new HashSet<TempDescriptor>();
+
+ FlatSESEEnterNode parent = exiter.getParent();
if( parent == null ) {
- // have no parent or siblings
- return virtualLiveIn;
- }
-
- remove_A_if_B( parent, curr, liveIn, virtualLiveIn );
+ // having no parent means no siblings, too
+ return virtReadSet;
+ }
+ Set<FlatSESEEnterNode> alternateSESEs = new HashSet<FlatSESEEnterNode>();
+ alternateSESEs.add( parent );
Iterator<FlatSESEEnterNode> childItr = parent.getChildren().iterator();
- if( childItr.hasNext() ) {
- FlatSESEEnterNode child = childItr.next();
-
- if( !child.equals( curr ) ) {
- remove_A_if_B( child, curr, liveIn, virtualLiveIn );
+ while( childItr.hasNext() ) {
+ FlatSESEEnterNode sibling = childItr.next();
+ if( !sibling.equals( exiter ) ) {
+ alternateSESEs.add( sibling );
}
}
- assertConsistency();
- return virtualLiveIn;
- }
-
- // if B is also a source for some variable, remove all entries
- // of A as a source for that variable: s is virtual reads
- protected void remove_A_if_B( FlatSESEEnterNode a,
- FlatSESEEnterNode b,
- Set<TempDescriptor> liveInCurrentSESE,
- Set<TempDescriptor> virtualLiveIn ) {
-
+ // VSTs to remove if they are alternate sources for exiter VSTs
+ // whose variables will become virtual reads
Set<VariableSourceToken> forRemoval = new HashSet<VariableSourceToken>();
- Iterator<VariableSourceToken> vstItr = get( a ).iterator();
+ // look at all of this SESE's VSTs at exit...
+ Iterator<VariableSourceToken> vstItr = get( exiter ).iterator();
while( vstItr.hasNext() ) {
- VariableSourceToken vst = vstItr.next();
- Iterator<TempDescriptor> refVarItr = vst.getRefVars().iterator();
+ VariableSourceToken vstExiterSrc = vstItr.next();
+
+ // only interested in tokens that come from our current instance
+ if( vstExiterSrc.getAge() != 0 ) {
+ continue;
+ }
+
+ // for each variable that might come from those sources...
+ Iterator<TempDescriptor> refVarItr = vstExiterSrc.getRefVars().iterator();
while( refVarItr.hasNext() ) {
- TempDescriptor refVar = refVarItr.next();
- Set<VariableSourceToken> bSet = get( b, refVar );
-
- if( !bSet.isEmpty() ) {
- forRemoval.add( vst );
+ TempDescriptor refVar = refVarItr.next();
+
+ // only matters for live variables at SESE exit program point
+ if( !liveVars.contains( refVar ) ) {
+ continue;
+ }
- // mark this variable as a virtual read as well
- virtualLiveIn.add( refVar );
+ // examine other sources for a variable...
+ Iterator<VariableSourceToken> srcItr = get( refVar ).iterator();
+ while( srcItr.hasNext() ) {
+ VariableSourceToken vstPossibleOtherSrc = srcItr.next();
+
+ if( vstPossibleOtherSrc.getSESE().equals( exiter ) &&
+ vstPossibleOtherSrc.getAge() > 0
+ ) {
+ // this is an alternate source if its
+ // an older instance of this SESE
+ virtReadSet.add( refVar );
+ forRemoval.add( vstPossibleOtherSrc );
+
+ } else if( alternateSESEs.contains( vstPossibleOtherSrc.getSESE() ) ) {
+ // this is an alternate source from parent or sibling
+ virtReadSet.add( refVar );
+ forRemoval.add( vstPossibleOtherSrc );
+
+ } else {
+ assert vstPossibleOtherSrc.getSESE().equals( exiter );
+ assert vstPossibleOtherSrc.getAge().equals( 0 );
+ }
}
}
}
VariableSourceToken vst = vstItr.next();
remove( vst );
}
-
assertConsistency();
+
+ return virtReadSet;
}
-
+
// get the set of VST's that come from a child
public Set<VariableSourceToken> getChildrenVSTs( FlatSESEEnterNode curr ) {
}
- // get the set of variables that have exactly one source
- // from the static perspective
- public Set<VariableSourceToken> getStaticSet() {
+ // get a sufficient set of VariableSourceTokens to cover all static sources
+ public Set<VariableSourceToken> getStaticSet( FlatSESEEnterNode current,
+ FlatSESEEnterNode parent
+ ) {
Set<VariableSourceToken> out = new HashSet<VariableSourceToken>();
TempDescriptor var = (TempDescriptor) me.getKey();
HashSet<VariableSourceToken> s1 = (HashSet<VariableSourceToken>) me.getValue();
- if( s1.size() == 1 ) {
- out.addAll( s1 );
+ if( getRefVarSrcType( var, current, parent ) == SrcType_STATIC ) {
+ out.add( s1.iterator().next() );
}
}
// dynamic source and return them
public Hashtable<TempDescriptor, VariableSourceToken>
getStatic2DynamicSet( VarSrcTokTable nextTable,
- Set<TempDescriptor> nextLiveIn ) {
+ Set<TempDescriptor> nextLiveIn,
+ FlatSESEEnterNode current,
+ FlatSESEEnterNode parent
+ ) {
Hashtable<TempDescriptor, VariableSourceToken> out =
new Hashtable<TempDescriptor, VariableSourceToken>();
// only worth tracking if live
if( nextLiveIn.contains( var ) ) {
- // this is a variable with a static source if it
- // currently has one vst
- if( s1.size() == 1 ) {
- Set<VariableSourceToken> s2 = nextTable.get( var );
-
- // and if in the next table, it is dynamic, then
- // this is a transition point, so
- if( s2.size() > 1 ) {
-
- // remember the variable and the only source
- // it had before crossing the transition
- out.put( var, s1.iterator().next() );
- }
+ if( this.getRefVarSrcType( var, current, parent ) == SrcType_STATIC &&
+ nextTable.getRefVarSrcType( var, current, parent ) == SrcType_DYNAMIC
+ ) {
+ // remember the variable and a static source
+ // it had before crossing the transition
+ out.put( var, s1.iterator().next() );
}
}
}
return SrcType_READY;
}
+ // if there appear to be no sources, it means this variable
+ // comes from outside of any statically-known SESE scope,
+ // which means the system guarantees its READY
Set<VariableSourceToken> srcs = get( refVar );
- assert !srcs.isEmpty();
+ if( srcs.isEmpty() ) {
+ return SrcType_READY;
+ }
- // if the variable may have more than one source, or that
- // source is at the summary age, it must be tracked dynamically
- if( srcs.size() > 1 ||
- srcs.iterator().next().getAge() == MLPAnalysis.maxSESEage ) {
+ // if the variable may have more than one source it might be
+ // dynamic, unless all sources are from a placeholder
+ if( srcs.size() > 1 ) {
+ Iterator<VariableSourceToken> itrSrcs = srcs.iterator();
+ VariableSourceToken oneSrc = itrSrcs.next();
+ while( itrSrcs.hasNext() ) {
+ VariableSourceToken anotherSrc = itrSrcs.next();
+ if( !oneSrc.getSESE().equals( anotherSrc.getSESE() ) ||
+ !oneSrc.getAge( ).equals( anotherSrc.getAge( ) )
+ ) {
+ return SrcType_DYNAMIC;
+ }
+ }
+
+ // all sources were same SESE and age, BUT, make sure it's
+ // not a placeholder SESE, who's vars are always ready
+ if( oneSrc.getSESE().getIsCallerSESEplaceholder() ) {
+ return SrcType_READY;
+ }
+
+ return SrcType_DYNAMIC;
+ }
+
+ VariableSourceToken singleSrc = srcs.iterator().next();
+ // if the one source is max age, track it dynamically
+ if( singleSrc.getAge() == MLPAnalysis.maxSESEage ) {
return SrcType_DYNAMIC;
}
// if it has one source that comes from the parent, it's ready
- if( srcs.iterator().next().getSESE() == parent ) {
+ if( singleSrc.getSESE() == parent ) {
return SrcType_READY;
}
+ // if the one source is a placeholder SESE then it's ready
+ if( singleSrc.getSESE().getIsCallerSESEplaceholder() ) {
+ return SrcType_READY;
+ }
+
// otherwise it comes from one source not the parent (sibling)
// and we know exactly which static SESE/age it will come from
return SrcType_STATIC;
// any reference variables that are not live can be pruned
// from the table, and if any VSTs are then no longer
// referenced, they can be dropped as well
- /* THIS CAUSES INCONSISTENCY, FIX LATER, NOT REQUIRED
+ // THIS CAUSES INCONSISTENCY, FIX LATER, NOT REQUIRED
public void pruneByLiveness( Set<TempDescriptor> rootLiveSet ) {
// the set of reference variables in the table minus the
assertConsistency();
}
- */
+
// use as an aid for debugging, where true-set is checked