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

章明 via llvm-dev llvm-dev at lists.llvm.org
Mon Nov 13 18:58:23 PST 2017

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 &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); } }

More information about the llvm-dev mailing list