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