lib/Target/ARM/Thumb2ITBlockPass.cpp

   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(bool PreRA) :
  31       MachineFunctionPass(&ID), PreRegAlloc(PreRA) {}
  32
  33     const Thumb2InstrInfo *TII;
  34     const TargetRegisterInfo *TRI;
  35     ARMFunctionInfo *AFI;
  36
  37     virtual bool runOnMachineFunction(MachineFunction &Fn);
  38
  39     virtual const char *getPassName() const {
  40       return "Thumb IT blocks insertion pass";
  41     }
  42
  43   private:
  44     bool MoveCPSRUseUp(MachineBasicBlock &MBB,
  45                        MachineBasicBlock::iterator MBBI,
  46                        MachineBasicBlock::iterator E,
  47                        unsigned PredReg,
  48                        ARMCC::CondCodes CC, ARMCC::CondCodes OCC,
  49                        bool &Done);
  50
  51     void FindITBlockRanges(MachineBasicBlock &MBB,
  52                            SmallVector<MachineInstr*,4> &FirstUses,
  53                            SmallVector<MachineInstr*,4> &LastUses);
  54     bool InsertITBlock(MachineInstr *First, MachineInstr *Last);
  55     bool InsertITBlocks(MachineBasicBlock &MBB);
  56     bool MoveCopyOutOfITBlock(MachineInstr *MI,
  57                               ARMCC::CondCodes CC, ARMCC::CondCodes OCC,
  58                               SmallSet<unsigned, 4> &Defs,
  59                               SmallSet<unsigned, 4> &Uses);
  60     bool InsertITInstructions(MachineBasicBlock &MBB);
  61   };
  62   char Thumb2ITBlockPass::ID = 0;
  63 }
  64
  65 bool
  66 Thumb2ITBlockPass::MoveCPSRUseUp(MachineBasicBlock &MBB,
  67                                  MachineBasicBlock::iterator MBBI,
  68                                  MachineBasicBlock::iterator E,
  69                                  unsigned PredReg,
  70                                  ARMCC::CondCodes CC, ARMCC::CondCodes OCC,
  71                                  bool &Done) {
  72   SmallSet<unsigned, 4> Defs, Uses;
  73   MachineBasicBlock::iterator I = MBBI;
  74   // Look for next CPSR use by scanning up to 4 instructions.
  75   for (unsigned i = 0; i < 4; ++i) {
  76     MachineInstr *MI = &*I;
  77     unsigned MPredReg = 0;
  78     ARMCC::CondCodes MCC = llvm::getITInstrPredicate(MI, MPredReg);
  79     if (MCC != ARMCC::AL) {
  80       if (MPredReg != PredReg || (MCC != CC && MCC != OCC))
  81         return false;
  82
  83       // Check if the instruction is using any register that's defined
  84       // below the previous predicated instruction. Also return false if
  85       // it defines any register which is used in between.
  86       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  87         const MachineOperand &MO = MI->getOperand(i);
  88         if (!MO.isReg())
  89           continue;
  90         unsigned Reg = MO.getReg();
  91         if (!Reg)
  92           continue;
  93         if (MO.isDef()) {
  94           if (Reg == PredReg || Uses.count(Reg))
  95             return false;
  96         } else {
  97           if (Defs.count(Reg))
  98             return false;
  99         }
 100       }
 101
 102       Done = (I == E);
 103       MBB.remove(MI);
 104       MBB.insert(MBBI, MI);
 105       ++NumMovedInsts;
 106       return true;
 107     }
 108
 109     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 110       const MachineOperand &MO = MI->getOperand(i);
 111       if (!MO.isReg())
 112         continue;
 113       unsigned Reg = MO.getReg();
 114       if (!Reg)
 115         continue;
 116       if (MO.isDef()) {
 117         if (Reg == PredReg)
 118           return false;
 119         Defs.insert(Reg);
 120       } else
 121         Uses.insert(Reg);
 122     }
 123
 124     if (I == E)
 125       break;
 126     ++I;
 127   }
 128   return false;
 129 }
 130
 131 static bool isCPSRLiveout(MachineBasicBlock &MBB) {
 132   for (MachineBasicBlock::succ_iterator I = MBB.succ_begin(),
 133          E = MBB.succ_end(); I != E; ++I) {
 134     if ((*I)->isLiveIn(ARM::CPSR))
 135       return true;
 136   }
 137   return false;
 138 }
 139
 140 void Thumb2ITBlockPass::FindITBlockRanges(MachineBasicBlock &MBB,
 141                                        SmallVector<MachineInstr*,4> &FirstUses,
 142                                        SmallVector<MachineInstr*,4> &LastUses) {
 143   bool SeenUse = false;
 144   MachineOperand *LastDef = 0;
 145   MachineOperand *LastUse = 0;
 146   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
 147   while (MBBI != E) {
 148     MachineInstr *MI = &*MBBI;
 149     ++MBBI;
 150
 151     MachineOperand *Def = 0;
 152     MachineOperand *Use = 0;
 153     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 154       MachineOperand &MO = MI->getOperand(i);
 155       if (!MO.isReg() || MO.getReg() != ARM::CPSR)
 156         continue;
 157       if (MO.isDef()) {
 158         assert(Def == 0 && "Multiple defs of CPSR?");
 159         Def = &MO;
 160       } else {
 161         assert(Use == 0 && "Multiple uses of CPSR?");
 162         Use = &MO;
 163       }
 164     }
 165
 166     if (Use) {
 167       LastUse = Use;
 168       if (!SeenUse) {
 169         FirstUses.push_back(MI);
 170         SeenUse = true;
 171       }
 172     }
 173     if (Def) {
 174       if (LastUse) {
 175         LastUses.push_back(LastUse->getParent());
 176         LastUse = 0;
 177       }
 178       LastDef = Def;
 179       SeenUse = false;
 180     }
 181   }
 182
 183   if (LastUse) {
 184     // Is the last use a kill?
 185     if (isCPSRLiveout(MBB))
 186       LastUses.push_back(0);
 187     else
 188       LastUses.push_back(LastUse->getParent());
 189   }
 190 }
 191
 192 bool Thumb2ITBlockPass::InsertITBlock(MachineInstr *First, MachineInstr *Last) {
 193   if (First == Last)
 194     return false;
 195
 196   bool Modified = false;
 197   MachineBasicBlock *MBB = First->getParent();
 198   MachineBasicBlock::iterator MBBI = First;
 199   MachineBasicBlock::iterator E = Last;
 200
 201   if (First->getDesc().isBranch() || First->getDesc().isReturn())
 202     return false;
 203
 204   unsigned PredReg = 0;
 205   ARMCC::CondCodes CC = llvm::getITInstrPredicate(First, PredReg);
 206   if (CC == ARMCC::AL)
 207     return Modified;
 208
 209   // Move uses of the CPSR together if possible.
 210   ARMCC::CondCodes OCC = ARMCC::getOppositeCondition(CC);
 211
 212   do {
 213     ++MBBI;
 214     if (MBBI->getDesc().isBranch() || MBBI->getDesc().isReturn())
 215       return Modified;
 216     MachineInstr *NMI = &*MBBI;
 217     unsigned NPredReg = 0;
 218     ARMCC::CondCodes NCC = llvm::getITInstrPredicate(NMI, NPredReg);
 219     if (NCC != CC && NCC != OCC) {
 220       if (NCC != ARMCC::AL)
 221         return Modified;
 222       assert(MBBI != E);
 223       bool Done = false;
 224       if (!MoveCPSRUseUp(*MBB, MBBI, E, PredReg, CC, OCC, Done))
 225         return Modified;
 226       Modified = true;
 227       if (Done)
 228         MBBI = E;
 229     }
 230   } while (MBBI != E);
 231   return true;
 232 }
 233
 234 bool Thumb2ITBlockPass::InsertITBlocks(MachineBasicBlock &MBB) {
 235   SmallVector<MachineInstr*, 4> FirstUses;
 236   SmallVector<MachineInstr*, 4> LastUses;
 237   FindITBlockRanges(MBB, FirstUses, LastUses);
 238   assert(FirstUses.size() == LastUses.size() && "Incorrect range information!");
 239
 240   bool Modified = false;
 241   for (unsigned i = 0, e = FirstUses.size(); i != e; ++i) {
 242     if (LastUses[i] == 0)
 243       // Must be the last pair where CPSR is live out of the block.
 244       return Modified;
 245     Modified |= InsertITBlock(FirstUses[i], LastUses[i]);
 246   }
 247   return Modified;
 248 }
 249
 250 /// TrackDefUses - Tracking what registers are being defined and used by
 251 /// instructions in the IT block. This also tracks "dependencies", i.e. uses
 252 /// in the IT block that are defined before the IT instruction.
 253 static void TrackDefUses(MachineInstr *MI,
 254                          SmallSet<unsigned, 4> &Defs,
 255                          SmallSet<unsigned, 4> &Uses,
 256                          const TargetRegisterInfo *TRI) {
 257   SmallVector<unsigned, 4> LocalDefs;
 258   SmallVector<unsigned, 4> LocalUses;
 259
 260   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 261     MachineOperand &MO = MI->getOperand(i);
 262     if (!MO.isReg())
 263       continue;
 264     unsigned Reg = MO.getReg();
 265     if (!Reg || Reg == ARM::ITSTATE || Reg == ARM::SP)
 266       continue;
 267     if (MO.isUse())
 268       LocalUses.push_back(Reg);
 269     else
 270       LocalDefs.push_back(Reg);
 271   }
 272
 273   for (unsigned i = 0, e = LocalUses.size(); i != e; ++i) {
 274     unsigned Reg = LocalUses[i];
 275     Uses.insert(Reg);
 276     for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
 277          *Subreg; ++Subreg)
 278       Uses.insert(*Subreg);
 279   }
 280
 281   for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
 282     unsigned Reg = LocalDefs[i];
 283     Defs.insert(Reg);
 284     for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
 285          *Subreg; ++Subreg)
 286       Defs.insert(*Subreg);
 287     if (Reg == ARM::CPSR)
 288       continue;
 289   }
 290 }
 291
 292 bool
 293 Thumb2ITBlockPass::MoveCopyOutOfITBlock(MachineInstr *MI,
 294                                       ARMCC::CondCodes CC, ARMCC::CondCodes OCC,
 295                                         SmallSet<unsigned, 4> &Defs,
 296                                         SmallSet<unsigned, 4> &Uses) {
 297   unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
 298   if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) {
 299     assert(SrcSubIdx == 0 && DstSubIdx == 0 &&
 300            "Sub-register indices still around?");
 301     // llvm models select's as two-address instructions. That means a copy
 302     // is inserted before a t2MOVccr, etc. If the copy is scheduled in
 303     // between selects we would end up creating multiple IT blocks.
 304
 305     // First check if it's safe to move it.
 306     if (Uses.count(DstReg) || Defs.count(SrcReg))
 307       return false;
 308
 309     // Then peek at the next instruction to see if it's predicated on CC or OCC.
 310     // If not, then there is nothing to be gained by moving the copy.
 311     MachineBasicBlock::iterator I = MI; ++I;
 312     MachineBasicBlock::iterator E = MI->getParent()->end();
 313     while (I != E && I->isDebugValue())
 314       ++I;
 315     if (I != E) {
 316       unsigned NPredReg = 0;
 317       ARMCC::CondCodes NCC = llvm::getITInstrPredicate(I, NPredReg);
 318       if (NCC == CC || NCC == OCC)
 319         return true;
 320     }
 321   }
 322   return false;
 323 }
 324
 325 bool Thumb2ITBlockPass::InsertITInstructions(MachineBasicBlock &MBB) {
 326   bool Modified = false;
 327
 328   SmallSet<unsigned, 4> Defs;
 329   SmallSet<unsigned, 4> Uses;
 330   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
 331   while (MBBI != E) {
 332     MachineInstr *MI = &*MBBI;
 333     DebugLoc dl = MI->getDebugLoc();
 334     unsigned PredReg = 0;
 335     ARMCC::CondCodes CC = llvm::getITInstrPredicate(MI, PredReg);
 336     if (CC == ARMCC::AL) {
 337       ++MBBI;
 338       continue;
 339     }
 340
 341     Defs.clear();
 342     Uses.clear();
 343     TrackDefUses(MI, Defs, Uses, TRI);
 344
 345     // Insert an IT instruction.
 346     MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(ARM::t2IT))
 347       .addImm(CC);
 348
 349     // Add implicit use of ITSTATE to IT block instructions.
 350     MI->addOperand(MachineOperand::CreateReg(ARM::ITSTATE, false/*ifDef*/,
 351                                              true/*isImp*/, false/*isKill*/));
 352
 353     MachineInstr *LastITMI = MI;
 354     MachineBasicBlock::iterator InsertPos = MIB;
 355     ++MBBI;
 356
 357     // Form IT block.
 358     ARMCC::CondCodes OCC = ARMCC::getOppositeCondition(CC);
 359     unsigned Mask = 0, Pos = 3;
 360     // Branches, including tricky ones like LDM_RET, need to end an IT
 361     // block so check the instruction we just put in the block.
 362     for (; MBBI != E && Pos &&
 363            (!MI->getDesc().isBranch() && !MI->getDesc().isReturn()) ; ++MBBI) {
 364       if (MBBI->isDebugValue())
 365         continue;
 366
 367       MachineInstr *NMI = &*MBBI;
 368       MI = NMI;
 369
 370       unsigned NPredReg = 0;
 371       ARMCC::CondCodes NCC = llvm::getITInstrPredicate(NMI, NPredReg);
 372       if (NCC == CC || NCC == OCC) {
 373         Mask |= (NCC & 1) << Pos;
 374         // Add implicit use of ITSTATE.
 375         NMI->addOperand(MachineOperand::CreateReg(ARM::ITSTATE, false/*ifDef*/,
 376                                                true/*isImp*/, false/*isKill*/));
 377         LastITMI = NMI;
 378       } else {
 379         if (NCC == ARMCC::AL &&
 380             MoveCopyOutOfITBlock(NMI, CC, OCC, Defs, Uses)) {
 381           --MBBI;
 382           MBB.remove(NMI);
 383           MBB.insert(InsertPos, NMI);
 384           ++NumMovedInsts;
 385           continue;
 386         }
 387         break;
 388       }
 389       TrackDefUses(NMI, Defs, Uses, TRI);
 390       --Pos;
 391     }
 392
 393     // Finalize IT mask.
 394     Mask |= (1 << Pos);
 395     // Tag along (firstcond[0] << 4) with the mask.
 396     Mask |= (CC & 1) << 4;
 397     MIB.addImm(Mask);
 398
 399     // Last instruction in IT block kills ITSTATE.
 400     LastITMI->findRegisterUseOperand(ARM::ITSTATE)->setIsKill();
 401
 402     Modified = true;
 403     ++NumITs;
 404   }
 405
 406   return Modified;
 407 }
 408
 409 bool Thumb2ITBlockPass::runOnMachineFunction(MachineFunction &Fn) {
 410   const TargetMachine &TM = Fn.getTarget();
 411   AFI = Fn.getInfo<ARMFunctionInfo>();
 412   TII = static_cast<const Thumb2InstrInfo*>(TM.getInstrInfo());
 413   TRI = TM.getRegisterInfo();
 414
 415   if (!AFI->isThumbFunction())
 416     return false;
 417
 418   bool Modified = false;
 419   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; ) {
 420     MachineBasicBlock &MBB = *MFI;
 421     ++MFI;
 422     if (PreRegAlloc)
 423       Modified |= InsertITBlocks(MBB);
 424     else
 425       Modified |= InsertITInstructions(MBB);
 426   }
 427
 428   if (Modified && !PreRegAlloc)
 429     AFI->setHasITBlocks(true);
 430
 431   return Modified;
 432 }
 433
 434 /// createThumb2ITBlockPass - Returns an instance of the Thumb2 IT blocks
 435 /// insertion pass.
 436 FunctionPass *llvm::createThumb2ITBlockPass(bool PreAlloc) {
 437   return new Thumb2ITBlockPass(PreAlloc);
 438 }