1 //===-- Thumb2ITBlockPass.cpp - Insert Thumb IT blocks ----------*- C++ -*-===//
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 "thumb2-it"
11 #include "ARM.h"
12 #include "ARMMachineFunctionInfo.h"
13 #include "Thumb2InstrInfo.h"
14 #include "llvm/CodeGen/MachineInstr.h"
15 #include "llvm/CodeGen/MachineInstrBuilder.h"
16 #include "llvm/CodeGen/MachineFunctionPass.h"
17 #include "llvm/ADT/SmallSet.h"
18 #include "llvm/ADT/Statistic.h"
19 using namespace llvm;
20 
21 STATISTIC(NumITs,        "Number of IT blocks inserted");
22 STATISTIC(NumMovedInsts, "Number of predicated instructions moved");
23 
24 namespace {
25   class Thumb2ITBlockPass : public MachineFunctionPass {
26     bool PreRegAlloc;
27 
28   public:
29     static char ID;
30     Thumb2ITBlockPass() : MachineFunctionPass(ID) {}
31 
32     const Thumb2InstrInfo *TII;
33     const TargetRegisterInfo *TRI;
34     ARMFunctionInfo *AFI;
35 
36     virtual bool runOnMachineFunction(MachineFunction &Fn);
37 
38     virtual const char *getPassName() const {
39       return "Thumb IT blocks insertion pass";
40     }
41 
42   private:
43     bool MoveCopyOutOfITBlock(MachineInstr *MI,
44                               ARMCC::CondCodes CC, ARMCC::CondCodes OCC,
45                               SmallSet<unsigned, 4> &Defs,
46                               SmallSet<unsigned, 4> &Uses);
47     bool InsertITInstructions(MachineBasicBlock &MBB);
48   };
49   char Thumb2ITBlockPass::ID = 0;
50 }
51 
52 /// TrackDefUses - Tracking what registers are being defined and used by
53 /// instructions in the IT block. This also tracks "dependencies", i.e. uses
54 /// in the IT block that are defined before the IT instruction.
55 static void TrackDefUses(MachineInstr *MI,
56                          SmallSet<unsigned, 4> &Defs,
57                          SmallSet<unsigned, 4> &Uses,
58                          const TargetRegisterInfo *TRI) {
59   SmallVector<unsigned, 4> LocalDefs;
60   SmallVector<unsigned, 4> LocalUses;
61 
62   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
63     MachineOperand &MO = MI->getOperand(i);
64     if (!MO.isReg())
65       continue;
66     unsigned Reg = MO.getReg();
67     if (!Reg || Reg == ARM::ITSTATE || Reg == ARM::SP)
68       continue;
69     if (MO.isUse())
70       LocalUses.push_back(Reg);
71     else
72       LocalDefs.push_back(Reg);
73   }
74 
75   for (unsigned i = 0, e = LocalUses.size(); i != e; ++i) {
76     unsigned Reg = LocalUses[i];
77     Uses.insert(Reg);
78     for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
79          *Subreg; ++Subreg)
80       Uses.insert(*Subreg);
81   }
82 
83   for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
84     unsigned Reg = LocalDefs[i];
85     Defs.insert(Reg);
86     for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
87          *Subreg; ++Subreg)
88       Defs.insert(*Subreg);
89     if (Reg == ARM::CPSR)
90       continue;
91   }
92 }
93 
94 static bool isCopy(MachineInstr *MI) {
95   switch (MI->getOpcode()) {
96   default:
97     return false;
98   case ARM::MOVr:
99   case ARM::MOVr_TC:
100   case ARM::tMOVr:
101   case ARM::t2MOVr:
102     return true;
103   }
104 }
105 
106 bool
107 Thumb2ITBlockPass::MoveCopyOutOfITBlock(MachineInstr *MI,
108                                       ARMCC::CondCodes CC, ARMCC::CondCodes OCC,
109                                         SmallSet<unsigned, 4> &Defs,
110                                         SmallSet<unsigned, 4> &Uses) {
111   if (!isCopy(MI))
112     return false;
113   // llvm models select's as two-address instructions. That means a copy
114   // is inserted before a t2MOVccr, etc. If the copy is scheduled in
115   // between selects we would end up creating multiple IT blocks.
116   assert(MI->getOperand(0).getSubReg() == 0 &&
117          MI->getOperand(1).getSubReg() == 0 &&
118          "Sub-register indices still around?");
119 
120   unsigned DstReg = MI->getOperand(0).getReg();
121   unsigned SrcReg = MI->getOperand(1).getReg();
122 
123   // First check if it's safe to move it.
124   if (Uses.count(DstReg) || Defs.count(SrcReg))
125     return false;
126 
127   // Then peek at the next instruction to see if it's predicated on CC or OCC.
128   // If not, then there is nothing to be gained by moving the copy.
129   MachineBasicBlock::iterator I = MI; ++I;
130   MachineBasicBlock::iterator E = MI->getParent()->end();
131   while (I != E && I->isDebugValue())
132     ++I;
133   if (I != E) {
134     unsigned NPredReg = 0;
135     ARMCC::CondCodes NCC = llvm::getITInstrPredicate(I, NPredReg);
136     if (NCC == CC || NCC == OCC)
137       return true;
138   }
139   return false;
140 }
141 
142 bool Thumb2ITBlockPass::InsertITInstructions(MachineBasicBlock &MBB) {
143   bool Modified = false;
144 
145   SmallSet<unsigned, 4> Defs;
146   SmallSet<unsigned, 4> Uses;
147   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
148   while (MBBI != E) {
149     MachineInstr *MI = &*MBBI;
150     DebugLoc dl = MI->getDebugLoc();
151     unsigned PredReg = 0;
152     ARMCC::CondCodes CC = llvm::getITInstrPredicate(MI, PredReg);
153     if (CC == ARMCC::AL) {
154       ++MBBI;
155       continue;
156     }
157 
158     Defs.clear();
159     Uses.clear();
160     TrackDefUses(MI, Defs, Uses, TRI);
161 
162     // Insert an IT instruction.
163     MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(ARM::t2IT))
164       .addImm(CC);
165 
166     // Add implicit use of ITSTATE to IT block instructions.
167     MI->addOperand(MachineOperand::CreateReg(ARM::ITSTATE, false/*ifDef*/,
168                                              true/*isImp*/, false/*isKill*/));
169 
170     MachineInstr *LastITMI = MI;
171     MachineBasicBlock::iterator InsertPos = MIB;
172     ++MBBI;
173 
174     // Form IT block.
175     ARMCC::CondCodes OCC = ARMCC::getOppositeCondition(CC);
176     unsigned Mask = 0, Pos = 3;
177     // Branches, including tricky ones like LDM_RET, need to end an IT
178     // block so check the instruction we just put in the block.
179     for (; MBBI != E && Pos &&
180            (!MI->getDesc().isBranch() && !MI->getDesc().isReturn()) ; ++MBBI) {
181       if (MBBI->isDebugValue())
182         continue;
183 
184       MachineInstr *NMI = &*MBBI;
185       MI = NMI;
186 
187       unsigned NPredReg = 0;
188       ARMCC::CondCodes NCC = llvm::getITInstrPredicate(NMI, NPredReg);
189       if (NCC == CC || NCC == OCC) {
190         Mask |= (NCC & 1) << Pos;
191         // Add implicit use of ITSTATE.
192         NMI->addOperand(MachineOperand::CreateReg(ARM::ITSTATE, false/*ifDef*/,
193                                                true/*isImp*/, false/*isKill*/));
194         LastITMI = NMI;
195       } else {
196         if (NCC == ARMCC::AL &&
197             MoveCopyOutOfITBlock(NMI, CC, OCC, Defs, Uses)) {
198           --MBBI;
199           MBB.remove(NMI);
200           MBB.insert(InsertPos, NMI);
201           ++NumMovedInsts;
202           continue;
203         }
204         break;
205       }
206       TrackDefUses(NMI, Defs, Uses, TRI);
207       --Pos;
208     }
209 
210     // Finalize IT mask.
211     Mask |= (1 << Pos);
212     // Tag along (firstcond[0] << 4) with the mask.
213     Mask |= (CC & 1) << 4;
214     MIB.addImm(Mask);
215 
216     // Last instruction in IT block kills ITSTATE.
217     LastITMI->findRegisterUseOperand(ARM::ITSTATE)->setIsKill();
218 
219     Modified = true;
220     ++NumITs;
221   }
222 
223   return Modified;
224 }
225 
226 bool Thumb2ITBlockPass::runOnMachineFunction(MachineFunction &Fn) {
227   const TargetMachine &TM = Fn.getTarget();
228   AFI = Fn.getInfo<ARMFunctionInfo>();
229   TII = static_cast<const Thumb2InstrInfo*>(TM.getInstrInfo());
230   TRI = TM.getRegisterInfo();
231 
232   if (!AFI->isThumbFunction())
233     return false;
234 
235   bool Modified = false;
236   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; ) {
237     MachineBasicBlock &MBB = *MFI;
238     ++MFI;
239     Modified |= InsertITInstructions(MBB);
240   }
241 
242   if (Modified)
243     AFI->setHasITBlocks(true);
244 
245   return Modified;
246 }
247 
248 /// createThumb2ITBlockPass - Returns an instance of the Thumb2 IT blocks
249 /// insertion pass.
250 FunctionPass *llvm::createThumb2ITBlockPass() {
251   return new Thumb2ITBlockPass();
252 }
253