contrib/llvm/lib/Target/PowerPC/PPCExpandISEL.cpp

   1 //===------------- PPCExpandISEL.cpp - Expand ISEL instruction ------------===//
   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 // A pass that expands the ISEL instruction into an if-then-else sequence.
  11 // This pass must be run post-RA since all operands must be physical registers.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "PPC.h"
  16 #include "PPCInstrInfo.h"
  17 #include "PPCSubtarget.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/CodeGen/LivePhysRegs.h"
  21 #include "llvm/CodeGen/MachineFunctionPass.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/raw_ostream.h"
  27
  28 using namespace llvm;
  29
  30 #define DEBUG_TYPE "ppc-expand-isel"
  31
  32 STATISTIC(NumExpanded, "Number of ISEL instructions expanded");
  33 STATISTIC(NumRemoved, "Number of ISEL instructions removed");
  34 STATISTIC(NumFolded, "Number of ISEL instructions folded");
  35
  36 // If -ppc-gen-isel=false is set, we will disable generating the ISEL
  37 // instruction on all PPC targets. Otherwise, if the user set option
  38 // -misel or the platform supports ISEL by default, still generate the
  39 // ISEL instruction, else expand it.
  40 static cl::opt<bool>
  41     GenerateISEL("ppc-gen-isel",
  42                  cl::desc("Enable generating the ISEL instruction."),
  43                  cl::init(true), cl::Hidden);
  44
  45 namespace {
  46 class PPCExpandISEL : public MachineFunctionPass {
  47   DebugLoc dl;
  48   MachineFunction *MF;
  49   const TargetInstrInfo *TII;
  50   bool IsTrueBlockRequired;
  51   bool IsFalseBlockRequired;
  52   MachineBasicBlock *TrueBlock;
  53   MachineBasicBlock *FalseBlock;
  54   MachineBasicBlock *NewSuccessor;
  55   MachineBasicBlock::iterator TrueBlockI;
  56   MachineBasicBlock::iterator FalseBlockI;
  57
  58   typedef SmallVector<MachineInstr *, 4> BlockISELList;
  59   typedef SmallDenseMap<int, BlockISELList> ISELInstructionList;
  60
  61   // A map of MBB numbers to their lists of contained ISEL instructions.
  62   // Please note when we traverse this list and expand ISEL, we only remove
  63   // the ISEL from the MBB not from this list.
  64   ISELInstructionList ISELInstructions;
  65
  66   /// Initialize the object.
  67   void initialize(MachineFunction &MFParam);
  68
  69   void handleSpecialCases(BlockISELList &BIL, MachineBasicBlock *MBB);
  70   void reorganizeBlockLayout(BlockISELList &BIL, MachineBasicBlock *MBB);
  71   void populateBlocks(BlockISELList &BIL);
  72   void expandMergeableISELs(BlockISELList &BIL);
  73   void expandAndMergeISELs();
  74
  75   bool canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI);
  76
  77   ///  Is this instruction an ISEL or ISEL8?
  78   static bool isISEL(const MachineInstr &MI) {
  79     return (MI.getOpcode() == PPC::ISEL || MI.getOpcode() == PPC::ISEL8);
  80   }
  81
  82   ///  Is this instruction an ISEL8?
  83   static bool isISEL8(const MachineInstr &MI) {
  84     return (MI.getOpcode() == PPC::ISEL8);
  85   }
  86
  87   /// Are the two operands using the same register?
  88   bool useSameRegister(const MachineOperand &Op1, const MachineOperand &Op2) {
  89     return (Op1.getReg() == Op2.getReg());
  90   }
  91
  92   ///
  93   ///  Collect all ISEL instructions from the current function.
  94   ///
  95   /// Walk the current function and collect all the ISEL instructions that are
  96   /// found. The instructions are placed in the ISELInstructions vector.
  97   ///
  98   /// \return true if any ISEL instructions were found, false otherwise
  99   ///
 100   bool collectISELInstructions();
 101
 102 public:
 103   static char ID;
 104   PPCExpandISEL() : MachineFunctionPass(ID) {
 105     initializePPCExpandISELPass(*PassRegistry::getPassRegistry());
 106   }
 107
 108   ///
 109   ///  Determine whether to generate the ISEL instruction or expand it.
 110   ///
 111   /// Expand ISEL instruction into if-then-else sequence when one of
 112   /// the following two conditions hold:
 113   /// (1) -ppc-gen-isel=false
 114   /// (2) hasISEL() return false
 115   /// Otherwise, still generate ISEL instruction.
 116   /// The -ppc-gen-isel option is set to true by default. Which means the ISEL
 117   /// instruction is still generated by default on targets that support them.
 118   ///
 119   /// \return true if ISEL should be expanded into if-then-else code sequence;
 120   ///         false if ISEL instruction should be generated, i.e. not expanded.
 121   ///
 122   static bool isExpandISELEnabled(const MachineFunction &MF);
 123
 124 #ifndef NDEBUG
 125   void DumpISELInstructions() const;
 126 #endif
 127
 128   bool runOnMachineFunction(MachineFunction &MF) override {
 129     LLVM_DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
 130     initialize(MF);
 131
 132     if (!collectISELInstructions()) {
 133       LLVM_DEBUG(dbgs() << "No ISEL instructions in this function\n");
 134       return false;
 135     }
 136
 137 #ifndef NDEBUG
 138     DumpISELInstructions();
 139 #endif
 140
 141     expandAndMergeISELs();
 142
 143     return true;
 144   }
 145 };
 146 } // end anonymous namespace
 147
 148 void PPCExpandISEL::initialize(MachineFunction &MFParam) {
 149   MF = &MFParam;
 150   TII = MF->getSubtarget().getInstrInfo();
 151   ISELInstructions.clear();
 152 }
 153
 154 bool PPCExpandISEL::isExpandISELEnabled(const MachineFunction &MF) {
 155   return !GenerateISEL || !MF.getSubtarget<PPCSubtarget>().hasISEL();
 156 }
 157
 158 bool PPCExpandISEL::collectISELInstructions() {
 159   for (MachineBasicBlock &MBB : *MF) {
 160     BlockISELList thisBlockISELs;
 161     for (MachineInstr &MI : MBB)
 162       if (isISEL(MI))
 163         thisBlockISELs.push_back(&MI);
 164     if (!thisBlockISELs.empty())
 165       ISELInstructions.insert(std::make_pair(MBB.getNumber(), thisBlockISELs));
 166   }
 167   return !ISELInstructions.empty();
 168 }
 169
 170 #ifndef NDEBUG
 171 void PPCExpandISEL::DumpISELInstructions() const {
 172   for (const auto &I : ISELInstructions) {
 173     LLVM_DEBUG(dbgs() << printMBBReference(*MF->getBlockNumbered(I.first))
 174                       << ":\n");
 175     for (const auto &VI : I.second)
 176       LLVM_DEBUG(dbgs() << "    "; VI->print(dbgs()));
 177   }
 178 }
 179 #endif
 180
 181 /// Contiguous ISELs that have the same condition can be merged.
 182 bool PPCExpandISEL::canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI) {
 183   // Same Condition Register?
 184   if (!useSameRegister(PrevPushedMI->getOperand(3), MI->getOperand(3)))
 185     return false;
 186
 187   MachineBasicBlock::iterator PrevPushedMBBI = *PrevPushedMI;
 188   MachineBasicBlock::iterator MBBI = *MI;
 189   return (std::prev(MBBI) == PrevPushedMBBI); // Contiguous ISELs?
 190 }
 191
 192 void PPCExpandISEL::expandAndMergeISELs() {
 193   bool ExpandISELEnabled = isExpandISELEnabled(*MF);
 194
 195   for (auto &BlockList : ISELInstructions) {
 196     LLVM_DEBUG(
 197         dbgs() << "Expanding ISEL instructions in "
 198                << printMBBReference(*MF->getBlockNumbered(BlockList.first))
 199                << "\n");
 200     BlockISELList &CurrentISELList = BlockList.second;
 201     auto I = CurrentISELList.begin();
 202     auto E = CurrentISELList.end();
 203
 204     while (I != E) {
 205       assert(isISEL(**I) && "Expecting an ISEL instruction");
 206       MachineOperand &Dest = (*I)->getOperand(0);
 207       MachineOperand &TrueValue = (*I)->getOperand(1);
 208       MachineOperand &FalseValue = (*I)->getOperand(2);
 209
 210       // Special case 1, all registers used by ISEL are the same one.
 211       // The non-redundant isel 0, 0, 0, N would not satisfy these conditions
 212       // as it would be ISEL %R0, %ZERO, %R0, %CRN.
 213       if (useSameRegister(Dest, TrueValue) &&
 214           useSameRegister(Dest, FalseValue)) {
 215         LLVM_DEBUG(dbgs() << "Remove redundant ISEL instruction: " << **I
 216                           << "\n");
 217         // FIXME: if the CR field used has no other uses, we could eliminate the
 218         // instruction that defines it. This would have to be done manually
 219         // since this pass runs too late to run DCE after it.
 220         NumRemoved++;
 221         (*I)->eraseFromParent();
 222         I++;
 223       } else if (useSameRegister(TrueValue, FalseValue)) {
 224         // Special case 2, the two input registers used by ISEL are the same.
 225         // Note: the non-foldable isel RX, 0, 0, N would not satisfy this
 226         // condition as it would be ISEL %RX, %ZERO, %R0, %CRN, which makes it
 227         // safe to fold ISEL to MR(OR) instead of ADDI.
 228         MachineBasicBlock *MBB = (*I)->getParent();
 229         LLVM_DEBUG(
 230             dbgs() << "Fold the ISEL instruction to an unconditional copy:\n");
 231         LLVM_DEBUG(dbgs() << "ISEL: " << **I << "\n");
 232         NumFolded++;
 233         // Note: we're using both the TrueValue and FalseValue operands so as
 234         // not to lose the kill flag if it is set on either of them.
 235         BuildMI(*MBB, (*I), dl, TII->get(isISEL8(**I) ? PPC::OR8 : PPC::OR))
 236             .add(Dest)
 237             .add(TrueValue)
 238             .add(FalseValue);
 239         (*I)->eraseFromParent();
 240         I++;
 241       } else if (ExpandISELEnabled) { // Normal cases expansion enabled
 242         LLVM_DEBUG(dbgs() << "Expand ISEL instructions:\n");
 243         LLVM_DEBUG(dbgs() << "ISEL: " << **I << "\n");
 244         BlockISELList SubISELList;
 245         SubISELList.push_back(*I++);
 246         // Collect the ISELs that can be merged together.
 247         // This will eat up ISEL instructions without considering whether they
 248         // may be redundant or foldable to a register copy. So we still keep
 249         // the handleSpecialCases() downstream to handle them.
 250         while (I != E && canMerge(SubISELList.back(), *I)) {
 251           LLVM_DEBUG(dbgs() << "ISEL: " << **I << "\n");
 252           SubISELList.push_back(*I++);
 253         }
 254
 255         expandMergeableISELs(SubISELList);
 256       } else { // Normal cases expansion disabled
 257         I++; // leave the ISEL as it is
 258       }
 259     } // end while
 260   } // end for
 261 }
 262
 263 void PPCExpandISEL::handleSpecialCases(BlockISELList &BIL,
 264                                        MachineBasicBlock *MBB) {
 265   IsTrueBlockRequired = false;
 266   IsFalseBlockRequired = false;
 267
 268   auto MI = BIL.begin();
 269   while (MI != BIL.end()) {
 270     assert(isISEL(**MI) && "Expecting an ISEL instruction");
 271     LLVM_DEBUG(dbgs() << "ISEL: " << **MI << "\n");
 272
 273     MachineOperand &Dest = (*MI)->getOperand(0);
 274     MachineOperand &TrueValue = (*MI)->getOperand(1);
 275     MachineOperand &FalseValue = (*MI)->getOperand(2);
 276
 277     // If at least one of the ISEL instructions satisfy the following
 278     // condition, we need the True Block:
 279     // The Dest Register and True Value Register are not the same
 280     // Similarly, if at least one of the ISEL instructions satisfy the
 281     // following condition, we need the False Block:
 282     // The Dest Register and False Value Register are not the same.
 283     bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
 284     bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
 285
 286     // Special case 1, all registers used by ISEL are the same one.
 287     if (!IsADDIInstRequired && !IsORIInstRequired) {
 288       LLVM_DEBUG(dbgs() << "Remove redundant ISEL instruction.");
 289       // FIXME: if the CR field used has no other uses, we could eliminate the
 290       // instruction that defines it. This would have to be done manually
 291       // since this pass runs too late to run DCE after it.
 292       NumRemoved++;
 293       (*MI)->eraseFromParent();
 294       // Setting MI to the erase result keeps the iterator valid and increased.
 295       MI = BIL.erase(MI);
 296       continue;
 297     }
 298
 299     // Special case 2, the two input registers used by ISEL are the same.
 300     // Note 1: We favor merging ISEL expansions over folding a single one. If
 301     // the passed list has multiple merge-able ISEL's, we won't fold any.
 302     // Note 2: There is no need to test for PPC::R0/PPC::X0 because PPC::ZERO/
 303     // PPC::ZERO8 will be used for the first operand if the value is meant to
 304     // be zero. In this case, the useSameRegister method will return false,
 305     // thereby preventing this ISEL from being folded.
 306     if (useSameRegister(TrueValue, FalseValue) && (BIL.size() == 1)) {
 307       LLVM_DEBUG(
 308           dbgs() << "Fold the ISEL instruction to an unconditional copy.");
 309       NumFolded++;
 310       // Note: we're using both the TrueValue and FalseValue operands so as
 311       // not to lose the kill flag if it is set on either of them.
 312       BuildMI(*MBB, (*MI), dl, TII->get(isISEL8(**MI) ? PPC::OR8 : PPC::OR))
 313           .add(Dest)
 314           .add(TrueValue)
 315           .add(FalseValue);
 316       (*MI)->eraseFromParent();
 317       // Setting MI to the erase result keeps the iterator valid and increased.
 318       MI = BIL.erase(MI);
 319       continue;
 320     }
 321
 322     IsTrueBlockRequired |= IsADDIInstRequired;
 323     IsFalseBlockRequired |= IsORIInstRequired;
 324     MI++;
 325   }
 326 }
 327
 328 void PPCExpandISEL::reorganizeBlockLayout(BlockISELList &BIL,
 329                                           MachineBasicBlock *MBB) {
 330   if (BIL.empty())
 331     return;
 332
 333   assert((IsTrueBlockRequired || IsFalseBlockRequired) &&
 334          "Should have been handled by special cases earlier!");
 335
 336   MachineBasicBlock *Successor = nullptr;
 337   const BasicBlock *LLVM_BB = MBB->getBasicBlock();
 338   MachineBasicBlock::iterator MBBI = (*BIL.back());
 339   NewSuccessor = (MBBI != MBB->getLastNonDebugInstr() || !MBB->canFallThrough())
 340                      // Another BB is needed to move the instructions that
 341                      // follow this ISEL.  If the ISEL is the last instruction
 342                      // in a block that can't fall through, we also need a block
 343                      // to branch to.
 344                      ? MF->CreateMachineBasicBlock(LLVM_BB)
 345                      : nullptr;
 346
 347   MachineFunction::iterator It = MBB->getIterator();
 348   ++It; // Point to the successor block of MBB.
 349
 350   // If NewSuccessor is NULL then the last ISEL in this group is the last
 351   // non-debug instruction in this block. Find the fall-through successor
 352   // of this block to use when updating the CFG below.
 353   if (!NewSuccessor) {
 354     for (auto &Succ : MBB->successors()) {
 355       if (MBB->isLayoutSuccessor(Succ)) {
 356         Successor = Succ;
 357         break;
 358       }
 359     }
 360   } else
 361     Successor = NewSuccessor;
 362
 363   // The FalseBlock and TrueBlock are inserted after the MBB block but before
 364   // its successor.
 365   // Note this need to be done *after* the above setting the Successor code.
 366   if (IsFalseBlockRequired) {
 367     FalseBlock = MF->CreateMachineBasicBlock(LLVM_BB);
 368     MF->insert(It, FalseBlock);
 369   }
 370
 371   if (IsTrueBlockRequired) {
 372     TrueBlock = MF->CreateMachineBasicBlock(LLVM_BB);
 373     MF->insert(It, TrueBlock);
 374   }
 375
 376   if (NewSuccessor) {
 377     MF->insert(It, NewSuccessor);
 378
 379     // Transfer the rest of this block into the new successor block.
 380     NewSuccessor->splice(NewSuccessor->end(), MBB,
 381                          std::next(MachineBasicBlock::iterator(BIL.back())),
 382                          MBB->end());
 383     NewSuccessor->transferSuccessorsAndUpdatePHIs(MBB);
 384
 385     // Copy the original liveIns of MBB to NewSuccessor.
 386     for (auto &LI : MBB->liveins())
 387       NewSuccessor->addLiveIn(LI);
 388
 389     // After splitting the NewSuccessor block, Regs defined but not killed
 390     // in MBB should be treated as liveins of NewSuccessor.
 391     // Note: Cannot use stepBackward instead since we are using the Reg
 392     // liveness state at the end of MBB (liveOut of MBB) as the liveIn for
 393     // NewSuccessor. Otherwise, will cause cyclic dependence.
 394     LivePhysRegs LPR(*MF->getSubtarget<PPCSubtarget>().getRegisterInfo());
 395     SmallVector<std::pair<MCPhysReg, const MachineOperand *>, 2> Clobbers;
 396     for (MachineInstr &MI : *MBB)
 397       LPR.stepForward(MI, Clobbers);
 398     for (auto &LI : LPR)
 399       NewSuccessor->addLiveIn(LI);
 400   } else {
 401     // Remove successor from MBB.
 402     MBB->removeSuccessor(Successor);
 403   }
 404
 405   // Note that this needs to be done *after* transfering the successors from MBB
 406   // to the NewSuccessor block, otherwise these blocks will also be transferred
 407   // as successors!
 408   MBB->addSuccessor(IsTrueBlockRequired ? TrueBlock : Successor);
 409   MBB->addSuccessor(IsFalseBlockRequired ? FalseBlock : Successor);
 410
 411   if (IsTrueBlockRequired) {
 412     TrueBlockI = TrueBlock->begin();
 413     TrueBlock->addSuccessor(Successor);
 414   }
 415
 416   if (IsFalseBlockRequired) {
 417     FalseBlockI = FalseBlock->begin();
 418     FalseBlock->addSuccessor(Successor);
 419   }
 420
 421   // Conditional branch to the TrueBlock or Successor
 422   BuildMI(*MBB, BIL.back(), dl, TII->get(PPC::BC))
 423       .add(BIL.back()->getOperand(3))
 424       .addMBB(IsTrueBlockRequired ? TrueBlock : Successor);
 425
 426   // Jump over the true block to the new successor if the condition is false.
 427   BuildMI(*(IsFalseBlockRequired ? FalseBlock : MBB),
 428           (IsFalseBlockRequired ? FalseBlockI : BIL.back()), dl,
 429           TII->get(PPC::B))
 430       .addMBB(Successor);
 431
 432   if (IsFalseBlockRequired)
 433     FalseBlockI = FalseBlock->begin(); // get the position of PPC::B
 434 }
 435
 436 void PPCExpandISEL::populateBlocks(BlockISELList &BIL) {
 437   for (auto &MI : BIL) {
 438     assert(isISEL(*MI) && "Expecting an ISEL instruction");
 439
 440     MachineOperand &Dest = MI->getOperand(0);       // location to store to
 441     MachineOperand &TrueValue = MI->getOperand(1);  // Value to store if
 442                                                        // condition is true
 443     MachineOperand &FalseValue = MI->getOperand(2); // Value to store if
 444                                                        // condition is false
 445     MachineOperand &ConditionRegister = MI->getOperand(3); // Condition
 446
 447     LLVM_DEBUG(dbgs() << "Dest: " << Dest << "\n");
 448     LLVM_DEBUG(dbgs() << "TrueValue: " << TrueValue << "\n");
 449     LLVM_DEBUG(dbgs() << "FalseValue: " << FalseValue << "\n");
 450     LLVM_DEBUG(dbgs() << "ConditionRegister: " << ConditionRegister << "\n");
 451
 452     // If the Dest Register and True Value Register are not the same one, we
 453     // need the True Block.
 454     bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
 455     bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
 456
 457     if (IsADDIInstRequired) {
 458       // Copy the result into the destination if the condition is true.
 459       BuildMI(*TrueBlock, TrueBlockI, dl,
 460               TII->get(isISEL8(*MI) ? PPC::ADDI8 : PPC::ADDI))
 461           .add(Dest)
 462           .add(TrueValue)
 463           .add(MachineOperand::CreateImm(0));
 464
 465       // Add the LiveIn registers required by true block.
 466       TrueBlock->addLiveIn(TrueValue.getReg());
 467     }
 468
 469     if (IsORIInstRequired) {
 470       // Add the LiveIn registers required by false block.
 471       FalseBlock->addLiveIn(FalseValue.getReg());
 472     }
 473
 474     if (NewSuccessor) {
 475       // Add the LiveIn registers required by NewSuccessor block.
 476       NewSuccessor->addLiveIn(Dest.getReg());
 477       NewSuccessor->addLiveIn(TrueValue.getReg());
 478       NewSuccessor->addLiveIn(FalseValue.getReg());
 479       NewSuccessor->addLiveIn(ConditionRegister.getReg());
 480     }
 481
 482     // Copy the value into the destination if the condition is false.
 483     if (IsORIInstRequired)
 484       BuildMI(*FalseBlock, FalseBlockI, dl,
 485               TII->get(isISEL8(*MI) ? PPC::ORI8 : PPC::ORI))
 486           .add(Dest)
 487           .add(FalseValue)
 488           .add(MachineOperand::CreateImm(0));
 489
 490     MI->eraseFromParent(); // Remove the ISEL instruction.
 491
 492     NumExpanded++;
 493   }
 494 }
 495
 496 void PPCExpandISEL::expandMergeableISELs(BlockISELList &BIL) {
 497   // At this stage all the ISELs of BIL are in the same MBB.
 498   MachineBasicBlock *MBB = BIL.back()->getParent();
 499
 500   handleSpecialCases(BIL, MBB);
 501   reorganizeBlockLayout(BIL, MBB);
 502   populateBlocks(BIL);
 503 }
 504
 505 INITIALIZE_PASS(PPCExpandISEL, DEBUG_TYPE, "PowerPC Expand ISEL Generation",
 506                 false, false)
 507 char PPCExpandISEL::ID = 0;
 508
 509 FunctionPass *llvm::createPPCExpandISELPass() { return new PPCExpandISEL(); }