[IR] Add Instruction::getInsertionPointAfterDef()

[nikic]

Summary

Transforms occasionally want to insert an instruction directly after the definition point of a value. This involves quite a few different edge cases, e.g. for phi nodes the next insertion point is not the next instruction, and for invokes and callbrs its not even in the next block. Additionally, the insertion point may not exist at all if catchswitch is involved.

We currently reimplement this logic in a few places, and usually get it wrong in one way or another. I've added two tests to demonstrate issues.

This adds a general Instruction::getInsertionPointAfterDef() API to reuse the (hopefully correct) logic.

[nikic]

llvm/lib/Transforms/Coroutines/CoroFrame.cpp

2647

I'm wondering if it makes sense to move this API to Value instead, to handle this case as well. It's needed here and in the InstCombine freeze transform.

[reames]

llvm/lib/IR/Instruction.cpp

135

Please add a comment explaining this case. It's non obvious, and without your wording about catchswitch in the commit message, I'd not have figured this out.

Structure wise, I think I'd prefer:
if (phi node) {
} else if (terminator) {

if (invoke) {}
else if (callbr) {}
else { assert(catchswitch) }

} else {
}

Not a strong preference, so please treat that as a suggestion, nothing more.

[barannikov88]

llvm/lib/Transforms/Coroutines/CoroFrame.cpp

2647

There are other Values apart from Argument and Instruction for which the term "point [within a basic block] after the value is defined" does not make sense (e.g. Constant), . It of course could be asserted, but still, Value seems too low-level and too fundamental class for this kind of interface.
I'm not even sure the Instruction is a good place for this method either. The method always returns a location within some basic block, so putting this method into a BasicBlock might seem like a good idea. However, the method should be made static, which would just overload the class with rarely used method with no real benefit.
Considering all of this, I would suggest to turn this method into a standalone utility function with a template argument which is statically asserted to be an Instruction or an Argument.
llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h might be a good place.

Excuse my English

[barannikov88]

llvm/lib/Transforms/Coroutines/CoroFrame.cpp

2647

or llvm/include/llvm/Transforms/Utils/Local.h or ...

[nikic]

llvm/lib/Transforms/Coroutines/CoroFrame.cpp

2647

The variant on Value would accept a Function *, which would allow handling constants as well (for them, the insertion point is the same as for arguments: the start of the function).

I don't think this has any particular relation to basic blocks, so adding to BasicBlock or BasicBlockUtils does not seem appropriate to me.

[barannikov88]

llvm/lib/Transforms/Coroutines/CoroFrame.cpp

2647

Well, polluting Value with an interface which is used in exactly four places it not a solution either. That's why I'm suggesting to make this a standalone function, not a member of any particular class. Where to put it is a separate question, but since it is used in transformation passes it may make sense to put it somewhere under include/llvm/Transforms/.
Please consider my comments as a suggestion only.

[nikic]

Additional comments and assertions.

[nikic]

llvm/lib/IR/Instruction.cpp

135

I've kept the general code structure, but added an assertion that no terminators fall through to the last cast, so we notice if additional value-returning terminators are introduced.

[nikic]

Ping

[reames]

I would strongly prefer to see this split into a NFC change (even if that means preserving a bug), and functional changes to fix each bug in turn.

In fact, LGTM if you want to land the API with a non-functional change user. But only in that case.

I sort of wonder if we could handle the Argument case by having this be a utility on Function, but we can explore that in a future revision if that patterns turns out to be common.

llvm/include/llvm/IR/Instruction.h

157

Can you change this to getInsertionPointAfterDef? That reads more clearly to me.

llvm/lib/Transforms/Coroutines/CoroFrame.cpp

2648

I think you should assert InsertPt here. Otherwise, we have to figure out what to do with DVI in the catch switch case which the existing code didn't handle.

[efriedma]

llvm/lib/IR/Instruction.cpp

131

I think for CallBrInst, we're considering modifying the dominance rules to allow the produced value to be used in all destinations? In which case there wouldn't be one unique location after the definition.

[nickdesaulniers]

llvm/lib/IR/Instruction.cpp

131

I think for CallBrInst, we're considering modifying the dominance rules to allow the produced value to be used in all destinations?

Yes; GCC implemented asm goto w/ outputs this way; we should update our implementation, too. @morbo and I were just discussing this on Tuesday.

https://github.com/llvm/llvm-project/issues/53562

131

@void I meant.

[nikic]

This would have prevented D132105...

llvm/lib/IR/Instruction.cpp

131

But shouldn't we still implement the current semantics for now? Allowing callbr result to be used on all successors will need more changes, in particular to dominance.

[reames]

llvm/lib/IR/Instruction.cpp

131

Agreed. In particular, my LGTM still stands with this concern raised.

[nikic]

Rename method and rebase patch.

[nikic]

llvm/lib/Transforms/Coroutines/CoroFrame.cpp

2648

I believe this code just performs the move for cosmetic reasons (dbg.declare is not control dependent, it does not matter where in the function it occurs) -- so I think just doing nothing if no insertion point is found would be the right thing to do here (though I have no idea whether this can occur in practice in the context where this function is used).

llvm/include/llvm/IR/Instruction.h

public:
 
   /// Given an instruction Other in the same basic block as this instruction,
   /// return true if this instruction comes before Other. In this worst case,
   /// this takes linear time in the number of instructions in the block. The
   /// results are cached, so in common cases when the block remains unmodified,
   /// it takes constant time.
   bool comesBefore(const Instruction *Other) const;
 
+  /// Get the first insertion point at which the result of this instruction
+  /// is defined. This is *not* the directly following instruction in a number
+  /// of cases, e.g. phi nodes or terminators that return values. This function
+  /// may return null if the insertion after the definition is not possible,
+  /// e.g. due to a catchswitch terminator.
+  Instruction *getInsertionPointAfterDef();
+
   //===--------------------------------------------------------------------===//
   // Subclass classification.
   //===--------------------------------------------------------------------===//
 
   /// Returns a member of one of the enums like Instruction::Add.
   unsigned getOpcode() const { return getValueID() - InstructionVal; }
 
   const char *getOpcodeName() const { return getOpcodeName(getOpcode()); }

llvm/lib/IR/Instruction.cpp

bool Instruction::comesBefore(const Instruction *Other) const {
   assert(Parent && Other->Parent &&
          "instructions without BB parents have no order");
   assert(Parent == Other->Parent && "cross-BB instruction order comparison");
   if (!Parent->isInstrOrderValid())
     Parent->renumberInstructions();
   return Order < Other->Order;
 }
 
+Instruction *Instruction::getInsertionPointAfterDef() {
+  assert(!getType()->isVoidTy() && "Instruction must define result");
+  BasicBlock *InsertBB;
+  BasicBlock::iterator InsertPt;
+  if (auto *PN = dyn_cast<PHINode>(this)) {
+    InsertBB = PN->getParent();
+    InsertPt = InsertBB->getFirstInsertionPt();
+  } else if (auto *II = dyn_cast<InvokeInst>(this)) {
+    InsertBB = II->getNormalDest();
+    InsertPt = InsertBB->getFirstInsertionPt();
+  } else if (auto *CB = dyn_cast<CallBrInst>(this)) {
+    InsertBB = CB->getDefaultDest();
+    InsertPt = InsertBB->getFirstInsertionPt();
+  } else {
+    assert(!isTerminator() && "Only invoke/callbr terminators return value");
+    InsertBB = getParent();
+    InsertPt = std::next(getIterator());
+  }
+
+  // catchswitch blocks don't have any legal insertion point (because they
+  // are both an exception pad and a terminator).
+  if (InsertPt == InsertBB->end())
+    return nullptr;
+  return &*InsertPt;
+}
+
 bool Instruction::isOnlyUserOfAnyOperand() {
   return any_of(operands(), [](Value *V) { return V->hasOneUser(); });
 }
 
 void Instruction::setHasNoUnsignedWrap(bool b) {
   cast<OverflowingBinaryOperator>(this)->setHasNoUnsignedWrap(b);
 }
 

llvm/lib/Transforms/Coroutines/CoroFrame.cpp

if (!OptimizeFrame)
     }
 
   DVI->replaceVariableLocationOp(OriginalStorage, Storage);
   DVI->setExpression(Expr);
   // We only hoist dbg.declare today since it doesn't make sense to hoist
   // dbg.value or dbg.addr since they do not have the same function wide
   // guarantees that dbg.declare does.
   if (!isa<DbgValueInst>(DVI) && !isa<DbgAddrIntrinsic>(DVI)) {
-    if (auto *II = dyn_cast<InvokeInst>(Storage))
-      DVI->moveBefore(II->getNormalDest()->getFirstNonPHI());
-    else if (auto *CBI = dyn_cast<CallBrInst>(Storage))
-      DVI->moveBefore(CBI->getDefaultDest()->getFirstNonPHI());
-    else if (auto *InsertPt = dyn_cast<Instruction>(Storage)) {
-      assert(!InsertPt->isTerminator() &&
-             "Unimaged terminator that could return a storage.");
-      DVI->moveAfter(InsertPt);
-    } else if (isa<Argument>(Storage))
-      DVI->moveAfter(F->getEntryBlock().getFirstNonPHI());
+    Instruction *InsertPt = nullptr;
+    if (auto *I = dyn_cast<Instruction>(Storage))
+      InsertPt = I->getInsertionPointAfterDef();
+    else if (isa<Argument>(Storage))
+      InsertPt = &*F->getEntryBlock().begin();
+    if (InsertPt)
+      DVI->moveBefore(InsertPt);
   }
 }
 
 void coro::buildCoroutineFrame(Function &F, Shape &Shape) {
   // Don't eliminate swifterror in async functions that won't be split.
   if (Shape.ABI != coro::ABI::Async || !Shape.CoroSuspends.empty())
     eliminateSwiftError(F, Shape);
 

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

bool InstCombinerImpl::transformConstExprCastCall(CallBase &Call) {
   // Insert a cast of the return type as necessary.
   Instruction *NC = NewCall;
   Value *NV = NC;
   if (OldRetTy != NV->getType() && !Caller->use_empty()) {
     if (!NV->getType()->isVoidTy()) {
       NV = NC = CastInst::CreateBitOrPointerCast(NC, OldRetTy);
       NC->setDebugLoc(Caller->getDebugLoc());
 
-      // If this is an invoke/callbr instruction, we should insert it after the
-      // first non-phi instruction in the normal successor block.
-      if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
-        BasicBlock::iterator I = II->getNormalDest()->getFirstInsertionPt();
-        InsertNewInstBefore(NC, *I);
-      } else if (CallBrInst *CBI = dyn_cast<CallBrInst>(Caller)) {
-        BasicBlock::iterator I = CBI->getDefaultDest()->getFirstInsertionPt();
-        InsertNewInstBefore(NC, *I);
-      } else {
-        // Otherwise, it's a call, just insert cast right after the call.
-        InsertNewInstBefore(NC, *Caller);
-      }
+      Instruction *InsertPt = NewCall->getInsertionPointAfterDef();
+      assert(InsertPt && "No place to insert cast");
+      InsertNewInstBefore(NC, *InsertPt);
       Worklist.pushUsersToWorkList(*Caller);
     } else {
       NV = PoisonValue::get(Caller->getType());
     }
   }
 
   if (!Caller->use_empty())
     replaceInstUsesWith(*Caller, NV);