MathExtras.h Source File (original) (raw)

13#ifndef LLVM_SUPPORT_MATHEXTRAS_H

14#define LLVM_SUPPORT_MATHEXTRAS_H

18#include

19#include

20#include

21#include

22#include

23#include <type_traits>

25namespace llvm {

31template <typename T, typename U>

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

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

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

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

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

44namespace numbers {

48constexpr double e = 2.7182818284590452354,

49 egamma = .57721566490153286061,

50 ln2 = .69314718055994530942,

51 ln10 = 2.3025850929940456840,

52 log2e = 1.4426950408889634074,

53 log10e = .43429448190325182765,

54 pi = 3.1415926535897932385,

55 inv_pi = .31830988618379067154,

56 sqrtpi = 1.7724538509055160273,

57 inv_sqrtpi = .56418958354775628695,

58 sqrt2 = 1.4142135623730950488,

59 inv_sqrt2 = .70710678118654752440,

60 sqrt3 = 1.7320508075688772935,

61 inv_sqrt3 = .57735026918962576451,

62 phi = 1.6180339887498948482;

63constexpr float ef = 2.71828183F,

64 egammaf = .577215665F,

65 ln2f = .693147181F,

66 ln10f = 2.30258509F,

67 log2ef = 1.44269504F,

68 log10ef = .434294482F,

69 pif = 3.14159265F,

70 inv_pif = .318309886F,

71 sqrtpif = 1.77245385F,

72 inv_sqrtpif = .564189584F,

73 sqrt2f = 1.41421356F,

75 sqrt3f = 1.73205081F,

77 phif = 1.61803399F;

79}

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

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

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

87 if (N == 0)

88 return 0;

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

90}

95 return ~maskTrailingOnes(CHAR_BIT * sizeof(T) - N);

96}

101 return maskLeadingOnes(CHAR_BIT * sizeof(T) - N);

102}

103

104

105

107 return maskTrailingOnes(CHAR_BIT * sizeof(T) - N);

108}

109

110

111

112

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

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

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

118#undef R2

119#undef R4

120#undef R6

121};

122

123

125#if __has_builtin(__builtin_bitreverse8)

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

127 return __builtin_bitreverse8(Val);

128#endif

129#if __has_builtin(__builtin_bitreverse16)

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

131 return __builtin_bitreverse16(Val);

132#endif

133#if __has_builtin(__builtin_bitreverse32)

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

135 return __builtin_bitreverse32(Val);

136#endif

137#if __has_builtin(__builtin_bitreverse64)

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

139 return __builtin_bitreverse64(Val);

140#endif

141

142 unsigned char in[sizeof(Val)];

143 unsigned char out[sizeof(Val)];

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

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

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

148 return Val;

149}

150

151

152

153

154

155

158}

159

160

163}

164

165

168}

169

170

171template constexpr bool isInt(int64_t x) {

172 if constexpr (N == 0)

173 return 0 == x;

174 if constexpr (N == 8)

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

176 if constexpr (N == 16)

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

178 if constexpr (N == 32)

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

180 if constexpr (N < 64)

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

182 (void)x;

183 return true;

184}

185

186

187template <unsigned N, unsigned S>

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

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

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

192}

193

194

196 if constexpr (N == 0)

197 return 0 == x;

198 if constexpr (N == 8)

199 return static_cast<uint8_t>(x) == x;

200 if constexpr (N == 16)

201 return static_cast<uint16_t>(x) == x;

202 if constexpr (N == 32)

203 return static_cast<uint32_t>(x) == x;

204 if constexpr (N < 64)

205 return x < (UINT64_C(1) << (N));

206 (void)x;

207 return true;

208}

209

210

211template <unsigned N, unsigned S>

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

214 static_assert(N + S <= 64,

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

216

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

218}

219

220

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

223

224

225

226

227

228

229

230

231 if (N == 0)

232 return 0;

234}

235

236

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

239

240 if (N == 0)

241 return 0;

242 return UINT64_C(1) + ~(UINT64_C(1) << (N - 1));

243}

244

245

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

248

249

250

251 if (N == 0)

252 return 0;

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

254}

255

256

259}

260

261

262inline bool isIntN(unsigned N, int64_t x) {

264}

265

266

267

268

271}

272

273

274

277}

278

279

280

283}

284

285

286

289}

290

291

292

295}

296

297

300}

301

302

303

304

305

306

308 unsigned &MaskLen) {

310 return false;

313 return true;

314}

315

316

317

318

319

321 unsigned &MaskLen) {

323 return false;

326 return true;

327}

328

329

330

331template <size_t kValue> constexpr size_t CTLog2() {

333 "Value is not a valid power of 2");

334 return 1 + CTLog2<kValue / 2>();

335}

336

337template <> constexpr size_t CTLog2<1>() { return 0; }

338

339

340

341

344}

345

346

347

350}

351

352

353

354

357}

358

359

360

363}

364

365

366

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

369

370

371

372

373

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

375}

376

377

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

380}

381

382

383

385 A |= (A >> 1);

386 A |= (A >> 2);

387 A |= (A >> 4);

388 A |= (A >> 8);

389 A |= (A >> 16);

390 A |= (A >> 32);

391 return A + 1;

392}

393

394

395

398 return 0;

400}

401

402

403

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

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

407 T Bias = (Numerator != 0);

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

409}

410

411

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

414 uint64_t Bias = (Numerator != 0);

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

416}

417

418

419

420template <typename U, typename V>

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

423}

424

425

426

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

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

431 "Divide would overflow");

432 if (!Numerator)

433 return 0;

434

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

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

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

438 : Numerator / Denominator;

439}

440

441

442

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

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

447 "Divide would overflow");

448 if (!Numerator)

449 return 0;

450

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

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

453 return SameSign ? Numerator / Denominator

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

455}

456

457

458

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

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

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

462 T Mod = Numerator % Denominator;

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

464}

465

466

467

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

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

471 T Mod = Numerator % Denominator;

472 return (Numerator / Denominator) +

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

474}

475

476

477

478

479

480

481

482

483

484

485

486

487

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

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

492 return CeilDiv * Align;

493}

494

495

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

499 return CeilDiv * Align;

500}

501

502

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

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

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

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

509}

510

511

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

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

517}

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533template <typename U, typename V, typename W,

534 typename T = common_uint<common_uint<U, V>, W>>

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

539}

540

541

542

543

544

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

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

549 return CeilDiv * Align;

550}

551

552

553

554

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

556 typename T = common_uint<common_uint<U, V>, W>>

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

561}

562

563

564

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

567 if constexpr (B == 0)

568 return 0;

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

570}

571

572

573

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

576 if (B == 0)

577 return 0;

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

579}

580

581

582

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

585 if constexpr (B == 0)

586 return 0;

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

588}

589

590

591

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

594 if (B == 0)

595 return 0;

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

597}

598

599

600

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

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

604}

605

606

607

608

609template

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

612 bool Dummy;

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

614

615 T Z = X + Y;

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

617 if (Overflowed)

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

619 else

620 return Z;

621}

622

623

624

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

627 Ts... Args) {

628 bool Overflowed = false;

630 if (Overflowed)

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

633}

634

635

636

637

638template

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

641 bool Dummy;

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

643

644

645

646

647

648

649 Overflowed = false;

650

651

652

653

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

656 int Log2Max = Log2_64(Max);

657 if (Log2Z < Log2Max) {

658 return X * Y;

659 }

660 if (Log2Z > Log2Max) {

661 Overflowed = true;

662 return Max;

663 }

664

665

666

667

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

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

670 Overflowed = true;

671 return Max;

672 }

673 Z <<= 1;

674 if (X & 1)

676

677 return Z;

678}

679

680

681

682

683

684template

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

687 bool Dummy;

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

689

691 if (Overflowed)

692 return Product;

693

695}

696

697

699

700

701

702template

704#if __has_builtin(__builtin_add_overflow)

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

706#else

707

708 using U = std::make_unsigned_t;

709 const U UX = static_cast(X);

710 const U UY = static_cast(Y);

711 const U UResult = UX + UY;

712

713

714 Result = static_cast<T>(UResult);

715

716

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

718 return Result <= 0;

719

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

721 return Result >= 0;

722 return false;

723#endif

724}

725

726

727

728template

730#if __has_builtin(__builtin_sub_overflow)

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

732#else

733

734 using U = std::make_unsigned_t;

735 const U UX = static_cast(X);

736 const U UY = static_cast(Y);

737 const U UResult = UX - UY;

738

739

740 Result = static_cast<T>(UResult);

741

742

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

744 return Result >= 0;

745

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

747 return Result <= 0;

748 return false;

749#endif

750}

751

752

753

754template

756#if __has_builtin(__builtin_mul_overflow)

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

758#else

759

760 using U = std::make_unsigned_t;

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

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

763 const U UResult = UX * UY;

764

765

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

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

768

769

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

771 return false;

772

773

774

775

776 if (IsNegative)

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

778 else

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

780#endif

781}

782

783

784

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

787#else

789#endif

790

791}

792

793#endif

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

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

static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")

static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file implements the C++20 header.

LLVM Value Representation.

constexpr float inv_sqrtpif

constexpr double inv_sqrt2

constexpr double inv_sqrt3

constexpr double inv_sqrtpi

constexpr float inv_sqrt2f

constexpr float inv_sqrt3f

This is an optimization pass for GlobalISel generic memory operations.

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

float stack_float_t

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

@ 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.

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...

int64_t maxIntN(int64_t N)

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

constexpr bool divideSignedWouldOverflow(U Numerator, V Denominator)

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

is always non-negative.

int popcount(T Value) noexcept

Count the number of set bits in a value.

constexpr size_t CTLog2()

Compile time Log2.

constexpr bool isInt(int64_t x)

Checks if an integer fits into the given bit width.

bool isUIntN(unsigned N, uint64_t x)

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

constexpr size_t CTLog2< 1 >()

unsigned Log2_64_Ceil(uint64_t Value)

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

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...

constexpr T divideFloorSigned(U Numerator, V Denominator)

Returns the integer floor(Numerator / Denominator).

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.

constexpr bool isPowerOf2_64(uint64_t Value)

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

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...

unsigned Log2_64(uint64_t Value)

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

uint64_t PowerOf2Ceil(uint64_t A)

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

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...

constexpr T MinAlign(U A, V B)

A and B are either alignments or offsets.

constexpr T divideNearest(U Numerator, V Denominator)

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

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.

int countl_zero(T Val)

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

T maskLeadingZeros(unsigned N)

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

constexpr bool isPowerOf2_32(uint32_t Value)

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

T maskTrailingOnes(unsigned N)

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

T maskTrailingZeros(unsigned N)

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

constexpr uint32_t Hi_32(uint64_t Value)

Return the high 32 bits of a 64 bit value.

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

constexpr T alignToPowerOf2(U Value, V Align)

Will overflow only if result is not representable in T.

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...

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.

constexpr bool isUInt(uint64_t x)

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

constexpr T divideCeilSigned(U Numerator, V Denominator)

Returns the integer ceil(Numerator / Denominator).

constexpr uint32_t Lo_32(uint64_t Value)

Return the low 32 bits of a 64 bit value.

@ Mod

The access may modify the value stored in memory.

constexpr T divideCeil(U Numerator, V Denominator)

Returns the integer ceil(Numerator / Denominator).

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.

bool isIntN(unsigned N, int64_t x)

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

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.

int64_t minIntN(int64_t N)

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

constexpr bool isShiftedInt(int64_t x)

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

constexpr int32_t SignExtend32(uint32_t X)

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

T maskLeadingOnes(unsigned N)

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

constexpr int64_t SignExtend64(uint64_t x)

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

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 ...

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...

static const unsigned char BitReverseTable256[256]

Macro compressed bit reversal table for 256 bits.

T reverseBits(T Val)

Reverse the bits in Val.

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.

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.

constexpr bool isShiftedUInt(uint64_t x)

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

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.

uint64_t maxUIntN(uint64_t N)

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

constexpr uint64_t NextPowerOf2(uint64_t A)

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

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