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"
15 using 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.
21 MachineBasicBlock::iterator
findPHICopyInsertPoint(MachineBasicBlock * MBB,MachineBasicBlock * SuccMBB,unsigned SrcReg)22 llvm::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