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