| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| /** |
| * @author Intel, Mikhail Y. Fursov |
| * |
| */ |
| |
| #include "StaticProfiler.h" |
| #include "ControlFlowGraph.h" |
| #include "Dominator.h" |
| #include "Loop.h" |
| #include "constantfolder.h" |
| #include "mkernel.h" |
| #include "Stl.h" |
| #include "FlowGraph.h" |
| |
| /** see article: "Static Branch Frequency and Program Profile Analysis / Wu, Laurus, IEEE/ACM 1994" */ |
| |
| //TODO: avoid using postdom information. A lot of exceptions-paths make it useless. |
| |
| namespace Jitrino{ |
| |
| DEFINE_SESSION_ACTION(StaticProfilerPass, statprof, "Perform edge annotation pass based on static heuristics"); |
| |
| class StaticProfilerContext; |
| |
| |
| #define MAX(a,b) (((a) > (b)) ? (a) : (b)) |
| #define ABS(a) (((a) > (0)) ? (a) : -(a)) |
| |
| //probabilities of taken branch |
| #define PROB_ALL_EXCEPTIONS 0.0000001 |
| #define PROB_HEURISTIC_FAIL 0.50 |
| #define PROB_LOOP_EXIT 0.10 |
| #define PROB_OPCODE_HEURISTIC 0.84 |
| #define PROB_CALL_HEURISTIC 0.78 |
| #define PROB_LOOP_HEADER_HEURISTIC 0.75 |
| #define PROB_RET_HEURISTIC 0.72 |
| #define PROB_DEVIRT_GUARD_HEURISTIC 0.62 |
| #define PROB_REFERENCE 0.60 |
| #define PROB_STORE_HEURISTIC 0.55 |
| #define PROB_FALLTHRU_HEURISTIC 0.45 |
| |
| #define ACCEPTABLE_DOUBLE_PRECISION_LOSS 0.000000001 |
| |
| #define DEFAULT_ENTRY_NODE_FREQUENCY 10000 |
| |
| /** returns edge1 probability |
| Explicit parameters used here help to avoid code duplication in impl functions |
| */ |
| typedef double(*HeuristicsFn) (const StaticProfilerContext*); |
| |
| static double callHeuristic(const StaticProfilerContext*); |
| static double returnHeuristic(const StaticProfilerContext*); |
| static double loopHeaderHeuristic(const StaticProfilerContext*); |
| static double opcodeHeuristic(const StaticProfilerContext*); |
| static double storeHeuristic(const StaticProfilerContext*); |
| static double referenceHeuristic(const StaticProfilerContext*); |
| static double devirtGuardHeuristic(const StaticProfilerContext*); |
| static double fallThruHeuristic(const StaticProfilerContext*); |
| static void setHeatThreshold(IRManager& irm); |
| typedef std::vector<std::string> StringList; |
| static void splitString(const char* string, StringList& result, char separator, bool notEmptyTokensOnly); |
| |
| struct Heuristics { |
| std::string name; |
| HeuristicsFn fn; |
| |
| Heuristics(const std::string& _name, HeuristicsFn _fn) : name(_name), fn(_fn){} |
| Heuristics(){name="", fn=NULL;} |
| }; |
| |
| Heuristics HEURISTICS[] = { |
| Heuristics("loop", loopHeaderHeuristic), |
| Heuristics("call", callHeuristic), |
| Heuristics("ret", returnHeuristic), |
| Heuristics("opcode", opcodeHeuristic), |
| Heuristics("store", storeHeuristic), |
| Heuristics("ref", referenceHeuristic), |
| Heuristics("guard", devirtGuardHeuristic), |
| Heuristics("ft", fallThruHeuristic), |
| Heuristics("", NULL) |
| }; |
| |
| static Heuristics* findHeuristicsByName(const std::string& name) { |
| for (int i=0;;i++) { |
| Heuristics* h = &HEURISTICS[i]; |
| if (h->name == name) { |
| return h; |
| } |
| if (h->name.empty()) { |
| break; |
| } |
| } |
| return NULL; |
| } |
| |
| class StaticProfilerContext { |
| public: |
| IRManager& irm; |
| ControlFlowGraph* fg; |
| Node* node; |
| Edge* edge1; //trueEdge |
| Edge* edge2; //falseEdge |
| DominatorTree* domTree; |
| DominatorTree* postDomTree; |
| LoopTree* loopTree; |
| StlVector<Heuristics*> heuristics; |
| bool doLoopHeuristicsOverride; |
| |
| StaticProfilerContext(IRManager& _irm) |
| : irm(_irm), fg (&_irm.getFlowGraph()), node(NULL), edge1(NULL), edge2(NULL), |
| domTree(NULL), postDomTree(NULL), loopTree(NULL), |
| heuristics(_irm.getMemoryManager()), doLoopHeuristicsOverride(true) |
| { |
| initDefaultHeuristics(); |
| |
| OptPass::computeDominatorsAndLoops(irm, false); |
| |
| loopTree = irm.getLoopTree(); |
| domTree = irm.getDominatorTree(); |
| postDomTree = DominatorBuilder().computePostdominators(irm.getNestedMemoryManager(), fg, true); |
| fillActiveHeuristicsList(); |
| } |
| |
| private: |
| void fillActiveHeuristicsList() { |
| const OptimizerFlags& optFlags = irm.getOptimizerFlags(); |
| doLoopHeuristicsOverride = optFlags.statprof_do_loop_heuristics_override; |
| const char* heuristicsNamesList = optFlags.statprof_heuristics; |
| if (heuristicsNamesList == NULL) { |
| heuristics.resize(defaultHeuristics.size()); |
| std::copy(defaultHeuristics.begin(), defaultHeuristics.end(), heuristics.begin()); |
| } else { |
| getHeuristicsByNamesList(heuristicsNamesList, heuristics); |
| } |
| |
| } |
| |
| static void initDefaultHeuristics() { |
| static Mutex initMutex; |
| static bool defaultHeuristicsInited = false; |
| if (!defaultHeuristicsInited) { |
| initMutex.lock(); |
| if (!defaultHeuristicsInited) { |
| getHeuristicsByNamesList("loop,ret,ft,guard", defaultHeuristics); |
| defaultHeuristicsInited = true; |
| } |
| initMutex.unlock(); |
| } |
| } |
| |
| template <class Container> |
| static void getHeuristicsByNamesList(const char* list, Container& result) { |
| StringList nameList; |
| splitString(list, nameList, ',', true); |
| for (StringList::const_iterator it = nameList.begin(), end = nameList.end(); it!=end; ++it) { |
| const std::string& name = *it; |
| Heuristics* h = findHeuristicsByName(name); |
| assert(h!=NULL); |
| result.push_back(h); |
| } |
| } |
| |
| private: |
| static std::vector<Heuristics*> defaultHeuristics; |
| |
| }; |
| |
| std::vector<Heuristics*> StaticProfilerContext::defaultHeuristics; |
| |
| |
| static void estimateNode(StaticProfilerContext* c); |
| |
| /** looks for unconditional path to inner loop header. |
| */ |
| static Node* findLoopHeaderOnUncondPath(Node* parentLoopHeader, LoopTree* loopTree, Edge* edge) { |
| Node* node = edge->getTargetNode(); |
| if (!node->isBlockNode() || node == parentLoopHeader) { |
| return NULL; |
| } |
| |
| if (loopTree->isLoopHeader(node)) { |
| return node; |
| } |
| Edge* uncondEdge = node->getUnconditionalEdge(); |
| if (uncondEdge==NULL) { |
| return NULL; |
| } |
| return findLoopHeaderOnUncondPath(parentLoopHeader, loopTree, uncondEdge); |
| } |
| |
| /** returns TRUE if |
| * 1) edge is back-edge |
| * 2) if lookForDirectPath == TRUE returns isBackedge(edge->targetNode->targetUncondOutEdge ) |
| * if targetUncondOutEdge is the only unconditional edge of targetNode |
| */ |
| static inline bool isBackedge(LoopTree* loopTree, Edge* e, bool lookForDirectPath) { |
| Node* loopHeader = loopTree->getLoopHeader(e->getSourceNode(), false); |
| if (loopHeader == NULL) { |
| return false; |
| } |
| Node* targetNode = e->getTargetNode(); |
| if (targetNode == loopHeader) { |
| return true; |
| } |
| if (lookForDirectPath) { |
| Edge* targetUncondOutEdge = targetNode->getUnconditionalEdge(); |
| if (targetUncondOutEdge !=NULL) { |
| return isBackedge(loopTree, targetUncondOutEdge, lookForDirectPath); |
| } |
| } |
| return false; |
| } |
| |
| static bool isLoopHeuristicAcceptable(StaticProfilerContext* c) { |
| bool edge1IsLoopExit = c->loopTree->isLoopExit(c->edge1); |
| bool edge2IsLoopExit = c->loopTree->isLoopExit(c->edge2); |
| assert (!(edge1IsLoopExit && edge2IsLoopExit)); //both edges could not be loop exits at the same time |
| return edge1IsLoopExit || edge2IsLoopExit; |
| } |
| |
| void StaticProfiler::estimateGraph( IRManager& irm, double entryFreq, bool cleanOldEstimations) { |
| assert(entryFreq >= 0); |
| if (entryFreq == 0) { |
| entryFreq = DEFAULT_ENTRY_NODE_FREQUENCY; |
| } |
| if (irm.getFlowGraph().hasEdgeProfile() && !cleanOldEstimations) { |
| fixEdgeProbs(irm); |
| } else { |
| StaticProfilerContext c(irm); |
| const Nodes& nodes = c.fg->getNodes(); |
| for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) { |
| Node* node = *it; |
| c.node = node; |
| c.edge1 = NULL; |
| c.edge2 = NULL; |
| estimateNode(&c); |
| } |
| c.fg->getEntryNode()->setExecCount(entryFreq); |
| c.fg->setEdgeProfile(true); |
| } |
| irm.getFlowGraph().smoothEdgeProfile(); |
| |
| if (irm.getHeatThreshold()<=0) { |
| setHeatThreshold(irm); |
| } |
| } |
| |
| static void setHeatThreshold(IRManager& irm) { |
| const OptimizerFlags& optimizerFlags = irm.getOptimizerFlags(); |
| ControlFlowGraph& flowGraph = irm.getFlowGraph(); |
| double profile_threshold = optimizerFlags.profile_threshold; |
| if(optimizerFlags.use_average_threshold) { |
| // Keep a running average of method counts. |
| static U_32 count = 0; |
| static double total = 0.0; |
| count++; |
| double methodFreq = flowGraph.getEntryNode()->getExecCount(); |
| assert(methodFreq > 0); |
| total += methodFreq; |
| irm.setHeatThreshold(total / count); |
| } else if(optimizerFlags.use_minimum_threshold) { |
| double methodFreq = flowGraph.getEntryNode()->getExecCount(); |
| if(methodFreq < profile_threshold) { |
| methodFreq = profile_threshold; |
| } |
| irm.setHeatThreshold(methodFreq); |
| } else if(optimizerFlags.use_fixed_threshold) { |
| irm.setHeatThreshold(profile_threshold); |
| } else { |
| // Use the method entry |
| irm.setHeatThreshold(flowGraph.getEntryNode()->getExecCount()); |
| } |
| if (Log::isEnabled()) { |
| Log::out() << "Heat threshold = " << irm.getHeatThreshold() << std::endl; |
| } |
| } |
| |
| |
| void StaticProfilerPass::_run(IRManager& irm) { |
| OptPass::computeDominatorsAndLoops(irm, false); |
| StaticProfiler::estimateGraph(irm, DEFAULT_ENTRY_NODE_FREQUENCY); |
| } |
| |
| static void estimateNode(StaticProfilerContext* c) { |
| const Edges& edges = c->node->getOutEdges(); |
| if (edges.empty()) { |
| return; |
| } else if (edges.size() == 1) { |
| (*edges.begin())->setEdgeProb(1.0); |
| return; |
| } else { |
| for (Edges::const_iterator it = edges.begin(), itEnd = edges.end(); it!=itEnd; it++) { |
| Edge* e = *it; |
| e->setEdgeProb(0.0); |
| } |
| } |
| Edge* falseEdge = c->node->getFalseEdge(); |
| Edge* trueEdge = c->node->getTrueEdge(); |
| double probLeft = 1.0; |
| U_32 edgesLeft = (U_32)edges.size(); |
| if (falseEdge == NULL || trueEdge == NULL) { // can't apply general heuristics. |
| Edge* uncondEdge = c->node->getUnconditionalEdge(); |
| if (uncondEdge) { |
| uncondEdge->setEdgeProb(1 - PROB_ALL_EXCEPTIONS); |
| probLeft-=uncondEdge->getEdgeProb(); |
| edgesLeft--; |
| } |
| } else if (((Inst*)c->node->getLastInst())->isSwitch()) { |
| assert(c->node->getExceptionEdge() == 0); |
| falseEdge->setEdgeProb(0.5); |
| probLeft = 0.5; |
| edgesLeft--; |
| } else { |
| assert(falseEdge->getTargetNode()!=trueEdge->getTargetNode()); |
| |
| double prob = 0.5; // trueEdge prob |
| |
| // separate back-edge heuristic from others heuristics (the way it's done in article) |
| c->edge1 = trueEdge; |
| c->edge2 = falseEdge; |
| if (c->doLoopHeuristicsOverride && isLoopHeuristicAcceptable(c)) { |
| prob = c->loopTree->isLoopExit(trueEdge) ? PROB_LOOP_EXIT : 1 - PROB_LOOP_EXIT; |
| } else if (c->node->getTraversalNum() == c->fg->getTraversalNum()) {//node is reachable |
| // from this point we can apply general heuristics |
| for (StlVector<Heuristics*>::const_iterator it = c->heuristics.begin(), end = c->heuristics.end(); it!=end; ++it) { |
| Heuristics* h = *it; |
| HeuristicsFn fn = h->fn; |
| double dprob = (*fn)(c); |
| assert(dprob>0 && dprob<1); |
| if (dprob!=PROB_HEURISTIC_FAIL) { |
| double newprob = prob*dprob / (prob*dprob + (1-prob)*(1-dprob)); |
| assert(newprob>0 && newprob<1); |
| prob = newprob; |
| } |
| } |
| } |
| // all other edges (exception, catch..) have lower probability |
| double othersProb = edges.size() == 2 ? 0.0 : PROB_ALL_EXCEPTIONS; |
| trueEdge->setEdgeProb(prob - othersProb/2); |
| falseEdge->setEdgeProb(1 - prob - othersProb/2); |
| assert(trueEdge->getEdgeProb()!=0); |
| assert(falseEdge->getEdgeProb()!=0); |
| probLeft = othersProb; |
| edgesLeft-=2; |
| } |
| |
| if (edgesLeft != 0) { |
| double probPerEdge = probLeft / edgesLeft; |
| for (Edges::const_iterator it = edges.begin(), itEnd = edges.end(); it!=itEnd; it++) { |
| Edge* e = *it; |
| if (e->getEdgeProb()==0.0) { |
| e->setEdgeProb(probPerEdge); |
| } |
| } |
| } |
| |
| #ifdef _DEBUG //debug check |
| double probe = 0; |
| for (Edges::const_iterator it = edges.begin(), itEnd = edges.end(); it!=itEnd; it++) { |
| Edge* e = *it; |
| double dprob = e->getEdgeProb(); |
| assert (dprob!=0.0); |
| probe+=dprob; |
| } |
| assert(ABS(probe - 1.0) < ACCEPTABLE_DOUBLE_PRECISION_LOSS); |
| #endif |
| } |
| |
| |
| /** looks for Inst with opcode in specified range (both bounds are included) |
| * in specified node and it's unconditional successors. |
| */ |
| static inline Inst* findInst(Node* node, Opcode opcodeFrom, Opcode opcodeTo) { |
| for (Inst *i = (Inst*)node->getFirstInst(); i!=NULL ; i = i->getNextInst()) { |
| Opcode opcode = i->getOpcode(); |
| if (opcode>=opcodeFrom && opcode<=opcodeTo) { |
| return i; |
| } |
| } |
| |
| Edge* uncondEdge = node->getUnconditionalEdge(); |
| if (uncondEdge!=NULL && uncondEdge->getTargetNode()->getInEdges().size() == 1) { |
| return findInst(uncondEdge->getTargetNode(), opcodeFrom, opcodeTo); |
| } |
| return NULL; |
| } |
| |
| static inline Inst* findInst(Node* node, Opcode opcode) { |
| return findInst(node, opcode, opcode); |
| } |
| |
| |
| /** Call heuristic (CH). |
| * Predict a successor that contains |
| * a call and does not post-dominate will not be taken. |
| */ |
| static double callHeuristic(const StaticProfilerContext* c) { |
| Node* node1 = c->edge1->getTargetNode(); |
| Node* node2 = c->edge2->getTargetNode(); |
| bool node1HasCall = findInst(node1, Op_DirectCall, Op_VMHelperCall)!=NULL; |
| bool node2HasCall = findInst(node2, Op_DirectCall, Op_VMHelperCall)!=NULL; |
| |
| if (!node1HasCall && !node2HasCall) { |
| return PROB_HEURISTIC_FAIL; |
| } |
| |
| // at least one node has call from this point |
| bool node1Post = false; |
| bool node2Post = false; |
| |
| if (node1HasCall) { |
| node1Post = c->postDomTree->dominates(node1, c->node); |
| if (!node1Post && !node2HasCall) { |
| return 1 - PROB_CALL_HEURISTIC; |
| } |
| } |
| if (node2HasCall) { |
| node2Post = c->postDomTree->dominates(node2, c->node); |
| if (!node2Post && !node1HasCall) { |
| return PROB_CALL_HEURISTIC; |
| } |
| } |
| |
| if (node1HasCall != node2HasCall) { |
| return PROB_HEURISTIC_FAIL; |
| } |
| |
| // both nodes have call from this point |
| return node1Post==node2Post ? PROB_HEURISTIC_FAIL: (!node1Post ? 1- PROB_CALL_HEURISTIC: PROB_CALL_HEURISTIC); |
| |
| } |
| |
| |
| /** Return heuristic (RH). |
| * Predict a successor that contains a return will not be taken. |
| */ |
| static double returnHeuristic(const StaticProfilerContext* c) { |
| bool node1HasRet= findInst(c->edge1->getTargetNode(), Op_Return)!=NULL; |
| bool node2HasRet= findInst(c->edge2->getTargetNode(), Op_Return)!=NULL; |
| return node1HasRet == node2HasRet ? PROB_HEURISTIC_FAIL: (node1HasRet ? 1 - PROB_RET_HEURISTIC: PROB_RET_HEURISTIC); |
| } |
| |
| |
| /** Loop header heuristic (LHH) |
| * Predict a successor that is a loop header or loop pre-header will be taken |
| */ |
| static double loopHeaderHeuristic(const StaticProfilerContext* c) { |
| Node* parentLoopHeader = c->loopTree->getLoopHeader(c->node, true); |
| |
| Node* edge1Loop = findLoopHeaderOnUncondPath(parentLoopHeader, c->loopTree, c->edge1); |
| Node* edge2Loop = findLoopHeaderOnUncondPath(parentLoopHeader, c->loopTree, c->edge2); |
| |
| if ( (edge1Loop!=NULL && edge2Loop!=NULL) || edge2Loop==edge2Loop) { |
| return PROB_HEURISTIC_FAIL; |
| } |
| Node* edge1Target = c->edge1->getTargetNode(); |
| Node* edge2Target = c->edge2->getTargetNode(); |
| if ((edge1Loop != NULL && !c->domTree->dominates(edge1Target, edge1Loop)) |
| || (edge2Loop != NULL && !c->domTree->dominates(edge2Target, edge2Loop))) |
| { |
| return PROB_HEURISTIC_FAIL; |
| } |
| return edge1Loop!=NULL? PROB_LOOP_HEADER_HEURISTIC : 1 - PROB_LOOP_HEADER_HEURISTIC; |
| } |
| |
| |
| /** Opcode heuristic (OH) |
| * Predict that a comparison of an integer for less than zero, |
| * less than or equal to zero or equal to a constant, will fail. |
| */ |
| static double opcodeHeuristic(const StaticProfilerContext* c) { |
| Inst* inst = (Inst*)c->node->getLastInst(); |
| if (!(inst->getOpcode() == Op_Branch && inst->getSrc(0)->getType()->isInteger())) { |
| return PROB_HEURISTIC_FAIL; |
| } |
| |
| assert (inst->getNumSrcOperands() == 2); |
| |
| Opnd* src0 = inst->getSrc(0); |
| Opnd* src1 = inst->getSrc(1); |
| |
| |
| ConstInst::ConstValue v0, v1; |
| bool src0Const = ConstantFolder::isConstant(src0->getInst(), v0); |
| bool src1Const = ConstantFolder::isConstant(src1->getInst(), v1); |
| |
| if (!src0Const && !src1Const) { |
| return PROB_HEURISTIC_FAIL; |
| } |
| |
| Type::Tag tag = src0->getType()->tag; |
| |
| enum CMP_STATUS { CMP_UNDEF, CMP_OK, CMP_FAIL } rc = CMP_UNDEF; |
| |
| if (src0Const && src1Const) { |
| rc = v0.dword1 == v1.dword1 && v0.dword2 == v1.dword2 ? CMP_OK : CMP_FAIL; |
| } else { //!(src0Const && src1Const) |
| ConstInst::ConstValue val = src0Const ? v0: v1; |
| bool constValLEzero = false; |
| switch(tag) { |
| case Type::IntPtr: // ptr-sized integer |
| #ifdef POINTER64 |
| constValLEzero = val.i8 <= 0; |
| #else |
| constValLEzero = val.i4 <= 0; |
| #endif |
| break; |
| case Type::Int8: constValLEzero = ((I_8)val.i4) <= 0; break; |
| case Type::Int16: constValLEzero = ((int16)val.i4) <= 0; break; |
| case Type::Int32: constValLEzero = val.i4 <= 0; break; |
| case Type::Int64: constValLEzero = val.i8 <= 0; break; |
| |
| case Type::UIntPtr: //ConstValue is union |
| case Type::UInt8: |
| case Type::UInt16: |
| case Type::UInt32: |
| case Type::UInt64: constValLEzero = ((uint64)val.i8) == 0; break; |
| default: assert(false); |
| } |
| |
| ComparisonModifier cmpOp = inst->getComparisonModifier(); |
| switch (cmpOp) { |
| case Cmp_EQ: rc = CMP_FAIL; break;//comparison with const fails |
| case Cmp_NE_Un: rc = CMP_OK; break; |
| case Cmp_GT: |
| case Cmp_GT_Un: |
| case Cmp_GTE: |
| case Cmp_GTE_Un: |
| if (constValLEzero) { //negative or zero branch is not taken |
| rc = src0Const ? CMP_FAIL : CMP_OK; |
| } |
| break; |
| case Cmp_Zero: rc = CMP_FAIL; break;//compare with const fails |
| case Cmp_NonZero: rc = CMP_OK; break;//not equal to const -> OK |
| default: break; //to avoid warning that this enum value is not handled |
| } |
| } |
| if (rc == CMP_UNDEF) { |
| return PROB_HEURISTIC_FAIL; |
| } else if (rc == CMP_OK) { |
| return PROB_OPCODE_HEURISTIC; |
| } |
| return 1 - PROB_OPCODE_HEURISTIC; |
| } |
| |
| |
| /** Store heuristic (SH). |
| * Predict a successor that contains a store instruction |
| * and does not post dominate will not be taken |
| */ |
| static double storeHeuristic(const StaticProfilerContext* c) { |
| Node* node1 = c->edge1->getTargetNode(); |
| Node* node2 = c->edge2->getTargetNode(); |
| bool node1Accepted = (findInst(node1, Op_TauStInd)!=NULL||findInst(node1, Op_TauStRef)!=NULL); |
| bool node2Accepted = (findInst(node2, Op_TauStInd)!=NULL||findInst(node2, Op_TauStRef)!=NULL); |
| if (!node1Accepted && !node2Accepted) { |
| return PROB_HEURISTIC_FAIL; |
| } |
| node1Accepted == node1Accepted && !c->postDomTree->dominates(node1, c->node); |
| node2Accepted == node2Accepted && !c->postDomTree->dominates(node2, c->node); |
| |
| if (!node1Accepted && !node2Accepted) { |
| return PROB_HEURISTIC_FAIL; |
| } |
| return node1Accepted ? 1 - PROB_STORE_HEURISTIC: PROB_STORE_HEURISTIC; |
| } |
| /** |
| * Give more prob to fallthru branch |
| */ |
| static double fallThruHeuristic(const StaticProfilerContext * c) { |
| Inst* inst = (Inst*)c->node->getLastInst(); |
| if (inst->getOpcode() != Op_Branch) { |
| return PROB_HEURISTIC_FAIL; |
| } |
| return PROB_FALLTHRU_HEURISTIC; |
| } |
| |
| /** Reference heuristic (RH) |
| * Same as Pointer heuristic (PH) in article |
| * Predict that a comparison of object reference |
| * against null or two references will fail |
| */ |
| static double referenceHeuristic(const StaticProfilerContext *c) { |
| Inst* inst = (Inst*)c->node->getLastInst(); |
| if (inst->getOpcode() != Op_Branch || !inst->getSrc(0)->getType()->isObject()) { |
| return PROB_HEURISTIC_FAIL; |
| } |
| enum CMP_STATUS { CMP_UNDEF, CMP_OK, CMP_FAIL } rc = CMP_UNDEF; |
| ComparisonModifier cmpOp = inst->getComparisonModifier(); |
| switch (cmpOp) { |
| case Cmp_EQ: rc = CMP_FAIL; break; |
| case Cmp_NE_Un: rc = CMP_OK; break; |
| case Cmp_Zero: rc = CMP_FAIL; break; |
| case Cmp_NonZero: rc = CMP_OK; break; |
| default: assert(false); |
| } |
| assert(rc!=CMP_UNDEF); |
| return rc == CMP_OK ? PROB_REFERENCE : 1 - PROB_REFERENCE; |
| } |
| |
| /** De-virtualization guard heuristic (DGH) |
| * Predict that comparison of VTablePtr will succeed |
| */ |
| static double devirtGuardHeuristic(const StaticProfilerContext *c) { |
| Inst* inst = (Inst*)c->node->getLastInst(); |
| if (inst->getOpcode() != Op_Branch || !inst->getSrc(0)->getType()->isVTablePtr()) { |
| return PROB_HEURISTIC_FAIL; |
| } |
| ComparisonModifier cmpOp = inst->getComparisonModifier(); |
| assert(cmpOp == Cmp_EQ || cmpOp == Cmp_NE_Un); |
| return cmpOp == Cmp_EQ ? PROB_DEVIRT_GUARD_HEURISTIC : 1 - PROB_DEVIRT_GUARD_HEURISTIC; |
| } |
| |
| |
| void StaticProfiler::fixEdgeProbs(IRManager& irm) { |
| assert(irm.getFlowGraph().hasEdgeProfile()); |
| |
| double minProb = PROB_ALL_EXCEPTIONS; |
| |
| |
| //fix edge-probs, try to reuse old probs as much as possible.. |
| const Nodes& nodes = irm.getFlowGraph().getNodes(); |
| StaticProfilerContext* c = NULL; |
| for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) { |
| Node* node = *it; |
| double sumProb = 0; |
| U_32 nNotEstimated = 0; |
| const Edges& outEdges = node->getOutEdges(); |
| for(Edges::const_iterator eit = outEdges.begin(), eend = outEdges.end(); eit!=eend; ++eit) { |
| Edge* e = *eit; |
| double prob = e->getEdgeProb(); |
| sumProb+=prob; |
| if (prob <= 0) { |
| nNotEstimated++; |
| } |
| } |
| if (nNotEstimated==0 && ABS(1 - sumProb) <= ACCEPTABLE_DOUBLE_PRECISION_LOSS) { |
| continue; //ok, nothing to fix |
| } |
| if (nNotEstimated == outEdges.size()) { //apply all active heuristics |
| if (c == NULL) { |
| c = new (irm.getMemoryManager()) StaticProfilerContext(irm); |
| } |
| c->node = node; |
| c->edge1 = NULL; |
| c->edge2 = NULL; |
| estimateNode(c); |
| } else { //assign min.possible prob for all not-estimated edges and scale probs to have sum == 1. |
| double scale = 1; |
| if (nNotEstimated == 0) { //do scaling only. |
| scale = 1 / sumProb; |
| } else { //assign a min possible probs for all not estimated edges, calculate scale |
| sumProb = 0; |
| for(Edges::const_iterator eit = outEdges.begin(), eend = outEdges.end(); eit!=eend; ++eit) { |
| Edge* e = *eit; |
| double prob = e->getEdgeProb(); |
| if (prob <= 0) { |
| prob = minProb; |
| e->setEdgeProb(prob); |
| } |
| sumProb+=prob; |
| } |
| scale = 1 / sumProb; |
| } |
| sumProb = 0; |
| for(Edges::const_iterator eit = outEdges.begin(), eend = outEdges.end(); eit!=eend; ++eit) { |
| Edge* e = *eit; |
| double prob = e->getEdgeProb(); |
| prob = prob * scale; |
| assert(prob > 0); |
| e->setEdgeProb(prob); |
| #ifdef _DEBUG |
| sumProb+=prob; |
| #endif |
| } |
| assert(ABS(1-sumProb) < ACCEPTABLE_DOUBLE_PRECISION_LOSS); |
| } |
| } |
| setHeatThreshold(irm); |
| } |
| |
| static void splitString(const char* string, StringList& result, char separator, bool notEmptyTokensOnly) { |
| std::string token; |
| for (const char* suffix = string; *suffix!=0; ++suffix) { |
| char c = *suffix; |
| if (c == separator) { |
| if (token.empty() && notEmptyTokensOnly) { |
| continue; |
| } |
| result.push_back(token); |
| token.clear(); |
| } else { |
| token.push_back(c); |
| } |
| } |
| if (!token.empty()) { //last value |
| result.push_back(token); |
| } |
| } |
| |
| } //namespace |
