Bug Summary

File:llvm/lib/Target/AMDGPU/SIModeRegister.cpp
Warning:line 197, column 55
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'int'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name SIModeRegister.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 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-11/lib/clang/11.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/Target/AMDGPU -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Target/AMDGPU -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/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-11/lib/clang/11.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-11~++20200309111110+2c36c23f347/build-llvm/lib/Target/AMDGPU -fdebug-prefix-map=/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347=. -ferror-limit 19 -fmessage-length 0 -fvisibility hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-03-09-184146-41876-1 -x c++ /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Target/AMDGPU/SIModeRegister.cpp

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/Target/AMDGPU/SIModeRegister.cpp

1//===-- SIModeRegister.cpp - Mode Register --------------------------------===//
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/// \file
9/// This pass inserts changes to the Mode register settings as required.
10/// Note that currently it only deals with the Double Precision Floating Point
11/// rounding mode setting, but is intended to be generic enough to be easily
12/// expanded.
13///
14//===----------------------------------------------------------------------===//
15//
16#include "AMDGPU.h"
17#include "AMDGPUInstrInfo.h"
18#include "AMDGPUSubtarget.h"
19#include "SIInstrInfo.h"
20#include "SIMachineFunctionInfo.h"
21#include "llvm/ADT/Statistic.h"
22#include "llvm/CodeGen/MachineFunctionPass.h"
23#include "llvm/CodeGen/MachineInstrBuilder.h"
24#include "llvm/CodeGen/MachineRegisterInfo.h"
25#include "llvm/IR/Constants.h"
26#include "llvm/IR/Function.h"
27#include "llvm/IR/LLVMContext.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/raw_ostream.h"
30#include "llvm/Target/TargetMachine.h"
31#include <queue>
32
33#define DEBUG_TYPE"si-mode-register" "si-mode-register"
34
35STATISTIC(NumSetregInserted, "Number of setreg of mode register inserted.")static llvm::Statistic NumSetregInserted = {"si-mode-register"
, "NumSetregInserted", "Number of setreg of mode register inserted."
}
;
36
37using namespace llvm;
38
39struct Status {
40 // Mask is a bitmask where a '1' indicates the corresponding Mode bit has a
41 // known value
42 unsigned Mask;
43 unsigned Mode;
44
45 Status() : Mask(0), Mode(0){};
46
47 Status(unsigned NewMask, unsigned NewMode) : Mask(NewMask), Mode(NewMode) {
48 Mode &= Mask;
49 };
50
51 // merge two status values such that only values that don't conflict are
52 // preserved
53 Status merge(const Status &S) const {
54 return Status((Mask | S.Mask), ((Mode & ~S.Mask) | (S.Mode & S.Mask)));
55 }
56
57 // merge an unknown value by using the unknown value's mask to remove bits
58 // from the result
59 Status mergeUnknown(unsigned newMask) {
60 return Status(Mask & ~newMask, Mode & ~newMask);
61 }
62
63 // intersect two Status values to produce a mode and mask that is a subset
64 // of both values
65 Status intersect(const Status &S) const {
66 unsigned NewMask = (Mask & S.Mask) & (Mode ^ ~S.Mode);
67 unsigned NewMode = (Mode & NewMask);
68 return Status(NewMask, NewMode);
69 }
70
71 // produce the delta required to change the Mode to the required Mode
72 Status delta(const Status &S) const {
73 return Status((S.Mask & (Mode ^ S.Mode)) | (~Mask & S.Mask), S.Mode);
74 }
75
76 bool operator==(const Status &S) const {
77 return (Mask == S.Mask) && (Mode == S.Mode);
78 }
79
80 bool operator!=(const Status &S) const { return !(*this == S); }
81
82 bool isCompatible(Status &S) {
83 return ((Mask & S.Mask) == S.Mask) && ((Mode & S.Mask) == S.Mode);
84 }
85
86 bool isCombinable(Status &S) {
87 return !(Mask & S.Mask) || isCompatible(S);
88 }
89};
90
91class BlockData {
92public:
93 // The Status that represents the mode register settings required by the
94 // FirstInsertionPoint (if any) in this block. Calculated in Phase 1.
95 Status Require;
96
97 // The Status that represents the net changes to the Mode register made by
98 // this block, Calculated in Phase 1.
99 Status Change;
100
101 // The Status that represents the mode register settings on exit from this
102 // block. Calculated in Phase 2.
103 Status Exit;
104
105 // The Status that represents the intersection of exit Mode register settings
106 // from all predecessor blocks. Calculated in Phase 2, and used by Phase 3.
107 Status Pred;
108
109 // In Phase 1 we record the first instruction that has a mode requirement,
110 // which is used in Phase 3 if we need to insert a mode change.
111 MachineInstr *FirstInsertionPoint;
112
113 BlockData() : FirstInsertionPoint(nullptr) {};
114};
115
116namespace {
117
118class SIModeRegister : public MachineFunctionPass {
119public:
120 static char ID;
121
122 std::vector<std::unique_ptr<BlockData>> BlockInfo;
123 std::queue<MachineBasicBlock *> Phase2List;
124
125 // The default mode register setting currently only caters for the floating
126 // point double precision rounding mode.
127 // We currently assume the default rounding mode is Round to Nearest
128 // NOTE: this should come from a per function rounding mode setting once such
129 // a setting exists.
130 unsigned DefaultMode = FP_ROUND_ROUND_TO_NEAREST0;
131 Status DefaultStatus =
132 Status(FP_ROUND_MODE_DP(0x3)(((0x3) & 0x3) << 2), FP_ROUND_MODE_DP(DefaultMode)(((DefaultMode) & 0x3) << 2));
133
134public:
135 SIModeRegister() : MachineFunctionPass(ID) {}
136
137 bool runOnMachineFunction(MachineFunction &MF) override;
138
139 void getAnalysisUsage(AnalysisUsage &AU) const override {
140 AU.setPreservesCFG();
141 MachineFunctionPass::getAnalysisUsage(AU);
142 }
143
144 void processBlockPhase1(MachineBasicBlock &MBB, const SIInstrInfo *TII);
145
146 void processBlockPhase2(MachineBasicBlock &MBB, const SIInstrInfo *TII);
147
148 void processBlockPhase3(MachineBasicBlock &MBB, const SIInstrInfo *TII);
149
150 Status getInstructionMode(MachineInstr &MI, const SIInstrInfo *TII);
151
152 void insertSetreg(MachineBasicBlock &MBB, MachineInstr *I,
153 const SIInstrInfo *TII, Status InstrMode);
154};
155} // End anonymous namespace.
156
157INITIALIZE_PASS(SIModeRegister, DEBUG_TYPE,static void *initializeSIModeRegisterPassOnce(PassRegistry &
Registry) { PassInfo *PI = new PassInfo( "Insert required mode register values"
, "si-mode-register", &SIModeRegister::ID, PassInfo::NormalCtor_t
(callDefaultCtor<SIModeRegister>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeSIModeRegisterPassFlag; void llvm::initializeSIModeRegisterPass
(PassRegistry &Registry) { llvm::call_once(InitializeSIModeRegisterPassFlag
, initializeSIModeRegisterPassOnce, std::ref(Registry)); }
158 "Insert required mode register values", false, false)static void *initializeSIModeRegisterPassOnce(PassRegistry &
Registry) { PassInfo *PI = new PassInfo( "Insert required mode register values"
, "si-mode-register", &SIModeRegister::ID, PassInfo::NormalCtor_t
(callDefaultCtor<SIModeRegister>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeSIModeRegisterPassFlag; void llvm::initializeSIModeRegisterPass
(PassRegistry &Registry) { llvm::call_once(InitializeSIModeRegisterPassFlag
, initializeSIModeRegisterPassOnce, std::ref(Registry)); }
159
160char SIModeRegister::ID = 0;
161
162char &llvm::SIModeRegisterID = SIModeRegister::ID;
163
164FunctionPass *llvm::createSIModeRegisterPass() { return new SIModeRegister(); }
165
166// Determine the Mode register setting required for this instruction.
167// Instructions which don't use the Mode register return a null Status.
168// Note this currently only deals with instructions that use the floating point
169// double precision setting.
170Status SIModeRegister::getInstructionMode(MachineInstr &MI,
171 const SIInstrInfo *TII) {
172 if (TII->usesFPDPRounding(MI)) {
173 switch (MI.getOpcode()) {
174 case AMDGPU::V_INTERP_P1LL_F16:
175 case AMDGPU::V_INTERP_P1LV_F16:
176 case AMDGPU::V_INTERP_P2_F16:
177 // f16 interpolation instructions need double precision round to zero
178 return Status(FP_ROUND_MODE_DP(3)(((3) & 0x3) << 2),
179 FP_ROUND_MODE_DP(FP_ROUND_ROUND_TO_ZERO)(((3) & 0x3) << 2));
180 default:
181 return DefaultStatus;
182 }
183 }
184 return Status();
185}
186
187// Insert a setreg instruction to update the Mode register.
188// It is possible (though unlikely) for an instruction to require a change to
189// the value of disjoint parts of the Mode register when we don't know the
190// value of the intervening bits. In that case we need to use more than one
191// setreg instruction.
192void SIModeRegister::insertSetreg(MachineBasicBlock &MBB, MachineInstr *MI,
193 const SIInstrInfo *TII, Status InstrMode) {
194 while (InstrMode.Mask) {
8
Loop condition is true. Entering loop body
195 unsigned Offset = countTrailingZeros<unsigned>(InstrMode.Mask);
196 unsigned Width = countTrailingOnes<unsigned>(InstrMode.Mask >> Offset);
9
Calling 'countTrailingOnes<unsigned int>'
19
Returning from 'countTrailingOnes<unsigned int>'
20
'Width' initialized to 32
197 unsigned Value = (InstrMode.Mode >> Offset) & ((1 << Width) - 1);
21
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'int'
198 BuildMI(MBB, MI, 0, TII->get(AMDGPU::S_SETREG_IMM32_B32))
199 .addImm(Value)
200 .addImm(((Width - 1) << AMDGPU::Hwreg::WIDTH_M1_SHIFT_) |
201 (Offset << AMDGPU::Hwreg::OFFSET_SHIFT_) |
202 (AMDGPU::Hwreg::ID_MODE << AMDGPU::Hwreg::ID_SHIFT_));
203 ++NumSetregInserted;
204 InstrMode.Mask &= ~(((1 << Width) - 1) << Offset);
205 }
206}
207
208// In Phase 1 we iterate through the instructions of the block and for each
209// instruction we get its mode usage. If the instruction uses the Mode register
210// we:
211// - update the Change status, which tracks the changes to the Mode register
212// made by this block
213// - if this instruction's requirements are compatible with the current setting
214// of the Mode register we merge the modes
215// - if it isn't compatible and an InsertionPoint isn't set, then we set the
216// InsertionPoint to the current instruction, and we remember the current
217// mode
218// - if it isn't compatible and InsertionPoint is set we insert a seteg before
219// that instruction (unless this instruction forms part of the block's
220// entry requirements in which case the insertion is deferred until Phase 3
221// when predecessor exit values are known), and move the insertion point to
222// this instruction
223// - if this is a setreg instruction we treat it as an incompatible instruction.
224// This is sub-optimal but avoids some nasty corner cases, and is expected to
225// occur very rarely.
226// - on exit we have set the Require, Change, and initial Exit modes.
227void SIModeRegister::processBlockPhase1(MachineBasicBlock &MBB,
228 const SIInstrInfo *TII) {
229 auto NewInfo = std::make_unique<BlockData>();
230 MachineInstr *InsertionPoint = nullptr;
231 // RequirePending is used to indicate whether we are collecting the initial
232 // requirements for the block, and need to defer the first InsertionPoint to
233 // Phase 3. It is set to false once we have set FirstInsertionPoint, or when
234 // we discover an explict setreg that means this block doesn't have any
235 // initial requirements.
236 bool RequirePending = true;
237 Status IPChange;
238 for (MachineInstr &MI : MBB) {
239 Status InstrMode = getInstructionMode(MI, TII);
240 if ((MI.getOpcode() == AMDGPU::S_SETREG_B32) ||
241 (MI.getOpcode() == AMDGPU::S_SETREG_IMM32_B32)) {
242 // We preserve any explicit mode register setreg instruction we encounter,
243 // as we assume it has been inserted by a higher authority (this is
244 // likely to be a very rare occurrence).
245 unsigned Dst = TII->getNamedOperand(MI, AMDGPU::OpName::simm16)->getImm();
246 if (((Dst & AMDGPU::Hwreg::ID_MASK_) >> AMDGPU::Hwreg::ID_SHIFT_) !=
247 AMDGPU::Hwreg::ID_MODE)
248 continue;
249
250 unsigned Width = ((Dst & AMDGPU::Hwreg::WIDTH_M1_MASK_) >>
251 AMDGPU::Hwreg::WIDTH_M1_SHIFT_) +
252 1;
253 unsigned Offset =
254 (Dst & AMDGPU::Hwreg::OFFSET_MASK_) >> AMDGPU::Hwreg::OFFSET_SHIFT_;
255 unsigned Mask = ((1 << Width) - 1) << Offset;
256
257 // If an InsertionPoint is set we will insert a setreg there.
258 if (InsertionPoint) {
259 insertSetreg(MBB, InsertionPoint, TII, IPChange.delta(NewInfo->Change));
260 InsertionPoint = nullptr;
261 }
262 // If this is an immediate then we know the value being set, but if it is
263 // not an immediate then we treat the modified bits of the mode register
264 // as unknown.
265 if (MI.getOpcode() == AMDGPU::S_SETREG_IMM32_B32) {
266 unsigned Val = TII->getNamedOperand(MI, AMDGPU::OpName::imm)->getImm();
267 unsigned Mode = (Val << Offset) & Mask;
268 Status Setreg = Status(Mask, Mode);
269 // If we haven't already set the initial requirements for the block we
270 // don't need to as the requirements start from this explicit setreg.
271 RequirePending = false;
272 NewInfo->Change = NewInfo->Change.merge(Setreg);
273 } else {
274 NewInfo->Change = NewInfo->Change.mergeUnknown(Mask);
275 }
276 } else if (!NewInfo->Change.isCompatible(InstrMode)) {
277 // This instruction uses the Mode register and its requirements aren't
278 // compatible with the current mode.
279 if (InsertionPoint) {
280 // If the required mode change cannot be included in the current
281 // InsertionPoint changes, we need a setreg and start a new
282 // InsertionPoint.
283 if (!IPChange.delta(NewInfo->Change).isCombinable(InstrMode)) {
284 if (RequirePending) {
285 // This is the first insertionPoint in the block so we will defer
286 // the insertion of the setreg to Phase 3 where we know whether or
287 // not it is actually needed.
288 NewInfo->FirstInsertionPoint = InsertionPoint;
289 NewInfo->Require = NewInfo->Change;
290 RequirePending = false;
291 } else {
292 insertSetreg(MBB, InsertionPoint, TII,
293 IPChange.delta(NewInfo->Change));
294 IPChange = NewInfo->Change;
295 }
296 // Set the new InsertionPoint
297 InsertionPoint = &MI;
298 }
299 NewInfo->Change = NewInfo->Change.merge(InstrMode);
300 } else {
301 // No InsertionPoint is currently set - this is either the first in
302 // the block or we have previously seen an explicit setreg.
303 InsertionPoint = &MI;
304 IPChange = NewInfo->Change;
305 NewInfo->Change = NewInfo->Change.merge(InstrMode);
306 }
307 }
308 }
309 if (RequirePending) {
310 // If we haven't yet set the initial requirements for the block we set them
311 // now.
312 NewInfo->FirstInsertionPoint = InsertionPoint;
313 NewInfo->Require = NewInfo->Change;
314 } else if (InsertionPoint) {
315 // We need to insert a setreg at the InsertionPoint
316 insertSetreg(MBB, InsertionPoint, TII, IPChange.delta(NewInfo->Change));
317 }
318 NewInfo->Exit = NewInfo->Change;
319 BlockInfo[MBB.getNumber()] = std::move(NewInfo);
320}
321
322// In Phase 2 we revisit each block and calculate the common Mode register
323// value provided by all predecessor blocks. If the Exit value for the block
324// is changed, then we add the successor blocks to the worklist so that the
325// exit value is propagated.
326void SIModeRegister::processBlockPhase2(MachineBasicBlock &MBB,
327 const SIInstrInfo *TII) {
328// BlockData *BI = BlockInfo[MBB.getNumber()];
329 unsigned ThisBlock = MBB.getNumber();
330 if (MBB.pred_empty()) {
331 // There are no predecessors, so use the default starting status.
332 BlockInfo[ThisBlock]->Pred = DefaultStatus;
333 } else {
334 // Build a status that is common to all the predecessors by intersecting
335 // all the predecessor exit status values.
336 MachineBasicBlock::pred_iterator P = MBB.pred_begin(), E = MBB.pred_end();
337 MachineBasicBlock &PB = *(*P);
338 BlockInfo[ThisBlock]->Pred = BlockInfo[PB.getNumber()]->Exit;
339
340 for (P = std::next(P); P != E; P = std::next(P)) {
341 MachineBasicBlock *Pred = *P;
342 BlockInfo[ThisBlock]->Pred = BlockInfo[ThisBlock]->Pred.intersect(BlockInfo[Pred->getNumber()]->Exit);
343 }
344 }
345 Status TmpStatus = BlockInfo[ThisBlock]->Pred.merge(BlockInfo[ThisBlock]->Change);
346 if (BlockInfo[ThisBlock]->Exit != TmpStatus) {
347 BlockInfo[ThisBlock]->Exit = TmpStatus;
348 // Add the successors to the work list so we can propagate the changed exit
349 // status.
350 for (MachineBasicBlock::succ_iterator S = MBB.succ_begin(),
351 E = MBB.succ_end();
352 S != E; S = std::next(S)) {
353 MachineBasicBlock &B = *(*S);
354 Phase2List.push(&B);
355 }
356 }
357}
358
359// In Phase 3 we revisit each block and if it has an insertion point defined we
360// check whether the predecessor mode meets the block's entry requirements. If
361// not we insert an appropriate setreg instruction to modify the Mode register.
362void SIModeRegister::processBlockPhase3(MachineBasicBlock &MBB,
363 const SIInstrInfo *TII) {
364// BlockData *BI = BlockInfo[MBB.getNumber()];
365 unsigned ThisBlock = MBB.getNumber();
366 if (!BlockInfo[ThisBlock]->Pred.isCompatible(BlockInfo[ThisBlock]->Require)) {
4
Taking true branch
367 Status Delta = BlockInfo[ThisBlock]->Pred.delta(BlockInfo[ThisBlock]->Require);
368 if (BlockInfo[ThisBlock]->FirstInsertionPoint)
5
Assuming field 'FirstInsertionPoint' is null
6
Taking false branch
369 insertSetreg(MBB, BlockInfo[ThisBlock]->FirstInsertionPoint, TII, Delta);
370 else
371 insertSetreg(MBB, &MBB.instr_front(), TII, Delta);
7
Calling 'SIModeRegister::insertSetreg'
372 }
373}
374
375bool SIModeRegister::runOnMachineFunction(MachineFunction &MF) {
376 BlockInfo.resize(MF.getNumBlockIDs());
377 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
378 const SIInstrInfo *TII = ST.getInstrInfo();
379
380 // Processing is performed in a number of phases
381
382 // Phase 1 - determine the initial mode required by each block, and add setreg
383 // instructions for intra block requirements.
384 for (MachineBasicBlock &BB : MF)
385 processBlockPhase1(BB, TII);
386
387 // Phase 2 - determine the exit mode from each block. We add all blocks to the
388 // list here, but will also add any that need to be revisited during Phase 2
389 // processing.
390 for (MachineBasicBlock &BB : MF)
391 Phase2List.push(&BB);
392 while (!Phase2List.empty()) {
1
Assuming the condition is false
2
Loop condition is false. Execution continues on line 399
393 processBlockPhase2(*Phase2List.front(), TII);
394 Phase2List.pop();
395 }
396
397 // Phase 3 - add an initial setreg to each block where the required entry mode
398 // is not satisfied by the exit mode of all its predecessors.
399 for (MachineBasicBlock &BB : MF)
400 processBlockPhase3(BB, TII);
3
Calling 'SIModeRegister::processBlockPhase3'
401
402 BlockInfo.clear();
403
404 return NumSetregInserted > 0;
405}

/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h

1//===-- llvm/Support/MathExtras.h - Useful math functions -------*- 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// This file contains some functions that are useful for math stuff.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_SUPPORT_MATHEXTRAS_H
14#define LLVM_SUPPORT_MATHEXTRAS_H
15
16#include "llvm/Support/Compiler.h"
17#include <algorithm>
18#include <cassert>
19#include <climits>
20#include <cmath>
21#include <cstdint>
22#include <cstring>
23#include <limits>
24#include <type_traits>
25
26#ifdef __ANDROID_NDK__
27#include <android/api-level.h>
28#endif
29
30#ifdef _MSC_VER
31// Declare these intrinsics manually rather including intrin.h. It's very
32// expensive, and MathExtras.h is popular.
33// #include <intrin.h>
34extern "C" {
35unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
36unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
37unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
38unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
39}
40#endif
41
42namespace llvm {
43
44/// The behavior an operation has on an input of 0.
45enum ZeroBehavior {
46 /// The returned value is undefined.
47 ZB_Undefined,
48 /// The returned value is numeric_limits<T>::max()
49 ZB_Max,
50 /// The returned value is numeric_limits<T>::digits
51 ZB_Width
52};
53
54/// Mathematical constants.
55namespace numbers {
56// TODO: Track C++20 std::numbers.
57// TODO: Favor using the hexadecimal FP constants (requires C++17).
58constexpr double e = 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113
59 egamma = .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620
60 ln2 = .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162
61 ln10 = 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392
62 log2e = 1.4426950408889634074, // (0x1.71547652b82feP+0)
63 log10e = .43429448190325182765, // (0x1.bcb7b1526e50eP-2)
64 pi = 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796
65 inv_pi = .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541
66 sqrtpi = 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161
67 inv_sqrtpi = .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197
68 sqrt2 = 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219
69 inv_sqrt2 = .70710678118654752440, // (0x1.6a09e667f3bcdP-1)
70 sqrt3 = 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194
71 inv_sqrt3 = .57735026918962576451, // (0x1.279a74590331cP-1)
72 phi = 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622
73constexpr float ef = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113
74 egammaf = .577215665F, // (0x1.2788d0P-1) https://oeis.org/A001620
75 ln2f = .693147181F, // (0x1.62e430P-1) https://oeis.org/A002162
76 ln10f = 2.30258509F, // (0x1.26bb1cP+1) https://oeis.org/A002392
77 log2ef = 1.44269504F, // (0x1.715476P+0)
78 log10ef = .434294482F, // (0x1.bcb7b2P-2)
79 pif = 3.14159265F, // (0x1.921fb6P+1) https://oeis.org/A000796
80 inv_pif = .318309886F, // (0x1.45f306P-2) https://oeis.org/A049541
81 sqrtpif = 1.77245385F, // (0x1.c5bf8aP+0) https://oeis.org/A002161
82 inv_sqrtpif = .564189584F, // (0x1.20dd76P-1) https://oeis.org/A087197
83 sqrt2f = 1.41421356F, // (0x1.6a09e6P+0) https://oeis.org/A002193
84 inv_sqrt2f = .707106781F, // (0x1.6a09e6P-1)
85 sqrt3f = 1.73205081F, // (0x1.bb67aeP+0) https://oeis.org/A002194
86 inv_sqrt3f = .577350269F, // (0x1.279a74P-1)
87 phif = 1.61803399F; // (0x1.9e377aP+0) https://oeis.org/A001622
88} // namespace numbers
89
90namespace detail {
91template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
92 static unsigned count(T Val, ZeroBehavior) {
93 if (!Val)
94 return std::numeric_limits<T>::digits;
95 if (Val & 0x1)
96 return 0;
97
98 // Bisection method.
99 unsigned ZeroBits = 0;
100 T Shift = std::numeric_limits<T>::digits >> 1;
101 T Mask = std::numeric_limits<T>::max() >> Shift;
102 while (Shift) {
103 if ((Val & Mask) == 0) {
104 Val >>= Shift;
105 ZeroBits |= Shift;
106 }
107 Shift >>= 1;
108 Mask >>= Shift;
109 }
110 return ZeroBits;
111 }
112};
113
114#if defined(__GNUC__4) || defined(_MSC_VER)
115template <typename T> struct TrailingZerosCounter<T, 4> {
116 static unsigned count(T Val, ZeroBehavior ZB) {
117 if (ZB
11.1
'ZB' is not equal to ZB_Undefined
11.1
'ZB' is not equal to ZB_Undefined
!= ZB_Undefined && Val == 0)
12
Assuming 'Val' is equal to 0
13
Taking true branch
118 return 32;
14
Returning the value 32
119
120#if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4)
121 return __builtin_ctz(Val);
122#elif defined(_MSC_VER)
123 unsigned long Index;
124 _BitScanForward(&Index, Val);
125 return Index;
126#endif
127 }
128};
129
130#if !defined(_MSC_VER) || defined(_M_X64)
131template <typename T> struct TrailingZerosCounter<T, 8> {
132 static unsigned count(T Val, ZeroBehavior ZB) {
133 if (ZB != ZB_Undefined && Val == 0)
134 return 64;
135
136#if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4)
137 return __builtin_ctzll(Val);
138#elif defined(_MSC_VER)
139 unsigned long Index;
140 _BitScanForward64(&Index, Val);
141 return Index;
142#endif
143 }
144};
145#endif
146#endif
147} // namespace detail
148
149/// Count number of 0's from the least significant bit to the most
150/// stopping at the first 1.
151///
152/// Only unsigned integral types are allowed.
153///
154/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
155/// valid arguments.
156template <typename T>
157unsigned countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
158 static_assert(std::numeric_limits<T>::is_integer &&
159 !std::numeric_limits<T>::is_signed,
160 "Only unsigned integral types are allowed.");
161 return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
11
Calling 'TrailingZerosCounter::count'
15
Returning from 'TrailingZerosCounter::count'
16
Returning the value 32
162}
163
164namespace detail {
165template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
166 static unsigned count(T Val, ZeroBehavior) {
167 if (!Val)
168 return std::numeric_limits<T>::digits;
169
170 // Bisection method.
171 unsigned ZeroBits = 0;
172 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
173 T Tmp = Val >> Shift;
174 if (Tmp)
175 Val = Tmp;
176 else
177 ZeroBits |= Shift;
178 }
179 return ZeroBits;
180 }
181};
182
183#if defined(__GNUC__4) || defined(_MSC_VER)
184template <typename T> struct LeadingZerosCounter<T, 4> {
185 static unsigned count(T Val, ZeroBehavior ZB) {
186 if (ZB != ZB_Undefined && Val == 0)
187 return 32;
188
189#if __has_builtin(__builtin_clz)1 || defined(__GNUC__4)
190 return __builtin_clz(Val);
191#elif defined(_MSC_VER)
192 unsigned long Index;
193 _BitScanReverse(&Index, Val);
194 return Index ^ 31;
195#endif
196 }
197};
198
199#if !defined(_MSC_VER) || defined(_M_X64)
200template <typename T> struct LeadingZerosCounter<T, 8> {
201 static unsigned count(T Val, ZeroBehavior ZB) {
202 if (ZB != ZB_Undefined && Val == 0)
203 return 64;
204
205#if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4)
206 return __builtin_clzll(Val);
207#elif defined(_MSC_VER)
208 unsigned long Index;
209 _BitScanReverse64(&Index, Val);
210 return Index ^ 63;
211#endif
212 }
213};
214#endif
215#endif
216} // namespace detail
217
218/// Count number of 0's from the most significant bit to the least
219/// stopping at the first 1.
220///
221/// Only unsigned integral types are allowed.
222///
223/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
224/// valid arguments.
225template <typename T>
226unsigned countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
227 static_assert(std::numeric_limits<T>::is_integer &&
228 !std::numeric_limits<T>::is_signed,
229 "Only unsigned integral types are allowed.");
230 return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
231}
232
233/// Get the index of the first set bit starting from the least
234/// significant bit.
235///
236/// Only unsigned integral types are allowed.
237///
238/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
239/// valid arguments.
240template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
241 if (ZB == ZB_Max && Val == 0)
242 return std::numeric_limits<T>::max();
243
244 return countTrailingZeros(Val, ZB_Undefined);
245}
246
247/// Create a bitmask with the N right-most bits set to 1, and all other
248/// bits set to 0. Only unsigned types are allowed.
249template <typename T> T maskTrailingOnes(unsigned N) {
250 static_assert(std::is_unsigned<T>::value, "Invalid type!");
251 const unsigned Bits = CHAR_BIT8 * sizeof(T);
252 assert(N <= Bits && "Invalid bit index")((N <= Bits && "Invalid bit index") ? static_cast<
void> (0) : __assert_fail ("N <= Bits && \"Invalid bit index\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h"
, 252, __PRETTY_FUNCTION__))
;
253 return N == 0 ? 0 : (T(-1) >> (Bits - N));
254}
255
256/// Create a bitmask with the N left-most bits set to 1, and all other
257/// bits set to 0. Only unsigned types are allowed.
258template <typename T> T maskLeadingOnes(unsigned N) {
259 return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
260}
261
262/// Create a bitmask with the N right-most bits set to 0, and all other
263/// bits set to 1. Only unsigned types are allowed.
264template <typename T> T maskTrailingZeros(unsigned N) {
265 return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
266}
267
268/// Create a bitmask with the N left-most bits set to 0, and all other
269/// bits set to 1. Only unsigned types are allowed.
270template <typename T> T maskLeadingZeros(unsigned N) {
271 return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
272}
273
274/// Get the index of the last set bit starting from the least
275/// significant bit.
276///
277/// Only unsigned integral types are allowed.
278///
279/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
280/// valid arguments.
281template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
282 if (ZB == ZB_Max && Val == 0)
283 return std::numeric_limits<T>::max();
284
285 // Use ^ instead of - because both gcc and llvm can remove the associated ^
286 // in the __builtin_clz intrinsic on x86.
287 return countLeadingZeros(Val, ZB_Undefined) ^
288 (std::numeric_limits<T>::digits - 1);
289}
290
291/// Macro compressed bit reversal table for 256 bits.
292///
293/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
294static const unsigned char BitReverseTable256[256] = {
295#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
296#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
297#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
298 R6(0), R6(2), R6(1), R6(3)
299#undef R2
300#undef R4
301#undef R6
302};
303
304/// Reverse the bits in \p Val.
305template <typename T>
306T reverseBits(T Val) {
307 unsigned char in[sizeof(Val)];
308 unsigned char out[sizeof(Val)];
309 std::memcpy(in, &Val, sizeof(Val));
310 for (unsigned i = 0; i < sizeof(Val); ++i)
311 out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
312 std::memcpy(&Val, out, sizeof(Val));
313 return Val;
314}
315
316// NOTE: The following support functions use the _32/_64 extensions instead of
317// type overloading so that signed and unsigned integers can be used without
318// ambiguity.
319
320/// Return the high 32 bits of a 64 bit value.
321constexpr inline uint32_t Hi_32(uint64_t Value) {
322 return static_cast<uint32_t>(Value >> 32);
323}
324
325/// Return the low 32 bits of a 64 bit value.
326constexpr inline uint32_t Lo_32(uint64_t Value) {
327 return static_cast<uint32_t>(Value);
328}
329
330/// Make a 64-bit integer from a high / low pair of 32-bit integers.
331constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
332 return ((uint64_t)High << 32) | (uint64_t)Low;
333}
334
335/// Checks if an integer fits into the given bit width.
336template <unsigned N> constexpr inline bool isInt(int64_t x) {
337 return N >= 64 || (-(INT64_C(1)1L<<(N-1)) <= x && x < (INT64_C(1)1L<<(N-1)));
338}
339// Template specializations to get better code for common cases.
340template <> constexpr inline bool isInt<8>(int64_t x) {
341 return static_cast<int8_t>(x) == x;
342}
343template <> constexpr inline bool isInt<16>(int64_t x) {
344 return static_cast<int16_t>(x) == x;
345}
346template <> constexpr inline bool isInt<32>(int64_t x) {
347 return static_cast<int32_t>(x) == x;
348}
349
350/// Checks if a signed integer is an N bit number shifted left by S.
351template <unsigned N, unsigned S>
352constexpr inline bool isShiftedInt(int64_t x) {
353 static_assert(
354 N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
355 static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
356 return isInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
357}
358
359/// Checks if an unsigned integer fits into the given bit width.
360///
361/// This is written as two functions rather than as simply
362///
363/// return N >= 64 || X < (UINT64_C(1) << N);
364///
365/// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting
366/// left too many places.
367template <unsigned N>
368constexpr inline std::enable_if_t<(N < 64), bool> isUInt(uint64_t X) {
369 static_assert(N > 0, "isUInt<0> doesn't make sense");
370 return X < (UINT64_C(1)1UL << (N));
371}
372template <unsigned N>
373constexpr inline std::enable_if_t<N >= 64, bool> isUInt(uint64_t X) {
374 return true;
375}
376
377// Template specializations to get better code for common cases.
378template <> constexpr inline bool isUInt<8>(uint64_t x) {
379 return static_cast<uint8_t>(x) == x;
380}
381template <> constexpr inline bool isUInt<16>(uint64_t x) {
382 return static_cast<uint16_t>(x) == x;
383}
384template <> constexpr inline bool isUInt<32>(uint64_t x) {
385 return static_cast<uint32_t>(x) == x;
386}
387
388/// Checks if a unsigned integer is an N bit number shifted left by S.
389template <unsigned N, unsigned S>
390constexpr inline bool isShiftedUInt(uint64_t x) {
391 static_assert(
392 N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
393 static_assert(N + S <= 64,
394 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
395 // Per the two static_asserts above, S must be strictly less than 64. So
396 // 1 << S is not undefined behavior.
397 return isUInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
398}
399
400/// Gets the maximum value for a N-bit unsigned integer.
401inline uint64_t maxUIntN(uint64_t N) {
402 assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h"
, 402, __PRETTY_FUNCTION__))
;
403
404 // uint64_t(1) << 64 is undefined behavior, so we can't do
405 // (uint64_t(1) << N) - 1
406 // without checking first that N != 64. But this works and doesn't have a
407 // branch.
408 return UINT64_MAX(18446744073709551615UL) >> (64 - N);
409}
410
411/// Gets the minimum value for a N-bit signed integer.
412inline int64_t minIntN(int64_t N) {
413 assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h"
, 413, __PRETTY_FUNCTION__))
;
414
415 return -(UINT64_C(1)1UL<<(N-1));
416}
417
418/// Gets the maximum value for a N-bit signed integer.
419inline int64_t maxIntN(int64_t N) {
420 assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h"
, 420, __PRETTY_FUNCTION__))
;
421
422 // This relies on two's complement wraparound when N == 64, so we convert to
423 // int64_t only at the very end to avoid UB.
424 return (UINT64_C(1)1UL << (N - 1)) - 1;
425}
426
427/// Checks if an unsigned integer fits into the given (dynamic) bit width.
428inline bool isUIntN(unsigned N, uint64_t x) {
429 return N >= 64 || x <= maxUIntN(N);
430}
431
432/// Checks if an signed integer fits into the given (dynamic) bit width.
433inline bool isIntN(unsigned N, int64_t x) {
434 return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
435}
436
437/// Return true if the argument is a non-empty sequence of ones starting at the
438/// least significant bit with the remainder zero (32 bit version).
439/// Ex. isMask_32(0x0000FFFFU) == true.
440constexpr inline bool isMask_32(uint32_t Value) {
441 return Value && ((Value + 1) & Value) == 0;
442}
443
444/// Return true if the argument is a non-empty sequence of ones starting at the
445/// least significant bit with the remainder zero (64 bit version).
446constexpr inline bool isMask_64(uint64_t Value) {
447 return Value && ((Value + 1) & Value) == 0;
448}
449
450/// Return true if the argument contains a non-empty sequence of ones with the
451/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
452constexpr inline bool isShiftedMask_32(uint32_t Value) {
453 return Value && isMask_32((Value - 1) | Value);
454}
455
456/// Return true if the argument contains a non-empty sequence of ones with the
457/// remainder zero (64 bit version.)
458constexpr inline bool isShiftedMask_64(uint64_t Value) {
459 return Value && isMask_64((Value - 1) | Value);
460}
461
462/// Return true if the argument is a power of two > 0.
463/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
464constexpr inline bool isPowerOf2_32(uint32_t Value) {
465 return Value && !(Value & (Value - 1));
466}
467
468/// Return true if the argument is a power of two > 0 (64 bit edition.)
469constexpr inline bool isPowerOf2_64(uint64_t Value) {
470 return Value && !(Value & (Value - 1));
471}
472
473/// Count the number of ones from the most significant bit to the first
474/// zero bit.
475///
476/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
477/// Only unsigned integral types are allowed.
478///
479/// \param ZB the behavior on an input of all ones. Only ZB_Width and
480/// ZB_Undefined are valid arguments.
481template <typename T>
482unsigned countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
483 static_assert(std::numeric_limits<T>::is_integer &&
484 !std::numeric_limits<T>::is_signed,
485 "Only unsigned integral types are allowed.");
486 return countLeadingZeros<T>(~Value, ZB);
487}
488
489/// Count the number of ones from the least significant bit to the first
490/// zero bit.
491///
492/// Ex. countTrailingOnes(0x00FF00FF) == 8.
493/// Only unsigned integral types are allowed.
494///
495/// \param ZB the behavior on an input of all ones. Only ZB_Width and
496/// ZB_Undefined are valid arguments.
497template <typename T>
498unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
499 static_assert(std::numeric_limits<T>::is_integer &&
500 !std::numeric_limits<T>::is_signed,
501 "Only unsigned integral types are allowed.");
502 return countTrailingZeros<T>(~Value, ZB);
10
Calling 'countTrailingZeros<unsigned int>'
17
Returning from 'countTrailingZeros<unsigned int>'
18
Returning the value 32
503}
504
505namespace detail {
506template <typename T, std::size_t SizeOfT> struct PopulationCounter {
507 static unsigned count(T Value) {
508 // Generic version, forward to 32 bits.
509 static_assert(SizeOfT <= 4, "Not implemented!");
510#if defined(__GNUC__4)
511 return __builtin_popcount(Value);
512#else
513 uint32_t v = Value;
514 v = v - ((v >> 1) & 0x55555555);
515 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
516 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
517#endif
518 }
519};
520
521template <typename T> struct PopulationCounter<T, 8> {
522 static unsigned count(T Value) {
523#if defined(__GNUC__4)
524 return __builtin_popcountll(Value);
525#else
526 uint64_t v = Value;
527 v = v - ((v >> 1) & 0x5555555555555555ULL);
528 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
529 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
530 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
531#endif
532 }
533};
534} // namespace detail
535
536/// Count the number of set bits in a value.
537/// Ex. countPopulation(0xF000F000) = 8
538/// Returns 0 if the word is zero.
539template <typename T>
540inline unsigned countPopulation(T Value) {
541 static_assert(std::numeric_limits<T>::is_integer &&
542 !std::numeric_limits<T>::is_signed,
543 "Only unsigned integral types are allowed.");
544 return detail::PopulationCounter<T, sizeof(T)>::count(Value);
545}
546
547/// Compile time Log2.
548/// Valid only for positive powers of two.
549template <size_t kValue> constexpr inline size_t CTLog2() {
550 static_assert(kValue > 0 && llvm::isPowerOf2_64(kValue),
551 "Value is not a valid power of 2");
552 return 1 + CTLog2<kValue / 2>();
553}
554
555template <> constexpr inline size_t CTLog2<1>() { return 0; }
556
557/// Return the log base 2 of the specified value.
558inline double Log2(double Value) {
559#if defined(__ANDROID_API__) && __ANDROID_API__ < 18
560 return __builtin_log(Value) / __builtin_log(2.0);
561#else
562 return log2(Value);
563#endif
564}
565
566/// Return the floor log base 2 of the specified value, -1 if the value is zero.
567/// (32 bit edition.)
568/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
569inline unsigned Log2_32(uint32_t Value) {
570 return 31 - countLeadingZeros(Value);
571}
572
573/// Return the floor log base 2 of the specified value, -1 if the value is zero.
574/// (64 bit edition.)
575inline unsigned Log2_64(uint64_t Value) {
576 return 63 - countLeadingZeros(Value);
577}
578
579/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
580/// (32 bit edition).
581/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
582inline unsigned Log2_32_Ceil(uint32_t Value) {
583 return 32 - countLeadingZeros(Value - 1);
584}
585
586/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
587/// (64 bit edition.)
588inline unsigned Log2_64_Ceil(uint64_t Value) {
589 return 64 - countLeadingZeros(Value - 1);
590}
591
592/// Return the greatest common divisor of the values using Euclid's algorithm.
593template <typename T>
594inline T greatestCommonDivisor(T A, T B) {
595 while (B) {
596 T Tmp = B;
597 B = A % B;
598 A = Tmp;
599 }
600 return A;
601}
602
603inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
604 return greatestCommonDivisor<uint64_t>(A, B);
605}
606
607/// This function takes a 64-bit integer and returns the bit equivalent double.
608inline double BitsToDouble(uint64_t Bits) {
609 double D;
610 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
611 memcpy(&D, &Bits, sizeof(Bits));
612 return D;
613}
614
615/// This function takes a 32-bit integer and returns the bit equivalent float.
616inline float BitsToFloat(uint32_t Bits) {
617 float F;
618 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
619 memcpy(&F, &Bits, sizeof(Bits));
620 return F;
621}
622
623/// This function takes a double and returns the bit equivalent 64-bit integer.
624/// Note that copying doubles around changes the bits of NaNs on some hosts,
625/// notably x86, so this routine cannot be used if these bits are needed.
626inline uint64_t DoubleToBits(double Double) {
627 uint64_t Bits;
628 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
629 memcpy(&Bits, &Double, sizeof(Double));
630 return Bits;
631}
632
633/// This function takes a float and returns the bit equivalent 32-bit integer.
634/// Note that copying floats around changes the bits of NaNs on some hosts,
635/// notably x86, so this routine cannot be used if these bits are needed.
636inline uint32_t FloatToBits(float Float) {
637 uint32_t Bits;
638 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
639 memcpy(&Bits, &Float, sizeof(Float));
640 return Bits;
641}
642
643/// A and B are either alignments or offsets. Return the minimum alignment that
644/// may be assumed after adding the two together.
645constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
646 // The largest power of 2 that divides both A and B.
647 //
648 // Replace "-Value" by "1+~Value" in the following commented code to avoid
649 // MSVC warning C4146
650 // return (A | B) & -(A | B);
651 return (A | B) & (1 + ~(A | B));
652}
653
654/// Returns the next power of two (in 64-bits) that is strictly greater than A.
655/// Returns zero on overflow.
656inline uint64_t NextPowerOf2(uint64_t A) {
657 A |= (A >> 1);
658 A |= (A >> 2);
659 A |= (A >> 4);
660 A |= (A >> 8);
661 A |= (A >> 16);
662 A |= (A >> 32);
663 return A + 1;
664}
665
666/// Returns the power of two which is less than or equal to the given value.
667/// Essentially, it is a floor operation across the domain of powers of two.
668inline uint64_t PowerOf2Floor(uint64_t A) {
669 if (!A) return 0;
670 return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
671}
672
673/// Returns the power of two which is greater than or equal to the given value.
674/// Essentially, it is a ceil operation across the domain of powers of two.
675inline uint64_t PowerOf2Ceil(uint64_t A) {
676 if (!A)
677 return 0;
678 return NextPowerOf2(A - 1);
679}
680
681/// Returns the next integer (mod 2**64) that is greater than or equal to
682/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
683///
684/// If non-zero \p Skew is specified, the return value will be a minimal
685/// integer that is greater than or equal to \p Value and equal to
686/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
687/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
688///
689/// Examples:
690/// \code
691/// alignTo(5, 8) = 8
692/// alignTo(17, 8) = 24
693/// alignTo(~0LL, 8) = 0
694/// alignTo(321, 255) = 510
695///
696/// alignTo(5, 8, 7) = 7
697/// alignTo(17, 8, 1) = 17
698/// alignTo(~0LL, 8, 3) = 3
699/// alignTo(321, 255, 42) = 552
700/// \endcode
701inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
702 assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast<
void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h"
, 702, __PRETTY_FUNCTION__))
;
703 Skew %= Align;
704 return (Value + Align - 1 - Skew) / Align * Align + Skew;
705}
706
707/// Returns the next integer (mod 2**64) that is greater than or equal to
708/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
709template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
710 static_assert(Align != 0u, "Align must be non-zero");
711 return (Value + Align - 1) / Align * Align;
712}
713
714/// Returns the integer ceil(Numerator / Denominator).
715inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
716 return alignTo(Numerator, Denominator) / Denominator;
717}
718
719/// Returns the integer nearest(Numerator / Denominator).
720inline uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator) {
721 return (Numerator + (Denominator / 2)) / Denominator;
722}
723
724/// Returns the largest uint64_t less than or equal to \p Value and is
725/// \p Skew mod \p Align. \p Align must be non-zero
726inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
727 assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast<
void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h"
, 727, __PRETTY_FUNCTION__))
;
728 Skew %= Align;
729 return (Value - Skew) / Align * Align + Skew;
730}
731
732/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
733/// Requires 0 < B <= 32.
734template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
735 static_assert(B > 0, "Bit width can't be 0.");
736 static_assert(B <= 32, "Bit width out of range.");
737 return int32_t(X << (32 - B)) >> (32 - B);
738}
739
740/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
741/// Requires 0 < B < 32.
742inline int32_t SignExtend32(uint32_t X, unsigned B) {
743 assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast<
void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h"
, 743, __PRETTY_FUNCTION__))
;
744 assert(B <= 32 && "Bit width out of range.")((B <= 32 && "Bit width out of range.") ? static_cast
<void> (0) : __assert_fail ("B <= 32 && \"Bit width out of range.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h"
, 744, __PRETTY_FUNCTION__))
;
745 return int32_t(X << (32 - B)) >> (32 - B);
746}
747
748/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
749/// Requires 0 < B < 64.
750template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
751 static_assert(B > 0, "Bit width can't be 0.");
752 static_assert(B <= 64, "Bit width out of range.");
753 return int64_t(x << (64 - B)) >> (64 - B);
754}
755
756/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
757/// Requires 0 < B < 64.
758inline int64_t SignExtend64(uint64_t X, unsigned B) {
759 assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast<
void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h"
, 759, __PRETTY_FUNCTION__))
;
760 assert(B <= 64 && "Bit width out of range.")((B <= 64 && "Bit width out of range.") ? static_cast
<void> (0) : __assert_fail ("B <= 64 && \"Bit width out of range.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include/llvm/Support/MathExtras.h"
, 760, __PRETTY_FUNCTION__))
;
761 return int64_t(X << (64 - B)) >> (64 - B);
762}
763
764/// Subtract two unsigned integers, X and Y, of type T and return the absolute
765/// value of the result.
766template <typename T>
767std::enable_if_t<std::is_unsigned<T>::value, T> AbsoluteDifference(T X, T Y) {
768 return std::max(X, Y) - std::min(X, Y);
769}
770
771/// Add two unsigned integers, X and Y, of type T. Clamp the result to the
772/// maximum representable value of T on overflow. ResultOverflowed indicates if
773/// the result is larger than the maximum representable value of type T.
774template <typename T>
775std::enable_if_t<std::is_unsigned<T>::value, T>
776SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
777 bool Dummy;
778 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
779 // Hacker's Delight, p. 29
780 T Z = X + Y;
781 Overflowed = (Z < X || Z < Y);
782 if (Overflowed)
783 return std::numeric_limits<T>::max();
784 else
785 return Z;
786}
787
788/// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the
789/// maximum representable value of T on overflow. ResultOverflowed indicates if
790/// the result is larger than the maximum representable value of type T.
791template <typename T>
792std::enable_if_t<std::is_unsigned<T>::value, T>
793SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
794 bool Dummy;
795 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
796
797 // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
798 // because it fails for uint16_t (where multiplication can have undefined
799 // behavior due to promotion to int), and requires a division in addition
800 // to the multiplication.
801
802 Overflowed = false;
803
804 // Log2(Z) would be either Log2Z or Log2Z + 1.
805 // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
806 // will necessarily be less than Log2Max as desired.
807 int Log2Z = Log2_64(X) + Log2_64(Y);
808 const T Max = std::numeric_limits<T>::max();
809 int Log2Max = Log2_64(Max);
810 if (Log2Z < Log2Max) {
811 return X * Y;
812 }
813 if (Log2Z > Log2Max) {
814 Overflowed = true;
815 return Max;
816 }
817
818 // We're going to use the top bit, and maybe overflow one
819 // bit past it. Multiply all but the bottom bit then add
820 // that on at the end.
821 T Z = (X >> 1) * Y;
822 if (Z & ~(Max >> 1)) {
823 Overflowed = true;
824 return Max;
825 }
826 Z <<= 1;
827 if (X & 1)
828 return SaturatingAdd(Z, Y, ResultOverflowed);
829
830 return Z;
831}
832
833/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
834/// the product. Clamp the result to the maximum representable value of T on
835/// overflow. ResultOverflowed indicates if the result is larger than the
836/// maximum representable value of type T.
837template <typename T>
838std::enable_if_t<std::is_unsigned<T>::value, T>
839SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
840 bool Dummy;
841 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
842
843 T Product = SaturatingMultiply(X, Y, &Overflowed);
844 if (Overflowed)
845 return Product;
846
847 return SaturatingAdd(A, Product, &Overflowed);
848}
849
850/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
851extern const float huge_valf;
852
853
854/// Add two signed integers, computing the two's complement truncated result,
855/// returning true if overflow occured.
856template <typename T>
857std::enable_if_t<std::is_signed<T>::value, T> AddOverflow(T X, T Y, T &Result) {
858#if __has_builtin(__builtin_add_overflow)1
859 return __builtin_add_overflow(X, Y, &Result);
860#else
861 // Perform the unsigned addition.
862 using U = std::make_unsigned_t<T>;
863 const U UX = static_cast<U>(X);
864 const U UY = static_cast<U>(Y);
865 const U UResult = UX + UY;
866
867 // Convert to signed.
868 Result = static_cast<T>(UResult);
869
870 // Adding two positive numbers should result in a positive number.
871 if (X > 0 && Y > 0)
872 return Result <= 0;
873 // Adding two negatives should result in a negative number.
874 if (X < 0 && Y < 0)
875 return Result >= 0;
876 return false;
877#endif
878}
879
880/// Subtract two signed integers, computing the two's complement truncated
881/// result, returning true if an overflow ocurred.
882template <typename T>
883std::enable_if_t<std::is_signed<T>::value, T> SubOverflow(T X, T Y, T &Result) {
884#if __has_builtin(__builtin_sub_overflow)1
885 return __builtin_sub_overflow(X, Y, &Result);
886#else
887 // Perform the unsigned addition.
888 using U = std::make_unsigned_t<T>;
889 const U UX = static_cast<U>(X);
890 const U UY = static_cast<U>(Y);
891 const U UResult = UX - UY;
892
893 // Convert to signed.
894 Result = static_cast<T>(UResult);
895
896 // Subtracting a positive number from a negative results in a negative number.
897 if (X <= 0 && Y > 0)
898 return Result >= 0;
899 // Subtracting a negative number from a positive results in a positive number.
900 if (X >= 0 && Y < 0)
901 return Result <= 0;
902 return false;
903#endif
904}
905
906/// Multiply two signed integers, computing the two's complement truncated
907/// result, returning true if an overflow ocurred.
908template <typename T>
909std::enable_if_t<std::is_signed<T>::value, T> MulOverflow(T X, T Y, T &Result) {
910 // Perform the unsigned multiplication on absolute values.
911 using U = std::make_unsigned_t<T>;
912 const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X);
913 const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y);
914 const U UResult = UX * UY;
915
916 // Convert to signed.
917 const bool IsNegative = (X < 0) ^ (Y < 0);
918 Result = IsNegative ? (0 - UResult) : UResult;
919
920 // If any of the args was 0, result is 0 and no overflow occurs.
921 if (UX == 0 || UY == 0)
922 return false;
923
924 // UX and UY are in [1, 2^n], where n is the number of digits.
925 // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
926 // positive) divided by an argument compares to the other.
927 if (IsNegative)
928 return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY;
929 else
930 return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY;
931}
932
933} // End llvm namespace
934
935#endif