LLVM API Documentation
00001 //===-- lib/CodeGen/PHIElimination.h ----------------------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 00010 #ifndef LLVM_CODEGEN_PHIELIMINATION_HPP 00011 #define LLVM_CODEGEN_PHIELIMINATION_HPP 00012 00013 #include "llvm/ADT/DenseMap.h" 00014 #include "llvm/ADT/SmallSet.h" 00015 #include "llvm/ADT/SmallPtrSet.h" 00016 #include "llvm/CodeGen/MachineFunctionPass.h" 00017 #include "llvm/Target/TargetInstrInfo.h" 00018 00019 #include <map> 00020 00021 namespace llvm { 00022 00023 /// Lower PHI instructions to copies. 00024 class PHIElimination : public MachineFunctionPass { 00025 MachineRegisterInfo *MRI; // Machine register information 00026 private: 00027 00028 typedef SmallSet<MachineBasicBlock*, 4> PHIKillList; 00029 typedef DenseMap<unsigned, PHIKillList> PHIKillMap; 00030 typedef DenseMap<unsigned, MachineBasicBlock*> PHIDefMap; 00031 00032 public: 00033 00034 typedef PHIKillList::iterator phi_kill_iterator; 00035 typedef PHIKillList::const_iterator const_phi_kill_iterator; 00036 00037 static char ID; // Pass identification, replacement for typeid 00038 PHIElimination() : MachineFunctionPass(&ID) {} 00039 00040 virtual bool runOnMachineFunction(MachineFunction &Fn); 00041 00042 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00043 00044 /// Return true if the given vreg was defined by a PHI intsr prior to 00045 /// lowering. 00046 bool hasPHIDef(unsigned vreg) const { 00047 return PHIDefs.count(vreg); 00048 } 00049 00050 /// Returns the block in which the PHI instruction which defined the 00051 /// given vreg used to reside. 00052 MachineBasicBlock* getPHIDefBlock(unsigned vreg) { 00053 PHIDefMap::iterator phiDefItr = PHIDefs.find(vreg); 00054 assert(phiDefItr != PHIDefs.end() && "vreg has no phi-def."); 00055 return phiDefItr->second; 00056 } 00057 00058 /// Returns true if the given vreg was killed by a PHI instr. 00059 bool hasPHIKills(unsigned vreg) const { 00060 return PHIKills.count(vreg); 00061 } 00062 00063 /// Returns an iterator over the BasicBlocks which contained PHI 00064 /// kills of this register prior to lowering. 00065 phi_kill_iterator phiKillsBegin(unsigned vreg) { 00066 PHIKillMap::iterator phiKillItr = PHIKills.find(vreg); 00067 assert(phiKillItr != PHIKills.end() && "vreg has no phi-kills."); 00068 return phiKillItr->second.begin(); 00069 } 00070 phi_kill_iterator phiKillsEnd(unsigned vreg) { 00071 PHIKillMap::iterator phiKillItr = PHIKills.find(vreg); 00072 assert(phiKillItr != PHIKills.end() && "vreg has no phi-kills."); 00073 return phiKillItr->second.end(); 00074 } 00075 00076 private: 00077 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 00078 /// in predecessor basic blocks. 00079 /// 00080 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 00081 void LowerAtomicPHINode(MachineBasicBlock &MBB, 00082 MachineBasicBlock::iterator AfterPHIsIt); 00083 00084 /// analyzePHINodes - Gather information about the PHI nodes in 00085 /// here. In particular, we want to map the number of uses of a virtual 00086 /// register which is used in a PHI node. We map that to the BB the 00087 /// vreg is coming from. This is used later to determine when the vreg 00088 /// is killed in the BB. 00089 /// 00090 void analyzePHINodes(const MachineFunction& Fn); 00091 00092 // FindCopyInsertPoint - Find a safe place in MBB to insert a copy from 00093 // SrcReg. This needs to be after any def or uses of SrcReg, but before 00094 // any subsequent point where control flow might jump out of the basic 00095 // block. 00096 MachineBasicBlock::iterator FindCopyInsertPoint(MachineBasicBlock &MBB, 00097 unsigned SrcReg); 00098 00099 // SkipPHIsAndLabels - Copies need to be inserted after phi nodes and 00100 // also after any exception handling labels: in landing pads execution 00101 // starts at the label, so any copies placed before it won't be executed! 00102 MachineBasicBlock::iterator SkipPHIsAndLabels(MachineBasicBlock &MBB, 00103 MachineBasicBlock::iterator I) { 00104 // Rather than assuming that EH labels come before other kinds of labels, 00105 // just skip all labels. 00106 while (I != MBB.end() && 00107 (I->getOpcode() == TargetInstrInfo::PHI || I->isLabel())) 00108 ++I; 00109 return I; 00110 } 00111 00112 typedef std::pair<const MachineBasicBlock*, unsigned> BBVRegPair; 00113 typedef std::map<BBVRegPair, unsigned> VRegPHIUse; 00114 00115 VRegPHIUse VRegPHIUseCount; 00116 PHIDefMap PHIDefs; 00117 PHIKillMap PHIKills; 00118 00119 // Defs of PHI sources which are implicit_def. 00120 SmallPtrSet<MachineInstr*, 4> ImpDefs; 00121 }; 00122 00123 } 00124 00125 #endif /* PHIELIMINATION_H */