Introducing VPPHINode

[npanchen]

Summary

[VPlan] Added VPPHINode class that is constructed and used to represent phi-nodes.

Detailed description:
Current representation of phi-nodes in VPlan completely depends on underlying IR, which means that any VPlan xform has to generate PHINode instruction that contradicts to VPlan's philosophy "Don't generate any IR instruction before decision is taken."

In this patch VPPHINode is constructed for phi-nodes and underlying IR is still used in CG.
In a next patch CG will be fixed so that it will not use underlying IR.

[rengolin]

Hi Nikolay,

For what you describe, the patch looks good, ie. create a VPPHIInst. But it doesn't clearly show the benefits of doing so.

I can imagine that it would simplify reasoning and, as you say, avoid creating temporary instructions if not needed, but it would be good to have an example to base that claim.

Do you have the next patch somewhere? Would be good to put it in Phab, so we could look at it and make this review easier.

Thanks!
--renato

lib/Transforms/Vectorize/LoopVectorizationPlanner.h

142

If you need Inst to be a PHI (or null), then maybe adding an assert would help, here.

[npanchen]

In D53355#1270077, @rengolin wrote:

Hi Nikolay,

For what you describe, the patch looks good, ie. create a VPPHIInst. But it doesn't clearly show the benefits of doing so.

I can imagine that it would simplify reasoning and, as you say, avoid creating temporary instructions if not needed, but it would be good to have an example to base that claim.

Do you have the next patch somewhere? Would be good to put it in Phab, so we could look at it and make this review easier.

Thanks!
--renato

Hi Renato,

Sorry for this long reply. As Satish has pointed out in his review, this VPPHINode will be used to generate blending.

[rengolin]

In D53355#1366988, @npanchen wrote:

Sorry for this long reply. As Satish has pointed out in his review, this VPPHINode will be used to generate blending.

Right, that review has been approved. Once it lands, we should look into this patch and the one that will make use of it as a unit.

It can still remain as two separate patches, but by the looks of it, the next patch is not prepared to upstream yet, which means it can still have changes.

It would be good to see both patches, and with real tests on the second, to make sure the changes here are final.

thanks!
--renato

[fhahn]

@npanchen are you still looking into pushing this patch? If that's the case, it would be great if you could rebase it and share the follow-up that uses the new node. Also, please upload the patch with full context.

Marking as requested changes to clear up review queue.

lib/Transforms/Vectorize/LoopVectorizationPlanner.h

     return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS});
   }
 
+  VPInstruction *createPhiInstruction(Instruction *Inst = nullptr) {
+    VPInstruction *NewVPInst = new VPPHINode();
+    NewVPInst->setUnderlyingValue(Inst);
+    if (BB)
+      BB->insert(NewVPInst, InsertPt);
+    return NewVPInst;
+  }
+
   //===--------------------------------------------------------------------===//
   // RAII helpers.
   //===--------------------------------------------------------------------===//

lib/Transforms/Vectorize/VPlan.h

   void print(raw_ostream &O, const Twine &Indent) const override;
 };
 
+/// Concrete class for PHI instruction.
+class VPPHINode : public VPInstruction {
+private:
+  SmallVector<VPBasicBlock *, 2> VPBBUsers;
+
+public:
+  using vpblock_iterator = SmallVectorImpl<VPBasicBlock *>::iterator;
+  using const_vpblock_iterator =
+      SmallVectorImpl<VPBasicBlock *>::const_iterator;
+
+  explicit VPPHINode(void) : VPInstruction(Instruction::PHI,
+                                           ArrayRef<VPValue *>()) {}
+
+  vpblock_iterator block_begin(void) { return VPBBUsers.begin(); }
+
+  vpblock_iterator block_end(void) { return VPBBUsers.end(); }
+
+  const_vpblock_iterator block_begin(void) const {
+    return VPBBUsers.begin();
+  }
+
+  const_vpblock_iterator block_end(void) const {
+    return VPBBUsers.end();
+  }
+
+  iterator_range<vpblock_iterator> blocks(void) {
+    return make_range(block_begin(), block_end());
+  }
+
+  iterator_range<const_vpblock_iterator> blocks(void) const {
+    return make_range(block_begin(), block_end());
+  }
+
+  operand_range incoming_values(void) { return operands(); }
+  const_operand_range incoming_values(void) const { return operands(); }
+
+  /// Return number of incoming values.
+  unsigned getNumIncomingValues(void) const { return getNumOperands(); }
+
+  /// Return VPValue that corresponds to Idx'th incomming VPBasicBlock.
+  VPValue *getIncomingValue(const unsigned Idx) const { return getOperand(Idx); }
+
+  /// Return VPValue that corresponds to incomming VPBB.
+  VPValue *getIncomingValue(const VPBasicBlock *VPBB) const {
+    auto Idx = getBlockIndexOrNone(VPBB);
+    assert(Idx && "Cannot find value for a given BB.");
+    return getIncomingValue(Idx.getValue());
+  }
+
+  /// Add an incoming value to the end of the PHI list
+  void addIncoming(VPValue *Value, VPBasicBlock *Block) {
+    assert(Value && "Value must not be null.");
+    assert(Block && "Block must not be null.");
+    addOperand(Value);
+    VPBBUsers.push_back(Block);
+  }
+
+  /// Return incoming basic block number \p Idx.
+  VPBasicBlock *getIncomingBlock(const unsigned Idx) const {
+    return VPBBUsers[Idx];
+  }
+
+  /// Return index for a given \p Block.
+  int getBlockIndex(const VPBasicBlock *Block) const {
+    auto It = llvm::find(make_range(block_begin(), block_end()), Block);
+    if (It != block_end())
+      return std::distance(block_begin(), It);
+    return -1;
+  }
+
+  /// Return Optional index for a given basic block \p Block.
+  Optional<unsigned> getBlockIndexOrNone(const VPBasicBlock *Block) const {
+    int Idx = getBlockIndex(Block);
+    return Idx != -1 ? Optional<unsigned>(Idx) : None;
+  }
+
+  /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPInstruction *V) {
+    return V->getOpcode() == Instruction::PHI;
+  }
+
+  /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return isa<VPInstruction>(V) && classof(cast<VPInstruction>(V));
+  }
+
+  /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPRecipeBase *V) {
+    return isa<VPInstruction>(V) && classof(cast<VPInstruction>(V));
+  }
+};
+
 /// A recipe for handling all phi nodes except for integer and FP inductions.
 class VPWidenPHIRecipe : public VPRecipeBase {
 private:

lib/Transforms/Vectorize/VPlan.cpp

     O << Instruction::getOpcodeName(getOpcode());
   }
 
-  for (const VPValue *Operand : operands()) {
-    O << " ";
-    Operand->printAsOperand(O);
+  if (auto *Phi = dyn_cast<const VPPHINode>(this)) {
+    auto PrintValueWithBB = [&](const unsigned I) {
+      O << " ";
+      O << " [ ";
+      Phi->getIncomingValue(I)->printAsOperand(O);
+      O << ", ";
+      O << Phi->getIncomingBlock(I)->getName();
+      O << " ]";
+    };
+    const unsigned Size = Phi->getNumIncomingValues();
+    for (unsigned I = 0; I < Size - 1; ++I) {
+      PrintValueWithBB(I);
+      O << ",";
+    }
+    PrintValueWithBB(Size-1);
   }
+  else
+    for (const VPValue *Operand : operands()) {
+      O << " ";
+      Operand->printAsOperand(O);
+    }
 }
 
 /// Generate the code inside the body of the vectorized loop. Assumes a single

lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

   for (auto *Phi : PhisToFix) {
     assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");
     VPValue *VPVal = IRDef2VPValue[Phi];
-    assert(isa<VPInstruction>(VPVal) && "Expected VPInstruction for phi node.");
-    auto *VPPhi = cast<VPInstruction>(VPVal);
+    assert(isa<VPPHINode>(VPVal) && "Expected VPPHINode for phi node.");
+    auto *VPPhi = cast<VPPHINode>(VPVal);
     assert(VPPhi->getNumOperands() == 0 &&
-           "Expected VPInstruction with no operands.");
+           "Expected VPPHINode with no operands.");
 
-    for (Value *Op : Phi->operands())
-      VPPhi->addOperand(getOrCreateVPOperand(Op));
+    for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I)
+      VPPhi->addIncoming(getOrCreateVPOperand(Phi->getIncomingValue(I)),
+                         getOrCreateVPBB(Phi->getIncomingBlock(I)));
   }
 }
 

       // Phi node's operands may have not been visited at this point. We create
       // an empty VPInstruction that we will fix once the whole plain CFG has
       // been built.
-      NewVPInst = cast<VPInstruction>(VPIRBuilder.createNaryOp(
-          Inst->getOpcode(), {} /*No operands*/, Inst));
+      NewVPInst = cast<VPInstruction>(VPIRBuilder.createPhiInstruction(Inst));
       PhisToFix.push_back(Phi);
     } else {
       // Translate LLVM-IR operands into VPValue operands and set them in the

unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

   auto Plan = buildHCFG(LoopHeader);
 
   VPBasicBlock *Entry = Plan->getEntry()->getEntryBasicBlock();
-  EXPECT_NE(nullptr, Entry->getSingleSuccessor());
+  EXPECT_TRUE(Entry->getSingleSuccessor());
   EXPECT_EQ(0u, Entry->getNumPredecessors());
   EXPECT_EQ(1u, Entry->getNumSuccessors());
   EXPECT_EQ(nullptr, Entry->getCondBit());

   EXPECT_EQ(2u, VecBB->getNumSuccessors());
 
   auto Iter = VecBB->begin();
-  VPInstruction *Phi = dyn_cast<VPInstruction>(&*Iter++);
-  EXPECT_EQ(Instruction::PHI, Phi->getOpcode());
+  auto *Phi = dyn_cast<VPPHINode>(&*Iter++);
+  EXPECT_TRUE(Phi);
 
   VPInstruction *Idx = dyn_cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::GetElementPtr, Idx->getOpcode());

                                                  DeadInstructions);
 
   VPBlockBase *Entry = Plan->getEntry()->getEntryBasicBlock();
-  EXPECT_NE(nullptr, Entry->getSingleSuccessor());
+  EXPECT_TRUE(Entry->getSingleSuccessor());
   EXPECT_EQ(0u, Entry->getNumPredecessors());
   EXPECT_EQ(1u, Entry->getNumSuccessors());
 

 
   auto Iter = VecBB->begin();
   auto *Phi = dyn_cast<VPWidenPHIRecipe>(&*Iter++);
-  EXPECT_NE(nullptr, Phi);
+  EXPECT_TRUE(Phi);
 
   auto *Idx = dyn_cast<VPWidenRecipe>(&*Iter++);
-  EXPECT_NE(nullptr, Idx);
+  EXPECT_TRUE(Idx);
 
   auto *Load = dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++);
-  EXPECT_NE(nullptr, Load);
+  EXPECT_TRUE(Load);
 
   auto *Add = dyn_cast<VPWidenRecipe>(&*Iter++);
-  EXPECT_NE(nullptr, Add);
+  EXPECT_TRUE(Add);
 
   auto *Store = dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++);
-  EXPECT_NE(nullptr, Store);
+  EXPECT_TRUE(Store);
 
   auto *LastWiden = dyn_cast<VPWidenRecipe>(&*Iter++);
-  EXPECT_NE(nullptr, LastWiden);
+  EXPECT_TRUE(LastWiden);
   EXPECT_EQ(VecBB->end(), Iter);
 }