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