119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===-- PHIEliminationUtils.cpp - Helper functions for PHI elimination ----===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "PHIEliminationUtils.h" 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineBasicBlock.h" 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineFunction.h" 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineRegisterInfo.h" 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/SmallPtrSet.h" 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanusing namespace llvm; 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// findCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// when following the CFG edge to SuccMBB. This needs to be after any def of 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// SrcReg, but before any subsequent point where control flow might jump out of 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// the basic block. 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanMachineBasicBlock::iterator 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanllvm::findPHICopyInsertPoint(MachineBasicBlock* MBB, MachineBasicBlock* SuccMBB, 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned SrcReg) { 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Handle the trivial case trivially. 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MBB->empty()) 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return MBB->begin(); 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Usually, we just want to insert the copy before the first terminator 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // instruction. However, for the edge going to a landing pad, we must insert 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the copy before the call/invoke instruction. 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!SuccMBB->isLandingPad()) 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return MBB->getFirstTerminator(); 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Discover any defs/uses in this basic block. 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<MachineInstr*, 8> DefUsesInMBB; 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineRegisterInfo& MRI = MBB->getParent()->getRegInfo(); 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(SrcReg), 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RE = MRI.reg_end(); RI != RE; ++RI) { 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr* DefUseMI = &*RI; 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DefUseMI->getParent() == MBB) 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DefUsesInMBB.insert(DefUseMI); 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock::iterator InsertPoint; 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DefUsesInMBB.empty()) { 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // No defs. Insert the copy at the start of the basic block. 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InsertPoint = MBB->begin(); 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (DefUsesInMBB.size() == 1) { 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Insert the copy immediately after the def/use. 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InsertPoint = *DefUsesInMBB.begin(); 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++InsertPoint; 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Insert the copy immediately after the last def/use. 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InsertPoint = MBB->end(); 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!DefUsesInMBB.count(&*--InsertPoint)) {} 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++InsertPoint; 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make sure the copy goes after any phi nodes however. 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return MBB->SkipPHIsAndLabels(InsertPoint); 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 62