BranchHinting.cpp (2522B)
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- 2 * vim: set ts=8 sts=2 et sw=2 tw=80: 3 * This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #include "jit/BranchHinting.h" 8 9 #include "jit/IonAnalysis.h" 10 #include "jit/JitSpewer.h" 11 #include "jit/MIRGenerator.h" 12 #include "jit/MIRGraph.h" 13 14 using namespace js; 15 using namespace js::jit; 16 17 // Implementation of the branch hinting proposal 18 // Some control instructions (if and br_if) can have a hint of the form 19 // likely or unlikely. That means a specific branch will be likely/unlikely 20 // to be executed at runtime. 21 22 // This pass will propagate the branch hints to successor blocks in the CFG. 23 // Currently, we use the branch hinting information for the following: 24 // - Unlikely blocks are moved out of line, this is done at the LIR level. 25 // - TODO: use branch hinting to optimize likely blocks. 26 bool jit::BranchHinting(const MIRGenerator* mir, MIRGraph& graph) { 27 JitSpew(JitSpew_BranchHint, "Beginning BranchHinting pass"); 28 29 /* This pass propagates branch hints across the control flow graph 30 using dominator information. Branch hints are read at compile-time for 31 specific basic blocks. This pass propagates this property to successor 32 blocks in a conservative way. The algorithm works as follows: 33 - The CFG is traversed in reverse-post-order (RPO). Dominator parents are 34 visited before the blocks they dominate. 35 36 - For each basic block, if we have a hint, it is propagated to the 37 blocks it immediately dominates (its children in the dominator tree). 38 39 - The pass will then continue to work its way through the CFG. 40 41 Because we only propagate along dominator-tree edges (parent -> child), 42 each block receives information from exactly one source. This avoids 43 conflicts that would otherwise arise at CFG join points. 44 */ 45 for (ReversePostorderIterator block(graph.rpoBegin()); 46 block != graph.rpoEnd(); block++) { 47 if (block->isUnknownFrequency()) { 48 continue; 49 } 50 51 for (MBasicBlock** it = block->immediatelyDominatedBlocksBegin(); 52 it != block->immediatelyDominatedBlocksEnd(); it++) { 53 // Don't propagate the information if this successor block has already 54 // some branch hints. 55 if ((*it)->isUnknownFrequency()) { 56 (*it)->setFrequency(block->getFrequency()); 57 } 58 } 59 } 60 61 return true; 62 }