1//===-- PHIEliminationUtils.cpp - Helper functions for PHI elimination ----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "PHIEliminationUtils.h"
10#include "llvm/ADT/SmallPtrSet.h"
11#include "llvm/CodeGen/MachineBasicBlock.h"
12#include "llvm/CodeGen/MachineFunction.h"
13#include "llvm/CodeGen/MachineRegisterInfo.h"
14using namespace llvm;
15
16// findCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg
17// when following the CFG edge to SuccMBB. This needs to be after any def of
18// SrcReg, but before any subsequent point where control flow might jump out of
19// the basic block.
20MachineBasicBlock::iterator
21llvm::findPHICopyInsertPoint(MachineBasicBlock* MBB, MachineBasicBlock* SuccMBB,
22                             unsigned SrcReg) {
23  // Handle the trivial case trivially.
24  if (MBB->empty())
25    return MBB->begin();
26
27  // Usually, we just want to insert the copy before the first terminator
28  // instruction. However, for the edge going to a landing pad, we must insert
29  // the copy before the call/invoke instruction.
30  if (!SuccMBB->isEHPad())
31    return MBB->getFirstTerminator();
32
33  // Discover any defs/uses in this basic block.
34  SmallPtrSet<MachineInstr*, 8> DefUsesInMBB;
35  MachineRegisterInfo& MRI = MBB->getParent()->getRegInfo();
36  for (MachineInstr &RI : MRI.reg_instructions(SrcReg)) {
37    if (RI.getParent() == MBB)
38      DefUsesInMBB.insert(&RI);
39  }
40
41  MachineBasicBlock::iterator InsertPoint;
42  if (DefUsesInMBB.empty()) {
43    // No defs.  Insert the copy at the start of the basic block.
44    InsertPoint = MBB->begin();
45  } else if (DefUsesInMBB.size() == 1) {
46    // Insert the copy immediately after the def/use.
47    InsertPoint = *DefUsesInMBB.begin();
48    ++InsertPoint;
49  } else {
50    // Insert the copy immediately after the last def/use.
51    InsertPoint = MBB->end();
52    while (!DefUsesInMBB.count(&*--InsertPoint)) {}
53    ++InsertPoint;
54  }
55
56  // Make sure the copy goes after any phi nodes but before
57  // any debug nodes.
58  return MBB->SkipPHIsAndLabels(InsertPoint);
59}
60