MathExtras.h Source File (original) (raw)

13#ifndef LLVM_SUPPORT_MATHEXTRAS_H

14#define LLVM_SUPPORT_MATHEXTRAS_H

19#include

20#include

21#include

22#include

23#include

24#include <type_traits>

26namespace llvm {

32template <typename T, typename U>

34 std::enable_if_t<std::is_integral_v && std::is_integral_v>;

37template <typename T, typename U, typename = enableif_int<T, U>>

39 std::common_type_t<std::make_unsigned_t, std::make_unsigned_t>;

40template <typename T, typename U, typename = enableif_int<T, U>>

42 std::common_type_t<std::make_signed_t, std::make_signed_t>;

63template <typename T, typename = std::enable_if_t<std::is_floating_point_v>>

64inline constexpr T sqrtpi_v = T(0x1.c5bf891b4ef6bP+0);

70constexpr const char *pis = "3.141592653589793238462643383279502884",

71 *inv_pis = "0.318309886183790671537767526745028724";

73}

78 static_assert(std::is_unsigned_v, "Invalid type!");

79 const unsigned Bits = CHAR_BIT * sizeof(T);

80 assert(N <= Bits && "Invalid bit index");

81 if (N == 0)

82 return 0;

83 return T(-1) >> (Bits - N);

84}

103

104

105

106

108#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64

109#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)

110#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)

112#undef R2

113#undef R4

114#undef R6

115};

116

117

119#if __has_builtin(__builtin_bitreverse8)

120 if constexpr (std::is_same_v<T, uint8_t>)

121 return __builtin_bitreverse8(Val);

122#endif

123#if __has_builtin(__builtin_bitreverse16)

124 if constexpr (std::is_same_v<T, uint16_t>)

125 return __builtin_bitreverse16(Val);

126#endif

127#if __has_builtin(__builtin_bitreverse32)

128 if constexpr (std::is_same_v<T, uint32_t>)

129 return __builtin_bitreverse32(Val);

130#endif

131#if __has_builtin(__builtin_bitreverse64)

132 if constexpr (std::is_same_v<T, uint64_t>)

133 return __builtin_bitreverse64(Val);

134#endif

135

136 unsigned char in[sizeof(Val)];

137 unsigned char out[sizeof(Val)];

138 std::memcpy(in, &Val, sizeof(Val));

139 for (unsigned i = 0; i < sizeof(Val); ++i)

141 std::memcpy(&Val, out, sizeof(Val));

142 return Val;

143}

144

145

146

147

148

149

153

154

158

159

163

164

165template constexpr bool isInt(int64_t x) {

166 if constexpr (N == 0)

167 return 0 == x;

168 if constexpr (N == 8)

169 return static_cast<int8_t>(x) == x;

170 if constexpr (N == 16)

171 return static_cast<int16_t>(x) == x;

172 if constexpr (N == 32)

173 return static_cast<int32_t>(x) == x;

174 if constexpr (N < 64)

175 return -(INT64_C(1) << (N - 1)) <= x && x < (INT64_C(1) << (N - 1));

176 (void)x;

177 return true;

178}

179

180

181template <unsigned N, unsigned S>

183 static_assert(S < 64, "isShiftedInt<N, S> with S >= 64 is too much.");

184 static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");

185 return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);

186}

187

188

190 if constexpr (N < 64)

191 return (x >> N) == 0;

192 (void)x;

193 return true;

194}

195

196

197template <unsigned N, unsigned S>

199 static_assert(S < 64, "isShiftedUInt<N, S> with S >= 64 is too much.");

200 static_assert(N + S <= 64,

201 "isShiftedUInt<N, S> with N + S > 64 is too wide.");

202

203 return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);

204}

205

206

208 assert(N <= 64 && "integer width out of range");

209

210

211

212

213

214

215

216

217 if (N == 0)

218 return 0;

220}

221

222

223inline constexpr int64_t minIntN(int64_t N) {

224 assert(N <= 64 && "integer width out of range");

225

226 if (N == 0)

227 return 0;

229}

230

231

232inline constexpr int64_t maxIntN(int64_t N) {

233 assert(N <= 64 && "integer width out of range");

234

235

236

237 if (N == 0)

238 return 0;

239 return (UINT64_C(1) << (N - 1)) - 1;

240}

241

242

244 return N >= 64 || (x >> N) == 0;

245}

246

247

248inline constexpr bool isIntN(unsigned N, int64_t x) {

250}

251

252

253

254

258

259

260

264

265

266

270

271

272

276

277

278

282

283

287

288

289

290

291

292

294 unsigned &MaskLen) {

296 return false;

299 return true;

300}

301

302

303

304

305

307 unsigned &MaskLen) {

309 return false;

312 return true;

313}

314

315

316

321

322template <size_t kValue>

323LLVM_DEPRECATED("Use ConstantLog2 instead", "ConstantLog2")

327

328

329

330

334

335

336

340

341

342

343

347

348

349

353

354

355

356template <typename U, typename V, typename T = common_uint<U, V>>

358

359

360

361

362

363 return (A | B) & (1 + ~(A | B));

364}

365

366

368 return (A | B) & (1 + ~(A | B));

369}

370

371

372

374 A |= (A >> 1);

375 A |= (A >> 2);

376 A |= (A >> 4);

377 A |= (A >> 8);

378 A |= (A >> 16);

379 A |= (A >> 32);

380 return A + 1;

381}

382

383

384

390

391

392

393template <typename U, typename V, typename T = common_uint<U, V>>

395 assert(Denominator && "Division by zero");

396 T Bias = (Numerator != 0);

397 return (Numerator - Bias) / Denominator + Bias;

398}

399

400

402 assert(Denominator && "Division by zero");

403 uint64_t Bias = (Numerator != 0);

404 return (Numerator - Bias) / Denominator + Bias;

405}

406

407

408

409template <typename U, typename V>

411 return Numerator == std::numeric_limits::min() && Denominator == -1;

412}

413

414

415

416template <typename U, typename V, typename T = common_sint<U, V>>

418 assert(Denominator && "Division by zero");

420 "Divide would overflow");

421 if (!Numerator)

422 return 0;

423

424 T Bias = Denominator >= 0 ? 1 : -1;

425 bool SameSign = (Numerator >= 0) == (Denominator >= 0);

426 return SameSign ? (Numerator - Bias) / Denominator + 1

427 : Numerator / Denominator;

428}

429

430

431

432template <typename U, typename V, typename T = common_sint<U, V>>

434 assert(Denominator && "Division by zero");

436 "Divide would overflow");

437 if (!Numerator)

438 return 0;

439

440 T Bias = Denominator >= 0 ? -1 : 1;

441 bool SameSign = (Numerator >= 0) == (Denominator >= 0);

442 return SameSign ? Numerator / Denominator

443 : (Numerator - Bias) / Denominator - 1;

444}

445

446

447

448template <typename U, typename V, typename T = common_sint<U, V>>

449constexpr T mod(U Numerator, V Denominator) {

450 assert(Denominator >= 1 && "Mod by non-positive number");

451 T Mod = Numerator % Denominator;

452 return Mod < 0 ? Mod + Denominator : Mod;

453}

454

455

456

457template <typename U, typename V, typename T = common_uint<U, V>>

459 assert(Denominator && "Division by zero");

460 T Mod = Numerator % Denominator;

461 return (Numerator / Denominator) +

462 (Mod > (static_cast<T>(Denominator) - 1) / 2);

463}

464

465

466

467

468

469

470

471

472

473

474

475

476

477template <typename U, typename V, typename T = common_uint<U, V>>

479 assert(Align != 0u && "Align can't be 0.");

481 return CeilDiv * Align;

482}

483

484

486 assert(Align != 0u && "Align can't be 0.");

488 return CeilDiv * Align;

489}

490

491

492template <typename U, typename V, typename T = common_uint<U, V>>

495 "Align must be a power of 2");

496 T NegAlign = static_cast<T>(0) - Align;

497 return (Value + (Align - 1)) & NegAlign;

498}

499

500

503 "Align must be a power of 2");

505 return (Value + (Align - 1)) & NegAlign;

506}

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522template <typename U, typename V, typename W,

529

530

531

532

533

534template <auto Align, typename V, typename T = common_uint<decltype(Align), V>>

536 static_assert(Align != 0u, "Align must be non-zero");

538 return CeilDiv * Align;

539}

540

541

542

543

544template <typename U, typename V, typename W = uint8_t,

551

552

553

555 static_assert(B <= 32, "Bit width out of range.");

556 if constexpr (B == 0)

557 return 0;

558 return int32_t(X << (32 - B)) >> (32 - B);

559}

560

561

562

564 assert(B <= 32 && "Bit width out of range.");

565 if (B == 0)

566 return 0;

567 return int32_t(X << (32 - B)) >> (32 - B);

568}

569

570

571

573 static_assert(B <= 64, "Bit width out of range.");

574 if constexpr (B == 0)

575 return 0;

576 return int64_t(x << (64 - B)) >> (64 - B);

577}

578

579

580

582 assert(B <= 64 && "Bit width out of range.");

583 if (B == 0)

584 return 0;

585 return int64_t(X << (64 - B)) >> (64 - B);

586}

587

588

589

590

591template <typename T, typename U = std::make_unsigned_t>

593

594 return X < 0 ? -static_cast(X) : X;

595}

596

597

598

599template <typename U, typename V, typename T = common_uint<U, V>>

601 return X > Y ? (X - Y) : (Y - X);

602}

603

604

605

606

607template

608std::enable_if_t<std::is_unsigned_v, T>

610 bool Dummy;

611 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;

612

613 T Z = X + Y;

614 Overflowed = (Z < X || Z < Y);

615 if (Overflowed)

616 return std::numeric_limits::max();

617 else

618 return Z;

619}

620

621

622

623template <class T, class... Ts>

625 Ts... Args) {

626 bool Overflowed = false;

628 if (Overflowed)

629 return SaturatingAdd(std::numeric_limits::max(), T(1), Args...);

631}

632

633

634

635

636template

637std::enable_if_t<std::is_unsigned_v, T>

639 bool Dummy;

640 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;

641

642

643

644

645

646

647 Overflowed = false;

648

649

650

651

653 const T Max = std::numeric_limits::max();

654 int Log2Max = Log2_64(Max);

655 if (Log2Z < Log2Max) {

656 return X * Y;

657 }

658 if (Log2Z > Log2Max) {

659 Overflowed = true;

660 return Max;

661 }

662

663

664

665

666 T Z = (X >> 1) * Y;

667 if (Z & ~(Max >> 1)) {

668 Overflowed = true;

669 return Max;

670 }

671 Z <<= 1;

672 if (X & 1)

674

675 return Z;

676}

677

678

679

680

681

682template

683std::enable_if_t<std::is_unsigned_v, T>

685 bool Dummy;

686 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;

687

689 if (Overflowed)

690 return Product;

691

693}

694

695

697

698

699

700template

702#if __has_builtin(__builtin_add_overflow)

703 return __builtin_add_overflow(X, Y, &Result);

704#else

705

706 using U = std::make_unsigned_t;

707 const U UX = static_cast(X);

708 const U UY = static_cast(Y);

709 const U UResult = UX + UY;

710

711

712 Result = static_cast<T>(UResult);

713

714

715 if (X > 0 && Y > 0)

716 return Result <= 0;

717

718 if (X < 0 && Y < 0)

719 return Result >= 0;

720 return false;

721#endif

722}

723

724

725

726template

728#if __has_builtin(__builtin_sub_overflow)

729 return __builtin_sub_overflow(X, Y, &Result);

730#else

731

732 using U = std::make_unsigned_t;

733 const U UX = static_cast(X);

734 const U UY = static_cast(Y);

735 const U UResult = UX - UY;

736

737

738 Result = static_cast<T>(UResult);

739

740

742 return Result >= 0;

743

744 if (X >= 0 && Y < 0)

745 return Result <= 0;

746 return false;

747#endif

748}

749

750

751

752template

754#if __has_builtin(__builtin_mul_overflow)

755 return __builtin_mul_overflow(X, Y, &Result);

756#else

757

758 using U = std::make_unsigned_t;

759 const U UX = X < 0 ? (0 - static_cast(X)) : static_cast(X);

760 const U UY = Y < 0 ? (0 - static_cast(Y)) : static_cast(Y);

761 const U UResult = UX * UY;

762

763

764 const bool IsNegative = (X < 0) ^ (Y < 0);

765 Result = IsNegative ? (0 - UResult) : UResult;

766

767

768 if (UX == 0 || UY == 0)

769 return false;

770

771

772

773

774 if (IsNegative)

775 return UX > (static_cast(std::numeric_limits::max()) + U(1)) / UY;

776 else

777 return UX > (static_cast(std::numeric_limits::max())) / UY;

778#endif

779}

780

781

782

783#if defined(__i386__) || defined(_M_IX86)

785#else

787#endif

788

789}

790

791#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

#define LLVM_DEPRECATED(MSG, FIX)

This file contains library features backported from future STL versions.

static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

This file implements the C++20 header.

LLVM Value Representation.

constexpr float inv_sqrtpif

Definition MathExtras.h:55

constexpr double sqrtpi

Definition MathExtras.h:65

constexpr float pif

Definition MathExtras.h:53

constexpr float sqrtpif

Definition MathExtras.h:66

constexpr float log10ef

Definition MathExtras.h:52

constexpr float ln10f

Definition MathExtras.h:50

constexpr float phif

Definition MathExtras.h:60

constexpr const char * pis

Definition MathExtras.h:70

constexpr float sqrt3f

Definition MathExtras.h:58

constexpr float log2ef

Definition MathExtras.h:51

constexpr float sqrt2f

Definition MathExtras.h:56

constexpr const char * inv_pis

Definition MathExtras.h:71

constexpr float inv_pif

Definition MathExtras.h:54

constexpr T sqrtpi_v

Definition MathExtras.h:64

constexpr float inv_sqrt2f

Definition MathExtras.h:57

constexpr float egammaf

Definition MathExtras.h:48

constexpr float ln2f

Definition MathExtras.h:49

constexpr float ef

Definition MathExtras.h:47

constexpr float inv_sqrt3f

Definition MathExtras.h:59

This is an optimization pass for GlobalISel generic memory operations.

@ Low

Lower the current thread's priority such that it does not affect foreground tasks significantly.

unsigned Log2_32_Ceil(uint32_t Value)

Return the ceil log base 2 of the specified value, 32 if the value is zero.

Definition MathExtras.h:344

std::enable_if_t< std::is_signed_v< T >, T > MulOverflow(T X, T Y, T &Result)

Multiply two signed integers, computing the two's complement truncated result, returning true if an o...

Definition MathExtras.h:753

constexpr bool divideSignedWouldOverflow(U Numerator, V Denominator)

Definition MathExtras.h:410

LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt mod(const DynamicAPInt &LHS, const DynamicAPInt &RHS)

is always non-negative.

constexpr uint64_t maxUIntN(uint64_t N)

Gets the maximum value for a N-bit unsigned integer.

Definition MathExtras.h:207

constexpr size_t CTLog2()

Definition MathExtras.h:324

constexpr bool isInt(int64_t x)

Checks if an integer fits into the given bit width.

Definition MathExtras.h:165

unsigned Log2_64_Ceil(uint64_t Value)

Return the ceil log base 2 of the specified value, 64 if the value is zero.

Definition MathExtras.h:350

constexpr bool isMask_32(uint32_t Value)

Return true if the argument is a non-empty sequence of ones starting at the least significant bit wit...

Definition MathExtras.h:255

constexpr T divideFloorSigned(U Numerator, V Denominator)

Returns the integer floor(Numerator / Denominator).

Definition MathExtras.h:433

constexpr int64_t minIntN(int64_t N)

Gets the minimum value for a N-bit signed integer.

Definition MathExtras.h:223

constexpr size_t ConstantLog2()

Compile time Log2.

Definition MathExtras.h:317

constexpr T maskLeadingOnes(unsigned N)

Create a bitmask with the N left-most bits set to 1, and all other bits set to 0.

Definition MathExtras.h:88

constexpr bool isUIntN(unsigned N, uint64_t x)

Checks if an unsigned integer fits into the given (dynamic) bit width.

Definition MathExtras.h:243

constexpr T alignDown(U Value, V Align, W Skew=0)

Returns the largest unsigned integer less than or equal to Value and is Skew mod Align.

Definition MathExtras.h:546

constexpr bool isPowerOf2_64(uint64_t Value)

Return true if the argument is a power of two > 0 (64 bit edition.)

Definition MathExtras.h:284

constexpr bool isShiftedMask_32(uint32_t Value)

Return true if the argument contains a non-empty sequence of ones with the remainder zero (32 bit ver...

Definition MathExtras.h:267

constexpr int popcount(T Value) noexcept

Count the number of set bits in a value.

unsigned Log2_64(uint64_t Value)

Return the floor log base 2 of the specified value, -1 if the value is zero.

Definition MathExtras.h:337

uint64_t PowerOf2Ceil(uint64_t A)

Returns the power of two which is greater than or equal to the given value.

Definition MathExtras.h:385

int countr_zero(T Val)

Count number of 0's from the least significant bit to the most stopping at the first 1.

constexpr bool isShiftedMask_64(uint64_t Value)

Return true if the argument contains a non-empty sequence of ones with the remainder zero (64 bit ver...

Definition MathExtras.h:273

constexpr T MinAlign(U A, V B)

A and B are either alignments or offsets.

Definition MathExtras.h:357

constexpr T divideNearest(U Numerator, V Denominator)

Returns (Numerator / Denominator) rounded by round-half-up.

Definition MathExtras.h:458

constexpr bool has_single_bit(T Value) noexcept

unsigned Log2_32(uint32_t Value)

Return the floor log base 2 of the specified value, -1 if the value is zero.

Definition MathExtras.h:331

int countl_zero(T Val)

Count number of 0's from the most significant bit to the least stopping at the first 1.

constexpr bool isPowerOf2_32(uint32_t Value)

Return true if the argument is a power of two > 0.

Definition MathExtras.h:279

constexpr uint32_t Hi_32(uint64_t Value)

Return the high 32 bits of a 64 bit value.

Definition MathExtras.h:150

constexpr T alignToPowerOf2(U Value, V Align)

Will overflow only if result is not representable in T.

Definition MathExtras.h:493

constexpr bool isMask_64(uint64_t Value)

Return true if the argument is a non-empty sequence of ones starting at the least significant bit wit...

Definition MathExtras.h:261

std::enable_if_t< std::is_unsigned_v< T >, T > SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed=nullptr)

Multiply two unsigned integers, X and Y, and add the unsigned integer, A to the product.

Definition MathExtras.h:684

constexpr bool isUInt(uint64_t x)

Checks if an unsigned integer fits into the given bit width.

Definition MathExtras.h:189

std::common_type_t< std::make_unsigned_t< T >, std::make_unsigned_t > common_uint

Definition MathExtras.h:38

constexpr T divideCeilSigned(U Numerator, V Denominator)

Returns the integer ceil(Numerator / Denominator).

Definition MathExtras.h:417

constexpr uint32_t Lo_32(uint64_t Value)

Return the low 32 bits of a 64 bit value.

Definition MathExtras.h:155

constexpr T maskLeadingZeros(unsigned N)

Create a bitmask with the N left-most bits set to 0, and all other bits set to 1.

Definition MathExtras.h:100

@ Mod

The access may modify the value stored in memory.

constexpr T divideCeil(U Numerator, V Denominator)

Returns the integer ceil(Numerator / Denominator).

Definition MathExtras.h:394

LLVM_ABI const float huge_valf

Use this rather than HUGE_VALF; the latter causes warnings on MSVC.

std::enable_if_t< std::is_unsigned_v< T >, T > SaturatingMultiply(T X, T Y, bool *ResultOverflowed=nullptr)

Multiply two unsigned integers, X and Y, of type T.

Definition MathExtras.h:638

constexpr T maskTrailingZeros(unsigned N)

Create a bitmask with the N right-most bits set to 0, and all other bits set to 1.

Definition MathExtras.h:94

std::common_type_t< std::make_signed_t< T >, std::make_signed_t > common_sint

Definition MathExtras.h:41

uint64_t alignTo(uint64_t Size, Align A)

Returns a multiple of A needed to store Size bytes.

constexpr T AbsoluteDifference(U X, V Y)

Subtract two unsigned integers, X and Y, of type T and return the absolute value of the result.

Definition MathExtras.h:600

constexpr U AbsoluteValue(T X)

Return the absolute value of a signed integer, converted to the corresponding unsigned integer type.

Definition MathExtras.h:592

constexpr bool isShiftedInt(int64_t x)

Checks if a signed integer is an N bit number shifted left by S.

Definition MathExtras.h:182

constexpr int64_t maxIntN(int64_t N)

Gets the maximum value for a N-bit signed integer.

Definition MathExtras.h:232

constexpr int32_t SignExtend32(uint32_t X)

Sign-extend the number in the bottom B bits of X to a 32-bit integer.

Definition MathExtras.h:554

constexpr int countr_zero_constexpr(T Val)

Count number of 0's from the least significant bit to the most stopping at the first 1.

constexpr bool isIntN(unsigned N, int64_t x)

Checks if an signed integer fits into the given (dynamic) bit width.

Definition MathExtras.h:248

constexpr T reverseBits(T Val)

Reverse the bits in Val.

Definition MathExtras.h:118

constexpr int64_t SignExtend64(uint64_t x)

Sign-extend the number in the bottom B bits of X to a 64-bit integer.

Definition MathExtras.h:572

std::enable_if_t< std::is_signed_v< T >, T > AddOverflow(T X, T Y, T &Result)

Add two signed integers, computing the two's complement truncated result, returning true if overflow ...

Definition MathExtras.h:701

float stack_float_t

Type to force float point values onto the stack, so that x86 doesn't add hidden precision,...

Definition MathExtras.h:786

std::enable_if_t< std::is_signed_v< T >, T > SubOverflow(T X, T Y, T &Result)

Subtract two signed integers, computing the two's complement truncated result, returning true if an o...

Definition MathExtras.h:727

std::enable_if_t< std::is_integral_v< T > &&std::is_integral_v > enableif_int

Some template parameter helpers to optimize for bitwidth, for functions that take multiple arguments.

Definition MathExtras.h:33

static const unsigned char BitReverseTable256[256]

Macro compressed bit reversal table for 256 bits.

Definition MathExtras.h:107

constexpr T maskTrailingOnes(unsigned N)

Create a bitmask with the N right-most bits set to 1, and all other bits set to 0.

Definition MathExtras.h:77

std::enable_if_t< std::is_unsigned_v< T >, T > SaturatingAdd(T X, T Y, bool *ResultOverflowed=nullptr)

Add two unsigned integers, X and Y, of type T.

Definition MathExtras.h:609

constexpr bool isShiftedUInt(uint64_t x)

Checks if a unsigned integer is an N bit number shifted left by S.

Definition MathExtras.h:198

constexpr uint64_t Make_64(uint32_t High, uint32_t Low)

Make a 64-bit integer from a high / low pair of 32-bit integers.

Definition MathExtras.h:160

constexpr uint64_t NextPowerOf2(uint64_t A)

Returns the next power of two (in 64-bits) that is strictly greater than A.

Definition MathExtras.h:373

This struct is a compact representation of a valid (non-zero power of two) alignment.