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