File: | llvm/lib/Analysis/ConstraintSystem.cpp |
Warning: | line 88, column 7 Value stored to 'EliminatedInRow' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- ConstraintSytem.cpp - A system of linear constraints. ----*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #include "llvm/Analysis/ConstraintSystem.h" |
10 | #include "llvm/ADT/SmallVector.h" |
11 | #include "llvm/Support/MathExtras.h" |
12 | #include "llvm/ADT/StringExtras.h" |
13 | #include "llvm/Support/Debug.h" |
14 | |
15 | #include <algorithm> |
16 | #include <string> |
17 | |
18 | using namespace llvm; |
19 | |
20 | #define DEBUG_TYPE"constraint-system" "constraint-system" |
21 | |
22 | bool ConstraintSystem::eliminateUsingFM() { |
23 | // Implementation of Fourier–Motzkin elimination, with some tricks from the |
24 | // paper Pugh, William. "The Omega test: a fast and practical integer |
25 | // programming algorithm for dependence |
26 | // analysis." |
27 | // Supercomputing'91: Proceedings of the 1991 ACM/ |
28 | // IEEE conference on Supercomputing. IEEE, 1991. |
29 | assert(!Constraints.empty() &&((!Constraints.empty() && "should only be called for non-empty constraint systems" ) ? static_cast<void> (0) : __assert_fail ("!Constraints.empty() && \"should only be called for non-empty constraint systems\"" , "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/Analysis/ConstraintSystem.cpp" , 30, __PRETTY_FUNCTION__)) |
30 | "should only be called for non-empty constraint systems")((!Constraints.empty() && "should only be called for non-empty constraint systems" ) ? static_cast<void> (0) : __assert_fail ("!Constraints.empty() && \"should only be called for non-empty constraint systems\"" , "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/Analysis/ConstraintSystem.cpp" , 30, __PRETTY_FUNCTION__)); |
31 | unsigned NumVariables = Constraints[0].size(); |
32 | SmallVector<SmallVector<int64_t, 8>, 4> NewSystem; |
33 | |
34 | unsigned NumConstraints = Constraints.size(); |
35 | uint32_t NewGCD = 1; |
36 | // FIXME do not use copy |
37 | for (unsigned R1 = 0; R1 < NumConstraints; R1++) { |
38 | if (Constraints[R1][1] == 0) { |
39 | SmallVector<int64_t, 8> NR; |
40 | NR.push_back(Constraints[R1][0]); |
41 | for (unsigned i = 2; i < NumVariables; i++) { |
42 | NR.push_back(Constraints[R1][i]); |
43 | } |
44 | NewSystem.push_back(std::move(NR)); |
45 | continue; |
46 | } |
47 | |
48 | // FIXME do not use copy |
49 | bool EliminatedInRow = false; |
50 | for (unsigned R2 = R1 + 1; R2 < NumConstraints; R2++) { |
51 | if (R1 == R2) |
52 | continue; |
53 | |
54 | // FIXME: can we do better than just dropping things here? |
55 | if (Constraints[R2][1] == 0) |
56 | continue; |
57 | |
58 | if ((Constraints[R1][1] < 0 && Constraints[R2][1] < 0) || |
59 | (Constraints[R1][1] > 0 && Constraints[R2][1] > 0)) |
60 | continue; |
61 | |
62 | unsigned LowerR = R1; |
63 | unsigned UpperR = R2; |
64 | if (Constraints[UpperR][1] < 0) |
65 | std::swap(LowerR, UpperR); |
66 | |
67 | SmallVector<int64_t, 8> NR; |
68 | for (unsigned I = 0; I < NumVariables; I++) { |
69 | if (I == 1) |
70 | continue; |
71 | |
72 | int64_t M1, M2, N; |
73 | if (MulOverflow(Constraints[UpperR][I], |
74 | ((-1) * Constraints[LowerR][1] / GCD), M1)) |
75 | return false; |
76 | if (MulOverflow(Constraints[LowerR][I], |
77 | (Constraints[UpperR][1] / GCD), M2)) |
78 | return false; |
79 | if (AddOverflow(M1, M2, N)) |
80 | return false; |
81 | NR.push_back(N); |
82 | |
83 | NewGCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)NR.back()}, |
84 | {32, NewGCD}) |
85 | .getZExtValue(); |
86 | } |
87 | NewSystem.push_back(std::move(NR)); |
88 | EliminatedInRow = true; |
Value stored to 'EliminatedInRow' is never read | |
89 | } |
90 | } |
91 | Constraints = std::move(NewSystem); |
92 | GCD = NewGCD; |
93 | |
94 | return true; |
95 | } |
96 | |
97 | bool ConstraintSystem::mayHaveSolutionImpl() { |
98 | while (!Constraints.empty() && Constraints[0].size() > 1) { |
99 | if (!eliminateUsingFM()) |
100 | return true; |
101 | } |
102 | |
103 | if (Constraints.empty() || Constraints[0].size() > 1) |
104 | return true; |
105 | |
106 | return all_of(Constraints, [](auto &R) { return R[0] >= 0; }); |
107 | } |
108 | |
109 | void ConstraintSystem::dump(ArrayRef<std::string> Names) const { |
110 | if (Constraints.empty()) |
111 | return; |
112 | |
113 | for (auto &Row : Constraints) { |
114 | SmallVector<std::string, 16> Parts; |
115 | for (unsigned I = 1, S = Row.size(); I < S; ++I) { |
116 | if (Row[I] == 0) |
117 | continue; |
118 | std::string Coefficient = ""; |
119 | if (Row[I] != 1) |
120 | Coefficient = std::to_string(Row[I]) + " * "; |
121 | Parts.push_back(Coefficient + Names[I - 1]); |
122 | } |
123 | assert(!Parts.empty() && "need to have at least some parts")((!Parts.empty() && "need to have at least some parts" ) ? static_cast<void> (0) : __assert_fail ("!Parts.empty() && \"need to have at least some parts\"" , "/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/Analysis/ConstraintSystem.cpp" , 123, __PRETTY_FUNCTION__)); |
124 | LLVM_DEBUG(dbgs() << join(Parts, std::string(" + "))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("constraint-system")) { dbgs() << join(Parts, std::string (" + ")) << " <= " << std::to_string(Row[0]) << "\n"; } } while (false) |
125 | << " <= " << std::to_string(Row[0]) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("constraint-system")) { dbgs() << join(Parts, std::string (" + ")) << " <= " << std::to_string(Row[0]) << "\n"; } } while (false); |
126 | } |
127 | } |
128 | |
129 | void ConstraintSystem::dump() const { |
130 | SmallVector<std::string, 16> Names; |
131 | for (unsigned i = 1; i < Constraints.back().size(); ++i) |
132 | Names.push_back("x" + std::to_string(i)); |
133 | LLVM_DEBUG(dbgs() << "---\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("constraint-system")) { dbgs() << "---\n"; } } while ( false); |
134 | dump(Names); |
135 | } |
136 | |
137 | bool ConstraintSystem::mayHaveSolution() { |
138 | dump(); |
139 | bool HasSolution = mayHaveSolutionImpl(); |
140 | LLVM_DEBUG(dbgs() << (HasSolution ? "sat" : "unsat") << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("constraint-system")) { dbgs() << (HasSolution ? "sat" : "unsat") << "\n"; } } while (false); |
141 | return HasSolution; |
142 | } |
143 | |
144 | bool ConstraintSystem::isConditionImplied(SmallVector<int64_t, 8> R) { |
145 | // If there is no solution with the negation of R added to the system, the |
146 | // condition must hold based on the existing constraints. |
147 | R = ConstraintSystem::negate(R); |
148 | |
149 | auto NewSystem = *this; |
150 | NewSystem.addVariableRow(R); |
151 | return !NewSystem.mayHaveSolution(); |
152 | } |