Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
#include "jit/BranchHinting.h"
#include "jit/IonAnalysis.h"
#include "jit/JitSpewer.h"
#include "jit/MIRGenerator.h"
#include "jit/MIRGraph.h"
using namespace js;
using namespace js::jit;
// Implementation of the branch hinting proposal
// Some control instructions (if and br_if) can have a hint of the form
// likely or unlikely. That means a specific branch will be likely/unlikely
// to be executed at runtime.
// This pass will propagate the branch hints to successor blocks in the CFG.
// Currently, we use the branch hinting information for the following:
// - Unlikely blocks are moved out of line, this is done at the LIR level.
// - TODO: use branch hinting to optimize likely blocks.
bool jit::BranchHinting(const MIRGenerator* mir, MIRGraph& graph) {
JitSpew(JitSpew_BranchHint, "Beginning BranchHinting pass");
/* This pass propagates branch hints across the control flow graph
using dominator information. Branch hints are read at compile-time for
specific basic blocks. This pass propagates this property to successor
blocks in a conservative way. The algorithm works as follows:
- The CFG is traversed in reverse-post-order (RPO). Dominator parents are
visited before the blocks they dominate.
- For each basic block, if we have a hint, it is propagated to the
blocks it immediately dominates (its children in the dominator tree).
- The pass will then continue to work its way through the CFG.
Because we only propagate along dominator-tree edges (parent -> child),
each block receives information from exactly one source. This avoids
conflicts that would otherwise arise at CFG join points.
*/
for (ReversePostorderIterator block(graph.rpoBegin());
block != graph.rpoEnd(); block++) {
if (block->isUnknownFrequency()) {
continue;
}
for (MBasicBlock** it = block->immediatelyDominatedBlocksBegin();
it != block->immediatelyDominatedBlocksEnd(); it++) {
// Don't propagate the information if this successor block has already
// some branch hints.
if ((*it)->isUnknownFrequency()) {
(*it)->setFrequency(block->getFrequency());
}
}
}
return true;
}