LLVM: include/llvm/Transforms/Utils/LongestCommonSequence.h Source File (original) (raw)

39 FunctionMatchesProfile,

41 int32_t Size1 = AnchorList1.size(), Size2 = AnchorList2.size(),

42 MaxDepth = Size1 + Size2;

43 auto Index = [&](int32_t I) { return I + MaxDepth; };

44

45 if (MaxDepth == 0)

46 return;

47

48

51 int32_t X = Size1, Y = Size2;

54 int32_t K = X - Y;

55 int32_t PrevK = K;

56 if (K == -Depth || (K != Depth && P[Index(K - 1)] < P[Index(K + 1)]))

57 PrevK = K + 1;

58 else

59 PrevK = K - 1;

60

61 int32_t PrevX = P[Index(PrevK)];

62 int32_t PrevY = PrevX - PrevK;

63 while (X > PrevX && Y > PrevY) {

64 X--;

65 Y--;

66 InsertMatching(AnchorList1[X].first, AnchorList2[Y].first);

67 }

68

70 break;

71

72 if (Y == PrevY)

73 X--;

74 else if (X == PrevX)

75 Y--;

76 X = PrevX;

77 Y = PrevY;

78 }

79 };

80

81

82

83

84 std::vector<int32_t> V(2 * MaxDepth + 1, -1);

85 V[Index(1)] = 0;

86

87 std::vector<std::vector<int32_t>> Trace;

89 Trace.push_back(V);

90 for (int32_t K = -Depth; K <= Depth; K += 2) {

91 int32_t X = 0, Y = 0;

92 if (K == -Depth || (K != Depth && V[Index(K - 1)] < V[Index(K + 1)]))

93 X = V[Index(K + 1)];

94 else

95 X = V[Index(K - 1)] + 1;

96 Y = X - K;

97 while (

98 X < Size1 && Y < Size2 &&

99 FunctionMatchesProfile(AnchorList1[X].second, AnchorList2[Y].second))

100 X++, Y++;

101

102 V[Index(K)] = X;

103

104 if (X >= Size1 && Y >= Size2) {

105

106 Backtrack(Trace, AnchorList1, AnchorList2);

107 return;

108 }

109 }

110 }

111

112}

void longestCommonSequence(AnchorList AnchorList1, AnchorList AnchorList2, llvm::function_ref< bool(const Function &, const Function &)> FunctionMatchesProfile, llvm::function_ref< void(Loc, Loc)> InsertMatching)

Definition LongestCommonSequence.h:36