1//===- ComplexDeinterleavingPass.cpp --------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Identification:
10// This step is responsible for finding the patterns that can be lowered to
11// complex instructions, and building a graph to represent the complex
12// structures. Starting from the "Converging Shuffle" (a shuffle that
13// reinterleaves the complex components, with a mask of <0, 2, 1, 3>), the
14// operands are evaluated and identified as "Composite Nodes" (collections of
15// instructions that can potentially be lowered to a single complex
16// instruction). This is performed by checking the real and imaginary components
17// and tracking the data flow for each component while following the operand
18// pairs. Validity of each node is expected to be done upon creation, and any
19// validation errors should halt traversal and prevent further graph
20// construction.
21// Instead of relying on Shuffle operations, vector interleaving and
22// deinterleaving can be represented by vector.interleave2 and
23// vector.deinterleave2 intrinsics. Scalable vectors can be represented only by
24// these intrinsics, whereas, fixed-width vectors are recognized for both
25// shufflevector instruction and intrinsics.
26//
27// Replacement:
28// This step traverses the graph built up by identification, delegating to the
29// target to validate and generate the correct intrinsics, and plumbs them
30// together connecting each end of the new intrinsics graph to the existing
31// use-def chain. This step is assumed to finish successfully, as all
32// information is expected to be correct by this point.
33//
34//
35// Internal data structure:
36// ComplexDeinterleavingGraph:
37// Keeps references to all the valid CompositeNodes formed as part of the
38// transformation, and every Instruction contained within said nodes. It also
39// holds onto a reference to the root Instruction, and the root node that should
40// replace it.
41//
42// ComplexDeinterleavingCompositeNode:
43// A CompositeNode represents a single transformation point; each node should
44// transform into a single complex instruction (ignoring vector splitting, which
45// would generate more instructions per node). They are identified in a
46// depth-first manner, traversing and identifying the operands of each
47// instruction in the order they appear in the IR.
48// Each node maintains a reference to its Real and Imaginary instructions,
49// as well as any additional instructions that make up the identified operation
50// (Internal instructions should only have uses within their containing node).
51// A Node also contains the rotation and operation type that it represents.
52// Operands contains pointers to other CompositeNodes, acting as the edges in
53// the graph. ReplacementValue is the transformed Value* that has been emitted
54// to the IR.
55//
56// Note: If the operation of a Node is Shuffle, only the Real, Imaginary, and
57// ReplacementValue fields of that Node are relevant, where the ReplacementValue
58// should be pre-populated.
59//
60//===----------------------------------------------------------------------===//
61
62#include "llvm/CodeGen/ComplexDeinterleavingPass.h"
63#include "llvm/ADT/AllocatorList.h"
64#include "llvm/ADT/MapVector.h"
65#include "llvm/ADT/Statistic.h"
66#include "llvm/Analysis/TargetLibraryInfo.h"
67#include "llvm/Analysis/TargetTransformInfo.h"
68#include "llvm/CodeGen/TargetLowering.h"
69#include "llvm/CodeGen/TargetSubtargetInfo.h"
70#include "llvm/IR/IRBuilder.h"
71#include "llvm/IR/Intrinsics.h"
72#include "llvm/IR/PatternMatch.h"
73#include "llvm/InitializePasses.h"
74#include "llvm/Support/Allocator.h"
75#include "llvm/Target/TargetMachine.h"
76#include "llvm/Transforms/Utils/Local.h"
77#include <algorithm>
78
79using namespace llvm;
80using namespace PatternMatch;
81
82#define DEBUG_TYPE "complex-deinterleaving"
83
84STATISTIC(NumComplexTransformations, "Amount of complex patterns transformed");
85
86static cl::opt<bool> ComplexDeinterleavingEnabled(
87 "enable-complex-deinterleaving",
88 cl::desc("Enable generation of complex instructions"), cl::init(Val: true),
89 cl::Hidden);
90
91/// Checks the given mask, and determines whether said mask is interleaving.
92///
93/// To be interleaving, a mask must alternate between `i` and `i + (Length /
94/// 2)`, and must contain all numbers within the range of `[0..Length)` (e.g. a
95/// 4x vector interleaving mask would be <0, 2, 1, 3>).
96static bool isInterleavingMask(ArrayRef<int> Mask);
97
98/// Checks the given mask, and determines whether said mask is deinterleaving.
99///
100/// To be deinterleaving, a mask must increment in steps of 2, and either start
101/// with 0 or 1.
102/// (e.g. an 8x vector deinterleaving mask would be either <0, 2, 4, 6> or
103/// <1, 3, 5, 7>).
104static bool isDeinterleavingMask(ArrayRef<int> Mask);
105
106/// Returns true if the operation is a negation of V, and it works for both
107/// integers and floats.
108static bool isNeg(Value *V);
109
110/// Returns the operand for negation operation.
111static Value *getNegOperand(Value *V);
112
113namespace {
114struct ComplexValue {
115 Value *Real = nullptr;
116 Value *Imag = nullptr;
117
118 bool operator==(const ComplexValue &Other) const {
119 return Real == Other.Real && Imag == Other.Imag;
120 }
121};
122hash_code hash_value(const ComplexValue &Arg) {
123 return hash_combine(args: DenseMapInfo<Value *>::getHashValue(PtrVal: Arg.Real),
124 args: DenseMapInfo<Value *>::getHashValue(PtrVal: Arg.Imag));
125}
126} // end namespace
127typedef SmallVector<struct ComplexValue, 2> ComplexValues;
128
129template <> struct llvm::DenseMapInfo<ComplexValue> {
130 static unsigned getHashValue(const ComplexValue &Val) {
131 return hash_combine(args: DenseMapInfo<Value *>::getHashValue(PtrVal: Val.Real),
132 args: DenseMapInfo<Value *>::getHashValue(PtrVal: Val.Imag));
133 }
134 static bool isEqual(const ComplexValue &LHS, const ComplexValue &RHS) {
135 return LHS.Real == RHS.Real && LHS.Imag == RHS.Imag;
136 }
137};
138
139namespace {
140template <typename T, typename IterT>
141std::optional<T> findCommonBetweenCollections(IterT A, IterT B) {
142 auto Common = llvm::find_if(A, [B](T I) { return llvm::is_contained(B, I); });
143 if (Common != A.end())
144 return std::make_optional(*Common);
145 return std::nullopt;
146}
147
148class ComplexDeinterleavingLegacyPass : public FunctionPass {
149public:
150 static char ID;
151
152 ComplexDeinterleavingLegacyPass(const TargetMachine *TM = nullptr)
153 : FunctionPass(ID), TM(TM) {}
154
155 StringRef getPassName() const override {
156 return "Complex Deinterleaving Pass";
157 }
158
159 bool runOnFunction(Function &F) override;
160 void getAnalysisUsage(AnalysisUsage &AU) const override {
161 AU.addRequired<TargetLibraryInfoWrapperPass>();
162 AU.setPreservesCFG();
163 }
164
165private:
166 const TargetMachine *TM;
167};
168
169class ComplexDeinterleavingGraph;
170struct ComplexDeinterleavingCompositeNode {
171
172 ComplexDeinterleavingCompositeNode(ComplexDeinterleavingOperation Op,
173 Value *R, Value *I)
174 : Operation(Op) {
175 Vals.push_back(Elt: {.Real: R, .Imag: I});
176 }
177
178 ComplexDeinterleavingCompositeNode(ComplexDeinterleavingOperation Op,
179 ComplexValues &Other)
180 : Operation(Op), Vals(Other) {}
181
182private:
183 friend class ComplexDeinterleavingGraph;
184 using CompositeNode = ComplexDeinterleavingCompositeNode;
185 bool OperandsValid = true;
186
187public:
188 ComplexDeinterleavingOperation Operation;
189 ComplexValues Vals;
190
191 // This two members are required exclusively for generating
192 // ComplexDeinterleavingOperation::Symmetric operations.
193 unsigned Opcode;
194 std::optional<FastMathFlags> Flags;
195
196 ComplexDeinterleavingRotation Rotation =
197 ComplexDeinterleavingRotation::Rotation_0;
198 SmallVector<CompositeNode *> Operands;
199 Value *ReplacementNode = nullptr;
200
201 void addOperand(CompositeNode *Node) {
202 if (!Node)
203 OperandsValid = false;
204 Operands.push_back(Elt: Node);
205 }
206
207 void dump() { dump(OS&: dbgs()); }
208 void dump(raw_ostream &OS) {
209 auto PrintValue = [&](Value *V) {
210 if (V) {
211 OS << "\"";
212 V->print(O&: OS, IsForDebug: true);
213 OS << "\"\n";
214 } else
215 OS << "nullptr\n";
216 };
217 auto PrintNodeRef = [&](CompositeNode *Ptr) {
218 if (Ptr)
219 OS << Ptr << "\n";
220 else
221 OS << "nullptr\n";
222 };
223
224 OS << "- CompositeNode: " << this << "\n";
225 for (unsigned I = 0; I < Vals.size(); I++) {
226 OS << " Real(" << I << ") : ";
227 PrintValue(Vals[I].Real);
228 OS << " Imag(" << I << ") : ";
229 PrintValue(Vals[I].Imag);
230 }
231 OS << " ReplacementNode: ";
232 PrintValue(ReplacementNode);
233 OS << " Operation: " << (int)Operation << "\n";
234 OS << " Rotation: " << ((int)Rotation * 90) << "\n";
235 OS << " Operands: \n";
236 for (const auto &Op : Operands) {
237 OS << " - ";
238 PrintNodeRef(Op);
239 }
240 }
241
242 bool areOperandsValid() { return OperandsValid; }
243};
244
245class ComplexDeinterleavingGraph {
246public:
247 struct Product {
248 Value *Multiplier;
249 Value *Multiplicand;
250 bool IsPositive;
251 };
252
253 using Addend = std::pair<Value *, bool>;
254 using AddendList = BumpPtrList<Addend>;
255 using CompositeNode = ComplexDeinterleavingCompositeNode::CompositeNode;
256
257 // Helper struct for holding info about potential partial multiplication
258 // candidates
259 struct PartialMulCandidate {
260 Value *Common;
261 CompositeNode *Node;
262 unsigned RealIdx;
263 unsigned ImagIdx;
264 bool IsNodeInverted;
265 };
266
267 explicit ComplexDeinterleavingGraph(const TargetLowering *TL,
268 const TargetLibraryInfo *TLI,
269 unsigned Factor)
270 : TL(TL), TLI(TLI), Factor(Factor) {}
271
272private:
273 const TargetLowering *TL = nullptr;
274 const TargetLibraryInfo *TLI = nullptr;
275 unsigned Factor;
276 SmallVector<CompositeNode *> CompositeNodes;
277 DenseMap<ComplexValues, CompositeNode *> CachedResult;
278 SpecificBumpPtrAllocator<ComplexDeinterleavingCompositeNode> Allocator;
279
280 SmallPtrSet<Instruction *, 16> FinalInstructions;
281
282 /// Root instructions are instructions from which complex computation starts
283 DenseMap<Instruction *, CompositeNode *> RootToNode;
284
285 /// Topologically sorted root instructions
286 SmallVector<Instruction *, 1> OrderedRoots;
287
288 /// When examining a basic block for complex deinterleaving, if it is a simple
289 /// one-block loop, then the only incoming block is 'Incoming' and the
290 /// 'BackEdge' block is the block itself."
291 BasicBlock *BackEdge = nullptr;
292 BasicBlock *Incoming = nullptr;
293
294 /// ReductionInfo maps from %ReductionOp to %PHInode and Instruction
295 /// %OutsideUser as it is shown in the IR:
296 ///
297 /// vector.body:
298 /// %PHInode = phi <vector type> [ zeroinitializer, %entry ],
299 /// [ %ReductionOp, %vector.body ]
300 /// ...
301 /// %ReductionOp = fadd i64 ...
302 /// ...
303 /// br i1 %condition, label %vector.body, %middle.block
304 ///
305 /// middle.block:
306 /// %OutsideUser = llvm.vector.reduce.fadd(..., %ReductionOp)
307 ///
308 /// %OutsideUser can be `llvm.vector.reduce.fadd` or `fadd` preceding
309 /// `llvm.vector.reduce.fadd` when unroll factor isn't one.
310 MapVector<Instruction *, std::pair<PHINode *, Instruction *>> ReductionInfo;
311
312 /// In the process of detecting a reduction, we consider a pair of
313 /// %ReductionOP, which we refer to as real and imag (or vice versa), and
314 /// traverse the use-tree to detect complex operations. As this is a reduction
315 /// operation, it will eventually reach RealPHI and ImagPHI, which corresponds
316 /// to the %ReductionOPs that we suspect to be complex.
317 /// RealPHI and ImagPHI are used by the identifyPHINode method.
318 PHINode *RealPHI = nullptr;
319 PHINode *ImagPHI = nullptr;
320
321 /// Set this flag to true if RealPHI and ImagPHI were reached during reduction
322 /// detection.
323 bool PHIsFound = false;
324
325 /// OldToNewPHI maps the original real PHINode to a new, double-sized PHINode.
326 /// The new PHINode corresponds to a vector of deinterleaved complex numbers.
327 /// This mapping is populated during
328 /// ComplexDeinterleavingOperation::ReductionPHI node replacement. It is then
329 /// used in the ComplexDeinterleavingOperation::ReductionOperation node
330 /// replacement process.
331 DenseMap<PHINode *, PHINode *> OldToNewPHI;
332
333 CompositeNode *prepareCompositeNode(ComplexDeinterleavingOperation Operation,
334 Value *R, Value *I) {
335 assert(((Operation != ComplexDeinterleavingOperation::ReductionPHI &&
336 Operation != ComplexDeinterleavingOperation::ReductionOperation) ||
337 (R && I)) &&
338 "Reduction related nodes must have Real and Imaginary parts");
339 return new (Allocator.Allocate())
340 ComplexDeinterleavingCompositeNode(Operation, R, I);
341 }
342
343 CompositeNode *prepareCompositeNode(ComplexDeinterleavingOperation Operation,
344 ComplexValues &Vals) {
345#ifndef NDEBUG
346 for (auto &V : Vals) {
347 assert(
348 ((Operation != ComplexDeinterleavingOperation::ReductionPHI &&
349 Operation != ComplexDeinterleavingOperation::ReductionOperation) ||
350 (V.Real && V.Imag)) &&
351 "Reduction related nodes must have Real and Imaginary parts");
352 }
353#endif
354 return new (Allocator.Allocate())
355 ComplexDeinterleavingCompositeNode(Operation, Vals);
356 }
357
358 CompositeNode *submitCompositeNode(CompositeNode *Node) {
359 CompositeNodes.push_back(Elt: Node);
360 if (Node->Vals[0].Real)
361 CachedResult[Node->Vals] = Node;
362 return Node;
363 }
364
365 /// Identifies a complex partial multiply pattern and its rotation, based on
366 /// the following patterns
367 ///
368 /// 0: r: cr + ar * br
369 /// i: ci + ar * bi
370 /// 90: r: cr - ai * bi
371 /// i: ci + ai * br
372 /// 180: r: cr - ar * br
373 /// i: ci - ar * bi
374 /// 270: r: cr + ai * bi
375 /// i: ci - ai * br
376 CompositeNode *identifyPartialMul(Instruction *Real, Instruction *Imag);
377
378 /// Identify the other branch of a Partial Mul, taking the CommonOperandI that
379 /// is partially known from identifyPartialMul, filling in the other half of
380 /// the complex pair.
381 CompositeNode *
382 identifyNodeWithImplicitAdd(Instruction *I, Instruction *J,
383 std::pair<Value *, Value *> &CommonOperandI);
384
385 /// Identifies a complex add pattern and its rotation, based on the following
386 /// patterns.
387 ///
388 /// 90: r: ar - bi
389 /// i: ai + br
390 /// 270: r: ar + bi
391 /// i: ai - br
392 CompositeNode *identifyAdd(Instruction *Real, Instruction *Imag);
393 CompositeNode *identifySymmetricOperation(ComplexValues &Vals);
394 CompositeNode *identifyPartialReduction(Value *R, Value *I);
395 CompositeNode *identifyDotProduct(Value *Inst);
396
397 CompositeNode *identifyNode(ComplexValues &Vals);
398
399 CompositeNode *identifyNode(Value *R, Value *I) {
400 ComplexValues Vals;
401 Vals.push_back(Elt: {.Real: R, .Imag: I});
402 return identifyNode(Vals);
403 }
404
405 /// Determine if a sum of complex numbers can be formed from \p RealAddends
406 /// and \p ImagAddens. If \p Accumulator is not null, add the result to it.
407 /// Return nullptr if it is not possible to construct a complex number.
408 /// \p Flags are needed to generate symmetric Add and Sub operations.
409 CompositeNode *identifyAdditions(AddendList &RealAddends,
410 AddendList &ImagAddends,
411 std::optional<FastMathFlags> Flags,
412 CompositeNode *Accumulator);
413
414 /// Extract one addend that have both real and imaginary parts positive.
415 CompositeNode *extractPositiveAddend(AddendList &RealAddends,
416 AddendList &ImagAddends);
417
418 /// Determine if sum of multiplications of complex numbers can be formed from
419 /// \p RealMuls and \p ImagMuls. If \p Accumulator is not null, add the result
420 /// to it. Return nullptr if it is not possible to construct a complex number.
421 CompositeNode *identifyMultiplications(SmallVectorImpl<Product> &RealMuls,
422 SmallVectorImpl<Product> &ImagMuls,
423 CompositeNode *Accumulator);
424
425 /// Go through pairs of multiplication (one Real and one Imag) and find all
426 /// possible candidates for partial multiplication and put them into \p
427 /// Candidates. Returns true if all Product has pair with common operand
428 bool collectPartialMuls(ArrayRef<Product> RealMuls,
429 ArrayRef<Product> ImagMuls,
430 SmallVectorImpl<PartialMulCandidate> &Candidates);
431
432 /// If the code is compiled with -Ofast or expressions have `reassoc` flag,
433 /// the order of complex computation operations may be significantly altered,
434 /// and the real and imaginary parts may not be executed in parallel. This
435 /// function takes this into consideration and employs a more general approach
436 /// to identify complex computations. Initially, it gathers all the addends
437 /// and multiplicands and then constructs a complex expression from them.
438 CompositeNode *identifyReassocNodes(Instruction *I, Instruction *J);
439
440 CompositeNode *identifyRoot(Instruction *I);
441
442 /// Identifies the Deinterleave operation applied to a vector containing
443 /// complex numbers. There are two ways to represent the Deinterleave
444 /// operation:
445 /// * Using two shufflevectors with even indices for /pReal instruction and
446 /// odd indices for /pImag instructions (only for fixed-width vectors)
447 /// * Using N extractvalue instructions applied to `vector.deinterleaveN`
448 /// intrinsics (for both fixed and scalable vectors) where N is a multiple of
449 /// 2.
450 CompositeNode *identifyDeinterleave(ComplexValues &Vals);
451
452 /// identifying the operation that represents a complex number repeated in a
453 /// Splat vector. There are two possible types of splats: ConstantExpr with
454 /// the opcode ShuffleVector and ShuffleVectorInstr. Both should have an
455 /// initialization mask with all values set to zero.
456 CompositeNode *identifySplat(ComplexValues &Vals);
457
458 CompositeNode *identifyPHINode(Instruction *Real, Instruction *Imag);
459
460 /// Identifies SelectInsts in a loop that has reduction with predication masks
461 /// and/or predicated tail folding
462 CompositeNode *identifySelectNode(Instruction *Real, Instruction *Imag);
463
464 Value *replaceNode(IRBuilderBase &Builder, CompositeNode *Node);
465
466 /// Complete IR modifications after producing new reduction operation:
467 /// * Populate the PHINode generated for
468 /// ComplexDeinterleavingOperation::ReductionPHI
469 /// * Deinterleave the final value outside of the loop and repurpose original
470 /// reduction users
471 void processReductionOperation(Value *OperationReplacement,
472 CompositeNode *Node);
473 void processReductionSingle(Value *OperationReplacement, CompositeNode *Node);
474
475public:
476 void dump() { dump(OS&: dbgs()); }
477 void dump(raw_ostream &OS) {
478 for (const auto &Node : CompositeNodes)
479 Node->dump(OS);
480 }
481
482 /// Returns false if the deinterleaving operation should be cancelled for the
483 /// current graph.
484 bool identifyNodes(Instruction *RootI);
485
486 /// In case \pB is one-block loop, this function seeks potential reductions
487 /// and populates ReductionInfo. Returns true if any reductions were
488 /// identified.
489 bool collectPotentialReductions(BasicBlock *B);
490
491 void identifyReductionNodes();
492
493 /// Check that every instruction, from the roots to the leaves, has internal
494 /// uses.
495 bool checkNodes();
496
497 /// Perform the actual replacement of the underlying instruction graph.
498 void replaceNodes();
499};
500
501class ComplexDeinterleaving {
502public:
503 ComplexDeinterleaving(const TargetLowering *tl, const TargetLibraryInfo *tli)
504 : TL(tl), TLI(tli) {}
505 bool runOnFunction(Function &F);
506
507private:
508 bool evaluateBasicBlock(BasicBlock *B, unsigned Factor);
509
510 const TargetLowering *TL = nullptr;
511 const TargetLibraryInfo *TLI = nullptr;
512};
513
514} // namespace
515
516char ComplexDeinterleavingLegacyPass::ID = 0;
517
518INITIALIZE_PASS_BEGIN(ComplexDeinterleavingLegacyPass, DEBUG_TYPE,
519 "Complex Deinterleaving", false, false)
520INITIALIZE_PASS_END(ComplexDeinterleavingLegacyPass, DEBUG_TYPE,
521 "Complex Deinterleaving", false, false)
522
523PreservedAnalyses ComplexDeinterleavingPass::run(Function &F,
524 FunctionAnalysisManager &AM) {
525 const TargetLowering *TL = TM->getSubtargetImpl(F)->getTargetLowering();
526 auto &TLI = AM.getResult<llvm::TargetLibraryAnalysis>(IR&: F);
527 if (!ComplexDeinterleaving(TL, &TLI).runOnFunction(F))
528 return PreservedAnalyses::all();
529
530 PreservedAnalyses PA;
531 PA.preserve<FunctionAnalysisManagerModuleProxy>();
532 return PA;
533}
534
535FunctionPass *llvm::createComplexDeinterleavingPass(const TargetMachine *TM) {
536 return new ComplexDeinterleavingLegacyPass(TM);
537}
538
539bool ComplexDeinterleavingLegacyPass::runOnFunction(Function &F) {
540 const auto *TL = TM->getSubtargetImpl(F)->getTargetLowering();
541 auto TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
542 return ComplexDeinterleaving(TL, &TLI).runOnFunction(F);
543}
544
545bool ComplexDeinterleaving::runOnFunction(Function &F) {
546 if (!ComplexDeinterleavingEnabled) {
547 LLVM_DEBUG(
548 dbgs() << "Complex deinterleaving has been explicitly disabled.\n");
549 return false;
550 }
551
552 if (!TL->isComplexDeinterleavingSupported()) {
553 LLVM_DEBUG(
554 dbgs() << "Complex deinterleaving has been disabled, target does "
555 "not support lowering of complex number operations.\n");
556 return false;
557 }
558
559 bool Changed = false;
560 for (auto &B : F)
561 Changed |= evaluateBasicBlock(B: &B, Factor: 2);
562
563 // TODO: Permit changes for both interleave factors in the same function.
564 if (!Changed) {
565 for (auto &B : F)
566 Changed |= evaluateBasicBlock(B: &B, Factor: 4);
567 }
568
569 // TODO: We can also support interleave factors of 6 and 8 if needed.
570
571 return Changed;
572}
573
574static bool isInterleavingMask(ArrayRef<int> Mask) {
575 // If the size is not even, it's not an interleaving mask
576 if ((Mask.size() & 1))
577 return false;
578
579 int HalfNumElements = Mask.size() / 2;
580 for (int Idx = 0; Idx < HalfNumElements; ++Idx) {
581 int MaskIdx = Idx * 2;
582 if (Mask[MaskIdx] != Idx || Mask[MaskIdx + 1] != (Idx + HalfNumElements))
583 return false;
584 }
585
586 return true;
587}
588
589static bool isDeinterleavingMask(ArrayRef<int> Mask) {
590 int Offset = Mask[0];
591 int HalfNumElements = Mask.size() / 2;
592
593 for (int Idx = 1; Idx < HalfNumElements; ++Idx) {
594 if (Mask[Idx] != (Idx * 2) + Offset)
595 return false;
596 }
597
598 return true;
599}
600
601bool isNeg(Value *V) {
602 return match(V, P: m_FNeg(X: m_Value())) || match(V, P: m_Neg(V: m_Value()));
603}
604
605Value *getNegOperand(Value *V) {
606 assert(isNeg(V));
607 auto *I = cast<Instruction>(Val: V);
608 if (I->getOpcode() == Instruction::FNeg)
609 return I->getOperand(i: 0);
610
611 return I->getOperand(i: 1);
612}
613
614bool ComplexDeinterleaving::evaluateBasicBlock(BasicBlock *B, unsigned Factor) {
615 ComplexDeinterleavingGraph Graph(TL, TLI, Factor);
616 if (Graph.collectPotentialReductions(B))
617 Graph.identifyReductionNodes();
618
619 for (auto &I : *B)
620 Graph.identifyNodes(RootI: &I);
621
622 if (Graph.checkNodes()) {
623 Graph.replaceNodes();
624 return true;
625 }
626
627 return false;
628}
629
630ComplexDeinterleavingGraph::CompositeNode *
631ComplexDeinterleavingGraph::identifyNodeWithImplicitAdd(
632 Instruction *Real, Instruction *Imag,
633 std::pair<Value *, Value *> &PartialMatch) {
634 LLVM_DEBUG(dbgs() << "identifyNodeWithImplicitAdd " << *Real << " / " << *Imag
635 << "\n");
636
637 if (!Real->hasOneUse() || !Imag->hasOneUse()) {
638 LLVM_DEBUG(dbgs() << " - Mul operand has multiple uses.\n");
639 return nullptr;
640 }
641
642 if ((Real->getOpcode() != Instruction::FMul &&
643 Real->getOpcode() != Instruction::Mul) ||
644 (Imag->getOpcode() != Instruction::FMul &&
645 Imag->getOpcode() != Instruction::Mul)) {
646 LLVM_DEBUG(
647 dbgs() << " - Real or imaginary instruction is not fmul or mul\n");
648 return nullptr;
649 }
650
651 Value *R0 = Real->getOperand(i: 0);
652 Value *R1 = Real->getOperand(i: 1);
653 Value *I0 = Imag->getOperand(i: 0);
654 Value *I1 = Imag->getOperand(i: 1);
655
656 // A +/+ has a rotation of 0. If any of the operands are fneg, we flip the
657 // rotations and use the operand.
658 unsigned Negs = 0;
659 if (isNeg(V: R0)) {
660 Negs |= 1;
661 R0 = getNegOperand(V: R0);
662 } else if (isNeg(V: R1)) {
663 Negs |= 1;
664 R1 = getNegOperand(V: R1);
665 }
666
667 if (isNeg(V: I0)) {
668 Negs |= 2;
669 Negs ^= 1;
670 I0 = getNegOperand(V: I0);
671 } else if (isNeg(V: I1)) {
672 Negs |= 2;
673 Negs ^= 1;
674 I1 = getNegOperand(V: I1);
675 }
676
677 ComplexDeinterleavingRotation Rotation = (ComplexDeinterleavingRotation)Negs;
678
679 Value *CommonOperand;
680 Value *UncommonRealOp;
681 Value *UncommonImagOp;
682
683 if (R0 == I0 || R0 == I1) {
684 CommonOperand = R0;
685 UncommonRealOp = R1;
686 } else if (R1 == I0 || R1 == I1) {
687 CommonOperand = R1;
688 UncommonRealOp = R0;
689 } else {
690 LLVM_DEBUG(dbgs() << " - No equal operand\n");
691 return nullptr;
692 }
693
694 UncommonImagOp = (CommonOperand == I0) ? I1 : I0;
695 if (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||
696 Rotation == ComplexDeinterleavingRotation::Rotation_270)
697 std::swap(a&: UncommonRealOp, b&: UncommonImagOp);
698
699 // Between identifyPartialMul and here we need to have found a complete valid
700 // pair from the CommonOperand of each part.
701 if (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||
702 Rotation == ComplexDeinterleavingRotation::Rotation_180)
703 PartialMatch.first = CommonOperand;
704 else
705 PartialMatch.second = CommonOperand;
706
707 if (!PartialMatch.first || !PartialMatch.second) {
708 LLVM_DEBUG(dbgs() << " - Incomplete partial match\n");
709 return nullptr;
710 }
711
712 CompositeNode *CommonNode =
713 identifyNode(R: PartialMatch.first, I: PartialMatch.second);
714 if (!CommonNode) {
715 LLVM_DEBUG(dbgs() << " - No CommonNode identified\n");
716 return nullptr;
717 }
718
719 CompositeNode *UncommonNode = identifyNode(R: UncommonRealOp, I: UncommonImagOp);
720 if (!UncommonNode) {
721 LLVM_DEBUG(dbgs() << " - No UncommonNode identified\n");
722 return nullptr;
723 }
724
725 CompositeNode *Node = prepareCompositeNode(
726 Operation: ComplexDeinterleavingOperation::CMulPartial, R: Real, I: Imag);
727 Node->Rotation = Rotation;
728 Node->addOperand(Node: CommonNode);
729 Node->addOperand(Node: UncommonNode);
730 return submitCompositeNode(Node);
731}
732
733ComplexDeinterleavingGraph::CompositeNode *
734ComplexDeinterleavingGraph::identifyPartialMul(Instruction *Real,
735 Instruction *Imag) {
736 LLVM_DEBUG(dbgs() << "identifyPartialMul " << *Real << " / " << *Imag
737 << "\n");
738
739 // Determine rotation
740 auto IsAdd = [](unsigned Op) {
741 return Op == Instruction::FAdd || Op == Instruction::Add;
742 };
743 auto IsSub = [](unsigned Op) {
744 return Op == Instruction::FSub || Op == Instruction::Sub;
745 };
746 ComplexDeinterleavingRotation Rotation;
747 if (IsAdd(Real->getOpcode()) && IsAdd(Imag->getOpcode()))
748 Rotation = ComplexDeinterleavingRotation::Rotation_0;
749 else if (IsSub(Real->getOpcode()) && IsAdd(Imag->getOpcode()))
750 Rotation = ComplexDeinterleavingRotation::Rotation_90;
751 else if (IsSub(Real->getOpcode()) && IsSub(Imag->getOpcode()))
752 Rotation = ComplexDeinterleavingRotation::Rotation_180;
753 else if (IsAdd(Real->getOpcode()) && IsSub(Imag->getOpcode()))
754 Rotation = ComplexDeinterleavingRotation::Rotation_270;
755 else {
756 LLVM_DEBUG(dbgs() << " - Unhandled rotation.\n");
757 return nullptr;
758 }
759
760 if (isa<FPMathOperator>(Val: Real) &&
761 (!Real->getFastMathFlags().allowContract() ||
762 !Imag->getFastMathFlags().allowContract())) {
763 LLVM_DEBUG(dbgs() << " - Contract is missing from the FastMath flags.\n");
764 return nullptr;
765 }
766
767 Value *CR = Real->getOperand(i: 0);
768 Instruction *RealMulI = dyn_cast<Instruction>(Val: Real->getOperand(i: 1));
769 if (!RealMulI)
770 return nullptr;
771 Value *CI = Imag->getOperand(i: 0);
772 Instruction *ImagMulI = dyn_cast<Instruction>(Val: Imag->getOperand(i: 1));
773 if (!ImagMulI)
774 return nullptr;
775
776 if (!RealMulI->hasOneUse() || !ImagMulI->hasOneUse()) {
777 LLVM_DEBUG(dbgs() << " - Mul instruction has multiple uses\n");
778 return nullptr;
779 }
780
781 Value *R0 = RealMulI->getOperand(i: 0);
782 Value *R1 = RealMulI->getOperand(i: 1);
783 Value *I0 = ImagMulI->getOperand(i: 0);
784 Value *I1 = ImagMulI->getOperand(i: 1);
785
786 Value *CommonOperand;
787 Value *UncommonRealOp;
788 Value *UncommonImagOp;
789
790 if (R0 == I0 || R0 == I1) {
791 CommonOperand = R0;
792 UncommonRealOp = R1;
793 } else if (R1 == I0 || R1 == I1) {
794 CommonOperand = R1;
795 UncommonRealOp = R0;
796 } else {
797 LLVM_DEBUG(dbgs() << " - No equal operand\n");
798 return nullptr;
799 }
800
801 UncommonImagOp = (CommonOperand == I0) ? I1 : I0;
802 if (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||
803 Rotation == ComplexDeinterleavingRotation::Rotation_270)
804 std::swap(a&: UncommonRealOp, b&: UncommonImagOp);
805
806 std::pair<Value *, Value *> PartialMatch(
807 (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||
808 Rotation == ComplexDeinterleavingRotation::Rotation_180)
809 ? CommonOperand
810 : nullptr,
811 (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||
812 Rotation == ComplexDeinterleavingRotation::Rotation_270)
813 ? CommonOperand
814 : nullptr);
815
816 auto *CRInst = dyn_cast<Instruction>(Val: CR);
817 auto *CIInst = dyn_cast<Instruction>(Val: CI);
818
819 if (!CRInst || !CIInst) {
820 LLVM_DEBUG(dbgs() << " - Common operands are not instructions.\n");
821 return nullptr;
822 }
823
824 CompositeNode *CNode =
825 identifyNodeWithImplicitAdd(Real: CRInst, Imag: CIInst, PartialMatch);
826 if (!CNode) {
827 LLVM_DEBUG(dbgs() << " - No cnode identified\n");
828 return nullptr;
829 }
830
831 CompositeNode *UncommonRes = identifyNode(R: UncommonRealOp, I: UncommonImagOp);
832 if (!UncommonRes) {
833 LLVM_DEBUG(dbgs() << " - No UncommonRes identified\n");
834 return nullptr;
835 }
836
837 assert(PartialMatch.first && PartialMatch.second);
838 CompositeNode *CommonRes =
839 identifyNode(R: PartialMatch.first, I: PartialMatch.second);
840 if (!CommonRes) {
841 LLVM_DEBUG(dbgs() << " - No CommonRes identified\n");
842 return nullptr;
843 }
844
845 CompositeNode *Node = prepareCompositeNode(
846 Operation: ComplexDeinterleavingOperation::CMulPartial, R: Real, I: Imag);
847 Node->Rotation = Rotation;
848 Node->addOperand(Node: CommonRes);
849 Node->addOperand(Node: UncommonRes);
850 Node->addOperand(Node: CNode);
851 return submitCompositeNode(Node);
852}
853
854ComplexDeinterleavingGraph::CompositeNode *
855ComplexDeinterleavingGraph::identifyAdd(Instruction *Real, Instruction *Imag) {
856 LLVM_DEBUG(dbgs() << "identifyAdd " << *Real << " / " << *Imag << "\n");
857
858 // Determine rotation
859 ComplexDeinterleavingRotation Rotation;
860 if ((Real->getOpcode() == Instruction::FSub &&
861 Imag->getOpcode() == Instruction::FAdd) ||
862 (Real->getOpcode() == Instruction::Sub &&
863 Imag->getOpcode() == Instruction::Add))
864 Rotation = ComplexDeinterleavingRotation::Rotation_90;
865 else if ((Real->getOpcode() == Instruction::FAdd &&
866 Imag->getOpcode() == Instruction::FSub) ||
867 (Real->getOpcode() == Instruction::Add &&
868 Imag->getOpcode() == Instruction::Sub))
869 Rotation = ComplexDeinterleavingRotation::Rotation_270;
870 else {
871 LLVM_DEBUG(dbgs() << " - Unhandled case, rotation is not assigned.\n");
872 return nullptr;
873 }
874
875 auto *AR = dyn_cast<Instruction>(Val: Real->getOperand(i: 0));
876 auto *BI = dyn_cast<Instruction>(Val: Real->getOperand(i: 1));
877 auto *AI = dyn_cast<Instruction>(Val: Imag->getOperand(i: 0));
878 auto *BR = dyn_cast<Instruction>(Val: Imag->getOperand(i: 1));
879
880 if (!AR || !AI || !BR || !BI) {
881 LLVM_DEBUG(dbgs() << " - Not all operands are instructions.\n");
882 return nullptr;
883 }
884
885 CompositeNode *ResA = identifyNode(R: AR, I: AI);
886 if (!ResA) {
887 LLVM_DEBUG(dbgs() << " - AR/AI is not identified as a composite node.\n");
888 return nullptr;
889 }
890 CompositeNode *ResB = identifyNode(R: BR, I: BI);
891 if (!ResB) {
892 LLVM_DEBUG(dbgs() << " - BR/BI is not identified as a composite node.\n");
893 return nullptr;
894 }
895
896 CompositeNode *Node =
897 prepareCompositeNode(Operation: ComplexDeinterleavingOperation::CAdd, R: Real, I: Imag);
898 Node->Rotation = Rotation;
899 Node->addOperand(Node: ResA);
900 Node->addOperand(Node: ResB);
901 return submitCompositeNode(Node);
902}
903
904static bool isInstructionPairAdd(Instruction *A, Instruction *B) {
905 unsigned OpcA = A->getOpcode();
906 unsigned OpcB = B->getOpcode();
907
908 return (OpcA == Instruction::FSub && OpcB == Instruction::FAdd) ||
909 (OpcA == Instruction::FAdd && OpcB == Instruction::FSub) ||
910 (OpcA == Instruction::Sub && OpcB == Instruction::Add) ||
911 (OpcA == Instruction::Add && OpcB == Instruction::Sub);
912}
913
914static bool isInstructionPairMul(Instruction *A, Instruction *B) {
915 auto Pattern =
916 m_BinOp(L: m_FMul(L: m_Value(), R: m_Value()), R: m_FMul(L: m_Value(), R: m_Value()));
917
918 return match(V: A, P: Pattern) && match(V: B, P: Pattern);
919}
920
921static bool isInstructionPotentiallySymmetric(Instruction *I) {
922 switch (I->getOpcode()) {
923 case Instruction::FAdd:
924 case Instruction::FSub:
925 case Instruction::FMul:
926 case Instruction::FNeg:
927 case Instruction::Add:
928 case Instruction::Sub:
929 case Instruction::Mul:
930 return true;
931 default:
932 return false;
933 }
934}
935
936ComplexDeinterleavingGraph::CompositeNode *
937ComplexDeinterleavingGraph::identifySymmetricOperation(ComplexValues &Vals) {
938 auto *FirstReal = cast<Instruction>(Val: Vals[0].Real);
939 unsigned FirstOpc = FirstReal->getOpcode();
940 FastMathFlags CommonFlags;
941 if (isa<FPMathOperator>(Val: FirstReal))
942 CommonFlags = FirstReal->getFastMathFlags();
943 for (auto &V : Vals) {
944 auto *Real = cast<Instruction>(Val: V.Real);
945 auto *Imag = cast<Instruction>(Val: V.Imag);
946 if (Real->getOpcode() != FirstOpc || Imag->getOpcode() != FirstOpc)
947 return nullptr;
948
949 if (!isInstructionPotentiallySymmetric(I: Real) ||
950 !isInstructionPotentiallySymmetric(I: Imag))
951 return nullptr;
952
953 if (isa<FPMathOperator>(Val: FirstReal)) {
954 CommonFlags &= Real->getFastMathFlags();
955 CommonFlags &= Imag->getFastMathFlags();
956 }
957 }
958
959 ComplexValues OpVals;
960 for (auto &V : Vals) {
961 auto *R0 = cast<Instruction>(Val: V.Real)->getOperand(i: 0);
962 auto *I0 = cast<Instruction>(Val: V.Imag)->getOperand(i: 0);
963 OpVals.push_back(Elt: {.Real: R0, .Imag: I0});
964 }
965
966 CompositeNode *Op0 = identifyNode(Vals&: OpVals);
967 CompositeNode *Op1 = nullptr;
968 if (Op0 == nullptr)
969 return nullptr;
970
971 if (FirstReal->isBinaryOp()) {
972 OpVals.clear();
973 for (auto &V : Vals) {
974 auto *R1 = cast<Instruction>(Val: V.Real)->getOperand(i: 1);
975 auto *I1 = cast<Instruction>(Val: V.Imag)->getOperand(i: 1);
976 OpVals.push_back(Elt: {.Real: R1, .Imag: I1});
977 }
978 Op1 = identifyNode(Vals&: OpVals);
979 if (Op1 == nullptr)
980 return nullptr;
981 }
982
983 auto Node =
984 prepareCompositeNode(Operation: ComplexDeinterleavingOperation::Symmetric, Vals);
985 Node->Opcode = FirstReal->getOpcode();
986 if (isa<FPMathOperator>(Val: FirstReal))
987 Node->Flags = CommonFlags;
988
989 Node->addOperand(Node: Op0);
990 if (FirstReal->isBinaryOp())
991 Node->addOperand(Node: Op1);
992
993 return submitCompositeNode(Node);
994}
995
996ComplexDeinterleavingGraph::CompositeNode *
997ComplexDeinterleavingGraph::identifyDotProduct(Value *V) {
998 if (!TL->isComplexDeinterleavingOperationSupported(
999 Operation: ComplexDeinterleavingOperation::CDot, Ty: V->getType())) {
1000 LLVM_DEBUG(dbgs() << "Target doesn't support complex deinterleaving "
1001 "operation CDot with the type "
1002 << *V->getType() << "\n");
1003 return nullptr;
1004 }
1005
1006 auto *Inst = cast<Instruction>(Val: V);
1007 auto *RealUser = cast<Instruction>(Val: *Inst->user_begin());
1008
1009 CompositeNode *CN =
1010 prepareCompositeNode(Operation: ComplexDeinterleavingOperation::CDot, R: Inst, I: nullptr);
1011
1012 CompositeNode *ANode = nullptr;
1013
1014 const Intrinsic::ID PartialReduceInt = Intrinsic::vector_partial_reduce_add;
1015
1016 Value *AReal = nullptr;
1017 Value *AImag = nullptr;
1018 Value *BReal = nullptr;
1019 Value *BImag = nullptr;
1020 Value *Phi = nullptr;
1021
1022 auto UnwrapCast = [](Value *V) -> Value * {
1023 if (auto *CI = dyn_cast<CastInst>(Val: V))
1024 return CI->getOperand(i_nocapture: 0);
1025 return V;
1026 };
1027
1028 auto PatternRot0 = m_Intrinsic<PartialReduceInt>(
1029 Ops: m_Intrinsic<PartialReduceInt>(Ops: m_Value(V&: Phi),
1030 Ops: m_Mul(L: m_Value(V&: BReal), R: m_Value(V&: AReal))),
1031 Ops: m_Neg(V: m_Mul(L: m_Value(V&: BImag), R: m_Value(V&: AImag))));
1032
1033 auto PatternRot270 = m_Intrinsic<PartialReduceInt>(
1034 Ops: m_Intrinsic<PartialReduceInt>(
1035 Ops: m_Value(V&: Phi), Ops: m_Neg(V: m_Mul(L: m_Value(V&: BReal), R: m_Value(V&: AImag)))),
1036 Ops: m_Mul(L: m_Value(V&: BImag), R: m_Value(V&: AReal)));
1037
1038 if (match(V: Inst, P: PatternRot0)) {
1039 CN->Rotation = ComplexDeinterleavingRotation::Rotation_0;
1040 } else if (match(V: Inst, P: PatternRot270)) {
1041 CN->Rotation = ComplexDeinterleavingRotation::Rotation_270;
1042 } else {
1043 Value *A0, *A1;
1044 // The rotations 90 and 180 share the same operation pattern, so inspect the
1045 // order of the operands, identifying where the real and imaginary
1046 // components of A go, to discern between the aforementioned rotations.
1047 auto PatternRot90Rot180 = m_Intrinsic<PartialReduceInt>(
1048 Ops: m_Intrinsic<PartialReduceInt>(Ops: m_Value(V&: Phi),
1049 Ops: m_Mul(L: m_Value(V&: BReal), R: m_Value(V&: A0))),
1050 Ops: m_Mul(L: m_Value(V&: BImag), R: m_Value(V&: A1)));
1051
1052 if (!match(V: Inst, P: PatternRot90Rot180))
1053 return nullptr;
1054
1055 A0 = UnwrapCast(A0);
1056 A1 = UnwrapCast(A1);
1057
1058 // Test if A0 is real/A1 is imag
1059 ANode = identifyNode(R: A0, I: A1);
1060 if (!ANode) {
1061 // Test if A0 is imag/A1 is real
1062 ANode = identifyNode(R: A1, I: A0);
1063 // Unable to identify operand components, thus unable to identify rotation
1064 if (!ANode)
1065 return nullptr;
1066 CN->Rotation = ComplexDeinterleavingRotation::Rotation_90;
1067 AReal = A1;
1068 AImag = A0;
1069 } else {
1070 AReal = A0;
1071 AImag = A1;
1072 CN->Rotation = ComplexDeinterleavingRotation::Rotation_180;
1073 }
1074 }
1075
1076 AReal = UnwrapCast(AReal);
1077 AImag = UnwrapCast(AImag);
1078 BReal = UnwrapCast(BReal);
1079 BImag = UnwrapCast(BImag);
1080
1081 VectorType *VTy = cast<VectorType>(Val: V->getType());
1082 Type *ExpectedOperandTy = VectorType::getSubdividedVectorType(VTy, NumSubdivs: 2);
1083 if (AReal->getType() != ExpectedOperandTy)
1084 return nullptr;
1085 if (AImag->getType() != ExpectedOperandTy)
1086 return nullptr;
1087 if (BReal->getType() != ExpectedOperandTy)
1088 return nullptr;
1089 if (BImag->getType() != ExpectedOperandTy)
1090 return nullptr;
1091
1092 if (Phi->getType() != VTy && RealUser->getType() != VTy)
1093 return nullptr;
1094
1095 CompositeNode *Node = identifyNode(R: AReal, I: AImag);
1096
1097 // In the case that a node was identified to figure out the rotation, ensure
1098 // that trying to identify a node with AReal and AImag post-unwrap results in
1099 // the same node
1100 if (ANode && Node != ANode) {
1101 LLVM_DEBUG(
1102 dbgs()
1103 << "Identified node is different from previously identified node. "
1104 "Unable to confidently generate a complex operation node\n");
1105 return nullptr;
1106 }
1107
1108 CN->addOperand(Node);
1109 CN->addOperand(Node: identifyNode(R: BReal, I: BImag));
1110 CN->addOperand(Node: identifyNode(R: Phi, I: RealUser));
1111
1112 return submitCompositeNode(Node: CN);
1113}
1114
1115ComplexDeinterleavingGraph::CompositeNode *
1116ComplexDeinterleavingGraph::identifyPartialReduction(Value *R, Value *I) {
1117 // Partial reductions don't support non-vector types, so check these first
1118 if (!isa<VectorType>(Val: R->getType()) || !isa<VectorType>(Val: I->getType()))
1119 return nullptr;
1120
1121 if (!R->hasUseList() || !I->hasUseList())
1122 return nullptr;
1123
1124 auto CommonUser =
1125 findCommonBetweenCollections<Value *>(A: R->users(), B: I->users());
1126 if (!CommonUser)
1127 return nullptr;
1128
1129 auto *IInst = dyn_cast<IntrinsicInst>(Val: *CommonUser);
1130 if (!IInst || IInst->getIntrinsicID() != Intrinsic::vector_partial_reduce_add)
1131 return nullptr;
1132
1133 if (CompositeNode *CN = identifyDotProduct(V: IInst))
1134 return CN;
1135
1136 return nullptr;
1137}
1138
1139ComplexDeinterleavingGraph::CompositeNode *
1140ComplexDeinterleavingGraph::identifyNode(ComplexValues &Vals) {
1141 auto It = CachedResult.find(Val: Vals);
1142 if (It != CachedResult.end()) {
1143 LLVM_DEBUG(dbgs() << " - Folding to existing node\n");
1144 return It->second;
1145 }
1146
1147 if (Vals.size() == 1) {
1148 assert(Factor == 2 && "Can only handle interleave factors of 2");
1149 Value *R = Vals[0].Real;
1150 Value *I = Vals[0].Imag;
1151 if (CompositeNode *CN = identifyPartialReduction(R, I))
1152 return CN;
1153 bool IsReduction = RealPHI == R && (!ImagPHI || ImagPHI == I);
1154 if (!IsReduction && R->getType() != I->getType())
1155 return nullptr;
1156 }
1157
1158 if (CompositeNode *CN = identifySplat(Vals))
1159 return CN;
1160
1161 for (auto &V : Vals) {
1162 auto *Real = dyn_cast<Instruction>(Val: V.Real);
1163 auto *Imag = dyn_cast<Instruction>(Val: V.Imag);
1164 if (!Real || !Imag)
1165 return nullptr;
1166 }
1167
1168 if (CompositeNode *CN = identifyDeinterleave(Vals))
1169 return CN;
1170
1171 if (Vals.size() == 1) {
1172 assert(Factor == 2 && "Can only handle interleave factors of 2");
1173 auto *Real = dyn_cast<Instruction>(Val: Vals[0].Real);
1174 auto *Imag = dyn_cast<Instruction>(Val: Vals[0].Imag);
1175 if (CompositeNode *CN = identifyPHINode(Real, Imag))
1176 return CN;
1177
1178 if (CompositeNode *CN = identifySelectNode(Real, Imag))
1179 return CN;
1180
1181 auto *VTy = cast<VectorType>(Val: Real->getType());
1182 auto *NewVTy = VectorType::getDoubleElementsVectorType(VTy);
1183
1184 bool HasCMulSupport = TL->isComplexDeinterleavingOperationSupported(
1185 Operation: ComplexDeinterleavingOperation::CMulPartial, Ty: NewVTy);
1186 bool HasCAddSupport = TL->isComplexDeinterleavingOperationSupported(
1187 Operation: ComplexDeinterleavingOperation::CAdd, Ty: NewVTy);
1188
1189 if (HasCMulSupport && isInstructionPairMul(A: Real, B: Imag)) {
1190 if (CompositeNode *CN = identifyPartialMul(Real, Imag))
1191 return CN;
1192 }
1193
1194 if (HasCAddSupport && isInstructionPairAdd(A: Real, B: Imag)) {
1195 if (CompositeNode *CN = identifyAdd(Real, Imag))
1196 return CN;
1197 }
1198
1199 if (HasCMulSupport && HasCAddSupport) {
1200 if (CompositeNode *CN = identifyReassocNodes(I: Real, J: Imag)) {
1201 return CN;
1202 }
1203 }
1204 }
1205
1206 if (CompositeNode *CN = identifySymmetricOperation(Vals))
1207 return CN;
1208
1209 LLVM_DEBUG(dbgs() << " - Not recognised as a valid pattern.\n");
1210 CachedResult[Vals] = nullptr;
1211 return nullptr;
1212}
1213
1214ComplexDeinterleavingGraph::CompositeNode *
1215ComplexDeinterleavingGraph::identifyReassocNodes(Instruction *Real,
1216 Instruction *Imag) {
1217 auto IsOperationSupported = [](Instruction *I) -> bool {
1218 unsigned Opcode = I->getOpcode();
1219 return match(V: I, P: m_AnyIntrinsic<Intrinsic::fma, Intrinsic::fmuladd>()) ||
1220 Opcode == Instruction::FAdd || Opcode == Instruction::FSub ||
1221 Opcode == Instruction::FNeg || Opcode == Instruction::Add ||
1222 Opcode == Instruction::Sub;
1223 };
1224
1225 if (!IsOperationSupported(Real) || !IsOperationSupported(Imag))
1226 return nullptr;
1227
1228 std::optional<FastMathFlags> Flags;
1229 if (isa<FPMathOperator>(Val: Real)) {
1230 Flags = Real->getFastMathFlags() & Imag->getFastMathFlags();
1231 if (!Flags->allowReassoc()) {
1232 LLVM_DEBUG(
1233 dbgs()
1234 << "the 'Reassoc' attribute is missing in the FastMath flags\n");
1235 return nullptr;
1236 }
1237 }
1238
1239 // Collect multiplications and addend instructions from the given instruction
1240 // while traversing it operands. Additionally, verify that all instructions
1241 // allow reassociation, and narrow \p Flags to the intersection of their
1242 // flags.
1243 auto Collect = [&Flags](Instruction *Insn, SmallVectorImpl<Product> &Muls,
1244 AddendList &Addends) -> bool {
1245 SmallVector<PointerIntPair<Value *, 1, bool>> Worklist = {{Insn, true}};
1246 while (!Worklist.empty()) {
1247 auto [V, IsPositive] = Worklist.pop_back_val();
1248
1249 Instruction *I = dyn_cast<Instruction>(Val: V);
1250 if (!I) {
1251 Addends.emplace_back(Vs&: V, Vs&: IsPositive);
1252 continue;
1253 }
1254
1255 // If an instruction has more than one user, it indicates that it either
1256 // has an external user, which will be later checked by the checkNodes
1257 // function, or it is a subexpression utilized by multiple expressions. In
1258 // the latter case, we will attempt to separately identify the complex
1259 // operation from here in order to create a shared
1260 // ComplexDeinterleavingCompositeNode.
1261 if (I != Insn && I->hasNUsesOrMore(N: 2)) {
1262 LLVM_DEBUG(dbgs() << "Found potential sub-expression: " << *I << "\n");
1263 Addends.emplace_back(Vs&: I, Vs&: IsPositive);
1264 continue;
1265 }
1266 switch (I->getOpcode()) {
1267 case Instruction::FAdd:
1268 case Instruction::Add:
1269 Worklist.emplace_back(Args: I->getOperand(i: 1), Args&: IsPositive);
1270 Worklist.emplace_back(Args: I->getOperand(i: 0), Args&: IsPositive);
1271 break;
1272 case Instruction::FSub:
1273 Worklist.emplace_back(Args: I->getOperand(i: 1), Args: !IsPositive);
1274 Worklist.emplace_back(Args: I->getOperand(i: 0), Args&: IsPositive);
1275 break;
1276 case Instruction::Sub:
1277 if (isNeg(V: I)) {
1278 Worklist.emplace_back(Args: getNegOperand(V: I), Args: !IsPositive);
1279 } else {
1280 Worklist.emplace_back(Args: I->getOperand(i: 1), Args: !IsPositive);
1281 Worklist.emplace_back(Args: I->getOperand(i: 0), Args&: IsPositive);
1282 }
1283 break;
1284 case Instruction::FMul:
1285 case Instruction::Mul: {
1286 Value *A, *B;
1287 if (isNeg(V: I->getOperand(i: 0))) {
1288 A = getNegOperand(V: I->getOperand(i: 0));
1289 IsPositive = !IsPositive;
1290 } else {
1291 A = I->getOperand(i: 0);
1292 }
1293
1294 if (isNeg(V: I->getOperand(i: 1))) {
1295 B = getNegOperand(V: I->getOperand(i: 1));
1296 IsPositive = !IsPositive;
1297 } else {
1298 B = I->getOperand(i: 1);
1299 }
1300 Muls.push_back(Elt: Product{.Multiplier: A, .Multiplicand: B, .IsPositive: IsPositive});
1301 break;
1302 }
1303 case Instruction::FNeg:
1304 Worklist.emplace_back(Args: I->getOperand(i: 0), Args: !IsPositive);
1305 break;
1306 case Instruction::Call: {
1307 Value *A, *B, *C;
1308 if (!match(V: I, P: m_Intrinsic<Intrinsic::fma>(Ops: m_Value(V&: A), Ops: m_Value(V&: B),
1309 Ops: m_Value(V&: C))) &&
1310 !match(V: I, P: m_Intrinsic<Intrinsic::fmuladd>(Ops: m_Value(V&: A), Ops: m_Value(V&: B),
1311 Ops: m_Value(V&: C)))) {
1312 Addends.emplace_back(Vs&: I, Vs&: IsPositive);
1313 continue;
1314 }
1315
1316 bool IsProductPositive = IsPositive;
1317 if (isNeg(V: A)) {
1318 A = getNegOperand(V: A);
1319 IsProductPositive = !IsProductPositive;
1320 }
1321
1322 if (isNeg(V: B)) {
1323 B = getNegOperand(V: B);
1324 IsProductPositive = !IsProductPositive;
1325 }
1326
1327 Muls.push_back(Elt: Product{.Multiplier: A, .Multiplicand: B, .IsPositive: IsProductPositive});
1328 Worklist.emplace_back(Args&: C, Args&: IsPositive);
1329 break;
1330 }
1331 default:
1332 Addends.emplace_back(Vs&: I, Vs&: IsPositive);
1333 continue;
1334 }
1335
1336 if (Flags) {
1337 if (!I->getFastMathFlags().allowReassoc()) {
1338 LLVM_DEBUG(dbgs() << "The instruction does not allow reassociation: "
1339 << *I << "\n");
1340 return false;
1341 }
1342 *Flags &= I->getFastMathFlags();
1343 }
1344 }
1345 return true;
1346 };
1347
1348 SmallVector<Product> RealMuls, ImagMuls;
1349 AddendList RealAddends, ImagAddends;
1350 if (!Collect(Real, RealMuls, RealAddends) ||
1351 !Collect(Imag, ImagMuls, ImagAddends))
1352 return nullptr;
1353
1354 if (RealAddends.size() != ImagAddends.size())
1355 return nullptr;
1356
1357 CompositeNode *FinalNode = nullptr;
1358 if (!RealMuls.empty() || !ImagMuls.empty()) {
1359 // If there are multiplicands, extract positive addend and use it as an
1360 // accumulator
1361 FinalNode = extractPositiveAddend(RealAddends, ImagAddends);
1362 FinalNode = identifyMultiplications(RealMuls, ImagMuls, Accumulator: FinalNode);
1363 if (!FinalNode)
1364 return nullptr;
1365 }
1366
1367 // Identify and process remaining additions
1368 if (!RealAddends.empty() || !ImagAddends.empty()) {
1369 FinalNode = identifyAdditions(RealAddends, ImagAddends, Flags, Accumulator: FinalNode);
1370 if (!FinalNode)
1371 return nullptr;
1372 }
1373 assert(FinalNode && "FinalNode can not be nullptr here");
1374 assert(FinalNode->Vals.size() == 1);
1375 // Set the Real and Imag fields of the final node and submit it
1376 FinalNode->Vals[0].Real = Real;
1377 FinalNode->Vals[0].Imag = Imag;
1378 submitCompositeNode(Node: FinalNode);
1379 return FinalNode;
1380}
1381
1382bool ComplexDeinterleavingGraph::collectPartialMuls(
1383 ArrayRef<Product> RealMuls, ArrayRef<Product> ImagMuls,
1384 SmallVectorImpl<PartialMulCandidate> &PartialMulCandidates) {
1385 // Helper function to extract a common operand from two products
1386 auto FindCommonInstruction = [](const Product &Real,
1387 const Product &Imag) -> Value * {
1388 if (Real.Multiplicand == Imag.Multiplicand ||
1389 Real.Multiplicand == Imag.Multiplier)
1390 return Real.Multiplicand;
1391
1392 if (Real.Multiplier == Imag.Multiplicand ||
1393 Real.Multiplier == Imag.Multiplier)
1394 return Real.Multiplier;
1395
1396 return nullptr;
1397 };
1398
1399 // Iterating over real and imaginary multiplications to find common operands
1400 // If a common operand is found, a partial multiplication candidate is created
1401 // and added to the candidates vector The function returns false if no common
1402 // operands are found for any product
1403 for (unsigned i = 0; i < RealMuls.size(); ++i) {
1404 bool FoundCommon = false;
1405 for (unsigned j = 0; j < ImagMuls.size(); ++j) {
1406 auto *Common = FindCommonInstruction(RealMuls[i], ImagMuls[j]);
1407 if (!Common)
1408 continue;
1409
1410 auto *A = RealMuls[i].Multiplicand == Common ? RealMuls[i].Multiplier
1411 : RealMuls[i].Multiplicand;
1412 auto *B = ImagMuls[j].Multiplicand == Common ? ImagMuls[j].Multiplier
1413 : ImagMuls[j].Multiplicand;
1414
1415 auto Node = identifyNode(R: A, I: B);
1416 if (Node) {
1417 FoundCommon = true;
1418 PartialMulCandidates.push_back(Elt: {.Common: Common, .Node: Node, .RealIdx: i, .ImagIdx: j, .IsNodeInverted: false});
1419 }
1420
1421 Node = identifyNode(R: B, I: A);
1422 if (Node) {
1423 FoundCommon = true;
1424 PartialMulCandidates.push_back(Elt: {.Common: Common, .Node: Node, .RealIdx: i, .ImagIdx: j, .IsNodeInverted: true});
1425 }
1426 }
1427 if (!FoundCommon)
1428 return false;
1429 }
1430 return true;
1431}
1432
1433ComplexDeinterleavingGraph::CompositeNode *
1434ComplexDeinterleavingGraph::identifyMultiplications(
1435 SmallVectorImpl<Product> &RealMuls, SmallVectorImpl<Product> &ImagMuls,
1436 CompositeNode *Accumulator = nullptr) {
1437 if (RealMuls.size() != ImagMuls.size())
1438 return nullptr;
1439
1440 SmallVector<PartialMulCandidate> Info;
1441 if (!collectPartialMuls(RealMuls, ImagMuls, PartialMulCandidates&: Info))
1442 return nullptr;
1443
1444 // Map to store common instruction to node pointers
1445 DenseMap<Value *, CompositeNode *> CommonToNode;
1446 SmallVector<bool> Processed(Info.size(), false);
1447 for (unsigned I = 0; I < Info.size(); ++I) {
1448 if (Processed[I])
1449 continue;
1450
1451 PartialMulCandidate &InfoA = Info[I];
1452 for (unsigned J = I + 1; J < Info.size(); ++J) {
1453 if (Processed[J])
1454 continue;
1455
1456 PartialMulCandidate &InfoB = Info[J];
1457 auto *InfoReal = &InfoA;
1458 auto *InfoImag = &InfoB;
1459
1460 auto NodeFromCommon = identifyNode(R: InfoReal->Common, I: InfoImag->Common);
1461 if (!NodeFromCommon) {
1462 std::swap(a&: InfoReal, b&: InfoImag);
1463 NodeFromCommon = identifyNode(R: InfoReal->Common, I: InfoImag->Common);
1464 }
1465 if (!NodeFromCommon)
1466 continue;
1467
1468 CommonToNode[InfoReal->Common] = NodeFromCommon;
1469 CommonToNode[InfoImag->Common] = NodeFromCommon;
1470 Processed[I] = true;
1471 Processed[J] = true;
1472 }
1473 }
1474
1475 SmallVector<bool> ProcessedReal(RealMuls.size(), false);
1476 SmallVector<bool> ProcessedImag(ImagMuls.size(), false);
1477 CompositeNode *Result = Accumulator;
1478 for (auto &PMI : Info) {
1479 if (ProcessedReal[PMI.RealIdx] || ProcessedImag[PMI.ImagIdx])
1480 continue;
1481
1482 auto It = CommonToNode.find(Val: PMI.Common);
1483 // TODO: Process independent complex multiplications. Cases like this:
1484 // A.real() * B where both A and B are complex numbers.
1485 if (It == CommonToNode.end()) {
1486 LLVM_DEBUG({
1487 dbgs() << "Unprocessed independent partial multiplication:\n";
1488 for (auto *Mul : {&RealMuls[PMI.RealIdx], &RealMuls[PMI.RealIdx]})
1489 dbgs().indent(4) << (Mul->IsPositive ? "+" : "-") << *Mul->Multiplier
1490 << " multiplied by " << *Mul->Multiplicand << "\n";
1491 });
1492 return nullptr;
1493 }
1494
1495 auto &RealMul = RealMuls[PMI.RealIdx];
1496 auto &ImagMul = ImagMuls[PMI.ImagIdx];
1497
1498 auto NodeA = It->second;
1499 auto NodeB = PMI.Node;
1500 auto IsMultiplicandReal = PMI.Common == NodeA->Vals[0].Real;
1501 // The following table illustrates the relationship between multiplications
1502 // and rotations. If we consider the multiplication (X + iY) * (U + iV), we
1503 // can see:
1504 //
1505 // Rotation | Real | Imag |
1506 // ---------+--------+--------+
1507 // 0 | x * u | x * v |
1508 // 90 | -y * v | y * u |
1509 // 180 | -x * u | -x * v |
1510 // 270 | y * v | -y * u |
1511 //
1512 // Check if the candidate can indeed be represented by partial
1513 // multiplication
1514 // TODO: Add support for multiplication by complex one
1515 if ((IsMultiplicandReal && PMI.IsNodeInverted) ||
1516 (!IsMultiplicandReal && !PMI.IsNodeInverted))
1517 continue;
1518
1519 // Determine the rotation based on the multiplications
1520 ComplexDeinterleavingRotation Rotation;
1521 if (IsMultiplicandReal) {
1522 // Detect 0 and 180 degrees rotation
1523 if (RealMul.IsPositive && ImagMul.IsPositive)
1524 Rotation = llvm::ComplexDeinterleavingRotation::Rotation_0;
1525 else if (!RealMul.IsPositive && !ImagMul.IsPositive)
1526 Rotation = llvm::ComplexDeinterleavingRotation::Rotation_180;
1527 else
1528 continue;
1529
1530 } else {
1531 // Detect 90 and 270 degrees rotation
1532 if (!RealMul.IsPositive && ImagMul.IsPositive)
1533 Rotation = llvm::ComplexDeinterleavingRotation::Rotation_90;
1534 else if (RealMul.IsPositive && !ImagMul.IsPositive)
1535 Rotation = llvm::ComplexDeinterleavingRotation::Rotation_270;
1536 else
1537 continue;
1538 }
1539
1540 LLVM_DEBUG({
1541 dbgs() << "Identified partial multiplication (X, Y) * (U, V):\n";
1542 dbgs().indent(4) << "X: " << *NodeA->Vals[0].Real << "\n";
1543 dbgs().indent(4) << "Y: " << *NodeA->Vals[0].Imag << "\n";
1544 dbgs().indent(4) << "U: " << *NodeB->Vals[0].Real << "\n";
1545 dbgs().indent(4) << "V: " << *NodeB->Vals[0].Imag << "\n";
1546 dbgs().indent(4) << "Rotation - " << (int)Rotation * 90 << "\n";
1547 });
1548
1549 CompositeNode *NodeMul = prepareCompositeNode(
1550 Operation: ComplexDeinterleavingOperation::CMulPartial, R: nullptr, I: nullptr);
1551 NodeMul->Rotation = Rotation;
1552 NodeMul->addOperand(Node: NodeA);
1553 NodeMul->addOperand(Node: NodeB);
1554 if (Result)
1555 NodeMul->addOperand(Node: Result);
1556 submitCompositeNode(Node: NodeMul);
1557 Result = NodeMul;
1558 ProcessedReal[PMI.RealIdx] = true;
1559 ProcessedImag[PMI.ImagIdx] = true;
1560 }
1561
1562 // Ensure all products have been processed, if not return nullptr.
1563 if (!all_of(Range&: ProcessedReal, P: [](bool V) { return V; }) ||
1564 !all_of(Range&: ProcessedImag, P: [](bool V) { return V; })) {
1565
1566 // Dump debug information about which partial multiplications are not
1567 // processed.
1568 LLVM_DEBUG({
1569 dbgs() << "Unprocessed products (Real):\n";
1570 for (size_t i = 0; i < ProcessedReal.size(); ++i) {
1571 if (!ProcessedReal[i])
1572 dbgs().indent(4) << (RealMuls[i].IsPositive ? "+" : "-")
1573 << *RealMuls[i].Multiplier << " multiplied by "
1574 << *RealMuls[i].Multiplicand << "\n";
1575 }
1576 dbgs() << "Unprocessed products (Imag):\n";
1577 for (size_t i = 0; i < ProcessedImag.size(); ++i) {
1578 if (!ProcessedImag[i])
1579 dbgs().indent(4) << (ImagMuls[i].IsPositive ? "+" : "-")
1580 << *ImagMuls[i].Multiplier << " multiplied by "
1581 << *ImagMuls[i].Multiplicand << "\n";
1582 }
1583 });
1584 return nullptr;
1585 }
1586
1587 return Result;
1588}
1589
1590ComplexDeinterleavingGraph::CompositeNode *
1591ComplexDeinterleavingGraph::identifyAdditions(
1592 AddendList &RealAddends, AddendList &ImagAddends,
1593 std::optional<FastMathFlags> Flags, CompositeNode *Accumulator = nullptr) {
1594 if (RealAddends.size() != ImagAddends.size())
1595 return nullptr;
1596
1597 CompositeNode *Result = nullptr;
1598 // If we have accumulator use it as first addend
1599 if (Accumulator)
1600 Result = Accumulator;
1601 // Otherwise find an element with both positive real and imaginary parts.
1602 else
1603 Result = extractPositiveAddend(RealAddends, ImagAddends);
1604
1605 if (!Result)
1606 return nullptr;
1607
1608 while (!RealAddends.empty()) {
1609 auto ItR = RealAddends.begin();
1610 auto [R, IsPositiveR] = *ItR;
1611
1612 bool FoundImag = false;
1613 for (auto ItI = ImagAddends.begin(); ItI != ImagAddends.end(); ++ItI) {
1614 auto [I, IsPositiveI] = *ItI;
1615 ComplexDeinterleavingRotation Rotation;
1616 if (IsPositiveR && IsPositiveI)
1617 Rotation = ComplexDeinterleavingRotation::Rotation_0;
1618 else if (!IsPositiveR && IsPositiveI)
1619 Rotation = ComplexDeinterleavingRotation::Rotation_90;
1620 else if (!IsPositiveR && !IsPositiveI)
1621 Rotation = ComplexDeinterleavingRotation::Rotation_180;
1622 else
1623 Rotation = ComplexDeinterleavingRotation::Rotation_270;
1624
1625 CompositeNode *AddNode = nullptr;
1626 if (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||
1627 Rotation == ComplexDeinterleavingRotation::Rotation_180) {
1628 AddNode = identifyNode(R, I);
1629 } else {
1630 AddNode = identifyNode(R: I, I: R);
1631 }
1632 if (AddNode) {
1633 LLVM_DEBUG({
1634 dbgs() << "Identified addition:\n";
1635 dbgs().indent(4) << "X: " << *R << "\n";
1636 dbgs().indent(4) << "Y: " << *I << "\n";
1637 dbgs().indent(4) << "Rotation - " << (int)Rotation * 90 << "\n";
1638 });
1639
1640 CompositeNode *TmpNode = nullptr;
1641 if (Rotation == llvm::ComplexDeinterleavingRotation::Rotation_0) {
1642 TmpNode = prepareCompositeNode(
1643 Operation: ComplexDeinterleavingOperation::Symmetric, R: nullptr, I: nullptr);
1644 if (Flags) {
1645 TmpNode->Opcode = Instruction::FAdd;
1646 TmpNode->Flags = *Flags;
1647 } else {
1648 TmpNode->Opcode = Instruction::Add;
1649 }
1650 } else if (Rotation ==
1651 llvm::ComplexDeinterleavingRotation::Rotation_180) {
1652 TmpNode = prepareCompositeNode(
1653 Operation: ComplexDeinterleavingOperation::Symmetric, R: nullptr, I: nullptr);
1654 if (Flags) {
1655 TmpNode->Opcode = Instruction::FSub;
1656 TmpNode->Flags = *Flags;
1657 } else {
1658 TmpNode->Opcode = Instruction::Sub;
1659 }
1660 } else {
1661 TmpNode = prepareCompositeNode(Operation: ComplexDeinterleavingOperation::CAdd,
1662 R: nullptr, I: nullptr);
1663 TmpNode->Rotation = Rotation;
1664 }
1665
1666 TmpNode->addOperand(Node: Result);
1667 TmpNode->addOperand(Node: AddNode);
1668 submitCompositeNode(Node: TmpNode);
1669 Result = TmpNode;
1670 RealAddends.erase(I: ItR);
1671 ImagAddends.erase(I: ItI);
1672 FoundImag = true;
1673 break;
1674 }
1675 }
1676 if (!FoundImag)
1677 return nullptr;
1678 }
1679 return Result;
1680}
1681
1682ComplexDeinterleavingGraph::CompositeNode *
1683ComplexDeinterleavingGraph::extractPositiveAddend(AddendList &RealAddends,
1684 AddendList &ImagAddends) {
1685 for (auto ItR = RealAddends.begin(); ItR != RealAddends.end(); ++ItR) {
1686 for (auto ItI = ImagAddends.begin(); ItI != ImagAddends.end(); ++ItI) {
1687 auto [R, IsPositiveR] = *ItR;
1688 auto [I, IsPositiveI] = *ItI;
1689 if (IsPositiveR && IsPositiveI) {
1690 auto Result = identifyNode(R, I);
1691 if (Result) {
1692 RealAddends.erase(I: ItR);
1693 ImagAddends.erase(I: ItI);
1694 return Result;
1695 }
1696 }
1697 }
1698 }
1699 return nullptr;
1700}
1701
1702bool ComplexDeinterleavingGraph::identifyNodes(Instruction *RootI) {
1703 // This potential root instruction might already have been recognized as
1704 // reduction. Because RootToNode maps both Real and Imaginary parts to
1705 // CompositeNode we should choose only one either Real or Imag instruction to
1706 // use as an anchor for generating complex instruction.
1707 auto It = RootToNode.find(Val: RootI);
1708 if (It != RootToNode.end()) {
1709 auto RootNode = It->second;
1710 assert(RootNode->Operation ==
1711 ComplexDeinterleavingOperation::ReductionOperation ||
1712 RootNode->Operation ==
1713 ComplexDeinterleavingOperation::ReductionSingle);
1714 assert(RootNode->Vals.size() == 1 &&
1715 "Cannot handle reductions involving multiple complex values");
1716 // Find out which part, Real or Imag, comes later, and only if we come to
1717 // the latest part, add it to OrderedRoots.
1718 auto *R = cast<Instruction>(Val: RootNode->Vals[0].Real);
1719 auto *I = RootNode->Vals[0].Imag ? cast<Instruction>(Val: RootNode->Vals[0].Imag)
1720 : nullptr;
1721
1722 Instruction *ReplacementAnchor;
1723 if (I)
1724 ReplacementAnchor = R->comesBefore(Other: I) ? I : R;
1725 else
1726 ReplacementAnchor = R;
1727
1728 if (ReplacementAnchor != RootI)
1729 return false;
1730 OrderedRoots.push_back(Elt: RootI);
1731 return true;
1732 }
1733
1734 auto RootNode = identifyRoot(I: RootI);
1735 if (!RootNode)
1736 return false;
1737
1738 LLVM_DEBUG({
1739 Function *F = RootI->getFunction();
1740 BasicBlock *B = RootI->getParent();
1741 dbgs() << "Complex deinterleaving graph for " << F->getName()
1742 << "::" << B->getName() << ".\n";
1743 dump(dbgs());
1744 dbgs() << "\n";
1745 });
1746 RootToNode[RootI] = RootNode;
1747 OrderedRoots.push_back(Elt: RootI);
1748 return true;
1749}
1750
1751bool ComplexDeinterleavingGraph::collectPotentialReductions(BasicBlock *B) {
1752 bool FoundPotentialReduction = false;
1753 if (Factor != 2)
1754 return false;
1755
1756 auto *Br = dyn_cast<CondBrInst>(Val: B->getTerminator());
1757 if (!Br)
1758 return false;
1759
1760 // Identify simple one-block loop
1761 if (Br->getSuccessor(i: 0) != B && Br->getSuccessor(i: 1) != B)
1762 return false;
1763
1764 for (auto &PHI : B->phis()) {
1765 if (PHI.getNumIncomingValues() != 2)
1766 continue;
1767
1768 if (!PHI.getType()->isVectorTy())
1769 continue;
1770
1771 auto *ReductionOp = dyn_cast<Instruction>(Val: PHI.getIncomingValueForBlock(BB: B));
1772 if (!ReductionOp)
1773 continue;
1774
1775 // Check if final instruction is reduced outside of current block
1776 Instruction *FinalReduction = nullptr;
1777 auto NumUsers = 0u;
1778 for (auto *U : ReductionOp->users()) {
1779 ++NumUsers;
1780 if (U == &PHI)
1781 continue;
1782 FinalReduction = dyn_cast<Instruction>(Val: U);
1783 }
1784
1785 if (NumUsers != 2 || !FinalReduction || FinalReduction->getParent() == B ||
1786 isa<PHINode>(Val: FinalReduction))
1787 continue;
1788
1789 ReductionInfo[ReductionOp] = {&PHI, FinalReduction};
1790 BackEdge = B;
1791 auto BackEdgeIdx = PHI.getBasicBlockIndex(BB: B);
1792 auto IncomingIdx = BackEdgeIdx == 0 ? 1 : 0;
1793 Incoming = PHI.getIncomingBlock(i: IncomingIdx);
1794 FoundPotentialReduction = true;
1795
1796 // If the initial value of PHINode is an Instruction, consider it a leaf
1797 // value of a complex deinterleaving graph.
1798 if (auto *InitPHI =
1799 dyn_cast<Instruction>(Val: PHI.getIncomingValueForBlock(BB: Incoming)))
1800 FinalInstructions.insert(Ptr: InitPHI);
1801 }
1802 return FoundPotentialReduction;
1803}
1804
1805void ComplexDeinterleavingGraph::identifyReductionNodes() {
1806 assert(Factor == 2 && "Cannot handle multiple complex values");
1807
1808 SmallVector<bool> Processed(ReductionInfo.size(), false);
1809 SmallVector<Instruction *> OperationInstruction;
1810 for (auto &P : ReductionInfo)
1811 OperationInstruction.push_back(Elt: P.first);
1812
1813 // Identify a complex computation by evaluating two reduction operations that
1814 // potentially could be involved
1815 for (size_t i = 0; i < OperationInstruction.size(); ++i) {
1816 if (Processed[i])
1817 continue;
1818 for (size_t j = i + 1; j < OperationInstruction.size(); ++j) {
1819 if (Processed[j])
1820 continue;
1821 auto *Real = OperationInstruction[i];
1822 auto *Imag = OperationInstruction[j];
1823 if (Real->getType() != Imag->getType())
1824 continue;
1825
1826 RealPHI = ReductionInfo[Real].first;
1827 ImagPHI = ReductionInfo[Imag].first;
1828 PHIsFound = false;
1829 auto Node = identifyNode(R: Real, I: Imag);
1830 if (!Node) {
1831 std::swap(a&: Real, b&: Imag);
1832 std::swap(a&: RealPHI, b&: ImagPHI);
1833 Node = identifyNode(R: Real, I: Imag);
1834 }
1835
1836 // If a node is identified and reduction PHINode is used in the chain of
1837 // operations, mark its operation instructions as used to prevent
1838 // re-identification and attach the node to the real part
1839 if (Node && PHIsFound) {
1840 LLVM_DEBUG(dbgs() << "Identified reduction starting from instructions: "
1841 << *Real << " / " << *Imag << "\n");
1842 Processed[i] = true;
1843 Processed[j] = true;
1844 auto RootNode = prepareCompositeNode(
1845 Operation: ComplexDeinterleavingOperation::ReductionOperation, R: Real, I: Imag);
1846 RootNode->addOperand(Node);
1847 RootToNode[Real] = RootNode;
1848 RootToNode[Imag] = RootNode;
1849 submitCompositeNode(Node: RootNode);
1850 break;
1851 }
1852 }
1853
1854 auto *Real = OperationInstruction[i];
1855 // We want to check that we have 2 operands, but the function attributes
1856 // being counted as operands bloats this value.
1857 if (Processed[i] || Real->getNumOperands() < 2)
1858 continue;
1859
1860 // Can only combined integer reductions at the moment.
1861 if (!ReductionInfo[Real].second->getType()->isIntegerTy())
1862 continue;
1863
1864 RealPHI = ReductionInfo[Real].first;
1865 ImagPHI = nullptr;
1866 PHIsFound = false;
1867 auto Node = identifyNode(R: Real->getOperand(i: 0), I: Real->getOperand(i: 1));
1868 if (Node && PHIsFound) {
1869 LLVM_DEBUG(
1870 dbgs() << "Identified single reduction starting from instruction: "
1871 << *Real << "/" << *ReductionInfo[Real].second << "\n");
1872
1873 // Reducing to a single vector is not supported, only permit reducing down
1874 // to scalar values.
1875 // Doing this here will leave the prior node in the graph,
1876 // however with no uses the node will be unreachable by the replacement
1877 // process. That along with the usage outside the graph should prevent the
1878 // replacement process from kicking off at all for this graph.
1879 // TODO Add support for reducing to a single vector value
1880 if (ReductionInfo[Real].second->getType()->isVectorTy())
1881 continue;
1882
1883 Processed[i] = true;
1884 auto RootNode = prepareCompositeNode(
1885 Operation: ComplexDeinterleavingOperation::ReductionSingle, R: Real, I: nullptr);
1886 RootNode->addOperand(Node);
1887 RootToNode[Real] = RootNode;
1888 submitCompositeNode(Node: RootNode);
1889 }
1890 }
1891
1892 RealPHI = nullptr;
1893 ImagPHI = nullptr;
1894}
1895
1896bool ComplexDeinterleavingGraph::checkNodes() {
1897 bool FoundDeinterleaveNode = false;
1898 for (CompositeNode *N : CompositeNodes) {
1899 if (!N->areOperandsValid())
1900 return false;
1901
1902 if (N->Operation == ComplexDeinterleavingOperation::Deinterleave)
1903 FoundDeinterleaveNode = true;
1904 }
1905
1906 // We need a deinterleave node in order to guarantee that we're working with
1907 // complex numbers.
1908 if (!FoundDeinterleaveNode) {
1909 LLVM_DEBUG(
1910 dbgs() << "Couldn't find a deinterleave node within the graph, cannot "
1911 "guarantee safety during graph transformation.\n");
1912 return false;
1913 }
1914
1915 // Collect all instructions from roots to leaves
1916 SmallPtrSet<Instruction *, 16> AllInstructions;
1917 SmallVector<Instruction *, 8> Worklist;
1918 for (auto &Pair : RootToNode)
1919 Worklist.push_back(Elt: Pair.first);
1920
1921 // Extract all instructions that are used by all XCMLA/XCADD/ADD/SUB/NEG
1922 // chains
1923 while (!Worklist.empty()) {
1924 auto *I = Worklist.pop_back_val();
1925
1926 if (!AllInstructions.insert(Ptr: I).second)
1927 continue;
1928
1929 for (Value *Op : I->operands()) {
1930 if (auto *OpI = dyn_cast<Instruction>(Val: Op)) {
1931 if (!FinalInstructions.count(Ptr: I))
1932 Worklist.emplace_back(Args&: OpI);
1933 }
1934 }
1935 }
1936
1937 // Find instructions that have users outside of chain
1938 for (auto *I : AllInstructions) {
1939 // Skip root nodes
1940 if (RootToNode.count(Val: I))
1941 continue;
1942
1943 for (User *U : I->users()) {
1944 if (AllInstructions.count(Ptr: cast<Instruction>(Val: U)))
1945 continue;
1946
1947 // Found an instruction that is not used by XCMLA/XCADD chain
1948 Worklist.emplace_back(Args&: I);
1949 break;
1950 }
1951 }
1952
1953 // If any instructions are found to be used outside, find and remove roots
1954 // that somehow connect to those instructions.
1955 SmallPtrSet<Instruction *, 16> Visited;
1956 while (!Worklist.empty()) {
1957 auto *I = Worklist.pop_back_val();
1958 if (!Visited.insert(Ptr: I).second)
1959 continue;
1960
1961 // Found an impacted root node. Removing it from the nodes to be
1962 // deinterleaved
1963 if (RootToNode.count(Val: I)) {
1964 LLVM_DEBUG(dbgs() << "Instruction " << *I
1965 << " could be deinterleaved but its chain of complex "
1966 "operations have an outside user\n");
1967 RootToNode.erase(Val: I);
1968 }
1969
1970 if (!AllInstructions.count(Ptr: I) || FinalInstructions.count(Ptr: I))
1971 continue;
1972
1973 for (User *U : I->users())
1974 Worklist.emplace_back(Args: cast<Instruction>(Val: U));
1975
1976 for (Value *Op : I->operands()) {
1977 if (auto *OpI = dyn_cast<Instruction>(Val: Op))
1978 Worklist.emplace_back(Args&: OpI);
1979 }
1980 }
1981 return !RootToNode.empty();
1982}
1983
1984ComplexDeinterleavingGraph::CompositeNode *
1985ComplexDeinterleavingGraph::identifyRoot(Instruction *RootI) {
1986 if (auto *Intrinsic = dyn_cast<IntrinsicInst>(Val: RootI)) {
1987 if (Intrinsic::getInterleaveIntrinsicID(Factor) !=
1988 Intrinsic->getIntrinsicID())
1989 return nullptr;
1990
1991 ComplexValues Vals;
1992 for (unsigned I = 0; I < Factor; I += 2) {
1993 auto *Real = dyn_cast<Instruction>(Val: Intrinsic->getOperand(i_nocapture: I));
1994 auto *Imag = dyn_cast<Instruction>(Val: Intrinsic->getOperand(i_nocapture: I + 1));
1995 if (!Real || !Imag)
1996 return nullptr;
1997 Vals.push_back(Elt: {.Real: Real, .Imag: Imag});
1998 }
1999
2000 ComplexDeinterleavingGraph::CompositeNode *Node1 = identifyNode(Vals);
2001 if (!Node1)
2002 return nullptr;
2003 return Node1;
2004 }
2005
2006 // TODO: We could also add support for fixed-width interleave factors of 4
2007 // and above, but currently for symmetric operations the interleaves and
2008 // deinterleaves are already removed by VectorCombine. If we extend this to
2009 // permit complex multiplications, reductions, etc. then we should also add
2010 // support for fixed-width here.
2011 if (Factor != 2)
2012 return nullptr;
2013
2014 auto *SVI = dyn_cast<ShuffleVectorInst>(Val: RootI);
2015 if (!SVI)
2016 return nullptr;
2017
2018 // Look for a shufflevector that takes separate vectors of the real and
2019 // imaginary components and recombines them into a single vector.
2020 if (!isInterleavingMask(Mask: SVI->getShuffleMask()))
2021 return nullptr;
2022
2023 Instruction *Real;
2024 Instruction *Imag;
2025 if (!match(V: RootI, P: m_Shuffle(v1: m_Instruction(I&: Real), v2: m_Instruction(I&: Imag))))
2026 return nullptr;
2027
2028 return identifyNode(R: Real, I: Imag);
2029}
2030
2031ComplexDeinterleavingGraph::CompositeNode *
2032ComplexDeinterleavingGraph::identifyDeinterleave(ComplexValues &Vals) {
2033 Instruction *II = nullptr;
2034
2035 // Must be at least one complex value.
2036 auto CheckExtract = [&](Value *V, unsigned ExpectedIdx,
2037 Instruction *ExpectedInsn) -> ExtractValueInst * {
2038 auto *EVI = dyn_cast<ExtractValueInst>(Val: V);
2039 if (!EVI || EVI->getNumIndices() != 1 ||
2040 EVI->getIndices()[0] != ExpectedIdx ||
2041 !isa<Instruction>(Val: EVI->getAggregateOperand()) ||
2042 (ExpectedInsn && ExpectedInsn != EVI->getAggregateOperand()))
2043 return nullptr;
2044 return EVI;
2045 };
2046
2047 for (unsigned Idx = 0; Idx < Vals.size(); Idx++) {
2048 ExtractValueInst *RealEVI = CheckExtract(Vals[Idx].Real, Idx * 2, II);
2049 if (RealEVI && Idx == 0)
2050 II = cast<Instruction>(Val: RealEVI->getAggregateOperand());
2051 if (!RealEVI || !CheckExtract(Vals[Idx].Imag, (Idx * 2) + 1, II)) {
2052 II = nullptr;
2053 break;
2054 }
2055 }
2056
2057 if (auto *IntrinsicII = dyn_cast_or_null<IntrinsicInst>(Val: II)) {
2058 if (IntrinsicII->getIntrinsicID() !=
2059 Intrinsic::getDeinterleaveIntrinsicID(Factor: 2 * Vals.size()))
2060 return nullptr;
2061
2062 // The remaining should match too.
2063 CompositeNode *PlaceholderNode = prepareCompositeNode(
2064 Operation: llvm::ComplexDeinterleavingOperation::Deinterleave, Vals);
2065 PlaceholderNode->ReplacementNode = II->getOperand(i: 0);
2066 for (auto &V : Vals) {
2067 FinalInstructions.insert(Ptr: cast<Instruction>(Val: V.Real));
2068 FinalInstructions.insert(Ptr: cast<Instruction>(Val: V.Imag));
2069 }
2070 return submitCompositeNode(Node: PlaceholderNode);
2071 }
2072
2073 if (Vals.size() != 1)
2074 return nullptr;
2075
2076 Value *Real = Vals[0].Real;
2077 Value *Imag = Vals[0].Imag;
2078 auto *RealShuffle = dyn_cast<ShuffleVectorInst>(Val: Real);
2079 auto *ImagShuffle = dyn_cast<ShuffleVectorInst>(Val: Imag);
2080 if (!RealShuffle || !ImagShuffle) {
2081 if (RealShuffle || ImagShuffle)
2082 LLVM_DEBUG(dbgs() << " - There's a shuffle where there shouldn't be.\n");
2083 return nullptr;
2084 }
2085
2086 Value *RealOp1 = RealShuffle->getOperand(i_nocapture: 1);
2087 if (!isa<UndefValue>(Val: RealOp1) && !match(V: RealOp1, P: m_Zero())) {
2088 LLVM_DEBUG(dbgs() << " - RealOp1 is not undef or zero.\n");
2089 return nullptr;
2090 }
2091 Value *ImagOp1 = ImagShuffle->getOperand(i_nocapture: 1);
2092 if (!isa<UndefValue>(Val: ImagOp1) && !match(V: ImagOp1, P: m_Zero())) {
2093 LLVM_DEBUG(dbgs() << " - ImagOp1 is not undef or zero.\n");
2094 return nullptr;
2095 }
2096
2097 Value *RealOp0 = RealShuffle->getOperand(i_nocapture: 0);
2098 Value *ImagOp0 = ImagShuffle->getOperand(i_nocapture: 0);
2099
2100 if (RealOp0 != ImagOp0) {
2101 LLVM_DEBUG(dbgs() << " - Shuffle operands are not equal.\n");
2102 return nullptr;
2103 }
2104
2105 ArrayRef<int> RealMask = RealShuffle->getShuffleMask();
2106 ArrayRef<int> ImagMask = ImagShuffle->getShuffleMask();
2107 if (!isDeinterleavingMask(Mask: RealMask) || !isDeinterleavingMask(Mask: ImagMask)) {
2108 LLVM_DEBUG(dbgs() << " - Masks are not deinterleaving.\n");
2109 return nullptr;
2110 }
2111
2112 if (RealMask[0] != 0 || ImagMask[0] != 1) {
2113 LLVM_DEBUG(dbgs() << " - Masks do not have the correct initial value.\n");
2114 return nullptr;
2115 }
2116
2117 // Type checking, the shuffle type should be a vector type of the same
2118 // scalar type, but half the size
2119 auto CheckType = [&](ShuffleVectorInst *Shuffle) {
2120 Value *Op = Shuffle->getOperand(i_nocapture: 0);
2121 auto *ShuffleTy = cast<FixedVectorType>(Val: Shuffle->getType());
2122 auto *OpTy = cast<FixedVectorType>(Val: Op->getType());
2123
2124 if (OpTy->getScalarType() != ShuffleTy->getScalarType())
2125 return false;
2126 if ((ShuffleTy->getNumElements() * 2) != OpTy->getNumElements())
2127 return false;
2128
2129 return true;
2130 };
2131
2132 auto CheckDeinterleavingShuffle = [&](ShuffleVectorInst *Shuffle) -> bool {
2133 if (!CheckType(Shuffle))
2134 return false;
2135
2136 ArrayRef<int> Mask = Shuffle->getShuffleMask();
2137 int Last = *Mask.rbegin();
2138
2139 Value *Op = Shuffle->getOperand(i_nocapture: 0);
2140 auto *OpTy = cast<FixedVectorType>(Val: Op->getType());
2141 int NumElements = OpTy->getNumElements();
2142
2143 // Ensure that the deinterleaving shuffle only pulls from the first
2144 // shuffle operand.
2145 return Last < NumElements;
2146 };
2147
2148 if (RealShuffle->getType() != ImagShuffle->getType()) {
2149 LLVM_DEBUG(dbgs() << " - Shuffle types aren't equal.\n");
2150 return nullptr;
2151 }
2152 if (!CheckDeinterleavingShuffle(RealShuffle)) {
2153 LLVM_DEBUG(dbgs() << " - RealShuffle is invalid type.\n");
2154 return nullptr;
2155 }
2156 if (!CheckDeinterleavingShuffle(ImagShuffle)) {
2157 LLVM_DEBUG(dbgs() << " - ImagShuffle is invalid type.\n");
2158 return nullptr;
2159 }
2160
2161 CompositeNode *PlaceholderNode =
2162 prepareCompositeNode(Operation: llvm::ComplexDeinterleavingOperation::Deinterleave,
2163 R: RealShuffle, I: ImagShuffle);
2164 PlaceholderNode->ReplacementNode = RealShuffle->getOperand(i_nocapture: 0);
2165 FinalInstructions.insert(Ptr: RealShuffle);
2166 FinalInstructions.insert(Ptr: ImagShuffle);
2167 return submitCompositeNode(Node: PlaceholderNode);
2168}
2169
2170ComplexDeinterleavingGraph::CompositeNode *
2171ComplexDeinterleavingGraph::identifySplat(ComplexValues &Vals) {
2172 auto IsSplat = [](Value *V) -> bool {
2173 // Fixed-width vector with constants
2174 if (isa<ConstantDataVector>(Val: V))
2175 return true;
2176
2177 if (isa<ConstantInt>(Val: V) || isa<ConstantFP>(Val: V))
2178 return isa<VectorType>(Val: V->getType());
2179
2180 VectorType *VTy;
2181 ArrayRef<int> Mask;
2182 // Splats are represented differently depending on whether the repeated
2183 // value is a constant or an Instruction
2184 if (auto *Const = dyn_cast<ConstantExpr>(Val: V)) {
2185 if (Const->getOpcode() != Instruction::ShuffleVector)
2186 return false;
2187 VTy = cast<VectorType>(Val: Const->getType());
2188 Mask = Const->getShuffleMask();
2189 } else if (auto *Shuf = dyn_cast<ShuffleVectorInst>(Val: V)) {
2190 VTy = Shuf->getType();
2191 Mask = Shuf->getShuffleMask();
2192 } else {
2193 return false;
2194 }
2195
2196 // When the data type is <1 x Type>, it's not possible to differentiate
2197 // between the ComplexDeinterleaving::Deinterleave and
2198 // ComplexDeinterleaving::Splat operations.
2199 if (!VTy->isScalableTy() && VTy->getElementCount().getKnownMinValue() == 1)
2200 return false;
2201
2202 return all_equal(Range&: Mask) && Mask[0] == 0;
2203 };
2204
2205 // The splats must meet the following requirements:
2206 // 1. Must either be all instructions or all values.
2207 // 2. Non-constant splats must live in the same block.
2208 if (auto *FirstValAsInstruction = dyn_cast<Instruction>(Val: Vals[0].Real)) {
2209 BasicBlock *FirstBB = FirstValAsInstruction->getParent();
2210 for (auto &V : Vals) {
2211 if (!IsSplat(V.Real) || !IsSplat(V.Imag))
2212 return nullptr;
2213
2214 auto *Real = dyn_cast<Instruction>(Val: V.Real);
2215 auto *Imag = dyn_cast<Instruction>(Val: V.Imag);
2216 if (!Real || !Imag || Real->getParent() != FirstBB ||
2217 Imag->getParent() != FirstBB)
2218 return nullptr;
2219 }
2220 } else {
2221 for (auto &V : Vals) {
2222 if (!IsSplat(V.Real) || !IsSplat(V.Imag) || isa<Instruction>(Val: V.Real) ||
2223 isa<Instruction>(Val: V.Imag))
2224 return nullptr;
2225 }
2226 }
2227
2228 for (auto &V : Vals) {
2229 auto *Real = dyn_cast<Instruction>(Val: V.Real);
2230 auto *Imag = dyn_cast<Instruction>(Val: V.Imag);
2231 if (Real && Imag) {
2232 FinalInstructions.insert(Ptr: Real);
2233 FinalInstructions.insert(Ptr: Imag);
2234 }
2235 }
2236 CompositeNode *PlaceholderNode =
2237 prepareCompositeNode(Operation: ComplexDeinterleavingOperation::Splat, Vals);
2238 return submitCompositeNode(Node: PlaceholderNode);
2239}
2240
2241ComplexDeinterleavingGraph::CompositeNode *
2242ComplexDeinterleavingGraph::identifyPHINode(Instruction *Real,
2243 Instruction *Imag) {
2244 if (Real != RealPHI || (ImagPHI && Imag != ImagPHI))
2245 return nullptr;
2246
2247 PHIsFound = true;
2248 CompositeNode *PlaceholderNode = prepareCompositeNode(
2249 Operation: ComplexDeinterleavingOperation::ReductionPHI, R: Real, I: Imag);
2250 return submitCompositeNode(Node: PlaceholderNode);
2251}
2252
2253ComplexDeinterleavingGraph::CompositeNode *
2254ComplexDeinterleavingGraph::identifySelectNode(Instruction *Real,
2255 Instruction *Imag) {
2256 auto *SelectReal = dyn_cast<SelectInst>(Val: Real);
2257 auto *SelectImag = dyn_cast<SelectInst>(Val: Imag);
2258 if (!SelectReal || !SelectImag)
2259 return nullptr;
2260
2261 Instruction *MaskA, *MaskB;
2262 Instruction *AR, *AI, *RA, *BI;
2263 if (!match(V: Real, P: m_Select(C: m_Instruction(I&: MaskA), L: m_Instruction(I&: AR),
2264 R: m_Instruction(I&: RA))) ||
2265 !match(V: Imag, P: m_Select(C: m_Instruction(I&: MaskB), L: m_Instruction(I&: AI),
2266 R: m_Instruction(I&: BI))))
2267 return nullptr;
2268
2269 if (MaskA != MaskB && !MaskA->isIdenticalTo(I: MaskB))
2270 return nullptr;
2271
2272 if (!MaskA->getType()->isVectorTy())
2273 return nullptr;
2274
2275 auto NodeA = identifyNode(R: AR, I: AI);
2276 if (!NodeA)
2277 return nullptr;
2278
2279 auto NodeB = identifyNode(R: RA, I: BI);
2280 if (!NodeB)
2281 return nullptr;
2282
2283 CompositeNode *PlaceholderNode = prepareCompositeNode(
2284 Operation: ComplexDeinterleavingOperation::ReductionSelect, R: Real, I: Imag);
2285 PlaceholderNode->addOperand(Node: NodeA);
2286 PlaceholderNode->addOperand(Node: NodeB);
2287 FinalInstructions.insert(Ptr: MaskA);
2288 FinalInstructions.insert(Ptr: MaskB);
2289 return submitCompositeNode(Node: PlaceholderNode);
2290}
2291
2292static Value *replaceSymmetricNode(IRBuilderBase &B, unsigned Opcode,
2293 std::optional<FastMathFlags> Flags,
2294 Value *InputA, Value *InputB) {
2295 Value *I;
2296 switch (Opcode) {
2297 case Instruction::FNeg:
2298 I = B.CreateFNeg(V: InputA);
2299 break;
2300 case Instruction::FAdd:
2301 I = B.CreateFAdd(L: InputA, R: InputB);
2302 break;
2303 case Instruction::Add:
2304 I = B.CreateAdd(LHS: InputA, RHS: InputB);
2305 break;
2306 case Instruction::FSub:
2307 I = B.CreateFSub(L: InputA, R: InputB);
2308 break;
2309 case Instruction::Sub:
2310 I = B.CreateSub(LHS: InputA, RHS: InputB);
2311 break;
2312 case Instruction::FMul:
2313 I = B.CreateFMul(L: InputA, R: InputB);
2314 break;
2315 case Instruction::Mul:
2316 I = B.CreateMul(LHS: InputA, RHS: InputB);
2317 break;
2318 default:
2319 llvm_unreachable("Incorrect symmetric opcode");
2320 }
2321 if (Flags)
2322 cast<Instruction>(Val: I)->setFastMathFlags(*Flags);
2323 return I;
2324}
2325
2326Value *ComplexDeinterleavingGraph::replaceNode(IRBuilderBase &Builder,
2327 CompositeNode *Node) {
2328 if (Node->ReplacementNode)
2329 return Node->ReplacementNode;
2330
2331 auto ReplaceOperandIfExist = [&](CompositeNode *Node,
2332 unsigned Idx) -> Value * {
2333 return Node->Operands.size() > Idx
2334 ? replaceNode(Builder, Node: Node->Operands[Idx])
2335 : nullptr;
2336 };
2337
2338 Value *ReplacementNode = nullptr;
2339 switch (Node->Operation) {
2340 case ComplexDeinterleavingOperation::CDot: {
2341 Value *Input0 = ReplaceOperandIfExist(Node, 0);
2342 Value *Input1 = ReplaceOperandIfExist(Node, 1);
2343 Value *Accumulator = ReplaceOperandIfExist(Node, 2);
2344 assert(!Input1 || (Input0->getType() == Input1->getType() &&
2345 "Node inputs need to be of the same type"));
2346 ReplacementNode = TL->createComplexDeinterleavingIR(
2347 B&: Builder, OperationType: Node->Operation, Rotation: Node->Rotation, InputA: Input0, InputB: Input1, Accumulator);
2348 break;
2349 }
2350 case ComplexDeinterleavingOperation::CAdd:
2351 case ComplexDeinterleavingOperation::CMulPartial:
2352 case ComplexDeinterleavingOperation::Symmetric: {
2353 Value *Input0 = ReplaceOperandIfExist(Node, 0);
2354 Value *Input1 = ReplaceOperandIfExist(Node, 1);
2355 Value *Accumulator = ReplaceOperandIfExist(Node, 2);
2356 assert(!Input1 || (Input0->getType() == Input1->getType() &&
2357 "Node inputs need to be of the same type"));
2358 assert(!Accumulator ||
2359 (Input0->getType() == Accumulator->getType() &&
2360 "Accumulator and input need to be of the same type"));
2361 if (Node->Operation == ComplexDeinterleavingOperation::Symmetric)
2362 ReplacementNode = replaceSymmetricNode(B&: Builder, Opcode: Node->Opcode, Flags: Node->Flags,
2363 InputA: Input0, InputB: Input1);
2364 else
2365 ReplacementNode = TL->createComplexDeinterleavingIR(
2366 B&: Builder, OperationType: Node->Operation, Rotation: Node->Rotation, InputA: Input0, InputB: Input1,
2367 Accumulator);
2368 break;
2369 }
2370 case ComplexDeinterleavingOperation::Deinterleave:
2371 llvm_unreachable("Deinterleave node should already have ReplacementNode");
2372 break;
2373 case ComplexDeinterleavingOperation::Splat: {
2374 SmallVector<Value *> Ops;
2375 for (auto &V : Node->Vals) {
2376 Ops.push_back(Elt: V.Real);
2377 Ops.push_back(Elt: V.Imag);
2378 }
2379 auto *R = dyn_cast<Instruction>(Val: Node->Vals[0].Real);
2380 auto *I = dyn_cast<Instruction>(Val: Node->Vals[0].Imag);
2381 if (R && I) {
2382 // Splats that are not constant are interleaved where they are located
2383 Instruction *InsertPoint = R;
2384 for (auto V : Node->Vals) {
2385 if (InsertPoint->comesBefore(Other: cast<Instruction>(Val: V.Real)))
2386 InsertPoint = cast<Instruction>(Val: V.Real);
2387 if (InsertPoint->comesBefore(Other: cast<Instruction>(Val: V.Imag)))
2388 InsertPoint = cast<Instruction>(Val: V.Imag);
2389 }
2390 InsertPoint = InsertPoint->getNextNode();
2391 IRBuilder<> IRB(InsertPoint);
2392 ReplacementNode = IRB.CreateVectorInterleave(Ops);
2393 } else {
2394 ReplacementNode = Builder.CreateVectorInterleave(Ops);
2395 }
2396 break;
2397 }
2398 case ComplexDeinterleavingOperation::ReductionPHI: {
2399 // If Operation is ReductionPHI, a new empty PHINode is created.
2400 // It is filled later when the ReductionOperation is processed.
2401 auto *OldPHI = cast<PHINode>(Val: Node->Vals[0].Real);
2402 auto *VTy = cast<VectorType>(Val: Node->Vals[0].Real->getType());
2403 auto *NewVTy = VectorType::getDoubleElementsVectorType(VTy);
2404 auto *NewPHI = PHINode::Create(Ty: NewVTy, NumReservedValues: 0, NameStr: "", InsertBefore: BackEdge->getFirstNonPHIIt());
2405 OldToNewPHI[OldPHI] = NewPHI;
2406 ReplacementNode = NewPHI;
2407 break;
2408 }
2409 case ComplexDeinterleavingOperation::ReductionSingle:
2410 ReplacementNode = replaceNode(Builder, Node: Node->Operands[0]);
2411 processReductionSingle(OperationReplacement: ReplacementNode, Node);
2412 break;
2413 case ComplexDeinterleavingOperation::ReductionOperation:
2414 ReplacementNode = replaceNode(Builder, Node: Node->Operands[0]);
2415 processReductionOperation(OperationReplacement: ReplacementNode, Node);
2416 break;
2417 case ComplexDeinterleavingOperation::ReductionSelect: {
2418 auto *MaskReal = cast<Instruction>(Val: Node->Vals[0].Real)->getOperand(i: 0);
2419 auto *MaskImag = cast<Instruction>(Val: Node->Vals[0].Imag)->getOperand(i: 0);
2420 auto *A = replaceNode(Builder, Node: Node->Operands[0]);
2421 auto *B = replaceNode(Builder, Node: Node->Operands[1]);
2422 auto *NewMask = Builder.CreateVectorInterleave(Ops: {MaskReal, MaskImag});
2423 ReplacementNode = Builder.CreateSelect(C: NewMask, True: A, False: B);
2424 break;
2425 }
2426 }
2427
2428 assert(ReplacementNode && "Target failed to create Intrinsic call.");
2429 NumComplexTransformations += 1;
2430 Node->ReplacementNode = ReplacementNode;
2431 return ReplacementNode;
2432}
2433
2434void ComplexDeinterleavingGraph::processReductionSingle(
2435 Value *OperationReplacement, CompositeNode *Node) {
2436 auto *Real = cast<Instruction>(Val: Node->Vals[0].Real);
2437 auto *OldPHI = ReductionInfo[Real].first;
2438 auto *NewPHI = OldToNewPHI[OldPHI];
2439 auto *VTy = cast<VectorType>(Val: Real->getType());
2440 auto *NewVTy = VectorType::getDoubleElementsVectorType(VTy);
2441
2442 Value *Init = OldPHI->getIncomingValueForBlock(BB: Incoming);
2443
2444 IRBuilder<> Builder(Incoming->getTerminator());
2445
2446 Value *NewInit = nullptr;
2447 if (auto *C = dyn_cast<Constant>(Val: Init)) {
2448 if (C->isNullValue())
2449 NewInit = Constant::getNullValue(Ty: NewVTy);
2450 }
2451
2452 if (!NewInit)
2453 NewInit =
2454 Builder.CreateVectorInterleave(Ops: {Init, Constant::getNullValue(Ty: VTy)});
2455
2456 NewPHI->addIncoming(V: NewInit, BB: Incoming);
2457 NewPHI->addIncoming(V: OperationReplacement, BB: BackEdge);
2458
2459 auto *FinalReduction = ReductionInfo[Real].second;
2460 Builder.SetInsertPoint(&*FinalReduction->getParent()->getFirstInsertionPt());
2461
2462 auto *AddReduce = Builder.CreateAddReduce(Src: OperationReplacement);
2463 FinalReduction->replaceAllUsesWith(V: AddReduce);
2464}
2465
2466void ComplexDeinterleavingGraph::processReductionOperation(
2467 Value *OperationReplacement, CompositeNode *Node) {
2468 auto *Real = cast<Instruction>(Val: Node->Vals[0].Real);
2469 auto *Imag = cast<Instruction>(Val: Node->Vals[0].Imag);
2470 auto *OldPHIReal = ReductionInfo[Real].first;
2471 auto *OldPHIImag = ReductionInfo[Imag].first;
2472 auto *NewPHI = OldToNewPHI[OldPHIReal];
2473
2474 // We have to interleave initial origin values coming from IncomingBlock
2475 Value *InitReal = OldPHIReal->getIncomingValueForBlock(BB: Incoming);
2476 Value *InitImag = OldPHIImag->getIncomingValueForBlock(BB: Incoming);
2477
2478 IRBuilder<> Builder(Incoming->getTerminator());
2479 auto *NewInit = Builder.CreateVectorInterleave(Ops: {InitReal, InitImag});
2480
2481 NewPHI->addIncoming(V: NewInit, BB: Incoming);
2482 NewPHI->addIncoming(V: OperationReplacement, BB: BackEdge);
2483
2484 // Deinterleave complex vector outside of loop so that it can be finally
2485 // reduced
2486 auto *FinalReductionReal = ReductionInfo[Real].second;
2487 auto *FinalReductionImag = ReductionInfo[Imag].second;
2488
2489 auto *Br = cast<CondBrInst>(Val: BackEdge->getTerminator());
2490 BasicBlock *ExitBB = Br->getSuccessor(i: Br->getSuccessor(i: 0) == BackEdge);
2491 Builder.SetInsertPoint(&*ExitBB->getFirstInsertionPt());
2492
2493 auto *Deinterleave = Builder.CreateIntrinsic(ID: Intrinsic::vector_deinterleave2,
2494 OverloadTypes: OperationReplacement->getType(),
2495 Args: OperationReplacement);
2496
2497 auto *NewReal = Builder.CreateExtractValue(Agg: Deinterleave, Idxs: (uint64_t)0);
2498 FinalReductionReal->replaceUsesOfWith(From: Real, To: NewReal);
2499
2500 Builder.SetInsertPoint(FinalReductionImag);
2501 auto *NewImag = Builder.CreateExtractValue(Agg: Deinterleave, Idxs: 1);
2502 FinalReductionImag->replaceUsesOfWith(From: Imag, To: NewImag);
2503}
2504
2505void ComplexDeinterleavingGraph::replaceNodes() {
2506 SmallVector<Instruction *, 16> DeadInstrRoots;
2507 for (auto *RootInstruction : OrderedRoots) {
2508 // Check if this potential root went through check process and we can
2509 // deinterleave it
2510 if (!RootToNode.count(Val: RootInstruction))
2511 continue;
2512
2513 IRBuilder<> Builder(RootInstruction);
2514 auto RootNode = RootToNode[RootInstruction];
2515 Value *R = replaceNode(Builder, Node: RootNode);
2516
2517 if (RootNode->Operation ==
2518 ComplexDeinterleavingOperation::ReductionOperation) {
2519 auto *RootReal = cast<Instruction>(Val: RootNode->Vals[0].Real);
2520 auto *RootImag = cast<Instruction>(Val: RootNode->Vals[0].Imag);
2521 ReductionInfo[RootReal].first->removeIncomingValue(BB: BackEdge);
2522 ReductionInfo[RootImag].first->removeIncomingValue(BB: BackEdge);
2523 DeadInstrRoots.push_back(Elt: RootReal);
2524 DeadInstrRoots.push_back(Elt: RootImag);
2525 } else if (RootNode->Operation ==
2526 ComplexDeinterleavingOperation::ReductionSingle) {
2527 auto *RootInst = cast<Instruction>(Val: RootNode->Vals[0].Real);
2528 auto &Info = ReductionInfo[RootInst];
2529 Info.first->removeIncomingValue(BB: BackEdge);
2530 DeadInstrRoots.push_back(Elt: Info.second);
2531 } else {
2532 assert(R && "Unable to find replacement for RootInstruction");
2533 DeadInstrRoots.push_back(Elt: RootInstruction);
2534 RootInstruction->replaceAllUsesWith(V: R);
2535 }
2536 }
2537
2538 for (auto *I : DeadInstrRoots)
2539 RecursivelyDeleteTriviallyDeadInstructions(V: I, TLI);
2540}
2541