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