1218885Sdim//===-- PHIEliminationUtils.cpp - Helper functions for PHI elimination ----===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim 10218885Sdim#include "PHIEliminationUtils.h" 11249423Sdim#include "llvm/ADT/SmallPtrSet.h" 12218885Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 13218885Sdim#include "llvm/CodeGen/MachineFunction.h" 14218885Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 15218885Sdimusing namespace llvm; 16218885Sdim 17218885Sdim// findCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg 18218885Sdim// when following the CFG edge to SuccMBB. This needs to be after any def of 19218885Sdim// SrcReg, but before any subsequent point where control flow might jump out of 20218885Sdim// the basic block. 21218885SdimMachineBasicBlock::iterator 22218885Sdimllvm::findPHICopyInsertPoint(MachineBasicBlock* MBB, MachineBasicBlock* SuccMBB, 23218885Sdim unsigned SrcReg) { 24218885Sdim // Handle the trivial case trivially. 25218885Sdim if (MBB->empty()) 26218885Sdim return MBB->begin(); 27218885Sdim 28218885Sdim // Usually, we just want to insert the copy before the first terminator 29218885Sdim // instruction. However, for the edge going to a landing pad, we must insert 30218885Sdim // the copy before the call/invoke instruction. 31218885Sdim if (!SuccMBB->isLandingPad()) 32218885Sdim return MBB->getFirstTerminator(); 33218885Sdim 34218885Sdim // Discover any defs/uses in this basic block. 35218885Sdim SmallPtrSet<MachineInstr*, 8> DefUsesInMBB; 36218885Sdim MachineRegisterInfo& MRI = MBB->getParent()->getRegInfo(); 37218885Sdim for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(SrcReg), 38218885Sdim RE = MRI.reg_end(); RI != RE; ++RI) { 39218885Sdim MachineInstr* DefUseMI = &*RI; 40218885Sdim if (DefUseMI->getParent() == MBB) 41218885Sdim DefUsesInMBB.insert(DefUseMI); 42218885Sdim } 43218885Sdim 44218885Sdim MachineBasicBlock::iterator InsertPoint; 45218885Sdim if (DefUsesInMBB.empty()) { 46218885Sdim // No defs. Insert the copy at the start of the basic block. 47218885Sdim InsertPoint = MBB->begin(); 48218885Sdim } else if (DefUsesInMBB.size() == 1) { 49218885Sdim // Insert the copy immediately after the def/use. 50218885Sdim InsertPoint = *DefUsesInMBB.begin(); 51218885Sdim ++InsertPoint; 52218885Sdim } else { 53218885Sdim // Insert the copy immediately after the last def/use. 54218885Sdim InsertPoint = MBB->end(); 55218885Sdim while (!DefUsesInMBB.count(&*--InsertPoint)) {} 56218885Sdim ++InsertPoint; 57218885Sdim } 58218885Sdim 59218885Sdim // Make sure the copy goes after any phi nodes however. 60218885Sdim return MBB->SkipPHIsAndLabels(InsertPoint); 61218885Sdim} 62