1234353Sdim//===-- Thumb2ITBlockPass.cpp - Insert Thumb-2 IT blocks ------------------===// 2198090Srdivacky// 3198090Srdivacky// The LLVM Compiler Infrastructure 4198090Srdivacky// 5198090Srdivacky// This file is distributed under the University of Illinois Open Source 6198090Srdivacky// License. See LICENSE.TXT for details. 7198090Srdivacky// 8198090Srdivacky//===----------------------------------------------------------------------===// 9198090Srdivacky 10198090Srdivacky#define DEBUG_TYPE "thumb2-it" 11198090Srdivacky#include "ARM.h" 12198090Srdivacky#include "ARMMachineFunctionInfo.h" 13198090Srdivacky#include "Thumb2InstrInfo.h" 14249423Sdim#include "llvm/ADT/SmallSet.h" 15249423Sdim#include "llvm/ADT/Statistic.h" 16249423Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 17198090Srdivacky#include "llvm/CodeGen/MachineInstr.h" 18198090Srdivacky#include "llvm/CodeGen/MachineInstrBuilder.h" 19234353Sdim#include "llvm/CodeGen/MachineInstrBundle.h" 20198090Srdivackyusing namespace llvm; 21198090Srdivacky 22210299SedSTATISTIC(NumITs, "Number of IT blocks inserted"); 23210299SedSTATISTIC(NumMovedInsts, "Number of predicated instructions moved"); 24198090Srdivacky 25198090Srdivackynamespace { 26210299Sed class Thumb2ITBlockPass : public MachineFunctionPass { 27210299Sed public: 28198090Srdivacky static char ID; 29212904Sdim Thumb2ITBlockPass() : MachineFunctionPass(ID) {} 30198090Srdivacky 31263508Sdim bool restrictIT; 32198090Srdivacky const Thumb2InstrInfo *TII; 33210299Sed const TargetRegisterInfo *TRI; 34198090Srdivacky ARMFunctionInfo *AFI; 35198090Srdivacky 36198090Srdivacky virtual bool runOnMachineFunction(MachineFunction &Fn); 37198090Srdivacky 38198090Srdivacky virtual const char *getPassName() const { 39198090Srdivacky return "Thumb IT blocks insertion pass"; 40198090Srdivacky } 41198090Srdivacky 42198090Srdivacky private: 43210299Sed bool MoveCopyOutOfITBlock(MachineInstr *MI, 44210299Sed ARMCC::CondCodes CC, ARMCC::CondCodes OCC, 45210299Sed SmallSet<unsigned, 4> &Defs, 46210299Sed SmallSet<unsigned, 4> &Uses); 47210299Sed bool InsertITInstructions(MachineBasicBlock &MBB); 48198090Srdivacky }; 49198090Srdivacky char Thumb2ITBlockPass::ID = 0; 50198090Srdivacky} 51198090Srdivacky 52210299Sed/// TrackDefUses - Tracking what registers are being defined and used by 53210299Sed/// instructions in the IT block. This also tracks "dependencies", i.e. uses 54210299Sed/// in the IT block that are defined before the IT instruction. 55210299Sedstatic void TrackDefUses(MachineInstr *MI, 56210299Sed SmallSet<unsigned, 4> &Defs, 57210299Sed SmallSet<unsigned, 4> &Uses, 58210299Sed const TargetRegisterInfo *TRI) { 59210299Sed SmallVector<unsigned, 4> LocalDefs; 60210299Sed SmallVector<unsigned, 4> LocalUses; 61210299Sed 62210299Sed for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 63210299Sed MachineOperand &MO = MI->getOperand(i); 64210299Sed if (!MO.isReg()) 65210299Sed continue; 66210299Sed unsigned Reg = MO.getReg(); 67210299Sed if (!Reg || Reg == ARM::ITSTATE || Reg == ARM::SP) 68210299Sed continue; 69210299Sed if (MO.isUse()) 70210299Sed LocalUses.push_back(Reg); 71210299Sed else 72210299Sed LocalDefs.push_back(Reg); 73210299Sed } 74210299Sed 75210299Sed for (unsigned i = 0, e = LocalUses.size(); i != e; ++i) { 76210299Sed unsigned Reg = LocalUses[i]; 77263508Sdim for (MCSubRegIterator Subreg(Reg, TRI, /*IncludeSelf=*/true); 78263508Sdim Subreg.isValid(); ++Subreg) 79210299Sed Uses.insert(*Subreg); 80210299Sed } 81210299Sed 82210299Sed for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) { 83210299Sed unsigned Reg = LocalDefs[i]; 84263508Sdim for (MCSubRegIterator Subreg(Reg, TRI, /*IncludeSelf=*/true); 85263508Sdim Subreg.isValid(); ++Subreg) 86210299Sed Defs.insert(*Subreg); 87210299Sed if (Reg == ARM::CPSR) 88210299Sed continue; 89210299Sed } 90198090Srdivacky} 91198090Srdivacky 92212904Sdimstatic bool isCopy(MachineInstr *MI) { 93212904Sdim switch (MI->getOpcode()) { 94212904Sdim default: 95212904Sdim return false; 96212904Sdim case ARM::MOVr: 97212904Sdim case ARM::MOVr_TC: 98212904Sdim case ARM::tMOVr: 99212904Sdim case ARM::t2MOVr: 100212904Sdim return true; 101212904Sdim } 102212904Sdim} 103212904Sdim 104210299Sedbool 105210299SedThumb2ITBlockPass::MoveCopyOutOfITBlock(MachineInstr *MI, 106210299Sed ARMCC::CondCodes CC, ARMCC::CondCodes OCC, 107210299Sed SmallSet<unsigned, 4> &Defs, 108210299Sed SmallSet<unsigned, 4> &Uses) { 109212904Sdim if (!isCopy(MI)) 110212904Sdim return false; 111212904Sdim // llvm models select's as two-address instructions. That means a copy 112212904Sdim // is inserted before a t2MOVccr, etc. If the copy is scheduled in 113212904Sdim // between selects we would end up creating multiple IT blocks. 114212904Sdim assert(MI->getOperand(0).getSubReg() == 0 && 115212904Sdim MI->getOperand(1).getSubReg() == 0 && 116212904Sdim "Sub-register indices still around?"); 117210299Sed 118212904Sdim unsigned DstReg = MI->getOperand(0).getReg(); 119212904Sdim unsigned SrcReg = MI->getOperand(1).getReg(); 120210299Sed 121212904Sdim // First check if it's safe to move it. 122212904Sdim if (Uses.count(DstReg) || Defs.count(SrcReg)) 123212904Sdim return false; 124212904Sdim 125226633Sdim // If the CPSR is defined by this copy, then we don't want to move it. E.g., 126226633Sdim // if we have: 127226633Sdim // 128226633Sdim // movs r1, r1 129226633Sdim // rsb r1, 0 130226633Sdim // movs r2, r2 131226633Sdim // rsb r2, 0 132226633Sdim // 133226633Sdim // we don't want this to be converted to: 134226633Sdim // 135226633Sdim // movs r1, r1 136226633Sdim // movs r2, r2 137226633Sdim // itt mi 138226633Sdim // rsb r1, 0 139226633Sdim // rsb r2, 0 140226633Sdim // 141226633Sdim const MCInstrDesc &MCID = MI->getDesc(); 142234353Sdim if (MI->hasOptionalDef() && 143226633Sdim MI->getOperand(MCID.getNumOperands() - 1).getReg() == ARM::CPSR) 144226633Sdim return false; 145226633Sdim 146212904Sdim // Then peek at the next instruction to see if it's predicated on CC or OCC. 147212904Sdim // If not, then there is nothing to be gained by moving the copy. 148212904Sdim MachineBasicBlock::iterator I = MI; ++I; 149212904Sdim MachineBasicBlock::iterator E = MI->getParent()->end(); 150212904Sdim while (I != E && I->isDebugValue()) 151212904Sdim ++I; 152212904Sdim if (I != E) { 153212904Sdim unsigned NPredReg = 0; 154234353Sdim ARMCC::CondCodes NCC = getITInstrPredicate(I, NPredReg); 155212904Sdim if (NCC == CC || NCC == OCC) 156212904Sdim return true; 157210299Sed } 158210299Sed return false; 159210299Sed} 160210299Sed 161210299Sedbool Thumb2ITBlockPass::InsertITInstructions(MachineBasicBlock &MBB) { 162198090Srdivacky bool Modified = false; 163198090Srdivacky 164210299Sed SmallSet<unsigned, 4> Defs; 165210299Sed SmallSet<unsigned, 4> Uses; 166198090Srdivacky MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end(); 167198090Srdivacky while (MBBI != E) { 168198090Srdivacky MachineInstr *MI = &*MBBI; 169198090Srdivacky DebugLoc dl = MI->getDebugLoc(); 170198090Srdivacky unsigned PredReg = 0; 171234353Sdim ARMCC::CondCodes CC = getITInstrPredicate(MI, PredReg); 172198090Srdivacky if (CC == ARMCC::AL) { 173198090Srdivacky ++MBBI; 174198090Srdivacky continue; 175198090Srdivacky } 176198090Srdivacky 177210299Sed Defs.clear(); 178210299Sed Uses.clear(); 179210299Sed TrackDefUses(MI, Defs, Uses, TRI); 180210299Sed 181198090Srdivacky // Insert an IT instruction. 182198090Srdivacky MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(ARM::t2IT)) 183198090Srdivacky .addImm(CC); 184210299Sed 185210299Sed // Add implicit use of ITSTATE to IT block instructions. 186210299Sed MI->addOperand(MachineOperand::CreateReg(ARM::ITSTATE, false/*ifDef*/, 187210299Sed true/*isImp*/, false/*isKill*/)); 188210299Sed 189210299Sed MachineInstr *LastITMI = MI; 190210299Sed MachineBasicBlock::iterator InsertPos = MIB; 191198090Srdivacky ++MBBI; 192198090Srdivacky 193210299Sed // Form IT block. 194198090Srdivacky ARMCC::CondCodes OCC = ARMCC::getOppositeCondition(CC); 195198090Srdivacky unsigned Mask = 0, Pos = 3; 196210299Sed 197263508Sdim // v8 IT blocks are limited to one conditional op unless -arm-no-restrict-it 198263508Sdim // is set: skip the loop 199263508Sdim if (!restrictIT) { 200263508Sdim // Branches, including tricky ones like LDM_RET, need to end an IT 201263508Sdim // block so check the instruction we just put in the block. 202263508Sdim for (; MBBI != E && Pos && 203263508Sdim (!MI->isBranch() && !MI->isReturn()) ; ++MBBI) { 204263508Sdim if (MBBI->isDebugValue()) 205263508Sdim continue; 206210299Sed 207263508Sdim MachineInstr *NMI = &*MBBI; 208263508Sdim MI = NMI; 209263508Sdim 210263508Sdim unsigned NPredReg = 0; 211263508Sdim ARMCC::CondCodes NCC = getITInstrPredicate(NMI, NPredReg); 212263508Sdim if (NCC == CC || NCC == OCC) { 213263508Sdim Mask |= (NCC & 1) << Pos; 214263508Sdim // Add implicit use of ITSTATE. 215263508Sdim NMI->addOperand(MachineOperand::CreateReg(ARM::ITSTATE, false/*ifDef*/, 216263508Sdim true/*isImp*/, false/*isKill*/)); 217263508Sdim LastITMI = NMI; 218263508Sdim } else { 219263508Sdim if (NCC == ARMCC::AL && 220263508Sdim MoveCopyOutOfITBlock(NMI, CC, OCC, Defs, Uses)) { 221263508Sdim --MBBI; 222263508Sdim MBB.remove(NMI); 223263508Sdim MBB.insert(InsertPos, NMI); 224263508Sdim ++NumMovedInsts; 225263508Sdim continue; 226263508Sdim } 227263508Sdim break; 228210299Sed } 229263508Sdim TrackDefUses(NMI, Defs, Uses, TRI); 230263508Sdim --Pos; 231210299Sed } 232198090Srdivacky } 233210299Sed 234210299Sed // Finalize IT mask. 235198090Srdivacky Mask |= (1 << Pos); 236205407Srdivacky // Tag along (firstcond[0] << 4) with the mask. 237205407Srdivacky Mask |= (CC & 1) << 4; 238198090Srdivacky MIB.addImm(Mask); 239210299Sed 240210299Sed // Last instruction in IT block kills ITSTATE. 241210299Sed LastITMI->findRegisterUseOperand(ARM::ITSTATE)->setIsKill(); 242210299Sed 243234353Sdim // Finalize the bundle. 244234353Sdim MachineBasicBlock::instr_iterator LI = LastITMI; 245234353Sdim finalizeBundle(MBB, InsertPos.getInstrIterator(), llvm::next(LI)); 246234353Sdim 247198090Srdivacky Modified = true; 248198090Srdivacky ++NumITs; 249198090Srdivacky } 250198090Srdivacky 251198090Srdivacky return Modified; 252198090Srdivacky} 253198090Srdivacky 254198090Srdivackybool Thumb2ITBlockPass::runOnMachineFunction(MachineFunction &Fn) { 255198090Srdivacky const TargetMachine &TM = Fn.getTarget(); 256198090Srdivacky AFI = Fn.getInfo<ARMFunctionInfo>(); 257198090Srdivacky TII = static_cast<const Thumb2InstrInfo*>(TM.getInstrInfo()); 258210299Sed TRI = TM.getRegisterInfo(); 259263508Sdim restrictIT = TM.getSubtarget<ARMSubtarget>().restrictIT(); 260198090Srdivacky 261198090Srdivacky if (!AFI->isThumbFunction()) 262198090Srdivacky return false; 263198090Srdivacky 264198090Srdivacky bool Modified = false; 265210299Sed for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; ) { 266198090Srdivacky MachineBasicBlock &MBB = *MFI; 267210299Sed ++MFI; 268210299Sed Modified |= InsertITInstructions(MBB); 269198090Srdivacky } 270198090Srdivacky 271210299Sed if (Modified) 272210299Sed AFI->setHasITBlocks(true); 273210299Sed 274198090Srdivacky return Modified; 275198090Srdivacky} 276198090Srdivacky 277198090Srdivacky/// createThumb2ITBlockPass - Returns an instance of the Thumb2 IT blocks 278198090Srdivacky/// insertion pass. 279198090SrdivackyFunctionPass *llvm::createThumb2ITBlockPass() { 280198090Srdivacky return new Thumb2ITBlockPass(); 281198090Srdivacky} 282