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   ISELInstructionList ISELInstructions;
  63
  64   /// Initialize the object.
  65   void initialize(MachineFunction &MFParam);
  66
  67   void handleSpecialCases(BlockISELList &BIL, MachineBasicBlock *MBB);
  68   void reorganizeBlockLayout(BlockISELList &BIL, MachineBasicBlock *MBB);
  69   void populateBlocks(BlockISELList &BIL);
  70   void expandMergeableISELs(BlockISELList &BIL);
  71   void expandAndMergeISELs();
  72
  73   bool canMerge(MachineInstr *PrevPushedMI, MachineInstr *MI);
  74
  75   ///  Is this instruction an ISEL or ISEL8?
  76   static bool isISEL(const MachineInstr &MI) {
  77     return (MI.getOpcode() == PPC::ISEL || MI.getOpcode() == PPC::ISEL8);
  78   }
  79
  80   ///  Is this instruction an ISEL8?
  81   static bool isISEL8(const MachineInstr &MI) {
  82     return (MI.getOpcode() == PPC::ISEL8);
  83   }
  84
  85   /// Are the two operands using the same register?
  86   bool useSameRegister(const MachineOperand &Op1, const MachineOperand &Op2) {
  87     return (Op1.getReg() == Op2.getReg());
  88   }
  89
  90   ///
  91   ///  Collect all ISEL instructions from the current function.
  92   ///
  93   /// Walk the current function and collect all the ISEL instructions that are
  94   /// found. The instructions are placed in the ISELInstructions vector.
  95   ///
  96   /// \return true if any ISEL instructions were found, false otherwise
  97   ///
  98   bool collectISELInstructions();
  99
 100 public:
 101   static char ID;
 102   PPCExpandISEL() : MachineFunctionPass(ID) {
 103     initializePPCExpandISELPass(*PassRegistry::getPassRegistry());
 104   }
 105
 106   ///
 107   ///  Determine whether to generate the ISEL instruction or expand it.
 108   ///
 109   /// Expand ISEL instruction into if-then-else sequence when one of
 110   /// the following two conditions hold:
 111   /// (1) -ppc-gen-isel=false
 112   /// (2) hasISEL() return false
 113   /// Otherwise, still generate ISEL instruction.
 114   /// The -ppc-gen-isel option is set to true by default. Which means the ISEL
 115   /// instruction is still generated by default on targets that support them.
 116   ///
 117   /// \return true if ISEL should be expanded into if-then-else code sequence;
 118   ///         false if ISEL instruction should be generated, i.e. not expaned.
 119   ///
 120   static bool isExpandISELEnabled(const MachineFunction &MF);
 121
 122 #ifndef NDEBUG
 123   void DumpISELInstructions() const;
 124 #endif
 125
 126   bool runOnMachineFunction(MachineFunction &MF) override {
 127     if (!isExpandISELEnabled(MF))
 128       return false;
 129
 130     DEBUG(dbgs() << "Function: "; MF.dump(); dbgs() << "\n");
 131     initialize(MF);
 132
 133     if (!collectISELInstructions()) {
 134       DEBUG(dbgs() << "No ISEL instructions in this function\n");
 135       return false;
 136     }
 137
 138 #ifndef NDEBUG
 139     DumpISELInstructions();
 140 #endif
 141
 142     expandAndMergeISELs();
 143
 144     return true;
 145   }
 146 };
 147 } // end anonymous namespace
 148
 149 void PPCExpandISEL::initialize(MachineFunction &MFParam) {
 150   MF = &MFParam;
 151   TII = MF->getSubtarget().getInstrInfo();
 152   ISELInstructions.clear();
 153 }
 154
 155 bool PPCExpandISEL::isExpandISELEnabled(const MachineFunction &MF) {
 156   return !GenerateISEL || !MF.getSubtarget<PPCSubtarget>().hasISEL();
 157 }
 158
 159 bool PPCExpandISEL::collectISELInstructions() {
 160   for (MachineBasicBlock &MBB : *MF) {
 161     BlockISELList thisBlockISELs;
 162     for (MachineInstr &MI : MBB)
 163       if (isISEL(MI))
 164         thisBlockISELs.push_back(&MI);
 165     if (!thisBlockISELs.empty())
 166       ISELInstructions.insert(std::make_pair(MBB.getNumber(), thisBlockISELs));
 167   }
 168   return !ISELInstructions.empty();
 169 }
 170
 171 #ifndef NDEBUG
 172 void PPCExpandISEL::DumpISELInstructions() const {
 173   for (const auto &I : ISELInstructions) {
 174     DEBUG(dbgs() << "BB#" << I.first << ":\n");
 175     for (const auto &VI : I.second)
 176       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   for (auto &BlockList : ISELInstructions) {
 194     DEBUG(dbgs() << "Expanding ISEL instructions in BB#" << BlockList.first
 195                  << "\n");
 196
 197     BlockISELList &CurrentISELList = BlockList.second;
 198     auto I = CurrentISELList.begin();
 199     auto E = CurrentISELList.end();
 200
 201     while (I != E) {
 202       BlockISELList SubISELList;
 203
 204       SubISELList.push_back(*I++);
 205
 206       // Collect the ISELs that can be merged together.
 207       while (I != E && canMerge(SubISELList.back(), *I))
 208         SubISELList.push_back(*I++);
 209
 210       expandMergeableISELs(SubISELList);
 211     }
 212   }
 213 }
 214
 215 void PPCExpandISEL::handleSpecialCases(BlockISELList &BIL,
 216                                        MachineBasicBlock *MBB) {
 217   IsTrueBlockRequired = false;
 218   IsFalseBlockRequired = false;
 219
 220   auto MI = BIL.begin();
 221   while (MI != BIL.end()) {
 222     assert(isISEL(**MI) && "Expecting an ISEL instruction");
 223     DEBUG(dbgs() << "ISEL: " << **MI << "\n");
 224
 225     MachineOperand &Dest = (*MI)->getOperand(0);
 226     MachineOperand &TrueValue = (*MI)->getOperand(1);
 227     MachineOperand &FalseValue = (*MI)->getOperand(2);
 228
 229     // If at least one of the ISEL instructions satisfy the following
 230     // condition, we need the True Block:
 231     // The Dest Register and True Value Register are not the same
 232     // Similarly, if at least one of the ISEL instructions satisfy the
 233     // following condition, we need the False Block:
 234     // The Dest Register and False Value Register are not the same.
 235
 236     bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
 237     bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
 238
 239     // Special case 1, all registers used by ISEL are the same one.
 240     if (!IsADDIInstRequired && !IsORIInstRequired) {
 241       DEBUG(dbgs() << "Remove redudant ISEL instruction.");
 242       NumRemoved++;
 243       (*MI)->eraseFromParent();
 244       // Setting MI to the erase result keeps the iterator valid and increased.
 245       MI = BIL.erase(MI);
 246       continue;
 247     }
 248
 249     // Special case 2, the two input registers used by ISEL are the same.
 250     // Note 1: We favor merging ISEL expansions over folding a single one. If
 251     // the passed list has multiple merge-able ISEL's, we won't fold any.
 252     // Note 2: There is no need to test for PPC::R0/PPC::X0 because PPC::ZERO/
 253     // PPC::ZERO8 will be used for the first operand if the value is meant to
 254     // be zero. In this case, the useSameRegister method will return false,
 255     // thereby preventing this ISEL from being folded.
 256
 257     if (useSameRegister(TrueValue, FalseValue) && (BIL.size() == 1)) {
 258       DEBUG(dbgs() << "Fold the ISEL instruction to an unconditonal copy.");
 259       NumFolded++;
 260       BuildMI(*MBB, (*MI), dl, TII->get(isISEL8(**MI) ? PPC::ADDI8 : PPC::ADDI))
 261           .add(Dest)
 262           .add(TrueValue)
 263           .add(MachineOperand::CreateImm(0));
 264       (*MI)->eraseFromParent();
 265       // Setting MI to the erase result keeps the iterator valid and increased.
 266       MI = BIL.erase(MI);
 267       continue;
 268     }
 269
 270     IsTrueBlockRequired |= IsADDIInstRequired;
 271     IsFalseBlockRequired |= IsORIInstRequired;
 272     MI++;
 273   }
 274 }
 275
 276 void PPCExpandISEL::reorganizeBlockLayout(BlockISELList &BIL,
 277                                           MachineBasicBlock *MBB) {
 278   if (BIL.empty())
 279     return;
 280
 281   assert((IsTrueBlockRequired || IsFalseBlockRequired) &&
 282          "Should have been handled by special cases earlier!");
 283
 284   MachineBasicBlock *Successor = nullptr;
 285   const BasicBlock *LLVM_BB = MBB->getBasicBlock();
 286   MachineBasicBlock::iterator MBBI = (*BIL.back());
 287   NewSuccessor = (MBBI != MBB->getLastNonDebugInstr() || !MBB->canFallThrough())
 288                      // Another BB is needed to move the instructions that
 289                      // follow this ISEL.  If the ISEL is the last instruction
 290                      // in a block that can't fall through, we also need a block
 291                      // to branch to.
 292                      ? MF->CreateMachineBasicBlock(LLVM_BB)
 293                      : nullptr;
 294
 295   MachineFunction::iterator It = MBB->getIterator();
 296   ++It; // Point to the successor block of MBB.
 297
 298   // If NewSuccessor is NULL then the last ISEL in this group is the last
 299   // non-debug instruction in this block. Find the fall-through successor
 300   // of this block to use when updating the CFG below.
 301   if (!NewSuccessor) {
 302     for (auto &Succ : MBB->successors()) {
 303       if (MBB->isLayoutSuccessor(Succ)) {
 304         Successor = Succ;
 305         break;
 306       }
 307     }
 308   } else
 309     Successor = NewSuccessor;
 310
 311   // The FalseBlock and TrueBlock are inserted after the MBB block but before
 312   // its successor.
 313   // Note this need to be done *after* the above setting the Successor code.
 314   if (IsFalseBlockRequired) {
 315     FalseBlock = MF->CreateMachineBasicBlock(LLVM_BB);
 316     MF->insert(It, FalseBlock);
 317   }
 318
 319   if (IsTrueBlockRequired) {
 320     TrueBlock = MF->CreateMachineBasicBlock(LLVM_BB);
 321     MF->insert(It, TrueBlock);
 322   }
 323
 324   if (NewSuccessor) {
 325     MF->insert(It, NewSuccessor);
 326
 327     // Transfer the rest of this block into the new successor block.
 328     NewSuccessor->splice(NewSuccessor->end(), MBB,
 329                          std::next(MachineBasicBlock::iterator(BIL.back())),
 330                          MBB->end());
 331     NewSuccessor->transferSuccessorsAndUpdatePHIs(MBB);
 332
 333     // Copy the original liveIns of MBB to NewSuccessor.
 334     for (auto &LI : MBB->liveins())
 335       NewSuccessor->addLiveIn(LI);
 336
 337     // After splitting the NewSuccessor block, Regs defined but not killed
 338     // in MBB should be treated as liveins of NewSuccessor.
 339     // Note: Cannot use stepBackward instead since we are using the Reg
 340     // liveness state at the end of MBB (liveOut of MBB) as the liveIn for
 341     // NewSuccessor. Otherwise, will cause cyclic dependence.
 342     LivePhysRegs LPR(MF->getSubtarget<PPCSubtarget>().getRegisterInfo());
 343     SmallVector<std::pair<unsigned, const MachineOperand *>, 2> Clobbers;
 344     for (MachineInstr &MI : *MBB)
 345       LPR.stepForward(MI, Clobbers);
 346     for (auto &LI : LPR)
 347       NewSuccessor->addLiveIn(LI);
 348   } else {
 349     // Remove successor from MBB.
 350     MBB->removeSuccessor(Successor);
 351   }
 352
 353   // Note that this needs to be done *after* transfering the successors from MBB
 354   // to the NewSuccessor block, otherwise these blocks will also be transferred
 355   // as successors!
 356   MBB->addSuccessor(IsTrueBlockRequired ? TrueBlock : Successor);
 357   MBB->addSuccessor(IsFalseBlockRequired ? FalseBlock : Successor);
 358
 359   if (IsTrueBlockRequired) {
 360     TrueBlockI = TrueBlock->begin();
 361     TrueBlock->addSuccessor(Successor);
 362   }
 363
 364   if (IsFalseBlockRequired) {
 365     FalseBlockI = FalseBlock->begin();
 366     FalseBlock->addSuccessor(Successor);
 367   }
 368
 369   // Conditional branch to the TrueBlock or Successor
 370   BuildMI(*MBB, BIL.back(), dl, TII->get(PPC::BC))
 371       .add(BIL.back()->getOperand(3))
 372       .addMBB(IsTrueBlockRequired ? TrueBlock : Successor);
 373
 374   // Jump over the true block to the new successor if the condition is false.
 375   BuildMI(*(IsFalseBlockRequired ? FalseBlock : MBB),
 376           (IsFalseBlockRequired ? FalseBlockI : BIL.back()), dl,
 377           TII->get(PPC::B))
 378       .addMBB(Successor);
 379
 380   if (IsFalseBlockRequired)
 381     FalseBlockI = FalseBlock->begin(); // get the position of PPC::B
 382 }
 383
 384 void PPCExpandISEL::populateBlocks(BlockISELList &BIL) {
 385   for (auto &MI : BIL) {
 386     assert(isISEL(*MI) && "Expecting an ISEL instruction");
 387
 388     MachineOperand &Dest = MI->getOperand(0);       // location to store to
 389     MachineOperand &TrueValue = MI->getOperand(1);  // Value to store if
 390                                                        // condition is true
 391     MachineOperand &FalseValue = MI->getOperand(2); // Value to store if
 392                                                        // condition is false
 393     MachineOperand &ConditionRegister = MI->getOperand(3); // Condition
 394
 395     DEBUG(dbgs() << "Dest: " << Dest << "\n");
 396     DEBUG(dbgs() << "TrueValue: " << TrueValue << "\n");
 397     DEBUG(dbgs() << "FalseValue: " << FalseValue << "\n");
 398     DEBUG(dbgs() << "ConditionRegister: " << ConditionRegister << "\n");
 399
 400
 401     // If the Dest Register and True Value Register are not the same one, we
 402     // need the True Block.
 403     bool IsADDIInstRequired = !useSameRegister(Dest, TrueValue);
 404     bool IsORIInstRequired = !useSameRegister(Dest, FalseValue);
 405
 406     if (IsADDIInstRequired) {
 407       // Copy the result into the destination if the condition is true.
 408       BuildMI(*TrueBlock, TrueBlockI, dl,
 409               TII->get(isISEL8(*MI) ? PPC::ADDI8 : PPC::ADDI))
 410           .add(Dest)
 411           .add(TrueValue)
 412           .add(MachineOperand::CreateImm(0));
 413
 414       // Add the LiveIn registers required by true block.
 415       TrueBlock->addLiveIn(TrueValue.getReg());
 416     }
 417
 418     if (IsORIInstRequired) {
 419       // Add the LiveIn registers required by false block.
 420       FalseBlock->addLiveIn(FalseValue.getReg());
 421     }
 422
 423     if (NewSuccessor) {
 424       // Add the LiveIn registers required by NewSuccessor block.
 425       NewSuccessor->addLiveIn(Dest.getReg());
 426       NewSuccessor->addLiveIn(TrueValue.getReg());
 427       NewSuccessor->addLiveIn(FalseValue.getReg());
 428       NewSuccessor->addLiveIn(ConditionRegister.getReg());
 429     }
 430
 431     // Copy the value into the destination if the condition is false.
 432     if (IsORIInstRequired)
 433       BuildMI(*FalseBlock, FalseBlockI, dl,
 434               TII->get(isISEL8(*MI) ? PPC::ORI8 : PPC::ORI))
 435           .add(Dest)
 436           .add(FalseValue)
 437           .add(MachineOperand::CreateImm(0));
 438
 439     MI->eraseFromParent(); // Remove the ISEL instruction.
 440
 441     NumExpanded++;
 442   }
 443 }
 444
 445 void PPCExpandISEL::expandMergeableISELs(BlockISELList &BIL) {
 446   // At this stage all the ISELs of BIL are in the same MBB.
 447   MachineBasicBlock *MBB = BIL.back()->getParent();
 448
 449   handleSpecialCases(BIL, MBB);
 450   reorganizeBlockLayout(BIL, MBB);
 451   populateBlocks(BIL);
 452 }
 453
 454 INITIALIZE_PASS(PPCExpandISEL, DEBUG_TYPE, "PowerPC Expand ISEL Generation",
 455                 false, false)
 456 char PPCExpandISEL::ID = 0;
 457
 458 FunctionPass *llvm::createPPCExpandISELPass() { return new PPCExpandISEL(); }