Bug Summary

File:llvm/lib/Analysis/ConstraintSystem.cpp
Warning:line 88, column 7
Value stored to 'EliminatedInRow' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ConstraintSystem.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/build-llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-12/lib/clang/12.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/build-llvm/lib/Analysis -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-09-17-195756-12974-1 -x c++ /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/Analysis/ConstraintSystem.cpp
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
18using namespace llvm;
19
20#define DEBUG_TYPE"constraint-system" "constraint-system"
21
22bool 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
97bool 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
109void 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
129void 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
137bool 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
144bool 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}