LLVM API Documentation

PHIElimination.h

Go to the documentation of this file.
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 */