in vm/jitrino/src/dynopt/EdgeProfiler.cpp [255:503]
static bool calculateProbsFromProfile(MemoryManager& mm, ControlFlowGraph& fg, const Edges& pEdges,
DominatorTree* dt, LoopTree* lt, EdgeMethodProfile* profile,
bool bcLevelProfiling, const StlSet<Node*>& nodesToIgnore)
{
//calculate edge freqs and use them to calculate edge probs.
bool debug = Log::isEnabled();
if (debug) {
Log::out()<<"Starting probs calculation" <<std::endl;
}
U_32 entryCount = *profile->getEntryCounter();
//1. assign default value to nodes and edges, this value is used for consistency checks latter
StlVector<Node*> nodes(mm);
fg.getNodesPostOrder(nodes);
for (StlVector<Node*>::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
Node* node = *it;
node->setExecCount(-1);
const Edges& edges = node->getOutEdges();
for (Edges::const_iterator it2 = edges.begin(), end2 = edges.end(); it2!=end2; ++it2) {
Edge* edge = *it2;
edge->setEdgeProb(-1);
}
}
//2. calculate edge-freq for every edge.
//2.1 get freqs from profile
StlVector<double> edgeFreqs(mm, fg.getMaxEdgeId(), -1);
U_32 n = 1;
for (Edges::const_iterator it = pEdges.begin(), end = pEdges.end(); it!=end; ++it, ++n) {
Edge* edge = *it;
U_32 key = genKey(n, edge, bcLevelProfiling, debug);
U_32* counterAddr = profile->getCounter(key);
//assert(bcLevelProfiling || counterAddr!=NULL); -> TODO: hits in lazy resolution mode
U_32 freq = 0;
if (counterAddr == NULL) {
if (!bcLevelProfiling) { //avoid crash, use static profiler for a method
return false;
}
} else {
freq = *counterAddr;
}
setEdgeFreq(edgeFreqs, edge, freq, debug);
}
//2.2 propagate edge frequencies on linear paths
// this operation is needed because we do not instrument artificial edges (edges that connect nodes with the same bc-mapping)
if (bcLevelProfiling) {
for (StlVector<Node*>::reverse_iterator it = nodes.rbegin(), end = nodes.rend(); it!=end; ++it) {
Node* node = *it;
const Edges& outEdges = node->getOutEdges();
for (Edges::const_iterator it2 = outEdges.begin(), end2 = outEdges.end(); it2!=end2; ++it2) {
Edge* edge = *it2;
double freq = edgeFreqs[edge->getId()];
if (freq==-1) { //this edge has no profile -> can't use it for propagation
continue;
}
Node* targetNode = edge->getTargetNode();
//check pattern for artificial nodes: 1 unconditional + no changes in bcmapping
if (targetNode->isBlockNode() && targetNode->getOutDegree() <= 2 && targetNode->getUnconditionalEdge()!=NULL) {
Edge* unconditionalEdge = targetNode->getUnconditionalEdge();
if (targetNode->getFirstInst()->getBCOffset() == unconditionalEdge->getTargetNode()->getFirstInst()->getBCOffset()) {
double ufreq = edgeFreqs[unconditionalEdge->getId()];
double newUFreq= freq + MAX(ufreq, 0);
if (debug) {
Log::out()<<"Restoring profile for artificial edge : edge-id="<<unconditionalEdge->getId()<<std::endl;
}
setEdgeFreq(edgeFreqs, unconditionalEdge, newUFreq, debug);
}
}
}
}
}
//2.3 fix catch freqs, so we will have estimated D->C edges
if (debug) {
Log::out()<<"\tFixing catch freqs"<<std::endl;
}
for (StlVector<Node*>::reverse_iterator it = nodes.rbegin(), end = nodes.rend(); it!=end; ++it) {
Node* node = *it;
bool ignored = nodesToIgnore.find(node)!=nodesToIgnore.end();
if (!node->isCatchBlock() || ignored) {
continue;
}
//set up catch block prob -> will be used for dispatch nodes.
double nodeFreq = 0;
const Edges& outEdges = node->getOutEdges();
for (Edges::const_iterator it2 = outEdges.begin(), end2 = outEdges.end(); it2!=end2; ++it2) {
Edge* edge = *it2;
double edgeFreq = edgeFreqs[edge->getId()];
edgeFreq = MAX(0, edgeFreq); //if Cn->Ln edge is marked as artificial it's not instrumented
nodeFreq+=edgeFreq;
}
node->setExecCount(nodeFreq);
if (debug) {
Log::out()<<"\t\t fixing catch node ";FlowGraph::printLabel(Log::out(), node);Log::out()<<" freq="<<nodeFreq<<std::endl;
}
updateDispatchPathsToCatch(node, edgeFreqs, debug);
}
//2.4 calculate freqs for every edge in topological order
// set up nodes exec count for every node.
if (debug) {
Log::out()<<"\tPropagating edge freqs"<<std::endl;
}
for (StlVector<Node*>::reverse_iterator it = nodes.rbegin(), end = nodes.rend(); it!=end; ++it) {
Node* node = *it;
bool ignored = nodesToIgnore.find(node)!=nodesToIgnore.end();
double nodeFreq = 0;
const Edges& outEdges = node->getOutEdges();
const Edges& inEdges = node->getInEdges();
if (debug) {
Log::out()<<"\t\tNode="; FlowGraph::printLabel(Log::out(), node);Log::out()<<" in-edges="<<inEdges.size() << " was ignored="<<ignored<<std::endl;
}
if (node->getInDegree() == 0) {
assert(node == fg.getEntryNode());
nodeFreq = entryCount;
} else if (node->isCatchBlock()) { //set up catch block prob -> will be used for dispatch nodes.
if (ignored) {
// ignored catch edge (successor of ignored node or catch-loop)
// max we can do here is to try to get catch freq from in-edge
double _freq = 0;
Edge* inEdge = *node->getInEdges().begin();
if (node->getInDegree() == 1 && edgeFreqs[inEdge->getId()]>=0) {
_freq = edgeFreqs[inEdge->getId()];
}
Edge* outEdge = *node->getOutEdges().begin();
nodeFreq = edgeFreqs[outEdge->getId()] = _freq;
} else {//all out-edges were instrumented -> easy to calculate freq
nodeFreq = node->getExecCount(); //already assigned
assert(nodeFreq>=0);
}
} else {
for (Edges::const_iterator it2 = inEdges.begin(), end2 = inEdges.end(); it2!=end2; ++it2) {
Edge* edge = *it2;
Node* srcNode = edge->getSourceNode();
//assign edge-freq when available
//or 0-freq when source is dispatch (catches handled separately)
//or freq of src node when src node was removed from instrumentation(equal freq for all out-edges)
double edgeFreq = 0;
if (nodesToIgnore.find(srcNode)!=nodesToIgnore.end()) {
assert(srcNode->getExecCount()!= -1 || (srcNode->isCatchBlock() && dt->dominates(node, srcNode)) || (hasCatch(node) && srcNode->isEmpty()));
edgeFreq = srcNode->getExecCount();
} else if (srcNode->isBlockNode()) {
edgeFreq = edgeFreqs[edge->getId()];
}
if (debug) {
Log::out()<<"\t\t\tedge id="<<edge->getId()<<" from="; FlowGraph::printLabel(Log::out(), srcNode);
Log::out()<<" freq="<<edgeFreq<<std::endl;
}
if (edgeFreq == -1) {
//the only way to get not estimated edge here is to have catch loops (monexit pattern)
#ifdef _DEBUG
Node* head = lt->getLoopHeader(node, false); //catch loops are not instrumented
assert(head != NULL && (head->isCatchBlock() || head->isDispatchNode() || hasCatch(head)));
#endif
edgeFreq = 0;
setEdgeFreq(edgeFreqs, edge, edgeFreq, debug);
}
nodeFreq +=edgeFreq;
}
}
if (debug) {
Log::out()<<"\t\t\tnode freq="<<nodeFreq<<std::endl;
}
assert(nodeFreq!=-1);
node->setExecCount(nodeFreq);
if (node->isExitNode()) {
continue;
}
//now we able to calculate all outgoing edge freqs for current node
//if node is bb -> only 1 edge is allowed to be without freq here and we will fix it
//if node is dispatch -> use catch node freqs
//if node was ignored -> equal freq for every bb edge, 0 to dispatch edge
double freqLeft = nodeFreq;
if (ignored) {
if ( outEdges.size()==1 ) {
Edge* edge = *outEdges.begin();
setEdgeFreq(edgeFreqs, edge, nodeFreq, debug);
} else {
double freqPerBB = nodeFreq / (outEdges.size() - (node->getExceptionEdge() == NULL ? 0 : 1));
for (Edges::const_iterator it = outEdges.begin(), end = outEdges.end(); it!=end; ++it) {
Edge* edge = *it;
setEdgeFreq(edgeFreqs, edge, edge->getTargetNode()->isBlockNode() ? freqPerBB : 0, debug);
}
}
} else if (node->isBlockNode()) {
Edge* notEstimatedEdge = NULL;
for (Edges::const_iterator it2 = outEdges.begin(), end2 = outEdges.end(); it2!=end2; ++it2) {
Edge* edge = *it2;
double edgeFreq = edgeFreqs[edge->getId()];
if (edgeFreq != -1) {
freqLeft-=edgeFreq;
} else {
// here we can have 2 not-estimated edges only of this block was connected to 'ignored' node during annotation.
if (notEstimatedEdge == NULL) {
notEstimatedEdge = edge;
} else if (notEstimatedEdge->getTargetNode()->isDispatchNode()) {
setEdgeFreq(edgeFreqs, notEstimatedEdge, 0, debug);
notEstimatedEdge = edge;
} else {
setEdgeFreq(edgeFreqs, edge, 0, debug);
}
}
}
if (notEstimatedEdge!=NULL) {
freqLeft = freqLeft < 0 ? 0 : freqLeft;
setEdgeFreq(edgeFreqs, notEstimatedEdge, freqLeft, debug);
}
} else if (node->isDispatchNode()) {
//for all not estimated on step 2.2 D->X edges set edge prob to min (0).
for (Edges::const_iterator it = outEdges.begin(), end = outEdges.end(); it!=end; ++it) {
Edge* edge = *it;
double _freq = edgeFreqs[edge->getId()];
if (_freq==-1) {
setEdgeFreq(edgeFreqs, edge, 0, false);
}
}
}
}
//3. calculate edge probs using edge freqs.
if (debug) {
Log::out()<<"Calculating edge probs using freqs.."<<std::endl;
}
for (StlVector<Node*>::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it, n++) {
Node* node = *it;
double nodeFreq = node->getExecCount();
assert(nodeFreq!=-1);
const Edges& edges = node->getOutEdges();
for (Edges::const_iterator it2 = edges.begin(), end2 = edges.end(); it2!=end2; ++it2) {
Edge* edge = *it2;
double edgeFreq =edgeFreqs[edge->getId()];
assert(edgeFreq!=-1);
double edgeProb = nodeFreq == 0 ? 0 : edgeFreq / nodeFreq ;
// assert(edgeProb >= 0 && edgeProb <= 1);
edge->setEdgeProb(edgeProb);
}
}
if (debug) {
Log::out()<<"Finished probs calculation";
}
return true;
}