VectorUtils.h Source File (original) (raw)

13#ifndef LLVM_ANALYSIS_VECTORUTILS_H

14#define LLVM_ANALYSIS_VECTORUTILS_H

25namespace llvm {

44 static void getVFABIMappings(const CallInst &CI,

46 if (!CI.getCalledFunction())

47 return;

49 const StringRef ScalarName = CI.getCalledFunction()->getName();

55 if (ListOfStrings.empty())

56 return;

57 for (const auto &MangledName : ListOfStrings) {

58 const std::optional Shape =

64 if (Shape && (Shape->ScalarName == ScalarName)) {

65 assert(CI.getModule()->getFunction(Shape->VectorName) &&

66 "Vector function is missing.");

68 }

69 }

70 }

72public:

78 getVFABIMappings(CI, Ret);

82 return Ret;

83 }

86 std::optional VF = std::nullopt) {

92 if (!VF || Info.Shape.VF == *VF)

93 if (Info.isMasked())

94 return true;

96 return false;

97 }

101 : M(CI.getModule()), CI(CI),

103

104

105

106

107

110 return CI.getCalledFunction();

111

112 for (const auto &Info : ScalarToVectorMappings)

113 if (Info.Shape == Shape)

115

116 return nullptr;

117 }

118

119};

120

121template class ArrayRef;

122class DemandedBits;

123template class InterleaveGroup;

124class IRBuilderBase;

125class Loop;

126class TargetTransformInfo;

127class Value;

128

129namespace Intrinsic {

130typedef unsigned ID;

131}

132

133

134

135

136

137

138

140

141

142

143

144

145

146

147

148

151

152

153

154

158

159

160

161

162

166

167

168

169

170

173

174

175

176

179

180

182

183

185

186

187

189

190

191

192

194

195

196

197

199

200

201

202

204

205

206

207

208

209

210

212

213

214

215

216

218 const APInt &DemandedElts,

219 APInt &DemandedLHS, APInt &DemandedRHS,

220 bool AllowUndefElts = false);

221

222

223

224

225

226

227

229 std::array<std::pair<int, int>, 2> &SrcInfo);

230

231

232

233

234

235

236

237

238

239

240

241

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

262

263

264

265

266

269

270

271

272

273

274

277

278

279

282

283

284

285

286

287

288

289

290

291

292

293

294

296 ArrayRef Mask, unsigned NumOfSrcRegs, unsigned NumOfDestRegs,

297 unsigned NumOfUsedRegs, function_ref<void()> NoInputAction,

300 ManyInputsAction);

301

302

303

304

305

306

307

308

309

310

311

312

313

315 const APInt &DemandedElts,

316 APInt &DemandedLHS,

317 APInt &DemandedRHS);

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

356

357

358

359

360

362

363

364

365

366

367

368

371

372

373

374

375

379

380

381

382

383

384

385

386

387

389

390

391

392

393

394

395

396

397

398

399

400

404

405

406

407

408

409

410

411

412

413

414

415

416

419

420

421

422

423

424

425

426

427

428

429

430

432 unsigned NumVecs);

433

434

435

436

437

438

439

440

441

442

443

444

445

447createStrideMask(unsigned Start, unsigned Stride, unsigned VF);

448

449

450

451

452

453

454

455

456

457

458

459

462

463

464

465

467 unsigned NumElts);

468

469

470

471

472

473

474

475

478

479

480

481

483

484

485

486

488

489

490

491

493

494

495

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

525public:

527 : Factor(Factor), Reverse(Reverse), Alignment(Alignment),

528 InsertPos(nullptr) {}

529

531 : Alignment(Alignment), InsertPos(Instr) {

532 Factor = std::abs(Stride);

533 assert(Factor > 1 && "Invalid interleave factor");

534

535 Reverse = Stride < 0;

536 Members[0] = Instr;

537 }

538

543

544

545

546

547

548

550

551 std::optional<int32_t> MaybeKey = checkedAdd(Index, SmallestKey);

552 if (!MaybeKey)

553 return false;

554 int32_t Key = *MaybeKey;

555

556

559 return false;

560

561

562 if (Members.contains(Key))

563 return false;

564

565 if (Key > LargestKey) {

566

567 if (Index >= static_cast<int32_t>(Factor))

568 return false;

569

570 LargestKey = Key;

571 } else if (Key < SmallestKey) {

572

573

574 std::optional<int32_t> MaybeLargestIndex = checkedSub(LargestKey, Key);

575 if (!MaybeLargestIndex)

576 return false;

577

578

579 if (*MaybeLargestIndex >= static_cast<int64_t>(Factor))

580 return false;

581

582 SmallestKey = Key;

583 }

584

585

586 Alignment = std::min(Alignment, NewAlign);

587 Members[Key] = Instr;

588 return true;

589 }

590

591

592

593

595 int32_t Key = SmallestKey + Index;

596 return Members.lookup(Key);

597 }

598

599

600

602 for (auto I : Members) {

603 if (I.second == Instr)

604 return I.first - SmallestKey;

605 }

606

608 }

609

612

613

614

615

616

617

618

620

621

623

624

626 return false;

627

628

629

630 assert( isReverse () && "Group should have been invalidated");

631

632

633 return true;

634 }

635

636

638

639private:

640 uint32_t Factor;

644 int32_t SmallestKey = 0;

645 int32_t LargestKey = 0;

646

647

648

649

650

651

652

653

654

655

656

657

658 InstTy *InsertPos;

659};

660

661

662

663

664

665

666

667

668

670public:

674 : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}

675

677

678

679

680

681

683

684

685

686

687

688

690 if (InterleaveGroups.empty()) {

692 !RequiresScalarEpilogue &&

693 "RequiresScalarEpilog should not be set without interleave groups");

694 return false;

695 }

696

697 InterleaveGroupMap.clear();

698 for (auto *Ptr : InterleaveGroups)

699 delete Ptr;

700 InterleaveGroups.clear();

701 RequiresScalarEpilogue = false;

702 return true;

703 }

704

705

707 return InterleaveGroupMap.contains(Instr);

708 }

709

710

711

712

715 return InterleaveGroupMap.lookup(Instr);

716 }

717

720 return make_range(InterleaveGroups.begin(), InterleaveGroups.end());

721 }

722

723

724

726

727

728

729

731

732

733 bool hasGroups() const { return !InterleaveGroups.empty(); }

734

735private:

736

737

738

739

741

742 Loop *TheLoop;

746

747

748

749

750 bool RequiresScalarEpilogue = false;

751

752

754

756

757

758

760

761

762 struct StrideDescriptor {

763 StrideDescriptor() = default;

764 StrideDescriptor(int64_t Stride, const SCEV *Scev, uint64_t Size,

766 : Stride(Stride), Scev(Scev), Size(Size), Alignment(Alignment) {}

767

768

769 int64_t Stride = 0;

770

771

772 const SCEV *Scev = nullptr;

773

774

776

777

778 Align Alignment;

779 };

780

781

782 using StrideEntry = std::pair<Instruction *, StrideDescriptor>;

783

784

785

786

787

788 InterleaveGroup *

789 createInterleaveGroup(Instruction *Instr, int Stride, Align Alignment) {

790 auto [It, Inserted] = InterleaveGroupMap.try_emplace(Instr);

791 assert(Inserted && "Already in an interleaved access group");

792 It->second = new InterleaveGroup(Instr, Stride, Alignment);

793 InterleaveGroups.insert(It->second);

794 return It->second;

795 }

796

797

798 void releaseGroup(InterleaveGroup *Group) {

799 InterleaveGroups.erase(Group);

800 releaseGroupWithoutRemovingFromSet(Group);

801 }

802

803

804

805 void releaseGroupWithoutRemovingFromSet(InterleaveGroup *Group) {

806 for (unsigned i = 0; i < Group->getFactor(); i++)

807 if (Instruction *Member = Group->getMember(i))

808 InterleaveGroupMap.erase(Member);

809

810 delete Group;

811 }

812

813

814 void collectConstStrideAccesses(

815 MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,

816 const DenseMap<Value *, const SCEV *> &Strides);

817

818

819 LLVM_ABI static bool isStrided(int Stride);

820

821

822 bool isPredicated(BasicBlock *BB) const {

824 }

825

826

827 bool areDependencesValid() const {

828 return LAI && LAI->getDepChecker().getDependences();

829 }

830

831

832

833

834

835

836 bool canReorderMemAccessesForInterleavedGroups(StrideEntry *A,

837 StrideEntry *B) const {

838

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853 auto *Src = A->first;

854 auto SrcDes = A->second;

855

856

857 auto *Sink = B->first;

858 auto SinkDes = B->second;

859

860

861

862 if (!Src->mayWriteToMemory())

863 return true;

864

865

866 if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))

867 return true;

868

869

870

871 if (!areDependencesValid())

872 return false;

873

874

875

876 return !Dependences.contains(Src) || !Dependences.lookup(Src).count(Sink);

877 }

878

879

880

881

882

883 void collectDependences() {

884 if (!areDependencesValid())

885 return;

886 const auto &DepChecker = LAI->getDepChecker();

887 auto *Deps = DepChecker.getDependences();

888 for (auto Dep : *Deps)

889 Dependences[Dep.getSource(DepChecker)].insert(

890 Dep.getDestination(DepChecker));

891 }

892};

893

894}

895

896#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")

Analysis containing CSE Info

Module.h This file contains the declarations for the Module class.

This file implements a map that provides insertion order iteration.

This file defines the SmallVector class.

Class for arbitrary precision integers.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

This class represents a function call, abstracting a target machine's calling convention.

This is an important base class in LLVM.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

const Function & getFunction() const

Common base class shared among various IRBuilders.

The group of interleaved loads/stores sharing the same stride and close to each other.

Definition VectorUtils.h:524

bool requiresScalarEpilogue() const

Returns true if this Group requires a scalar iteration to handle gaps.

Definition VectorUtils.h:622

uint32_t getFactor() const

Definition VectorUtils.h:540

InstTy * getMember(uint32_t Index) const

Get the member with the given index Index.

Definition VectorUtils.h:594

InterleaveGroup(uint32_t Factor, bool Reverse, Align Alignment)

Definition VectorUtils.h:526

bool isFull() const

Return true if this group is full, i.e. it has no gaps.

Definition VectorUtils.h:637

uint32_t getIndex(const InstTy *Instr) const

Get the index for the given member.

Definition VectorUtils.h:601

void setInsertPos(InstTy *Inst)

Definition VectorUtils.h:611

bool isReverse() const

Definition VectorUtils.h:539

InstTy * getInsertPos() const

Definition VectorUtils.h:610

void addMetadata(InstTy *NewInst) const

Add metadata (e.g.

Align getAlign() const

Definition VectorUtils.h:541

InterleaveGroup(InstTy *Instr, int32_t Stride, Align Alignment)

Definition VectorUtils.h:530

bool insertMember(InstTy *Instr, int32_t Index, Align NewAlign)

Try to insert a new member Instr with index Index and alignment NewAlign.

Definition VectorUtils.h:549

uint32_t getNumMembers() const

Definition VectorUtils.h:542

InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const

Get the interleave group that Instr belongs to.

Definition VectorUtils.h:714

bool requiresScalarEpilogue() const

Returns true if an interleaved group that may access memory out-of-bounds requires a scalar epilogue ...

Definition VectorUtils.h:725

bool hasGroups() const

Returns true if we have any interleave groups.

Definition VectorUtils.h:733

bool isInterleaved(Instruction *Instr) const

Check if Instr belongs to any interleave group.

Definition VectorUtils.h:706

bool invalidateGroups()

Invalidate groups, e.g., in case all blocks in loop will be predicated contrary to original assumptio...

Definition VectorUtils.h:689

iterator_range< SmallPtrSetIterator< llvm::InterleaveGroup< Instruction > * > > getInterleaveGroups()

Definition VectorUtils.h:719

LLVM_ABI void analyzeInterleaving(bool EnableMaskedInterleavedGroup)

Analyze the interleaved accesses and collect them in interleave groups.

LLVM_ABI void invalidateGroupsRequiringScalarEpilogue()

Invalidate groups that require a scalar epilogue (due to gaps).

~InterleavedAccessInfo()

Definition VectorUtils.h:676

InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L, DominatorTree *DT, LoopInfo *LI, const LoopAccessInfo *LAI)

Definition VectorUtils.h:671

A wrapper class for inspecting calls to intrinsic functions.

Drive the analysis of memory accesses in the loop.

static LLVM_ABI bool blockNeedsPredication(const BasicBlock *BB, const Loop *TheLoop, const DominatorTree *DT)

Return true if the block BB needs to be predicated in order for the loop to be vectorized.

Represents a single loop in the control flow graph.

This class implements a map that also provides access to all stored values in a deterministic order.

A Module instance is used to store all the information related to an LLVM module.

An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...

This class represents an analyzed expression in the program.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

Provides information about what library functions are available for the current target.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

VFDatabase(CallInst &CI)

Constructor, requires a CallInst instance.

Definition VectorUtils.h:100

static bool hasMaskedVariant(const CallInst &CI, std::optional< ElementCount > VF=std::nullopt)

Definition VectorUtils.h:85

static SmallVector< VFInfo, 8 > getMappings(const CallInst &CI)

Retrieve all the VFInfo instances associated to the CallInst CI.

Definition VectorUtils.h:74

LLVM Value Representation.

Base class of all SIMD vector types.

An efficient, type-erasing, non-owning reference to a callable.

A range adaptor for a pair of iterators.

Function * getVectorizedFunction(const VFShape &Shape) const

Definition VectorUtils.h:108

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

LLVM_ABI std::optional< VFInfo > tryDemangleForVFABI(StringRef MangledName, const FunctionType *FTy)

Function to construct a VFInfo out of a mangled names in the following format:

LLVM_ABI void getVectorVariantNames(const CallInst &CI, SmallVectorImpl< std::string > &VariantMappings)

Populates a set of strings representing the Vector Function ABI variants associated to the CallInst C...

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI bool isTriviallyScalarizable(Intrinsic::ID ID, const TargetTransformInfo *TTI)

Identify if the intrinsic is trivially scalarizable.

LLVM_ABI Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)

Returns intrinsic ID for call.

LLVM_ABI APInt possiblyDemandedEltsInMask(Value *Mask)

Given a mask vector of the form , return an APInt (of bitwidth Y) for each lane which may be ...

LLVM_ABI llvm::SmallVector< int, 16 > createUnaryMask(ArrayRef< int > Mask, unsigned NumElts)

Given a shuffle mask for a binary shuffle, create the equivalent shuffle mask assuming both operands ...

LLVM_ABI void getMetadataToPropagate(Instruction *Inst, SmallVectorImpl< std::pair< unsigned, MDNode * > > &Metadata)

Add metadata from Inst to Metadata, if it can be preserved after vectorization.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

LLVM_ABI Value * concatenateVectors(IRBuilderBase &Builder, ArrayRef< Value * > Vecs)

Concatenate a list of vectors.

LLVM_ABI bool widenShuffleMaskElts(int Scale, ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)

Try to transform a shuffle mask by replacing elements with the scaled index for an equivalent mask of...

LLVM_ABI Instruction * propagateMetadata(Instruction *I, ArrayRef< Value * > VL)

Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath, MD_nontemporal,...

LLVM_ABI Value * getSplatValue(const Value *V)

Get splat value if the input is a splat vector or return nullptr.

LLVM_ABI MDNode * intersectAccessGroups(const Instruction *Inst1, const Instruction *Inst2)

Compute the access-group list of access groups that Inst1 and Inst2 are both in.

LLVM_ABI bool getShuffleDemandedElts(int SrcWidth, ArrayRef< int > Mask, const APInt &DemandedElts, APInt &DemandedLHS, APInt &DemandedRHS, bool AllowUndefElts=false)

Transform a shuffle mask's output demanded element mask into demanded element masks for the 2 operand...

LLVM_ABI bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)

Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...

LLVM_ABI Constant * createBitMaskForGaps(IRBuilderBase &Builder, unsigned VF, const InterleaveGroup< Instruction > &Group)

Create a mask that filters the members of an interleave group where there are gaps.

LLVM_ABI llvm::SmallVector< int, 16 > createStrideMask(unsigned Start, unsigned Stride, unsigned VF)

Create a stride shuffle mask.

LLVM_ABI void getHorizDemandedEltsForFirstOperand(unsigned VectorBitWidth, const APInt &DemandedElts, APInt &DemandedLHS, APInt &DemandedRHS)

Compute the demanded elements mask of horizontal binary operations.

LLVM_ABI llvm::SmallVector< int, 16 > createReplicatedMask(unsigned ReplicationFactor, unsigned VF)

Create a mask with replicated elements.

LLVM_ABI unsigned getDeinterleaveIntrinsicFactor(Intrinsic::ID ID)

Returns the corresponding factor of llvm.vector.deinterleaveN intrinsics.

LLVM_ABI unsigned getInterleaveIntrinsicFactor(Intrinsic::ID ID)

Returns the corresponding factor of llvm.vector.interleaveN intrinsics.

LLVM_ABI bool maskIsAllOneOrUndef(Value *Mask)

Given a mask vector of i1, Return true if all of the elements of this predicate mask are known to be ...

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

LLVM_ABI bool isVectorIntrinsicWithStructReturnOverloadAtField(Intrinsic::ID ID, int RetIdx, const TargetTransformInfo *TTI)

Identifies if the vector form of the intrinsic that returns a struct is overloaded at the struct elem...

LLVM_ABI void narrowShuffleMaskElts(int Scale, ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)

Replace each shuffle mask index with the scaled sequential indices for an equivalent mask of narrowed...

LLVM_ABI bool isMaskedSlidePair(ArrayRef< int > Mask, int NumElts, std::array< std::pair< int, int >, 2 > &SrcInfo)

Does this shuffle mask represent either one slide shuffle or a pair of two slide shuffles,...

LLVM_ABI VectorType * getDeinterleavedVectorType(IntrinsicInst *DI)

Given a deinterleaveN intrinsic, return the (narrow) vector type of each factor.

LLVM_ABI llvm::SmallVector< int, 16 > createInterleaveMask(unsigned VF, unsigned NumVecs)

Create an interleave shuffle mask.

LLVM_ABI bool isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx, const TargetTransformInfo *TTI)

Identifies if the vector form of the intrinsic has a scalar operand.

LLVM_ABI Value * findScalarElement(Value *V, unsigned EltNo)

Given a vector and an element number, see if the scalar value is already around as a register,...

LLVM_ABI MDNode * uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2)

Compute the union of two access-group lists.

ArrayRef(const T &OneElt) -> ArrayRef< T >

LLVM_ABI bool maskIsAllZeroOrUndef(Value *Mask)

Given a mask vector of i1, Return true if all of the elements of this predicate mask are known to be ...

std::enable_if_t< std::is_signed_v< T >, std::optional< T > > checkedSub(T LHS, T RHS)

Subtract two signed integers LHS and RHS.

LLVM_ABI void getShuffleMaskWithWidestElts(ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)

Repetitively apply widenShuffleMaskElts() for as long as it succeeds, to get the shuffle mask with wi...

std::enable_if_t< std::is_signed_v< T >, std::optional< T > > checkedAdd(T LHS, T RHS)

Add two signed integers LHS and RHS.

LLVM_ABI void processShuffleMasks(ArrayRef< int > Mask, unsigned NumOfSrcRegs, unsigned NumOfDestRegs, unsigned NumOfUsedRegs, function_ref< void()> NoInputAction, function_ref< void(ArrayRef< int >, unsigned, unsigned)> SingleInputAction, function_ref< void(ArrayRef< int >, unsigned, unsigned, bool)> ManyInputsAction)

Splits and processes shuffle mask depending on the number of input and output registers.

LLVM_ABI bool maskContainsAllOneOrUndef(Value *Mask)

Given a mask vector of i1, Return true if any of the elements of this predicate mask are known to be ...

LLVM_ABI bool isTriviallyVectorizable(Intrinsic::ID ID)

Identify if the intrinsic is trivially vectorizable.

LLVM_ABI llvm::SmallVector< int, 16 > createSequentialMask(unsigned Start, unsigned NumInts, unsigned NumUndefs)

Create a sequential shuffle mask.

LLVM_ABI bool isVectorIntrinsicWithOverloadTypeAtArg(Intrinsic::ID ID, int OpdIdx, const TargetTransformInfo *TTI)

Identifies if the vector form of the intrinsic is overloaded on the type of the operand at index OpdI...

LLVM_ABI MapVector< Instruction *, uint64_t > computeMinimumValueSizes(ArrayRef< BasicBlock * > Blocks, DemandedBits &DB, const TargetTransformInfo *TTI=nullptr)

Compute a map of integer instructions to their minimum legal type size.

LLVM_ABI bool scaleShuffleMaskElts(unsigned NumDstElts, ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)

Attempt to narrow/widen the Mask shuffle mask to the NumDstElts target width.

LLVM_ABI int getSplatIndex(ArrayRef< int > Mask)

If all non-negative Mask elements are the same value, return that value.

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

An information struct used to provide DenseMap with the various necessary components for a given valu...

Holds the VFShape for a specific scalar to vector function mapping.

Contains the information about the kind of vectorization available.

static VFShape getScalarShape(const FunctionType *FTy)

Retrieve the VFShape that can be used to map a scalar function to itself, with VF = 1.