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 expaned.
 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     DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
 130     initialize(MF);
 131
 132     if (!collectISELInstructions()) {
 133       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     DEBUG(dbgs() << printMBBReference(*MF->getBlockNumbered(I.first)) << ":\n");
 174     for (const auto &VI : I.second)
 175       DEBUG(dbgs() << "    "; VI->print(dbgs()));
 176   }
 177 }
 178 #endif
 179
 180 /// Contiguous ISELs that have the same condition can be merged.
 181 bool PPCExpandISEL::canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI) {
 182   // Same Condition Register?
 183   if (!useSameRegister(PrevPushedMI->getOperand(3), MI->getOperand(3)))
 184     return false;
 185
 186   MachineBasicBlock::iterator PrevPushedMBBI = *PrevPushedMI;
 187   MachineBasicBlock::iterator MBBI = *MI;
 188   return (std::prev(MBBI) == PrevPushedMBBI); // Contiguous ISELs?
 189 }
 190
 191 void PPCExpandISEL::expandAndMergeISELs() {
 192   bool ExpandISELEnabled = isExpandISELEnabled(*MF);
 193
 194   for (auto &BlockList : ISELInstructions) {
 195     DEBUG(dbgs() << "Expanding ISEL instructions in "
 196                  << printMBBReference(*MF->getBlockNumbered(BlockList.first))
 197                  << "\n");
 198     BlockISELList &CurrentISELList = BlockList.second;
 199     auto I = CurrentISELList.begin();
 200     auto E = CurrentISELList.end();
 201
 202     while (I != E) {
 203       assert(isISEL(**I) && "Expecting an ISEL instruction");
 204       MachineOperand &Dest = (*I)->getOperand(0);
 205       MachineOperand &TrueValue = (*I)->getOperand(1);
 206       MachineOperand &FalseValue = (*I)->getOperand(2);
 207
 208       // Special case 1, all registers used by ISEL are the same one.
 209       // The non-redundant isel 0, 0, 0, N would not satisfy these conditions
 210       // as it would be ISEL %R0, %ZERO, %R0, %CRN.
 211       if (useSameRegister(Dest, TrueValue) &&
 212           useSameRegister(Dest, FalseValue)) {
 213         DEBUG(dbgs() << "Remove redudant ISEL instruction: " << **I << "\n");
 214         // FIXME: if the CR field used has no other uses, we could eliminate the
 215         // instruction that defines it. This would have to be done manually
 216         // since this pass runs too late to run DCE after it.
 217         NumRemoved++;
 218         (*I)->eraseFromParent();
 219         I++;
 220       } else if (useSameRegister(TrueValue, FalseValue)) {
 221         // Special case 2, the two input registers used by ISEL are the same.
 222         // Note: the non-foldable isel RX, 0, 0, N would not satisfy this
 223         // condition as it would be ISEL %RX, %ZERO, %R0, %CRN, which makes it
 224         // safe to fold ISEL to MR(OR) instead of ADDI.
 225         MachineBasicBlock *MBB = (*I)->getParent();
 226         DEBUG(dbgs() << "Fold the ISEL instruction to an unconditonal copy:\n");
 227         DEBUG(dbgs() << "ISEL: " << **I << "\n");
 228         NumFolded++;
 229         // Note: we're using both the TrueValue and FalseValue operands so as
 230         // not to lose the kill flag if it is set on either of them.
 231         BuildMI(*MBB, (*I), dl, TII->get(isISEL8(**I) ? PPC::OR8 : PPC::OR))
 232             .add(Dest)
 233             .add(TrueValue)
 234             .add(FalseValue);
 235         (*I)->eraseFromParent();
 236         I++;
 237       } else if (ExpandISELEnabled) { // Normal cases expansion enabled
 238         DEBUG(dbgs() << "Expand ISEL instructions:\n");
 239         DEBUG(dbgs() << "ISEL: " << **I << "\n");
 240         BlockISELList SubISELList;
 241         SubISELList.push_back(*I++);
 242         // Collect the ISELs that can be merged together.
 243         // This will eat up ISEL instructions without considering whether they
 244         // may be redundant or foldable to a register copy. So we still keep
 245         // the handleSpecialCases() downstream to handle them.
 246         while (I != E && canMerge(SubISELList.back(), *I)) {
 247           DEBUG(dbgs() << "ISEL: " << **I << "\n");
 248           SubISELList.push_back(*I++);
 249         }
 250
 251         expandMergeableISELs(SubISELList);
 252       } else { // Normal cases expansion disabled
 253         I++; // leave the ISEL as it is
 254       }
 255     } // end while
 256   } // end for
 257 }
 258
 259 void PPCExpandISEL::handleSpecialCases(BlockISELList &BIL,
 260                                        MachineBasicBlock *MBB) {
 261   IsTrueBlockRequired = false;
 262   IsFalseBlockRequired = false;
 263
 264   auto MI = BIL.begin();
 265   while (MI != BIL.end()) {
 266     assert(isISEL(**MI) && "Expecting an ISEL instruction");
 267     DEBUG(dbgs() << "ISEL: " << **MI << "\n");
 268
 269     MachineOperand &Dest = (*MI)->getOperand(0);
 270     MachineOperand &TrueValue = (*MI)->getOperand(1);
 271     MachineOperand &FalseValue = (*MI)->getOperand(2);
 272
 273     // If at least one of the ISEL instructions satisfy the following
 274     // condition, we need the True Block:
 275     // The Dest Register and True Value Register are not the same
 276     // Similarly, if at least one of the ISEL instructions satisfy the
 277     // following condition, we need the False Block:
 278     // The Dest Register and False Value Register are not the same.
 279     bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
 280     bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
 281
 282     // Special case 1, all registers used by ISEL are the same one.
 283     if (!IsADDIInstRequired && !IsORIInstRequired) {
 284       DEBUG(dbgs() << "Remove redudant ISEL instruction.");
 285       // FIXME: if the CR field used has no other uses, we could eliminate the
 286       // instruction that defines it. This would have to be done manually
 287       // since this pass runs too late to run DCE after it.
 288       NumRemoved++;
 289       (*MI)->eraseFromParent();
 290       // Setting MI to the erase result keeps the iterator valid and increased.
 291       MI = BIL.erase(MI);
 292       continue;
 293     }
 294
 295     // Special case 2, the two input registers used by ISEL are the same.
 296     // Note 1: We favor merging ISEL expansions over folding a single one. If
 297     // the passed list has multiple merge-able ISEL's, we won't fold any.
 298     // Note 2: There is no need to test for PPC::R0/PPC::X0 because PPC::ZERO/
 299     // PPC::ZERO8 will be used for the first operand if the value is meant to
 300     // be zero. In this case, the useSameRegister method will return false,
 301     // thereby preventing this ISEL from being folded.
 302     if (useSameRegister(TrueValue, FalseValue) && (BIL.size() == 1)) {
 303       DEBUG(dbgs() << "Fold the ISEL instruction to an unconditonal copy.");
 304       NumFolded++;
 305       // Note: we're using both the TrueValue and FalseValue operands so as
 306       // not to lose the kill flag if it is set on either of them.
 307       BuildMI(*MBB, (*MI), dl, TII->get(isISEL8(**MI) ? PPC::OR8 : PPC::OR))
 308           .add(Dest)
 309           .add(TrueValue)
 310           .add(FalseValue);
 311       (*MI)->eraseFromParent();
 312       // Setting MI to the erase result keeps the iterator valid and increased.
 313       MI = BIL.erase(MI);
 314       continue;
 315     }
 316
 317     IsTrueBlockRequired |= IsADDIInstRequired;
 318     IsFalseBlockRequired |= IsORIInstRequired;
 319     MI++;
 320   }
 321 }
 322
 323 void PPCExpandISEL::reorganizeBlockLayout(BlockISELList &BIL,
 324                                           MachineBasicBlock *MBB) {
 325   if (BIL.empty())
 326     return;
 327
 328   assert((IsTrueBlockRequired || IsFalseBlockRequired) &&
 329          "Should have been handled by special cases earlier!");
 330
 331   MachineBasicBlock *Successor = nullptr;
 332   const BasicBlock *LLVM_BB = MBB->getBasicBlock();
 333   MachineBasicBlock::iterator MBBI = (*BIL.back());
 334   NewSuccessor = (MBBI != MBB->getLastNonDebugInstr() || !MBB->canFallThrough())
 335                      // Another BB is needed to move the instructions that
 336                      // follow this ISEL.  If the ISEL is the last instruction
 337                      // in a block that can't fall through, we also need a block
 338                      // to branch to.
 339                      ? MF->CreateMachineBasicBlock(LLVM_BB)
 340                      : nullptr;
 341
 342   MachineFunction::iterator It = MBB->getIterator();
 343   ++It; // Point to the successor block of MBB.
 344
 345   // If NewSuccessor is NULL then the last ISEL in this group is the last
 346   // non-debug instruction in this block. Find the fall-through successor
 347   // of this block to use when updating the CFG below.
 348   if (!NewSuccessor) {
 349     for (auto &Succ : MBB->successors()) {
 350       if (MBB->isLayoutSuccessor(Succ)) {
 351         Successor = Succ;
 352         break;
 353       }
 354     }
 355   } else
 356     Successor = NewSuccessor;
 357
 358   // The FalseBlock and TrueBlock are inserted after the MBB block but before
 359   // its successor.
 360   // Note this need to be done *after* the above setting the Successor code.
 361   if (IsFalseBlockRequired) {
 362     FalseBlock = MF->CreateMachineBasicBlock(LLVM_BB);
 363     MF->insert(It, FalseBlock);
 364   }
 365
 366   if (IsTrueBlockRequired) {
 367     TrueBlock = MF->CreateMachineBasicBlock(LLVM_BB);
 368     MF->insert(It, TrueBlock);
 369   }
 370
 371   if (NewSuccessor) {
 372     MF->insert(It, NewSuccessor);
 373
 374     // Transfer the rest of this block into the new successor block.
 375     NewSuccessor->splice(NewSuccessor->end(), MBB,
 376                          std::next(MachineBasicBlock::iterator(BIL.back())),
 377                          MBB->end());
 378     NewSuccessor->transferSuccessorsAndUpdatePHIs(MBB);
 379
 380     // Copy the original liveIns of MBB to NewSuccessor.
 381     for (auto &LI : MBB->liveins())
 382       NewSuccessor->addLiveIn(LI);
 383
 384     // After splitting the NewSuccessor block, Regs defined but not killed
 385     // in MBB should be treated as liveins of NewSuccessor.
 386     // Note: Cannot use stepBackward instead since we are using the Reg
 387     // liveness state at the end of MBB (liveOut of MBB) as the liveIn for
 388     // NewSuccessor. Otherwise, will cause cyclic dependence.
 389     LivePhysRegs LPR(*MF->getSubtarget<PPCSubtarget>().getRegisterInfo());
 390     SmallVector<std::pair<unsigned, const MachineOperand *>, 2> Clobbers;
 391     for (MachineInstr &MI : *MBB)
 392       LPR.stepForward(MI, Clobbers);
 393     for (auto &LI : LPR)
 394       NewSuccessor->addLiveIn(LI);
 395   } else {
 396     // Remove successor from MBB.
 397     MBB->removeSuccessor(Successor);
 398   }
 399
 400   // Note that this needs to be done *after* transfering the successors from MBB
 401   // to the NewSuccessor block, otherwise these blocks will also be transferred
 402   // as successors!
 403   MBB->addSuccessor(IsTrueBlockRequired ? TrueBlock : Successor);
 404   MBB->addSuccessor(IsFalseBlockRequired ? FalseBlock : Successor);
 405
 406   if (IsTrueBlockRequired) {
 407     TrueBlockI = TrueBlock->begin();
 408     TrueBlock->addSuccessor(Successor);
 409   }
 410
 411   if (IsFalseBlockRequired) {
 412     FalseBlockI = FalseBlock->begin();
 413     FalseBlock->addSuccessor(Successor);
 414   }
 415
 416   // Conditional branch to the TrueBlock or Successor
 417   BuildMI(*MBB, BIL.back(), dl, TII->get(PPC::BC))
 418       .add(BIL.back()->getOperand(3))
 419       .addMBB(IsTrueBlockRequired ? TrueBlock : Successor);
 420
 421   // Jump over the true block to the new successor if the condition is false.
 422   BuildMI(*(IsFalseBlockRequired ? FalseBlock : MBB),
 423           (IsFalseBlockRequired ? FalseBlockI : BIL.back()), dl,
 424           TII->get(PPC::B))
 425       .addMBB(Successor);
 426
 427   if (IsFalseBlockRequired)
 428     FalseBlockI = FalseBlock->begin(); // get the position of PPC::B
 429 }
 430
 431 void PPCExpandISEL::populateBlocks(BlockISELList &BIL) {
 432   for (auto &MI : BIL) {
 433     assert(isISEL(*MI) && "Expecting an ISEL instruction");
 434
 435     MachineOperand &Dest = MI->getOperand(0);       // location to store to
 436     MachineOperand &TrueValue = MI->getOperand(1);  // Value to store if
 437                                                        // condition is true
 438     MachineOperand &FalseValue = MI->getOperand(2); // Value to store if
 439                                                        // condition is false
 440     MachineOperand &ConditionRegister = MI->getOperand(3); // Condition
 441
 442     DEBUG(dbgs() << "Dest: " << Dest << "\n");
 443     DEBUG(dbgs() << "TrueValue: " << TrueValue << "\n");
 444     DEBUG(dbgs() << "FalseValue: " << FalseValue << "\n");
 445     DEBUG(dbgs() << "ConditionRegister: " << ConditionRegister << "\n");
 446
 447
 448     // If the Dest Register and True Value Register are not the same one, we
 449     // need the True Block.
 450     bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
 451     bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
 452
 453     if (IsADDIInstRequired) {
 454       // Copy the result into the destination if the condition is true.
 455       BuildMI(*TrueBlock, TrueBlockI, dl,
 456               TII->get(isISEL8(*MI) ? PPC::ADDI8 : PPC::ADDI))
 457           .add(Dest)
 458           .add(TrueValue)
 459           .add(MachineOperand::CreateImm(0));
 460
 461       // Add the LiveIn registers required by true block.
 462       TrueBlock->addLiveIn(TrueValue.getReg());
 463     }
 464
 465     if (IsORIInstRequired) {
 466       // Add the LiveIn registers required by false block.
 467       FalseBlock->addLiveIn(FalseValue.getReg());
 468     }
 469
 470     if (NewSuccessor) {
 471       // Add the LiveIn registers required by NewSuccessor block.
 472       NewSuccessor->addLiveIn(Dest.getReg());
 473       NewSuccessor->addLiveIn(TrueValue.getReg());
 474       NewSuccessor->addLiveIn(FalseValue.getReg());
 475       NewSuccessor->addLiveIn(ConditionRegister.getReg());
 476     }
 477
 478     // Copy the value into the destination if the condition is false.
 479     if (IsORIInstRequired)
 480       BuildMI(*FalseBlock, FalseBlockI, dl,
 481               TII->get(isISEL8(*MI) ? PPC::ORI8 : PPC::ORI))
 482           .add(Dest)
 483           .add(FalseValue)
 484           .add(MachineOperand::CreateImm(0));
 485
 486     MI->eraseFromParent(); // Remove the ISEL instruction.
 487
 488     NumExpanded++;
 489   }
 490 }
 491
 492 void PPCExpandISEL::expandMergeableISELs(BlockISELList &BIL) {
 493   // At this stage all the ISELs of BIL are in the same MBB.
 494   MachineBasicBlock *MBB = BIL.back()->getParent();
 495
 496   handleSpecialCases(BIL, MBB);
 497   reorganizeBlockLayout(BIL, MBB);
 498   populateBlocks(BIL);
 499 }
 500
 501 INITIALIZE_PASS(PPCExpandISEL, DEBUG_TYPE, "PowerPC Expand ISEL Generation",
 502                 false, false)
 503 char PPCExpandISEL::ID = 0;
 504
 505 FunctionPass *llvm::createPPCExpandISELPass() { return new PPCExpandISEL(); }