Repository: llvm/llvm-project
File: llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp (C++)

Code before:
void ComplexDeinterleavingGraph::processReductionOperation(
    Value *OperationReplacement, CompositeNode *Node) {
  auto *Real = cast<Instruction>(Node->Vals[0].Real);
  auto *Imag = cast<Instruction>(Node->Vals[0].Imag);
  auto *OldPHIReal = ReductionInfo[Real].first;
  auto *OldPHIImag = ReductionInfo[Imag].first;
  auto *NewPHI = OldToNewPHI[OldPHIReal];

  // We have to interleave initial origin values coming from IncomingBlock
  Value *InitReal = OldPHIReal->getIncomingValueForBlock(Incoming);
  Value *InitImag = OldPHIImag->getIncomingValueForBlock(Incoming);

  IRBuilder<> Builder(Incoming->getTerminator());
  auto *NewInit = Builder.CreateVectorInterleave({InitReal, InitImag});

  NewPHI->addIncoming(NewInit, Incoming);
  NewPHI->addIncoming(OperationReplacement, BackEdge);

  // Deinterleave complex vector outside of loop so that it can be finally
  // reduced
  auto *FinalReductionReal = ReductionInfo[Real].second;
  auto *FinalReductionImag = ReductionInfo[Imag].second;

  BasicBlock *InsertBB = FinalReductionReal->getParent();
  if (FinalReductionImag->getParent() != InsertBB) {
    DominatorTree DT(*Real->getFunction());
    if (BasicBlock *DomBB = DT.findNearestCommonDominator(
            FinalReductionReal->getParent(), FinalReductionImag->getParent()))
      InsertBB = DomBB;
  }

  // Ensure we place the deinterleave after it's source
  Instruction *InsertPt = &*InsertBB->getFirstInsertionPt();
  if (auto *OpInst = dyn_cast<Instruction>(OperationReplacement)) {
    if (OpInst->getParent() == InsertBB && !isa<PHINode>(OpInst)) {
      if (Instruction *Next = OpInst->getNextNode())
        InsertPt = Next;
      else
        InsertPt = InsertBB->getTerminator();
    }
  }
  Builder.SetInsertPoint(InsertPt);

  auto *Deinterleave = Builder.CreateIntrinsic(Intrinsic::vector_deinterleave2,
                                               OperationReplacement->getType(),
                                               OperationReplacement);

  auto *NewReal = Builder.CreateExtractValue(Deinterleave, (uint64_t)0);
  FinalReductionReal->replaceUsesOfWith(Real, NewReal);

  Builder.SetInsertPoint(FinalReductionImag);

Review comment (performance):
Calling DP is quite expensive. May be let's just put deinterleave2 into the exit block? Something like this:

```
  auto *Br = cast<BranchInst>(BackEdge->getTerminator());
  BasicBlock *ExitBB = Br->getSuccessor(Br->getSuccessor(0) == BackEdge);
  Builder.SetInsertPoint(&*ExitBB->getFirstInsertionPt());
```

Code after:
    Value *OperationReplacement, CompositeNode *Node) {
  auto *Real = cast<Instruction>(Node->Vals[0].Real);
  auto *Imag = cast<Instruction>(Node->Vals[0].Imag);
  auto *OldPHIReal = ReductionInfo[Real].first;
  auto *OldPHIImag = ReductionInfo[Imag].first;
  auto *NewPHI = OldToNewPHI[OldPHIReal];

  // We have to interleave initial origin values coming from IncomingBlock
  Value *InitReal = OldPHIReal->getIncomingValueForBlock(Incoming);
  Value *InitImag = OldPHIImag->getIncomingValueForBlock(Incoming);

  IRBuilder<> Builder(Incoming->getTerminator());
  auto *NewInit = Builder.CreateVectorInterleave({InitReal, InitImag});

  NewPHI->addIncoming(NewInit, Incoming);
  NewPHI->addIncoming(OperationReplacement, BackEdge);

  // Deinterleave complex vector outside of loop so that it can be finally
  // reduced
  auto *FinalReductionReal = ReductionInfo[Real].second;
  auto *FinalReductionImag = ReductionInfo[Imag].second;

  auto *Br = cast<BranchInst>(BackEdge->getTerminator());
  BasicBlock *ExitBB = Br->getSuccessor(Br->getSuccessor(0) == BackEdge);
  Builder.SetInsertPoint(&*ExitBB->getFirstInsertionPt());

  auto *Deinterleave = Builder.CreateIntrinsic(Intrinsic::vector_deinterleave2,
                                               OperationReplacement->getType(),
                                               OperationReplacement);

  auto *NewReal = Builder.CreateExtractValue(Deinterleave, (uint64_t)0);
  FinalReductionReal->replaceUsesOfWith(Real, NewReal);

  Builder.SetInsertPoint(FinalReductionImag);
  auto *NewImag = Builder.CreateExtractValue(Deinterleave, 1);
  FinalReductionImag->replaceUsesOfWith(Imag, NewImag);
}

void ComplexDeinterleavingGraph::replaceNodes() {
  SmallVector<Instruction *, 16> DeadInstrRoots;
  for (auto *RootInstruction : OrderedRoots) {
    // Check if this potential root went through check process and we can
    // deinterleave it
    if (!RootToNode.count(RootInstruction))
      continue;

    IRBuilder<> Builder(RootInstruction);
    auto RootNode = RootToNode[RootInstruction];
    Value *R = replaceNode(Builder, RootNode);

    if (RootNode->Operation ==