1 //===-- OptimizePHIs.cpp - Optimize machine instruction PHIs --------------===//
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 // This pass optimizes machine instruction PHIs to take advantage of
11 // opportunities created during DAG legalization.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "phi-opt"
16 #include "llvm/CodeGen/Passes.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/MachineInstr.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/Target/TargetInstrInfo.h"
21 #include "llvm/Function.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/Statistic.h"
26 STATISTIC(NumPHICycles, "Number of PHI cycles replaced");
27 STATISTIC(NumDeadPHICycles, "Number of dead PHI cycles");
30 class OptimizePHIs : public MachineFunctionPass {
31 MachineRegisterInfo *MRI;
32 const TargetInstrInfo *TII;
35 static char ID; // Pass identification
36 OptimizePHIs() : MachineFunctionPass(&ID) {}
38 virtual bool runOnMachineFunction(MachineFunction &MF);
40 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
42 MachineFunctionPass::getAnalysisUsage(AU);
46 typedef SmallPtrSet<MachineInstr*, 16> InstrSet;
47 typedef SmallPtrSetIterator<MachineInstr*> InstrSetIterator;
49 bool IsSingleValuePHICycle(MachineInstr *MI, unsigned &SingleValReg,
50 InstrSet &PHIsInCycle);
51 bool IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle);
52 bool OptimizeBB(MachineBasicBlock &MBB);
56 char OptimizePHIs::ID = 0;
57 static RegisterPass<OptimizePHIs>
58 X("opt-phis", "Optimize machine instruction PHIs");
60 FunctionPass *llvm::createOptimizePHIsPass() { return new OptimizePHIs(); }
62 bool OptimizePHIs::runOnMachineFunction(MachineFunction &Fn) {
63 MRI = &Fn.getRegInfo();
64 TII = Fn.getTarget().getInstrInfo();
66 // Find dead PHI cycles and PHI cycles that can be replaced by a single
67 // value. InstCombine does these optimizations, but DAG legalization may
68 // introduce new opportunities, e.g., when i64 values are split up for
71 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
72 Changed |= OptimizeBB(*I);
77 /// IsSingleValuePHICycle - Check if MI is a PHI where all the source operands
78 /// are copies of SingleValReg, possibly via copies through other PHIs. If
79 /// SingleValReg is zero on entry, it is set to the register with the single
80 /// non-copy value. PHIsInCycle is a set used to keep track of the PHIs that
81 /// have been scanned.
82 bool OptimizePHIs::IsSingleValuePHICycle(MachineInstr *MI,
83 unsigned &SingleValReg,
84 InstrSet &PHIsInCycle) {
85 assert(MI->isPHI() && "IsSingleValuePHICycle expects a PHI instruction");
86 unsigned DstReg = MI->getOperand(0).getReg();
88 // See if we already saw this register.
89 if (!PHIsInCycle.insert(MI))
92 // Don't scan crazily complex things.
93 if (PHIsInCycle.size() == 16)
96 // Scan the PHI operands.
97 for (unsigned i = 1; i != MI->getNumOperands(); i += 2) {
98 unsigned SrcReg = MI->getOperand(i).getReg();
101 MachineInstr *SrcMI = MRI->getVRegDef(SrcReg);
103 // Skip over register-to-register moves.
104 if (SrcMI && SrcMI->isCopy() &&
105 !SrcMI->getOperand(0).getSubReg() &&
106 !SrcMI->getOperand(1).getSubReg() &&
107 TargetRegisterInfo::isVirtualRegister(SrcMI->getOperand(1).getReg()))
108 SrcMI = MRI->getVRegDef(SrcMI->getOperand(1).getReg());
112 if (SrcMI->isPHI()) {
113 if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
116 // Fail if there is more than one non-phi/non-move register.
117 if (SingleValReg != 0)
119 SingleValReg = SrcReg;
125 /// IsDeadPHICycle - Check if the register defined by a PHI is only used by
126 /// other PHIs in a cycle.
127 bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
128 assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
129 unsigned DstReg = MI->getOperand(0).getReg();
130 assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
131 "PHI destination is not a virtual register");
133 // See if we already saw this register.
134 if (!PHIsInCycle.insert(MI))
137 // Don't scan crazily complex things.
138 if (PHIsInCycle.size() == 16)
141 for (MachineRegisterInfo::use_iterator I = MRI->use_begin(DstReg),
142 E = MRI->use_end(); I != E; ++I) {
143 MachineInstr *UseMI = &*I;
144 if (!UseMI->isPHI() || !IsDeadPHICycle(UseMI, PHIsInCycle))
151 /// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
153 bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
154 bool Changed = false;
155 for (MachineBasicBlock::iterator
156 MII = MBB.begin(), E = MBB.end(); MII != E; ) {
157 MachineInstr *MI = &*MII++;
161 // Check for single-value PHI cycles.
162 unsigned SingleValReg = 0;
163 InstrSet PHIsInCycle;
164 if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
166 MRI->replaceRegWith(MI->getOperand(0).getReg(), SingleValReg);
167 MI->eraseFromParent();
173 // Check for dead PHI cycles.
175 if (IsDeadPHICycle(MI, PHIsInCycle)) {
176 for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
178 MachineInstr *PhiMI = *PI;
181 PhiMI->eraseFromParent();