SSAUpdater: Add mode when Phi creation is not allowed

[skatkov]

Summary

Add one more parameter to SSAUpdater to disable PHI node creation.
SSAUpdater will find a Phi node if it exists but will return undef value if
new Phi node should be created.

By default the behavior is not changed. Phi nodes can be created.

I need this patch for implementation of PR26223.

[efriedma]

include/llvm/Transforms/Utils/SSAUpdaterImpl.h

97

This is bad: the caller has no way to tell what happened if you return undef (is the value actually undef at the given point, or did PHI construction fail?).

[• dberlin]

I need this patch for implementation of PR26223.

Can you share more details, looking at that bug, i do not understand why this mode would be needed, at all.

I also don't see the point in using ssaupdater if it doesn't allow phi node creation.
In such a situation, all the answers are pre-determined and don't require the updater at all.

[skatkov]

Hi Daniel, I plan to upload the patch for PR26233 this week. I'd like to think a bit more about relation of recursion and the patch I have - whether it works correctly and whether SSAUpdater work correctly with this pattern.

For now, shortly, the idea of future patch is as follows: in CodeGenPrepare::OptimizeMemoryInst I'd like to collect all cases where address computation is identical but base might be different. So to sink address computation to memory instruction I need to find a common Phi node for all bases which can be used in BB where memory instruction is located. For that purpose I'd like to use SSAUpdater. However it is possible that Phi node for bases may not exists (for example if there is no further uses of base it can be removed).

It is not clear that creation of new Phi node is profitable with respect to folding of address computation to memory instruction.
I'd like to add an option which allows/disallows creation of Phi nodes. For that I need this patch.

SSAUpdater is able to correctly answer to the question: if I know the different values in different basic blocks is there any merge of these values in BB I'm interested in. In general it is not so easy and straightforward in complex CFG.

I also can just use SSAUpdater as is and after that remove the created Phi nodes if needed but this approach seems better to me.

I hope it answers why I'd like to use this utility in the mode when I need only to check whether there is a Phi node merging all my values.

include/llvm/Transforms/Utils/SSAUpdaterImpl.h

97

I see. Is nullptr better?

[• dberlin]

In D35474#812370, @skatkov wrote:

Hi Daniel, I plan to upload the patch for PR26233 this week. I'd like to think a bit more about relation of recursion and the patch I have - whether it works correctly and whether SSAUpdater work correctly with this pattern.

For now, shortly, the idea of future patch is as follows: in CodeGenPrepare::OptimizeMemoryInst I'd like to collect all cases where address computation is identical but base might be different. So to sink address computation to memory instruction I need to find a common Phi node for all bases which can be used in BB where memory instruction is located. For that purpose I'd like to use SSAUpdater. However it is possible that Phi node for bases may not exists (for example if there is no further uses of base it can be removed).

Please don't use SSA updater for this.
This is trivial to do without it., and SSAUpdater can't do it any faster than you can.

It is not clear that creation of new Phi node is profitable with respect to folding of address computation to memory instruction.
I'd like to add an option which allows/disallows creation of Phi nodes. For that I need this patch.

I'm really strongly opposed to doing it for this use case.

SSAUpdater is able to correctly answer to the question: if I know the different values in different basic blocks is there any merge of these values in BB I'm interested in. In general it is not so easy and straightforward in complex CFG.

I strongly disagree.
The algorithm is < 100 lines of code.
SSAUpdater is not going to perform any magic here.

The algorithm you are looking for is a simple walking algorithm that looks like this (taken from a paper i can give you if you like).

(The code below supports tracking multiple variables at once, you could remove unsigned Var if you only ever are trying one at a time)

CurrentDef is a map from std::pair{varnum, bb} to a definition of varnum in BB.
Fill it in with your existing values.

void writeVariable(unsigned Var, BasicBlock *BB, Value *V) {
  CurrentDef[{Var, BB}] = V;
}
Value *GetExistingVariableOrCreate(unsigned Var, BasicBlock *BB) {
  auto CDI = CurrentDefs.find({Var, BB});
  if (CDI != CurrentDefs.end())
    return CDI->second;
  return GetVariableInBlock(Var, BB);
}
Value *GetVariableInBlock(unsigned int VarNum, BasicBlock *BB)
{
  Value *Result;

  // Single predecessor case, just recurse
  if (BasicBlock *Pred = BB->getSinglePredecessor()) {
    Result = GetVariableInBlock(Var, Pred);
  } else if (VisitedBlocks.count({Var, BB})) {
    // We hit our node again, meaning we had a cycle, we must insert a phi
    // node to break it.
   Result = Create an empty phi we'll fill in later.
    {Search for PHI Node here, you need one, if you don't find one, you need a phi but don't have one}
  } else {
    // Mark us visited so we can detect a cycle
    VisitedBlocks.insert({Var, BB});
    SmallVector<Value *, 8> PHIOps;

    // Recurse to get the values in our predecessors. This will look for phi nodes if we cycle.
    for (auto *Pred : predecessors(BB))
      PHIOps.push_back(GetVariableInBlock(Var, Pred));
      Result = {Search for PHI that has PHIOps in BB}

 writeVariable(Var, BB, Result);
 return Result;
}

Using the current SSAUpdater to do this will compute dominance frontiers, etc, all which is a complete waste of time for you.
You are just trying to see if there are merge blocks that values reach.

The above is one way of doing it (by walking up).

If you are only concerned about existing phis, you can also just look at the uses.

[skatkov]

Hi Daniel,
thank you much for a hint. I'm looking into this direction right now.

Side question: what is a primary goal for SSAUpdater then?

[• dberlin]

SSA Updater exists to perform SSA Updates for complicated cases (I also have a patch out to rewrite it, because it's super-slow. The algorithm i gave you is a variant of that patch. See https://reviews.llvm.org/D28934).

Most algorithms in LLVM are pretty straightforward to update, but things like "copying a loop and then unrolling + vectorizing it", may be difficult.

SSAUpdater can perform the updating for these cases. You give it a set of existing values, and tell it what block you are trying to place a new value in, and it will insert the right set of phi nodes.

You are using it as an available value finder, which it's not really meant for, and there are much faster ways of doing.

Without seeing your patch, i would expect you could just look at the uses of your defs to see if a phi node exists that meets your specifications.
But if you have to understand what such a phi node would look like, the algorithm i gave should do it.

In any case, SSAUpdater is really not the right mechanism to go find what phis match a certain set of values.
:)

[skatkov]

Thanks :)

[skatkov]

Hi Daniel,

I've come up with the following implementation basing on your idea: https://reviews.llvm.org/D36073

Please take into account that finally I realized that I could not use SSAUpdater API because it is possible that I can observe the base instruction in the same BB but the difference might be in the path I can get it.
Simple example:
p1 = b1 + 40
p2 = b2 + 40
p = p1
if (cond) p = p2
v = *(p)

So I have p1 and p2 in the same basic block, so I cannot say to SSA update that I saw b1 and b2 in the same basic block to get the right phi node merging b1 and b2.
I hope the right implementation may b found in D36073

include/llvm/Transforms/Utils/SSAUpdater.h

private:
 
   /// PHI nodes are given a name based on ProtoName.
   std::string ProtoName;
 
   /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to
   /// the vector.
   SmallVectorImpl<PHINode*> *InsertedPHIs;
 
+  /// False if we should not create new Phis but only find an existing.
+  bool AllowPhiCreation;
+
 public:
   /// If InsertedPHIs is specified, it will be filled
   /// in with all PHI Nodes created by rewriting.
   explicit SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = nullptr);
   SSAUpdater(const SSAUpdater &) = delete;
   SSAUpdater &operator=(const SSAUpdater &) = delete;
   ~SSAUpdater();
 
   /// \brief Reset this object to get ready for a new set of SSA updates with
   /// type 'Ty'.
   ///
   /// PHI nodes get a name based on 'Name'.
   void Initialize(Type *Ty, StringRef Name);
 
+  /// \brief Sets whether we are allowed creation new Phi node.
+  void SetAllowPhiCreation(bool Val) { AllowPhiCreation = Val; }
+
   /// \brief Indicate that a rewritten value is available in the specified block
   /// with the specified value.
   void AddAvailableValue(BasicBlock *BB, Value *V);
 
   /// \brief Return true if the SSAUpdater already has a value for the specified
   /// block.
   bool HasValueForBlock(BasicBlock *BB) const;
 

include/llvm/Transforms/Utils/SSAUpdaterImpl.h

private:
   AvailableValsTy *AvailableVals;
 
   SmallVectorImpl<PhiT*> *InsertedPHIs;
 
   typedef SmallVectorImpl<BBInfo*> BlockListTy;
   typedef DenseMap<BlkT*, BBInfo*> BBMapTy;
   BBMapTy BBMap;
   BumpPtrAllocator Allocator;
+  bool AllowPhiCreation;
 
 public:
   explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
-                          SmallVectorImpl<PhiT*> *Ins) :
-    Updater(U), AvailableVals(A), InsertedPHIs(Ins) { }
+                          SmallVectorImpl<PhiT *> *Ins, bool APC = true)
+      : Updater(U), AvailableVals(A), InsertedPHIs(Ins), AllowPhiCreation(APC) {
+  }
 
   /// GetValue - Check to see if AvailableVals has an entry for the specified
   /// BB and if so, return it.  If not, construct SSA form by first
   /// calculating the required placement of PHIs and then inserting new PHIs
   /// where needed.
   ValT GetValue(BlkT *BB) {
     SmallVector<BBInfo*, 100> BlockList;
     BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
 
     // Special case: bail out if BB is unreachable.
     if (BlockList.size() == 0) {
       ValT V = Traits::GetUndefVal(BB, Updater);
       (*AvailableVals)[BB] = V;
       return V;
     }
 
     FindDominators(&BlockList, PseudoEntry);
     FindPHIPlacement(&BlockList);
-    FindAvailableVals(&BlockList);
+    if (!FindAvailableVals(&BlockList))
+      return Traits::GetUndefVal(BB, Updater);
 
     return BBMap[BB]->DefBB->AvailableVal;
   }
 
+private:
   /// BuildBlockList - Starting from the specified basic block, traverse back
   /// through its predecessors until reaching blocks with known values.
   /// Create BBInfo structures for the blocks and append them to the block
   /// list.
   BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
     SmallVector<BBInfo*, 10> RootList;
     SmallVector<BBInfo*, 64> WorkList;
 
void FindPHIPlacement(BlockListTy *BlockList) {
     } while (Changed);
   }
 
   /// FindAvailableVal - If this block requires a PHI, first check if an
   /// existing PHI matches the PHI placement and reaching definitions computed
   /// earlier, and if not, create a new PHI.  Visit all the block's
   /// predecessors to calculate the available value for each one and fill in
   /// the incoming values for a new PHI.
-  void FindAvailableVals(BlockListTy *BlockList) {
+  /// Return false if new Phi creation is required but we are not allowed to do
+  /// that.
+  bool FindAvailableVals(BlockListTy *BlockList) {
     // Go through the worklist in forward order (i.e., backward through the CFG)
     // and check if existing PHIs can be used.  If not, create empty PHIs where
     // they are needed.
     for (typename BlockListTy::iterator I = BlockList->begin(),
            E = BlockList->end(); I != E; ++I) {
       BBInfo *Info = *I;
       // Check if there needs to be a PHI in BB.
       if (Info->DefBB != Info)
         continue;
 
       // Look for an existing PHI.
       FindExistingPHI(Info->BB, BlockList);
       if (Info->AvailableVal)
         continue;
 
+      // If we are not allowed to create a new Phi then bail out.
+      if (!AllowPhiCreation)
+        return false;
+
       ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
       Info->AvailableVal = PHI;
       (*AvailableVals)[Info->BB] = PHI;
     }
 
     // Now go back through the worklist in reverse order to fill in the
     // arguments for any new PHIs added in the forward traversal.
     for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
         Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
       }
 
       DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");
 
       // If the client wants to know about all new instructions, tell it.
       if (InsertedPHIs) InsertedPHIs->push_back(PHI);
     }
+    return true;
   }
 
   /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
   /// them match what is needed.
   void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
     for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end();
          BBI != BBE; ++BBI) {
       PhiT *SomePHI = Traits::InstrIsPHI(&*BBI);

lib/Transforms/Utils/SSAUpdater.cpp

 
 #define DEBUG_TYPE "ssaupdater"
 
 typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
 static AvailableValsTy &getAvailableVals(void *AV) {
   return *static_cast<AvailableValsTy*>(AV);
 }
 
-SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI)
-  : InsertedPHIs(NewPHI) {}
+SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode *> *NewPHI)
+    : InsertedPHIs(NewPHI), AllowPhiCreation(true) {}
 
 SSAUpdater::~SSAUpdater() {
   delete static_cast<AvailableValsTy*>(AV);
 }
 
 void SSAUpdater::Initialize(Type *Ty, StringRef Name) {
   if (!AV)
     AV = new AvailableValsTy();
if (isa<PHINode>(BB->begin())) {
     PHINode *SomePHI;
     for (BasicBlock::iterator It = BB->begin();
          (SomePHI = dyn_cast<PHINode>(It)); ++It) {
       if (IsEquivalentPHI(SomePHI, ValueMapping))
         return SomePHI;
     }
   }
 
+  if (!AllowPhiCreation)
+    return UndefValue::get(ProtoType);
+
   // Ok, we have no way out, insert a new one now.
   PHINode *InsertedPHI = PHINode::Create(ProtoType, PredValues.size(),
                                          ProtoName, &BB->front());
 
   // Fill in all the predecessors of the PHI.
   for (const auto &PredValue : PredValues)
     InsertedPHI->addIncoming(PredValue.second, PredValue.first);
 

 /// Check to see if AvailableVals has an entry for the specified BB and if so,
 /// return it.  If not, construct SSA form by first calculating the required
 /// placement of PHIs and then inserting new PHIs where needed.
 Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
   AvailableValsTy &AvailableVals = getAvailableVals(AV);
   if (Value *V = AvailableVals[BB])
     return V;
 
-  SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
+  SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs,
+                                  AllowPhiCreation);
   return Impl.GetValue(BB);
 }
 
 //===----------------------------------------------------------------------===//
 // LoadAndStorePromoter Implementation
 //===----------------------------------------------------------------------===//
 
 LoadAndStorePromoter::