Bug Summary

File:build/source/bolt/lib/Core/ParallelUtilities.cpp
Warning:line 201, column 43
Division by zero

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name ParallelUtilities.cpp -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 -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D _LIBCPP_ENABLE_ASSERTIONS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/bolt/lib/Core -I /build/source/bolt/lib/Core -I include -I /build/source/llvm/include -I /build/source/bolt/include -I tools/bolt/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-17/lib/clang/17/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1683717183 -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-05-10-133810-16478-1 -x c++ /build/source/bolt/lib/Core/ParallelUtilities.cpp
1//===- bolt/Core/ParallelUtilities.cpp - Parallel utilities ---------------===//
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// Implementation of the class that manages parallel work on BinaryFunctions.
10//
11//===----------------------------------------------------------------------===//
12
13#include "bolt/Core/ParallelUtilities.h"
14#include "bolt/Core/BinaryContext.h"
15#include "bolt/Core/BinaryFunction.h"
16#include "llvm/Support/RWMutex.h"
17#include "llvm/Support/ThreadPool.h"
18#include "llvm/Support/Timer.h"
19#include <mutex>
20
21#define DEBUG_TYPE"par-utils" "par-utils"
22
23namespace opts {
24extern cl::OptionCategory BoltCategory;
25
26cl::opt<unsigned>
27ThreadCount("thread-count",
28 cl::desc("number of threads"),
29 cl::init(hardware_concurrency().compute_thread_count()),
30 cl::cat(BoltCategory));
31
32cl::opt<bool>
33NoThreads("no-threads",
34 cl::desc("disable multithreading"),
35 cl::init(false),
36 cl::cat(BoltCategory));
37
38cl::opt<unsigned>
39TaskCount("tasks-per-thread",
40 cl::desc("number of tasks to be created per thread"),
41 cl::init(20),
42 cl::cat(BoltCategory));
43
44} // namespace opts
45
46namespace llvm {
47namespace bolt {
48namespace ParallelUtilities {
49
50namespace {
51/// A single thread pool that is used to run parallel tasks
52std::unique_ptr<ThreadPool> ThreadPoolPtr;
53
54unsigned computeCostFor(const BinaryFunction &BF,
55 const PredicateTy &SkipPredicate,
56 const SchedulingPolicy &SchedPolicy) {
57 if (SchedPolicy == SchedulingPolicy::SP_TRIVIAL)
58 return 1;
59
60 if (SkipPredicate && SkipPredicate(BF))
61 return 0;
62
63 switch (SchedPolicy) {
64 case SchedulingPolicy::SP_CONSTANT:
65 return 1;
66 case SchedulingPolicy::SP_INST_LINEAR:
67 return BF.getSize();
68 case SchedulingPolicy::SP_INST_QUADRATIC:
69 return BF.getSize() * BF.getSize();
70 case SchedulingPolicy::SP_BB_LINEAR:
71 return BF.size();
72 case SchedulingPolicy::SP_BB_QUADRATIC:
73 return BF.size() * BF.size();
74 default:
75 llvm_unreachable("unsupported scheduling policy")::llvm::llvm_unreachable_internal("unsupported scheduling policy"
, "bolt/lib/Core/ParallelUtilities.cpp", 75);
76 }
77}
78
79inline unsigned estimateTotalCost(const BinaryContext &BC,
80 const PredicateTy &SkipPredicate,
81 SchedulingPolicy &SchedPolicy) {
82 if (SchedPolicy == SchedulingPolicy::SP_TRIVIAL)
83 return BC.getBinaryFunctions().size();
84
85 unsigned TotalCost = 0;
86 for (auto &BFI : BC.getBinaryFunctions()) {
87 const BinaryFunction &BF = BFI.second;
88 TotalCost += computeCostFor(BF, SkipPredicate, SchedPolicy);
89 }
90
91 // Switch to trivial scheduling if total estimated work is zero
92 if (TotalCost == 0) {
93 outs() << "BOLT-WARNING: Running parallel work of 0 estimated cost, will "
94 "switch to trivial scheduling.\n";
95
96 SchedPolicy = SP_TRIVIAL;
97 TotalCost = BC.getBinaryFunctions().size();
98 }
99 return TotalCost;
100}
101
102} // namespace
103
104ThreadPool &getThreadPool() {
105 if (ThreadPoolPtr.get())
106 return *ThreadPoolPtr;
107
108 ThreadPoolPtr = std::make_unique<ThreadPool>(
109 llvm::hardware_concurrency(opts::ThreadCount));
110 return *ThreadPoolPtr;
111}
112
113void runOnEachFunction(BinaryContext &BC, SchedulingPolicy SchedPolicy,
114 WorkFuncTy WorkFunction, PredicateTy SkipPredicate,
115 std::string LogName, bool ForceSequential,
116 unsigned TasksPerThread) {
117 if (BC.getBinaryFunctions().size() == 0)
118 return;
119
120 auto runBlock = [&](std::map<uint64_t, BinaryFunction>::iterator BlockBegin,
121 std::map<uint64_t, BinaryFunction>::iterator BlockEnd) {
122 Timer T(LogName, LogName);
123 LLVM_DEBUG(T.startTimer())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("par-utils")) { T.startTimer(); } } while (false);
124
125 for (auto It = BlockBegin; It != BlockEnd; ++It) {
126 BinaryFunction &BF = It->second;
127 if (SkipPredicate && SkipPredicate(BF))
128 continue;
129
130 WorkFunction(BF);
131 }
132 LLVM_DEBUG(T.stopTimer())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("par-utils")) { T.stopTimer(); } } while (false);
133 };
134
135 if (opts::NoThreads || ForceSequential) {
136 runBlock(BC.getBinaryFunctions().begin(), BC.getBinaryFunctions().end());
137 return;
138 }
139
140 // Estimate the overall runtime cost using the scheduling policy
141 const unsigned TotalCost = estimateTotalCost(BC, SkipPredicate, SchedPolicy);
142 const unsigned BlocksCount = TasksPerThread * opts::ThreadCount;
143 const unsigned BlockCost =
144 TotalCost > BlocksCount ? TotalCost / BlocksCount : 1;
145
146 // Divide work into blocks of equal cost
147 ThreadPool &Pool = getThreadPool();
148 auto BlockBegin = BC.getBinaryFunctions().begin();
149 unsigned CurrentCost = 0;
150
151 for (auto It = BC.getBinaryFunctions().begin();
152 It != BC.getBinaryFunctions().end(); ++It) {
153 BinaryFunction &BF = It->second;
154 CurrentCost += computeCostFor(BF, SkipPredicate, SchedPolicy);
155
156 if (CurrentCost >= BlockCost) {
157 Pool.async(runBlock, BlockBegin, std::next(It));
158 BlockBegin = std::next(It);
159 CurrentCost = 0;
160 }
161 }
162 Pool.async(runBlock, BlockBegin, BC.getBinaryFunctions().end());
163 Pool.wait();
164}
165
166void runOnEachFunctionWithUniqueAllocId(
167 BinaryContext &BC, SchedulingPolicy SchedPolicy,
168 WorkFuncWithAllocTy WorkFunction, PredicateTy SkipPredicate,
169 std::string LogName, bool ForceSequential, unsigned TasksPerThread) {
170 if (BC.getBinaryFunctions().size() == 0)
1
Assuming the condition is false
→
2
←
Taking false branch
→
171 return;
172
173 llvm::sys::RWMutex MainLock;
174 auto runBlock = [&](std::map<uint64_t, BinaryFunction>::iterator BlockBegin,
175 std::map<uint64_t, BinaryFunction>::iterator BlockEnd,
176 MCPlusBuilder::AllocatorIdTy AllocId) {
177 Timer T(LogName, LogName);
178 LLVM_DEBUG(T.startTimer())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("par-utils")) { T.startTimer(); } } while (false);
179 std::shared_lock<llvm::sys::RWMutex> Lock(MainLock);
180 for (auto It = BlockBegin; It != BlockEnd; ++It) {
181 BinaryFunction &BF = It->second;
182 if (SkipPredicate && SkipPredicate(BF))
183 continue;
184
185 WorkFunction(BF, AllocId);
186 }
187 LLVM_DEBUG(T.stopTimer())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("par-utils")) { T.stopTimer(); } } while (false);
188 };
189
190 if (opts::NoThreads || ForceSequential) {
3
←
Assuming the condition is false
→
4
←
Assuming 'ForceSequential' is false
→
5
←
Taking false branch
→
191 runBlock(BC.getBinaryFunctions().begin(), BC.getBinaryFunctions().end(), 0);
192 return;
193 }
194 // This lock is used to postpone task execution
195 std::unique_lock<llvm::sys::RWMutex> Lock(MainLock);
196
197 // Estimate the overall runtime cost using the scheduling policy
198 const unsigned TotalCost = estimateTotalCost(BC, SkipPredicate, SchedPolicy);
199 const unsigned BlocksCount = TasksPerThread * opts::ThreadCount;
6
←
'BlocksCount' initialized here
→
200 const unsigned BlockCost =
201 TotalCost > BlocksCount ? TotalCost / BlocksCount : 1;
7
←
Assuming 'TotalCost' is > 'BlocksCount'
→
8
←
'?' condition is true
→
9
←
Division by zero
202
203 // Divide work into blocks of equal cost
204 ThreadPool &Pool = getThreadPool();
205 auto BlockBegin = BC.getBinaryFunctions().begin();
206 unsigned CurrentCost = 0;
207 unsigned AllocId = 1;
208 for (auto It = BC.getBinaryFunctions().begin();
209 It != BC.getBinaryFunctions().end(); ++It) {
210 BinaryFunction &BF = It->second;
211 CurrentCost += computeCostFor(BF, SkipPredicate, SchedPolicy);
212
213 if (CurrentCost >= BlockCost) {
214 if (!BC.MIB->checkAllocatorExists(AllocId)) {
215 MCPlusBuilder::AllocatorIdTy Id =
216 BC.MIB->initializeNewAnnotationAllocator();
217 (void)Id;
218 assert(AllocId == Id && "unexpected allocator id created")(static_cast <bool> (AllocId == Id && "unexpected allocator id created"
) ? void (0) : __assert_fail ("AllocId == Id && \"unexpected allocator id created\""
, "bolt/lib/Core/ParallelUtilities.cpp", 218, __extension__ __PRETTY_FUNCTION__
));
219 }
220 Pool.async(runBlock, BlockBegin, std::next(It), AllocId);
221 AllocId++;
222 BlockBegin = std::next(It);
223 CurrentCost = 0;
224 }
225 }
226
227 if (!BC.MIB->checkAllocatorExists(AllocId)) {
228 MCPlusBuilder::AllocatorIdTy Id =
229 BC.MIB->initializeNewAnnotationAllocator();
230 (void)Id;
231 assert(AllocId == Id && "unexpected allocator id created")(static_cast <bool> (AllocId == Id && "unexpected allocator id created"
) ? void (0) : __assert_fail ("AllocId == Id && \"unexpected allocator id created\""
, "bolt/lib/Core/ParallelUtilities.cpp", 231, __extension__ __PRETTY_FUNCTION__
));
232 }
233
234 Pool.async(runBlock, BlockBegin, BC.getBinaryFunctions().end(), AllocId);
235 Lock.unlock();
236 Pool.wait();
237}
238
239} // namespace ParallelUtilities
240} // namespace bolt
241} // namespace llvm