CD-эквивалентные дуги
Алгоритм поиска cd-эквивалентных дуг для каждого узла требует наличия дерева пост-доминаторов и RDJ-графа.
Поиск cd-эквивалентных дуг:
FindCDEdgesLists( CFG_Node ^ node) {
for ( edge = node->GetFirstSuccInSpace(RDJ_EDGE);
edge != nullptr;
edge = edge->GetNextSuccInSpace())
{
succ = edge->GetEdgeSucc();
if (edge->IsDJEdgeJ())
{
if (succ->GetTreeLevel(PDOM_TREE) <= node->GetTreeLevel(PDOM_TREE))
{
for ( cfg_edge = node->GetFirstPred();
cfg_edge != nullptr;
cfg_edge = edge->GetNextPred(cfg_edge))
{
cfg_pred = edge->GetPred();
if ( cfg_pred == succ) break;
}
#ifdef CHECK
if ( cfg_edge == nullptr) fatal();
#endif /* CHECK */
cur_list->ConsRef(cfg_edge);
}
} else
{
FindCDEdgesLists(succ);
}
}
cur_succs_cd_list->ConsRef(cur_list);
cur_succs_cd_list->SetData2(True);
cur_node_list = cur_list;
for ( edge = node->GetFirstSuccInSpace(RDJ_EDGE);
edge != nullptr;
edge = edge->GetNextSuccInSpace())
{
if (edge->IsDJEdgeD())
{
succ = edge->GetSucc();
list_unit = succ->GetCDEdgesList();
cur_succs_cd_lists->ConsRef(list_unit);
cur_succs_cd_lists->SetData2(False);
while(list_unit != nullptr)
{
list_edge = list_unit->GetRef();
succ = list_edge->GetPred();
if ( succ->GetTreeLevel(PDOM_TREE) <= node->GetTreeLevel(PDOM_TREE))
{
cur_list->ConsRef(list_edge);
cur_succs_cd_lists->SetData2(True);
}
list_unit = list_unit->Next();
}
}
}
i =0;
inherited_list= nullptr;
while ( cur_succs_cd_lists != nullptr)
{
list_unit = cur_succs_cd_lists->GetRef();
if ( list_unit != nullptr)
{
if ( cur_succs_cd_lists->GetData2 == True )
{
i++;
inherited_list = list_unit;
}
}
cur_succs_cd_lists = cur_succs_cd_lists->Next();
}
if (i > 1)
{
node->SetCDEdgesList(cur_list);
} else
{
node->SetCDEdgesList(inherited_list);
if ( cur_node_list != inherited_lsit)
{
cur_list->Delete();
}
}
return;
}
void foo() {
...
cCFG_Node ^ stop_node = cfg->GetStopNode();
FindCDEdgesLists(stop_node);
...
}
page revision: 1, last edited: 20 Nov 2006 17:10