AArch64ExpandImm.cpp Source File (original) (raw)

17using namespace llvm;

23 assert(ChunkIdx < 4 && "Out of range chunk index specified!");

25 return (Imm >> (ChunkIdx * 16)) & 0xFFFF;

26}

31 Chunk = (Chunk << 48) | (Chunk << 32) | (Chunk << 16) | Chunk;

34}

47 CountMap Counts;

50 for (unsigned Idx = 0; Idx < 4; ++Idx)

51 ++Counts[getChunk(UImm, Idx)];

54 for (const auto &Chunk : Counts) {

55 const uint64_t ChunkVal = Chunk.first;

56 const unsigned Count = Chunk.second;

63 continue;

65 const bool CountThree = Count == 3;

67 Insn.push_back({ AArch64::ORRXri, 0, Encoding });

69 unsigned ShiftAmt = 0;

72 for (; ShiftAmt < 64; ShiftAmt += 16) {

73 Imm16 = (UImm >> ShiftAmt) & 0xFFFF;

75 if (Imm16 != ChunkVal)

76 break;

77 }

80 Insn.push_back({ AArch64::MOVKXi, Imm16,

85 if (CountThree)

86 return true;

89 for (ShiftAmt += 16; ShiftAmt < 64; ShiftAmt += 16) {

90 Imm16 = (UImm >> ShiftAmt) & 0xFFFF;

92 if (Imm16 != ChunkVal)

93 break;

94 }

95 Insn.push_back({ AArch64::MOVKXi, Imm16,

97 return true;

98 }

100 return false;

101}

102

103

104

105

107 if (Chunk == 0 || Chunk == std::numeric_limits<uint64_t>::max())

108 return false;

109

111}

112

113

114

115

117 if (Chunk == 0 || Chunk == std::numeric_limits<uint64_t>::max())

118 return false;

119

121}

122

123

125 const uint64_t Mask = 0xFFFF;

126

127 if (Clear)

128

129 Imm &= ~(Mask << (Idx * 16));

130 else

131

132 Imm |= Mask << (Idx * 16);

133

134 return Imm;

135}

136

137

138

139

140

141

142

143

144

145

146

147

148

149

152 const int NotSet = -1;

153 const uint64_t Mask = 0xFFFF;

154

155 int StartIdx = NotSet;

156 int EndIdx = NotSet;

157

158 for (int Idx = 0; Idx < 4; ++Idx) {

159 int64_t Chunk = getChunk(UImm, Idx);

160

161 Chunk = (Chunk << 48) >> 48;

162

164 StartIdx = Idx;

166 EndIdx = Idx;

167 }

168

169

170 if (StartIdx == NotSet || EndIdx == NotSet)

171 return false;

172

173

175

177

178

179

180

181 if (StartIdx > EndIdx) {

184 }

185

187 int FirstMovkIdx = NotSet;

188 int SecondMovkIdx = NotSet;

189

190

191

192 for (int Idx = 0; Idx < 4; ++Idx) {

194

195

196

197 if ((Idx < StartIdx || EndIdx < Idx) && Chunk != Outside) {

198 OrrImm = updateImm(OrrImm, Idx, Outside == 0);

199

200

201 if (FirstMovkIdx == NotSet)

202 FirstMovkIdx = Idx;

203 else

204 SecondMovkIdx = Idx;

205

206

207

208 } else if (Idx > StartIdx && Idx < EndIdx && Chunk != Inside) {

209 OrrImm = updateImm(OrrImm, Idx, Inside != Mask);

210

211

212 if (FirstMovkIdx == NotSet)

213 FirstMovkIdx = Idx;

214 else

215 SecondMovkIdx = Idx;

216 }

217 }

218 assert(FirstMovkIdx != NotSet && "Constant materializable with single ORR!");

219

220

223 Insn.push_back({ AArch64::ORRXri, 0, Encoding });

224

225 const bool SingleMovk = SecondMovkIdx == NotSet;

228 FirstMovkIdx * 16) });

229

230

231 if (SingleMovk)

232 return true;

233

234

237 SecondMovkIdx * 16) });

238

239 return true;

240}

241

244

246 if (NumOnes == 64) {

247 UnshiftedOnes = ~0ULL;

248 } else {

249 UnshiftedOnes = (1ULL << NumOnes) - 1;

250 }

251 return UnshiftedOnes << StartPosition;

252}

253

256

257

258 for (uint64_t i = 0; i < 6; ++i) {

259 uint64_t Rotation = 1ULL << (6 - i);

261 if (Closure != (Closure & V)) {

262 break;

263 }

264 Result = Closure;

265 }

266

267 return Result;

268}

269

270

271

274

276

277

279

280

281

283

284 return MaximalImm;

285}

286

287static std::optional<std::pair<uint64_t, uint64_t>>

289 if (UImm == 0 || ~UImm == 0)

290 return std::nullopt;

291

292

295

296

298

299

300 uint64_t RemainingBits = RotatedBits & ~MaximalImm1;

301

302

303

305

306

307 if (RemainingBits & ~MaximalImm2)

308 return std::nullopt;

309

310

311 return std::make_pair(rotl(MaximalImm1, InitialTrailingOnes),

312 rotl(MaximalImm2, InitialTrailingOnes));

313}

314

315

319 if (MaybeDecomposition == std::nullopt)

320 return false;

321 uint64_t Imm1 = MaybeDecomposition->first;

322 uint64_t Imm2 = MaybeDecomposition->second;

323

324 uint64_t Encoding1, Encoding2;

327

328 if (Imm1Success && Imm2Success) {

329

330 Insn.push_back({AArch64::ORRXri, 0, Encoding1});

331 Insn.push_back({AArch64::ORRXri, 1, Encoding2});

332 return true;

333 }

334

335 return false;

336}

337

338

339

340

343

345 if (MaybeDecomposition == std::nullopt)

346 return false;

347 uint64_t Imm1 = MaybeDecomposition->first;

348 uint64_t Imm2 = MaybeDecomposition->second;

349

350 uint64_t Encoding1, Encoding2;

353

354 if (Imm1Success && Imm2Success) {

355

356 Insn.push_back({AArch64::ORRXri, 0, Encoding1});

357

358 Insn.push_back({AArch64::ANDXri, 1, Encoding2});

359 return true;

360 }

361

362 return false;

363}

364

365

366

367

368

369

370

371

372

375

376

377 unsigned BigSize = 64;

378

379 do {

380 BigSize /= 2;

381 uint64_t Mask = (1ULL << BigSize) - 1;

382

383 if ((Imm & Mask) != ((Imm >> BigSize) & Mask)) {

384 BigSize *= 2;

385 break;

386 }

387 } while (BigSize > 2);

388

390

391

392

393

395

396

397

398

399

400

401 int RunsPerBigChunk = popcount(RunStarts & BigMask);

402

403 static const int8_t BigToSmallSizeTable[32] = {

404 -1, -1, 0, 1, 2, 2, -1, 3, 3, 3, -1, -1, -1, -1, -1, 4,

405 4, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 5,

406 };

407

408 int BigToSmallShift = BigToSmallSizeTable[RunsPerBigChunk];

409

410

411

412 if (BigToSmallShift == -1)

413 return false;

414

415 unsigned SmallSize = BigSize >> BigToSmallShift;

416

417

418 static const uint64_t RepeatedOnesTable[] = {

419 0xffffffffffffffff, 0x5555555555555555, 0x1111111111111111,

420 0x0101010101010101, 0x0001000100010001, 0x0000000100000001,

421 0x0000000000000001,

422 };

423

424

425

426

427

429

430

431

432

433

434

437 for (int Attempt = 0; Attempt < 3; ++Attempt) {

438 unsigned RunLength = countr_one(RotatedImm);

439

440

441

442

444 rotl<uint64_t>((SmallOnes << RunLength) - SmallOnes, Rotation);

445 uint64_t BigImm = Imm ^ SmallImm;

446

451 Insn.push_back({AArch64::ORRXri, 0, SmallEncoding});

452 Insn.push_back({AArch64::EORXri, 1, BigEncoding});

453 return true;

454 }

455

456

459 }

460

461 return false;

462}

463

464

465

467 unsigned OneChunks, unsigned ZeroChunks,

469 const unsigned Mask = 0xFFFF;

470

471

472

473

474 bool isNeg = false;

475

476

477

478 if (OneChunks > ZeroChunks) {

480 Imm = ~Imm;

481 }

482

483 unsigned FirstOpc;

484 if (BitSize == 32) {

485 Imm &= (1LL << 32) - 1;

486 FirstOpc = (isNeg ? AArch64::MOVNWi : AArch64::MOVZWi);

487 } else {

488 FirstOpc = (isNeg ? AArch64::MOVNXi : AArch64::MOVZXi);

489 }

490 unsigned Shift = 0;

491 unsigned LastShift = 0;

492 if (Imm != 0) {

495 Shift = (TZ / 16) * 16;

496 LastShift = ((63 - LZ) / 16) * 16;

497 }

498 unsigned Imm16 = (Imm >> Shift) & Mask;

499

500 Insn.push_back({ FirstOpc, Imm16,

502

503 if (Shift == LastShift)

504 return;

505

506

507

509 Imm = ~Imm;

510

511 unsigned Opc = (BitSize == 32 ? AArch64::MOVKWi : AArch64::MOVKXi);

512 while (Shift < LastShift) {

513 Shift += 16;

514 Imm16 = (Imm >> Shift) & Mask;

515 if (Imm16 == (isNeg ? Mask : 0))

516 continue;

517

520 }

521

522

523

524 if (Insn.size() > 2 && (Imm >> 32) == (Imm & 0xffffffffULL)) {

527 Insn.push_back({AArch64::ORRXrs, 0, 32});

528 }

529}

530

531

532

535 const unsigned Mask = 0xFFFF;

536

537

538

539 unsigned OneChunks = 0;

540 unsigned ZeroChunks = 0;

541 for (unsigned Shift = 0; Shift < BitSize; Shift += 16) {

542 const unsigned Chunk = (Imm >> Shift) & Mask;

543 if (Chunk == Mask)

544 OneChunks++;

545 else if (Chunk == 0)

546 ZeroChunks++;

547 }

548

549

550 if ((BitSize / 16) - OneChunks <= 1 || (BitSize / 16) - ZeroChunks <= 1) {

553 "Move of immediate should have expanded to a single MOVZ/MOVN");

554 return;

555 }

556

557

558 uint64_t UImm = Imm << (64 - BitSize) >> (64 - BitSize);

561 unsigned Opc = (BitSize == 32 ? AArch64::ORRWri : AArch64::ORRXri);

563 return;

564 }

565

566

567

568

569

570 if (OneChunks >= (BitSize / 16) - 2 || ZeroChunks >= (BitSize / 16) - 2) {

572 return;

573 }

574

575 assert(BitSize == 64 && "All 32-bit immediates can be expanded with a"

576 "MOVZ/MOVK pair");

577

578

579

580

581

582

583

584

585

586 for (unsigned Shift = 0; Shift < BitSize; Shift += 16) {

587 uint64_t ShiftedMask = (0xFFFFULL << Shift);

588 uint64_t ZeroChunk = UImm & ~ShiftedMask;

589 uint64_t OneChunk = UImm | ShiftedMask;

591 uint64_t ReplicateChunk = ZeroChunk | (RotatedImm & ShiftedMask);

595 Encoding)) {

596

597 Insn.push_back({ AArch64::ORRXri, 0, Encoding });

598

599

600 const unsigned Imm16 = getChunk(UImm, Shift / 16);

601 Insn.push_back({ AArch64::MOVKXi, Imm16,

603 return;

604 }

605 }

606

607

609 return;

610

611

613 return;

614

615

617 return;

618

619

620

621

622

623

624

625

626

627 if (OneChunks || ZeroChunks) {

629 return;

630 }

631

632

633

634

636 return;

637

638

639

640

641

642

644 return;

645

646

647

649}

static uint64_t GetRunOfOnesStartingAt(uint64_t V, uint64_t StartPosition)

Definition AArch64ExpandImm.cpp:242

static void expandMOVImmSimple(uint64_t Imm, unsigned BitSize, unsigned OneChunks, unsigned ZeroChunks, SmallVectorImpl< ImmInsnModel > &Insn)

Expand a MOVi32imm or MOVi64imm pseudo instruction to a MOVZ or MOVN of width BitSize followed by up ...

Definition AArch64ExpandImm.cpp:466

static uint64_t updateImm(uint64_t Imm, unsigned Idx, bool Clear)

Clear or set all bits in the chunk at the given index.

Definition AArch64ExpandImm.cpp:124

static bool canUseOrr(uint64_t Chunk, uint64_t &Encoding)

Check whether the given 16-bit chunk replicated to full 64-bit width can be materialized with an ORR ...

Definition AArch64ExpandImm.cpp:30

static bool tryToreplicateChunks(uint64_t UImm, SmallVectorImpl< ImmInsnModel > &Insn)

Check for identical 16-bit chunks within the constant and if so materialize them with a single ORR in...

Definition AArch64ExpandImm.cpp:43

static bool trySequenceOfOnes(uint64_t UImm, SmallVectorImpl< ImmInsnModel > &Insn)

Check whether the constant contains a sequence of contiguous ones, which might be interrupted by one ...

Definition AArch64ExpandImm.cpp:150

static uint64_t MaximallyReplicateSubImmediate(uint64_t V, uint64_t Subset)

Definition AArch64ExpandImm.cpp:254

static bool tryAndOfLogicalImmediates(uint64_t UImm, SmallVectorImpl< ImmInsnModel > &Insn)

Definition AArch64ExpandImm.cpp:341

static uint64_t getChunk(uint64_t Imm, unsigned ChunkIdx)

Helper function which extracts the specified 16-bit chunk from a 64-bit value.

Definition AArch64ExpandImm.cpp:22

static bool tryEorOfLogicalImmediates(uint64_t Imm, SmallVectorImpl< ImmInsnModel > &Insn)

Definition AArch64ExpandImm.cpp:373

static uint64_t maximalLogicalImmWithin(uint64_t RemainingBits, uint64_t OriginalBits)

Definition AArch64ExpandImm.cpp:272

static bool isStartChunk(uint64_t Chunk)

Check whether this chunk matches the pattern '1...0...'.

Definition AArch64ExpandImm.cpp:106

static bool isEndChunk(uint64_t Chunk)

Check whether this chunk matches the pattern '0...1...' This pattern ends a contiguous sequence of on...

Definition AArch64ExpandImm.cpp:116

static bool tryOrrOfLogicalImmediates(uint64_t UImm, SmallVectorImpl< ImmInsnModel > &Insn)

Definition AArch64ExpandImm.cpp:316

static std::optional< std::pair< uint64_t, uint64_t > > decomposeIntoOrrOfLogicalImmediates(uint64_t UImm)

Definition AArch64ExpandImm.cpp:288

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

static bool isNeg(Value *V)

Returns true if the operation is a negation of V, and it works for both integers and floats.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

static bool processLogicalImmediate(uint64_t Imm, unsigned RegSize, uint64_t &Encoding)

processLogicalImmediate - Determine if an immediate value can be encoded as the immediate operand of ...

static unsigned getShifterImm(AArch64_AM::ShiftExtendType ST, unsigned Imm)

getShifterImm - Encode the shift type and amount: imm: 6-bit shift amount shifter: 000 ==> lsl 001 ==...

void expandMOVImm(uint64_t Imm, unsigned BitSize, SmallVectorImpl< ImmInsnModel > &Insn)

Expand a MOVi32imm or MOVi64imm pseudo instruction to one or more real move-immediate instructions to...

Definition AArch64ExpandImm.cpp:533

This is an optimization pass for GlobalISel generic memory operations.

constexpr T rotr(T V, int R)

int countr_one(T Value)

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

constexpr int popcount(T Value) noexcept

Count the number of set bits in a value.

int countr_zero(T Val)

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

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 isMask_64(uint64_t Value)

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

FunctionAddr VTableAddr Count

constexpr T rotl(T V, int R)

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

Implement std::swap in terms of BitVector swap.