Compute the longest common sequence of two anchor lists using Myers' diff.
Declared in <llvm/Transforms/Utils/LongestCommonSequence.h>
template<
typename Loc,
typename Function,
typename AnchorList = ArrayRef<std::pair<Loc, Function>>>
void
longestCommonSequence(
AnchorList AnchorList1,
AnchorList AnchorList2,
llvm::function_ref<bool(Function const&, Function const&)> FunctionMatchesProfile,
llvm::function_ref<void(Loc, Loc)> InsertMatching);This function implements the Myers diff algorithm used for stale profile matching. The algorithm provides a simple and efficient way to find the Longest Common Subsequence(LCS) or the Shortest Edit Script(SES) of two sequences. For more details, refer to the paper 'An O(ND) Difference Algorithm and Its Variations' by Eugene W. Myers. In the scenario of profile fuzzy matching, the two sequences are the IR callsite anchors and profile callsite anchors. The subsequence equivalent parts from the resulting SES are used to remap the IR locations to the profile locations. As the number of function callsite is usually not big, we currently just implements the basic greedy version(page 6 of the paper).
| Name | Description |
|---|---|
| Loc | Location type of each anchor. |
| Function | Function type compared when matching anchors. |
| AnchorList | Sequence type holding (Loc, Function) pairs. |
| Name | Description |
|---|---|
| AnchorList1 | First sequence of anchors. |
| AnchorList2 | Second sequence of anchors. |
| FunctionMatchesProfile | Predicate that returns true when two functions should be considered a match. |
| InsertMatching | Callback invoked for each matched pair of locations. |