in vm/jitrino/src/codegenerator/ia32/Ia32GlobalPropagation.cpp [140:531]
void GlobalPropagation::runImpl()
{
irManager->updateLoopInfo();
MemoryManager mm("global_prop");
StlHashMap<Node*, BBInfo*> BBInfoList(mm);
StlSet<Opnd*> temp(mm);
StlHashMap<Opnd*, Opnd*> newIn(mm);
/* Local analysis and propagation */
const Nodes& postOrdered = irManager->getFlowGraph()->getNodesPostOrder();
for (Nodes::const_reverse_iterator it=postOrdered.rbegin(), end=postOrdered.rend();it!=end;++it) {
Node * node=*it;
BBInfo *bbInfo = new(mm) BBInfo;
BBInfoList[node] = bbInfo;
bbInfo->in = new(mm) StlHashMap<Opnd*, Opnd*>(mm);
bbInfo->out = new(mm) StlHashMap<Opnd*, Opnd*>(mm);
bbInfo->kill = new(mm) StlSet<Opnd*>(mm);
bbInfo->gen = new(mm) StlHashMap<Opnd*, Opnd*>(mm);
bbInfo->visited = false;
/*
* Traverse all INST in a BB in preorder
* For all INST - several DEF, several USE
* + Replace a USE with [USE, src] in GEN
* + Delete [DEF, ...] and [..., DEF] from GEN
* + Add DEF to KILL
*/
for (Inst * inst=(Inst*)node->getFirstInst();inst != NULL;inst=inst->getNextInst()) {
const bool isCopy = inst->getMnemonic() == Mnemonic_MOV;
Inst::Opnds opnds(inst, Inst::OpndRole_All);
for (Inst::Opnds::iterator it=opnds.begin();it != opnds.end();it = opnds.next(it)) {
Opnd * opnd=inst->getOpnd(it);
U_32 roles=inst->getOpndRoles(it);
if (roles & Inst::OpndRole_Use) {
if ((roles & Inst::OpndRole_All & Inst::OpndRole_FromEncoder)
&& (roles & Inst::OpndRole_All & Inst::OpndRole_ForIterator)
&& (roles & Inst::OpndRole_Changeable) && ((roles & Inst::OpndRole_Def) == 0)
&& bbInfo->gen->has(opnd)) {
if (opnd->getType()->isUnmanagedPtr() && (*(bbInfo->gen))[opnd]->getType()->isInteger())
(*(bbInfo->gen))[opnd]->setType(opnd->getType());
inst->setOpnd(it, (*(bbInfo->gen))[opnd]);
}
}
}
for (Inst::Opnds::iterator it = opnds.begin();it != opnds.end();it = opnds.next(it)) {
Opnd * opnd=inst->getOpnd(it);
U_32 roles=inst->getOpndRoles(it);
if (roles & Inst::OpndRole_Def) {
if (bbInfo->gen->has(opnd)) {
bbInfo->gen->erase(opnd);
}
temp.clear();
for(StlHashMap<Opnd*, Opnd*>::iterator iter=bbInfo->gen->begin();
iter!=bbInfo->gen->end();++iter) {
if (iter->second == opnd) {
temp.insert(iter->first);
}
}
for(StlSet<Opnd*>::iterator iter=temp.begin();
iter!=temp.end();++iter) {
bbInfo->gen->erase(*iter);
}
if (!bbInfo->kill->has(opnd))
bbInfo->kill->insert(opnd);
}
}
/*
* For MOV inst which could update the map - one DEF, one USE
* + Add [DEF, USE] to GEN
* - If [USE, s_old] exists in OUT then add [DEF, s_old] instead.
* - Otherwise add [DEF, USE] itself.
*/
if (isCopy) {
Inst::Opnds opnds(inst, Inst::OpndRole_All);
Opnd * dst = NULL;
Opnd * src = NULL;
U_32 counterDef = 0;
U_32 counterUse = 0;
for (Inst::Opnds::iterator it=opnds.begin();it!=opnds.end();it=opnds.next(it)) {
Opnd * opnd = inst->getOpnd(it);
U_32 roles = inst->getOpndRoles(it);
if (roles & Inst::OpndRole_Def) {
counterDef++;
dst = opnd;
} else if (roles & Inst::OpndRole_Use) {
counterUse++;
src = opnd;
}
}
if ((counterDef == 1) && (counterUse == 1) && (!dst->hasAssignedPhysicalLocation())) {
bool kindsAreOk = true;
if(src->canBePlacedIn(OpndKind_FPReg) || dst->canBePlacedIn(OpndKind_FPReg)) {
Constraint srcConstr = src->getConstraint(Opnd::ConstraintKind_Calculated);
Constraint dstConstr = dst->getConstraint(Opnd::ConstraintKind_Calculated);
kindsAreOk = ! (srcConstr&dstConstr).isNull();
}
bool typeConvOk = isTypeConversionAllowed(src, dst);
if (typeConvOk && kindsAreOk && ! src->isPlacedIn(OpndKind_Reg)) {
if (bbInfo->gen->has(src)) {
/* The oldest source is selected heuristically. Some chances maybe missed afterward. */
(*(bbInfo->gen))[dst] = (*(bbInfo->gen))[src];
}
else {
(*(bbInfo->gen))[dst] = src;
}
}
}
}
}
bbInfo->out->insert(bbInfo->gen->begin(), bbInfo->gen->end());
}
#ifdef DEBUG_GLOBAL_PROP
for (Nodes::const_reverse_iterator it=postOrdered.rbegin(),end=postOrdered.rend();it!=end;++it) {
Node * node=*it;
if (isMain)
outputBBInfo(node, BBInfoList[node]);
}
#endif
/* Iterative data-flow analysis */
bool changed = true;
while (changed) {
changed = false;
for (Nodes::const_reverse_iterator it=postOrdered.rbegin(),end = postOrdered.rend();it!=end;++it) {
Node * node = *it;
BBInfo *bbInfo = BBInfoList[node];
if (!bbInfo->visited)
bbInfo->visited = true;
/* Set IN of a BB as the Intersection of all the OUT of its visited predecessors */
const Edges& edges = node->getInEdges();
Edges::const_iterator ite=edges.begin();
Edges::const_iterator ende=edges.end();
Edge* edge = NULL;
Node * pred = NULL;
BBInfo *predBBInfo = NULL;
newIn.clear();
/* Find the first valid predecessor */
while (ite != ende) {
edge = *ite;
pred = edge->getSourceNode();
predBBInfo = BBInfoList[pred];
if (predBBInfo->visited)
break;
pred = NULL;
predBBInfo = NULL;
++ite;
}
if (predBBInfo) {
for(StlHashMap<Opnd*, Opnd*>::iterator iter=predBBInfo->out->begin();
iter!=predBBInfo->out->end();++iter) {
Opnd* dst = iter->first;
Opnd* src = iter->second;
newIn[dst] = src;
}
++ite;
for (;ite!=ende;++ite) {
edge = *ite;
pred = edge->getSourceNode();
predBBInfo = BBInfoList[pred];
if (!predBBInfo->visited)
continue;
/* Do intersection */
temp.clear();
for(StlHashMap<Opnd*, Opnd*>::iterator iter=newIn.begin();
iter!=newIn.end();++iter) {
Opnd* dst = iter->first;
if (!predBBInfo->out->has(dst)) {
temp.insert(dst);
}
else {
Opnd* src = (*(predBBInfo->out))[dst];
Opnd* exSrc = iter->second;
if (src != BOTTOM) {
if (exSrc == BOTTOM)
src = BOTTOM;
else if ((exSrc != src) && (!(exSrc->isPlacedIn(OpndKind_Imm)
&& src->isPlacedIn(OpndKind_Imm) && (exSrc->getImmValue() == src->getImmValue()))))
src = BOTTOM;
}
if (src == BOTTOM) {
temp.insert(dst);
}
}
}
for(StlSet<Opnd*>::iterator iter=temp.begin();
iter!=temp.end();++iter) {
newIn.erase(*iter);
}
}
}
bool equal = true;
for (StlHashMap<Opnd*, Opnd*>::iterator iter=newIn.begin();
iter!=newIn.end();++iter) {
if (!((bbInfo->in->has(iter->first)) && ((*(bbInfo->in))[iter->first] == iter->second))) {
equal = false;
break;
}
}
if (equal) {
for (StlHashMap<Opnd*, Opnd*>::iterator iter=bbInfo->in->begin();
iter!=bbInfo->in->end();++iter) {
if (!((newIn.has(iter->first)) && (newIn[iter->first] == iter->second))) {
equal = false;
break;
}
}
}
if (!equal) {
bbInfo->in->clear();
bbInfo->in->insert(newIn.begin(), newIn.end());
if (!changed)
changed = true;
} else {
continue;
}
/* Compute OUT from current IN and invariant KILL, GEN */
bbInfo->out->clear();
for(StlHashMap<Opnd*, Opnd*>::iterator iter=bbInfo->in->begin();
iter!=bbInfo->in->end();++iter) {
Opnd* dst = iter->first;
Opnd* src = iter->second;
if (!(bbInfo->kill->has(dst) || bbInfo->kill->has(src)))
(*(bbInfo->out))[dst] = src;
}
/*
* Try to add [d_new, s_new] from GEN to OUT
* - If [s_new, s_old] exists in OUT then add [d_new, s_old] instead.
* - Otherwise add [d_new, s_new] itself.
*/
for(StlHashMap<Opnd*, Opnd*>::iterator iterr=bbInfo->gen->begin();
iterr!=bbInfo->gen->end();++iterr) {
Opnd* dst = iterr->first;
Opnd* src = iterr->second;
assert(!bbInfo->out->has(dst));
if (bbInfo->out->has(src))
(*(bbInfo->out))[dst] = (*(bbInfo->out))[src];
else
(*(bbInfo->out))[dst] = src;
}
}
#ifdef DEBUG_GLOBAL_PROP
for (Nodes::const_reverse_iterator it=postOrdered.rbegin(),end=postOrdered.rend();it!=end;++it) {
Node * node=*it;
if (isMain)
outputBBInfo(node, BBInfoList[node]);
}
#endif
}
#ifdef DEBUG_GLOBAL_PROP
for (Nodes::const_reverse_iterator it=postOrdered.rbegin(),end=postOrdered.rend();it!=end;++it) {
Node * node=*it;
if (isMain)
outputBBInfo(node, BBInfoList[node]);
}
#endif
/* Local propagation for the pairs in IN */
for (Nodes::const_reverse_iterator it=postOrdered.rbegin(), end=postOrdered.rend();it!=end;++it) {
Node * node=*it;
if (!node->isBlockNode()) {
continue;
}
BBInfo *bbInfo = BBInfoList[node];
/*
* Traverse all INST in a BB in preorder
* For all INST - several DEF, several USE
* + Replace a USE with [USE, src] in IN
* + Delete [DEF, ...] and [..., DEF] from IN
* + Add DEF to KILL
*/
for (Inst * inst=(Inst*)node->getFirstInst();inst != NULL;inst=inst->getNextInst()) {
const bool isCopy = inst->getMnemonic() == Mnemonic_MOV;
Inst::Opnds opnds(inst, Inst::OpndRole_All);
for (Inst::Opnds::iterator it=opnds.begin();it != opnds.end();it = opnds.next(it)) {
Opnd * opnd=inst->getOpnd(it);
U_32 roles=inst->getOpndRoles(it);
if (roles & Inst::OpndRole_Use) {
if ((roles & Inst::OpndRole_All & Inst::OpndRole_FromEncoder)
&& (roles & Inst::OpndRole_All & Inst::OpndRole_ForIterator)
&& (roles & Inst::OpndRole_Changeable) && ((roles & Inst::OpndRole_Def) == 0)
&& bbInfo->in->has(opnd) && ((*(bbInfo->in))[opnd] != BOTTOM)) {
assert((*(bbInfo->in))[opnd] != BOTTOM);
if (opnd->getType()->isUnmanagedPtr() && (*(bbInfo->in))[opnd]->getType()->isInteger())
(*(bbInfo->in))[opnd]->setType(opnd->getType());
inst->setOpnd(it, (*(bbInfo->in))[opnd]);
}
}
}
for (Inst::Opnds::iterator it = opnds.begin();it != opnds.end();it = opnds.next(it)) {
Opnd * opnd=inst->getOpnd(it);
U_32 roles=inst->getOpndRoles(it);
if (roles & Inst::OpndRole_Def) {
if (bbInfo->in->has(opnd)) {
bbInfo->in->erase(opnd);
}
temp.clear();
for(StlHashMap<Opnd*, Opnd*>::iterator iter=bbInfo->in->begin();
iter!=bbInfo->in->end();++iter) {
if (iter->second == opnd) {
temp.insert(iter->first);
}
}
for(StlSet<Opnd*>::iterator iter=temp.begin();
iter!=temp.end();++iter) {
bbInfo->in->erase(*iter);
}
if (!bbInfo->kill->has(opnd))
bbInfo->kill->insert(opnd);
}
}
/*
* For MOV inst which could update the map - one DEF, one USE
* + Try to add [DEF, USE] to IN
* - If [USE, s_old] exists in IN then add [DEF, s_old] too.
* - Otherwise add [DEF, USE] itself.
*/
if (isCopy) {
Inst::Opnds opnds(inst, Inst::OpndRole_All);
Opnd * dst = NULL;
Opnd * src = NULL;
U_32 counterDef = 0;
U_32 counterUse = 0;
for (Inst::Opnds::iterator it=opnds.begin();it!=opnds.end();it=opnds.next(it)) {
Opnd * opnd = inst->getOpnd(it);
U_32 roles = inst->getOpndRoles(it);
if (roles & Inst::OpndRole_Def) {
counterDef++;
dst = opnd;
} else if (roles & Inst::OpndRole_Use) {
counterUse++;
src = opnd;
}
}
if ((counterDef == 1) && (counterUse == 1) && (!dst->hasAssignedPhysicalLocation())) {
bool kindsAreOk = true;
if(src->canBePlacedIn(OpndKind_FPReg) || dst->canBePlacedIn(OpndKind_FPReg)) {
Constraint srcConstr = src->getConstraint(Opnd::ConstraintKind_Calculated);
Constraint dstConstr = dst->getConstraint(Opnd::ConstraintKind_Calculated);
kindsAreOk = ! (srcConstr&dstConstr).isNull();
}
bool typeConvOk = isTypeConversionAllowed(src, dst);
if (typeConvOk && kindsAreOk && ! src->isPlacedIn(OpndKind_Reg)) {
if (bbInfo->in->has(src)) {
/* The oldest source is selected heuristically. Some chances maybe missed afterward. */
(*(bbInfo->in))[dst] = (*(bbInfo->in))[src];
}
else {
(*(bbInfo->in))[dst] = src;
}
}
}
}
}
}
}