lib/Target/Hexagon/HexagonCopyToCombine.cpp

   1 //===------- HexagonCopyToCombine.cpp - Hexagon Copy-To-Combine Pass ------===//
   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 // This pass replaces transfer instructions by combine instructions.
  10 // We walk along a basic block and look for two combinable instructions and try
  11 // to move them together. If we can move them next to each other we do so and
  12 // replace them with a combine instruction.
  13 //===----------------------------------------------------------------------===//
  14 #define DEBUG_TYPE "hexagon-copy-combine"
  15
  16 #include "llvm/PassSupport.h"
  17 #include "llvm/CodeGen/Passes.h"
  18 #include "llvm/CodeGen/MachineBasicBlock.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/Target/TargetRegisterInfo.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/raw_ostream.h"
  27
  28 #include "Hexagon.h"
  29 #include "HexagonInstrInfo.h"
  30 #include "HexagonRegisterInfo.h"
  31 #include "HexagonSubtarget.h"
  32 #include "HexagonTargetMachine.h"
  33 #include "HexagonMachineFunctionInfo.h"
  34
  35 using namespace llvm;
  36
  37 static
  38 cl::opt<bool> IsCombinesDisabled("disable-merge-into-combines",
  39                                  cl::Hidden, cl::ZeroOrMore,
  40                                  cl::init(false),
  41                                  cl::desc("Disable merging into combines"));
  42
  43 namespace {
  44
  45 class HexagonCopyToCombine : public MachineFunctionPass  {
  46   const HexagonInstrInfo *TII;
  47   const TargetRegisterInfo *TRI;
  48 public:
  49   static char ID;
  50
  51   HexagonCopyToCombine() : MachineFunctionPass(ID) { }
  52
  53   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  54     MachineFunctionPass::getAnalysisUsage(AU);
  55   }
  56
  57   const char *getPassName() const {
  58     return "Hexagon Copy-To-Combine Pass";
  59   }
  60
  61   virtual bool runOnMachineFunction(MachineFunction &Fn);
  62
  63 private:
  64   MachineInstr *findPairable(MachineInstr *I1, bool &DoInsertAtI1);
  65
  66   void combine(MachineInstr *I1, MachineInstr *I2,
  67                MachineBasicBlock::iterator &MI, bool DoInsertAtI1);
  68
  69   bool isSafeToMoveTogether(MachineInstr *I1, MachineInstr *I2,
  70                             unsigned I1DestReg, unsigned I2DestReg,
  71                             bool &DoInsertAtI1);
  72
  73   void emitCombineRR(MachineBasicBlock::iterator &Before, unsigned DestReg,
  74                      MachineOperand &HiOperand, MachineOperand &LoOperand);
  75
  76   void emitCombineRI(MachineBasicBlock::iterator &Before, unsigned DestReg,
  77                      MachineOperand &HiOperand, MachineOperand &LoOperand);
  78
  79   void emitCombineIR(MachineBasicBlock::iterator &Before, unsigned DestReg,
  80                      MachineOperand &HiOperand, MachineOperand &LoOperand);
  81
  82   void emitCombineII(MachineBasicBlock::iterator &Before, unsigned DestReg,
  83                      MachineOperand &HiOperand, MachineOperand &LoOperand);
  84 };
  85
  86 } // End anonymous namespace.
  87
  88 char HexagonCopyToCombine::ID = 0;
  89
  90 static bool isCombinableInstType(MachineInstr *MI,
  91                                  const HexagonInstrInfo *TII) {
  92   switch(MI->getOpcode()) {
  93   case Hexagon::TFR: {
  94     // A COPY instruction can be combined if its arguments are IntRegs (32bit).
  95     assert(MI->getOperand(0).isReg() && MI->getOperand(1).isReg());
  96
  97     unsigned DestReg = MI->getOperand(0).getReg();
  98     unsigned SrcReg = MI->getOperand(1).getReg();
  99     return Hexagon::IntRegsRegClass.contains(DestReg) &&
 100       Hexagon::IntRegsRegClass.contains(SrcReg);
 101   }
 102
 103   case Hexagon::TFRI: {
 104     // A transfer-immediate can be combined if its argument is a signed 8bit
 105     // value.
 106     assert(MI->getOperand(0).isReg() && MI->getOperand(1).isImm());
 107     unsigned DestReg = MI->getOperand(0).getReg();
 108     return Hexagon::IntRegsRegClass.contains(DestReg) &&
 109       isInt<8>(MI->getOperand(1).getImm());
 110   }
 111   default:
 112     break;
 113   }
 114
 115   return false;
 116 }
 117
 118
 119 /// areCombinableOperations - Returns true if the two instruction can be merge
 120 /// into a combine (ignoring register constraints).
 121 static bool areCombinableOperations(const TargetRegisterInfo *TRI,
 122                                     MachineInstr *I1, MachineInstr *I2) {
 123   assert((I1->getOpcode() == Hexagon::TFR ||
 124           I1->getOpcode() == Hexagon::TFRI) &&
 125          (I2->getOpcode() == Hexagon::TFR ||
 126           I2->getOpcode() == Hexagon::TFRI) &&
 127          "Assume individual instructions are of a combinable type");
 128
 129   const HexagonRegisterInfo *QRI =
 130     static_cast<const HexagonRegisterInfo *>(TRI);
 131
 132   // V4 added some combine variations (mixed immediate and register source
 133   // operands), if we are on < V4 we can only combine 2 register-to-register
 134   // moves and 2 immediate-to-register moves.
 135   if (QRI->Subtarget.getHexagonArchVersion() < HexagonSubtarget::V4)
 136     return I1->getOpcode() == I2->getOpcode();
 137
 138   return true;
 139 }
 140
 141 static bool isEvenReg(unsigned Reg) {
 142   assert(TargetRegisterInfo::isPhysicalRegister(Reg) &&
 143          Hexagon::IntRegsRegClass.contains(Reg));
 144   return (Reg - Hexagon::R0) % 2 == 0;
 145 }
 146
 147 static void removeKillInfo(MachineInstr *MI, unsigned RegNotKilled) {
 148   for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) {
 149     MachineOperand &Op = MI->getOperand(I);
 150     if (!Op.isReg() || Op.getReg() != RegNotKilled || !Op.isKill())
 151       continue;
 152     Op.setIsKill(false);
 153   }
 154 }
 155
 156 /// isUnsafeToMoveAccross - Returns true if it is unsafe to move a copy
 157 /// instruction from \p UseReg to \p DestReg over the instruction \p I.
 158 bool isUnsafeToMoveAccross(MachineInstr *I, unsigned UseReg, unsigned DestReg,
 159                             const TargetRegisterInfo *TRI) {
 160   return (UseReg && (I->modifiesRegister(UseReg, TRI))) ||
 161           I->modifiesRegister(DestReg, TRI) ||
 162           I->readsRegister(DestReg, TRI) ||
 163           I->hasUnmodeledSideEffects() ||
 164           I->isInlineAsm() || I->isDebugValue();
 165 }
 166
 167 /// isSafeToMoveTogether - Returns true if it is safe to move I1 next to I2 such
 168 /// that the two instructions can be paired in a combine.
 169 bool HexagonCopyToCombine::isSafeToMoveTogether(MachineInstr *I1,
 170                                                 MachineInstr *I2,
 171                                                 unsigned I1DestReg,
 172                                                 unsigned I2DestReg,
 173                                                 bool &DoInsertAtI1) {
 174   bool isSafe = true;
 175
 176   // First try to move I2 towards I1.
 177   {
 178     // A reverse_iterator instantiated like below starts before I2, and I1
 179     // respectively.
 180     // Look at instructions I in between I2 and (including) I1.
 181     MachineBasicBlock::reverse_iterator I(I2),
 182       End = MachineBasicBlock::reverse_iterator(I1);
 183     bool IsImmUseReg = I2->getOperand(1).isImm();
 184     unsigned I2UseReg = IsImmUseReg ? 0 : I2->getOperand(1).getReg();
 185
 186     // If I2 kills its operand and we move I2 over an instruction that also
 187     // uses I2's use reg we need to modify that (first) instruction to now kill
 188     // this reg.
 189     unsigned KilledOperand = 0;
 190     if (I2->killsRegister(I2UseReg))
 191       KilledOperand = I2UseReg;
 192     MachineInstr *KillingInstr = 0;
 193
 194     for (; I != End; ++I) {
 195       // If the intervening instruction I:
 196       //   * modifies I2's use reg
 197       //   * modifies I2's def reg
 198       //   * reads I2's def reg
 199       //   * or has unmodelled side effects
 200       // we can't move I2 across it.
 201       if (isUnsafeToMoveAccross(&*I, I2UseReg, I2DestReg, TRI)) {
 202         isSafe = false;
 203         break;
 204       }
 205
 206       // Update first use of the killed operand.
 207       if (!KillingInstr && KilledOperand &&
 208           I->readsRegister(KilledOperand, TRI))
 209         KillingInstr = &*I;
 210     }
 211     if (isSafe) {
 212       // Update the intermediate instruction to with the kill flag.
 213       if (KillingInstr) {
 214         bool Added = KillingInstr->addRegisterKilled(KilledOperand, TRI, true);
 215         assert(Added && "Must successfully update kill flag");
 216         (void)Added;
 217         removeKillInfo(I2, KilledOperand);
 218       }
 219       DoInsertAtI1 = true;
 220       return true;
 221     }
 222   }
 223
 224   // Try to move I1 towards I2.
 225   {
 226     // Look at instructions I in between I1 and (including) I2.
 227     MachineBasicBlock::iterator I(I1),
 228       End(llvm::next(MachineBasicBlock::iterator(I2)));
 229     bool IsImmUseReg = I1->getOperand(1).isImm();
 230     unsigned I1UseReg = IsImmUseReg ? 0 : I1->getOperand(1).getReg();
 231     // Track killed operands. If we move accross an instruction that kills our
 232     // operand, we need to update the kill information on the moved I1. It kills
 233     // the operand now.
 234     MachineInstr *KillingInstr = 0;
 235     unsigned KilledOperand = 0;
 236
 237     while(++I != End) {
 238       // If the intervening instruction I:
 239       //   * modifies I1's use reg
 240       //   * modifies I1's def reg
 241       //   * reads I1's def reg
 242       //   * or has unmodelled side effects
 243       //   We introduce this special case because llvm has no api to remove a
 244       //   kill flag for a register (a removeRegisterKilled() analogous to
 245       //   addRegisterKilled) that handles aliased register correctly.
 246       //   * or has a killed aliased register use of I1's use reg
 247       //           %D4<def> = TFRI64 16
 248       //           %R6<def> = TFR %R9
 249       //           %R8<def> = KILL %R8, %D4<imp-use,kill>
 250       //      If we want to move R6 = across the KILL instruction we would have
 251       //      to remove the %D4<imp-use,kill> operand. For now, we are
 252       //      conservative and disallow the move.
 253       // we can't move I1 across it.
 254       if (isUnsafeToMoveAccross(I, I1UseReg, I1DestReg, TRI) ||
 255           // Check for an aliased register kill. Bail out if we see one.
 256           (!I->killsRegister(I1UseReg) && I->killsRegister(I1UseReg, TRI)))
 257         return false;
 258
 259       // Check for an exact kill (registers match).
 260       if (I1UseReg && I->killsRegister(I1UseReg)) {
 261         assert(KillingInstr == 0 && "Should only see one killing instruction");
 262         KilledOperand = I1UseReg;
 263         KillingInstr = &*I;
 264       }
 265     }
 266     if (KillingInstr) {
 267       removeKillInfo(KillingInstr, KilledOperand);
 268       // Update I1 to set the kill flag. This flag will later be picked up by
 269       // the new COMBINE instruction.
 270       bool Added = I1->addRegisterKilled(KilledOperand, TRI);
 271       assert(Added && "Must successfully update kill flag");
 272       (void)Added;
 273     }
 274     DoInsertAtI1 = false;
 275   }
 276
 277   return true;
 278 }
 279
 280 bool HexagonCopyToCombine::runOnMachineFunction(MachineFunction &MF) {
 281
 282   if (IsCombinesDisabled) return false;
 283
 284   bool HasChanged = false;
 285
 286   // Get target info.
 287   TRI = MF.getTarget().getRegisterInfo();
 288   TII = static_cast<const HexagonInstrInfo *>(MF.getTarget().getInstrInfo());
 289
 290   // Traverse basic blocks.
 291   for (MachineFunction::iterator BI = MF.begin(), BE = MF.end(); BI != BE;
 292        ++BI) {
 293     // Traverse instructions in basic block.
 294     for(MachineBasicBlock::iterator MI = BI->begin(), End = BI->end();
 295         MI != End;) {
 296       MachineInstr *I1 = MI++;
 297
 298       // Ignore instructions that are not combinable.
 299       if (!isCombinableInstType(I1, TII))
 300         continue;
 301
 302       // Find a second instruction that can be merged into a combine
 303       // instruction.
 304       bool DoInsertAtI1 = false;
 305       MachineInstr *I2 = findPairable(I1, DoInsertAtI1);
 306       if (I2) {
 307         HasChanged = true;
 308         combine(I1, I2, MI, DoInsertAtI1);
 309       }
 310     }
 311   }
 312
 313   return HasChanged;
 314 }
 315
 316 /// findPairable - Returns an instruction that can be merged with \p I1 into a
 317 /// COMBINE instruction or 0 if no such instruction can be found. Returns true
 318 /// in \p DoInsertAtI1 if the combine must be inserted at instruction \p I1
 319 /// false if the combine must be inserted at the returned instruction.
 320 MachineInstr *HexagonCopyToCombine::findPairable(MachineInstr *I1,
 321                                                  bool &DoInsertAtI1) {
 322   MachineBasicBlock::iterator I2 = llvm::next(MachineBasicBlock::iterator(I1));
 323   unsigned I1DestReg = I1->getOperand(0).getReg();
 324
 325   for (MachineBasicBlock::iterator End = I1->getParent()->end(); I2 != End;
 326        ++I2) {
 327     // Bail out early if we see a second definition of I1DestReg.
 328     if (I2->modifiesRegister(I1DestReg, TRI))
 329       break;
 330
 331     // Ignore non-combinable instructions.
 332     if (!isCombinableInstType(I2, TII))
 333       continue;
 334
 335     unsigned I2DestReg = I2->getOperand(0).getReg();
 336
 337     // Check that registers are adjacent and that the first destination register
 338     // is even.
 339     bool IsI1BeforeI2 = (I2DestReg - I1DestReg) == 1;
 340     bool IsI2BeforeI1 = (I1DestReg - I2DestReg) == 1;
 341     unsigned FirstRegIndex = IsI1BeforeI2 ? I1DestReg : I2DestReg;
 342     if ((!IsI1BeforeI2 && !IsI2BeforeI1) || !isEvenReg(FirstRegIndex))
 343       continue;
 344
 345     // Check that the two instructions are combinable. V4 allows more
 346     // instructions to be merged into a combine.
 347     if (!areCombinableOperations(TRI, I1, I2))
 348       break;
 349
 350     if (isSafeToMoveTogether(I1, I2, I1DestReg, I2DestReg,
 351                              DoInsertAtI1))
 352       return I2;
 353
 354     // Not safe. Stop searching.
 355     break;
 356   }
 357   return 0;
 358 }
 359
 360 void HexagonCopyToCombine::combine(MachineInstr *I1, MachineInstr *I2,
 361                                    MachineBasicBlock::iterator &MI,
 362                                    bool DoInsertAtI1) {
 363   // We are going to delete I2. If MI points to I2 advance it to the next
 364   // instruction.
 365   if ((MachineInstr *)MI == I2) ++MI;
 366
 367   // Figure out whether I1 or I2 goes into the lowreg part.
 368   unsigned I1DestReg = I1->getOperand(0).getReg();
 369   unsigned I2DestReg = I2->getOperand(0).getReg();
 370   bool IsI1Loreg = (I2DestReg - I1DestReg) == 1;
 371   unsigned LoRegDef = IsI1Loreg ? I1DestReg : I2DestReg;
 372
 373   // Get the double word register.
 374   unsigned DoubleRegDest =
 375     TRI->getMatchingSuperReg(LoRegDef, Hexagon::subreg_loreg,
 376                              Hexagon::DoubleRegsRegisterClass);
 377   assert(DoubleRegDest != 0 && "Expect a valid register");
 378
 379
 380   // Setup source operands.
 381   MachineOperand &LoOperand = IsI1Loreg ? I1->getOperand(1) :
 382     I2->getOperand(1);
 383   MachineOperand &HiOperand = IsI1Loreg ? I2->getOperand(1) :
 384     I1->getOperand(1);
 385
 386   // Figure out which source is a register and which a constant.
 387   bool IsHiReg = HiOperand.isReg();
 388   bool IsLoReg = LoOperand.isReg();
 389
 390   MachineBasicBlock::iterator InsertPt(DoInsertAtI1 ? I1 : I2);
 391   // Emit combine.
 392   if (IsHiReg && IsLoReg)
 393     emitCombineRR(InsertPt, DoubleRegDest, HiOperand, LoOperand);
 394   else if (IsHiReg)
 395     emitCombineRI(InsertPt, DoubleRegDest, HiOperand, LoOperand);
 396   else if (IsLoReg)
 397     emitCombineIR(InsertPt, DoubleRegDest, HiOperand, LoOperand);
 398   else
 399     emitCombineII(InsertPt, DoubleRegDest, HiOperand, LoOperand);
 400
 401   I1->eraseFromParent();
 402   I2->eraseFromParent();
 403 }
 404
 405 void HexagonCopyToCombine::emitCombineII(MachineBasicBlock::iterator &InsertPt,
 406                                          unsigned DoubleDestReg,
 407                                          MachineOperand &HiOperand,
 408                                          MachineOperand &LoOperand) {
 409   DebugLoc DL = InsertPt->getDebugLoc();
 410   MachineBasicBlock *BB = InsertPt->getParent();
 411
 412   // Insert new combine instruction.
 413   //  DoubleRegDest = combine #HiImm, #LoImm
 414   BuildMI(*BB, InsertPt, DL, TII->get(Hexagon::COMBINE_ii), DoubleDestReg)
 415     .addImm(HiOperand.getImm())
 416     .addImm(LoOperand.getImm());
 417 }
 418
 419 void HexagonCopyToCombine::emitCombineIR(MachineBasicBlock::iterator &InsertPt,
 420                                          unsigned DoubleDestReg,
 421                                          MachineOperand &HiOperand,
 422                                          MachineOperand &LoOperand) {
 423   unsigned LoReg = LoOperand.getReg();
 424   unsigned LoRegKillFlag = getKillRegState(LoOperand.isKill());
 425
 426   DebugLoc DL = InsertPt->getDebugLoc();
 427   MachineBasicBlock *BB = InsertPt->getParent();
 428
 429   // Insert new combine instruction.
 430   //  DoubleRegDest = combine #HiImm, LoReg
 431   BuildMI(*BB, InsertPt, DL, TII->get(Hexagon::COMBINE_ir_V4), DoubleDestReg)
 432     .addImm(HiOperand.getImm())
 433     .addReg(LoReg, LoRegKillFlag);
 434 }
 435
 436 void HexagonCopyToCombine::emitCombineRI(MachineBasicBlock::iterator &InsertPt,
 437                                          unsigned DoubleDestReg,
 438                                          MachineOperand &HiOperand,
 439                                          MachineOperand &LoOperand) {
 440   unsigned HiRegKillFlag = getKillRegState(HiOperand.isKill());
 441   unsigned HiReg = HiOperand.getReg();
 442
 443   DebugLoc DL = InsertPt->getDebugLoc();
 444   MachineBasicBlock *BB = InsertPt->getParent();
 445
 446   // Insert new combine instruction.
 447   //  DoubleRegDest = combine HiReg, #LoImm
 448   BuildMI(*BB, InsertPt, DL, TII->get(Hexagon::COMBINE_ri_V4), DoubleDestReg)
 449     .addReg(HiReg, HiRegKillFlag)
 450     .addImm(LoOperand.getImm());
 451 }
 452
 453 void HexagonCopyToCombine::emitCombineRR(MachineBasicBlock::iterator &InsertPt,
 454                                          unsigned DoubleDestReg,
 455                                          MachineOperand &HiOperand,
 456                                          MachineOperand &LoOperand) {
 457   unsigned LoRegKillFlag = getKillRegState(LoOperand.isKill());
 458   unsigned HiRegKillFlag = getKillRegState(HiOperand.isKill());
 459   unsigned LoReg = LoOperand.getReg();
 460   unsigned HiReg = HiOperand.getReg();
 461
 462   DebugLoc DL = InsertPt->getDebugLoc();
 463   MachineBasicBlock *BB = InsertPt->getParent();
 464
 465   // Insert new combine instruction.
 466   //  DoubleRegDest = combine HiReg, LoReg
 467   BuildMI(*BB, InsertPt, DL, TII->get(Hexagon::COMBINE_rr), DoubleDestReg)
 468     .addReg(HiReg, HiRegKillFlag)
 469     .addReg(LoReg, LoRegKillFlag);
 470 }
 471
 472 FunctionPass *llvm::createHexagonCopyToCombine() {
 473   return new HexagonCopyToCombine();
 474 }
 475