contrib/llvm/lib/Target/ARM/Thumb2ITBlockPass.cpp

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