contrib/llvm/lib/CodeGen/PHIEliminationUtils.cpp

   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
  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 (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(SrcReg),
  38          RE = MRI.reg_end(); RI != RE; ++RI) {
  39     MachineInstr* DefUseMI = &*RI;
  40     if (DefUseMI->getParent() == MBB)
  41       DefUsesInMBB.insert(DefUseMI);
  42   }
  43
  44   MachineBasicBlock::iterator InsertPoint;
  45   if (DefUsesInMBB.empty()) {
  46     // No defs.  Insert the copy at the start of the basic block.
  47     InsertPoint = MBB->begin();
  48   } else if (DefUsesInMBB.size() == 1) {
  49     // Insert the copy immediately after the def/use.
  50     InsertPoint = *DefUsesInMBB.begin();
  51     ++InsertPoint;
  52   } else {
  53     // Insert the copy immediately after the last def/use.
  54     InsertPoint = MBB->end();
  55     while (!DefUsesInMBB.count(&*--InsertPoint)) {}
  56     ++InsertPoint;
  57   }
  58
  59   // Make sure the copy goes after any phi nodes however.
  60   return MBB->SkipPHIsAndLabels(InsertPoint);
  61 }