ReMat: fix overly cavalier attitude to sub-register indices
[oota-llvm.git] / lib / CodeGen / ProcessImplicitDefs.cpp
1 //===---------------------- ProcessImplicitDefs.cpp -----------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #define DEBUG_TYPE "processimplicitdefs"
11
12 #include "llvm/ADT/SetVector.h"
13 #include "llvm/Analysis/AliasAnalysis.h"
14 #include "llvm/CodeGen/MachineFunctionPass.h"
15 #include "llvm/CodeGen/MachineInstr.h"
16 #include "llvm/CodeGen/MachineRegisterInfo.h"
17 #include "llvm/CodeGen/Passes.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/raw_ostream.h"
20 #include "llvm/Target/TargetInstrInfo.h"
21
22 using namespace llvm;
23
24 namespace {
25 /// Process IMPLICIT_DEF instructions and make sure there is one implicit_def
26 /// for each use. Add isUndef marker to implicit_def defs and their uses.
27 class ProcessImplicitDefs : public MachineFunctionPass {
28   const TargetInstrInfo *TII;
29   const TargetRegisterInfo *TRI;
30   MachineRegisterInfo *MRI;
31
32   SmallSetVector<MachineInstr*, 16> WorkList;
33
34   void processImplicitDef(MachineInstr *MI);
35   bool canTurnIntoImplicitDef(MachineInstr *MI);
36
37 public:
38   static char ID;
39
40   ProcessImplicitDefs() : MachineFunctionPass(ID) {
41     initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry());
42   }
43
44   virtual void getAnalysisUsage(AnalysisUsage &au) const;
45
46   virtual bool runOnMachineFunction(MachineFunction &fn);
47 };
48 } // end anonymous namespace
49
50 char ProcessImplicitDefs::ID = 0;
51 char &llvm::ProcessImplicitDefsID = ProcessImplicitDefs::ID;
52
53 INITIALIZE_PASS_BEGIN(ProcessImplicitDefs, "processimpdefs",
54                 "Process Implicit Definitions", false, false)
55 INITIALIZE_PASS_END(ProcessImplicitDefs, "processimpdefs",
56                 "Process Implicit Definitions", false, false)
57
58 void ProcessImplicitDefs::getAnalysisUsage(AnalysisUsage &AU) const {
59   AU.setPreservesCFG();
60   AU.addPreserved<AliasAnalysis>();
61   MachineFunctionPass::getAnalysisUsage(AU);
62 }
63
64 bool ProcessImplicitDefs::canTurnIntoImplicitDef(MachineInstr *MI) {
65   if (!MI->isCopyLike() &&
66       !MI->isInsertSubreg() &&
67       !MI->isRegSequence() &&
68       !MI->isPHI())
69     return false;
70   for (MIOperands MO(MI); MO.isValid(); ++MO)
71     if (MO->isReg() && MO->isUse() && MO->readsReg())
72       return false;
73   return true;
74 }
75
76 void ProcessImplicitDefs::processImplicitDef(MachineInstr *MI) {
77   DEBUG(dbgs() << "Processing " << *MI);
78   unsigned Reg = MI->getOperand(0).getReg();
79
80   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
81     // For virtual registers, mark all uses as <undef>, and convert users to
82     // implicit-def when possible.
83     for (MachineRegisterInfo::use_nodbg_iterator UI =
84          MRI->use_nodbg_begin(Reg),
85          UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
86       MachineOperand &MO = UI.getOperand();
87       MO.setIsUndef();
88       MachineInstr *UserMI = MO.getParent();
89       if (!canTurnIntoImplicitDef(UserMI))
90         continue;
91       DEBUG(dbgs() << "Converting to IMPLICIT_DEF: " << *UserMI);
92       UserMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
93       WorkList.insert(UserMI);
94     }
95     MI->eraseFromParent();
96     return;
97   }
98
99   // This is a physreg implicit-def.
100   // Look for the first instruction to use or define an alias.
101   MachineBasicBlock::instr_iterator UserMI = MI;
102   MachineBasicBlock::instr_iterator UserE = MI->getParent()->instr_end();
103   bool Found = false;
104   for (++UserMI; UserMI != UserE; ++UserMI) {
105     for (MIOperands MO(UserMI); MO.isValid(); ++MO) {
106       if (!MO->isReg())
107         continue;
108       unsigned UserReg = MO->getReg();
109       if (!TargetRegisterInfo::isPhysicalRegister(UserReg) ||
110           !TRI->regsOverlap(Reg, UserReg))
111         continue;
112       // UserMI uses or redefines Reg. Set <undef> flags on all uses.
113       Found = true;
114       if (MO->isUse())
115         MO->setIsUndef();
116     }
117     if (Found)
118       break;
119   }
120
121   // If we found the using MI, we can erase the IMPLICIT_DEF.
122   if (Found) {
123     DEBUG(dbgs() << "Physreg user: " << *UserMI);
124     MI->eraseFromParent();
125     return;
126   }
127
128   // Using instr wasn't found, it could be in another block.
129   // Leave the physreg IMPLICIT_DEF, but trim any extra operands.
130   for (unsigned i = MI->getNumOperands() - 1; i; --i)
131     MI->RemoveOperand(i);
132   DEBUG(dbgs() << "Keeping physreg: " << *MI);
133 }
134
135 /// processImplicitDefs - Process IMPLICIT_DEF instructions and turn them into
136 /// <undef> operands.
137 bool ProcessImplicitDefs::runOnMachineFunction(MachineFunction &MF) {
138
139   DEBUG(dbgs() << "********** PROCESS IMPLICIT DEFS **********\n"
140                << "********** Function: " << MF.getName() << '\n');
141
142   bool Changed = false;
143
144   TII = MF.getTarget().getInstrInfo();
145   TRI = MF.getTarget().getRegisterInfo();
146   MRI = &MF.getRegInfo();
147   assert(MRI->isSSA() && "ProcessImplicitDefs only works on SSA form.");
148   assert(WorkList.empty() && "Inconsistent worklist state");
149
150   for (MachineFunction::iterator MFI = MF.begin(), MFE = MF.end();
151        MFI != MFE; ++MFI) {
152     // Scan the basic block for implicit defs.
153     for (MachineBasicBlock::instr_iterator MBBI = MFI->instr_begin(),
154          MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI)
155       if (MBBI->isImplicitDef())
156         WorkList.insert(MBBI);
157
158     if (WorkList.empty())
159       continue;
160
161     DEBUG(dbgs() << "BB#" << MFI->getNumber() << " has " << WorkList.size()
162                  << " implicit defs.\n");
163     Changed = true;
164
165     // Drain the WorkList to recursively process any new implicit defs.
166     do processImplicitDef(WorkList.pop_back_val());
167     while (!WorkList.empty());
168   }
169   return Changed;
170 }