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
unsigned MvSrcReg, MvDstReg, SrcSubIdx, DstSubIdx;
106
TII->isMoveInstr(*SrcMI, MvSrcReg, MvDstReg, SrcSubIdx, DstSubIdx) &&
107
SrcSubIdx == 0 && DstSubIdx == 0 &&
108
TargetRegisterInfo::isVirtualRegister(MvSrcReg))
109
SrcMI = MRI->getVRegDef(MvSrcReg);
113
if (SrcMI->isPHI()) {
114
if (!IsSingleValuePHICycle(SrcMI, SingleValReg, PHIsInCycle))
117
// Fail if there is more than one non-phi/non-move register.
118
if (SingleValReg != 0)
120
SingleValReg = SrcReg;
126
/// IsDeadPHICycle - Check if the register defined by a PHI is only used by
127
/// other PHIs in a cycle.
128
bool OptimizePHIs::IsDeadPHICycle(MachineInstr *MI, InstrSet &PHIsInCycle) {
129
assert(MI->isPHI() && "IsDeadPHICycle expects a PHI instruction");
130
unsigned DstReg = MI->getOperand(0).getReg();
131
assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
132
"PHI destination is not a virtual register");
134
// See if we already saw this register.
135
if (!PHIsInCycle.insert(MI))
138
// Don't scan crazily complex things.
139
if (PHIsInCycle.size() == 16)
142
for (MachineRegisterInfo::use_iterator I = MRI->use_begin(DstReg),
143
E = MRI->use_end(); I != E; ++I) {
144
MachineInstr *UseMI = &*I;
145
if (!UseMI->isPHI() || !IsDeadPHICycle(UseMI, PHIsInCycle))
152
/// OptimizeBB - Remove dead PHI cycles and PHI cycles that can be replaced by
154
bool OptimizePHIs::OptimizeBB(MachineBasicBlock &MBB) {
155
bool Changed = false;
156
for (MachineBasicBlock::iterator
157
MII = MBB.begin(), E = MBB.end(); MII != E; ) {
158
MachineInstr *MI = &*MII++;
162
// Check for single-value PHI cycles.
163
unsigned SingleValReg = 0;
164
InstrSet PHIsInCycle;
165
if (IsSingleValuePHICycle(MI, SingleValReg, PHIsInCycle) &&
167
MRI->replaceRegWith(MI->getOperand(0).getReg(), SingleValReg);
168
MI->eraseFromParent();
174
// Check for dead PHI cycles.
176
if (IsDeadPHICycle(MI, PHIsInCycle)) {
177
for (InstrSetIterator PI = PHIsInCycle.begin(), PE = PHIsInCycle.end();
179
MachineInstr *PhiMI = *PI;
182
PhiMI->eraseFromParent();