Generate branch weight metadata for all branches in F.
Declared in <llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h>
bool
computeAndPropagateWeights(
FunctionT& F,
DenseSet<GlobalValue::GUID> const& InlinedGUIDs);
Branch weights are computed out of instruction samples using a propagation heuristic. Propagation proceeds in 3 phases:
1- Assignment of block weights. All the basic blocks in the function are initial assigned the same weight as their most frequently executed instruction.
2- Creation of equivalence classes. Since samples may be missing from blocks, we can fill in the gaps by setting the weights of all the blocks in the same equivalence class to the same weight. To compute the concept of equivalence, we use dominance and loop information. Two blocks B1 and B2 are in the same equivalence class if B1 dominates B2, B2 post-dominates B1 and both are in the same loop.
3- Propagation of block weights into edges. This uses a simple propagation heuristic. The following rules are applied to every block BB in the CFG:
If BB has a single predecessor/successor, then the weight of that edge is the weight of the block.
If all the edges are known except one, and the weight of the block is already known, the weight of the unknown edge will be the weight of the block minus the sum of all the known edges. If the sum of all the known edges is larger than BB's weight, we set the unknown edge weight to zero.
If there is a self-referential edge, and the weight of the block is known, the weight for that edge is set to the weight of the block minus the weight of the other incoming edges to that block (if known).
Since this propagation is not guaranteed to finalize for every CFG, we only allow it to proceed for a limited number of iterations (controlled by -sample-profile-max-propagate-iterations).
FIXME: Try to replace this propagation heuristic with a scheme that is guaranteed to finalize. A work-list approach similar to the standard value propagation algorithm used by SSA-CCP might work here.
true if F was modified. Returns false, otherwise.
| Name | Description |
|---|---|
| F | The function to query. |
| InlinedGUIDs | GUIDs of functions inlined in the profiled binary. |