[MachineSSAUpdater] compile time improvement in GetValueInMiddleOfBlock

[skatkov]

Summary

GetValueInMiddleOfBlock uses result of GetValueAtEndOfBlockInternal if there is no value
defined for current basic block.

If there is already a value it tries (in this order):

• to find single register coming from all predecessors
• find existing phi node which matches our incoming registers
• build new phi.

The compile time improvement is to use current available value if
it is defined out of current BB or it is a PHI register.
This is due to it can be used in the middle basic block.

[skatkov]

ping

[skatkov]

ping.

[sameerds]

Looks straightforward enough to me. If the value is a PHI, it must be at the beginning of the current block. If it is outside this block, then whoever registered it is confident that it dominates this block. Is it correct that the SSAUpdater will not end up in a state where it tries to use a phi to produce another phi in the same block? Because that might race against the assumption that the used phi is available earlier in the block.

[sameerds]

Same typo in the change description, last paragraph ... middle "of" the block.

llvm/lib/CodeGen/MachineSSAUpdater.cpp

156–157

middle "of" the block?

llvm/lib/Transforms/Utils/SSAUpdater.cpp

104

middle "of" the block?

[skatkov]

In D126523#3580887, @sameerds wrote:

Looks straightforward enough to me. If the value is a PHI, it must be at the beginning of the current block. If it is outside this block, then whoever registered it is confident that it dominates this block. Is it correct that the SSAUpdater will not end up in a state where it tries to use a phi to produce another phi in the same block? Because that might race against the assumption that the used phi is available earlier in the block.

That is my understanding. As I see GetValueInMiddleOfBlock is not used anywhere to build new phi, its result is not saved to any internal structures, so I do not change anything as I see.

[skatkov]

Comments updated.

llvm/lib/CodeGen/MachineSSAUpdater.cpp

 /// merge the appropriate values, and this value isn't live out of the block.
 Register MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB,
                                                     bool ExistingValueOnly) {
   // If there is no definition of the renamed variable in this block, just use
   // GetValueAtEndOfBlock to do our work.
   if (!HasValueForBlock(BB))
     return GetValueAtEndOfBlockInternal(BB, ExistingValueOnly);
 
+  // Ok, we have already got a value for this block. If it is out of our block
+  // or it is a phi - we can re-use it as it will be defined in the middle of
+  // block as well.
+  Register defR = getAvailableVals(AV).lookup(BB);
+  if (auto I = MRI->getVRegDef(defR))
+    if (I->isPHI() || I->getParent() != BB)
+      return defR;
+
   // If there are no predecessors, just return undef.
   if (BB->pred_empty()) {
     // If we cannot insert new instructions, just return $noreg.
     if (ExistingValueOnly)
       return Register();
     // Insert an implicit_def to represent an undef value.
     MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
                                         BB, BB->getFirstTerminator(),

llvm/lib/Transforms/Utils/SSAUpdater.cpp

 }
 
 Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
   // If there is no definition of the renamed variable in this block, just use
   // GetValueAtEndOfBlock to do our work.
   if (!HasValueForBlock(BB))
     return GetValueAtEndOfBlock(BB);
 
+  // Ok, we have already got a value for this block. If it is out of our block
+  // or it is a phi - we can re-use it as it will be defined in the middle of
+  // block as well.
+  Value *defV = FindValueForBlock(BB);
+  if (auto I = dyn_cast<Instruction>(defV))
+    if (isa<PHINode>(I) || I->getParent() != BB)
+      return defV;
+
   // Otherwise, we have the hard case.  Get the live-in values for each
   // predecessor.
   SmallVector<std::pair<BasicBlock *, Value *>, 8> PredValues;
   Value *SingularValue = nullptr;
 
   // We can get our predecessor info by walking the pred_iterator list, but it
   // is relatively slow.  If we already have PHI nodes in this block, walk one
   // of them to get the predecessor list instead.