KnownBits.cpp Source File (original) (raw)

17#include

19using namespace llvm;

22 unsigned SignBitPosition = Val.getBitWidth() - 1;

25 Zero.setBitVal(SignBitPosition, Val.One[SignBitPosition]);

26 One.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);

28}

31 bool CarryZero, bool CarryOne) {

33 APInt PossibleSumZero = LHS.getMaxValue() + RHS.getMaxValue() + !CarryZero;

34 APInt PossibleSumOne = LHS.getMinValue() + RHS.getMinValue() + CarryOne;

37 APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);

38 APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;

43 APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne;

44 APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;

49 KnownOut.One = std::move(PossibleSumOne) & Known;

50 return KnownOut;

51}

54 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) {

56 return ::computeForAddCarry(

58}

61 const KnownBits &LHS,

62 const KnownBits &RHS) {

63 unsigned BitWidth = LHS.getBitWidth();

67 if (LHS.isUnknown() && RHS.isUnknown())

68 return KnownOut;

70 if (!LHS.isUnknown() && !RHS.isUnknown()) {

71 if (Add) {

74 false);

75 } else {

77 KnownBits NotRHS = RHS;

80 true);

81 }

82 }

85 if (NUW) {

86 if (Add) {

91 if (NSW) {

96 }

98 } else {

101

102

103 if (NSW) {

104

105

108 }

110 }

111 }

112

113 if (NSW) {

116 if (Add) {

117

120 } else {

121

124 }

126

127

131 }

133

137 }

138 }

139

140

143 return KnownOut;

144}

145

147 const KnownBits &Borrow) {

149

150

151

153 return ::computeForAddCarry(LHS, RHS,

156}

157

161 "Illegal sext-in-register");

162

164 return *this;

165

166 unsigned ExtBits = BitWidth - SrcBitWidth;

167 KnownBits Result;

168 Result.One = One << ExtBits;

169 Result.Zero = Zero << ExtBits;

170 Result.One.ashrInPlace(ExtBits);

171 Result.Zero.ashrInPlace(ExtBits);

172 return Result;

173}

174

176

177

179

180

181

182 APInt MaskedVal(Val);

185}

186

187KnownBits KnownBits::umax(const KnownBits &LHS, const KnownBits &RHS) {

188

189

190

191

192 if (LHS.getMinValue().uge(RHS.getMaxValue()))

193 return LHS;

194 if (RHS.getMinValue().uge(LHS.getMaxValue()))

195 return RHS;

196

197

198

199

200 KnownBits L = LHS.makeGE(RHS.getMinValue());

201 KnownBits R = RHS.makeGE(LHS.getMinValue());

202 return L.intersectWith(R);

203}

204

205KnownBits KnownBits::umin(const KnownBits &LHS, const KnownBits &RHS) {

206

207 auto Flip = [](const KnownBits &Val) { return KnownBits(Val.One, Val.Zero); };

208 return Flip(umax(Flip(LHS), Flip(RHS)));

209}

210

211KnownBits KnownBits::smax(const KnownBits &LHS, const KnownBits &RHS) {

212 return flipSignBit(umax(flipSignBit(LHS), flipSignBit(RHS)));

213}

214

215KnownBits KnownBits::smin(const KnownBits &LHS, const KnownBits &RHS) {

216

217 auto Flip = [](const KnownBits &Val) {

218 unsigned SignBitPosition = Val.getBitWidth() - 1;

221 Zero.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);

222 One.setBitVal(SignBitPosition, Val.One[SignBitPosition]);

224 };

225 return Flip(umax(Flip(LHS), Flip(RHS)));

226}

227

228KnownBits KnownBits::abdu(const KnownBits &LHS, const KnownBits &RHS) {

229

230

231 if (LHS.getMinValue().uge(RHS.getMaxValue()))

232 return computeForAddSub(false, false, false, LHS,

233 RHS);

234 if (RHS.getMinValue().uge(LHS.getMaxValue()))

235 return computeForAddSub(false, false, false, RHS,

236 LHS);

237

238

239

240 KnownBits Diff0 =

241 computeForAddSub(false, false, true, LHS, RHS);

242 KnownBits Diff1 =

243 computeForAddSub(false, false, true, RHS, LHS);

245}

246

248

249

250 if (LHS.getSignedMinValue().sge(RHS.getSignedMaxValue()))

251 return computeForAddSub(false, false, false, LHS,

252 RHS);

253 if (RHS.getSignedMinValue().sge(LHS.getSignedMaxValue()))

254 return computeForAddSub(false, false, false, RHS,

255 LHS);

256

257

258

259

260

261

262

263 unsigned SignBitPosition = LHS.getBitWidth() - 1;

264 for (auto Arg : {&LHS, &RHS}) {

265 bool Tmp = Arg->Zero[SignBitPosition];

266 Arg->Zero.setBitVal(SignBitPosition, Arg->One[SignBitPosition]);

267 Arg->One.setBitVal(SignBitPosition, Tmp);

268 }

269

270

271 KnownBits Diff0 =

272 computeForAddSub(false, false, true, LHS, RHS);

273 KnownBits Diff1 =

274 computeForAddSub(false, false, true, RHS, LHS);

276}

277

284

285KnownBits KnownBits::shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW,

286 bool NSW, bool ShAmtNonZero) {

287 unsigned BitWidth = LHS.getBitWidth();

288 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {

289 KnownBits Known;

290 bool ShiftedOutZero, ShiftedOutOne;

291 Known.Zero = LHS.Zero.ushl_ov(ShiftAmt, ShiftedOutZero);

293 Known.One = LHS.One.ushl_ov(ShiftAmt, ShiftedOutOne);

294

295

296 if (NSW) {

297 if (NUW && ShiftAmt != 0)

298

299 ShiftedOutZero = true;

300

301 if (ShiftedOutZero)

303 else if (ShiftedOutOne)

305 }

306 return Known;

307 };

308

309

311 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);

312 if (MinShiftAmount == 0 && ShAmtNonZero)

313 MinShiftAmount = 1;

314 if (LHS.isUnknown()) {

316 if (NUW && NSW && MinShiftAmount != 0)

318 return Known;

319 }

320

321

324 if (NUW && NSW)

325 MaxShiftAmount = std::min(MaxShiftAmount, LHS.countMaxLeadingZeros() - 1);

326 if (NUW)

327 MaxShiftAmount = std::min(MaxShiftAmount, LHS.countMaxLeadingZeros());

328 if (NSW)

329 MaxShiftAmount = std::min(

330 MaxShiftAmount,

331 std::max(LHS.countMaxLeadingZeros(), LHS.countMaxLeadingOnes()) - 1);

332

333

334 if (MinShiftAmount == 0 && MaxShiftAmount == BitWidth - 1 &&

337 if (LHS.isAllOnes())

339 if (NSW) {

340 if (LHS.isNonNegative())

342 if (LHS.isNegative())

344 }

345 return Known;

346 }

347

348

349 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();

350 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();

352 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;

353 ++ShiftAmt) {

354

355 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||

356 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)

357 continue;

358 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));

360 break;

361 }

362

363

366 return Known;

367}

368

370 bool ShAmtNonZero, bool Exact) {

371 unsigned BitWidth = LHS.getBitWidth();

372 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {

373 KnownBits Known = LHS;

374 Known >>= ShiftAmt;

375

377 return Known;

378 };

379

380

382 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);

383 if (MinShiftAmount == 0 && ShAmtNonZero)

384 MinShiftAmount = 1;

385 if (LHS.isUnknown()) {

387 return Known;

388 }

389

390

393

394

395 if (Exact) {

396 unsigned FirstOne = LHS.countMaxTrailingZeros();

397 if (FirstOne < MinShiftAmount) {

398

400 return Known;

401 }

402 MaxShiftAmount = std::min(MaxShiftAmount, FirstOne);

403 }

404

405 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();

406 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();

408 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;

409 ++ShiftAmt) {

410

411 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||

412 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)

413 continue;

414 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));

416 break;

417 }

418

419

422 return Known;

423}

424

426 bool ShAmtNonZero, bool Exact) {

427 unsigned BitWidth = LHS.getBitWidth();

428 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {

429 KnownBits Known = LHS;

432 return Known;

433 };

434

435

437 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);

438 if (MinShiftAmount == 0 && ShAmtNonZero)

439 MinShiftAmount = 1;

440 if (LHS.isUnknown()) {

441 if (MinShiftAmount == BitWidth) {

442

444 return Known;

445 }

446 return Known;

447 }

448

449

452

453

454 if (Exact) {

455 unsigned FirstOne = LHS.countMaxTrailingZeros();

456 if (FirstOne < MinShiftAmount) {

457

459 return Known;

460 }

461 MaxShiftAmount = std::min(MaxShiftAmount, FirstOne);

462 }

463

464 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();

465 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();

467 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;

468 ++ShiftAmt) {

469

470 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||

471 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)

472 continue;

473 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));

475 break;

476 }

477

478

481 return Known;

482}

483

484std::optional KnownBits::eq(const KnownBits &LHS, const KnownBits &RHS) {

485 if (LHS.isConstant() && RHS.isConstant())

486 return std::optional(LHS.getConstant() == RHS.getConstant());

487 if (LHS.One.intersects(RHS.Zero) || RHS.One.intersects(LHS.Zero))

488 return std::optional(false);

489 return std::nullopt;

490}

491

492std::optional KnownBits::ne(const KnownBits &LHS, const KnownBits &RHS) {

493 if (std::optional KnownEQ = eq(LHS, RHS))

494 return std::optional(!*KnownEQ);

495 return std::nullopt;

496}

497

498std::optional KnownBits::ugt(const KnownBits &LHS, const KnownBits &RHS) {

499

500 if (LHS.getMaxValue().ule(RHS.getMinValue()))

501 return std::optional(false);

502

503 if (LHS.getMinValue().ugt(RHS.getMaxValue()))

504 return std::optional(true);

505 return std::nullopt;

506}

507

508std::optional KnownBits::uge(const KnownBits &LHS, const KnownBits &RHS) {

509 if (std::optional IsUGT = ugt(RHS, LHS))

510 return std::optional(!*IsUGT);

511 return std::nullopt;

512}

513

514std::optional KnownBits::ult(const KnownBits &LHS, const KnownBits &RHS) {

515 return ugt(RHS, LHS);

516}

517

518std::optional KnownBits::ule(const KnownBits &LHS, const KnownBits &RHS) {

519 return uge(RHS, LHS);

520}

521

522std::optional KnownBits::sgt(const KnownBits &LHS, const KnownBits &RHS) {

523

524 if (LHS.getSignedMaxValue().sle(RHS.getSignedMinValue()))

525 return std::optional(false);

526

527 if (LHS.getSignedMinValue().sgt(RHS.getSignedMaxValue()))

528 return std::optional(true);

529 return std::nullopt;

530}

531

532std::optional KnownBits::sge(const KnownBits &LHS, const KnownBits &RHS) {

533 if (std::optional KnownSGT = sgt(RHS, LHS))

534 return std::optional(!*KnownSGT);

535 return std::nullopt;

536}

537

538std::optional KnownBits::slt(const KnownBits &LHS, const KnownBits &RHS) {

539 return sgt(RHS, LHS);

540}

541

542std::optional KnownBits::sle(const KnownBits &LHS, const KnownBits &RHS) {

543 return sge(RHS, LHS);

544}

545

547

549 return *this;

550

551

553

554

556 KnownBits Tmp = *this;

557

558

559

560

561 if (IntMinIsPoison && (Zero.popcount() + 2) == getBitWidth())

563

565 false, IntMinIsPoison, false,

567

568

569

570

571

572

573

574

581 }

582

583 } else {

586

588

589 if (MaxTZ == MinTZ && MaxTZ < getBitWidth())

591

592

593

594

595 if (IntMinIsPoison || ( One .isZero() && One .isMinSignedValue())) {

598 }

599 }

600

601 return KnownAbs;

602}

603

607

608

610

611 std::optional Overflow;

612

613

614

615

616 bool MayNegClamp = true;

617 bool MayPosClamp = true;

619

620 if (Add && ((LHS.isNegative() && RHS.isNonNegative()) ||

621 (LHS.isNonNegative() && RHS.isNegative())))

622 Overflow = false;

623 else if ( Add && (((LHS.isNegative() && RHS.isNegative()) ||

624 (LHS.isNonNegative() && RHS.isNonNegative()))))

625 Overflow = false;

626 else {

627

628

631

632

633

634

641 false, UnsignedLHS, UnsignedRHS);

642 if (Add) {

644

645 MayNegClamp = false;

646

647 if (LHS.isNonNegative() && RHS.isNonNegative())

648 Overflow = true;

650

651 MayPosClamp = false;

652

653 if (LHS.isNegative() && RHS.isNegative())

654 Overflow = true;

655 }

656

657 if (LHS.isNegative() || RHS.isNegative())

658 MayPosClamp = false;

659 if (LHS.isNonNegative() || RHS.isNonNegative())

660 MayNegClamp = false;

661 } else {

663

664 MayPosClamp = false;

665

666 if (LHS.isNegative() && RHS.isNonNegative())

667 Overflow = true;

669

670 MayNegClamp = false;

671

672 if (LHS.isNonNegative() && RHS.isNegative())

673 Overflow = true;

674 }

675

676 if (LHS.isNegative() || RHS.isNonNegative())

677 MayPosClamp = false;

678 if (LHS.isNonNegative() || RHS.isNegative())

679 MayNegClamp = false;

680 }

681 }

682

683 if (!MayNegClamp && !MayPosClamp)

684 Overflow = false;

685 } else if (Add) {

686

687 bool Of;

688 (void)LHS.getMaxValue().uadd_ov(RHS.getMaxValue(), Of);

689 if (!Of) {

690 Overflow = false;

691 } else {

692 (void)LHS.getMinValue().uadd_ov(RHS.getMinValue(), Of);

693 if (Of)

694 Overflow = true;

695 }

696 } else {

697

698 bool Of;

699 (void)LHS.getMinValue().usub_ov(RHS.getMaxValue(), Of);

700 if (!Of) {

701 Overflow = false;

702 } else {

703 (void)LHS.getMaxValue().usub_ov(RHS.getMinValue(), Of);

704 if (Of)

705 Overflow = true;

706 }

707 }

708

711

712 if (Overflow) {

713

714 if (!(*Overflow)) {

715

716 return Res;

717 }

718

719

722

724 "We somehow know overflow without knowing input sign");

727 } else if (Add) {

728

730 } else {

731

733 }

734

737 return Res;

738 }

739

740

742

743

744 if (MayPosClamp)

746 if (MayNegClamp)

748 } else if (Add) {

749

750

752 } else {

753

754

756 }

757

758 return Res;

759}

760

773

783

785 return flipSignBit(avgFloorU(flipSignBit(LHS), flipSignBit(RHS)));

786}

787

791

793 return flipSignBit(avgCeilU(flipSignBit(LHS), flipSignBit(RHS)));

794}

795

799

800KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS,

801 bool NoUndefSelfMultiply) {

802 unsigned BitWidth = LHS.getBitWidth();

803 assert(BitWidth == RHS.getBitWidth() && "Operand mismatch");

804 assert((!NoUndefSelfMultiply || LHS == RHS) &&

805 "Self multiplication knownbits mismatch");

806

807

808

809

810

811

814

815

816

817 bool HasOverflow;

818 APInt UMaxResult = UMaxLHS.umul_ov(UMaxRHS, HasOverflow);

819 unsigned LeadZ = HasOverflow ? 0 : UMaxResult.countl_zero();

820

821

822

823

824

825

826

827

828

829

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863 const APInt &Bottom0 = LHS.One;

864 const APInt &Bottom1 = RHS.One;

865

866

867

868 unsigned TrailBitsKnown0 = (LHS.Zero | LHS.One).countr_one();

869 unsigned TrailBitsKnown1 = (RHS.Zero | RHS.One).countr_one();

870 unsigned TrailZero0 = LHS.countMinTrailingZeros();

871 unsigned TrailZero1 = RHS.countMinTrailingZeros();

872 unsigned TrailZ = TrailZero0 + TrailZero1;

873

874

875 unsigned SmallestOperand =

876 std::min(TrailBitsKnown0 - TrailZero0, TrailBitsKnown1 - TrailZero1);

877 unsigned ResultBitsKnown = std::min(SmallestOperand + TrailZ, BitWidth);

878

879 APInt BottomKnown =

880 Bottom0.getLoBits(TrailBitsKnown0) * Bottom1.getLoBits(TrailBitsKnown1);

881

884 Res.Zero |= (~BottomKnown).getLoBits(ResultBitsKnown);

885 Res.One = BottomKnown.getLoBits(ResultBitsKnown);

886

887 if (NoUndefSelfMultiply) {

888

889 unsigned TwoTZP1 = 2 * TrailZero0 + 1;

892

893

894

895 if (TrailZero0 < BitWidth && LHS.One[TrailZero0]) {

896 unsigned TwoTZP2 = TwoTZP1 + 1;

899 }

900 }

901

902 return Res;

903}

904

906 unsigned BitWidth = LHS.getBitWidth();

907 assert(BitWidth == RHS.getBitWidth() && "Operand mismatch");

908 KnownBits WideLHS = LHS.sext(2 * BitWidth);

909 KnownBits WideRHS = RHS.sext(2 * BitWidth);

911}

912

914 unsigned BitWidth = LHS.getBitWidth();

915 assert(BitWidth == RHS.getBitWidth() && "Operand mismatch");

916 KnownBits WideLHS = LHS.zext(2 * BitWidth);

917 KnownBits WideRHS = RHS.zext(2 * BitWidth);

919}

920

923

924 if (!Exact)

925 return Known;

926

927

928

929

930 if (LHS.One[0])

932

933 int MinTZ =

934 (int)LHS.countMinTrailingZeros() - (int)RHS.countMaxTrailingZeros();

935 int MaxTZ =

936 (int)LHS.countMaxTrailingZeros() - (int)RHS.countMinTrailingZeros();

937 if (MinTZ >= 0) {

938

940 if (MinTZ == MaxTZ) {

941

943 }

944 } else if (MaxTZ < 0) {

945

947 }

948

949

950

953

954 return Known;

955}

956

958 bool Exact) {

959

960 if (LHS.isNonNegative() && RHS.isNonNegative())

961 return udiv(LHS, RHS, Exact);

962

963 unsigned BitWidth = LHS.getBitWidth();

965

966 if (LHS.isZero() || RHS.isZero()) {

967

968

970 return Known;

971 }

972

973 std::optional Res;

974 if (LHS.isNegative() && RHS.isNegative()) {

975

978

979

982 : Num.sdiv(Denom);

983 } else if (LHS.isNegative() && RHS.isNonNegative()) {

984

985 if (Exact || (-LHS.getSignedMaxValue()).uge(RHS.getSignedMaxValue())) {

988 Res = Denom.isZero() ? Num : Num.sdiv(Denom);

989 }

990 } else if (LHS.isStrictlyPositive() && RHS.isNegative()) {

991

992 if (Exact || LHS.getSignedMinValue().uge(-RHS.getSignedMinValue())) {

995 Res = Num.sdiv(Denom);

996 }

997 }

998

999 if (Res) {

1000 if (Res->isNonNegative()) {

1001 unsigned LeadZ = Res->countLeadingZeros();

1003 } else {

1004 unsigned LeadO = Res->countLeadingOnes();

1006 }

1007 }

1008

1010 return Known;

1011}

1012

1014 bool Exact) {

1015 unsigned BitWidth = LHS.getBitWidth();

1017

1018 if (LHS.isZero() || RHS.isZero()) {

1019

1020

1022 return Known;

1023 }

1024

1025

1026

1027

1030 APInt MaxRes = MinDenom.isZero() ? MaxNum : MaxNum.udiv(MinDenom);

1031

1033

1036

1037 return Known;

1038}

1039

1041 unsigned BitWidth = LHS.getBitWidth();

1042 if (!RHS.isZero() && RHS.Zero[0]) {

1043

1044 unsigned RHSZeros = RHS.countMinTrailingZeros();

1046 APInt OnesMask = LHS.One & Mask;

1047 APInt ZerosMask = LHS.Zero & Mask;

1048 return KnownBits(ZerosMask, OnesMask);

1049 }

1051}

1052

1054 KnownBits Known = remGetLowBits(LHS, RHS);

1055 if (RHS.isConstant() && RHS.getConstant().isPowerOf2()) {

1056

1057 APInt HighBits = ~(RHS.getConstant() - 1);

1058 Known.Zero |= HighBits;

1059 return Known;

1060 }

1061

1062

1063

1065 std::max(LHS.countMinLeadingZeros(), RHS.countMinLeadingZeros());

1067 return Known;

1068}

1069

1071 KnownBits Known = remGetLowBits(LHS, RHS);

1072 if (RHS.isConstant() && RHS.getConstant().isPowerOf2()) {

1073

1074 APInt LowBits = RHS.getConstant() - 1;

1075

1076

1077 if (LHS.isNonNegative() || LowBits.isSubsetOf(LHS.Zero))

1078 Known.Zero |= ~LowBits;

1079

1080

1081

1082 if (LHS.isNegative() && LowBits.intersects(LHS.One))

1083 Known.One |= ~LowBits;

1084 return Known;

1085 }

1086

1087

1088

1089

1090 if (LHS.isNegative() && Known.isNonZero())

1092 std::max(LHS.countMinLeadingOnes(), RHS.countMinSignBits()));

1093 else if (LHS.isNonNegative())

1095 std::max(LHS.countMinLeadingZeros(), RHS.countMinSignBits()));

1096 return Known;

1097}

1098

1100

1101 Zero |= RHS.Zero;

1102

1103 One &= RHS.One;

1104 return *this;

1105}

1106

1108

1109 Zero &= RHS.Zero;

1110

1111 One |= RHS.One;

1112 return *this;

1113}

1114

1116

1117 APInt Z = (Zero & RHS.Zero) | (One & RHS.One);

1118

1119 One = (Zero & RHS.One) | (One & RHS.Zero);

1120 Zero = std::move(Z);

1121 return *this;

1122}

1123

1130 if (Max == Min && Max < BitWidth)

1132 return Known;

1133}

1134

1144

1147 for (unsigned I = 0; I < BitWidth; ++I) {

1150 OS << "!";

1151 else if (Zero[N])

1152 OS << "0";

1153 else if (One[N])

1154 OS << "1";

1155 else

1156 OS << "?";

1157 }

1158}

1159

1160#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

1163 dbgs() << "\n";

1164}

1165#endif

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

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

static KnownBits avgComputeU(KnownBits LHS, KnownBits RHS, bool IsCeil)

Definition KnownBits.cpp:774

static KnownBits computeForSatAddSub(bool Add, bool Signed, const KnownBits &LHS, const KnownBits &RHS)

Definition KnownBits.cpp:604

static KnownBits divComputeLowBit(KnownBits Known, const KnownBits &LHS, const KnownBits &RHS, bool Exact)

Definition KnownBits.cpp:921

static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)

Definition KnownBits.cpp:30

static unsigned getMaxShiftAmount(const APInt &MaxValue, unsigned BitWidth)

Definition KnownBits.cpp:278

Class for arbitrary precision integers.

LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const

LLVM_ABI APInt usub_sat(const APInt &RHS) const

LLVM_ABI APInt udiv(const APInt &RHS) const

Unsigned division operation.

LLVM_ABI APInt getLoBits(unsigned numBits) const

Compute an APInt containing numBits lowbits from this APInt.

bool isMinSignedValue() const

Determine if this is the smallest signed value.

void setHighBits(unsigned hiBits)

Set the top hiBits bits.

void setBitsFrom(unsigned loBit)

Set the top bits starting from loBit.

LLVM_ABI uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const

LLVM_ABI APInt trunc(unsigned width) const

Truncate to new width.

static APInt getMaxValue(unsigned numBits)

Gets maximum unsigned value of APInt for specific bit width.

void setBit(unsigned BitPosition)

Set the given bit to 1 whose position is given as "bitPosition".

LLVM_ABI APInt sadd_sat(const APInt &RHS) const

bool isAllOnes() const

Determine if all bits are set. This is true for zero-width values.

bool isZero() const

Determine if this value is zero, i.e. all bits are clear.

void setSignBit()

Set the sign bit to 1.

static APInt getSignedMaxValue(unsigned numBits)

Gets maximum signed value of APInt for a specific bit width.

static APInt getMinValue(unsigned numBits)

Gets minimum unsigned value of APInt for a specific bit width.

bool isNegative() const

Determine sign of this APInt.

bool intersects(const APInt &RHS) const

This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...

LLVM_ABI APInt sdiv(const APInt &RHS) const

Signed division function for APInt.

void clearAllBits()

Set every bit to 0.

void ashrInPlace(unsigned ShiftAmt)

Arithmetic right-shift this APInt by ShiftAmt in place.

unsigned countl_zero() const

The APInt version of std::countl_zero.

static APInt getSignedMinValue(unsigned numBits)

Gets minimum signed value of APInt for a specific bit width.

LLVM_ABI APInt ushl_ov(const APInt &Amt, bool &Overflow) const

unsigned countLeadingZeros() const

unsigned countl_one() const

Count the number of leading one bits.

void clearLowBits(unsigned loBits)

Set bottom loBits bits to 0.

uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const

If this value is smaller than the specified limit, return it, otherwise return the limit value.

LLVM_ABI APInt uadd_sat(const APInt &RHS) const

bool getBoolValue() const

Convert APInt to a boolean value.

bool isNonNegative() const

Determine if this APInt Value is non-negative (>= 0)

void setBits(unsigned loBit, unsigned hiBit)

Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.

bool isSubsetOf(const APInt &RHS) const

This operation checks that all bits set in this APInt are also set in RHS.

static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)

Constructs an APInt value that has the bottom loBitsSet bits set.

void setLowBits(unsigned loBits)

Set the bottom loBits bits.

void clearSignBit()

Set the sign bit to 0.

LLVM_ABI APInt ssub_sat(const APInt &RHS) const

This class implements an extremely fast bulk output stream that can only output to a stream.

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

int countr_one(T Value)

Count the number of ones from the least significant bit to the first zero bit.

unsigned Log2_32(uint32_t Value)

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

constexpr bool isPowerOf2_32(uint32_t Value)

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

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

int countl_one(T Value)

Count the number of ones from the most significant bit to the first zero bit.

constexpr unsigned BitWidth

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

Implement std::hash so that hash_code can be used in STL containers.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

static KnownBits makeConstant(const APInt &C)

Create known bits from a known constant.

static LLVM_ABI KnownBits sadd_sat(const KnownBits &LHS, const KnownBits &RHS)

Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)

Definition KnownBits.cpp:761

static LLVM_ABI std::optional< bool > eq(const KnownBits &LHS, const KnownBits &RHS)

Determine if these known bits always give the same ICMP_EQ result.

Definition KnownBits.cpp:484

LLVM_ABI KnownBits sextInReg(unsigned SrcBitWidth) const

Return known bits for a in-register sign extension of the value we're tracking.

Definition KnownBits.cpp:158

static LLVM_ABI KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS)

Compute known bits from zero-extended multiply-hi.

Definition KnownBits.cpp:913

static LLVM_ABI KnownBits smax(const KnownBits &LHS, const KnownBits &RHS)

Compute known bits for smax(LHS, RHS).

Definition KnownBits.cpp:211

bool isNonNegative() const

Returns true if this value is known to be non-negative.

LLVM_ABI KnownBits blsi() const

Compute known bits for X & -X, which has only the lowest bit set of X set.

Definition KnownBits.cpp:1124

void makeNonNegative()

Make this value non-negative.

static LLVM_ABI KnownBits usub_sat(const KnownBits &LHS, const KnownBits &RHS)

Compute knownbits resulting from llvm.usub.sat(LHS, RHS)

Definition KnownBits.cpp:770

unsigned countMinTrailingZeros() const

Returns the minimum number of trailing zero bits.

static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)

Compute known bits for ashr(LHS, RHS).

Definition KnownBits.cpp:425

static LLVM_ABI KnownBits ssub_sat(const KnownBits &LHS, const KnownBits &RHS)

Compute knownbits resulting from llvm.ssub.sat(LHS, RHS)

Definition KnownBits.cpp:764

static LLVM_ABI KnownBits urem(const KnownBits &LHS, const KnownBits &RHS)

Compute known bits for urem(LHS, RHS).

Definition KnownBits.cpp:1053

bool isUnknown() const

Returns true if we don't know any bits.

unsigned countMaxTrailingZeros() const

Returns the maximum number of trailing zero bits possible.

static LLVM_ABI std::optional< bool > ne(const KnownBits &LHS, const KnownBits &RHS)

Determine if these known bits always give the same ICMP_NE result.

Definition KnownBits.cpp:492

LLVM_ABI KnownBits makeGE(const APInt &Val) const

Return KnownBits based on this, but updated given that the underlying value is known to be greater th...

Definition KnownBits.cpp:175

LLVM_ABI KnownBits blsmsk() const

Compute known bits for X ^ (X - 1), which has all bits up to and including the lowest set bit of X se...

Definition KnownBits.cpp:1135

void makeNegative()

Make this value negative.

void setAllConflict()

Make all bits known to be both zero and one.

bool hasConflict() const

Returns true if there is conflicting information.

static LLVM_ABI std::optional< bool > sge(const KnownBits &LHS, const KnownBits &RHS)

Determine if these known bits always give the same ICMP_SGE result.

Definition KnownBits.cpp:532

unsigned countMaxPopulation() const

Returns the maximum number of bits that could be one.

void setAllZero()

Make all bits known to be zero and discard any previous information.

LLVM_ABI KnownBits & operator|=(const KnownBits &RHS)

Update known bits based on ORing with RHS.

Definition KnownBits.cpp:1107

LLVM_ABI void print(raw_ostream &OS) const

Definition KnownBits.cpp:1145

unsigned getBitWidth() const

Get the bit width of this value.

static LLVM_ABI KnownBits umax(const KnownBits &LHS, const KnownBits &RHS)

Compute known bits for umax(LHS, RHS).

Definition KnownBits.cpp:187

LLVM_DUMP_METHOD void dump() const

Definition KnownBits.cpp:1161

static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)

Compute known bits for lshr(LHS, RHS).

Definition KnownBits.cpp:369

bool isNonZero() const

Returns true if this value is known to be non-zero.

static LLVM_ABI KnownBits abdu(const KnownBits &LHS, const KnownBits &RHS)

Compute known bits for abdu(LHS, RHS).

Definition KnownBits.cpp:228

KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const

Return a subset of the known bits from [bitPosition,bitPosition+numBits).

static LLVM_ABI KnownBits avgFloorU(const KnownBits &LHS, const KnownBits &RHS)

Compute knownbits resulting from APIntOps::avgFloorU.

Definition KnownBits.cpp:788

KnownBits intersectWith(const KnownBits &RHS) const

Returns KnownBits information that is known to be true for both this and RHS.

static LLVM_ABI KnownBits computeForSubBorrow(const KnownBits &LHS, KnownBits RHS, const KnownBits &Borrow)

Compute known bits results from subtracting RHS from LHS with 1-bit Borrow.

Definition KnownBits.cpp:146

unsigned countMinLeadingZeros() const

Returns the minimum number of leading zero bits.

static LLVM_ABI KnownBits abds(KnownBits LHS, KnownBits RHS)

Compute known bits for abds(LHS, RHS).

Definition KnownBits.cpp:247

static LLVM_ABI KnownBits smin(const KnownBits &LHS, const KnownBits &RHS)

Compute known bits for smin(LHS, RHS).

Definition KnownBits.cpp:215

LLVM_ABI KnownBits & operator&=(const KnownBits &RHS)

Update known bits based on ANDing with RHS.

Definition KnownBits.cpp:1099

static LLVM_ABI KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS)

Compute known bits from sign-extended multiply-hi.

Definition KnownBits.cpp:905

static LLVM_ABI KnownBits srem(const KnownBits &LHS, const KnownBits &RHS)

Compute known bits for srem(LHS, RHS).

Definition KnownBits.cpp:1070

static LLVM_ABI std::optional< bool > ugt(const KnownBits &LHS, const KnownBits &RHS)

Determine if these known bits always give the same ICMP_UGT result.

Definition KnownBits.cpp:498

static LLVM_ABI KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)

Compute known bits for udiv(LHS, RHS).

Definition KnownBits.cpp:1013

static LLVM_ABI std::optional< bool > slt(const KnownBits &LHS, const KnownBits &RHS)

Determine if these known bits always give the same ICMP_SLT result.

Definition KnownBits.cpp:538

static LLVM_ABI KnownBits computeForAddSub(bool Add, bool NSW, bool NUW, const KnownBits &LHS, const KnownBits &RHS)

Compute known bits resulting from adding LHS and RHS.

Definition KnownBits.cpp:60

static LLVM_ABI KnownBits sdiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)

Compute known bits for sdiv(LHS, RHS).

Definition KnownBits.cpp:957

static LLVM_ABI std::optional< bool > ult(const KnownBits &LHS, const KnownBits &RHS)

Determine if these known bits always give the same ICMP_ULT result.

Definition KnownBits.cpp:514

static LLVM_ABI KnownBits avgFloorS(const KnownBits &LHS, const KnownBits &RHS)

Compute knownbits resulting from APIntOps::avgFloorS.

Definition KnownBits.cpp:784

static LLVM_ABI std::optional< bool > ule(const KnownBits &LHS, const KnownBits &RHS)

Determine if these known bits always give the same ICMP_ULE result.

Definition KnownBits.cpp:518

bool isNegative() const

Returns true if this value is known to be negative.

static LLVM_ABI KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry)

Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.

Definition KnownBits.cpp:53

static LLVM_ABI KnownBits avgCeilU(const KnownBits &LHS, const KnownBits &RHS)

Compute knownbits resulting from APIntOps::avgCeilU.

Definition KnownBits.cpp:796

static LLVM_ABI KnownBits uadd_sat(const KnownBits &LHS, const KnownBits &RHS)

Compute knownbits resulting from llvm.uadd.sat(LHS, RHS)

Definition KnownBits.cpp:767

static LLVM_ABI KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NoUndefSelfMultiply=false)

Compute known bits resulting from multiplying LHS and RHS.

Definition KnownBits.cpp:800

LLVM_ABI KnownBits abs(bool IntMinIsPoison=false) const

Compute known bits for the absolute value.

Definition KnownBits.cpp:546

static LLVM_ABI std::optional< bool > sle(const KnownBits &LHS, const KnownBits &RHS)

Determine if these known bits always give the same ICMP_SLE result.

Definition KnownBits.cpp:542

static LLVM_ABI std::optional< bool > sgt(const KnownBits &LHS, const KnownBits &RHS)

Determine if these known bits always give the same ICMP_SGT result.

Definition KnownBits.cpp:522

unsigned countMinPopulation() const

Returns the number of bits known to be one.

static LLVM_ABI std::optional< bool > uge(const KnownBits &LHS, const KnownBits &RHS)

Determine if these known bits always give the same ICMP_UGE result.

Definition KnownBits.cpp:508

LLVM_ABI KnownBits & operator^=(const KnownBits &RHS)

Update known bits based on XORing with RHS.

Definition KnownBits.cpp:1115

static LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)

Compute known bits for shl(LHS, RHS).

Definition KnownBits.cpp:285

static LLVM_ABI KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)

Compute known bits for umin(LHS, RHS).

Definition KnownBits.cpp:205

static LLVM_ABI KnownBits avgCeilS(const KnownBits &LHS, const KnownBits &RHS)

Compute knownbits resulting from APIntOps::avgCeilS.

Definition KnownBits.cpp:792