1 //===-- lib/CodeGen/PHIElimination.h ----------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_CODEGEN_PHIELIMINATION_HPP
11 #define LLVM_CODEGEN_PHIELIMINATION_HPP
13 #include "llvm/ADT/DenseMap.h"
14 #include "llvm/ADT/SmallSet.h"
15 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/CodeGen/MachineFunctionPass.h"
17 #include "llvm/Target/TargetInstrInfo.h"
23 /// Lower PHI instructions to copies.
24 class PHIElimination : public MachineFunctionPass {
25 MachineRegisterInfo *MRI; // Machine register information
28 typedef SmallSet<MachineBasicBlock*, 4> PHIKillList;
29 typedef DenseMap<unsigned, PHIKillList> PHIKillMap;
30 typedef DenseMap<unsigned, MachineBasicBlock*> PHIDefMap;
34 typedef PHIKillList::iterator phi_kill_iterator;
35 typedef PHIKillList::const_iterator const_phi_kill_iterator;
37 static char ID; // Pass identification, replacement for typeid
38 PHIElimination() : MachineFunctionPass(&ID) {}
40 virtual bool runOnMachineFunction(MachineFunction &Fn);
42 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
44 /// Return true if the given vreg was defined by a PHI intsr prior to
46 bool hasPHIDef(unsigned vreg) const {
47 return PHIDefs.count(vreg);
50 /// Returns the block in which the PHI instruction which defined the
51 /// given vreg used to reside.
52 MachineBasicBlock* getPHIDefBlock(unsigned vreg) {
53 PHIDefMap::iterator phiDefItr = PHIDefs.find(vreg);
54 assert(phiDefItr != PHIDefs.end() && "vreg has no phi-def.");
55 return phiDefItr->second;
58 /// Returns true if the given vreg was killed by a PHI instr.
59 bool hasPHIKills(unsigned vreg) const {
60 return PHIKills.count(vreg);
63 /// Returns an iterator over the BasicBlocks which contained PHI
64 /// kills of this register prior to lowering.
65 phi_kill_iterator phiKillsBegin(unsigned vreg) {
66 PHIKillMap::iterator phiKillItr = PHIKills.find(vreg);
67 assert(phiKillItr != PHIKills.end() && "vreg has no phi-kills.");
68 return phiKillItr->second.begin();
70 phi_kill_iterator phiKillsEnd(unsigned vreg) {
71 PHIKillMap::iterator phiKillItr = PHIKills.find(vreg);
72 assert(phiKillItr != PHIKills.end() && "vreg has no phi-kills.");
73 return phiKillItr->second.end();
77 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
78 /// in predecessor basic blocks.
80 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
81 void LowerAtomicPHINode(MachineBasicBlock &MBB,
82 MachineBasicBlock::iterator AfterPHIsIt);
84 /// analyzePHINodes - Gather information about the PHI nodes in
85 /// here. In particular, we want to map the number of uses of a virtual
86 /// register which is used in a PHI node. We map that to the BB the
87 /// vreg is coming from. This is used later to determine when the vreg
88 /// is killed in the BB.
90 void analyzePHINodes(const MachineFunction& Fn);
92 /// Split critical edges where necessary for good coalescer performance.
93 bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB);
95 /// isLiveOut - Determine if Reg is live out from MBB, when not
96 /// considering PHI nodes. This means that Reg is either killed by
97 /// a successor block or passed through one.
98 bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB,
101 /// isLiveIn - Determine if Reg is live in to MBB, not considering PHI
102 /// source registers. This means that Reg is either killed by MBB or passes
104 bool isLiveIn(unsigned Reg, const MachineBasicBlock &MBB,
107 /// SplitCriticalEdge - Split a critical edge from A to B by
108 /// inserting a new MBB. Update branches in A and PHI instructions
109 /// in B. Return the new block.
110 MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *A,
111 MachineBasicBlock *B);
113 /// FindCopyInsertPoint - Find a safe place in MBB to insert a copy from
114 /// SrcReg when following the CFG edge to SuccMBB. This needs to be after
115 /// any def of SrcReg, but before any subsequent point where control flow
116 /// might jump out of the basic block.
117 MachineBasicBlock::iterator FindCopyInsertPoint(MachineBasicBlock &MBB,
118 MachineBasicBlock &SuccMBB,
121 // SkipPHIsAndLabels - Copies need to be inserted after phi nodes and
122 // also after any exception handling labels: in landing pads execution
123 // starts at the label, so any copies placed before it won't be executed!
124 MachineBasicBlock::iterator SkipPHIsAndLabels(MachineBasicBlock &MBB,
125 MachineBasicBlock::iterator I) {
126 // Rather than assuming that EH labels come before other kinds of labels,
127 // just skip all labels.
128 while (I != MBB.end() &&
129 (I->getOpcode() == TargetInstrInfo::PHI || I->isLabel()))
134 typedef std::pair<const MachineBasicBlock*, unsigned> BBVRegPair;
135 typedef std::map<BBVRegPair, unsigned> VRegPHIUse;
137 VRegPHIUse VRegPHIUseCount;
141 // Defs of PHI sources which are implicit_def.
142 SmallPtrSet<MachineInstr*, 4> ImpDefs;
147 #endif /* LLVM_CODEGEN_PHIELIMINATION_HPP */