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 // TODO: Confirm whether m_FNegOrFSubNegZero is correct.
603 return match(V, P: m_FNegOrFSubNegZero(X: m_Value())) || match(V, P: m_Neg(V: m_Value()));
604}
605
606Value *getNegOperand(Value *V) {
607 assert(isNeg(V));
608 auto *I = cast<Instruction>(Val: V);
609 if (I->getOpcode() == Instruction::FNeg)
610 return I->getOperand(i: 0);
611
612 return I->getOperand(i: 1);
613}
614
615bool ComplexDeinterleaving::evaluateBasicBlock(BasicBlock *B, unsigned Factor) {
616 ComplexDeinterleavingGraph Graph(TL, TLI, Factor);
617 if (Graph.collectPotentialReductions(B))
618 Graph.identifyReductionNodes();
619
620 for (auto &I : *B)
621 Graph.identifyNodes(RootI: &I);
622
623 if (Graph.checkNodes()) {
624 Graph.replaceNodes();
625 return true;
626 }
627
628 return false;
629}
630
631ComplexDeinterleavingGraph::CompositeNode *
632ComplexDeinterleavingGraph::identifyNodeWithImplicitAdd(
633 Instruction *Real, Instruction *Imag,
634 std::pair<Value *, Value *> &PartialMatch) {
635 LLVM_DEBUG(dbgs() << "identifyNodeWithImplicitAdd " << *Real << " / " << *Imag
636 << "\n");
637
638 if (!Real->hasOneUse() || !Imag->hasOneUse()) {
639 LLVM_DEBUG(dbgs() << " - Mul operand has multiple uses.\n");
640 return nullptr;
641 }
642
643 if ((Real->getOpcode() != Instruction::FMul &&
644 Real->getOpcode() != Instruction::Mul) ||
645 (Imag->getOpcode() != Instruction::FMul &&
646 Imag->getOpcode() != Instruction::Mul)) {
647 LLVM_DEBUG(
648 dbgs() << " - Real or imaginary instruction is not fmul or mul\n");
649 return nullptr;
650 }
651
652 Value *R0 = Real->getOperand(i: 0);
653 Value *R1 = Real->getOperand(i: 1);
654 Value *I0 = Imag->getOperand(i: 0);
655 Value *I1 = Imag->getOperand(i: 1);
656
657 // A +/+ has a rotation of 0. If any of the operands are fneg, we flip the
658 // rotations and use the operand.
659 unsigned Negs = 0;
660 if (isNeg(V: R0)) {
661 Negs |= 1;
662 R0 = getNegOperand(V: R0);
663 } else if (isNeg(V: R1)) {
664 Negs |= 1;
665 R1 = getNegOperand(V: R1);
666 }
667
668 if (isNeg(V: I0)) {
669 Negs |= 2;
670 Negs ^= 1;
671 I0 = getNegOperand(V: I0);
672 } else if (isNeg(V: I1)) {
673 Negs |= 2;
674 Negs ^= 1;
675 I1 = getNegOperand(V: I1);
676 }
677
678 ComplexDeinterleavingRotation Rotation = (ComplexDeinterleavingRotation)Negs;
679
680 Value *CommonOperand;
681 Value *UncommonRealOp;
682 Value *UncommonImagOp;
683
684 if (R0 == I0 || R0 == I1) {
685 CommonOperand = R0;
686 UncommonRealOp = R1;
687 } else if (R1 == I0 || R1 == I1) {
688 CommonOperand = R1;
689 UncommonRealOp = R0;
690 } else {
691 LLVM_DEBUG(dbgs() << " - No equal operand\n");
692 return nullptr;
693 }
694
695 UncommonImagOp = (CommonOperand == I0) ? I1 : I0;
696 if (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||
697 Rotation == ComplexDeinterleavingRotation::Rotation_270)
698 std::swap(a&: UncommonRealOp, b&: UncommonImagOp);
699
700 // Between identifyPartialMul and here we need to have found a complete valid
701 // pair from the CommonOperand of each part.
702 if (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||
703 Rotation == ComplexDeinterleavingRotation::Rotation_180)
704 PartialMatch.first = CommonOperand;
705 else
706 PartialMatch.second = CommonOperand;
707
708 if (!PartialMatch.first || !PartialMatch.second) {
709 LLVM_DEBUG(dbgs() << " - Incomplete partial match\n");
710 return nullptr;
711 }
712
713 CompositeNode *CommonNode =
714 identifyNode(R: PartialMatch.first, I: PartialMatch.second);
715 if (!CommonNode) {
716 LLVM_DEBUG(dbgs() << " - No CommonNode identified\n");
717 return nullptr;
718 }
719
720 CompositeNode *UncommonNode = identifyNode(R: UncommonRealOp, I: UncommonImagOp);
721 if (!UncommonNode) {
722 LLVM_DEBUG(dbgs() << " - No UncommonNode identified\n");
723 return nullptr;
724 }
725
726 CompositeNode *Node = prepareCompositeNode(
727 Operation: ComplexDeinterleavingOperation::CMulPartial, R: Real, I: Imag);
728 Node->Rotation = Rotation;
729 Node->addOperand(Node: CommonNode);
730 Node->addOperand(Node: UncommonNode);
731 return submitCompositeNode(Node);
732}
733
734ComplexDeinterleavingGraph::CompositeNode *
735ComplexDeinterleavingGraph::identifyPartialMul(Instruction *Real,
736 Instruction *Imag) {
737 LLVM_DEBUG(dbgs() << "identifyPartialMul " << *Real << " / " << *Imag
738 << "\n");
739
740 // Determine rotation
741 auto IsAdd = [](unsigned Op) {
742 return Op == Instruction::FAdd || Op == Instruction::Add;
743 };
744 auto IsSub = [](unsigned Op) {
745 return Op == Instruction::FSub || Op == Instruction::Sub;
746 };
747 ComplexDeinterleavingRotation Rotation;
748 if (IsAdd(Real->getOpcode()) && IsAdd(Imag->getOpcode()))
749 Rotation = ComplexDeinterleavingRotation::Rotation_0;
750 else if (IsSub(Real->getOpcode()) && IsAdd(Imag->getOpcode()))
751 Rotation = ComplexDeinterleavingRotation::Rotation_90;
752 else if (IsSub(Real->getOpcode()) && IsSub(Imag->getOpcode()))
753 Rotation = ComplexDeinterleavingRotation::Rotation_180;
754 else if (IsAdd(Real->getOpcode()) && IsSub(Imag->getOpcode()))
755 Rotation = ComplexDeinterleavingRotation::Rotation_270;
756 else {
757 LLVM_DEBUG(dbgs() << " - Unhandled rotation.\n");
758 return nullptr;
759 }
760
761 if (isa<FPMathOperator>(Val: Real) &&
762 (!Real->getFastMathFlags().allowContract() ||
763 !Imag->getFastMathFlags().allowContract())) {
764 LLVM_DEBUG(dbgs() << " - Contract is missing from the FastMath flags.\n");
765 return nullptr;
766 }
767
768 Value *CR = Real->getOperand(i: 0);
769 Instruction *RealMulI = dyn_cast<Instruction>(Val: Real->getOperand(i: 1));
770 if (!RealMulI)
771 return nullptr;
772 Value *CI = Imag->getOperand(i: 0);
773 Instruction *ImagMulI = dyn_cast<Instruction>(Val: Imag->getOperand(i: 1));
774 if (!ImagMulI)
775 return nullptr;
776
777 if (!RealMulI->hasOneUse() || !ImagMulI->hasOneUse()) {
778 LLVM_DEBUG(dbgs() << " - Mul instruction has multiple uses\n");
779 return nullptr;
780 }
781
782 Value *R0 = RealMulI->getOperand(i: 0);
783 Value *R1 = RealMulI->getOperand(i: 1);
784 Value *I0 = ImagMulI->getOperand(i: 0);
785 Value *I1 = ImagMulI->getOperand(i: 1);
786
787 Value *CommonOperand;
788 Value *UncommonRealOp;
789 Value *UncommonImagOp;
790
791 if (R0 == I0 || R0 == I1) {
792 CommonOperand = R0;
793 UncommonRealOp = R1;
794 } else if (R1 == I0 || R1 == I1) {
795 CommonOperand = R1;
796 UncommonRealOp = R0;
797 } else {
798 LLVM_DEBUG(dbgs() << " - No equal operand\n");
799 return nullptr;
800 }
801
802 UncommonImagOp = (CommonOperand == I0) ? I1 : I0;
803 if (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||
804 Rotation == ComplexDeinterleavingRotation::Rotation_270)
805 std::swap(a&: UncommonRealOp, b&: UncommonImagOp);
806
807 std::pair<Value *, Value *> PartialMatch(
808 (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||
809 Rotation == ComplexDeinterleavingRotation::Rotation_180)
810 ? CommonOperand
811 : nullptr,
812 (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||
813 Rotation == ComplexDeinterleavingRotation::Rotation_270)
814 ? CommonOperand
815 : nullptr);
816
817 auto *CRInst = dyn_cast<Instruction>(Val: CR);
818 auto *CIInst = dyn_cast<Instruction>(Val: CI);
819
820 if (!CRInst || !CIInst) {
821 LLVM_DEBUG(dbgs() << " - Common operands are not instructions.\n");
822 return nullptr;
823 }
824
825 CompositeNode *CNode =
826 identifyNodeWithImplicitAdd(Real: CRInst, Imag: CIInst, PartialMatch);
827 if (!CNode) {
828 LLVM_DEBUG(dbgs() << " - No cnode identified\n");
829 return nullptr;
830 }
831
832 CompositeNode *UncommonRes = identifyNode(R: UncommonRealOp, I: UncommonImagOp);
833 if (!UncommonRes) {
834 LLVM_DEBUG(dbgs() << " - No UncommonRes identified\n");
835 return nullptr;
836 }
837
838 assert(PartialMatch.first && PartialMatch.second);
839 CompositeNode *CommonRes =
840 identifyNode(R: PartialMatch.first, I: PartialMatch.second);
841 if (!CommonRes) {
842 LLVM_DEBUG(dbgs() << " - No CommonRes identified\n");
843 return nullptr;
844 }
845
846 CompositeNode *Node = prepareCompositeNode(
847 Operation: ComplexDeinterleavingOperation::CMulPartial, R: Real, I: Imag);
848 Node->Rotation = Rotation;
849 Node->addOperand(Node: CommonRes);
850 Node->addOperand(Node: UncommonRes);
851 Node->addOperand(Node: CNode);
852 return submitCompositeNode(Node);
853}
854
855ComplexDeinterleavingGraph::CompositeNode *
856ComplexDeinterleavingGraph::identifyAdd(Instruction *Real, Instruction *Imag) {
857 LLVM_DEBUG(dbgs() << "identifyAdd " << *Real << " / " << *Imag << "\n");
858
859 // Determine rotation
860 ComplexDeinterleavingRotation Rotation;
861 if ((Real->getOpcode() == Instruction::FSub &&
862 Imag->getOpcode() == Instruction::FAdd) ||
863 (Real->getOpcode() == Instruction::Sub &&
864 Imag->getOpcode() == Instruction::Add))
865 Rotation = ComplexDeinterleavingRotation::Rotation_90;
866 else if ((Real->getOpcode() == Instruction::FAdd &&
867 Imag->getOpcode() == Instruction::FSub) ||
868 (Real->getOpcode() == Instruction::Add &&
869 Imag->getOpcode() == Instruction::Sub))
870 Rotation = ComplexDeinterleavingRotation::Rotation_270;
871 else {
872 LLVM_DEBUG(dbgs() << " - Unhandled case, rotation is not assigned.\n");
873 return nullptr;
874 }
875
876 auto *AR = dyn_cast<Instruction>(Val: Real->getOperand(i: 0));
877 auto *BI = dyn_cast<Instruction>(Val: Real->getOperand(i: 1));
878 auto *AI = dyn_cast<Instruction>(Val: Imag->getOperand(i: 0));
879 auto *BR = dyn_cast<Instruction>(Val: Imag->getOperand(i: 1));
880
881 if (!AR || !AI || !BR || !BI) {
882 LLVM_DEBUG(dbgs() << " - Not all operands are instructions.\n");
883 return nullptr;
884 }
885
886 CompositeNode *ResA = identifyNode(R: AR, I: AI);
887 if (!ResA) {
888 LLVM_DEBUG(dbgs() << " - AR/AI is not identified as a composite node.\n");
889 return nullptr;
890 }
891 CompositeNode *ResB = identifyNode(R: BR, I: BI);
892 if (!ResB) {
893 LLVM_DEBUG(dbgs() << " - BR/BI is not identified as a composite node.\n");
894 return nullptr;
895 }
896
897 CompositeNode *Node =
898 prepareCompositeNode(Operation: ComplexDeinterleavingOperation::CAdd, R: Real, I: Imag);
899 Node->Rotation = Rotation;
900 Node->addOperand(Node: ResA);
901 Node->addOperand(Node: ResB);
902 return submitCompositeNode(Node);
903}
904
905static bool isInstructionPairAdd(Instruction *A, Instruction *B) {
906 unsigned OpcA = A->getOpcode();
907 unsigned OpcB = B->getOpcode();
908
909 return (OpcA == Instruction::FSub && OpcB == Instruction::FAdd) ||
910 (OpcA == Instruction::FAdd && OpcB == Instruction::FSub) ||
911 (OpcA == Instruction::Sub && OpcB == Instruction::Add) ||
912 (OpcA == Instruction::Add && OpcB == Instruction::Sub);
913}
914
915static bool isInstructionPairMul(Instruction *A, Instruction *B) {
916 auto Pattern =
917 m_BinOp(L: m_FMul(L: m_Value(), R: m_Value()), R: m_FMul(L: m_Value(), R: m_Value()));
918
919 return match(V: A, P: Pattern) && match(V: B, P: Pattern);
920}
921
922static bool isInstructionPotentiallySymmetric(Instruction *I) {
923 switch (I->getOpcode()) {
924 case Instruction::FAdd:
925 case Instruction::FSub:
926 case Instruction::FMul:
927 case Instruction::FNeg:
928 case Instruction::Add:
929 case Instruction::Sub:
930 case Instruction::Mul:
931 return true;
932 default:
933 return false;
934 }
935}
936
937ComplexDeinterleavingGraph::CompositeNode *
938ComplexDeinterleavingGraph::identifySymmetricOperation(ComplexValues &Vals) {
939 auto *FirstReal = cast<Instruction>(Val: Vals[0].Real);
940 unsigned FirstOpc = FirstReal->getOpcode();
941 FastMathFlags CommonFlags;
942 if (isa<FPMathOperator>(Val: FirstReal))
943 CommonFlags = FirstReal->getFastMathFlags();
944 for (auto &V : Vals) {
945 auto *Real = cast<Instruction>(Val: V.Real);
946 auto *Imag = cast<Instruction>(Val: V.Imag);
947 if (Real->getOpcode() != FirstOpc || Imag->getOpcode() != FirstOpc)
948 return nullptr;
949
950 if (!isInstructionPotentiallySymmetric(I: Real) ||
951 !isInstructionPotentiallySymmetric(I: Imag))
952 return nullptr;
953
954 if (isa<FPMathOperator>(Val: FirstReal)) {
955 CommonFlags &= Real->getFastMathFlags();
956 CommonFlags &= Imag->getFastMathFlags();
957 }
958 }
959
960 ComplexValues OpVals;
961 for (auto &V : Vals) {
962 auto *R0 = cast<Instruction>(Val: V.Real)->getOperand(i: 0);
963 auto *I0 = cast<Instruction>(Val: V.Imag)->getOperand(i: 0);
964 OpVals.push_back(Elt: {.Real: R0, .Imag: I0});
965 }
966
967 CompositeNode *Op0 = identifyNode(Vals&: OpVals);
968 CompositeNode *Op1 = nullptr;
969 if (Op0 == nullptr)
970 return nullptr;
971
972 if (FirstReal->isBinaryOp()) {
973 OpVals.clear();
974 for (auto &V : Vals) {
975 auto *R1 = cast<Instruction>(Val: V.Real)->getOperand(i: 1);
976 auto *I1 = cast<Instruction>(Val: V.Imag)->getOperand(i: 1);
977 OpVals.push_back(Elt: {.Real: R1, .Imag: I1});
978 }
979 Op1 = identifyNode(Vals&: OpVals);
980 if (Op1 == nullptr)
981 return nullptr;
982 }
983
984 auto Node =
985 prepareCompositeNode(Operation: ComplexDeinterleavingOperation::Symmetric, Vals);
986 Node->Opcode = FirstReal->getOpcode();
987 if (isa<FPMathOperator>(Val: FirstReal))
988 Node->Flags = CommonFlags;
989
990 Node->addOperand(Node: Op0);
991 if (FirstReal->isBinaryOp())
992 Node->addOperand(Node: Op1);
993
994 return submitCompositeNode(Node);
995}
996
997ComplexDeinterleavingGraph::CompositeNode *
998ComplexDeinterleavingGraph::identifyDotProduct(Value *V) {
999 if (!TL->isComplexDeinterleavingOperationSupported(
1000 Operation: ComplexDeinterleavingOperation::CDot, Ty: V->getType())) {
1001 LLVM_DEBUG(dbgs() << "Target doesn't support complex deinterleaving "
1002 "operation CDot with the type "
1003 << *V->getType() << "\n");
1004 return nullptr;
1005 }
1006
1007 auto *Inst = cast<Instruction>(Val: V);
1008 auto *RealUser = cast<Instruction>(Val: *Inst->user_begin());
1009
1010 CompositeNode *CN =
1011 prepareCompositeNode(Operation: ComplexDeinterleavingOperation::CDot, R: Inst, I: nullptr);
1012
1013 CompositeNode *ANode = nullptr;
1014
1015 const Intrinsic::ID PartialReduceInt = Intrinsic::vector_partial_reduce_add;
1016
1017 Value *AReal = nullptr;
1018 Value *AImag = nullptr;
1019 Value *BReal = nullptr;
1020 Value *BImag = nullptr;
1021 Value *Phi = nullptr;
1022
1023 auto UnwrapCast = [](Value *V) -> Value * {
1024 if (auto *CI = dyn_cast<CastInst>(Val: V))
1025 return CI->getOperand(i_nocapture: 0);
1026 return V;
1027 };
1028
1029 auto PatternRot0 = m_Intrinsic<PartialReduceInt>(
1030 Ops: m_Intrinsic<PartialReduceInt>(Ops: m_Value(V&: Phi),
1031 Ops: m_Mul(L: m_Value(V&: BReal), R: m_Value(V&: AReal))),
1032 Ops: m_Neg(V: m_Mul(L: m_Value(V&: BImag), R: m_Value(V&: AImag))));
1033
1034 auto PatternRot270 = m_Intrinsic<PartialReduceInt>(
1035 Ops: m_Intrinsic<PartialReduceInt>(
1036 Ops: m_Value(V&: Phi), Ops: m_Neg(V: m_Mul(L: m_Value(V&: BReal), R: m_Value(V&: AImag)))),
1037 Ops: m_Mul(L: m_Value(V&: BImag), R: m_Value(V&: AReal)));
1038
1039 if (match(V: Inst, P: PatternRot0)) {
1040 CN->Rotation = ComplexDeinterleavingRotation::Rotation_0;
1041 } else if (match(V: Inst, P: PatternRot270)) {
1042 CN->Rotation = ComplexDeinterleavingRotation::Rotation_270;
1043 } else {
1044 Value *A0, *A1;
1045 // The rotations 90 and 180 share the same operation pattern, so inspect the
1046 // order of the operands, identifying where the real and imaginary
1047 // components of A go, to discern between the aforementioned rotations.
1048 auto PatternRot90Rot180 = m_Intrinsic<PartialReduceInt>(
1049 Ops: m_Intrinsic<PartialReduceInt>(Ops: m_Value(V&: Phi),
1050 Ops: m_Mul(L: m_Value(V&: BReal), R: m_Value(V&: A0))),
1051 Ops: m_Mul(L: m_Value(V&: BImag), R: m_Value(V&: A1)));
1052
1053 if (!match(V: Inst, P: PatternRot90Rot180))
1054 return nullptr;
1055
1056 A0 = UnwrapCast(A0);
1057 A1 = UnwrapCast(A1);
1058
1059 // Test if A0 is real/A1 is imag
1060 ANode = identifyNode(R: A0, I: A1);
1061 if (!ANode) {
1062 // Test if A0 is imag/A1 is real
1063 ANode = identifyNode(R: A1, I: A0);
1064 // Unable to identify operand components, thus unable to identify rotation
1065 if (!ANode)
1066 return nullptr;
1067 CN->Rotation = ComplexDeinterleavingRotation::Rotation_90;
1068 AReal = A1;
1069 AImag = A0;
1070 } else {
1071 AReal = A0;
1072 AImag = A1;
1073 CN->Rotation = ComplexDeinterleavingRotation::Rotation_180;
1074 }
1075 }
1076
1077 AReal = UnwrapCast(AReal);
1078 AImag = UnwrapCast(AImag);
1079 BReal = UnwrapCast(BReal);
1080 BImag = UnwrapCast(BImag);
1081
1082 VectorType *VTy = cast<VectorType>(Val: V->getType());
1083 Type *ExpectedOperandTy = VectorType::getSubdividedVectorType(VTy, NumSubdivs: 2);
1084 if (AReal->getType() != ExpectedOperandTy)
1085 return nullptr;
1086 if (AImag->getType() != ExpectedOperandTy)
1087 return nullptr;
1088 if (BReal->getType() != ExpectedOperandTy)
1089 return nullptr;
1090 if (BImag->getType() != ExpectedOperandTy)
1091 return nullptr;
1092
1093 if (Phi->getType() != VTy && RealUser->getType() != VTy)
1094 return nullptr;
1095
1096 CompositeNode *Node = identifyNode(R: AReal, I: AImag);
1097
1098 // In the case that a node was identified to figure out the rotation, ensure
1099 // that trying to identify a node with AReal and AImag post-unwrap results in
1100 // the same node
1101 if (ANode && Node != ANode) {
1102 LLVM_DEBUG(
1103 dbgs()
1104 << "Identified node is different from previously identified node. "
1105 "Unable to confidently generate a complex operation node\n");
1106 return nullptr;
1107 }
1108
1109 CN->addOperand(Node);
1110 CN->addOperand(Node: identifyNode(R: BReal, I: BImag));
1111 CN->addOperand(Node: identifyNode(R: Phi, I: RealUser));
1112
1113 return submitCompositeNode(Node: CN);
1114}
1115
1116ComplexDeinterleavingGraph::CompositeNode *
1117ComplexDeinterleavingGraph::identifyPartialReduction(Value *R, Value *I) {
1118 // Partial reductions don't support non-vector types, so check these first
1119 if (!isa<VectorType>(Val: R->getType()) || !isa<VectorType>(Val: I->getType()))
1120 return nullptr;
1121
1122 if (!R->hasUseList() || !I->hasUseList())
1123 return nullptr;
1124
1125 auto CommonUser =
1126 findCommonBetweenCollections<Value *>(A: R->users(), B: I->users());
1127 if (!CommonUser)
1128 return nullptr;
1129
1130 auto *IInst = dyn_cast<IntrinsicInst>(Val: *CommonUser);
1131 if (!IInst || IInst->getIntrinsicID() != Intrinsic::vector_partial_reduce_add)
1132 return nullptr;
1133
1134 if (CompositeNode *CN = identifyDotProduct(V: IInst))
1135 return CN;
1136
1137 return nullptr;
1138}
1139
1140ComplexDeinterleavingGraph::CompositeNode *
1141ComplexDeinterleavingGraph::identifyNode(ComplexValues &Vals) {
1142 auto It = CachedResult.find(Val: Vals);
1143 if (It != CachedResult.end()) {
1144 LLVM_DEBUG(dbgs() << " - Folding to existing node\n");
1145 return It->second;
1146 }
1147
1148 if (Vals.size() == 1) {
1149 assert(Factor == 2 && "Can only handle interleave factors of 2");
1150 Value *R = Vals[0].Real;
1151 Value *I = Vals[0].Imag;
1152 if (CompositeNode *CN = identifyPartialReduction(R, I))
1153 return CN;
1154 bool IsReduction = RealPHI == R && (!ImagPHI || ImagPHI == I);
1155 if (!IsReduction && R->getType() != I->getType())
1156 return nullptr;
1157 }
1158
1159 if (CompositeNode *CN = identifySplat(Vals))
1160 return CN;
1161
1162 for (auto &V : Vals) {
1163 auto *Real = dyn_cast<Instruction>(Val: V.Real);
1164 auto *Imag = dyn_cast<Instruction>(Val: V.Imag);
1165 if (!Real || !Imag)
1166 return nullptr;
1167 }
1168
1169 if (CompositeNode *CN = identifyDeinterleave(Vals))
1170 return CN;
1171
1172 if (Vals.size() == 1) {
1173 assert(Factor == 2 && "Can only handle interleave factors of 2");
1174 auto *Real = dyn_cast<Instruction>(Val: Vals[0].Real);
1175 auto *Imag = dyn_cast<Instruction>(Val: Vals[0].Imag);
1176 if (CompositeNode *CN = identifyPHINode(Real, Imag))
1177 return CN;
1178
1179 if (CompositeNode *CN = identifySelectNode(Real, Imag))
1180 return CN;
1181
1182 auto *VTy = cast<VectorType>(Val: Real->getType());
1183 auto *NewVTy = VectorType::getDoubleElementsVectorType(VTy);
1184
1185 bool HasCMulSupport = TL->isComplexDeinterleavingOperationSupported(
1186 Operation: ComplexDeinterleavingOperation::CMulPartial, Ty: NewVTy);
1187 bool HasCAddSupport = TL->isComplexDeinterleavingOperationSupported(
1188 Operation: ComplexDeinterleavingOperation::CAdd, Ty: NewVTy);
1189
1190 if (HasCMulSupport && isInstructionPairMul(A: Real, B: Imag)) {
1191 if (CompositeNode *CN = identifyPartialMul(Real, Imag))
1192 return CN;
1193 }
1194
1195 if (HasCAddSupport && isInstructionPairAdd(A: Real, B: Imag)) {
1196 if (CompositeNode *CN = identifyAdd(Real, Imag))
1197 return CN;
1198 }
1199
1200 if (HasCMulSupport && HasCAddSupport) {
1201 if (CompositeNode *CN = identifyReassocNodes(I: Real, J: Imag)) {
1202 return CN;
1203 }
1204 }
1205 }
1206
1207 if (CompositeNode *CN = identifySymmetricOperation(Vals))
1208 return CN;
1209
1210 LLVM_DEBUG(dbgs() << " - Not recognised as a valid pattern.\n");
1211 CachedResult[Vals] = nullptr;
1212 return nullptr;
1213}
1214
1215ComplexDeinterleavingGraph::CompositeNode *
1216ComplexDeinterleavingGraph::identifyReassocNodes(Instruction *Real,
1217 Instruction *Imag) {
1218 auto IsOperationSupported = [](Instruction *I) -> bool {
1219 unsigned Opcode = I->getOpcode();
1220 return match(V: I, P: m_AnyIntrinsic<Intrinsic::fma, Intrinsic::fmuladd>()) ||
1221 Opcode == Instruction::FAdd || Opcode == Instruction::FSub ||
1222 Opcode == Instruction::FNeg || Opcode == Instruction::Add ||
1223 Opcode == Instruction::Sub;
1224 };
1225
1226 if (!IsOperationSupported(Real) || !IsOperationSupported(Imag))
1227 return nullptr;
1228
1229 std::optional<FastMathFlags> Flags;
1230 if (isa<FPMathOperator>(Val: Real)) {
1231 Flags = Real->getFastMathFlags() & Imag->getFastMathFlags();
1232 if (!Flags->allowReassoc()) {
1233 LLVM_DEBUG(
1234 dbgs()
1235 << "the 'Reassoc' attribute is missing in the FastMath flags\n");
1236 return nullptr;
1237 }
1238 }
1239
1240 // Collect multiplications and addend instructions from the given instruction
1241 // while traversing it operands. Additionally, verify that all instructions
1242 // allow reassociation, and narrow \p Flags to the intersection of their
1243 // flags.
1244 auto Collect = [&Flags](Instruction *Insn, SmallVectorImpl<Product> &Muls,
1245 AddendList &Addends) -> bool {
1246 SmallVector<PointerIntPair<Value *, 1, bool>> Worklist = {{Insn, true}};
1247 while (!Worklist.empty()) {
1248 auto [V, IsPositive] = Worklist.pop_back_val();
1249
1250 Instruction *I = dyn_cast<Instruction>(Val: V);
1251 if (!I) {
1252 Addends.emplace_back(Vs&: V, Vs&: IsPositive);
1253 continue;
1254 }
1255
1256 // If an instruction has more than one user, it indicates that it either
1257 // has an external user, which will be later checked by the checkNodes
1258 // function, or it is a subexpression utilized by multiple expressions. In
1259 // the latter case, we will attempt to separately identify the complex
1260 // operation from here in order to create a shared
1261 // ComplexDeinterleavingCompositeNode.
1262 if (I != Insn && I->hasNUsesOrMore(N: 2)) {
1263 LLVM_DEBUG(dbgs() << "Found potential sub-expression: " << *I << "\n");
1264 Addends.emplace_back(Vs&: I, Vs&: IsPositive);
1265 continue;
1266 }
1267 switch (I->getOpcode()) {
1268 case Instruction::FAdd:
1269 case Instruction::Add:
1270 Worklist.emplace_back(Args: I->getOperand(i: 1), Args&: IsPositive);
1271 Worklist.emplace_back(Args: I->getOperand(i: 0), Args&: IsPositive);
1272 break;
1273 case Instruction::FSub:
1274 Worklist.emplace_back(Args: I->getOperand(i: 1), Args: !IsPositive);
1275 Worklist.emplace_back(Args: I->getOperand(i: 0), Args&: IsPositive);
1276 break;
1277 case Instruction::Sub:
1278 if (isNeg(V: I)) {
1279 Worklist.emplace_back(Args: getNegOperand(V: I), Args: !IsPositive);
1280 } else {
1281 Worklist.emplace_back(Args: I->getOperand(i: 1), Args: !IsPositive);
1282 Worklist.emplace_back(Args: I->getOperand(i: 0), Args&: IsPositive);
1283 }
1284 break;
1285 case Instruction::FMul:
1286 case Instruction::Mul: {
1287 Value *A, *B;
1288 if (isNeg(V: I->getOperand(i: 0))) {
1289 A = getNegOperand(V: I->getOperand(i: 0));
1290 IsPositive = !IsPositive;
1291 } else {
1292 A = I->getOperand(i: 0);
1293 }
1294
1295 if (isNeg(V: I->getOperand(i: 1))) {
1296 B = getNegOperand(V: I->getOperand(i: 1));
1297 IsPositive = !IsPositive;
1298 } else {
1299 B = I->getOperand(i: 1);
1300 }
1301 Muls.push_back(Elt: Product{.Multiplier: A, .Multiplicand: B, .IsPositive: IsPositive});
1302 break;
1303 }
1304 case Instruction::FNeg:
1305 Worklist.emplace_back(Args: I->getOperand(i: 0), Args: !IsPositive);
1306 break;
1307 case Instruction::Call: {
1308 Value *A, *B, *C;
1309 if (!match(V: I, P: m_Intrinsic<Intrinsic::fma>(Ops: m_Value(V&: A), Ops: m_Value(V&: B),
1310 Ops: m_Value(V&: C))) &&
1311 !match(V: I, P: m_Intrinsic<Intrinsic::fmuladd>(Ops: m_Value(V&: A), Ops: m_Value(V&: B),
1312 Ops: m_Value(V&: C)))) {
1313 Addends.emplace_back(Vs&: I, Vs&: IsPositive);
1314 continue;
1315 }
1316
1317 bool IsProductPositive = IsPositive;
1318 if (isNeg(V: A)) {
1319 A = getNegOperand(V: A);
1320 IsProductPositive = !IsProductPositive;
1321 }
1322
1323 if (isNeg(V: B)) {
1324 B = getNegOperand(V: B);
1325 IsProductPositive = !IsProductPositive;
1326 }
1327
1328 Muls.push_back(Elt: Product{.Multiplier: A, .Multiplicand: B, .IsPositive: IsProductPositive});
1329 Worklist.emplace_back(Args&: C, Args&: IsPositive);
1330 break;
1331 }
1332 default:
1333 Addends.emplace_back(Vs&: I, Vs&: IsPositive);
1334 continue;
1335 }
1336
1337 if (Flags) {
1338 if (!I->getFastMathFlags().allowReassoc()) {
1339 LLVM_DEBUG(dbgs() << "The instruction does not allow reassociation: "
1340 << *I << "\n");
1341 return false;
1342 }
1343 *Flags &= I->getFastMathFlags();
1344 }
1345 }
1346 return true;
1347 };
1348
1349 SmallVector<Product> RealMuls, ImagMuls;
1350 AddendList RealAddends, ImagAddends;
1351 if (!Collect(Real, RealMuls, RealAddends) ||
1352 !Collect(Imag, ImagMuls, ImagAddends))
1353 return nullptr;
1354
1355 if (RealAddends.size() != ImagAddends.size())
1356 return nullptr;
1357
1358 CompositeNode *FinalNode = nullptr;
1359 if (!RealMuls.empty() || !ImagMuls.empty()) {
1360 // If there are multiplicands, extract positive addend and use it as an
1361 // accumulator
1362 FinalNode = extractPositiveAddend(RealAddends, ImagAddends);
1363 FinalNode = identifyMultiplications(RealMuls, ImagMuls, Accumulator: FinalNode);
1364 if (!FinalNode)
1365 return nullptr;
1366 }
1367
1368 // Identify and process remaining additions
1369 if (!RealAddends.empty() || !ImagAddends.empty()) {
1370 FinalNode = identifyAdditions(RealAddends, ImagAddends, Flags, Accumulator: FinalNode);
1371 if (!FinalNode)
1372 return nullptr;
1373 }
1374 assert(FinalNode && "FinalNode can not be nullptr here");
1375 assert(FinalNode->Vals.size() == 1);
1376 // Set the Real and Imag fields of the final node and submit it
1377 FinalNode->Vals[0].Real = Real;
1378 FinalNode->Vals[0].Imag = Imag;
1379 submitCompositeNode(Node: FinalNode);
1380 return FinalNode;
1381}
1382
1383bool ComplexDeinterleavingGraph::collectPartialMuls(
1384 ArrayRef<Product> RealMuls, ArrayRef<Product> ImagMuls,
1385 SmallVectorImpl<PartialMulCandidate> &PartialMulCandidates) {
1386 // Helper function to extract a common operand from two products
1387 auto FindCommonInstruction = [](const Product &Real,
1388 const Product &Imag) -> Value * {
1389 if (Real.Multiplicand == Imag.Multiplicand ||
1390 Real.Multiplicand == Imag.Multiplier)
1391 return Real.Multiplicand;
1392
1393 if (Real.Multiplier == Imag.Multiplicand ||
1394 Real.Multiplier == Imag.Multiplier)
1395 return Real.Multiplier;
1396
1397 return nullptr;
1398 };
1399
1400 // Iterating over real and imaginary multiplications to find common operands
1401 // If a common operand is found, a partial multiplication candidate is created
1402 // and added to the candidates vector The function returns false if no common
1403 // operands are found for any product
1404 for (unsigned i = 0; i < RealMuls.size(); ++i) {
1405 bool FoundCommon = false;
1406 for (unsigned j = 0; j < ImagMuls.size(); ++j) {
1407 auto *Common = FindCommonInstruction(RealMuls[i], ImagMuls[j]);
1408 if (!Common)
1409 continue;
1410
1411 auto *A = RealMuls[i].Multiplicand == Common ? RealMuls[i].Multiplier
1412 : RealMuls[i].Multiplicand;
1413 auto *B = ImagMuls[j].Multiplicand == Common ? ImagMuls[j].Multiplier
1414 : ImagMuls[j].Multiplicand;
1415
1416 auto Node = identifyNode(R: A, I: B);
1417 if (Node) {
1418 FoundCommon = true;
1419 PartialMulCandidates.push_back(Elt: {.Common: Common, .Node: Node, .RealIdx: i, .ImagIdx: j, .IsNodeInverted: false});
1420 }
1421
1422 Node = identifyNode(R: B, I: A);
1423 if (Node) {
1424 FoundCommon = true;
1425 PartialMulCandidates.push_back(Elt: {.Common: Common, .Node: Node, .RealIdx: i, .ImagIdx: j, .IsNodeInverted: true});
1426 }
1427 }
1428 if (!FoundCommon)
1429 return false;
1430 }
1431 return true;
1432}
1433
1434ComplexDeinterleavingGraph::CompositeNode *
1435ComplexDeinterleavingGraph::identifyMultiplications(
1436 SmallVectorImpl<Product> &RealMuls, SmallVectorImpl<Product> &ImagMuls,
1437 CompositeNode *Accumulator = nullptr) {
1438 if (RealMuls.size() != ImagMuls.size())
1439 return nullptr;
1440
1441 SmallVector<PartialMulCandidate> Info;
1442 if (!collectPartialMuls(RealMuls, ImagMuls, PartialMulCandidates&: Info))
1443 return nullptr;
1444
1445 // Map to store common instruction to node pointers
1446 DenseMap<Value *, CompositeNode *> CommonToNode;
1447 SmallVector<bool> Processed(Info.size(), false);
1448 for (unsigned I = 0; I < Info.size(); ++I) {
1449 if (Processed[I])
1450 continue;
1451
1452 PartialMulCandidate &InfoA = Info[I];
1453 for (unsigned J = I + 1; J < Info.size(); ++J) {
1454 if (Processed[J])
1455 continue;
1456
1457 PartialMulCandidate &InfoB = Info[J];
1458 auto *InfoReal = &InfoA;
1459 auto *InfoImag = &InfoB;
1460
1461 auto NodeFromCommon = identifyNode(R: InfoReal->Common, I: InfoImag->Common);
1462 if (!NodeFromCommon) {
1463 std::swap(a&: InfoReal, b&: InfoImag);
1464 NodeFromCommon = identifyNode(R: InfoReal->Common, I: InfoImag->Common);
1465 }
1466 if (!NodeFromCommon)
1467 continue;
1468
1469 CommonToNode[InfoReal->Common] = NodeFromCommon;
1470 CommonToNode[InfoImag->Common] = NodeFromCommon;
1471 Processed[I] = true;
1472 Processed[J] = true;
1473 }
1474 }
1475
1476 SmallVector<bool> ProcessedReal(RealMuls.size(), false);
1477 SmallVector<bool> ProcessedImag(ImagMuls.size(), false);
1478 CompositeNode *Result = Accumulator;
1479 for (auto &PMI : Info) {
1480 if (ProcessedReal[PMI.RealIdx] || ProcessedImag[PMI.ImagIdx])
1481 continue;
1482
1483 auto It = CommonToNode.find(Val: PMI.Common);
1484 // TODO: Process independent complex multiplications. Cases like this:
1485 // A.real() * B where both A and B are complex numbers.
1486 if (It == CommonToNode.end()) {
1487 LLVM_DEBUG({
1488 dbgs() << "Unprocessed independent partial multiplication:\n";
1489 for (auto *Mul : {&RealMuls[PMI.RealIdx], &RealMuls[PMI.RealIdx]})
1490 dbgs().indent(4) << (Mul->IsPositive ? "+" : "-") << *Mul->Multiplier
1491 << " multiplied by " << *Mul->Multiplicand << "\n";
1492 });
1493 return nullptr;
1494 }
1495
1496 auto &RealMul = RealMuls[PMI.RealIdx];
1497 auto &ImagMul = ImagMuls[PMI.ImagIdx];
1498
1499 auto NodeA = It->second;
1500 auto NodeB = PMI.Node;
1501 auto IsMultiplicandReal = PMI.Common == NodeA->Vals[0].Real;
1502 // The following table illustrates the relationship between multiplications
1503 // and rotations. If we consider the multiplication (X + iY) * (U + iV), we
1504 // can see:
1505 //
1506 // Rotation | Real | Imag |
1507 // ---------+--------+--------+
1508 // 0 | x * u | x * v |
1509 // 90 | -y * v | y * u |
1510 // 180 | -x * u | -x * v |
1511 // 270 | y * v | -y * u |
1512 //
1513 // Check if the candidate can indeed be represented by partial
1514 // multiplication
1515 // TODO: Add support for multiplication by complex one
1516 if ((IsMultiplicandReal && PMI.IsNodeInverted) ||
1517 (!IsMultiplicandReal && !PMI.IsNodeInverted))
1518 continue;
1519
1520 // Determine the rotation based on the multiplications
1521 ComplexDeinterleavingRotation Rotation;
1522 if (IsMultiplicandReal) {
1523 // Detect 0 and 180 degrees rotation
1524 if (RealMul.IsPositive && ImagMul.IsPositive)
1525 Rotation = llvm::ComplexDeinterleavingRotation::Rotation_0;
1526 else if (!RealMul.IsPositive && !ImagMul.IsPositive)
1527 Rotation = llvm::ComplexDeinterleavingRotation::Rotation_180;
1528 else
1529 continue;
1530
1531 } else {
1532 // Detect 90 and 270 degrees rotation
1533 if (!RealMul.IsPositive && ImagMul.IsPositive)
1534 Rotation = llvm::ComplexDeinterleavingRotation::Rotation_90;
1535 else if (RealMul.IsPositive && !ImagMul.IsPositive)
1536 Rotation = llvm::ComplexDeinterleavingRotation::Rotation_270;
1537 else
1538 continue;
1539 }
1540
1541 LLVM_DEBUG({
1542 dbgs() << "Identified partial multiplication (X, Y) * (U, V):\n";
1543 dbgs().indent(4) << "X: " << *NodeA->Vals[0].Real << "\n";
1544 dbgs().indent(4) << "Y: " << *NodeA->Vals[0].Imag << "\n";
1545 dbgs().indent(4) << "U: " << *NodeB->Vals[0].Real << "\n";
1546 dbgs().indent(4) << "V: " << *NodeB->Vals[0].Imag << "\n";
1547 dbgs().indent(4) << "Rotation - " << (int)Rotation * 90 << "\n";
1548 });
1549
1550 CompositeNode *NodeMul = prepareCompositeNode(
1551 Operation: ComplexDeinterleavingOperation::CMulPartial, R: nullptr, I: nullptr);
1552 NodeMul->Rotation = Rotation;
1553 NodeMul->addOperand(Node: NodeA);
1554 NodeMul->addOperand(Node: NodeB);
1555 if (Result)
1556 NodeMul->addOperand(Node: Result);
1557 submitCompositeNode(Node: NodeMul);
1558 Result = NodeMul;
1559 ProcessedReal[PMI.RealIdx] = true;
1560 ProcessedImag[PMI.ImagIdx] = true;
1561 }
1562
1563 // Ensure all products have been processed, if not return nullptr.
1564 if (!all_of(Range&: ProcessedReal, P: [](bool V) { return V; }) ||
1565 !all_of(Range&: ProcessedImag, P: [](bool V) { return V; })) {
1566
1567 // Dump debug information about which partial multiplications are not
1568 // processed.
1569 LLVM_DEBUG({
1570 dbgs() << "Unprocessed products (Real):\n";
1571 for (size_t i = 0; i < ProcessedReal.size(); ++i) {
1572 if (!ProcessedReal[i])
1573 dbgs().indent(4) << (RealMuls[i].IsPositive ? "+" : "-")
1574 << *RealMuls[i].Multiplier << " multiplied by "
1575 << *RealMuls[i].Multiplicand << "\n";
1576 }
1577 dbgs() << "Unprocessed products (Imag):\n";
1578 for (size_t i = 0; i < ProcessedImag.size(); ++i) {
1579 if (!ProcessedImag[i])
1580 dbgs().indent(4) << (ImagMuls[i].IsPositive ? "+" : "-")
1581 << *ImagMuls[i].Multiplier << " multiplied by "
1582 << *ImagMuls[i].Multiplicand << "\n";
1583 }
1584 });
1585 return nullptr;
1586 }
1587
1588 return Result;
1589}
1590
1591ComplexDeinterleavingGraph::CompositeNode *
1592ComplexDeinterleavingGraph::identifyAdditions(
1593 AddendList &RealAddends, AddendList &ImagAddends,
1594 std::optional<FastMathFlags> Flags, CompositeNode *Accumulator = nullptr) {
1595 if (RealAddends.size() != ImagAddends.size())
1596 return nullptr;
1597
1598 CompositeNode *Result = nullptr;
1599 // If we have accumulator use it as first addend
1600 if (Accumulator)
1601 Result = Accumulator;
1602 // Otherwise find an element with both positive real and imaginary parts.
1603 else
1604 Result = extractPositiveAddend(RealAddends, ImagAddends);
1605
1606 if (!Result)
1607 return nullptr;
1608
1609 while (!RealAddends.empty()) {
1610 auto ItR = RealAddends.begin();
1611 auto [R, IsPositiveR] = *ItR;
1612
1613 bool FoundImag = false;
1614 for (auto ItI = ImagAddends.begin(); ItI != ImagAddends.end(); ++ItI) {
1615 auto [I, IsPositiveI] = *ItI;
1616 ComplexDeinterleavingRotation Rotation;
1617 if (IsPositiveR && IsPositiveI)
1618 Rotation = ComplexDeinterleavingRotation::Rotation_0;
1619 else if (!IsPositiveR && IsPositiveI)
1620 Rotation = ComplexDeinterleavingRotation::Rotation_90;
1621 else if (!IsPositiveR && !IsPositiveI)
1622 Rotation = ComplexDeinterleavingRotation::Rotation_180;
1623 else
1624 Rotation = ComplexDeinterleavingRotation::Rotation_270;
1625
1626 CompositeNode *AddNode = nullptr;
1627 if (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||
1628 Rotation == ComplexDeinterleavingRotation::Rotation_180) {
1629 AddNode = identifyNode(R, I);
1630 } else {
1631 AddNode = identifyNode(R: I, I: R);
1632 }
1633 if (AddNode) {
1634 LLVM_DEBUG({
1635 dbgs() << "Identified addition:\n";
1636 dbgs().indent(4) << "X: " << *R << "\n";
1637 dbgs().indent(4) << "Y: " << *I << "\n";
1638 dbgs().indent(4) << "Rotation - " << (int)Rotation * 90 << "\n";
1639 });
1640
1641 CompositeNode *TmpNode = nullptr;
1642 if (Rotation == llvm::ComplexDeinterleavingRotation::Rotation_0) {
1643 TmpNode = prepareCompositeNode(
1644 Operation: ComplexDeinterleavingOperation::Symmetric, R: nullptr, I: nullptr);
1645 if (Flags) {
1646 TmpNode->Opcode = Instruction::FAdd;
1647 TmpNode->Flags = *Flags;
1648 } else {
1649 TmpNode->Opcode = Instruction::Add;
1650 }
1651 } else if (Rotation ==
1652 llvm::ComplexDeinterleavingRotation::Rotation_180) {
1653 TmpNode = prepareCompositeNode(
1654 Operation: ComplexDeinterleavingOperation::Symmetric, R: nullptr, I: nullptr);
1655 if (Flags) {
1656 TmpNode->Opcode = Instruction::FSub;
1657 TmpNode->Flags = *Flags;
1658 } else {
1659 TmpNode->Opcode = Instruction::Sub;
1660 }
1661 } else {
1662 TmpNode = prepareCompositeNode(Operation: ComplexDeinterleavingOperation::CAdd,
1663 R: nullptr, I: nullptr);
1664 TmpNode->Rotation = Rotation;
1665 }
1666
1667 TmpNode->addOperand(Node: Result);
1668 TmpNode->addOperand(Node: AddNode);
1669 submitCompositeNode(Node: TmpNode);
1670 Result = TmpNode;
1671 RealAddends.erase(I: ItR);
1672 ImagAddends.erase(I: ItI);
1673 FoundImag = true;
1674 break;
1675 }
1676 }
1677 if (!FoundImag)
1678 return nullptr;
1679 }
1680 return Result;
1681}
1682
1683ComplexDeinterleavingGraph::CompositeNode *
1684ComplexDeinterleavingGraph::extractPositiveAddend(AddendList &RealAddends,
1685 AddendList &ImagAddends) {
1686 for (auto ItR = RealAddends.begin(); ItR != RealAddends.end(); ++ItR) {
1687 for (auto ItI = ImagAddends.begin(); ItI != ImagAddends.end(); ++ItI) {
1688 auto [R, IsPositiveR] = *ItR;
1689 auto [I, IsPositiveI] = *ItI;
1690 if (IsPositiveR && IsPositiveI) {
1691 auto Result = identifyNode(R, I);
1692 if (Result) {
1693 RealAddends.erase(I: ItR);
1694 ImagAddends.erase(I: ItI);
1695 return Result;
1696 }
1697 }
1698 }
1699 }
1700 return nullptr;
1701}
1702
1703bool ComplexDeinterleavingGraph::identifyNodes(Instruction *RootI) {
1704 // This potential root instruction might already have been recognized as
1705 // reduction. Because RootToNode maps both Real and Imaginary parts to
1706 // CompositeNode we should choose only one either Real or Imag instruction to
1707 // use as an anchor for generating complex instruction.
1708 auto It = RootToNode.find(Val: RootI);
1709 if (It != RootToNode.end()) {
1710 auto RootNode = It->second;
1711 assert(RootNode->Operation ==
1712 ComplexDeinterleavingOperation::ReductionOperation ||
1713 RootNode->Operation ==
1714 ComplexDeinterleavingOperation::ReductionSingle);
1715 assert(RootNode->Vals.size() == 1 &&
1716 "Cannot handle reductions involving multiple complex values");
1717 // Find out which part, Real or Imag, comes later, and only if we come to
1718 // the latest part, add it to OrderedRoots.
1719 auto *R = cast<Instruction>(Val: RootNode->Vals[0].Real);
1720 auto *I = RootNode->Vals[0].Imag ? cast<Instruction>(Val: RootNode->Vals[0].Imag)
1721 : nullptr;
1722
1723 Instruction *ReplacementAnchor;
1724 if (I)
1725 ReplacementAnchor = R->comesBefore(Other: I) ? I : R;
1726 else
1727 ReplacementAnchor = R;
1728
1729 if (ReplacementAnchor != RootI)
1730 return false;
1731 OrderedRoots.push_back(Elt: RootI);
1732 return true;
1733 }
1734
1735 auto RootNode = identifyRoot(I: RootI);
1736 if (!RootNode)
1737 return false;
1738
1739 LLVM_DEBUG({
1740 Function *F = RootI->getFunction();
1741 BasicBlock *B = RootI->getParent();
1742 dbgs() << "Complex deinterleaving graph for " << F->getName()
1743 << "::" << B->getName() << ".\n";
1744 dump(dbgs());
1745 dbgs() << "\n";
1746 });
1747 RootToNode[RootI] = RootNode;
1748 OrderedRoots.push_back(Elt: RootI);
1749 return true;
1750}
1751
1752bool ComplexDeinterleavingGraph::collectPotentialReductions(BasicBlock *B) {
1753 bool FoundPotentialReduction = false;
1754 if (Factor != 2)
1755 return false;
1756
1757 auto *Br = dyn_cast<CondBrInst>(Val: B->getTerminator());
1758 if (!Br)
1759 return false;
1760
1761 // Identify simple one-block loop
1762 if (Br->getSuccessor(i: 0) != B && Br->getSuccessor(i: 1) != B)
1763 return false;
1764
1765 for (auto &PHI : B->phis()) {
1766 if (PHI.getNumIncomingValues() != 2)
1767 continue;
1768
1769 if (!PHI.getType()->isVectorTy())
1770 continue;
1771
1772 auto *ReductionOp = dyn_cast<Instruction>(Val: PHI.getIncomingValueForBlock(BB: B));
1773 if (!ReductionOp)
1774 continue;
1775
1776 // Check if final instruction is reduced outside of current block
1777 Instruction *FinalReduction = nullptr;
1778 auto NumUsers = 0u;
1779 for (auto *U : ReductionOp->users()) {
1780 ++NumUsers;
1781 if (U == &PHI)
1782 continue;
1783 FinalReduction = dyn_cast<Instruction>(Val: U);
1784 }
1785
1786 if (NumUsers != 2 || !FinalReduction || FinalReduction->getParent() == B ||
1787 isa<PHINode>(Val: FinalReduction))
1788 continue;
1789
1790 ReductionInfo[ReductionOp] = {&PHI, FinalReduction};
1791 BackEdge = B;
1792 auto BackEdgeIdx = PHI.getBasicBlockIndex(BB: B);
1793 auto IncomingIdx = BackEdgeIdx == 0 ? 1 : 0;
1794 Incoming = PHI.getIncomingBlock(i: IncomingIdx);
1795 FoundPotentialReduction = true;
1796
1797 // If the initial value of PHINode is an Instruction, consider it a leaf
1798 // value of a complex deinterleaving graph.
1799 if (auto *InitPHI =
1800 dyn_cast<Instruction>(Val: PHI.getIncomingValueForBlock(BB: Incoming)))
1801 FinalInstructions.insert(Ptr: InitPHI);
1802 }
1803 return FoundPotentialReduction;
1804}
1805
1806void ComplexDeinterleavingGraph::identifyReductionNodes() {
1807 assert(Factor == 2 && "Cannot handle multiple complex values");
1808
1809 SmallVector<bool> Processed(ReductionInfo.size(), false);
1810 SmallVector<Instruction *> OperationInstruction;
1811 for (auto &P : ReductionInfo)
1812 OperationInstruction.push_back(Elt: P.first);
1813
1814 // Identify a complex computation by evaluating two reduction operations that
1815 // potentially could be involved
1816 for (size_t i = 0; i < OperationInstruction.size(); ++i) {
1817 if (Processed[i])
1818 continue;
1819 for (size_t j = i + 1; j < OperationInstruction.size(); ++j) {
1820 if (Processed[j])
1821 continue;
1822 auto *Real = OperationInstruction[i];
1823 auto *Imag = OperationInstruction[j];
1824 if (Real->getType() != Imag->getType())
1825 continue;
1826
1827 RealPHI = ReductionInfo[Real].first;
1828 ImagPHI = ReductionInfo[Imag].first;
1829 PHIsFound = false;
1830 auto Node = identifyNode(R: Real, I: Imag);
1831 if (!Node) {
1832 std::swap(a&: Real, b&: Imag);
1833 std::swap(a&: RealPHI, b&: ImagPHI);
1834 Node = identifyNode(R: Real, I: Imag);
1835 }
1836
1837 // If a node is identified and reduction PHINode is used in the chain of
1838 // operations, mark its operation instructions as used to prevent
1839 // re-identification and attach the node to the real part
1840 if (Node && PHIsFound) {
1841 LLVM_DEBUG(dbgs() << "Identified reduction starting from instructions: "
1842 << *Real << " / " << *Imag << "\n");
1843 Processed[i] = true;
1844 Processed[j] = true;
1845 auto RootNode = prepareCompositeNode(
1846 Operation: ComplexDeinterleavingOperation::ReductionOperation, R: Real, I: Imag);
1847 RootNode->addOperand(Node);
1848 RootToNode[Real] = RootNode;
1849 RootToNode[Imag] = RootNode;
1850 submitCompositeNode(Node: RootNode);
1851 break;
1852 }
1853 }
1854
1855 auto *Real = OperationInstruction[i];
1856 // We want to check that we have 2 operands, but the function attributes
1857 // being counted as operands bloats this value.
1858 if (Processed[i] || Real->getNumOperands() < 2)
1859 continue;
1860
1861 // Can only combined integer reductions at the moment.
1862 if (!ReductionInfo[Real].second->getType()->isIntegerTy())
1863 continue;
1864
1865 RealPHI = ReductionInfo[Real].first;
1866 ImagPHI = nullptr;
1867 PHIsFound = false;
1868 auto Node = identifyNode(R: Real->getOperand(i: 0), I: Real->getOperand(i: 1));
1869 if (Node && PHIsFound) {
1870 LLVM_DEBUG(
1871 dbgs() << "Identified single reduction starting from instruction: "
1872 << *Real << "/" << *ReductionInfo[Real].second << "\n");
1873
1874 // Reducing to a single vector is not supported, only permit reducing down
1875 // to scalar values.
1876 // Doing this here will leave the prior node in the graph,
1877 // however with no uses the node will be unreachable by the replacement
1878 // process. That along with the usage outside the graph should prevent the
1879 // replacement process from kicking off at all for this graph.
1880 // TODO Add support for reducing to a single vector value
1881 if (ReductionInfo[Real].second->getType()->isVectorTy())
1882 continue;
1883
1884 Processed[i] = true;
1885 auto RootNode = prepareCompositeNode(
1886 Operation: ComplexDeinterleavingOperation::ReductionSingle, R: Real, I: nullptr);
1887 RootNode->addOperand(Node);
1888 RootToNode[Real] = RootNode;
1889 submitCompositeNode(Node: RootNode);
1890 }
1891 }
1892
1893 RealPHI = nullptr;
1894 ImagPHI = nullptr;
1895}
1896
1897bool ComplexDeinterleavingGraph::checkNodes() {
1898 bool FoundDeinterleaveNode = false;
1899 for (CompositeNode *N : CompositeNodes) {
1900 if (!N->areOperandsValid())
1901 return false;
1902
1903 if (N->Operation == ComplexDeinterleavingOperation::Deinterleave)
1904 FoundDeinterleaveNode = true;
1905 }
1906
1907 // We need a deinterleave node in order to guarantee that we're working with
1908 // complex numbers.
1909 if (!FoundDeinterleaveNode) {
1910 LLVM_DEBUG(
1911 dbgs() << "Couldn't find a deinterleave node within the graph, cannot "
1912 "guarantee safety during graph transformation.\n");
1913 return false;
1914 }
1915
1916 // Collect all instructions from roots to leaves
1917 SmallPtrSet<Instruction *, 16> AllInstructions;
1918 SmallVector<Instruction *, 8> Worklist;
1919 for (auto &Pair : RootToNode)
1920 Worklist.push_back(Elt: Pair.first);
1921
1922 // Extract all instructions that are used by all XCMLA/XCADD/ADD/SUB/NEG
1923 // chains
1924 while (!Worklist.empty()) {
1925 auto *I = Worklist.pop_back_val();
1926
1927 if (!AllInstructions.insert(Ptr: I).second)
1928 continue;
1929
1930 for (Value *Op : I->operands()) {
1931 if (auto *OpI = dyn_cast<Instruction>(Val: Op)) {
1932 if (!FinalInstructions.count(Ptr: I))
1933 Worklist.emplace_back(Args&: OpI);
1934 }
1935 }
1936 }
1937
1938 // Find instructions that have users outside of chain
1939 for (auto *I : AllInstructions) {
1940 // Skip root nodes
1941 if (RootToNode.count(Val: I))
1942 continue;
1943
1944 for (User *U : I->users()) {
1945 if (AllInstructions.count(Ptr: cast<Instruction>(Val: U)))
1946 continue;
1947
1948 // Found an instruction that is not used by XCMLA/XCADD chain
1949 Worklist.emplace_back(Args&: I);
1950 break;
1951 }
1952 }
1953
1954 // If any instructions are found to be used outside, find and remove roots
1955 // that somehow connect to those instructions.
1956 SmallPtrSet<Instruction *, 16> Visited;
1957 while (!Worklist.empty()) {
1958 auto *I = Worklist.pop_back_val();
1959 if (!Visited.insert(Ptr: I).second)
1960 continue;
1961
1962 // Found an impacted root node. Removing it from the nodes to be
1963 // deinterleaved
1964 if (RootToNode.count(Val: I)) {
1965 LLVM_DEBUG(dbgs() << "Instruction " << *I
1966 << " could be deinterleaved but its chain of complex "
1967 "operations have an outside user\n");
1968 RootToNode.erase(Val: I);
1969 }
1970
1971 if (!AllInstructions.count(Ptr: I) || FinalInstructions.count(Ptr: I))
1972 continue;
1973
1974 for (User *U : I->users())
1975 Worklist.emplace_back(Args: cast<Instruction>(Val: U));
1976
1977 for (Value *Op : I->operands()) {
1978 if (auto *OpI = dyn_cast<Instruction>(Val: Op))
1979 Worklist.emplace_back(Args&: OpI);
1980 }
1981 }
1982 return !RootToNode.empty();
1983}
1984
1985ComplexDeinterleavingGraph::CompositeNode *
1986ComplexDeinterleavingGraph::identifyRoot(Instruction *RootI) {
1987 if (auto *Intrinsic = dyn_cast<IntrinsicInst>(Val: RootI)) {
1988 if (Intrinsic::getInterleaveIntrinsicID(Factor) !=
1989 Intrinsic->getIntrinsicID())
1990 return nullptr;
1991
1992 ComplexValues Vals;
1993 for (unsigned I = 0; I < Factor; I += 2) {
1994 auto *Real = dyn_cast<Instruction>(Val: Intrinsic->getOperand(i_nocapture: I));
1995 auto *Imag = dyn_cast<Instruction>(Val: Intrinsic->getOperand(i_nocapture: I + 1));
1996 if (!Real || !Imag)
1997 return nullptr;
1998 Vals.push_back(Elt: {.Real: Real, .Imag: Imag});
1999 }
2000
2001 ComplexDeinterleavingGraph::CompositeNode *Node1 = identifyNode(Vals);
2002 if (!Node1)
2003 return nullptr;
2004 return Node1;
2005 }
2006
2007 // TODO: We could also add support for fixed-width interleave factors of 4
2008 // and above, but currently for symmetric operations the interleaves and
2009 // deinterleaves are already removed by VectorCombine. If we extend this to
2010 // permit complex multiplications, reductions, etc. then we should also add
2011 // support for fixed-width here.
2012 if (Factor != 2)
2013 return nullptr;
2014
2015 auto *SVI = dyn_cast<ShuffleVectorInst>(Val: RootI);
2016 if (!SVI)
2017 return nullptr;
2018
2019 // Look for a shufflevector that takes separate vectors of the real and
2020 // imaginary components and recombines them into a single vector.
2021 if (!isInterleavingMask(Mask: SVI->getShuffleMask()))
2022 return nullptr;
2023
2024 Instruction *Real;
2025 Instruction *Imag;
2026 if (!match(V: RootI, P: m_Shuffle(v1: m_Instruction(I&: Real), v2: m_Instruction(I&: Imag))))
2027 return nullptr;
2028
2029 return identifyNode(R: Real, I: Imag);
2030}
2031
2032ComplexDeinterleavingGraph::CompositeNode *
2033ComplexDeinterleavingGraph::identifyDeinterleave(ComplexValues &Vals) {
2034 Instruction *II = nullptr;
2035
2036 // Must be at least one complex value.
2037 auto CheckExtract = [&](Value *V, unsigned ExpectedIdx,
2038 Instruction *ExpectedInsn) -> ExtractValueInst * {
2039 auto *EVI = dyn_cast<ExtractValueInst>(Val: V);
2040 if (!EVI || EVI->getNumIndices() != 1 ||
2041 EVI->getIndices()[0] != ExpectedIdx ||
2042 !isa<Instruction>(Val: EVI->getAggregateOperand()) ||
2043 (ExpectedInsn && ExpectedInsn != EVI->getAggregateOperand()))
2044 return nullptr;
2045 return EVI;
2046 };
2047
2048 for (unsigned Idx = 0; Idx < Vals.size(); Idx++) {
2049 ExtractValueInst *RealEVI = CheckExtract(Vals[Idx].Real, Idx * 2, II);
2050 if (RealEVI && Idx == 0)
2051 II = cast<Instruction>(Val: RealEVI->getAggregateOperand());
2052 if (!RealEVI || !CheckExtract(Vals[Idx].Imag, (Idx * 2) + 1, II)) {
2053 II = nullptr;
2054 break;
2055 }
2056 }
2057
2058 if (auto *IntrinsicII = dyn_cast_or_null<IntrinsicInst>(Val: II)) {
2059 if (IntrinsicII->getIntrinsicID() !=
2060 Intrinsic::getDeinterleaveIntrinsicID(Factor: 2 * Vals.size()))
2061 return nullptr;
2062
2063 // The remaining should match too.
2064 CompositeNode *PlaceholderNode = prepareCompositeNode(
2065 Operation: llvm::ComplexDeinterleavingOperation::Deinterleave, Vals);
2066 PlaceholderNode->ReplacementNode = II->getOperand(i: 0);
2067 for (auto &V : Vals) {
2068 FinalInstructions.insert(Ptr: cast<Instruction>(Val: V.Real));
2069 FinalInstructions.insert(Ptr: cast<Instruction>(Val: V.Imag));
2070 }
2071 return submitCompositeNode(Node: PlaceholderNode);
2072 }
2073
2074 if (Vals.size() != 1)
2075 return nullptr;
2076
2077 Value *Real = Vals[0].Real;
2078 Value *Imag = Vals[0].Imag;
2079 auto *RealShuffle = dyn_cast<ShuffleVectorInst>(Val: Real);
2080 auto *ImagShuffle = dyn_cast<ShuffleVectorInst>(Val: Imag);
2081 if (!RealShuffle || !ImagShuffle) {
2082 if (RealShuffle || ImagShuffle)
2083 LLVM_DEBUG(dbgs() << " - There's a shuffle where there shouldn't be.\n");
2084 return nullptr;
2085 }
2086
2087 Value *RealOp1 = RealShuffle->getOperand(i_nocapture: 1);
2088 if (!isa<UndefValue>(Val: RealOp1) && !match(V: RealOp1, P: m_Zero())) {
2089 LLVM_DEBUG(dbgs() << " - RealOp1 is not undef or zero.\n");
2090 return nullptr;
2091 }
2092 Value *ImagOp1 = ImagShuffle->getOperand(i_nocapture: 1);
2093 if (!isa<UndefValue>(Val: ImagOp1) && !match(V: ImagOp1, P: m_Zero())) {
2094 LLVM_DEBUG(dbgs() << " - ImagOp1 is not undef or zero.\n");
2095 return nullptr;
2096 }
2097
2098 Value *RealOp0 = RealShuffle->getOperand(i_nocapture: 0);
2099 Value *ImagOp0 = ImagShuffle->getOperand(i_nocapture: 0);
2100
2101 if (RealOp0 != ImagOp0) {
2102 LLVM_DEBUG(dbgs() << " - Shuffle operands are not equal.\n");
2103 return nullptr;
2104 }
2105
2106 ArrayRef<int> RealMask = RealShuffle->getShuffleMask();
2107 ArrayRef<int> ImagMask = ImagShuffle->getShuffleMask();
2108 if (!isDeinterleavingMask(Mask: RealMask) || !isDeinterleavingMask(Mask: ImagMask)) {
2109 LLVM_DEBUG(dbgs() << " - Masks are not deinterleaving.\n");
2110 return nullptr;
2111 }
2112
2113 if (RealMask[0] != 0 || ImagMask[0] != 1) {
2114 LLVM_DEBUG(dbgs() << " - Masks do not have the correct initial value.\n");
2115 return nullptr;
2116 }
2117
2118 // Type checking, the shuffle type should be a vector type of the same
2119 // scalar type, but half the size
2120 auto CheckType = [&](ShuffleVectorInst *Shuffle) {
2121 Value *Op = Shuffle->getOperand(i_nocapture: 0);
2122 auto *ShuffleTy = cast<FixedVectorType>(Val: Shuffle->getType());
2123 auto *OpTy = cast<FixedVectorType>(Val: Op->getType());
2124
2125 if (OpTy->getScalarType() != ShuffleTy->getScalarType())
2126 return false;
2127 if ((ShuffleTy->getNumElements() * 2) != OpTy->getNumElements())
2128 return false;
2129
2130 return true;
2131 };
2132
2133 auto CheckDeinterleavingShuffle = [&](ShuffleVectorInst *Shuffle) -> bool {
2134 if (!CheckType(Shuffle))
2135 return false;
2136
2137 ArrayRef<int> Mask = Shuffle->getShuffleMask();
2138 int Last = *Mask.rbegin();
2139
2140 Value *Op = Shuffle->getOperand(i_nocapture: 0);
2141 auto *OpTy = cast<FixedVectorType>(Val: Op->getType());
2142 int NumElements = OpTy->getNumElements();
2143
2144 // Ensure that the deinterleaving shuffle only pulls from the first
2145 // shuffle operand.
2146 return Last < NumElements;
2147 };
2148
2149 if (RealShuffle->getType() != ImagShuffle->getType()) {
2150 LLVM_DEBUG(dbgs() << " - Shuffle types aren't equal.\n");
2151 return nullptr;
2152 }
2153 if (!CheckDeinterleavingShuffle(RealShuffle)) {
2154 LLVM_DEBUG(dbgs() << " - RealShuffle is invalid type.\n");
2155 return nullptr;
2156 }
2157 if (!CheckDeinterleavingShuffle(ImagShuffle)) {
2158 LLVM_DEBUG(dbgs() << " - ImagShuffle is invalid type.\n");
2159 return nullptr;
2160 }
2161
2162 CompositeNode *PlaceholderNode =
2163 prepareCompositeNode(Operation: llvm::ComplexDeinterleavingOperation::Deinterleave,
2164 R: RealShuffle, I: ImagShuffle);
2165 PlaceholderNode->ReplacementNode = RealShuffle->getOperand(i_nocapture: 0);
2166 FinalInstructions.insert(Ptr: RealShuffle);
2167 FinalInstructions.insert(Ptr: ImagShuffle);
2168 return submitCompositeNode(Node: PlaceholderNode);
2169}
2170
2171ComplexDeinterleavingGraph::CompositeNode *
2172ComplexDeinterleavingGraph::identifySplat(ComplexValues &Vals) {
2173 auto IsSplat = [](Value *V) -> bool {
2174 // Fixed-width vector with constants
2175 if (isa<ConstantDataVector>(Val: V))
2176 return true;
2177
2178 if (isa<ConstantInt>(Val: V) || isa<ConstantFP>(Val: V))
2179 return isa<VectorType>(Val: V->getType());
2180
2181 VectorType *VTy;
2182 ArrayRef<int> Mask;
2183 // Splats are represented differently depending on whether the repeated
2184 // value is a constant or an Instruction
2185 if (auto *Const = dyn_cast<ConstantExpr>(Val: V)) {
2186 if (Const->getOpcode() != Instruction::ShuffleVector)
2187 return false;
2188 VTy = cast<VectorType>(Val: Const->getType());
2189 Mask = Const->getShuffleMask();
2190 } else if (auto *Shuf = dyn_cast<ShuffleVectorInst>(Val: V)) {
2191 VTy = Shuf->getType();
2192 Mask = Shuf->getShuffleMask();
2193 } else {
2194 return false;
2195 }
2196
2197 // When the data type is <1 x Type>, it's not possible to differentiate
2198 // between the ComplexDeinterleaving::Deinterleave and
2199 // ComplexDeinterleaving::Splat operations.
2200 if (!VTy->isScalableTy() && VTy->getElementCount().getKnownMinValue() == 1)
2201 return false;
2202
2203 return all_equal(Range&: Mask) && Mask[0] == 0;
2204 };
2205
2206 // The splats must meet the following requirements:
2207 // 1. Must either be all instructions or all values.
2208 // 2. Non-constant splats must live in the same block.
2209 if (auto *FirstValAsInstruction = dyn_cast<Instruction>(Val: Vals[0].Real)) {
2210 BasicBlock *FirstBB = FirstValAsInstruction->getParent();
2211 for (auto &V : Vals) {
2212 if (!IsSplat(V.Real) || !IsSplat(V.Imag))
2213 return nullptr;
2214
2215 auto *Real = dyn_cast<Instruction>(Val: V.Real);
2216 auto *Imag = dyn_cast<Instruction>(Val: V.Imag);
2217 if (!Real || !Imag || Real->getParent() != FirstBB ||
2218 Imag->getParent() != FirstBB)
2219 return nullptr;
2220 }
2221 } else {
2222 for (auto &V : Vals) {
2223 if (!IsSplat(V.Real) || !IsSplat(V.Imag) || isa<Instruction>(Val: V.Real) ||
2224 isa<Instruction>(Val: V.Imag))
2225 return nullptr;
2226 }
2227 }
2228
2229 for (auto &V : Vals) {
2230 auto *Real = dyn_cast<Instruction>(Val: V.Real);
2231 auto *Imag = dyn_cast<Instruction>(Val: V.Imag);
2232 if (Real && Imag) {
2233 FinalInstructions.insert(Ptr: Real);
2234 FinalInstructions.insert(Ptr: Imag);
2235 }
2236 }
2237 CompositeNode *PlaceholderNode =
2238 prepareCompositeNode(Operation: ComplexDeinterleavingOperation::Splat, Vals);
2239 return submitCompositeNode(Node: PlaceholderNode);
2240}
2241
2242ComplexDeinterleavingGraph::CompositeNode *
2243ComplexDeinterleavingGraph::identifyPHINode(Instruction *Real,
2244 Instruction *Imag) {
2245 if (Real != RealPHI || (ImagPHI && Imag != ImagPHI))
2246 return nullptr;
2247
2248 PHIsFound = true;
2249 CompositeNode *PlaceholderNode = prepareCompositeNode(
2250 Operation: ComplexDeinterleavingOperation::ReductionPHI, R: Real, I: Imag);
2251 return submitCompositeNode(Node: PlaceholderNode);
2252}
2253
2254ComplexDeinterleavingGraph::CompositeNode *
2255ComplexDeinterleavingGraph::identifySelectNode(Instruction *Real,
2256 Instruction *Imag) {
2257 auto *SelectReal = dyn_cast<SelectInst>(Val: Real);
2258 auto *SelectImag = dyn_cast<SelectInst>(Val: Imag);
2259 if (!SelectReal || !SelectImag)
2260 return nullptr;
2261
2262 Instruction *MaskA, *MaskB;
2263 Instruction *AR, *AI, *RA, *BI;
2264 if (!match(V: Real, P: m_Select(C: m_Instruction(I&: MaskA), L: m_Instruction(I&: AR),
2265 R: m_Instruction(I&: RA))) ||
2266 !match(V: Imag, P: m_Select(C: m_Instruction(I&: MaskB), L: m_Instruction(I&: AI),
2267 R: m_Instruction(I&: BI))))
2268 return nullptr;
2269
2270 if (MaskA != MaskB && !MaskA->isIdenticalTo(I: MaskB))
2271 return nullptr;
2272
2273 if (!MaskA->getType()->isVectorTy())
2274 return nullptr;
2275
2276 auto NodeA = identifyNode(R: AR, I: AI);
2277 if (!NodeA)
2278 return nullptr;
2279
2280 auto NodeB = identifyNode(R: RA, I: BI);
2281 if (!NodeB)
2282 return nullptr;
2283
2284 CompositeNode *PlaceholderNode = prepareCompositeNode(
2285 Operation: ComplexDeinterleavingOperation::ReductionSelect, R: Real, I: Imag);
2286 PlaceholderNode->addOperand(Node: NodeA);
2287 PlaceholderNode->addOperand(Node: NodeB);
2288 FinalInstructions.insert(Ptr: MaskA);
2289 FinalInstructions.insert(Ptr: MaskB);
2290 return submitCompositeNode(Node: PlaceholderNode);
2291}
2292
2293static Value *replaceSymmetricNode(IRBuilderBase &B, unsigned Opcode,
2294 std::optional<FastMathFlags> Flags,
2295 Value *InputA, Value *InputB) {
2296 Value *I;
2297 switch (Opcode) {
2298 case Instruction::FNeg:
2299 I = B.CreateFNeg(V: InputA);
2300 break;
2301 case Instruction::FAdd:
2302 I = B.CreateFAdd(L: InputA, R: InputB);
2303 break;
2304 case Instruction::Add:
2305 I = B.CreateAdd(LHS: InputA, RHS: InputB);
2306 break;
2307 case Instruction::FSub:
2308 I = B.CreateFSub(L: InputA, R: InputB);
2309 break;
2310 case Instruction::Sub:
2311 I = B.CreateSub(LHS: InputA, RHS: InputB);
2312 break;
2313 case Instruction::FMul:
2314 I = B.CreateFMul(L: InputA, R: InputB);
2315 break;
2316 case Instruction::Mul:
2317 I = B.CreateMul(LHS: InputA, RHS: InputB);
2318 break;
2319 default:
2320 llvm_unreachable("Incorrect symmetric opcode");
2321 }
2322 if (Flags)
2323 cast<Instruction>(Val: I)->setFastMathFlags(*Flags);
2324 return I;
2325}
2326
2327Value *ComplexDeinterleavingGraph::replaceNode(IRBuilderBase &Builder,
2328 CompositeNode *Node) {
2329 if (Node->ReplacementNode)
2330 return Node->ReplacementNode;
2331
2332 auto ReplaceOperandIfExist = [&](CompositeNode *Node,
2333 unsigned Idx) -> Value * {
2334 return Node->Operands.size() > Idx
2335 ? replaceNode(Builder, Node: Node->Operands[Idx])
2336 : nullptr;
2337 };
2338
2339 Value *ReplacementNode = nullptr;
2340 switch (Node->Operation) {
2341 case ComplexDeinterleavingOperation::CDot: {
2342 Value *Input0 = ReplaceOperandIfExist(Node, 0);
2343 Value *Input1 = ReplaceOperandIfExist(Node, 1);
2344 Value *Accumulator = ReplaceOperandIfExist(Node, 2);
2345 assert(!Input1 || (Input0->getType() == Input1->getType() &&
2346 "Node inputs need to be of the same type"));
2347 ReplacementNode = TL->createComplexDeinterleavingIR(
2348 B&: Builder, OperationType: Node->Operation, Rotation: Node->Rotation, InputA: Input0, InputB: Input1, Accumulator);
2349 break;
2350 }
2351 case ComplexDeinterleavingOperation::CAdd:
2352 case ComplexDeinterleavingOperation::CMulPartial:
2353 case ComplexDeinterleavingOperation::Symmetric: {
2354 Value *Input0 = ReplaceOperandIfExist(Node, 0);
2355 Value *Input1 = ReplaceOperandIfExist(Node, 1);
2356 Value *Accumulator = ReplaceOperandIfExist(Node, 2);
2357 assert(!Input1 || (Input0->getType() == Input1->getType() &&
2358 "Node inputs need to be of the same type"));
2359 assert(!Accumulator ||
2360 (Input0->getType() == Accumulator->getType() &&
2361 "Accumulator and input need to be of the same type"));
2362 if (Node->Operation == ComplexDeinterleavingOperation::Symmetric)
2363 ReplacementNode = replaceSymmetricNode(B&: Builder, Opcode: Node->Opcode, Flags: Node->Flags,
2364 InputA: Input0, InputB: Input1);
2365 else
2366 ReplacementNode = TL->createComplexDeinterleavingIR(
2367 B&: Builder, OperationType: Node->Operation, Rotation: Node->Rotation, InputA: Input0, InputB: Input1,
2368 Accumulator);
2369 break;
2370 }
2371 case ComplexDeinterleavingOperation::Deinterleave:
2372 llvm_unreachable("Deinterleave node should already have ReplacementNode");
2373 break;
2374 case ComplexDeinterleavingOperation::Splat: {
2375 SmallVector<Value *> Ops;
2376 for (auto &V : Node->Vals) {
2377 Ops.push_back(Elt: V.Real);
2378 Ops.push_back(Elt: V.Imag);
2379 }
2380 auto *R = dyn_cast<Instruction>(Val: Node->Vals[0].Real);
2381 auto *I = dyn_cast<Instruction>(Val: Node->Vals[0].Imag);
2382 if (R && I) {
2383 // Splats that are not constant are interleaved where they are located
2384 Instruction *InsertPoint = R;
2385 for (auto V : Node->Vals) {
2386 if (InsertPoint->comesBefore(Other: cast<Instruction>(Val: V.Real)))
2387 InsertPoint = cast<Instruction>(Val: V.Real);
2388 if (InsertPoint->comesBefore(Other: cast<Instruction>(Val: V.Imag)))
2389 InsertPoint = cast<Instruction>(Val: V.Imag);
2390 }
2391 InsertPoint = InsertPoint->getNextNode();
2392 IRBuilder<> IRB(InsertPoint);
2393 ReplacementNode = IRB.CreateVectorInterleave(Ops);
2394 } else {
2395 ReplacementNode = Builder.CreateVectorInterleave(Ops);
2396 }
2397 break;
2398 }
2399 case ComplexDeinterleavingOperation::ReductionPHI: {
2400 // If Operation is ReductionPHI, a new empty PHINode is created.
2401 // It is filled later when the ReductionOperation is processed.
2402 auto *OldPHI = cast<PHINode>(Val: Node->Vals[0].Real);
2403 auto *VTy = cast<VectorType>(Val: Node->Vals[0].Real->getType());
2404 auto *NewVTy = VectorType::getDoubleElementsVectorType(VTy);
2405 auto *NewPHI = PHINode::Create(Ty: NewVTy, NumReservedValues: 0, NameStr: "", InsertBefore: BackEdge->getFirstNonPHIIt());
2406 OldToNewPHI[OldPHI] = NewPHI;
2407 ReplacementNode = NewPHI;
2408 break;
2409 }
2410 case ComplexDeinterleavingOperation::ReductionSingle:
2411 ReplacementNode = replaceNode(Builder, Node: Node->Operands[0]);
2412 processReductionSingle(OperationReplacement: ReplacementNode, Node);
2413 break;
2414 case ComplexDeinterleavingOperation::ReductionOperation:
2415 ReplacementNode = replaceNode(Builder, Node: Node->Operands[0]);
2416 processReductionOperation(OperationReplacement: ReplacementNode, Node);
2417 break;
2418 case ComplexDeinterleavingOperation::ReductionSelect: {
2419 auto *MaskReal = cast<Instruction>(Val: Node->Vals[0].Real)->getOperand(i: 0);
2420 auto *MaskImag = cast<Instruction>(Val: Node->Vals[0].Imag)->getOperand(i: 0);
2421 auto *A = replaceNode(Builder, Node: Node->Operands[0]);
2422 auto *B = replaceNode(Builder, Node: Node->Operands[1]);
2423 auto *NewMask = Builder.CreateVectorInterleave(Ops: {MaskReal, MaskImag});
2424 ReplacementNode = Builder.CreateSelect(C: NewMask, True: A, False: B);
2425 break;
2426 }
2427 }
2428
2429 assert(ReplacementNode && "Target failed to create Intrinsic call.");
2430 NumComplexTransformations += 1;
2431 Node->ReplacementNode = ReplacementNode;
2432 return ReplacementNode;
2433}
2434
2435void ComplexDeinterleavingGraph::processReductionSingle(
2436 Value *OperationReplacement, CompositeNode *Node) {
2437 auto *Real = cast<Instruction>(Val: Node->Vals[0].Real);
2438 auto *OldPHI = ReductionInfo[Real].first;
2439 auto *NewPHI = OldToNewPHI[OldPHI];
2440 auto *VTy = cast<VectorType>(Val: Real->getType());
2441 auto *NewVTy = VectorType::getDoubleElementsVectorType(VTy);
2442
2443 Value *Init = OldPHI->getIncomingValueForBlock(BB: Incoming);
2444
2445 IRBuilder<> Builder(Incoming->getTerminator());
2446
2447 Value *NewInit = nullptr;
2448 if (auto *C = dyn_cast<Constant>(Val: Init)) {
2449 if (C->isNullValue())
2450 NewInit = Constant::getNullValue(Ty: NewVTy);
2451 }
2452
2453 if (!NewInit)
2454 NewInit =
2455 Builder.CreateVectorInterleave(Ops: {Init, Constant::getNullValue(Ty: VTy)});
2456
2457 NewPHI->addIncoming(V: NewInit, BB: Incoming);
2458 NewPHI->addIncoming(V: OperationReplacement, BB: BackEdge);
2459
2460 auto *FinalReduction = ReductionInfo[Real].second;
2461 Builder.SetInsertPoint(&*FinalReduction->getParent()->getFirstInsertionPt());
2462
2463 auto *AddReduce = Builder.CreateAddReduce(Src: OperationReplacement);
2464 FinalReduction->replaceAllUsesWith(V: AddReduce);
2465}
2466
2467void ComplexDeinterleavingGraph::processReductionOperation(
2468 Value *OperationReplacement, CompositeNode *Node) {
2469 auto *Real = cast<Instruction>(Val: Node->Vals[0].Real);
2470 auto *Imag = cast<Instruction>(Val: Node->Vals[0].Imag);
2471 auto *OldPHIReal = ReductionInfo[Real].first;
2472 auto *OldPHIImag = ReductionInfo[Imag].first;
2473 auto *NewPHI = OldToNewPHI[OldPHIReal];
2474
2475 // We have to interleave initial origin values coming from IncomingBlock
2476 Value *InitReal = OldPHIReal->getIncomingValueForBlock(BB: Incoming);
2477 Value *InitImag = OldPHIImag->getIncomingValueForBlock(BB: Incoming);
2478
2479 IRBuilder<> Builder(Incoming->getTerminator());
2480 auto *NewInit = Builder.CreateVectorInterleave(Ops: {InitReal, InitImag});
2481
2482 NewPHI->addIncoming(V: NewInit, BB: Incoming);
2483 NewPHI->addIncoming(V: OperationReplacement, BB: BackEdge);
2484
2485 // Deinterleave complex vector outside of loop so that it can be finally
2486 // reduced
2487 auto *FinalReductionReal = ReductionInfo[Real].second;
2488 auto *FinalReductionImag = ReductionInfo[Imag].second;
2489
2490 auto *Br = cast<CondBrInst>(Val: BackEdge->getTerminator());
2491 BasicBlock *ExitBB = Br->getSuccessor(i: Br->getSuccessor(i: 0) == BackEdge);
2492 Builder.SetInsertPoint(&*ExitBB->getFirstInsertionPt());
2493
2494 auto *Deinterleave = Builder.CreateIntrinsic(ID: Intrinsic::vector_deinterleave2,
2495 OverloadTypes: OperationReplacement->getType(),
2496 Args: OperationReplacement);
2497
2498 auto *NewReal = Builder.CreateExtractValue(Agg: Deinterleave, Idxs: (uint64_t)0);
2499 FinalReductionReal->replaceUsesOfWith(From: Real, To: NewReal);
2500
2501 Builder.SetInsertPoint(FinalReductionImag);
2502 auto *NewImag = Builder.CreateExtractValue(Agg: Deinterleave, Idxs: 1);
2503 FinalReductionImag->replaceUsesOfWith(From: Imag, To: NewImag);
2504}
2505
2506void ComplexDeinterleavingGraph::replaceNodes() {
2507 SmallVector<Instruction *, 16> DeadInstrRoots;
2508 for (auto *RootInstruction : OrderedRoots) {
2509 // Check if this potential root went through check process and we can
2510 // deinterleave it
2511 if (!RootToNode.count(Val: RootInstruction))
2512 continue;
2513
2514 IRBuilder<> Builder(RootInstruction);
2515 auto RootNode = RootToNode[RootInstruction];
2516 Value *R = replaceNode(Builder, Node: RootNode);
2517
2518 if (RootNode->Operation ==
2519 ComplexDeinterleavingOperation::ReductionOperation) {
2520 auto *RootReal = cast<Instruction>(Val: RootNode->Vals[0].Real);
2521 auto *RootImag = cast<Instruction>(Val: RootNode->Vals[0].Imag);
2522 ReductionInfo[RootReal].first->removeIncomingValue(BB: BackEdge);
2523 ReductionInfo[RootImag].first->removeIncomingValue(BB: BackEdge);
2524 DeadInstrRoots.push_back(Elt: RootReal);
2525 DeadInstrRoots.push_back(Elt: RootImag);
2526 } else if (RootNode->Operation ==
2527 ComplexDeinterleavingOperation::ReductionSingle) {
2528 auto *RootInst = cast<Instruction>(Val: RootNode->Vals[0].Real);
2529 auto &Info = ReductionInfo[RootInst];
2530 Info.first->removeIncomingValue(BB: BackEdge);
2531 DeadInstrRoots.push_back(Elt: Info.second);
2532 } else {
2533 assert(R && "Unable to find replacement for RootInstruction");
2534 DeadInstrRoots.push_back(Elt: RootInstruction);
2535 RootInstruction->replaceAllUsesWith(V: R);
2536 }
2537 }
2538
2539 for (auto *I : DeadInstrRoots)
2540 RecursivelyDeleteTriviallyDeadInstructions(V: I, TLI);
2541}
2542