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