[llvm-dev] Update control flow graph when splitting a machine basic block?

[章明 via llvm-dev]

> It looks like what's happening is that IfConversion makes the return 
> conditional, then that gets merged with the following block.  I mean, I 
> would say it's a bug in that there's a "terminator" in a position not at 
> the end of the block, but a return doesn't have any CFG successors, so 
> I'm not sure it has any practical effect.
> 
> I think we won't merge with the following block for an indirect branch 
> which is not a return.

I believe MachineBasicBlock::getFirstTerminator, MachineBasicBlock::getFirstInstrTerminator, and
Methods/functions that use these methods will break on a machine basic block like this,
although I have not tested these with such a machine basic block. I don't know whether
MachineBasicBlock::getFirstTerminator and MachineBasicBlock::getFirstInstrTerminator are 
intended to be used in a late stage like just before code emission or not.

I am trying to circumvent this issue by splitting machine basic blocks, s.t. if
a machine basic block contains a terminator, only terminators or non-real instructions
like DBG_VALUE may come after the first terminator. This would probably also involve
updating the CFG. I'm trying to update the CFG by inspecting targets of terminators, but
I am not sure whether this approach is viable. My code for updating the CFG after splitting
a machine basic block is as follows. I intend to run the code before ARMConstantIslands.
Could you please give me some advice? Thank you!

// This function assumes the successors of the old machine basic
// block are correct. If the target of a terminator in a new machine basic
// block is not a successor of the old machine basic block, the target is not
// treated as a successor of the new machine basic block. If a successor of the
// old machine basic block is not the target of any of the terminators in the
// new machine basic blocks, the successor of the old machine basic block is
// conservatively treated as a common successor of all the new machine basic
// blocks.

// MBBBefore: New machine basic block before the split point.
// MBBAfter: New machine basic block after the split point.
// Successors: Successors of the old machine basic block.
// MF: Machine function that contains the new machine basic blocks and the
//     successors of the old machine basic block.

void UpdateCFG(MachineBasicBlock &MBBBefore,
               MachineBasicBlock &MBBAfter,
               std::unordered_set<MachineBasicBlock *> &Successors,
               MachineFunction &MF) {
  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
  assert(TII && "The target instruction information must not be a null pointer.");
  const MachineJumpTableInfo *MJTI = MF.getJumpTableInfo();
  assert(MJTI && "The machine jump table information must not be a null pointer.");
  const std::vector<MachineJumpTableEntry> &JumpTables = MJTI->getJumpTables();
  SmallVector<MachineBasicBlock *, 2> MBBs = {&MBBBefore, &MBBAfter};
  std::unordered_set<MachineBasicBlock *> RemainingSuccessors = Successors;

  for (auto MBB : MBBs) {
    assert(MBB && "A new machine basic block cannot be a null pointer.");
    // Remove all successors from the new machine basic block.
    for (auto SuccI = MBB->succ_begin(), SuccE = MBB->succ_end();
         SuccI != SuccE;
         SuccI++)
      MBB->removeSuccessor(SuccI);
    bool MayFallthrough = true;
    // Iterate over all terminators of the new machine basic block.
    // Note: MachineBasicBlock::getFirstTerminator and
    // MachineBasicBlock::getFirstInstrTerminator seem to assume that every
    // machine instructions after the first terminator is either a terminator or
    // a debug instruction. This assumption does not always hold.
    // We do not use MachineBasicBlock::terminators here, because it depends on
    // MachineBasicBlock::getFirstTerminator.
    for (auto MI = MBB->begin(), MIE = MBB->end(); MI != MIE; MI++) {
      if (!MI->isTerminator())
        continue;
      // Determine the target of the terminator.
      // We search for operands that are machine basic blocks or jump table
      // indices.
      // Returns and indirect branches are ignored, since their targets are not
      // machine basic blocks.
      for (auto Op = MI->operands_begin(), OpE = MI->operands_end();
           Op != OpE;
           Op++) {
// FIXME: Could a machine basic block operand of a terminator not be the target of the terminator?
// FIXME: Could a terminator other than jump table have more than one targets?
        if (Op->isMBB()) {
          // The operand is a machine basic block.
          MachineBasicBlock *Target = Op->getMBB();
          // If the possible target of the terminator is a successor of the old
          // machine basic block, or if the terminator is in the new machine
          // basic block before the split point and the operand is the new
          // machine basic block after the split point, then treat the target of
          // the terminator as a successor of the new basic block and remove it
          // from the remaining successors.
          if (Successors.count(Target) ||
              (MBB == &MBBBefore && Target == &MBBAfter)) {
            MBB->addSuccessor(Target);
            RemainingSuccessors.erase(Target);
          }
        }
        if (Op->isJTI()) {
          // The operand is a jump table index.
          unsigned JTI = Op->getIndex();
          assert(JTI < JumpTables.size() &&
                 "The jump table index is out-of-range.");
          const MachineJumpTableEntry &JT = JumpTables[JTI];
          for (MachineBasicBlock *Target : JT.MBBs) {
            // If the possible target of the terminator is a successor of the
            // old machine basic block, then treat it as a successor of the new
            // basic block and remove it from the remaining successors.
            if (Successors.count(Target)) {
              MBB->addSuccessor(Target);
              RemainingSuccessors.erase(Target);
            }
          }
        }
      }
      // If the terminator is an unconditional control flow barrier, then the
      // machine basic block cannot fall through to its layout successor, and
      // instructions after it cannot be executed.
// FIXME: Is this a correct way to determine whether an machine instruction may fall through?
      if (MI->isBarrier() && !TII->isPredicated(*MI)) {
        MayFallthrough = false;
        break;
      }
    }
    // If the new machine basic block may fall through to its layout successor,
    // then treat the layout successor as a successor of the new machine basic
    // block.
    if (MayFallthrough) {
      MachineFunction::iterator LayoutSuccessor = std::next(MBB->getIterator());
      if (LayoutSuccessor != MF.end()) {
        if ((MBB == &MBBBefore && &*LayoutSuccessor == &MBBAfter) ||
            (MBB == &MBBAfter && Successors.count(&*LayoutSuccessor))) {
          MBB->addSuccessor(&*LayoutSuccessor);
          RemainingSuccessors.erase(&*LayoutSuccessor);
        }
      }
    }
  }
  // Treat the remaining successors, i.e., successors of the old machine basic
  // block that are not found to be targets of terminators in the new machine
  // basic blocks, as common successors of all the new machine basic blocks.
  for (auto MBB : MBBs) {
    for (auto Succ : RemainingSuccessors)
      MBB->addSuccessor(Succ);
  }
}