1234353Sdim//===-- Thumb2ITBlockPass.cpp - Insert Thumb-2 IT blocks ------------------===// 2198090Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6198090Srdivacky// 7198090Srdivacky//===----------------------------------------------------------------------===// 8198090Srdivacky 9198090Srdivacky#include "ARM.h" 10198090Srdivacky#include "ARMMachineFunctionInfo.h" 11321369Sdim#include "ARMSubtarget.h" 12321369Sdim#include "MCTargetDesc/ARMBaseInfo.h" 13198090Srdivacky#include "Thumb2InstrInfo.h" 14249423Sdim#include "llvm/ADT/SmallSet.h" 15321369Sdim#include "llvm/ADT/SmallVector.h" 16249423Sdim#include "llvm/ADT/Statistic.h" 17321369Sdim#include "llvm/ADT/StringRef.h" 18321369Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 19321369Sdim#include "llvm/CodeGen/MachineFunction.h" 20249423Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 21198090Srdivacky#include "llvm/CodeGen/MachineInstr.h" 22198090Srdivacky#include "llvm/CodeGen/MachineInstrBuilder.h" 23234353Sdim#include "llvm/CodeGen/MachineInstrBundle.h" 24321369Sdim#include "llvm/CodeGen/MachineOperand.h" 25321369Sdim#include "llvm/IR/DebugLoc.h" 26321369Sdim#include "llvm/MC/MCInstrDesc.h" 27321369Sdim#include "llvm/MC/MCRegisterInfo.h" 28321369Sdim#include <cassert> 29321369Sdim#include <new> 30321369Sdim 31198090Srdivackyusing namespace llvm; 32198090Srdivacky 33276479Sdim#define DEBUG_TYPE "thumb2-it" 34353358Sdim#define PASS_NAME "Thumb IT blocks insertion pass" 35276479Sdim 36210299SedSTATISTIC(NumITs, "Number of IT blocks inserted"); 37210299SedSTATISTIC(NumMovedInsts, "Number of predicated instructions moved"); 38198090Srdivacky 39353358Sdimusing RegisterSet = SmallSet<unsigned, 4>; 40353358Sdim 41198090Srdivackynamespace { 42321369Sdim 43353358Sdim class Thumb2ITBlock : public MachineFunctionPass { 44210299Sed public: 45198090Srdivacky static char ID; 46198090Srdivacky 47261991Sdim bool restrictIT; 48198090Srdivacky const Thumb2InstrInfo *TII; 49210299Sed const TargetRegisterInfo *TRI; 50198090Srdivacky ARMFunctionInfo *AFI; 51198090Srdivacky 52353358Sdim Thumb2ITBlock() : MachineFunctionPass(ID) {} 53321369Sdim 54276479Sdim bool runOnMachineFunction(MachineFunction &Fn) override; 55198090Srdivacky 56309124Sdim MachineFunctionProperties getRequiredProperties() const override { 57309124Sdim return MachineFunctionProperties().set( 58314564Sdim MachineFunctionProperties::Property::NoVRegs); 59309124Sdim } 60309124Sdim 61314564Sdim StringRef getPassName() const override { 62353358Sdim return PASS_NAME; 63198090Srdivacky } 64198090Srdivacky 65198090Srdivacky private: 66210299Sed bool MoveCopyOutOfITBlock(MachineInstr *MI, 67210299Sed ARMCC::CondCodes CC, ARMCC::CondCodes OCC, 68353358Sdim RegisterSet &Defs, RegisterSet &Uses); 69353358Sdim bool InsertITInstructions(MachineBasicBlock &Block); 70198090Srdivacky }; 71321369Sdim 72353358Sdim char Thumb2ITBlock::ID = 0; 73198090Srdivacky 74321369Sdim} // end anonymous namespace 75321369Sdim 76353358SdimINITIALIZE_PASS(Thumb2ITBlock, DEBUG_TYPE, PASS_NAME, false, false) 77353358Sdim 78210299Sed/// TrackDefUses - Tracking what registers are being defined and used by 79210299Sed/// instructions in the IT block. This also tracks "dependencies", i.e. uses 80210299Sed/// in the IT block that are defined before the IT instruction. 81353358Sdimstatic void TrackDefUses(MachineInstr *MI, RegisterSet &Defs, RegisterSet &Uses, 82210299Sed const TargetRegisterInfo *TRI) { 83353358Sdim using RegList = SmallVector<unsigned, 4>; 84353358Sdim RegList LocalDefs; 85353358Sdim RegList LocalUses; 86210299Sed 87353358Sdim for (auto &MO : MI->operands()) { 88210299Sed if (!MO.isReg()) 89210299Sed continue; 90360784Sdim Register Reg = MO.getReg(); 91210299Sed if (!Reg || Reg == ARM::ITSTATE || Reg == ARM::SP) 92210299Sed continue; 93210299Sed if (MO.isUse()) 94210299Sed LocalUses.push_back(Reg); 95210299Sed else 96210299Sed LocalDefs.push_back(Reg); 97210299Sed } 98210299Sed 99353358Sdim auto InsertUsesDefs = [&](RegList &Regs, RegisterSet &UsesDefs) { 100353358Sdim for (unsigned Reg : Regs) 101353358Sdim for (MCSubRegIterator Subreg(Reg, TRI, /*IncludeSelf=*/true); 102353358Sdim Subreg.isValid(); ++Subreg) 103353358Sdim UsesDefs.insert(*Subreg); 104353358Sdim }; 105210299Sed 106353358Sdim InsertUsesDefs(LocalDefs, Defs); 107353358Sdim InsertUsesDefs(LocalUses, Uses); 108198090Srdivacky} 109198090Srdivacky 110288943Sdim/// Clear kill flags for any uses in the given set. This will likely 111288943Sdim/// conservatively remove more kill flags than are necessary, but removing them 112288943Sdim/// is safer than incorrect kill flags remaining on instructions. 113353358Sdimstatic void ClearKillFlags(MachineInstr *MI, RegisterSet &Uses) { 114288943Sdim for (MachineOperand &MO : MI->operands()) { 115288943Sdim if (!MO.isReg() || MO.isDef() || !MO.isKill()) 116288943Sdim continue; 117288943Sdim if (!Uses.count(MO.getReg())) 118288943Sdim continue; 119288943Sdim MO.setIsKill(false); 120288943Sdim } 121288943Sdim} 122288943Sdim 123212904Sdimstatic bool isCopy(MachineInstr *MI) { 124212904Sdim switch (MI->getOpcode()) { 125212904Sdim default: 126212904Sdim return false; 127212904Sdim case ARM::MOVr: 128212904Sdim case ARM::MOVr_TC: 129212904Sdim case ARM::tMOVr: 130212904Sdim case ARM::t2MOVr: 131212904Sdim return true; 132212904Sdim } 133212904Sdim} 134212904Sdim 135210299Sedbool 136353358SdimThumb2ITBlock::MoveCopyOutOfITBlock(MachineInstr *MI, 137353358Sdim ARMCC::CondCodes CC, ARMCC::CondCodes OCC, 138353358Sdim RegisterSet &Defs, RegisterSet &Uses) { 139212904Sdim if (!isCopy(MI)) 140212904Sdim return false; 141212904Sdim // llvm models select's as two-address instructions. That means a copy 142212904Sdim // is inserted before a t2MOVccr, etc. If the copy is scheduled in 143212904Sdim // between selects we would end up creating multiple IT blocks. 144212904Sdim assert(MI->getOperand(0).getSubReg() == 0 && 145212904Sdim MI->getOperand(1).getSubReg() == 0 && 146212904Sdim "Sub-register indices still around?"); 147210299Sed 148360784Sdim Register DstReg = MI->getOperand(0).getReg(); 149360784Sdim Register SrcReg = MI->getOperand(1).getReg(); 150210299Sed 151212904Sdim // First check if it's safe to move it. 152212904Sdim if (Uses.count(DstReg) || Defs.count(SrcReg)) 153212904Sdim return false; 154212904Sdim 155226633Sdim // If the CPSR is defined by this copy, then we don't want to move it. E.g., 156226633Sdim // if we have: 157226633Sdim // 158226633Sdim // movs r1, r1 159226633Sdim // rsb r1, 0 160226633Sdim // movs r2, r2 161226633Sdim // rsb r2, 0 162226633Sdim // 163226633Sdim // we don't want this to be converted to: 164226633Sdim // 165226633Sdim // movs r1, r1 166226633Sdim // movs r2, r2 167226633Sdim // itt mi 168226633Sdim // rsb r1, 0 169226633Sdim // rsb r2, 0 170226633Sdim // 171226633Sdim const MCInstrDesc &MCID = MI->getDesc(); 172234353Sdim if (MI->hasOptionalDef() && 173226633Sdim MI->getOperand(MCID.getNumOperands() - 1).getReg() == ARM::CPSR) 174226633Sdim return false; 175226633Sdim 176212904Sdim // Then peek at the next instruction to see if it's predicated on CC or OCC. 177212904Sdim // If not, then there is nothing to be gained by moving the copy. 178353358Sdim MachineBasicBlock::iterator I = MI; 179353358Sdim ++I; 180212904Sdim MachineBasicBlock::iterator E = MI->getParent()->end(); 181353358Sdim 182341825Sdim while (I != E && I->isDebugInstr()) 183212904Sdim ++I; 184353358Sdim 185212904Sdim if (I != E) { 186212904Sdim unsigned NPredReg = 0; 187309124Sdim ARMCC::CondCodes NCC = getITInstrPredicate(*I, NPredReg); 188212904Sdim if (NCC == CC || NCC == OCC) 189212904Sdim return true; 190210299Sed } 191210299Sed return false; 192210299Sed} 193210299Sed 194353358Sdimbool Thumb2ITBlock::InsertITInstructions(MachineBasicBlock &MBB) { 195198090Srdivacky bool Modified = false; 196353358Sdim RegisterSet Defs, Uses; 197353358Sdim MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end(); 198198090Srdivacky 199198090Srdivacky while (MBBI != E) { 200198090Srdivacky MachineInstr *MI = &*MBBI; 201198090Srdivacky DebugLoc dl = MI->getDebugLoc(); 202198090Srdivacky unsigned PredReg = 0; 203309124Sdim ARMCC::CondCodes CC = getITInstrPredicate(*MI, PredReg); 204198090Srdivacky if (CC == ARMCC::AL) { 205198090Srdivacky ++MBBI; 206198090Srdivacky continue; 207198090Srdivacky } 208198090Srdivacky 209210299Sed Defs.clear(); 210210299Sed Uses.clear(); 211210299Sed TrackDefUses(MI, Defs, Uses, TRI); 212210299Sed 213198090Srdivacky // Insert an IT instruction. 214198090Srdivacky MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(ARM::t2IT)) 215198090Srdivacky .addImm(CC); 216210299Sed 217210299Sed // Add implicit use of ITSTATE to IT block instructions. 218210299Sed MI->addOperand(MachineOperand::CreateReg(ARM::ITSTATE, false/*ifDef*/, 219210299Sed true/*isImp*/, false/*isKill*/)); 220210299Sed 221210299Sed MachineInstr *LastITMI = MI; 222280031Sdim MachineBasicBlock::iterator InsertPos = MIB.getInstr(); 223198090Srdivacky ++MBBI; 224198090Srdivacky 225210299Sed // Form IT block. 226198090Srdivacky ARMCC::CondCodes OCC = ARMCC::getOppositeCondition(CC); 227198090Srdivacky unsigned Mask = 0, Pos = 3; 228210299Sed 229261991Sdim // v8 IT blocks are limited to one conditional op unless -arm-no-restrict-it 230261991Sdim // is set: skip the loop 231261991Sdim if (!restrictIT) { 232261991Sdim // Branches, including tricky ones like LDM_RET, need to end an IT 233261991Sdim // block so check the instruction we just put in the block. 234261991Sdim for (; MBBI != E && Pos && 235261991Sdim (!MI->isBranch() && !MI->isReturn()) ; ++MBBI) { 236341825Sdim if (MBBI->isDebugInstr()) 237261991Sdim continue; 238210299Sed 239261991Sdim MachineInstr *NMI = &*MBBI; 240261991Sdim MI = NMI; 241261991Sdim 242261991Sdim unsigned NPredReg = 0; 243309124Sdim ARMCC::CondCodes NCC = getITInstrPredicate(*NMI, NPredReg); 244261991Sdim if (NCC == CC || NCC == OCC) { 245353358Sdim Mask |= ((NCC ^ CC) & 1) << Pos; 246261991Sdim // Add implicit use of ITSTATE. 247261991Sdim NMI->addOperand(MachineOperand::CreateReg(ARM::ITSTATE, false/*ifDef*/, 248261991Sdim true/*isImp*/, false/*isKill*/)); 249261991Sdim LastITMI = NMI; 250261991Sdim } else { 251261991Sdim if (NCC == ARMCC::AL && 252261991Sdim MoveCopyOutOfITBlock(NMI, CC, OCC, Defs, Uses)) { 253261991Sdim --MBBI; 254261991Sdim MBB.remove(NMI); 255261991Sdim MBB.insert(InsertPos, NMI); 256288943Sdim ClearKillFlags(MI, Uses); 257261991Sdim ++NumMovedInsts; 258261991Sdim continue; 259261991Sdim } 260261991Sdim break; 261210299Sed } 262261991Sdim TrackDefUses(NMI, Defs, Uses, TRI); 263261991Sdim --Pos; 264210299Sed } 265198090Srdivacky } 266210299Sed 267210299Sed // Finalize IT mask. 268198090Srdivacky Mask |= (1 << Pos); 269198090Srdivacky MIB.addImm(Mask); 270210299Sed 271210299Sed // Last instruction in IT block kills ITSTATE. 272210299Sed LastITMI->findRegisterUseOperand(ARM::ITSTATE)->setIsKill(); 273210299Sed 274234353Sdim // Finalize the bundle. 275296417Sdim finalizeBundle(MBB, InsertPos.getInstrIterator(), 276296417Sdim ++LastITMI->getIterator()); 277234353Sdim 278198090Srdivacky Modified = true; 279198090Srdivacky ++NumITs; 280198090Srdivacky } 281198090Srdivacky 282198090Srdivacky return Modified; 283198090Srdivacky} 284198090Srdivacky 285353358Sdimbool Thumb2ITBlock::runOnMachineFunction(MachineFunction &Fn) { 286288943Sdim const ARMSubtarget &STI = 287288943Sdim static_cast<const ARMSubtarget &>(Fn.getSubtarget()); 288288943Sdim if (!STI.isThumb2()) 289288943Sdim return false; 290198090Srdivacky AFI = Fn.getInfo<ARMFunctionInfo>(); 291288943Sdim TII = static_cast<const Thumb2InstrInfo *>(STI.getInstrInfo()); 292288943Sdim TRI = STI.getRegisterInfo(); 293288943Sdim restrictIT = STI.restrictIT(); 294198090Srdivacky 295198090Srdivacky if (!AFI->isThumbFunction()) 296198090Srdivacky return false; 297198090Srdivacky 298198090Srdivacky bool Modified = false; 299353358Sdim for (auto &MBB : Fn ) 300210299Sed Modified |= InsertITInstructions(MBB); 301198090Srdivacky 302210299Sed if (Modified) 303210299Sed AFI->setHasITBlocks(true); 304210299Sed 305198090Srdivacky return Modified; 306198090Srdivacky} 307198090Srdivacky 308198090Srdivacky/// createThumb2ITBlockPass - Returns an instance of the Thumb2 IT blocks 309198090Srdivacky/// insertion pass. 310353358SdimFunctionPass *llvm::createThumb2ITBlockPass() { return new Thumb2ITBlock(); } 311