ComplexDeinterleavingPass.cpp Source File (original) (raw)

77#include

79using namespace llvm;

82#define DEBUG_TYPE "complex-deinterleaving"

84 STATISTIC(NumComplexTransformations, "Amount of complex patterns transformed");

87 "enable-complex-deinterleaving",

88 cl::desc("Enable generation of complex instructions"), cl::init(true),

100

101

102

103

105

106

107

109

110

112

113namespace {

114struct ComplexValue {

115 Value *Real = nullptr;

116 Value *Imag = nullptr;

117

119 return Real == Other.Real && Imag == Other.Imag;

120 }

121};

125}

126}

128

142 static bool isEqual(const ComplexValue &LHS, const ComplexValue &RHS) {

143 return LHS.Real == RHS.Real && LHS.Imag == RHS.Imag;

144 }

145};

146

147namespace {

148template <typename T, typename IterT>

149std::optional findCommonBetweenCollections(IterT A, IterT B) {

151 if (Common != A.end())

152 return std::make_optional(*Common);

153 return std::nullopt;

154}

155

156class ComplexDeinterleavingLegacyPass : public FunctionPass {

157public:

158 static char ID;

159

160 ComplexDeinterleavingLegacyPass(const TargetMachine *TM = nullptr)

161 : FunctionPass(ID), TM(TM) {

164 }

165

166 StringRef getPassName() const override {

167 return "Complex Deinterleaving Pass";

168 }

169

171 void getAnalysisUsage(AnalysisUsage &AU) const override {

172 AU.addRequired();

174 }

175

176private:

177 const TargetMachine *TM;

178};

179

180class ComplexDeinterleavingGraph;

181struct ComplexDeinterleavingCompositeNode {

182

185 : Operation(Op) {

186 Vals.push_back({R, I});

187 }

188

191 : Operation(Op), Vals(Other) {}

192

193private:

194 friend class ComplexDeinterleavingGraph;

195 using CompositeNode = ComplexDeinterleavingCompositeNode;

196 bool OperandsValid = true;

197

198public:

201

202

203

204 unsigned Opcode;

205 std::optional Flags;

206

208 ComplexDeinterleavingRotation::Rotation_0;

210 Value *ReplacementNode = nullptr;

211

212 void addOperand(CompositeNode *Node) {

213 if (!Node)

214 OperandsValid = false;

215 Operands.push_back(Node);

216 }

217

219 void dump(raw_ostream &OS) {

220 auto PrintValue = [&](Value *V) {

221 if (V) {

222 OS << "\"";

223 V->print(OS, true);

224 OS << "\"\n";

225 } else

226 OS << "nullptr\n";

227 };

228 auto PrintNodeRef = [&](CompositeNode *Ptr) {

229 if (Ptr)

230 OS << Ptr << "\n";

231 else

232 OS << "nullptr\n";

233 };

234

235 OS << "- CompositeNode: " << this << "\n";

236 for (unsigned I = 0; I < Vals.size(); I++) {

237 OS << " Real(" << I << ") : ";

238 PrintValue(Vals[I].Real);

239 OS << " Imag(" << I << ") : ";

240 PrintValue(Vals[I].Imag);

241 }

242 OS << " ReplacementNode: ";

243 PrintValue(ReplacementNode);

244 OS << " Operation: " << (int)Operation << "\n";

245 OS << " Rotation: " << ((int)Rotation * 90) << "\n";

246 OS << " Operands: \n";

247 for (const auto &Op : Operands) {

248 OS << " - ";

249 PrintNodeRef(Op);

250 }

251 }

252

253 bool areOperandsValid() { return OperandsValid; }

254};

255

256class ComplexDeinterleavingGraph {

257public:

258 struct Product {

259 Value *Multiplier;

260 Value *Multiplicand;

261 bool IsPositive;

262 };

263

264 using Addend = std::pair<Value *, bool>;

266 using CompositeNode = ComplexDeinterleavingCompositeNode::CompositeNode;

267

268

269

270 struct PartialMulCandidate {

272 CompositeNode *Node;

273 unsigned RealIdx;

274 unsigned ImagIdx;

275 bool IsNodeInverted;

276 };

277

278 explicit ComplexDeinterleavingGraph(const TargetLowering *TL,

279 const TargetLibraryInfo *TLI,

280 unsigned Factor)

281 : TL(TL), TLI(TLI), Factor(Factor) {}

282

283private:

284 const TargetLowering *TL = nullptr;

285 const TargetLibraryInfo *TLI = nullptr;

286 unsigned Factor;

288 DenseMap<ComplexValues, CompositeNode *> CachedResult;

289 SpecificBumpPtrAllocator Allocator;

290

291 SmallPtrSet<Instruction *, 16> FinalInstructions;

292

293

294 DenseMap<Instruction *, CompositeNode *> RootToNode;

295

296

298

299

300

301

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321 MapVector<Instruction *, std::pair<PHINode *, Instruction *>> ReductionInfo;

322

323

324

325

326

327

328

329 PHINode *RealPHI = nullptr;

330 PHINode *ImagPHI = nullptr;

331

332

333

334 bool PHIsFound = false;

335

336

337

338

339

340

341

342 DenseMap<PHINode *, PHINode *> OldToNewPHI;

343

346 assert(((Operation != ComplexDeinterleavingOperation::ReductionPHI &&

347 Operation != ComplexDeinterleavingOperation::ReductionOperation) ||

348 (R && I)) &&

349 "Reduction related nodes must have Real and Imaginary parts");

350 return new (Allocator.Allocate())

351 ComplexDeinterleavingCompositeNode(Operation, R, I);

352 }

353

356#ifndef NDEBUG

357 for (auto &V : Vals) {

359 ((Operation != ComplexDeinterleavingOperation::ReductionPHI &&

360 Operation != ComplexDeinterleavingOperation::ReductionOperation) ||

361 (V.Real && V.Imag)) &&

362 "Reduction related nodes must have Real and Imaginary parts");

363 }

364#endif

365 return new (Allocator.Allocate())

366 ComplexDeinterleavingCompositeNode(Operation, Vals);

367 }

368

369 CompositeNode *submitCompositeNode(CompositeNode *Node) {

370 CompositeNodes.push_back(Node);

371 if (Node->Vals[0].Real)

372 CachedResult[Node->Vals] = Node;

374 }

375

376

377

378

379

380

381

382

383

384

385

386

387 CompositeNode *identifyPartialMul(Instruction *Real, Instruction *Imag);

388

389

390

391

392 CompositeNode *

393 identifyNodeWithImplicitAdd(Instruction *I, Instruction *J,

394 std::pair<Value *, Value *> &CommonOperandI);

395

396

397

398

399

400

401

402

403 CompositeNode *identifyAdd(Instruction *Real, Instruction *Imag);

404 CompositeNode *identifySymmetricOperation(ComplexValues &Vals);

405 CompositeNode *identifyPartialReduction(Value *R, Value *I);

406 CompositeNode *identifyDotProduct(Value *Inst);

407

408 CompositeNode *identifyNode(ComplexValues &Vals);

409

410 CompositeNode *identifyNode(Value *R, Value *I) {

413 return identifyNode(Vals);

414 }

415

416

417

418

419

420 CompositeNode *identifyAdditions(AddendList &RealAddends,

421 AddendList &ImagAddends,

422 std::optional Flags,

424

425

426 CompositeNode *extractPositiveAddend(AddendList &RealAddends,

427 AddendList &ImagAddends);

428

429

430

431

432 CompositeNode *identifyMultiplications(SmallVectorImpl &RealMuls,

433 SmallVectorImpl &ImagMuls,

435

436

437

438

441 SmallVectorImpl &Candidates);

442

443

444

445

446

447

448

449 CompositeNode *identifyReassocNodes(Instruction *I, Instruction *J);

450

451 CompositeNode *identifyRoot(Instruction *I);

452

453

454

455

456

457

458

459

460

461 CompositeNode *identifyDeinterleave(ComplexValues &Vals);

462

463

464

465

466

467 CompositeNode *identifySplat(ComplexValues &Vals);

468

469 CompositeNode *identifyPHINode(Instruction *Real, Instruction *Imag);

470

471

472

473 CompositeNode *identifySelectNode(Instruction *Real, Instruction *Imag);

474

475 Value *replaceNode(IRBuilderBase &Builder, CompositeNode *Node);

476

477

478

479

480

481

482 void processReductionOperation(Value *OperationReplacement,

483 CompositeNode *Node);

484 void processReductionSingle(Value *OperationReplacement, CompositeNode *Node);

485

486public:

488 void dump(raw_ostream &OS) {

489 for (const auto &Node : CompositeNodes)

490 Node->dump(OS);

491 }

492

493

494

495 bool identifyNodes(Instruction *RootI);

496

497

498

499

500 bool collectPotentialReductions(BasicBlock *B);

501

502 void identifyReductionNodes();

503

504

505

506 bool checkNodes();

507

508

509 void replaceNodes();

510};

511

512class ComplexDeinterleaving {

513public:

514 ComplexDeinterleaving(const TargetLowering *tl, const TargetLibraryInfo *tli)

515 : TL(tl), TLI(tli) {}

517

518private:

519 bool evaluateBasicBlock(BasicBlock *B, unsigned Factor);

520

521 const TargetLowering *TL = nullptr;

522 const TargetLibraryInfo *TLI = nullptr;

523};

524

525}

526

527char ComplexDeinterleavingLegacyPass::ID = 0;

528

530 "Complex Deinterleaving", false, false)

533

536 const TargetLowering *TL = TM->getSubtargetImpl(F)->getTargetLowering();

538 if (!ComplexDeinterleaving(TL, &TLI).runOnFunction(F))

540

543 return PA;

544}

545

547 return new ComplexDeinterleavingLegacyPass(TM);

548}

549

550bool ComplexDeinterleavingLegacyPass::runOnFunction(Function &F) {

552 auto TLI = getAnalysis().getTLI(F);

553 return ComplexDeinterleaving(TL, &TLI).runOnFunction(F);

554}

555

556bool ComplexDeinterleaving::runOnFunction(Function &F) {

559 dbgs() << "Complex deinterleaving has been explicitly disabled.\n");

560 return false;

561 }

562

565 dbgs() << "Complex deinterleaving has been disabled, target does "

566 "not support lowering of complex number operations.\n");

567 return false;

568 }

569

571 for (auto &B : F)

572 Changed |= evaluateBasicBlock(&B, 2);

573

574

576 for (auto &B : F)

577 Changed |= evaluateBasicBlock(&B, 4);

578 }

579

580

581

583}

584

586

587 if ((Mask.size() & 1))

588 return false;

589

590 int HalfNumElements = Mask.size() / 2;

591 for (int Idx = 0; Idx < HalfNumElements; ++Idx) {

592 int MaskIdx = Idx * 2;

593 if (Mask[MaskIdx] != Idx || Mask[MaskIdx + 1] != (Idx + HalfNumElements))

594 return false;

595 }

596

597 return true;

598}

599

601 int Offset = Mask[0];

602 int HalfNumElements = Mask.size() / 2;

603

604 for (int Idx = 1; Idx < HalfNumElements; ++Idx) {

605 if (Mask[Idx] != (Idx * 2) + Offset)

606 return false;

607 }

608

609 return true;

610}

611

615

619 if (I->getOpcode() == Instruction::FNeg)

620 return I->getOperand(0);

621

622 return I->getOperand(1);

623}

624

625bool ComplexDeinterleaving::evaluateBasicBlock(BasicBlock *B, unsigned Factor) {

626 ComplexDeinterleavingGraph Graph(TL, TLI, Factor);

627 if (Graph.collectPotentialReductions(B))

628 Graph.identifyReductionNodes();

629

630 for (auto &I : *B)

631 Graph.identifyNodes(&I);

632

633 if (Graph.checkNodes()) {

634 Graph.replaceNodes();

635 return true;

636 }

637

638 return false;

639}

640

641ComplexDeinterleavingGraph::CompositeNode *

642ComplexDeinterleavingGraph::identifyNodeWithImplicitAdd(

643 Instruction *Real, Instruction *Imag,

644 std::pair<Value *, Value *> &PartialMatch) {

645 LLVM_DEBUG(dbgs() << "identifyNodeWithImplicitAdd " << *Real << " / " << *Imag

646 << "\n");

647

649 LLVM_DEBUG(dbgs() << " - Mul operand has multiple uses.\n");

650 return nullptr;

651 }

652

653 if ((Real->getOpcode() != Instruction::FMul &&

654 Real->getOpcode() != Instruction::Mul) ||

655 (Imag->getOpcode() != Instruction::FMul &&

656 Imag->getOpcode() != Instruction::Mul)) {

658 dbgs() << " - Real or imaginary instruction is not fmul or mul\n");

659 return nullptr;

660 }

661

666

667

668

669 unsigned Negs = 0;

672 Negs |= 1;

673 R0 = Op;

675 Negs |= 1;

676 R1 = Op;

677 }

678

680 Negs |= 2;

681 Negs ^= 1;

682 I0 = Op;

684 Negs |= 2;

685 Negs ^= 1;

687 }

688

690

691 Value *CommonOperand;

692 Value *UncommonRealOp;

693 Value *UncommonImagOp;

694

695 if (R0 == I0 || R0 == I1) {

696 CommonOperand = R0;

697 UncommonRealOp = R1;

698 } else if (R1 == I0 || R1 == I1) {

699 CommonOperand = R1;

700 UncommonRealOp = R0;

701 } else {

703 return nullptr;

704 }

705

706 UncommonImagOp = (CommonOperand == I0) ? I1 : I0;

707 if (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||

708 Rotation == ComplexDeinterleavingRotation::Rotation_270)

709 std::swap(UncommonRealOp, UncommonImagOp);

710

711

712

713 if (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||

714 Rotation == ComplexDeinterleavingRotation::Rotation_180)

715 PartialMatch.first = CommonOperand;

716 else

717 PartialMatch.second = CommonOperand;

718

719 if (!PartialMatch.first || !PartialMatch.second) {

720 LLVM_DEBUG(dbgs() << " - Incomplete partial match\n");

721 return nullptr;

722 }

723

724 CompositeNode *CommonNode =

725 identifyNode(PartialMatch.first, PartialMatch.second);

726 if (!CommonNode) {

727 LLVM_DEBUG(dbgs() << " - No CommonNode identified\n");

728 return nullptr;

729 }

730

731 CompositeNode *UncommonNode = identifyNode(UncommonRealOp, UncommonImagOp);

732 if (!UncommonNode) {

733 LLVM_DEBUG(dbgs() << " - No UncommonNode identified\n");

734 return nullptr;

735 }

736

737 CompositeNode *Node = prepareCompositeNode(

738 ComplexDeinterleavingOperation::CMulPartial, Real, Imag);

739 Node->Rotation = Rotation;

740 Node->addOperand(CommonNode);

741 Node->addOperand(UncommonNode);

742 return submitCompositeNode(Node);

743}

744

745ComplexDeinterleavingGraph::CompositeNode *

746ComplexDeinterleavingGraph::identifyPartialMul(Instruction *Real,

747 Instruction *Imag) {

748 LLVM_DEBUG(dbgs() << "identifyPartialMul " << *Real << " / " << *Imag

749 << "\n");

750

751

752 auto IsAdd = [](unsigned Op) {

753 return Op == Instruction::FAdd || Op == Instruction::Add;

754 };

755 auto IsSub = [](unsigned Op) {

756 return Op == Instruction::FSub || Op == Instruction::Sub;

757 };

760 Rotation = ComplexDeinterleavingRotation::Rotation_0;

762 Rotation = ComplexDeinterleavingRotation::Rotation_90;

764 Rotation = ComplexDeinterleavingRotation::Rotation_180;

766 Rotation = ComplexDeinterleavingRotation::Rotation_270;

767 else {

769 return nullptr;

770 }

771

775 LLVM_DEBUG(dbgs() << " - Contract is missing from the FastMath flags.\n");

776 return nullptr;

777 }

778

781 if (!RealMulI)

782 return nullptr;

785 if (!ImagMulI)

786 return nullptr;

787

789 LLVM_DEBUG(dbgs() << " - Mul instruction has multiple uses\n");

790 return nullptr;

791 }

792

797

798 Value *CommonOperand;

799 Value *UncommonRealOp;

800 Value *UncommonImagOp;

801

802 if (R0 == I0 || R0 == I1) {

803 CommonOperand = R0;

804 UncommonRealOp = R1;

805 } else if (R1 == I0 || R1 == I1) {

806 CommonOperand = R1;

807 UncommonRealOp = R0;

808 } else {

810 return nullptr;

811 }

812

813 UncommonImagOp = (CommonOperand == I0) ? I1 : I0;

814 if (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||

815 Rotation == ComplexDeinterleavingRotation::Rotation_270)

816 std::swap(UncommonRealOp, UncommonImagOp);

817

818 std::pair<Value *, Value *> PartialMatch(

819 (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||

820 Rotation == ComplexDeinterleavingRotation::Rotation_180)

821 ? CommonOperand

822 : nullptr,

823 (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||

824 Rotation == ComplexDeinterleavingRotation::Rotation_270)

825 ? CommonOperand

826 : nullptr);

827

830

831 if (!CRInst || !CIInst) {

832 LLVM_DEBUG(dbgs() << " - Common operands are not instructions.\n");

833 return nullptr;

834 }

835

836 CompositeNode *CNode =

837 identifyNodeWithImplicitAdd(CRInst, CIInst, PartialMatch);

838 if (!CNode) {

840 return nullptr;

841 }

842

843 CompositeNode *UncommonRes = identifyNode(UncommonRealOp, UncommonImagOp);

844 if (!UncommonRes) {

845 LLVM_DEBUG(dbgs() << " - No UncommonRes identified\n");

846 return nullptr;

847 }

848

849 assert(PartialMatch.first && PartialMatch.second);

850 CompositeNode *CommonRes =

851 identifyNode(PartialMatch.first, PartialMatch.second);

852 if (!CommonRes) {

853 LLVM_DEBUG(dbgs() << " - No CommonRes identified\n");

854 return nullptr;

855 }

856

857 CompositeNode *Node = prepareCompositeNode(

858 ComplexDeinterleavingOperation::CMulPartial, Real, Imag);

859 Node->Rotation = Rotation;

860 Node->addOperand(CommonRes);

861 Node->addOperand(UncommonRes);

862 Node->addOperand(CNode);

863 return submitCompositeNode(Node);

864}

865

866ComplexDeinterleavingGraph::CompositeNode *

867ComplexDeinterleavingGraph::identifyAdd(Instruction *Real, Instruction *Imag) {

868 LLVM_DEBUG(dbgs() << "identifyAdd " << *Real << " / " << *Imag << "\n");

869

870

872 if ((Real->getOpcode() == Instruction::FSub &&

873 Imag->getOpcode() == Instruction::FAdd) ||

874 (Real->getOpcode() == Instruction::Sub &&

875 Imag->getOpcode() == Instruction::Add))

876 Rotation = ComplexDeinterleavingRotation::Rotation_90;

877 else if ((Real->getOpcode() == Instruction::FAdd &&

878 Imag->getOpcode() == Instruction::FSub) ||

879 (Real->getOpcode() == Instruction::Add &&

880 Imag->getOpcode() == Instruction::Sub))

881 Rotation = ComplexDeinterleavingRotation::Rotation_270;

882 else {

883 LLVM_DEBUG(dbgs() << " - Unhandled case, rotation is not assigned.\n");

884 return nullptr;

885 }

886

891

892 if (!AR || !AI || !BR || !BI) {

893 LLVM_DEBUG(dbgs() << " - Not all operands are instructions.\n");

894 return nullptr;

895 }

896

897 CompositeNode *ResA = identifyNode(AR, AI);

898 if (!ResA) {

899 LLVM_DEBUG(dbgs() << " - AR/AI is not identified as a composite node.\n");

900 return nullptr;

901 }

902 CompositeNode *ResB = identifyNode(BR, BI);

903 if (!ResB) {

904 LLVM_DEBUG(dbgs() << " - BR/BI is not identified as a composite node.\n");

905 return nullptr;

906 }

907

908 CompositeNode *Node =

909 prepareCompositeNode(ComplexDeinterleavingOperation::CAdd, Real, Imag);

910 Node->Rotation = Rotation;

911 Node->addOperand(ResA);

912 Node->addOperand(ResB);

913 return submitCompositeNode(Node);

914}

915

917 unsigned OpcA = A->getOpcode();

918 unsigned OpcB = B->getOpcode();

919

920 return (OpcA == Instruction::FSub && OpcB == Instruction::FAdd) ||

921 (OpcA == Instruction::FAdd && OpcB == Instruction::FSub) ||

922 (OpcA == Instruction::Sub && OpcB == Instruction::Add) ||

923 (OpcA == Instruction::Add && OpcB == Instruction::Sub);

924}

925

932

934 switch (I->getOpcode()) {

935 case Instruction::FAdd:

936 case Instruction::FSub:

937 case Instruction::FMul:

938 case Instruction::FNeg:

939 case Instruction::Add:

940 case Instruction::Sub:

941 case Instruction::Mul:

942 return true;

943 default:

944 return false;

945 }

946}

947

948ComplexDeinterleavingGraph::CompositeNode *

949ComplexDeinterleavingGraph::identifySymmetricOperation(ComplexValues &Vals) {

951 unsigned FirstOpc = FirstReal->getOpcode();

952 for (auto &V : Vals) {

956 return nullptr;

957

960 return nullptr;

961

963 if (Real->getFastMathFlags() != FirstReal->getFastMathFlags() ||

965 return nullptr;

966 }

967

969 for (auto &V : Vals) {

973 }

974

975 CompositeNode *Op0 = identifyNode(OpVals);

976 CompositeNode *Op1 = nullptr;

977 if (Op0 == nullptr)

978 return nullptr;

979

980 if (FirstReal->isBinaryOp()) {

982 for (auto &V : Vals) {

986 }

987 Op1 = identifyNode(OpVals);

988 if (Op1 == nullptr)

989 return nullptr;

990 }

991

993 prepareCompositeNode(ComplexDeinterleavingOperation::Symmetric, Vals);

994 Node->Opcode = FirstReal->getOpcode();

996 Node->Flags = FirstReal->getFastMathFlags();

997

998 Node->addOperand(Op0);

999 if (FirstReal->isBinaryOp())

1000 Node->addOperand(Op1);

1001

1002 return submitCompositeNode(Node);

1003}

1004

1005ComplexDeinterleavingGraph::CompositeNode *

1006ComplexDeinterleavingGraph::identifyDotProduct(Value *V) {

1008 ComplexDeinterleavingOperation::CDot, V->getType())) {

1009 LLVM_DEBUG(dbgs() << "Target doesn't support complex deinterleaving "

1010 "operation CDot with the type "

1011 << *V->getType() << "\n");

1012 return nullptr;

1013 }

1014

1017

1018 CompositeNode *CN =

1019 prepareCompositeNode(ComplexDeinterleavingOperation::CDot, Inst, nullptr);

1020

1021 CompositeNode *ANode = nullptr;

1022

1023 const Intrinsic::ID PartialReduceInt = Intrinsic::vector_partial_reduce_add;

1024

1025 Value *AReal = nullptr;

1026 Value *AImag = nullptr;

1027 Value *BReal = nullptr;

1028 Value *BImag = nullptr;

1030

1031 auto UnwrapCast = [](Value *V) -> Value * {

1033 return CI->getOperand(0);

1034 return V;

1035 };

1036

1041

1046

1047 if (match(Inst, PatternRot0)) {

1048 CN->Rotation = ComplexDeinterleavingRotation::Rotation_0;

1049 } else if (match(Inst, PatternRot270)) {

1050 CN->Rotation = ComplexDeinterleavingRotation::Rotation_270;

1051 } else {

1053

1054

1055

1060

1061 if ( match (Inst, PatternRot90Rot180))

1062 return nullptr;

1063

1064 A0 = UnwrapCast(A0);

1065 A1 = UnwrapCast(A1);

1066

1067

1068 ANode = identifyNode(A0, A1);

1069 if (!ANode) {

1070

1071 ANode = identifyNode(A1, A0);

1072

1073 if (!ANode)

1074 return nullptr;

1075 CN->Rotation = ComplexDeinterleavingRotation::Rotation_90;

1076 AReal = A1;

1077 AImag = A0;

1078 } else {

1079 AReal = A0;

1080 AImag = A1;

1081 CN->Rotation = ComplexDeinterleavingRotation::Rotation_180;

1082 }

1083 }

1084

1085 AReal = UnwrapCast(AReal);

1086 AImag = UnwrapCast(AImag);

1087 BReal = UnwrapCast(BReal);

1088 BImag = UnwrapCast(BImag);

1089

1091 Type *ExpectedOperandTy = VectorType::getSubdividedVectorType(VTy, 2);

1092 if (AReal->getType() != ExpectedOperandTy)

1093 return nullptr;

1094 if (AImag->getType() != ExpectedOperandTy)

1095 return nullptr;

1096 if (BReal->getType() != ExpectedOperandTy)

1097 return nullptr;

1098 if (BImag->getType() != ExpectedOperandTy)

1099 return nullptr;

1100

1101 if (Phi->getType() != VTy && RealUser->getType() != VTy)

1102 return nullptr;

1103

1104 CompositeNode *Node = identifyNode(AReal, AImag);

1105

1106

1107

1108

1109 if (ANode && Node != ANode) {

1112 << "Identified node is different from previously identified node. "

1113 "Unable to confidently generate a complex operation node\n");

1114 return nullptr;

1115 }

1116

1117 CN->addOperand(Node);

1118 CN->addOperand(identifyNode(BReal, BImag));

1119 CN->addOperand(identifyNode(Phi, RealUser));

1120

1121 return submitCompositeNode(CN);

1122}

1123

1124ComplexDeinterleavingGraph::CompositeNode *

1125ComplexDeinterleavingGraph::identifyPartialReduction(Value *R, Value *I) {

1126

1128 return nullptr;

1129

1130 if (->hasUseList() || ->hasUseList())

1131 return nullptr;

1132

1133 auto CommonUser =

1134 findCommonBetweenCollections<Value *>(R->users(), I->users());

1135 if (!CommonUser)

1136 return nullptr;

1137

1139 if (!IInst || IInst->getIntrinsicID() != Intrinsic::vector_partial_reduce_add)

1140 return nullptr;

1141

1142 if (CompositeNode *CN = identifyDotProduct(IInst))

1143 return CN;

1144

1145 return nullptr;

1146}

1147

1148ComplexDeinterleavingGraph::CompositeNode *

1149ComplexDeinterleavingGraph::identifyNode(ComplexValues &Vals) {

1150 auto It = CachedResult.find(Vals);

1151 if (It != CachedResult.end()) {

1152 LLVM_DEBUG(dbgs() << " - Folding to existing node\n");

1153 return It->second;

1154 }

1155

1156 if (Vals.size() == 1) {

1157 assert(Factor == 2 && "Can only handle interleave factors of 2");

1158 Value *R = Vals[0].Real;

1159 Value *I = Vals[0].Imag;

1160 if (CompositeNode *CN = identifyPartialReduction(R, I))

1161 return CN;

1162 bool IsReduction = RealPHI == R && (!ImagPHI || ImagPHI == I);

1163 if (!IsReduction && R->getType() != I->getType())

1164 return nullptr;

1165 }

1166

1167 if (CompositeNode *CN = identifySplat(Vals))

1168 return CN;

1169

1170 for (auto &V : Vals) {

1173 if (!Real || !Imag)

1174 return nullptr;

1175 }

1176

1177 if (CompositeNode *CN = identifyDeinterleave(Vals))

1178 return CN;

1179

1180 if (Vals.size() == 1) {

1181 assert(Factor == 2 && "Can only handle interleave factors of 2");

1184 if (CompositeNode *CN = identifyPHINode(Real, Imag))

1185 return CN;

1186

1187 if (CompositeNode *CN = identifySelectNode(Real, Imag))

1188 return CN;

1189

1191 auto *NewVTy = VectorType::getDoubleElementsVectorType(VTy);

1192

1194 ComplexDeinterleavingOperation::CMulPartial, NewVTy);

1196 ComplexDeinterleavingOperation::CAdd, NewVTy);

1197

1199 if (CompositeNode *CN = identifyPartialMul(Real, Imag))

1200 return CN;

1201 }

1202

1204 if (CompositeNode *CN = identifyAdd(Real, Imag))

1205 return CN;

1206 }

1207

1208 if (HasCMulSupport && HasCAddSupport) {

1209 if (CompositeNode *CN = identifyReassocNodes(Real, Imag)) {

1210 return CN;

1211 }

1212 }

1213 }

1214

1215 if (CompositeNode *CN = identifySymmetricOperation(Vals))

1216 return CN;

1217

1218 LLVM_DEBUG(dbgs() << " - Not recognised as a valid pattern.\n");

1219 CachedResult[Vals] = nullptr;

1220 return nullptr;

1221}

1222

1223ComplexDeinterleavingGraph::CompositeNode *

1224ComplexDeinterleavingGraph::identifyReassocNodes(Instruction *Real,

1225 Instruction *Imag) {

1226 auto IsOperationSupported = [](unsigned Opcode) -> bool {

1227 return Opcode == Instruction::FAdd || Opcode == Instruction::FSub ||

1228 Opcode == Instruction::FNeg || Opcode == Instruction::Add ||

1229 Opcode == Instruction::Sub;

1230 };

1231

1232 if (!IsOperationSupported(Real->getOpcode()) ||

1233 !IsOperationSupported(Imag->getOpcode()))

1234 return nullptr;

1235

1236 std::optional Flags;

1239 LLVM_DEBUG(dbgs() << "The flags in Real and Imaginary instructions are "

1240 "not identical\n");

1241 return nullptr;

1242 }

1243

1245 if ( Flags ->allowReassoc()) {

1248 << "the 'Reassoc' attribute is missing in the FastMath flags\n");

1249 return nullptr;

1250 }

1251 }

1252

1253

1254

1255

1256 auto Collect = [&Flags](Instruction *Insn, SmallVectorImpl &Muls,

1257 AddendList &Addends) -> bool {

1259 SmallPtrSet<Value *, 8> Visited;

1260 while (!Worklist.empty()) {

1262 if (!Visited.insert(V).second)

1263 continue;

1264

1266 if () {

1267 Addends.emplace_back(V, IsPositive);

1268 continue;

1269 }

1270

1271

1272

1273

1274

1275

1276

1277 if (I != Insn && I->hasNUsesOrMore(2)) {

1278 LLVM_DEBUG(dbgs() << "Found potential sub-expression: " << *I << "\n");

1279 Addends.emplace_back(I, IsPositive);

1280 continue;

1281 }

1282 switch (I->getOpcode()) {

1283 case Instruction::FAdd:

1284 case Instruction::Add:

1285 Worklist.emplace_back(I->getOperand(1), IsPositive);

1286 Worklist.emplace_back(I->getOperand(0), IsPositive);

1287 break;

1288 case Instruction::FSub:

1289 Worklist.emplace_back(I->getOperand(1), !IsPositive);

1290 Worklist.emplace_back(I->getOperand(0), IsPositive);

1291 break;

1292 case Instruction::Sub:

1295 } else {

1296 Worklist.emplace_back(I->getOperand(1), !IsPositive);

1297 Worklist.emplace_back(I->getOperand(0), IsPositive);

1298 }

1299 break;

1300 case Instruction::FMul:

1301 case Instruction::Mul: {

1303 if (isNeg(I->getOperand(0))) {

1305 IsPositive = !IsPositive;

1306 } else {

1307 A = I->getOperand(0);

1308 }

1309

1310 if (isNeg(I->getOperand(1))) {

1312 IsPositive = !IsPositive;

1313 } else {

1314 B = I->getOperand(1);

1315 }

1316 Muls.push_back(Product{A, B, IsPositive});

1317 break;

1318 }

1319 case Instruction::FNeg:

1320 Worklist.emplace_back(I->getOperand(0), !IsPositive);

1321 break;

1322 default:

1323 Addends.emplace_back(I, IsPositive);

1324 continue;

1325 }

1326

1327 if (Flags && I->getFastMathFlags() != *Flags) {

1328 LLVM_DEBUG(dbgs() << "The instruction's fast math flags are "

1329 "inconsistent with the root instructions' flags: "

1330 << *I << "\n");

1331 return false;

1332 }

1333 }

1334 return true;

1335 };

1336

1338 AddendList RealAddends, ImagAddends;

1339 if (!Collect(Real, RealMuls, RealAddends) ||

1340 !Collect(Imag, ImagMuls, ImagAddends))

1341 return nullptr;

1342

1343 if (RealAddends.size() != ImagAddends.size())

1344 return nullptr;

1345

1346 CompositeNode *FinalNode = nullptr;

1347 if (!RealMuls.empty() || !ImagMuls.empty()) {

1348

1349

1350 FinalNode = extractPositiveAddend(RealAddends, ImagAddends);

1351 FinalNode = identifyMultiplications(RealMuls, ImagMuls, FinalNode);

1352 if (!FinalNode)

1353 return nullptr;

1354 }

1355

1356

1357 if (!RealAddends.empty() || !ImagAddends.empty()) {

1358 FinalNode = identifyAdditions(RealAddends, ImagAddends, Flags, FinalNode);

1359 if (!FinalNode)

1360 return nullptr;

1361 }

1362 assert(FinalNode && "FinalNode can not be nullptr here");

1363 assert(FinalNode->Vals.size() == 1);

1364

1365 FinalNode->Vals[0].Real = Real;

1366 FinalNode->Vals[0].Imag = Imag;

1367 submitCompositeNode(FinalNode);

1368 return FinalNode;

1369}

1370

1371bool ComplexDeinterleavingGraph::collectPartialMuls(

1373 SmallVectorImpl &PartialMulCandidates) {

1374

1375 auto FindCommonInstruction = [](const Product &Real,

1376 const Product &Imag) -> Value * {

1377 if (Real.Multiplicand == Imag.Multiplicand ||

1378 Real.Multiplicand == Imag.Multiplier)

1379 return Real.Multiplicand;

1380

1381 if (Real.Multiplier == Imag.Multiplicand ||

1382 Real.Multiplier == Imag.Multiplier)

1383 return Real.Multiplier;

1384

1385 return nullptr;

1386 };

1387

1388

1389

1390

1391

1392 for (unsigned i = 0; i < RealMuls.size(); ++i) {

1393 bool FoundCommon = false;

1394 for (unsigned j = 0; j < ImagMuls.size(); ++j) {

1395 auto *Common = FindCommonInstruction(RealMuls[i], ImagMuls[j]);

1396 if (!Common)

1397 continue;

1398

1399 auto *A = RealMuls[i].Multiplicand == Common ? RealMuls[i].Multiplier

1400 : RealMuls[i].Multiplicand;

1401 auto *B = ImagMuls[j].Multiplicand == Common ? ImagMuls[j].Multiplier

1402 : ImagMuls[j].Multiplicand;

1403

1404 auto Node = identifyNode(A, B);

1405 if (Node) {

1406 FoundCommon = true;

1407 PartialMulCandidates.push_back({Common, Node, i, j, false});

1408 }

1409

1410 Node = identifyNode(B, A);

1411 if (Node) {

1412 FoundCommon = true;

1413 PartialMulCandidates.push_back({Common, Node, i, j, true});

1414 }

1415 }

1416 if (!FoundCommon)

1417 return false;

1418 }

1419 return true;

1420}

1421

1422ComplexDeinterleavingGraph::CompositeNode *

1423ComplexDeinterleavingGraph::identifyMultiplications(

1424 SmallVectorImpl &RealMuls, SmallVectorImpl &ImagMuls,

1426 if (RealMuls.size() != ImagMuls.size())

1427 return nullptr;

1428

1430 if (!collectPartialMuls(RealMuls, ImagMuls, Info))

1431 return nullptr;

1432

1433

1434 DenseMap<Value *, CompositeNode *> CommonToNode;

1435 SmallVector Processed(Info.size(), false);

1436 for (unsigned I = 0; I < Info.size(); ++I) {

1437 if (Processed[I])

1438 continue;

1439

1440 PartialMulCandidate &InfoA = Info[I];

1441 for (unsigned J = I + 1; J < Info.size(); ++J) {

1442 if (Processed[J])

1443 continue;

1444

1445 PartialMulCandidate &InfoB = Info[J];

1446 auto *InfoReal = &InfoA;

1447 auto *InfoImag = &InfoB;

1448

1449 auto NodeFromCommon = identifyNode(InfoReal->Common, InfoImag->Common);

1450 if (!NodeFromCommon) {

1452 NodeFromCommon = identifyNode(InfoReal->Common, InfoImag->Common);

1453 }

1454 if (!NodeFromCommon)

1455 continue;

1456

1457 CommonToNode[InfoReal->Common] = NodeFromCommon;

1458 CommonToNode[InfoImag->Common] = NodeFromCommon;

1459 Processed[I] = true;

1460 Processed[J] = true;

1461 }

1462 }

1463

1464 SmallVector ProcessedReal(RealMuls.size(), false);

1465 SmallVector ProcessedImag(ImagMuls.size(), false);

1467 for (auto &PMI : Info) {

1468 if (ProcessedReal[PMI.RealIdx] || ProcessedImag[PMI.ImagIdx])

1469 continue;

1470

1471 auto It = CommonToNode.find(PMI.Common);

1472

1473

1474 if (It == CommonToNode.end()) {

1476 dbgs() << "Unprocessed independent partial multiplication:\n";

1477 for (auto *Mul : {&RealMuls[PMI.RealIdx], &RealMuls[PMI.RealIdx]})

1478 dbgs().indent(4) << (Mul->IsPositive ? "+" : "-") << *Mul->Multiplier

1479 << " multiplied by " << *Mul->Multiplicand << "\n";

1480 });

1481 return nullptr;

1482 }

1483

1484 auto &RealMul = RealMuls[PMI.RealIdx];

1485 auto &ImagMul = ImagMuls[PMI.ImagIdx];

1486

1487 auto NodeA = It->second;

1488 auto NodeB = PMI.Node;

1489 auto IsMultiplicandReal = PMI.Common == NodeA->Vals[0].Real;

1490

1491

1492

1493

1494

1495

1496

1497

1498

1499

1500

1501

1502

1503

1504 if ((IsMultiplicandReal && PMI.IsNodeInverted) ||

1505 (!IsMultiplicandReal && !PMI.IsNodeInverted))

1506 continue;

1507

1508

1510 if (IsMultiplicandReal) {

1511

1512 if (RealMul.IsPositive && ImagMul.IsPositive)

1514 else if (!RealMul.IsPositive && !ImagMul.IsPositive)

1516 else

1517 continue;

1518

1519 } else {

1520

1521 if (!RealMul.IsPositive && ImagMul.IsPositive)

1523 else if (RealMul.IsPositive && !ImagMul.IsPositive)

1525 else

1526 continue;

1527 }

1528

1530 dbgs() << "Identified partial multiplication (X, Y) * (U, V):\n";

1531 dbgs().indent(4) << "X: " << *NodeA->Vals[0].Real << "\n";

1532 dbgs().indent(4) << "Y: " << *NodeA->Vals[0].Imag << "\n";

1533 dbgs().indent(4) << "U: " << *NodeB->Vals[0].Real << "\n";

1534 dbgs().indent(4) << "V: " << *NodeB->Vals[0].Imag << "\n";

1535 dbgs().indent(4) << "Rotation - " << (int)Rotation * 90 << "\n";

1536 });

1537

1538 CompositeNode *NodeMul = prepareCompositeNode(

1539 ComplexDeinterleavingOperation::CMulPartial, nullptr, nullptr);

1540 NodeMul->Rotation = Rotation;

1541 NodeMul->addOperand(NodeA);

1542 NodeMul->addOperand(NodeB);

1543 if (Result)

1544 NodeMul->addOperand(Result);

1545 submitCompositeNode(NodeMul);

1547 ProcessedReal[PMI.RealIdx] = true;

1548 ProcessedImag[PMI.ImagIdx] = true;

1549 }

1550

1551

1552 if ( $all\_of$ (ProcessedReal, [](bool V) { return V; }) ||

1553 $all\_of$ (ProcessedImag, [](bool V) { return V; })) {

1554

1555

1556

1558 dbgs() << "Unprocessed products (Real):\n";

1559 for (size_t i = 0; i < ProcessedReal.size(); ++i) {

1560 if (!ProcessedReal[i])

1561 dbgs().indent(4) << (RealMuls[i].IsPositive ? "+" : "-")

1562 << *RealMuls[i].Multiplier << " multiplied by "

1563 << *RealMuls[i].Multiplicand << "\n";

1564 }

1565 dbgs() << "Unprocessed products (Imag):\n";

1566 for (size_t i = 0; i < ProcessedImag.size(); ++i) {

1567 if (!ProcessedImag[i])

1568 dbgs().indent(4) << (ImagMuls[i].IsPositive ? "+" : "-")

1569 << *ImagMuls[i].Multiplier << " multiplied by "

1570 << *ImagMuls[i].Multiplicand << "\n";

1571 }

1572 });

1573 return nullptr;

1574 }

1575

1577}

1578

1579ComplexDeinterleavingGraph::CompositeNode *

1580ComplexDeinterleavingGraph::identifyAdditions(

1581 AddendList &RealAddends, AddendList &ImagAddends,

1582 std::optional Flags, CompositeNode *Accumulator = nullptr) {

1583 if (RealAddends.size() != ImagAddends.size())

1584 return nullptr;

1585

1586 CompositeNode *Result = nullptr;

1587

1590

1591 else

1592 Result = extractPositiveAddend(RealAddends, ImagAddends);

1593

1594 if (!Result)

1595 return nullptr;

1596

1597 while (!RealAddends.empty()) {

1598 auto ItR = RealAddends.begin();

1599 auto [R, IsPositiveR] = *ItR;

1600

1601 bool FoundImag = false;

1602 for (auto ItI = ImagAddends.begin(); ItI != ImagAddends.end(); ++ItI) {

1603 auto [I, IsPositiveI] = *ItI;

1605 if (IsPositiveR && IsPositiveI)

1606 Rotation = ComplexDeinterleavingRotation::Rotation_0;

1607 else if (!IsPositiveR && IsPositiveI)

1608 Rotation = ComplexDeinterleavingRotation::Rotation_90;

1609 else if (!IsPositiveR && !IsPositiveI)

1610 Rotation = ComplexDeinterleavingRotation::Rotation_180;

1611 else

1612 Rotation = ComplexDeinterleavingRotation::Rotation_270;

1613

1614 CompositeNode *AddNode = nullptr;

1615 if (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||

1616 Rotation == ComplexDeinterleavingRotation::Rotation_180) {

1617 AddNode = identifyNode(R, I);

1618 } else {

1619 AddNode = identifyNode(I, R);

1620 }

1621 if (AddNode) {

1623 dbgs() << "Identified addition:\n";

1624 dbgs().indent(4) << "X: " << *R << "\n";

1625 dbgs().indent(4) << "Y: " << *I << "\n";

1626 dbgs().indent(4) << "Rotation - " << (int)Rotation * 90 << "\n";

1627 });

1628

1629 CompositeNode *TmpNode = nullptr;

1631 TmpNode = prepareCompositeNode(

1632 ComplexDeinterleavingOperation::Symmetric, nullptr, nullptr);

1633 if (Flags) {

1634 TmpNode->Opcode = Instruction::FAdd;

1635 TmpNode->Flags = *Flags;

1636 } else {

1637 TmpNode->Opcode = Instruction::Add;

1638 }

1639 } else if (Rotation ==

1641 TmpNode = prepareCompositeNode(

1642 ComplexDeinterleavingOperation::Symmetric, nullptr, nullptr);

1643 if (Flags) {

1644 TmpNode->Opcode = Instruction::FSub;

1645 TmpNode->Flags = *Flags;

1646 } else {

1647 TmpNode->Opcode = Instruction::Sub;

1648 }

1649 } else {

1650 TmpNode = prepareCompositeNode(ComplexDeinterleavingOperation::CAdd,

1651 nullptr, nullptr);

1652 TmpNode->Rotation = Rotation;

1653 }

1654

1655 TmpNode->addOperand(Result);

1656 TmpNode->addOperand(AddNode);

1657 submitCompositeNode(TmpNode);

1659 RealAddends.erase(ItR);

1660 ImagAddends.erase(ItI);

1661 FoundImag = true;

1662 break;

1663 }

1664 }

1665 if (!FoundImag)

1666 return nullptr;

1667 }

1669}

1670

1671ComplexDeinterleavingGraph::CompositeNode *

1672ComplexDeinterleavingGraph::extractPositiveAddend(AddendList &RealAddends,

1673 AddendList &ImagAddends) {

1674 for (auto ItR = RealAddends.begin(); ItR != RealAddends.end(); ++ItR) {

1675 for (auto ItI = ImagAddends.begin(); ItI != ImagAddends.end(); ++ItI) {

1676 auto [R, IsPositiveR] = *ItR;

1677 auto [I, IsPositiveI] = *ItI;

1678 if (IsPositiveR && IsPositiveI) {

1679 auto Result = identifyNode(R, I);

1680 if (Result) {

1681 RealAddends.erase(ItR);

1682 ImagAddends.erase(ItI);

1684 }

1685 }

1686 }

1687 }

1688 return nullptr;

1689}

1690

1691bool ComplexDeinterleavingGraph::identifyNodes(Instruction *RootI) {

1692

1693

1694

1695

1696 auto It = RootToNode.find(RootI);

1697 if (It != RootToNode.end()) {

1698 auto RootNode = It->second;

1699 assert(RootNode->Operation ==

1700 ComplexDeinterleavingOperation::ReductionOperation ||

1701 RootNode->Operation ==

1702 ComplexDeinterleavingOperation::ReductionSingle);

1703 assert(RootNode->Vals.size() == 1 &&

1704 "Cannot handle reductions involving multiple complex values");

1705

1706

1708 auto *I = RootNode->Vals[0].Imag ? cast(RootNode->Vals[0].Imag)

1709 : nullptr;

1710

1712 if (I)

1713 ReplacementAnchor = R->comesBefore(I) ? I : R;

1714 else

1715 ReplacementAnchor = R;

1716

1717 if (ReplacementAnchor != RootI)

1718 return false;

1720 return true;

1721 }

1722

1723 auto RootNode = identifyRoot(RootI);

1724 if (!RootNode)

1725 return false;

1726

1730 dbgs() << "Complex deinterleaving graph for " << F->getName()

1731 << "::" << B->getName() << ".\n";

1733 dbgs() << "\n";

1734 });

1735 RootToNode[RootI] = RootNode;

1737 return true;

1738}

1739

1740bool ComplexDeinterleavingGraph::collectPotentialReductions(BasicBlock *B) {

1741 bool FoundPotentialReduction = false;

1742 if (Factor != 2)

1743 return false;

1744

1746 if (!Br || Br->getNumSuccessors() != 2)

1747 return false;

1748

1749

1750 if (Br->getSuccessor(0) != B && Br->getSuccessor(1) != B)

1751 return false;

1752

1753 for (auto &PHI : B->phis()) {

1754 if (PHI.getNumIncomingValues() != 2)

1755 continue;

1756

1757 if ( PHI .getType()->isVectorTy())

1758 continue;

1759

1761 if (!ReductionOp)

1762 continue;

1763

1764

1766 auto NumUsers = 0u;

1767 for (auto *U : ReductionOp->users()) {

1768 ++NumUsers;

1769 if (U == &PHI)

1770 continue;

1772 }

1773

1774 if (NumUsers != 2 || !FinalReduction || FinalReduction->getParent() == B ||

1776 continue;

1777

1778 ReductionInfo[ReductionOp] = {&PHI, FinalReduction};

1779 BackEdge = B;

1780 auto BackEdgeIdx = PHI.getBasicBlockIndex(B);

1781 auto IncomingIdx = BackEdgeIdx == 0 ? 1 : 0;

1782 Incoming = PHI.getIncomingBlock(IncomingIdx);

1783 FoundPotentialReduction = true;

1784

1785

1786

1787 if (auto *InitPHI =

1789 FinalInstructions.insert(InitPHI);

1790 }

1791 return FoundPotentialReduction;

1792}

1793

1794void ComplexDeinterleavingGraph::identifyReductionNodes() {

1795 assert(Factor == 2 && "Cannot handle multiple complex values");

1796

1797 SmallVector Processed(ReductionInfo.size(), false);

1799 for (auto &P : ReductionInfo)

1800 OperationInstruction.push_back(P.first);

1801

1802

1803

1804 for (size_t i = 0; i < OperationInstruction.size(); ++i) {

1805 if (Processed[i])

1806 continue;

1807 for (size_t j = i + 1; j < OperationInstruction.size(); ++j) {

1808 if (Processed[j])

1809 continue;

1810 auto *Real = OperationInstruction[i];

1811 auto *Imag = OperationInstruction[j];

1812 if (Real->getType() != Imag->getType())

1813 continue;

1814

1815 RealPHI = ReductionInfo[Real].first;

1816 ImagPHI = ReductionInfo[Imag].first;

1817 PHIsFound = false;

1818 auto Node = identifyNode(Real, Imag);

1819 if (!Node) {

1822 Node = identifyNode(Real, Imag);

1823 }

1824

1825

1826

1827

1828 if (Node && PHIsFound) {

1829 LLVM_DEBUG(dbgs() << "Identified reduction starting from instructions: "

1830 << *Real << " / " << *Imag << "\n");

1831 Processed[i] = true;

1832 Processed[j] = true;

1833 auto RootNode = prepareCompositeNode(

1834 ComplexDeinterleavingOperation::ReductionOperation, Real, Imag);

1835 RootNode->addOperand(Node);

1836 RootToNode[Real] = RootNode;

1837 RootToNode[Imag] = RootNode;

1838 submitCompositeNode(RootNode);

1839 break;

1840 }

1841 }

1842

1843 auto *Real = OperationInstruction[i];

1844

1845

1846 if (Processed[i] || Real->getNumOperands() < 2)

1847 continue;

1848

1849

1850 if (!ReductionInfo[Real].second->getType()->isIntegerTy())

1851 continue;

1852

1853 RealPHI = ReductionInfo[Real].first;

1854 ImagPHI = nullptr;

1855 PHIsFound = false;

1856 auto Node = identifyNode(Real->getOperand(0), Real->getOperand(1));

1857 if (Node && PHIsFound) {

1859 dbgs() << "Identified single reduction starting from instruction: "

1860 << *Real << "/" << *ReductionInfo[Real].second << "\n");

1861

1862

1863

1864

1865

1866

1867

1868

1869 if (ReductionInfo[Real].second->getType()->isVectorTy())

1870 continue;

1871

1872 Processed[i] = true;

1873 auto RootNode = prepareCompositeNode(

1874 ComplexDeinterleavingOperation::ReductionSingle, Real, nullptr);

1875 RootNode->addOperand(Node);

1876 RootToNode[Real] = RootNode;

1877 submitCompositeNode(RootNode);

1878 }

1879 }

1880

1881 RealPHI = nullptr;

1882 ImagPHI = nullptr;

1883}

1884

1885bool ComplexDeinterleavingGraph::checkNodes() {

1886 bool FoundDeinterleaveNode = false;

1887 for (CompositeNode *N : CompositeNodes) {

1888 if (->areOperandsValid())

1889 return false;

1890

1891 if (N->Operation == ComplexDeinterleavingOperation::Deinterleave)

1892 FoundDeinterleaveNode = true;

1893 }

1894

1895

1896

1897 if (!FoundDeinterleaveNode) {

1899 dbgs() << "Couldn't find a deinterleave node within the graph, cannot "

1900 "guarantee safety during graph transformation.\n");

1901 return false;

1902 }

1903

1904

1905 SmallPtrSet<Instruction *, 16> AllInstructions;

1906 SmallVector<Instruction *, 8> Worklist;

1907 for (auto &Pair : RootToNode)

1909

1910

1911

1912 while (!Worklist.empty()) {

1914

1915 if (!AllInstructions.insert(I).second)

1916 continue;

1917

1918 for (Value *Op : I->operands()) {

1920 if (!FinalInstructions.count(I))

1922 }

1923 }

1924 }

1925

1926

1927 for (auto *I : AllInstructions) {

1928

1929 if (RootToNode.count(I))

1930 continue;

1931

1932 for (User *U : I->users()) {

1934 continue;

1935

1936

1938 break;

1939 }

1940 }

1941

1942

1943

1944 SmallPtrSet<Instruction *, 16> Visited;

1945 while (!Worklist.empty()) {

1947 if (!Visited.insert(I).second)

1948 continue;

1949

1950

1951

1952 if (RootToNode.count(I)) {

1954 << " could be deinterleaved but its chain of complex "

1955 "operations have an outside user\n");

1956 RootToNode.erase(I);

1957 }

1958

1959 if (!AllInstructions.count(I) || FinalInstructions.count(I))

1960 continue;

1961

1962 for (User *U : I->users())

1964

1965 for (Value *Op : I->operands()) {

1968 }

1969 }

1970 return !RootToNode.empty();

1971}

1972

1973ComplexDeinterleavingGraph::CompositeNode *

1974ComplexDeinterleavingGraph::identifyRoot(Instruction *RootI) {

1978 return nullptr;

1979

1981 for (unsigned I = 0; I < Factor; I += 2) {

1984 if (!Real || !Imag)

1985 return nullptr;

1987 }

1988

1989 ComplexDeinterleavingGraph::CompositeNode *Node1 = identifyNode(Vals);

1990 if (!Node1)

1991 return nullptr;

1992 return Node1;

1993 }

1994

1995

1996

1997

1998

1999

2000 if (Factor != 2)

2001 return nullptr;

2002

2004 if (!SVI)

2005 return nullptr;

2006

2007

2008

2010 return nullptr;

2011

2015 return nullptr;

2016

2017 return identifyNode(Real, Imag);

2018}

2019

2020ComplexDeinterleavingGraph::CompositeNode *

2021ComplexDeinterleavingGraph::identifyDeinterleave(ComplexValues &Vals) {

2023

2024

2025 auto CheckExtract = [&](Value *V, unsigned ExpectedIdx,

2026 Instruction *ExpectedInsn) -> ExtractValueInst * {

2028 if (!EVI || EVI->getNumIndices() != 1 ||

2029 EVI->getIndices()[0] != ExpectedIdx ||

2031 (ExpectedInsn && ExpectedInsn != EVI->getAggregateOperand()))

2032 return nullptr;

2033 return EVI;

2034 };

2035

2036 for (unsigned Idx = 0; Idx < Vals.size(); Idx++) {

2037 ExtractValueInst *RealEVI = CheckExtract(Vals[Idx].Real, Idx * 2, II);

2038 if (RealEVI && Idx == 0)

2040 if (!RealEVI || !CheckExtract(Vals[Idx].Imag, (Idx * 2) + 1, II)) {

2041 II = nullptr;

2042 break;

2043 }

2044 }

2045

2047 if (IntrinsicII->getIntrinsicID() !=

2049 return nullptr;

2050

2051

2052 CompositeNode *PlaceholderNode = prepareCompositeNode(

2054 PlaceholderNode->ReplacementNode = II->getOperand(0);

2055 for (auto &V : Vals) {

2058 }

2059 return submitCompositeNode(PlaceholderNode);

2060 }

2061

2062 if (Vals.size() != 1)

2063 return nullptr;

2064

2065 Value *Real = Vals[0].Real;

2066 Value *Imag = Vals[0].Imag;

2069 if (!RealShuffle || !ImagShuffle) {

2070 if (RealShuffle || ImagShuffle)

2071 LLVM_DEBUG(dbgs() << " - There's a shuffle where there shouldn't be.\n");

2072 return nullptr;

2073 }

2074

2075 Value *RealOp1 = RealShuffle->getOperand(1);

2077 LLVM_DEBUG(dbgs() << " - RealOp1 is not undef or zero.\n");

2078 return nullptr;

2079 }

2080 Value *ImagOp1 = ImagShuffle->getOperand(1);

2082 LLVM_DEBUG(dbgs() << " - ImagOp1 is not undef or zero.\n");

2083 return nullptr;

2084 }

2085

2086 Value *RealOp0 = RealShuffle->getOperand(0);

2087 Value *ImagOp0 = ImagShuffle->getOperand(0);

2088

2089 if (RealOp0 != ImagOp0) {

2090 LLVM_DEBUG(dbgs() << " - Shuffle operands are not equal.\n");

2091 return nullptr;

2092 }

2093

2094 ArrayRef RealMask = RealShuffle->getShuffleMask();

2095 ArrayRef ImagMask = ImagShuffle->getShuffleMask();

2097 LLVM_DEBUG(dbgs() << " - Masks are not deinterleaving.\n");

2098 return nullptr;

2099 }

2100

2101 if (RealMask[0] != 0 || ImagMask[0] != 1) {

2102 LLVM_DEBUG(dbgs() << " - Masks do not have the correct initial value.\n");

2103 return nullptr;

2104 }

2105

2106

2107

2108 auto CheckType = [&](ShuffleVectorInst *Shuffle) {

2109 Value *Op = Shuffle->getOperand(0);

2112

2113 if (OpTy->getScalarType() != ShuffleTy->getScalarType())

2114 return false;

2115 if ((ShuffleTy->getNumElements() * 2) != OpTy->getNumElements())

2116 return false;

2117

2118 return true;

2119 };

2120

2121 auto CheckDeinterleavingShuffle = [&](ShuffleVectorInst *Shuffle) -> bool {

2123 return false;

2124

2125 ArrayRef Mask = Shuffle->getShuffleMask();

2127

2128 Value *Op = Shuffle->getOperand(0);

2130 int NumElements = OpTy->getNumElements();

2131

2132

2133

2134 return Last < NumElements;

2135 };

2136

2137 if (RealShuffle->getType() != ImagShuffle->getType()) {

2138 LLVM_DEBUG(dbgs() << " - Shuffle types aren't equal.\n");

2139 return nullptr;

2140 }

2141 if (!CheckDeinterleavingShuffle(RealShuffle)) {

2142 LLVM_DEBUG(dbgs() << " - RealShuffle is invalid type.\n");

2143 return nullptr;

2144 }

2145 if (!CheckDeinterleavingShuffle(ImagShuffle)) {

2146 LLVM_DEBUG(dbgs() << " - ImagShuffle is invalid type.\n");

2147 return nullptr;

2148 }

2149

2150 CompositeNode *PlaceholderNode =

2152 RealShuffle, ImagShuffle);

2153 PlaceholderNode->ReplacementNode = RealShuffle->getOperand(0);

2154 FinalInstructions.insert(RealShuffle);

2155 FinalInstructions.insert(ImagShuffle);

2156 return submitCompositeNode(PlaceholderNode);

2157}

2158

2159ComplexDeinterleavingGraph::CompositeNode *

2160ComplexDeinterleavingGraph::identifySplat(ComplexValues &Vals) {

2161 auto IsSplat = [](Value *V) -> bool {

2162

2164 return true;

2165

2168

2170 ArrayRef Mask;

2171

2172

2174 if (Const->getOpcode() != Instruction::ShuffleVector)

2175 return false;

2179 VTy = Shuf->getType();

2180 Mask = Shuf->getShuffleMask();

2181 } else {

2182 return false;

2183 }

2184

2185

2186

2187

2188 if (!VTy->isScalableTy() && VTy->getElementCount().getKnownMinValue() == 1)

2189 return false;

2190

2192 };

2193

2194

2195

2196

2198 BasicBlock *FirstBB = FirstValAsInstruction->getParent();

2199 for (auto &V : Vals) {

2200 if (!IsSplat(V.Real) || !IsSplat(V.Imag))

2201 return nullptr;

2202

2205 if (!Real || !Imag || Real->getParent() != FirstBB ||

2206 Imag->getParent() != FirstBB)

2207 return nullptr;

2208 }

2209 } else {

2210 for (auto &V : Vals) {

2213 return nullptr;

2214 }

2215 }

2216

2217 for (auto &V : Vals) {

2220 if (Real && Imag) {

2221 FinalInstructions.insert(Real);

2222 FinalInstructions.insert(Imag);

2223 }

2224 }

2225 CompositeNode *PlaceholderNode =

2226 prepareCompositeNode(ComplexDeinterleavingOperation::Splat, Vals);

2227 return submitCompositeNode(PlaceholderNode);

2228}

2229

2230ComplexDeinterleavingGraph::CompositeNode *

2231ComplexDeinterleavingGraph::identifyPHINode(Instruction *Real,

2232 Instruction *Imag) {

2233 if (Real != RealPHI || (ImagPHI && Imag != ImagPHI))

2234 return nullptr;

2235

2236 PHIsFound = true;

2237 CompositeNode *PlaceholderNode = prepareCompositeNode(

2238 ComplexDeinterleavingOperation::ReductionPHI, Real, Imag);

2239 return submitCompositeNode(PlaceholderNode);

2240}

2241

2242ComplexDeinterleavingGraph::CompositeNode *

2243ComplexDeinterleavingGraph::identifySelectNode(Instruction *Real,

2244 Instruction *Imag) {

2247 if (!SelectReal || !SelectImag)

2248 return nullptr;

2249

2256 return nullptr;

2257

2258 if (MaskA != MaskB && !MaskA->isIdenticalTo(MaskB))

2259 return nullptr;

2260

2262 return nullptr;

2263

2264 auto NodeA = identifyNode(AR, AI);

2265 if (!NodeA)

2266 return nullptr;

2267

2268 auto NodeB = identifyNode(RA, BI);

2269 if (!NodeB)

2270 return nullptr;

2271

2272 CompositeNode *PlaceholderNode = prepareCompositeNode(

2273 ComplexDeinterleavingOperation::ReductionSelect, Real, Imag);

2274 PlaceholderNode->addOperand(NodeA);

2275 PlaceholderNode->addOperand(NodeB);

2276 FinalInstructions.insert(MaskA);

2277 FinalInstructions.insert(MaskB);

2278 return submitCompositeNode(PlaceholderNode);

2279}

2280

2282 std::optional Flags,

2285 switch (Opcode) {

2286 case Instruction::FNeg:

2287 I = B.CreateFNeg(InputA);

2288 break;

2289 case Instruction::FAdd:

2290 I = B.CreateFAdd(InputA, InputB);

2291 break;

2292 case Instruction::Add:

2293 I = B.CreateAdd(InputA, InputB);

2294 break;

2295 case Instruction::FSub:

2296 I = B.CreateFSub(InputA, InputB);

2297 break;

2298 case Instruction::Sub:

2299 I = B.CreateSub(InputA, InputB);

2300 break;

2301 case Instruction::FMul:

2302 I = B.CreateFMul(InputA, InputB);

2303 break;

2304 case Instruction::Mul:

2305 I = B.CreateMul(InputA, InputB);

2306 break;

2307 default:

2309 }

2310 if (Flags)

2312 return I;

2313}

2314

2315Value *ComplexDeinterleavingGraph::replaceNode(IRBuilderBase &Builder,

2316 CompositeNode *Node) {

2317 if (Node->ReplacementNode)

2318 return Node->ReplacementNode;

2319

2320 auto ReplaceOperandIfExist = [&](CompositeNode *Node,

2321 unsigned Idx) -> Value * {

2322 return Node->Operands.size() > Idx

2323 ? replaceNode(Builder, Node->Operands[Idx])

2324 : nullptr;

2325 };

2326

2327 Value *ReplacementNode = nullptr;

2328 switch (Node->Operation) {

2329 case ComplexDeinterleavingOperation::CDot: {

2330 Value *Input0 = ReplaceOperandIfExist(Node, 0);

2331 Value *Input1 = ReplaceOperandIfExist(Node, 1);

2334 "Node inputs need to be of the same type"));

2337 break;

2338 }

2339 case ComplexDeinterleavingOperation::CAdd:

2340 case ComplexDeinterleavingOperation::CMulPartial:

2341 case ComplexDeinterleavingOperation::Symmetric: {

2342 Value *Input0 = ReplaceOperandIfExist(Node, 0);

2343 Value *Input1 = ReplaceOperandIfExist(Node, 1);

2346 "Node inputs need to be of the same type"));

2349 "Accumulator and input need to be of the same type"));

2350 if (Node->Operation == ComplexDeinterleavingOperation::Symmetric)

2352 Input0, Input1);

2353 else

2355 Builder, Node->Operation, Node->Rotation, Input0, Input1,

2357 break;

2358 }

2359 case ComplexDeinterleavingOperation::Deinterleave:

2360 llvm_unreachable("Deinterleave node should already have ReplacementNode");

2361 break;

2362 case ComplexDeinterleavingOperation::Splat: {

2364 for (auto &V : Node->Vals) {

2365 Ops.push_back(V.Real);

2366 Ops.push_back(V.Imag);

2367 }

2370 if (R && I) {

2371

2373 for (auto V : Node->Vals) {

2378 }

2379 InsertPoint = InsertPoint->getNextNode();

2381 ReplacementNode = IRB.CreateVectorInterleave(Ops);

2382 } else {

2384 }

2385 break;

2386 }

2387 case ComplexDeinterleavingOperation::ReductionPHI: {

2388

2389

2392 auto *NewVTy = VectorType::getDoubleElementsVectorType(VTy);

2394 OldToNewPHI[OldPHI] = NewPHI;

2395 ReplacementNode = NewPHI;

2396 break;

2397 }

2398 case ComplexDeinterleavingOperation::ReductionSingle:

2399 ReplacementNode = replaceNode(Builder, Node->Operands[0]);

2400 processReductionSingle(ReplacementNode, Node);

2401 break;

2402 case ComplexDeinterleavingOperation::ReductionOperation:

2403 ReplacementNode = replaceNode(Builder, Node->Operands[0]);

2404 processReductionOperation(ReplacementNode, Node);

2405 break;

2406 case ComplexDeinterleavingOperation::ReductionSelect: {

2409 auto *A = replaceNode(Builder, Node->Operands[0]);

2410 auto *B = replaceNode(Builder, Node->Operands[1]);

2412 ReplacementNode = Builder.CreateSelect(NewMask, A, B);

2413 break;

2414 }

2415 }

2416

2417 assert(ReplacementNode && "Target failed to create Intrinsic call.");

2418 NumComplexTransformations += 1;

2419 Node->ReplacementNode = ReplacementNode;

2420 return ReplacementNode;

2421}

2422

2423void ComplexDeinterleavingGraph::processReductionSingle(

2424 Value *OperationReplacement, CompositeNode *Node) {

2426 auto *OldPHI = ReductionInfo[Real].first;

2427 auto *NewPHI = OldToNewPHI[OldPHI];

2429 auto *NewVTy = VectorType::getDoubleElementsVectorType(VTy);

2430

2431 Value *Init = OldPHI->getIncomingValueForBlock(Incoming);

2432

2434

2435 Value *NewInit = nullptr;

2437 if (C->isZeroValue())

2439 }

2440

2441 if (!NewInit)

2442 NewInit =

2444

2445 NewPHI->addIncoming(NewInit, Incoming);

2446 NewPHI->addIncoming(OperationReplacement, BackEdge);

2447

2448 auto *FinalReduction = ReductionInfo[Real].second;

2450

2451 auto *AddReduce = Builder.CreateAddReduce(OperationReplacement);

2453}

2454

2455void ComplexDeinterleavingGraph::processReductionOperation(

2456 Value *OperationReplacement, CompositeNode *Node) {

2459 auto *OldPHIReal = ReductionInfo[Real].first;

2460 auto *OldPHIImag = ReductionInfo[Imag].first;

2461 auto *NewPHI = OldToNewPHI[OldPHIReal];

2462

2463

2464 Value *InitReal = OldPHIReal->getIncomingValueForBlock(Incoming);

2465 Value *InitImag = OldPHIImag->getIncomingValueForBlock(Incoming);

2466

2469

2470 NewPHI->addIncoming(NewInit, Incoming);

2471 NewPHI->addIncoming(OperationReplacement, BackEdge);

2472

2473

2474

2475 auto *FinalReductionReal = ReductionInfo[Real].second;

2476 auto *FinalReductionImag = ReductionInfo[Imag].second;

2477

2479 &*FinalReductionReal->getParent()->getFirstInsertionPt());

2481 OperationReplacement->getType(),

2482 OperationReplacement);

2483

2485 FinalReductionReal->replaceUsesOfWith(Real, NewReal);

2486

2489 FinalReductionImag->replaceUsesOfWith(Imag, NewImag);

2490}

2491

2492void ComplexDeinterleavingGraph::replaceNodes() {

2493 SmallVector<Instruction *, 16> DeadInstrRoots;

2494 for (auto *RootInstruction : OrderedRoots) {

2495

2496

2497 if (!RootToNode.count(RootInstruction))

2498 continue;

2499

2501 auto RootNode = RootToNode[RootInstruction];

2502 Value *R = replaceNode(Builder, RootNode);

2503

2504 if (RootNode->Operation ==

2505 ComplexDeinterleavingOperation::ReductionOperation) {

2508 ReductionInfo[RootReal].first->removeIncomingValue(BackEdge);

2509 ReductionInfo[RootImag].first->removeIncomingValue(BackEdge);

2510 DeadInstrRoots.push_back(RootReal);

2511 DeadInstrRoots.push_back(RootImag);

2512 } else if (RootNode->Operation ==

2513 ComplexDeinterleavingOperation::ReductionSingle) {

2515 auto &Info = ReductionInfo[RootInst];

2516 Info.first->removeIncomingValue(BackEdge);

2518 } else {

2519 assert(R && "Unable to find replacement for RootInstruction");

2520 DeadInstrRoots.push_back(RootInstruction);

2521 RootInstruction->replaceAllUsesWith(R);

2522 }

2523 }

2524

2525 for (auto *I : DeadInstrRoots)

2527}

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

static MCDisassembler::DecodeStatus addOperand(MCInst &Inst, const MCOperand &Opnd)

This file defines the BumpPtrAllocator interface.

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

static bool isInstructionPotentiallySymmetric(Instruction *I)

Definition ComplexDeinterleavingPass.cpp:933

static Value * getNegOperand(Value *V)

Returns the operand for negation operation.

Definition ComplexDeinterleavingPass.cpp:616

static bool isNeg(Value *V)

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

Definition ComplexDeinterleavingPass.cpp:612

static cl::opt< bool > ComplexDeinterleavingEnabled("enable-complex-deinterleaving", cl::desc("Enable generation of complex instructions"), cl::init(true), cl::Hidden)

static bool isInstructionPairAdd(Instruction *A, Instruction *B)

Definition ComplexDeinterleavingPass.cpp:916

static Value * replaceSymmetricNode(IRBuilderBase &B, unsigned Opcode, std::optional< FastMathFlags > Flags, Value *InputA, Value *InputB)

Definition ComplexDeinterleavingPass.cpp:2281

static bool isInterleavingMask(ArrayRef< int > Mask)

Checks the given mask, and determines whether said mask is interleaving.

Definition ComplexDeinterleavingPass.cpp:585

static bool isDeinterleavingMask(ArrayRef< int > Mask)

Checks the given mask, and determines whether said mask is deinterleaving.

Definition ComplexDeinterleavingPass.cpp:600

SmallVector< struct ComplexValue, 2 > ComplexValues

Definition ComplexDeinterleavingPass.cpp:127

static bool isInstructionPairMul(Instruction *A, Instruction *B)

Definition ComplexDeinterleavingPass.cpp:926

static bool runOnFunction(Function &F, bool PostInlining)

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

This file implements a map that provides insertion order iteration.

uint64_t IntrinsicInst * II

PowerPC Reduce CR logical Operation

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

SI optimize exec mask operations pre RA

static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckType(MVT::SimpleValueType VT, SDValue N, const TargetLowering *TLI, const DataLayout &DL)

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

This file describes how to lower LLVM code to machine code.

This pass exposes codegen information to IR-level passes.

AnalysisUsage & addRequired()

LLVM_ABI void setPreservesCFG()

This function should be called by the pass, iff they do not:

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

size_t size() const

size - Get the array size.

LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const

Returns an iterator to the first instruction in this block that is not a PHINode instruction.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

static LLVM_ABI Constant * getNullValue(Type *Ty)

Constructor to create a '0' constant of arbitrary type.

iterator find(const_arg_type_t< KeyT > Val)

bool allowContract() const

FunctionPass class - This class is used to implement most global optimizations.

Common base class shared among various IRBuilders.

Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")

LLVM_ABI Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)

LLVM_ABI CallInst * CreateAddReduce(Value *Src)

Create a vector int add reduction intrinsic of the source vector.

LLVM_ABI CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, FMFSource FMFSource={}, const Twine &Name="")

Create a call to intrinsic ID with Args, mangled using Types.

void SetInsertPoint(BasicBlock *TheBB)

This specifies that created instructions should be appended to the end of the specified block.

LLVM_ABI Value * CreateVectorInterleave(ArrayRef< Value * > Ops, const Twine &Name="")

LLVM_ABI const Function * getFunction() const

Return the function this instruction belongs to.

LLVM_ABI bool comesBefore(const Instruction *Other) const

Given an instruction Other in the same basic block as this instruction, return true if this instructi...

LLVM_ABI FastMathFlags getFastMathFlags() const LLVM_READONLY

Convenience function for getting all the fast-math flags, which must be an operator which supports th...

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY

Return true if the specified instruction is exactly identical to the current one.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

Analysis pass providing the TargetLibraryInfo.

virtual bool isComplexDeinterleavingOperationSupported(ComplexDeinterleavingOperation Operation, Type *Ty) const

Does this target support complex deinterleaving with the given operation and type.

virtual Value * createComplexDeinterleavingIR(IRBuilderBase &B, ComplexDeinterleavingOperation OperationType, ComplexDeinterleavingRotation Rotation, Value *InputA, Value *InputB, Value *Accumulator=nullptr) const

Create the IR node for the given complex deinterleaving operation.

virtual bool isComplexDeinterleavingSupported() const

Does this target support complex deinterleaving.

This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...

Primary interface to the complete machine description for the target machine.

virtual const TargetSubtargetInfo * getSubtargetImpl(const Function &) const

Virtual method implemented by subclasses that returns a reference to that target's TargetSubtargetInf...

virtual const TargetLowering * getTargetLowering() const

bool isVectorTy() const

True if this is an instance of VectorType.

Value * getOperand(unsigned i) const

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

bool hasOneUse() const

Return true if there is exactly one use of this value.

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

An opaque object representing a hash code.

const ParentTy * getParent() const

NodeTy * getNextNode()

Get the next node, or nullptr for the list tail.

raw_ostream & indent(unsigned NumSpaces)

indent - Insert 'NumSpaces' spaces.

#define llvm_unreachable(msg)

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

constexpr std::underlying_type_t< E > Mask()

Get a bitmask with 1s in all places up to the high-order bit of E's largest value.

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

LLVM_ABI Intrinsic::ID getDeinterleaveIntrinsicID(unsigned Factor)

Returns the corresponding llvm.vector.deinterleaveN intrinsic for factor N.

LLVM_ABI Intrinsic::ID getInterleaveIntrinsicID(unsigned Factor)

Returns the corresponding llvm.vector.interleaveN intrinsic for factor N.

BinaryOp_match< SpecificConstantMatch, SrcTy, TargetOpcode::G_SUB > m_Neg(const SrcTy &&Src)

Matches a register negated by a G_SUB.

class_match< BinaryOperator > m_BinOp()

Match an arbitrary binary operation and ignore it.

BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)

bool match(Val *V, const Pattern &P)

bind_ty< Instruction > m_Instruction(Instruction *&I)

Match an instruction, capturing it if we match.

IntrinsicID_match m_Intrinsic()

Match intrinsic calls like this: m_IntrinsicIntrinsic::fabs(m_Value(X))

ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)

Matches SelectInst.

BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)

TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)

Matches ShuffleVectorInst independently of mask value.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

FNeg_match< OpTy > m_FNeg(const OpTy &X)

Match 'fneg X' as 'fsub -0.0, X'.

initializer< Ty > init(const Ty &Val)

NodeAddr< PhiNode * > Phi

NodeAddr< NodeBase * > Node

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

FunctionAddr VTableAddr Value

bool all_of(R &&range, UnaryPredicate P)

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

hash_code hash_value(const FixedPointSemantics &Val)

LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())

If the specified value is a trivially dead instruction, delete it.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy

Provide the FunctionAnalysisManager to Module proxy.

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

auto dyn_cast_or_null(const Y &Val)

ComplexDeinterleavingOperation

LLVM_ABI FunctionPass * createComplexDeinterleavingPass(const TargetMachine *TM)

This pass implements generation of target-specific intrinsics to support handling of complex number a...

Definition ComplexDeinterleavingPass.cpp:546

LLVM_ABI raw_ostream & dbgs()

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

LLVM_ABI void initializeComplexDeinterleavingLegacyPassPass(PassRegistry &)

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

ComplexDeinterleavingRotation

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

DWARFExpression::Operation Op

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

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

auto find_if(R &&Range, UnaryPredicate P)

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

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

bool all_equal(std::initializer_list< T > Values)

Returns true if all Values in the initializer lists are equal or the list.

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

hash_code hash_combine(const Ts &...args)

Combine values into a single hash_code.

AllocatorList< T, BumpPtrAllocator > BumpPtrList

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

Implement std::swap in terms of BitVector swap.

ComplexDeinterleavingPass(const TargetMachine &TM)

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition ComplexDeinterleavingPass.cpp:534

static bool isEqual(const ComplexValue &LHS, const ComplexValue &RHS)

Definition ComplexDeinterleavingPass.cpp:142

static ComplexValue getEmptyKey()

Definition ComplexDeinterleavingPass.cpp:130

static unsigned getHashValue(const ComplexValue &Val)

Definition ComplexDeinterleavingPass.cpp:138

static ComplexValue getTombstoneKey()

Definition ComplexDeinterleavingPass.cpp:134

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