Author: shihui
Date: 2011-04-26 01:21:38 -0400 (Tue, 26 Apr 2011)
New Revision: 3573
Modified:
trunk/osprey/be/com/constraint_graph.cxx
trunk/osprey/be/com/constraint_graph.h
trunk/osprey/be/com/constraint_graph_solve.cxx
trunk/osprey/be/com/constraint_graph_solve.h
trunk/osprey/be/opt/opt_defs.h
trunk/osprey/common/util/sparse_bitset.h
trunk/osprey/ipa/main/analyze/ipa_nystrom_alias_analyzer.cxx
trunk/osprey/ipa/main/analyze/ipa_nystrom_alias_analyzer.h
trunk/osprey/ipa/main/optimize/ipo_inline.cxx
Log:
Add inline support for nystrom point to analysis.
Compute callsite specific points to info for constraint graph nodes when cloned
from callee into caller.
It contains two steps
1. Update Formal ST's points to set with actual's points to, when formal's
points_to is a strict subset of actual's points_to.
2. Begin with updated formal st's constraint graph nodes as working set, solve
the constraint graph node copied from callee.
If node's point to set is updated with more accurate points to set, create a
new node record new points to.
Code review by Sun Chan
Modified: trunk/osprey/be/com/constraint_graph.cxx
===================================================================
--- trunk/osprey/be/com/constraint_graph.cxx 2011-04-25 23:22:16 UTC (rev
3572)
+++ trunk/osprey/be/com/constraint_graph.cxx 2011-04-26 05:21:38 UTC (rev
3573)
@@ -492,6 +492,8 @@
// Set the flags
ST_SCLASS storage_class = ST_sclass(st);
if (storage_class == SCLASS_FSTATIC ||
+ (storage_class == SCLASS_PSTATIC &&
+ ST_IDX_level(st_idx) == GLOBAL_SYMTAB) ||
storage_class == SCLASS_COMMON ||
storage_class == SCLASS_UGLOBAL ||
storage_class == SCLASS_DGLOBAL ||
@@ -503,8 +505,10 @@
if (ST_class(st) == CLASS_FUNC)
addFlags(CG_ST_FLAGS_FUNC);
- if (ST_class(st) == CLASS_PREG)
+ if (ST_class(st) == CLASS_PREG) {
addFlags(CG_ST_FLAGS_PREG);
+ maxOffsets(0);
+ }
// Globals are treated context-insensitive
if (checkFlags(CG_ST_FLAGS_GLOBAL))
@@ -2920,6 +2924,15 @@
}
si->incrNumOffsets();
}
+ else {
+ // record preg has how many offset.
+ // recomrd max preg number in maxOffsets
+ si->incrNumOffsets();
+ Is_True(offset % CG_PREG_SCALE == 0, ("incorrect offset\n"));
+ if(offset > si->maxOffsets()*CG_PREG_SCALE) {
+ si->maxOffsets(offset/CG_PREG_SCALE);
+ }
+ }
cgNode = CXX_NEW(ConstraintGraphNode(cg_st_idx, offset, this), _memPool);
@@ -2962,6 +2975,15 @@
return NULL;
}
+bool
+ConstraintGraph::nodeInGraph(ConstraintGraphNode* node)
+{
+ CGNodeToIdMapIterator cgIter = _cgNodeToIdMap.find(node);
+ if (cgIter != _cgNodeToIdMap.end())
+ return true;
+ return false;
+}
+
PointsTo &
ConstraintGraphNode::_getPointsTo(CGEdgeQual qual, PtsType type)
{
@@ -3153,6 +3175,17 @@
}
}
+bool
+StInfo::isCollapse()
+{
+ if (checkFlags(CG_ST_FLAGS_MODRANGE)) {
+ return modRange()->mod() == 1;
+ }
+ else {
+ return mod()==1;
+ }
+}
+
// Collapse cur with 'this' node
void
ConstraintGraphNode::collapse(ConstraintGraphNode *cur)
@@ -3430,6 +3463,49 @@
_revPointsToList = NULL;
}
+void
+ConstraintGraphNode::deleteDiffPointsToSet()
+{
+ PointsToList *p = _diffPointsToList;
+ PointsToList *np;
+ while (p) {
+ np = p->next();
+ CXX_DELETE(p, cg()->memPool());
+ p = np;
+ }
+ _diffPointsToList = NULL;
+}
+
+// union node's points to, to a single set.
+void
+ConstraintGraphNode::UnionPointsToSet(PointsTo &unionPts)
+{
+ for ( PointsToIterator pti(this); pti != 0; ++pti ) {
+ unionPts.setUnion(*pti);
+ }
+}
+
+void
+ConstraintGraphNode::copyPtsToDiff()
+{
+ for ( PointsToIterator pti(this); pti != 0; ++pti ) {
+ PointsTo &diffPts = _getPointsTo(pti.qual(), PtsDiff);
+ diffPts = *pti;
+ }
+}
+
+void
+ConstraintGraphNode::unionDiffToPts()
+{
+ for ( PointsToIterator pti(this); pti != 0; ++pti ) {
+ PointsTo *diffPts = _findPointsTo(pti.qual(), PtsDiff);
+ if ( diffPts != NULL ) {
+ PointsTo &pts = *pti;
+ pts.setUnion(*diffPts);
+ }
+ }
+}
+
void
ConstraintGraphNode::deleteInEdgeSet()
{
@@ -3973,6 +4049,29 @@
}
}
+ST_IDX
+ConstraintGraph::getCloneOirgStIdx(ST_IDX clone_idx)
+{
+ for ( hash_map<ST_IDX, ST_IDX>::iterator iter = origToCloneStIdxMap.begin();
+ iter != origToCloneStIdxMap.end(); iter++ ) {
+ ST_IDX orig_st_idx = iter->first;
+ ST_IDX clone_st_idx = iter->second;
+ if ( clone_st_idx == clone_idx ) {
+ return orig_st_idx;
+ }
+ }
+ return ST_IDX_ZERO;
+}
+
+ST_IDX
+ConstraintGraph::getOrigCloneStIdx(ST_IDX orig_idx)
+{
+ hash_map<ST_IDX, ST_IDX>::iterator iter = origToCloneStIdxMap.find(orig_idx);
+ if ( iter != origToCloneStIdxMap.end() )
+ return iter->second;
+ return ST_IDX_ZERO;
+}
+
void
ConstraintGraph::updateOrigToCloneStIdxMap(ST_IDX orig_st_idx,
ST_IDX clone_st_idx)
@@ -4011,6 +4110,56 @@
//_maxAccessSize = node->_maxAccessSize;
}
+
+// copy node's points to set to this.
+void
+ConstraintGraphNode::copyPointsTo(ConstraintGraphNode *node)
+{
+ if ( repParent() != NULL && repParent() != this )
+ return;
+
+ _pointsToList = _revPointsToList = NULL;
+ // copy node's points_to to this.
+ // add revPointsTo for the pointed node
+ for ( PointsToIterator pti(node); pti != 0; ++pti ) {
+ CGEdgeQual qual = pti.qual();
+ PointsTo &pointsTo = _getPointsTo(qual, Pts);
+ pointsTo = *pti;
+ for ( PointsTo::SparseBitSetIterator iter(&pointsTo,0); iter != 0; iter++
) {
+ CGNodeId nodeId = *iter;
+ ConstraintGraph::cgNode(nodeId)->_addRevPointsTo(id(), qual);
+ }
+ }
+
+ // for nodes which points to input node, also points to this
+ for ( PointsToIterator pti(node, PtsRev); pti != 0; ++pti ) {
+ CGEdgeQual qual = pti.qual();
+ PointsTo &pointsTo = _getPointsTo(qual, PtsRev);
+ pointsTo = *pti;
+ for ( PointsTo::SparseBitSetIterator iter(&pointsTo,0); iter != 0; iter++
) {
+ CGNodeId nodeId = *iter;
+ ConstraintGraph::cgNode(nodeId)->_addPointsTo(id(), qual);
+ }
+ }
+}
+
+
+// exclude nodes in exclude sets from this node's points to set
+void
+ConstraintGraphNode::excludePointsTo(PointsTo &exclude)
+{
+ for ( PointsTo::SparseBitSetIterator iter(&exclude,0); iter != 0; iter++ ) {
+ CGNodeId nodeId = *iter;
+ ConstraintGraphNode *ptNode = ConstraintGraph::cgNode(nodeId);
+ for ( PointsToIterator pti(this); pti != 0; ++pti ) {
+ if(_checkPointsTo(nodeId, pti.qual())) {
+ removePointsTo(nodeId, pti.qual());
+ ptNode->removeRevPointsTo(id(), pti.qual());
+ }
+ }
+ }
+}
+
// Create a new ConstraintGraphNode with new_cg_st_idx, but the old node's id
// and offset. The new node is added to this CG using the new_cg_st_idx.
ConstraintGraphNode *
@@ -4033,6 +4182,22 @@
return newCGNode;
}
+
+// create a new node id for node, update maps use node id.
+void
+ConstraintGraph::newNodeId(ConstraintGraphNode *node)
+{
+#ifdef Is_True_On
+ CGNodeToIdMapIterator cgIter = _cgNodeToIdMap.find(node);
+ Is_True(cgIter != _cgNodeToIdMap.end(), ("node not in current graph\n"));
+#endif
+
+ node->setId(nextCGNodeId);
+ _cgNodeToIdMap[node] = nextCGNodeId;
+ cgIdToNodeMap[nextCGNodeId] = node;
+ nextCGNodeId++;
+}
+
// Remap node to this CG using new cg_st_idx
void
ConstraintGraph::remapCGNode(ConstraintGraphNode *node, CG_ST_IDX
new_cg_st_idx)
Modified: trunk/osprey/be/com/constraint_graph.h
===================================================================
--- trunk/osprey/be/com/constraint_graph.h 2011-04-25 23:22:16 UTC (rev
3572)
+++ trunk/osprey/be/com/constraint_graph.h 2011-04-26 05:21:38 UTC (rev
3573)
@@ -122,6 +122,7 @@
#define CG_NODE_FLAGS_COLLAPSED_PARENT 0x00100000 // Target of a collapse
#define CG_NODE_FLAGS_FORMAL_REF_PARAM 0x00200000 // formal parm,
SCLASS_FORMAL_REF
+#define CG_NODE_FLAGS_INLINE_NO_BENEFIT 0x00400000 // Used by cs-inline
// Call site flags
#define CS_FLAGS_UNKNOWN 0x01
@@ -576,7 +577,7 @@
}
#endif
- const PointsTo &revPointsTo(CGEdgeQual qual)
+ const PointsTo &revPointsTo(CGEdgeQual qual)
{
return findRep()->_revPointsTo(qual);
}
@@ -686,6 +687,7 @@
void deleteOutEdgeSet();
void deletePointsToSet();
void deleteRevPointsToSet();
+ void deleteDiffPointsToSet();
void deleteEdgesAndPtsSetList();
// Meant be called from createAliasTags, to provide a points-to
@@ -698,7 +700,10 @@
// processing. This includes handling if Kcycle adjustments, <ST,-1>
// cleanup and establishing the reverse points-to relationship.
bool updatePointsToFromDiff(void);
-
+ void UnionPointsToSet(PointsTo &unionPts);
+ void copyPtsToDiff();
+ void unionDiffToPts();
+
// Remove redundant nodes, in the presence of <ST, -1>
void sanitizePointsTo(CGEdgeQual qual);
static void sanitizePointsTo(PointsTo &,ConstraintGraphNode *,CGEdgeQual);
@@ -708,6 +713,11 @@
bool sanityCheckPointsTo(CGEdgeQual qual);
+
+ // current node is cloned from oirg.
+ // if some node points to orig, it also points to current node
+ void updatePointsToForClone(ConstraintGraphNode *orig);
+
void dbgPrint();
void print(FILE *file);
void print(ostream &str);
@@ -715,6 +725,10 @@
// Copy contents of node into 'this'
void copy(ConstraintGraphNode *node);
+ void copyPointsTo(ConstraintGraphNode *node);
+
+ void excludePointsTo(PointsTo &exclude);
+
void checkIsPtrAligned();
bool isAPossiblePtr();
@@ -1040,6 +1054,8 @@
_memPool(memPool)
{
_u._modulus = 0;
+ if (checkFlags(CG_ST_FLAGS_PREG))
+ maxOffsets(0);
}
// To create local symbols during IPA
@@ -1103,6 +1119,7 @@
// inter-procedural skew cycles that we are not removing from the
// constraint graph
UINT16 maxOffsets(void) const { return _maxOffsets; }
+ UINT16 maxOffsets(UINT16 offset) { _maxOffsets = offset; }
UINT16 numOffsets(void) const { return _numOffsets; }
void incrNumOffsets(void) { _numOffsets += 1; }
@@ -1134,6 +1151,7 @@
void ty_idx(TY_IDX idx) { _ty_idx = idx; }
void collapse();
+ bool isCollapse();
MEM_POOL *memPool() { return _memPool; }
@@ -1291,9 +1309,15 @@
static void updateCloneStIdxMap(ST_IDX old_clone_idx, ST_IDX new_clone_idx);
+ static ST_IDX getCloneOirgStIdx(ST_IDX clone_idx);
+
+ static ST_IDX getOrigCloneStIdx(ST_IDX orig_idx);
+
static void updateOrigToCloneStIdxMap(ST_IDX orig_st_idx,
ST_IDX clone_st_idx);
+ static void clearOrigToCloneStIdxMap(IPA_NODE *caller, IPA_NODE *callee);
+
static void updatePromoteStIdxMap(ST_IDX local_st_idx, ST_IDX
global_st_idx);
static void promoteLocals(IPA_NODE *callee);
@@ -1311,6 +1335,8 @@
static void stats(void);
+ static bool exprMayPoint(WN *const wn);
+
static char *
printCGStIdx(CG_ST_IDX cg_st_idx, char *buf, int n)
{
@@ -1464,6 +1490,8 @@
// Return CGNode mapped to (cg_st_idx, offset), if not return NULL
ConstraintGraphNode *checkCGNode(CG_ST_IDX cg_st_idx, INT64 offset);
+ bool nodeInGraph(ConstraintGraphNode* node);
+
ConstraintGraphNode *handleAlloca(WN *stmt);
CG_ST_IDX buildLocalStInfo(TY_IDX ty_idx);
@@ -1476,8 +1504,6 @@
void simpleOptimizer();
- bool exprMayPoint(WN *const wn);
-
list<CGNodeId> ¶meters(void) { return _parameters; }
list<CGNodeId> &returns(void) { return _returns; }
@@ -1521,6 +1547,8 @@
ConstraintGraphNode *cloneCGNode(ConstraintGraphNode *node,
CG_ST_IDX new_cg_st_idx);
+ void newNodeId(ConstraintGraphNode *node);
+
void remapCGNode(ConstraintGraphNode *node, CG_ST_IDX new_cg_st_idx);
void mapCGNode(ConstraintGraphNode *node);
@@ -1538,6 +1566,9 @@
ConstraintGraphNode *aliasedSym(ConstraintGraphNode *n);
void map_blk_Section_STs();
+
+ void cloneStInfo(StInfo* orig, CG_ST_IDX cg_st_idx);
+
sec_blk_elements* Get_BLK_Map_Set(ST_IDX st_idx, BOOL create=FALSE);
ST* Get_blk_Section_ST(ST* base_st, INT64 offset, INT64& new_offset);
void print_section_map(FILE* f, sec_blk_elements* blk_elems);
Modified: trunk/osprey/be/com/constraint_graph_solve.cxx
===================================================================
--- trunk/osprey/be/com/constraint_graph_solve.cxx 2011-04-25 23:22:16 UTC
(rev 3572)
+++ trunk/osprey/be/com/constraint_graph_solve.cxx 2011-04-26 05:21:38 UTC
(rev 3573)
@@ -1036,6 +1036,19 @@
}
}
+// give a src points to, and its points to qual and edge qual
+// exclude the src points to from dest points to set.
+void
+ConstraintGraphSolve::Exclude(PointsTo &src, CGEdgeType et, CGEdgeQual aq,
+ CGEdgeQual eq, bool cs, PointsTo &dest)
+{
+ CGEdgeQual targetqual = qualMap(et, aq, eq, cs);
+ if (targetqual == CQ_NONE)
+ return;
+ else
+ dest.setDiff(src);
+}
+
void
ConstraintGraph::addEdgesToWorkList(ConstraintGraphNode *node)
{
Modified: trunk/osprey/be/com/constraint_graph_solve.h
===================================================================
--- trunk/osprey/be/com/constraint_graph_solve.h 2011-04-25 23:22:16 UTC
(rev 3572)
+++ trunk/osprey/be/com/constraint_graph_solve.h 2011-04-26 05:21:38 UTC
(rev 3573)
@@ -63,6 +63,12 @@
static void postProcessPointsTo();
+ static void Exclude(PointsTo &src, CGEdgeType et, CGEdgeQual aq,
+ CGEdgeQual eq, bool cs, PointsTo &orig);
+
+ // Edge qualifier matrix mapping
+ static CGEdgeQual qualMap(CGEdgeType et,CGEdgeQual aq,CGEdgeQual eq, bool
cs);
+
static void printStats();
private:
@@ -89,9 +95,6 @@
EdgeDelta &edgeDelta() { return _edgeDelta; }
- // Edge qualifier matrix mapping
- CGEdgeQual qualMap(CGEdgeType et,CGEdgeQual aq,CGEdgeQual eq, bool cs);
-
ConstraintGraph *_cg;
ConstraintGraph *_globalCG;
MEM_POOL *_memPool;
Modified: trunk/osprey/be/opt/opt_defs.h
===================================================================
--- trunk/osprey/be/opt/opt_defs.h 2011-04-25 23:22:16 UTC (rev 3572)
+++ trunk/osprey/be/opt/opt_defs.h 2011-04-26 05:21:38 UTC (rev 3573)
@@ -173,6 +173,7 @@
#define NYSTROM_ALIAS_TAG_FLAG 0x00000400 /* be alias tag after
Transfer_alias_tag_to_occ_and_aux */
#define NYSTROM_LW_SOLVER_FLAG 0x00000800 /* light weight trace constraint
graph solver */
+#define NYSTROM_INLINE_FLAG 0x00001000 /* inline trace*/
/* TP_GLOBOPT (phase-number) */
#define DOM_DUMP_FLAG 0x0001 /* print dominator tree */
Modified: trunk/osprey/common/util/sparse_bitset.h
===================================================================
--- trunk/osprey/common/util/sparse_bitset.h 2011-04-25 23:22:16 UTC (rev
3572)
+++ trunk/osprey/common/util/sparse_bitset.h 2011-04-26 05:21:38 UTC (rev
3573)
@@ -533,6 +533,24 @@
return *this;
}
+ bool operator==(const SparseBitSet &rhs)
+ {
+ SparseBitSetElement *ptr;
+ SparseBitSetElement *ptr_rhs;
+ for (ptr = _firstElem, ptr_rhs = rhs._firstElem;
+ ptr && ptr_rhs;
+ ptr = ptr->_next, ptr_rhs = ptr_rhs->_next) {
+ if (ptr->_idx != ptr_rhs->_idx)
+ return false;
+ if (memcmp(ptr->_bits, ptr_rhs->_bits, sizeof(ptr->_bits)))
+ return false;
+ }
+
+ if(ptr == NULL && ptr_rhs == NULL)
+ return true;
+ return false;
+ }
+
// Return true if this AND rhs is not empty.
bool
intersect(const SparseBitSet& rhs) const
@@ -611,6 +629,41 @@
return changed != 0;
}
+ // return true if rhs is a subset of this.
+ bool
+ subset(const SparseBitSet& rhs) const
+ {
+ SparseBitSetElement *thisElt = _firstElem;
+ SparseBitSetElement *rhsElt = rhs._firstElem;
+ if (rhs.isEmpty())
+ return true;
+ if (isEmpty())
+ return false;
+
+ // rhs's element must be found in this
+ while (rhsElt && thisElt) {
+ if (thisElt->_idx > rhsElt->_idx) {
+ return false;
+ }
+ else if (thisElt->_idx == rhsElt->_idx) {
+ // compare each word
+ for (UINT32 ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) {
+ if (thisElt->_bits[ix] != (thisElt->_bits[ix] | rhsElt->_bits[ix]))
+ return false;
+ }
+ rhsElt = rhsElt->_next;
+ thisElt = thisElt->_next;
+ }
+ else {
+ thisElt = thisElt->_next;
+ }
+ }
+ // all thisElt's idx smaller than rhsElt's idx
+ if(rhsElt)
+ return false;
+ return true;
+ }
+
bool isEmpty() const { return _firstElem == NULL; }
UINT32 numElements() const {
Modified: trunk/osprey/ipa/main/analyze/ipa_nystrom_alias_analyzer.cxx
===================================================================
--- trunk/osprey/ipa/main/analyze/ipa_nystrom_alias_analyzer.cxx
2011-04-25 23:22:16 UTC (rev 3572)
+++ trunk/osprey/ipa/main/analyze/ipa_nystrom_alias_analyzer.cxx
2011-04-26 05:21:38 UTC (rev 3573)
@@ -731,6 +731,15 @@
summ->flags(), summ->inKCycle(),
newCGNodeId, this), _memPool);
cgNode->ty_idx(summ->ty_idx());
+ // if cg node is preg update preg's max offset.
+ // for create this preg's new cg node in ipa
+ StInfo* si = cgNode->stInfo();
+ if (si->checkFlags(CG_ST_FLAGS_PREG)) {
+ Is_True(summ->offset() % CG_PREG_SCALE == 0, ("incorrect offset\n"));
+ if (summ->offset() > si->maxOffsets()*CG_PREG_SCALE) {
+ si->maxOffsets(summ->offset()/CG_PREG_SCALE);
+ }
+ }
// Add to maps in the current ConstraintGraph
cgIdToNodeMap[newCGNodeId] = cgNode;
@@ -2212,6 +2221,697 @@
}
void
+IPA_NystromAliasAnalyzer::updateCloneTreeWithCgnode(WN* tree)
+{
+ for (WN_ITER *wni = WN_WALK_TreeIter(tree);
+ wni; wni = WN_WALK_TreeNext(wni)) {
+ WN *wn = WN_ITER_wn(wni);
+
+ UINT32 id = IPA_WN_MAP32_Get(Current_Map_Tab, WN_MAP_ALIAS_CGNODE, wn);
+ if (id == 0)
+ continue;
+
+ UINT32 cs_id = getInlineNodeMap(id);
+ if (cs_id == 0)
+ continue;
+
+ if (OPERATOR_is_call(WN_operator(wn))) {
+ // havn't processing callsite points to info yet.
+ Is_True(FALSE, ("unexpected case\n"));
+ } else {
+ WN_MAP_CGNodeId_Set(wn, cs_id);
+ }
+ }
+
+ _inline_node_map.clear();
+}
+
+// if callee's formal has more accurate points to info when inline.
+// try to solve the constraint graph nodes used in callee with more accurate
points to set.
+// for example
+// foo(int *p)
+// use *(P+4)
+//
+// call foo(&a);
+// processInlineFormal will make a new CG node for p in inlined body only
points to a.
+// solveInlineConstraints will solve p+4 copy skew edge.
+//
+// the whole function will have the fllowing steps.
+// 1. iterate _inline_node_map, collect initial nodes workset. return if set
is empty
+// 2. prcess each node in work set untill empty
+// iterate all out edges from this node
+// recompute the diff set of points to
+// update if points to set is narrowed.
+// create new cg node record new points to set.
+// add node into work set.
+//
+void
+IPA_NystromAliasAnalyzer::solveInlineConstraints(IPA_NODE *callee, IPA_NODE
*caller)
+{
+ // initial work list is the formals with updated points to set.
+ NodeWorkList nodeWorkList;
+ if (_inline_node_map.size() == 0)
+ return;
+ hash_map<UINT32, UINT32>::const_iterator formal_iter =
_inline_node_map.begin();
+ for (;formal_iter != _inline_node_map.end(); formal_iter++) {
+ nodeWorkList.push(ConstraintGraph::cgNode(formal_iter->first));
+ }
+
+ Is_True(!nodeWorkList.empty() != 0, ("initial work list can't be empty\n"));
+ ConstraintGraph* callee_cg = cg(callee->Node_Index());
+
+ do {
+ ConstraintGraphNode *old_node = nodeWorkList.pop();
+ ConstraintGraphNode *new_node =
ConstraintGraph::cgNode(getInlineNodeMap(old_node->id()));
+ const CGEdgeSet &outCopySkew = old_node->outCopySkewEdges();
+
+ // process copy skew edge
+ for (CGEdgeSetIterator iter = outCopySkew.begin();
+ iter != outCopySkew.end();
+ iter++) {
+ ConstraintGraphEdge *edge = *iter;
+ if (inlineSolveNode(edge->destNode(), callee_cg, caller)) {
+ nodeWorkList.push(edge->destNode());
+ }
+ }
+ } while(!nodeWorkList.empty());
+}
+
+
+// first check, if newly computed points is accurate then current points to.
+// 1. copy node's points to to diff.
+// 2. process incopyskew edges
+// iterate source node's points to qual
+// compute the dest's qual
+// dest's diff_points_to[qual] &= ~source_points_to[qual]
+// 3. if diff points to is not empty, (this indicate has some improvment on
points to)
+// create a new node, update its points to as
+// new_node[qual] = node[qual] & ~node_diff[qual]
+// map old node with new node
+bool
+IPA_NystromAliasAnalyzer::inlineSolveNode(ConstraintGraphNode *node,
ConstraintGraph* callee_cg,
+ IPA_NODE* caller)
+{
+ // not handling global nodes
+ // because <global_st, offset> is unique in constraint graph representation.
+ if (node->checkFlags(CG_NODE_FLAGS_UNKNOWN) ||
+ node->stInfo()->checkFlags(CG_ST_FLAGS_GLOBAL)) {
+ return false;
+ }
+ // check node is local in callee
+ if (!callee_cg->nodeInGraph(node))
+ return false;
+
+ // if node has parent, its points to comes from parent.
+ if (node->repParent() != NULL && node->repParent() != node)
+ return false;
+
+ // don't handle nodes has in loadstore edge.
+ // this is because when solve the constraints graph inloadstoredge
+ // is translate into incopyskew edge, see
ConstraintGraphSolve::addCopiesForLoadStore.
+ // If these copies edge still exist, the analysis result will always
consertevertive.
+ const CGEdgeSet &inloadstore = node->inLoadStoreEdges();
+ if (!inloadstore.empty())
+ return false;
+
+ // if node already has been optimized and record in inlineNodeMap
+ // during the following analysis
+ // 1. get points to set by new nodes
+ // 2. get edge set by orignal nodes.
+ CGNodeId new_id = getInlineNodeMap(node->id());
+ ConstraintGraphNode *new_node = NULL;
+ if (new_id != 0) {
+ new_node = ConstraintGraph::cgNode(new_id);
+ }
+
+ // copy pts points to to diff points to.
+ ConstraintGraphNode *updating_node;
+ if (new_node)
+ updating_node = new_node;
+ else
+ updating_node = node;
+ PointsTo origPointsTo;
+ updating_node->UnionPointsToSet(origPointsTo);
+
+ // process copy skew edge
+ const CGEdgeSet &inCopySkew = node->inCopySkewEdges();
+ for (CGEdgeSetIterator iter = inCopySkew.begin();
+ iter != inCopySkew.end(); iter++) {
+ ConstraintGraphEdge *edge = *iter;
+
+ // get edge in node, if in node is cloned, use new node
+ ConstraintGraphNode *in_node = edge->srcNode();
+ bool cntxt =
+
!in_node->cg()->stInfo(in_node->cg_st_idx())->checkFlags(CG_ST_FLAGS_NOCNTXT);
+
+ CGNodeId in_node_new_id = getInlineNodeMap(in_node->id());
+ if (in_node_new_id != 0) {
+ in_node = ConstraintGraph::cgNode(in_node_new_id);
+ }
+
+ if (edge->edgeType() == ETYPE_COPY) {
+ if (edge->checkFlags(CG_EDGE_PARENT_COPY)) {
+ // in node must hae offset -1, no points to propagate.
+ }
+ else {
+ // iterate in node's points to, exclude from current node's diff
+ for ( PointsToIterator pti(in_node); pti != 0; ++pti ) {
+ ConstraintGraphSolve::Exclude(*pti, ETYPE_COPY, pti.qual(),
+ edge->edgeQual(), cntxt, origPointsTo);
+ }
+ }
+ }
+ else {
+ Is_True(edge->edgeType() == ETYPE_SKEW, ("must be skew\n"));
+ for ( PointsToIterator pti(in_node); pti != 0; ++pti ) {
+ CGEdgeQual dstQual = ConstraintGraphSolve::qualMap(ETYPE_COPY,
+ pti.qual(),edge->edgeQual(),cntxt);
+ if(dstQual == CQ_NONE)
+ continue;
+ PointsTo &srcPTS = *pti;
+ for (PointsTo::SparseBitSetIterator iter(&srcPTS,0); iter != 0;
iter++) {
+ CGNodeId nodeId = *iter;
+ ConstraintGraphNode *pt_node = ConstraintGraph::cgNode(nodeId);
+ StInfo *st = pt_node->stInfo();
+ FmtAssert(!st->checkFlags(CG_ST_FLAGS_PREG),
+ ("processSkew: preg found in pts set of node: %d\n",
+ pt_node->id()));
+ INT32 newOffset;
+ if (pt_node->offset() == -1)
+ newOffset = -1;
+ else {
+ newOffset = pt_node->offset() + edge->skew();
+ if (newOffset < 0) newOffset = -newOffset;
+ }
+ ConstraintGraphNode *skewNode =
+ pt_node->cg()->getCGNode(pt_node->cg_st_idx(),newOffset);
+ origPointsTo.clearBit(skewNode->id());
+ }
+
+ }
+ }
+ if (origPointsTo.isEmpty())
+ return false;
+ }
+
+
+ // check final result
+ // if all points to cg nodes is found during checking input copy skew edge.
+ // then this node's points to set has no no improvment.
+ if (origPointsTo.isEmpty())
+ return false;
+
+ ConstraintGraphNode *clone_node = getCloneNode(node, callee_cg, caller);
+
+ if (clone_node == NULL)
+ return false;
+
+ // update points to set.
+ clone_node->excludePointsTo(origPointsTo);
+ return true;
+}
+
+// get a node to record new points to information.
+// there are two kinds nodes in callee cg needs be cloned
+// 1. local ST cloned into caller
+// ConstraintGraph::cloneConstraintGraphMaps will clone callee local
var's
+// constraint graph node to caller, (same points to and id, but differnt
cg_st_idx)
+// When a function in inlined into caller several times (multiple calls
in same function),
+// one local var in callee still map to one local var in caller.
+// for example
+// foo
+// call bar p->a, analysis result for this inline.
+// ...
+// call bar p->b, analysis result for this inline.
+// ..
+// bar
+// p->a,b,c, analysis reuslt before inline.
+// then p in foo function should points to a and b.
+// use two flags, cgnode_visited, cgnode_
+//
+//
+//
+// If IPO_INLINE can use two local st for p in foo, than each
+// it can get more accurate points to, like p1->a, p2->b
+// 2. preg
+// nodes is simply cloned into caller cg. with a unique offset.
+ConstraintGraphNode*
+IPA_NystromAliasAnalyzer::getCloneNode(ConstraintGraphNode *callee_node,
+ ConstraintGraph* callee_cg,
IPA_NODE* caller)
+{
+ // get callee_node's cg_st_idx, get its st_idx in caller by
ConstraintGraph::origToCloneStIdxMap,
+ CG_ST_IDX orig_cg_st_idx = callee_node->cg_st_idx();
+ ConstraintGraphNode* clone_node;
+
+ // 1. callee_node already has been cloned.
+ CGNodeId id = callee_node->id();
+ CGNodeId clone_id;
+ if (clone_id = getInlineNodeMap(id))
+ return ConstraintGraph::cgNode(clone_id);
+
+ // 2. not yet map in _inline_node_map, but cloned into caller's graph
+ CG_ST_IDX cloned_cg_st_idx =
ConstraintGraph::getOrigCloneStIdx(SYM_ST_IDX(orig_cg_st_idx));
+ ConstraintGraph* caller_cg = cg(caller->Node_Index());
+ if (cloned_cg_st_idx != ST_IDX_ZERO) {
+ cloned_cg_st_idx = ConstraintGraph::adjustCGstIdx(caller,
cloned_cg_st_idx);
+ clone_node = caller_cg->getCGNode(cloned_cg_st_idx, callee_node->offset());
+
+ // this node is not optimized in last inline into same caller
+ if (clone_node->checkFlags(CG_NODE_FLAGS_INLINE_NO_BENEFIT))
+ return NULL;
+
+ Is_True(clone_node, ("must be cloned in mapcloneconstraintgraph\n"));
+ if (clone_node->id() != callee_node->id()) {
+ clone_node->deletePointsToSet();
+ clone_node->deleteRevPointsToSet();
+ }
+ else {
+ Is_True(ConstraintGraph::cgNode(clone_node->id()) != clone_node,
+ ("clone_node not id's primiary node\n"));
+ caller_cg->newNodeId(clone_node);
+ }
+
+ // duplicated points to and add into inlineNodeMap.
+ clone_node->copyPointsTo(callee_node);
+ addInlineNodeMap(callee_node->id(), clone_node->id());
+ clone_node->addFlags(CG_NODE_FLAGS_VISITED);
+ return clone_node;
+ }
+
+ // 3. preg to be mapped into caller cg later in updateCGforBE
+ if (ST_IDX_level(SYM_ST_IDX(orig_cg_st_idx)) == GLOBAL_SYMTAB) {
+ // this must be a preg, that is boht local and not cloned symbol in new
alias
+ ST_IDX st_idx = SYM_ST_IDX(orig_cg_st_idx);
+ Is_True(ST_class(&St_Table[st_idx]) == CLASS_PREG, ("must be preg\n"));
+ StInfo *stinfo = callee_cg->stInfo(orig_cg_st_idx);
+ if (! caller_cg->stInfo(orig_cg_st_idx) )
+ caller_cg->mapStInfo(stinfo, orig_cg_st_idx, orig_cg_st_idx);
+
+ clone_node = caller_cg->getCGNode(orig_cg_st_idx,
(stinfo->maxOffsets()+1)*CG_PREG_SCALE);
+ stinfo->maxOffsets(stinfo->maxOffsets()+1);
+
+ clone_node->copyPointsTo(callee_node);
+ addInlineNodeMap(callee_node->id(), clone_node->id());
+ return clone_node;
+ }
+ return NULL;
+}
+
+
+// clear orig_to_clone map introduced in inline.
+// CG_NODE_FLAGS_VISITED means clone_node is optimized
+// by nystrom inline support.
+//
+// If it's not optimized, it can't be optimized in caller.
+// When same callee is inlined to same caller.
+void
+ConstraintGraph::clearOrigToCloneStIdxMap(IPA_NODE *caller, IPA_NODE *callee)
+{
+ ConstraintGraph *callerCG =
+
IPA_NystromAliasAnalyzer::aliasAnalyzer()->cg(caller->Node_Index());
+ ConstraintGraph *calleeCG =
+
IPA_NystromAliasAnalyzer::aliasAnalyzer()->cg(callee->Node_Index());
+ for (hash_map<ST_IDX, ST_IDX>::iterator iter = origToCloneStIdxMap.begin();
+ iter != origToCloneStIdxMap.end(); iter++) {
+ ST_IDX orig_st_idx = iter->first;
+ ST_IDX clone_st_idx = iter->second;
+
+ CG_ST_IDX orig_cg_st_idx =
+ ConstraintGraph::adjustCGstIdx(callee, orig_st_idx);
+ StInfo *origStInfo = calleeCG->stInfo(orig_cg_st_idx);
+ if (origStInfo == NULL)
+ continue;
+
+ CG_ST_IDX clone_cg_st_idx =
+ ConstraintGraph::adjustCGstIdx(caller, clone_st_idx);
+ ConstraintGraphNode *orig_node = origStInfo->firstOffset();
+ while (orig_node) {
+ ConstraintGraphNode *clone_node = callerCG->getCGNode(clone_cg_st_idx,
orig_node->offset());
+ if (!clone_node->checkFlags(CG_NODE_FLAGS_VISITED)) {
+ clone_node->addFlags(CG_NODE_FLAGS_INLINE_NO_BENEFIT);
+ CGNodeId id = clone_node->id();
+ if (id != orig_node->id()) {
+ clone_node->deletePointsToSet();
+ clone_node->copy(orig_node);
+ clone_node->setId(id);
+ }
+ }
+ else {
+ clone_node->clearFlags(CG_NODE_FLAGS_VISITED);
+ clone_node->unionDiffToPts();
+ }
+ orig_node = orig_node->nextOffset();
+ }
+ }
+ origToCloneStIdxMap.clear();
+}
+
+
+//
+// get WN node's cg node, from WN map or <st, offset>
+//
+ConstraintGraphNode*
+IPA_NystromAliasAnalyzer::getCGNode(WN* wn, IPA_NODE* ipaNode)
+{
+ if (!ConstraintGraph::exprMayPoint(wn)) {
+ return ConstraintGraph::notAPointer();
+ }
+
+ OPERATOR opr = WN_operator(wn);
+ switch(opr) {
+ case OPR_ILOAD: {
+ CGNodeId id;
+#ifdef Is_True_On
+ id = IPA_WN_MAP32_Get(Current_Map_Tab, WN_MAP_ALIAS_CGNODE, wn);
+ Is_True(id == 0, ("iload can't directly has cg node in IPA\n"));
+#endif
+ id = IPA_WN_MAP32_Get(Current_Map_Tab, WN_MAP_ALIAS_CGNODE, WN_kid0(wn));
+ ConstraintGraphNode* node = NULL;
+ if (id == 0) {
+ node = getCGNode(WN_kid0(wn), ipaNode);
+ if(node == NULL)
+ return NULL;
+ }
+ else {
+ node = ConstraintGraph::cgNode(id);
+ }
+
+ if (WN_offset(wn) != 0)
+ return NULL;
+
+ const CGEdgeSet &outset = node->outLoadStoreEdges();
+ for (CGEdgeSetIterator iter = outset.begin(); iter != outset.end();
++iter) {
+ ConstraintGraphEdge *edge = *iter;
+ if (edge->edgeType() == ETYPE_LOAD) {
+ ConstraintGraphNode* destNode = edge->destNode();
+ if (destNode->inLoadStoreEdges().size() == 1)
+ {
+ return destNode;
+ }
+ }
+ }
+ break;
+ }
+ case OPR_ADD:
+ case OPR_SUB: {
+ ConstraintGraphNode *kid0CGNode, *kid1CGNode;
+ if (!(kid0CGNode = getCGNode(WN_kid0(wn), ipaNode)))
+ return NULL;
+ if (!(kid1CGNode = getCGNode(WN_kid1(wn), ipaNode)))
+ return NULL;
+
+ if (kid0CGNode->checkFlags(CG_NODE_FLAGS_NOT_POINTER) &&
+ kid1CGNode->checkFlags(CG_NODE_FLAGS_NOT_POINTER)) {
+ return ConstraintGraph::globalCG()->notAPointer();
+ }
+ ConstraintGraphNode *kidCGNode = NULL;
+ if (!kid0CGNode->checkFlags(CG_NODE_FLAGS_NOT_POINTER))
+ kidCGNode = kid0CGNode;
+ else if (!kid1CGNode->checkFlags(CG_NODE_FLAGS_NOT_POINTER))
+ kidCGNode = kid1CGNode;
+
+ WN *intConst = NULL;
+ if (WN_operator(WN_kid0(wn)) == OPR_INTCONST)
+ intConst = WN_kid0(wn);
+ else if (WN_operator(WN_kid1(wn)) == OPR_INTCONST)
+ intConst = WN_kid1(wn);
+
+ Is_True(kidCGNode, ("kidCGNode can't be NULL\n"));
+ if (kidCGNode && intConst) {
+ // find node has only one edge that is incopykew edge
+ // fromt his node.
+ const CGEdgeSet &outCopySkewSet = kidCGNode->outCopySkewEdges();
+ for (CGEdgeSetIterator eiter = outCopySkewSet.begin();
+ eiter != outCopySkewSet.end(); eiter++) {
+ ConstraintGraphEdge *edge = *eiter;
+ if (edge->edgeType() != ETYPE_SKEW)
+ continue;
+ if (edge->skew() != WN_const_val(intConst))
+ continue;
+ ConstraintGraphNode *destNode = edge->destNode();
+ if (destNode->inCopySkewEdges().size() == 1 &&
+ destNode->inCopySkewEdges().empty()) {
+ return destNode;
+ }
+ }
+ return NULL;
+ }
+ return kidCGNode;
+ }
+ case OPR_LDID: {
+ // get cg node with <st, offset>
+ // get the node only points to this cg node.
+ CG_ST_IDX st_idx = WN_st_idx(wn);
+ WN_OFFSET offset = WN_offset(wn);
+ ConstraintGraph* nodeCg = cg(ipaNode->Node_Index());
+ ST_SCLASS storage_class = ST_sclass(WN_st(wn));
+ if (storage_class == SCLASS_FSTATIC ||
+ (storage_class == SCLASS_PSTATIC && ST_IDX_level(st_idx) ==
GLOBAL_SYMTAB)||
+ storage_class == SCLASS_COMMON ||
+ storage_class == SCLASS_UGLOBAL ||
+ storage_class == SCLASS_DGLOBAL ||
+ storage_class == SCLASS_UNKNOWN ||
+ storage_class == SCLASS_TEXT ||
+ storage_class == SCLASS_EXTERN) {
+ nodeCg = ConstraintGraph::globalCG();
+ }
+ else {
+ st_idx = ConstraintGraph::adjustCGstIdx(ipaNode, st_idx);
+ }
+ if (ST_class(WN_st(wn)) == CLASS_PREG)
+ offset *= CG_PREG_SCALE;
+ ConstraintGraphNode *node = nodeCg->checkCGNode(st_idx, offset);
+ // when this st's cg nodes are collpased, can't find the cg node.
+ return node;
+ }
+ case OPR_LDA: {
+ // get cg node with <st, offset>
+ // get the node only points to this cg node.
+ CG_ST_IDX st_idx = WN_st_idx(wn);
+ WN_OFFSET offset = WN_offset(wn);
+ ConstraintGraph* nodeCg = cg(ipaNode->Node_Index());
+ ST_SCLASS storage_class = ST_sclass(WN_st(wn));
+ if (storage_class == SCLASS_FSTATIC ||
+ (storage_class == SCLASS_PSTATIC && ST_IDX_level(st_idx) ==
GLOBAL_SYMTAB)||
+ storage_class == SCLASS_COMMON ||
+ storage_class == SCLASS_UGLOBAL ||
+ storage_class == SCLASS_DGLOBAL ||
+ storage_class == SCLASS_UNKNOWN ||
+ storage_class == SCLASS_TEXT ||
+ storage_class == SCLASS_EXTERN) {
+ nodeCg = ConstraintGraph::globalCG();
+ }
+ else {
+ st_idx = ConstraintGraph::adjustCGstIdx(ipaNode, st_idx);
+ }
+ ConstraintGraphNode *node = nodeCg->checkCGNode(st_idx, offset);
+ if (node == NULL)
+ return NULL;
+
+ // get node only points to this actual node.
+ StInfo* stinfo = nodeCg->stInfo(st_idx);
+ CGEdgeQual qual = CQ_HZ;
+ if (stinfo->checkFlags(CG_ST_FLAGS_NOCNTXT))
+ qual = CQ_GBL;
+
+ const PointsTo& rev_pts = node->myRevPointsTo(qual);
+ for (PointsTo::SparseBitSetIterator sbsi(&rev_pts, 0); sbsi != 0;
++sbsi) {
+ CGNodeId id = *sbsi;
+ ConstraintGraphNode *pt_node = ConstraintGraph::cgNode(id);
+
+ // if pt_node only points to node
+ BOOL match = true;
+ for (PointsToIterator pti(pt_node); pti != 0; ++pti) {
+ PointsTo &pts = *pti;
+ CGEdgeQual pt_qual = pti.qual();
+ if (pt_qual != qual) {
+ if (!pts.isEmpty()) {
+ match = false;
+ break;
+ }
+ }
+ else {
+ if (pts.numBits() != 1) {
+ match = false;
+ break;
+ }
+ }
+ }
+ if (match)
+ return pt_node;
+ }
+ return NULL;
+ }
+ case OPR_CVT:
+ case OPR_CVTL:{
+ if (MTYPE_byte_size(WN_rtype(wn)) < Pointer_Size ||
+ !MTYPE_is_unsigned(WN_rtype(wn)) ||
+ !MTYPE_is_unsigned(WN_rtype(WN_kid0(wn)))) {
+ return ConstraintGraph::notAPointer();
+ }
+ else {
+ return getCGNode(WN_kid0(wn), ipaNode);
+ }
+ }
+ case OPR_INTCONST:{
+ return ConstraintGraph::notAPointer();
+ }
+ default:
+ break;
+ }
+ return NULL;
+}
+
+bool
+IPA_NystromAliasAnalyzer::processInlineFormal(IPA_NODE *caller,
+ IPA_NODE *callee, WN* actual, ST* formal_st)
+{
+ if (!ConstraintGraph::exprMayPoint(actual))
+ return false;
+
+ // not handling MTYPE now
+ if (WN_rtype(actual) == MTYPE_M)
+ return false;
+ ConstraintGraph* caller_cg = cg(caller->Node_Index());
+ ConstraintGraph* callee_cg = cg(callee->Node_Index());
+ ConstraintGraph* global_cg = ConstraintGraph::globalCG();
+
+ // get original formal st in caller symtable
+ ST_IDX orig_idx = ConstraintGraph::getCloneOirgStIdx(ST_st_idx(formal_st));
+ if (orig_idx == ST_IDX_ZERO)
+ return false;
+
+ CG_ST_IDX formal_st_idx = ConstraintGraph::adjustCGstIdx(callee, orig_idx);
+ ConstraintGraphNode *formal_node = callee_cg->checkCGNode(formal_st_idx, 0);
+ Is_True(formal_node != NULL, ("can't get formal_st cg node\n"));
+ if (formal_node->checkFlags(CG_NODE_FLAGS_NOT_POINTER)) {
+ return false;
+ }
+
+
+ // get actual's cg node from caller or global graph
+ ConstraintGraphNode *actual_node = getCGNode(actual, caller);
+ if (actual_node == NULL)
+ return false;
+ if (actual_node->repParent() && actual_node->repParent() != actual_node)
+ return false;
+ // if actual node is merge parent of formal node, they must have same
+ // points to.
+ if (formal_node->checkFlags(CG_NODE_FLAGS_MERGED) &&
+ formal_node->findRep() == actual_node) {
+ return false;
+ }
+
+ // only handle scalar
+ StInfo *callee_orig_st_info = callee_cg->stInfo(formal_st_idx);
+ Is_True(callee_orig_st_info->numOffsets() == 1, ("formal in callee has only
one node\n"));
+
+ // check formal node has only in edge is in copy edge DN.
+ // if it has other in edge, can't optimize
+ // better solution maybe resolved the points to set and compare with current
points to.
+ // in case of formal is also modified in this function.
+ const CGEdgeSet& inLoadStoreSet = formal_node->inLoadStoreEdges();
+ if (!inLoadStoreSet.empty())
+ return false;
+ const CGEdgeSet& inCopySkewSet = formal_node->inCopySkewEdges();
+ for (CGEdgeSetIterator eiter = inCopySkewSet.begin();
+ eiter != inCopySkewSet.end(); eiter++) {
+ ConstraintGraphEdge *edge = *eiter;
+ if (edge->edgeQual() != CQ_DN)
+ return false;
+ }
+
+ ConstraintGraphNode *new_formal_node = NULL;
+ BOOL create_new = FALSE;
+ // check actaul nodes's points to set is a sub set of formal node's subset.
+ // DN copy edge always add points to into DN set, see
ConstraintGraphSolve::qualMap
+ // so only need check if formal's DN points to set includes actual's all
points to.
+ // itearate actual_node's points to set.
+ const PointsTo &formal_DN_set = formal_node->pointsTo(CQ_DN);
+ // if formal node has no DN points to set, no improvement
+ if (formal_DN_set.isEmpty())
+ return false;
+
+ PointsTo actual_union;
+ for (PointsToIterator pti(actual_node); pti != 0; ++pti) {
+ PointsTo &pts = *pti;
+ actual_union.setUnion(pts);
+ }
+ // actual's points to set is a true subset of formal's DN points to set.
+ bool pointsToUpdate = true;
+ if (!formal_DN_set.subset(actual_union) ||
+ formal_DN_set.numBits() == actual_union.numBits())
+ pointsToUpdate = false;
+
+ // TODO:
+ // if formal has no optimized chance and its parent function will not be
inlined.
+ // then it also has no chance to improve points to, when caller is inlined.
+
+
+ // create a new node with DN points to has actual_union's points to.
+ CG_ST_IDX new_cg_st_idx = ConstraintGraph::adjustCGstIdx(caller,
ST_st_idx(formal_st));
+ // 1. add new stinfo in caller cg.
+ StInfo *cloneStInfo = caller_cg->stInfo(new_cg_st_idx);
+ Is_True(cloneStInfo == NULL, ("callee's formal ST's stinfo already
setup\n"));
+ caller_cg->cloneStInfo(callee_orig_st_info, new_cg_st_idx);
+ new_formal_node = caller_cg->getCGNode(new_cg_st_idx, 0);
+ new_formal_node->addFlags(formal_node->flags());
+ new_formal_node->unionPointsTo(actual_union, CQ_DN);
+ new_formal_node->updatePointsToForClone(formal_node);
+
+ // add copy edge from actual node to new formal node
+ if (new_formal_node->checkFlags(CG_NODE_FLAGS_MERGED)) {
+ new_formal_node->clearFlags(CG_NODE_FLAGS_MERGED);
+ new_formal_node->repParent(NULL);
+ }
+ bool added;
+ caller_cg->addEdge(actual_node, new_formal_node, ETYPE_COPY, CQ_DN,
ST_size(formal_st), added);
+
+ // only add node into inline node map, when it is optimized.
+ if (pointsToUpdate == true)
+ addInlineNodeMap(formal_node->id(), new_formal_node->id());
+
+ if (Get_Trace(TP_ALIAS,NYSTROM_INLINE_FLAG)) {
+ fprintf(TFile, "cs inline, actual is\n");
+ fdump_tree(TFile, actual);
+ formal_node->print(TFile);
+ actual_node->print(TFile);
+ new_formal_node->print(TFile);
+ }
+ return true;
+}
+
+void
+ConstraintGraph::cloneStInfo(StInfo* orig, CG_ST_IDX cg_st_idx)
+{
+ StInfo *si = CXX_NEW(StInfo(orig->flags(), orig->varSize(), orig->ty_idx(),
_memPool), _memPool);
+ if (orig->checkFlags(CG_ST_FLAGS_MODRANGE)) {
+ si->modRange(orig->modRange());
+ }
+ else {
+ si->mod(orig->mod());
+ }
+ _cgStInfoMap[cg_st_idx] = si;
+}
+
+void
+ConstraintGraphNode::updatePointsToForClone(ConstraintGraphNode *orig)
+{
+ // iterate orig node's reverse pts nodes.
+ // mark they also points to this.
+
+ for ( PointsToIterator pti(orig, PtsRev); pti != 0; ++pti ) {
+ CGEdgeQual qual = pti.qual();
+ PointsTo &pointsTo = _getPointsTo(qual, PtsRev);
+ pointsTo = *pti;
+ for (PointsTo::SparseBitSetIterator iter(&pointsTo,0); iter != 0; iter++) {
+ CGNodeId nodeId = *iter;
+ ConstraintGraph::cgNode(nodeId)->_addPointsTo(id(), qual);
+ }
+ }
+}
+
+void
ConstraintGraph::cloneConstraintGraphMaps(IPA_NODE *caller, IPA_NODE *callee)
{
ConstraintGraph *callerCG =
@@ -2245,18 +2945,48 @@
CG_ST_IDX clone_cg_st_idx =
ConstraintGraph::adjustCGstIdx(caller, clone_st_idx);
StInfo *cloneStInfo = callerCG->stInfo(clone_cg_st_idx);
- // if StInfo does not exist, add
- if (cloneStInfo == NULL) {
+
+ if(cloneStInfo == NULL) {
// Map the StInfo
- callerCG->mapStInfo(origStInfo, orig_cg_st_idx, clone_cg_st_idx);
+ callerCG->cloneStInfo(origStInfo, clone_cg_st_idx);
+ cloneStInfo = callerCG->stInfo(clone_cg_st_idx);
ConstraintGraphNode *orig_node = origStInfo->firstOffset();
+ ConstraintGraphNode *prev_node = NULL;
while (orig_node) {
- callerCG->cloneCGNode(orig_node, clone_cg_st_idx);
+ ConstraintGraphNode *clone_node = callerCG->cloneCGNode(orig_node,
clone_cg_st_idx);
+ if (prev_node == NULL) {
+ cloneStInfo->firstOffset(clone_node);
+ }
+ else {
+ prev_node->nextOffset(clone_node);
+ }
+ clone_node->clearFlags(CG_NODE_FLAGS_VISITED);
+ clone_node->clearFlags(CG_NODE_FLAGS_INLINE_NO_BENEFIT);
+ clone_node->deleteDiffPointsToSet();
+ prev_node = clone_node;
orig_node = orig_node->nextOffset();
}
}
+ else {
+ // already cloned
+ ConstraintGraphNode *orig_node = origStInfo->firstOffset();
+ while (orig_node) {
+ ConstraintGraphNode *clone_node = callerCG->getCGNode(clone_cg_st_idx,
orig_node->offset());
+ // set info for inline analysis
+ // formal nodes updated when processinlineformal is visited and
optimized.
+ if
(IPA_NystromAliasAnalyzer::aliasAnalyzer()->getInlineNodeMap(orig_node->id())
== clone_node->id())
+ clone_node->addFlags(CG_NODE_FLAGS_VISITED);
+ else
+ clone_node->clearFlags(CG_NODE_FLAGS_VISITED);
+ // copy pts to pts diff.
+ if (!clone_node->checkFlags(CG_NODE_FLAGS_INLINE_NO_BENEFIT)) {
+ clone_node->deleteDiffPointsToSet();
+ clone_node->copyPtsToDiff();
+ }
+ orig_node = orig_node->nextOffset();
+ }
+ }
}
- origToCloneStIdxMap.clear();
}
void
Modified: trunk/osprey/ipa/main/analyze/ipa_nystrom_alias_analyzer.h
===================================================================
--- trunk/osprey/ipa/main/analyze/ipa_nystrom_alias_analyzer.h 2011-04-25
23:22:16 UTC (rev 3572)
+++ trunk/osprey/ipa/main/analyze/ipa_nystrom_alias_analyzer.h 2011-04-26
05:21:38 UTC (rev 3573)
@@ -129,6 +129,29 @@
void updateCGForBE(IPA_NODE *node);
+ bool processInlineFormal(IPA_NODE *caller, IPA_NODE *callee, WN* actaul, ST*
formal_st);
+
+ ConstraintGraphNode* getCGNode(WN* wn, IPA_NODE* ipaNode);
+
+ void solveInlineConstraints(IPA_NODE *callee, IPA_NODE *caller);
+
+ bool inlineSolveNode(ConstraintGraphNode *node, ConstraintGraph* callee_cg,
IPA_NODE *caller);
+
+ ConstraintGraphNode* getCloneNode(ConstraintGraphNode *callee_node,
ConstraintGraph* callee_cg, IPA_NODE* caller);
+
+ void addInlineNodeMap(CGNodeId orig, CGNodeId new_cs) {
+ _inline_node_map[orig] = new_cs;
+ }
+
+ CGNodeId getInlineNodeMap(CGNodeId orig) {
+ hash_map<UINT32, UINT32>::const_iterator iter =
_inline_node_map.find(orig);
+ if (iter == _inline_node_map.end())
+ return 0;
+ return iter->second;
+ }
+
+ void updateCloneTreeWithCgnode(WN* tree);
+
// For IPA call graph SCC detection
void allocSCCInfo(IPA_CALL_GRAPH *icg)
{
@@ -213,6 +236,9 @@
// The set of external calls made from within the IPA scope
hash_set<ST_IDX> _extCallSet;
+
+ // hashmap map original cg node id with cloned cg node for nystrom inline
+ hash_map<UINT32, UINT32> _inline_node_map;
};
#endif
Modified: trunk/osprey/ipa/main/optimize/ipo_inline.cxx
===================================================================
--- trunk/osprey/ipa/main/optimize/ipo_inline.cxx 2011-04-25 23:22:16 UTC
(rev 3572)
+++ trunk/osprey/ipa/main/optimize/ipo_inline.cxx 2011-04-26 05:21:38 UTC
(rev 3573)
@@ -72,7 +72,7 @@
#include "clone_DST_utils.h"
#include "ipo_inline.h"
-
+#include "ipa_nystrom_alias_analyzer.h"
static INT initial_initv_tab_size;
MEM_POOL Ipo_mem_pool;
@@ -3127,9 +3127,12 @@
parm->Set_formal_preg (wn_offset);
parm->Set_replace_st (ST_st_idx (copy_st));
#if (!defined(_STANDALONE_INLINER) && !defined(_LIGHTWEIGHT_INLINER))
- if (Alias_Nystrom_Analyzer)
+ if (Alias_Nystrom_Analyzer) {
ConstraintGraph::updateCloneStIdxMap(ST_st_idx(formal_st),
ST_st_idx(copy_st));
+ IPA_NystromAliasAnalyzer::aliasAnalyzer()->processInlineFormal(
+ Caller_node(), Callee_node(), actual, copy_st);
+ }
#endif
} else {
@@ -3249,9 +3252,12 @@
p->Set_replace_st (ST_st_idx (copy_st));
#if (!defined(_STANDALONE_INLINER) && !defined(_LIGHTWEIGHT_INLINER))
- if (Alias_Nystrom_Analyzer)
+ if (Alias_Nystrom_Analyzer){
ConstraintGraph::updateCloneStIdxMap(ST_st_idx(formal_st),
ST_st_idx(copy_st));
+ IPA_NystromAliasAnalyzer::aliasAnalyzer()->processInlineFormal(
+ Caller_node(), Callee_node(), wn_iload, copy_st);
+ }
#endif
@@ -4464,6 +4470,9 @@
if (Alias_Nystrom_Analyzer) {
ConstraintGraph::promoteLocals(Callee_node());
ConstraintGraph::cloneConstraintGraphMaps(Caller_node(), Callee_node());
+
IPA_NystromAliasAnalyzer::aliasAnalyzer()->solveInlineConstraints(Callee_node(),
Caller_node());
+
IPA_NystromAliasAnalyzer::aliasAnalyzer()->updateCloneTreeWithCgnode(aux.inlined_body);
+ ConstraintGraph::clearOrigToCloneStIdxMap(Caller_node(), Callee_node());
}
#endif
------------------------------------------------------------------------------
WhatsUp Gold - Download Free Network Management Software
The most intuitive, comprehensive, and cost-effective network
management toolset available today. Delivers lowest initial
acquisition cost and overall TCO of any competing solution.
http://p.sf.net/sfu/whatsupgold-sd
_______________________________________________
Open64-devel mailing list
Open64-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/open64-devel
