Transforms/Utils/LongestCommonSequence.h

0001 //===- LongestCommonSequence.h - Compute LCS --------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file implements longestCommonSequence, useful for finding matches
0010 // between two sequences, such as lists of profiling points.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_TRANSFORMS_UTILS_LONGESTCOMMONSEQEUNCE_H
0015 #define LLVM_TRANSFORMS_UTILS_LONGESTCOMMONSEQEUNCE_H
0016
0017 #include "llvm/ADT/ArrayRef.h"
0018
0019 #include <cstdint>
0020 #include <vector>
0021
0022 namespace llvm {
0023
0024 // This function implements the Myers diff algorithm used for stale profile
0025 // matching. The algorithm provides a simple and efficient way to find the
0026 // Longest Common Subsequence(LCS) or the Shortest Edit Script(SES) of two
0027 // sequences. For more details, refer to the paper 'An O(ND) Difference
0028 // Algorithm and Its Variations' by Eugene W. Myers.
0029 // In the scenario of profile fuzzy matching, the two sequences are the IR
0030 // callsite anchors and profile callsite anchors. The subsequence equivalent
0031 // parts from the resulting SES are used to remap the IR locations to the
0032 // profile locations. As the number of function callsite is usually not big,
0033 // we currently just implements the basic greedy version(page 6 of the paper).
0034 template <typename Loc, typename Function,
0035           typename AnchorList = ArrayRef<std::pair<Loc, Function>>>
0036 void longestCommonSequence(
0037     AnchorList AnchorList1, AnchorList AnchorList2,
0038     llvm::function_ref<bool(const Function &, const Function &)>
0039         FunctionMatchesProfile,
0040     llvm::function_ref<void(Loc, Loc)> InsertMatching) {
0041   int32_t Size1 = AnchorList1.size(), Size2 = AnchorList2.size(),
0042           MaxDepth = Size1 + Size2;
0043   auto Index = [&](int32_t I) { return I + MaxDepth; };
0044
0045   if (MaxDepth == 0)
0046     return;
0047
0048   // Backtrack the SES result.
0049   auto Backtrack = [&](ArrayRef<std::vector<int32_t>> Trace,
0050                        AnchorList AnchorList1, AnchorList AnchorList2) {
0051     int32_t X = Size1, Y = Size2;
0052     for (int32_t Depth = Trace.size() - 1; X > 0 || Y > 0; Depth--) {
0053       const auto &P = Trace[Depth];
0054       int32_t K = X - Y;
0055       int32_t PrevK = K;
0056       if (K == -Depth || (K != Depth && P[Index(K - 1)] < P[Index(K + 1)]))
0057         PrevK = K + 1;
0058       else
0059         PrevK = K - 1;
0060
0061       int32_t PrevX = P[Index(PrevK)];
0062       int32_t PrevY = PrevX - PrevK;
0063       while (X > PrevX && Y > PrevY) {
0064         X--;
0065         Y--;
0066         InsertMatching(AnchorList1[X].first, AnchorList2[Y].first);
0067       }
0068
0069       if (Depth == 0)
0070         break;
0071
0072       if (Y == PrevY)
0073         X--;
0074       else if (X == PrevX)
0075         Y--;
0076       X = PrevX;
0077       Y = PrevY;
0078     }
0079   };
0080
0081   // The greedy LCS/SES algorithm.
0082
0083   // An array contains the endpoints of the furthest reaching D-paths.
0084   std::vector<int32_t> V(2 * MaxDepth + 1, -1);
0085   V[Index(1)] = 0;
0086   // Trace is used to backtrack the SES result.
0087   std::vector<std::vector<int32_t>> Trace;
0088   for (int32_t Depth = 0; Depth <= MaxDepth; Depth++) {
0089     Trace.push_back(V);
0090     for (int32_t K = -Depth; K <= Depth; K += 2) {
0091       int32_t X = 0, Y = 0;
0092       if (K == -Depth || (K != Depth && V[Index(K - 1)] < V[Index(K + 1)]))
0093         X = V[Index(K + 1)];
0094       else
0095         X = V[Index(K - 1)] + 1;
0096       Y = X - K;
0097       while (
0098           X < Size1 && Y < Size2 &&
0099           FunctionMatchesProfile(AnchorList1[X].second, AnchorList2[Y].second))
0100         X++, Y++;
0101
0102       V[Index(K)] = X;
0103
0104       if (X >= Size1 && Y >= Size2) {
0105         // Length of an SES is D.
0106         Backtrack(Trace, AnchorList1, AnchorList2);
0107         return;
0108       }
0109     }
0110   }
0111   // Length of an SES is greater than MaxDepth.
0112 }
0113
0114 } // end namespace llvm
0115
0116 #endif // LLVM_TRANSFORMS_UTILS_LONGESTCOMMONSEQEUNCE_H