lib/CodeGen/MachineSink.cpp

   1 //===-- MachineSink.cpp - Sinking for machine instructions ----------------===//
   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 // This pass moves instructions into successor blocks when possible, so that
  11 // they aren't executed on paths where their results aren't needed.
  12 //
  13 // This pass is not intended to be a replacement or a complete alternative
  14 // for an LLVM-IR-level sinking pass. It is only designed to sink simple
  15 // constructs that are not exposed before lowering and instruction selection.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #define DEBUG_TYPE "machine-sink"
  20 #include "llvm/CodeGen/Passes.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/CodeGen/MachineDominators.h"
  23 #include "llvm/CodeGen/MachineLoopInfo.h"
  24 #include "llvm/Analysis/AliasAnalysis.h"
  25 #include "llvm/Target/TargetRegisterInfo.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27 #include "llvm/Target/TargetMachine.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include "llvm/Support/CommandLine.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Support/raw_ostream.h"
  32 using namespace llvm;
  33
  34 static cl::opt<bool>
  35 SplitEdges("machine-sink-split",
  36            cl::desc("Split critical edges during machine sinking"),
  37            cl::init(false), cl::Hidden);
  38 static cl::opt<unsigned>
  39 SplitLimit("split-limit",
  40            cl::init(~0u), cl::Hidden);
  41
  42 STATISTIC(NumSunk,  "Number of machine instructions sunk");
  43 STATISTIC(NumSplit, "Number of critical edges split");
  44
  45 namespace {
  46   class MachineSinking : public MachineFunctionPass {
  47     const TargetInstrInfo *TII;
  48     const TargetRegisterInfo *TRI;
  49     MachineRegisterInfo  *RegInfo; // Machine register information
  50     MachineDominatorTree *DT;   // Machine dominator tree
  51     MachineLoopInfo *LI;
  52     AliasAnalysis *AA;
  53     BitVector AllocatableSet;   // Which physregs are allocatable?
  54
  55   public:
  56     static char ID; // Pass identification
  57     MachineSinking() : MachineFunctionPass(ID) {}
  58
  59     virtual bool runOnMachineFunction(MachineFunction &MF);
  60
  61     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  62       AU.setPreservesCFG();
  63       MachineFunctionPass::getAnalysisUsage(AU);
  64       AU.addRequired<AliasAnalysis>();
  65       AU.addRequired<MachineDominatorTree>();
  66       AU.addRequired<MachineLoopInfo>();
  67       AU.addPreserved<MachineDominatorTree>();
  68       AU.addPreserved<MachineLoopInfo>();
  69     }
  70   private:
  71     bool ProcessBlock(MachineBasicBlock &MBB);
  72     MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *From,
  73                                          MachineBasicBlock *To);
  74     bool SinkInstruction(MachineInstr *MI, bool &SawStore);
  75     bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
  76                                MachineBasicBlock *DefMBB, bool &LocalUse) const;
  77   };
  78 } // end anonymous namespace
  79
  80 char MachineSinking::ID = 0;
  81 INITIALIZE_PASS(MachineSinking, "machine-sink",
  82                 "Machine code sinking", false, false);
  83
  84 FunctionPass *llvm::createMachineSinkingPass() { return new MachineSinking(); }
  85
  86 /// AllUsesDominatedByBlock - Return true if all uses of the specified register
  87 /// occur in blocks dominated by the specified block. If any use is in the
  88 /// definition block, then return false since it is never legal to move def
  89 /// after uses.
  90 bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg,
  91                                              MachineBasicBlock *MBB,
  92                                              MachineBasicBlock *DefMBB,
  93                                              bool &LocalUse) const {
  94   assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
  95          "Only makes sense for vregs");
  96   // Ignoring debug uses is necessary so debug info doesn't affect the code.
  97   // This may leave a referencing dbg_value in the original block, before
  98   // the definition of the vreg.  Dwarf generator handles this although the
  99   // user might not get the right info at runtime.
 100   for (MachineRegisterInfo::use_nodbg_iterator
 101          I = RegInfo->use_nodbg_begin(Reg), E = RegInfo->use_nodbg_end();
 102        I != E; ++I) {
 103     // Determine the block of the use.
 104     MachineInstr *UseInst = &*I;
 105     MachineBasicBlock *UseBlock = UseInst->getParent();
 106
 107     if (UseInst->isPHI()) {
 108       // PHI nodes use the operand in the predecessor block, not the block with
 109       // the PHI.
 110       UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB();
 111     } else if (UseBlock == DefMBB) {
 112       LocalUse = true;
 113       return false;
 114     }
 115
 116     // Check that it dominates.
 117     if (!DT->dominates(MBB, UseBlock))
 118       return false;
 119   }
 120
 121   return true;
 122 }
 123
 124 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
 125   DEBUG(dbgs() << "******** Machine Sinking ********\n");
 126
 127   const TargetMachine &TM = MF.getTarget();
 128   TII = TM.getInstrInfo();
 129   TRI = TM.getRegisterInfo();
 130   RegInfo = &MF.getRegInfo();
 131   DT = &getAnalysis<MachineDominatorTree>();
 132   LI = &getAnalysis<MachineLoopInfo>();
 133   AA = &getAnalysis<AliasAnalysis>();
 134   AllocatableSet = TRI->getAllocatableSet(MF);
 135
 136   bool EverMadeChange = false;
 137
 138   while (1) {
 139     bool MadeChange = false;
 140
 141     // Process all basic blocks.
 142     for (MachineFunction::iterator I = MF.begin(), E = MF.end();
 143          I != E; ++I)
 144       MadeChange |= ProcessBlock(*I);
 145
 146     // If this iteration over the code changed anything, keep iterating.
 147     if (!MadeChange) break;
 148     EverMadeChange = true;
 149   }
 150   return EverMadeChange;
 151 }
 152
 153 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
 154   // Can't sink anything out of a block that has less than two successors.
 155   if (MBB.succ_size() <= 1 || MBB.empty()) return false;
 156
 157   // Don't bother sinking code out of unreachable blocks. In addition to being
 158   // unprofitable, it can also lead to infinite looping, because in an
 159   // unreachable loop there may be nowhere to stop.
 160   if (!DT->isReachableFromEntry(&MBB)) return false;
 161
 162   bool MadeChange = false;
 163
 164   // Walk the basic block bottom-up.  Remember if we saw a store.
 165   MachineBasicBlock::iterator I = MBB.end();
 166   --I;
 167   bool ProcessedBegin, SawStore = false;
 168   do {
 169     MachineInstr *MI = I;  // The instruction to sink.
 170
 171     // Predecrement I (if it's not begin) so that it isn't invalidated by
 172     // sinking.
 173     ProcessedBegin = I == MBB.begin();
 174     if (!ProcessedBegin)
 175       --I;
 176
 177     if (MI->isDebugValue())
 178       continue;
 179
 180     if (SinkInstruction(MI, SawStore))
 181       ++NumSunk, MadeChange = true;
 182
 183     // If we just processed the first instruction in the block, we're done.
 184   } while (!ProcessedBegin);
 185
 186   return MadeChange;
 187 }
 188
 189 MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineBasicBlock *FromBB,
 190                                                      MachineBasicBlock *ToBB) {
 191   // Avoid breaking back edge. From == To means backedge for single BB loop.
 192   if (!SplitEdges || NumSplit == SplitLimit || FromBB == ToBB)
 193     return 0;
 194
 195   // Check for more "complex" loops.
 196   if (LI->getLoopFor(FromBB) != LI->getLoopFor(ToBB) ||
 197       !LI->isLoopHeader(ToBB)) {
 198     // It's not always legal to break critical edges and sink the computation
 199     // to the edge.
 200     //
 201     // BB#1:
 202     // v1024
 203     // Beq BB#3
 204     // <fallthrough>
 205     // BB#2:
 206     // ... no uses of v1024
 207     // <fallthrough>
 208     // BB#3:
 209     // ...
 210     //       = v1024
 211     //
 212     // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted:
 213     //
 214     // BB#1:
 215     // ...
 216     // Bne BB#2
 217     // BB#4:
 218     // v1024 =
 219     // B BB#3
 220     // BB#2:
 221     // ... no uses of v1024
 222     // <fallthrough>
 223     // BB#3:
 224     // ...
 225     //       = v1024
 226     //
 227     // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3
 228     // flow. We need to ensure the new basic block where the computation is
 229     // sunk to dominates all the uses.
 230     // It's only legal to break critical edge and sink the computation to the
 231     // new block if all the predecessors of "To", except for "From", are
 232     // not dominated by "From". Given SSA property, this means these
 233     // predecessors are dominated by "To".
 234     for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(),
 235            E = ToBB->pred_end(); PI != E; ++PI) {
 236       if (*PI == FromBB)
 237         continue;
 238       if (!DT->dominates(ToBB, *PI))
 239         return 0;
 240     }
 241
 242     // FIXME: Determine if it's cost effective to break this edge.
 243     return FromBB->SplitCriticalEdge(ToBB, this);
 244   }
 245
 246   return 0;
 247 }
 248
 249 /// SinkInstruction - Determine whether it is safe to sink the specified machine
 250 /// instruction out of its current block into a successor.
 251 bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) {
 252   // Check if it's safe to move the instruction.
 253   if (!MI->isSafeToMove(TII, AA, SawStore))
 254     return false;
 255
 256   // FIXME: This should include support for sinking instructions within the
 257   // block they are currently in to shorten the live ranges.  We often get
 258   // instructions sunk into the top of a large block, but it would be better to
 259   // also sink them down before their first use in the block.  This xform has to
 260   // be careful not to *increase* register pressure though, e.g. sinking
 261   // "x = y + z" down if it kills y and z would increase the live ranges of y
 262   // and z and only shrink the live range of x.
 263
 264   // Loop over all the operands of the specified instruction.  If there is
 265   // anything we can't handle, bail out.
 266   MachineBasicBlock *ParentBlock = MI->getParent();
 267
 268   // SuccToSinkTo - This is the successor to sink this instruction to, once we
 269   // decide.
 270   MachineBasicBlock *SuccToSinkTo = 0;
 271
 272   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 273     const MachineOperand &MO = MI->getOperand(i);
 274     if (!MO.isReg()) continue;  // Ignore non-register operands.
 275
 276     unsigned Reg = MO.getReg();
 277     if (Reg == 0) continue;
 278
 279     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 280       if (MO.isUse()) {
 281         // If the physreg has no defs anywhere, it's just an ambient register
 282         // and we can freely move its uses. Alternatively, if it's allocatable,
 283         // it could get allocated to something with a def during allocation.
 284         if (!RegInfo->def_empty(Reg))
 285           return false;
 286
 287         if (AllocatableSet.test(Reg))
 288           return false;
 289
 290         // Check for a def among the register's aliases too.
 291         for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
 292           unsigned AliasReg = *Alias;
 293           if (!RegInfo->def_empty(AliasReg))
 294             return false;
 295
 296           if (AllocatableSet.test(AliasReg))
 297             return false;
 298         }
 299       } else if (!MO.isDead()) {
 300         // A def that isn't dead. We can't move it.
 301         return false;
 302       }
 303     } else {
 304       // Virtual register uses are always safe to sink.
 305       if (MO.isUse()) continue;
 306
 307       // If it's not safe to move defs of the register class, then abort.
 308       if (!TII->isSafeToMoveRegClassDefs(RegInfo->getRegClass(Reg)))
 309         return false;
 310
 311       // FIXME: This picks a successor to sink into based on having one
 312       // successor that dominates all the uses.  However, there are cases where
 313       // sinking can happen but where the sink point isn't a successor.  For
 314       // example:
 315       //
 316       //   x = computation
 317       //   if () {} else {}
 318       //   use x
 319       //
 320       // the instruction could be sunk over the whole diamond for the
 321       // if/then/else (or loop, etc), allowing it to be sunk into other blocks
 322       // after that.
 323
 324       // Virtual register defs can only be sunk if all their uses are in blocks
 325       // dominated by one of the successors.
 326       if (SuccToSinkTo) {
 327         // If a previous operand picked a block to sink to, then this operand
 328         // must be sinkable to the same block.
 329         bool LocalUse = false;
 330         if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, ParentBlock, LocalUse))
 331           return false;
 332
 333         continue;
 334       }
 335
 336       // Otherwise, we should look at all the successors and decide which one
 337       // we should sink to.
 338       for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(),
 339            E = ParentBlock->succ_end(); SI != E; ++SI) {
 340         bool LocalUse = false;
 341         if (AllUsesDominatedByBlock(Reg, *SI, ParentBlock, LocalUse)) {
 342           SuccToSinkTo = *SI;
 343           break;
 344         }
 345         if (LocalUse)
 346           // Def is used locally, it's never safe to move this def.
 347           return false;
 348       }
 349
 350       // If we couldn't find a block to sink to, ignore this instruction.
 351       if (SuccToSinkTo == 0)
 352         return false;
 353     }
 354   }
 355
 356   // If there are no outputs, it must have side-effects.
 357   if (SuccToSinkTo == 0)
 358     return false;
 359
 360   // It's not safe to sink instructions to EH landing pad. Control flow into
 361   // landing pad is implicitly defined.
 362   if (SuccToSinkTo->isLandingPad())
 363     return false;
 364
 365   // It is not possible to sink an instruction into its own block.  This can
 366   // happen with loops.
 367   if (MI->getParent() == SuccToSinkTo)
 368     return false;
 369
 370   // If the instruction to move defines a dead physical register which is live
 371   // when leaving the basic block, don't move it because it could turn into a
 372   // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>)
 373   for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) {
 374     const MachineOperand &MO = MI->getOperand(I);
 375     if (!MO.isReg()) continue;
 376     unsigned Reg = MO.getReg();
 377     if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
 378     if (SuccToSinkTo->isLiveIn(Reg))
 379       return false;
 380   }
 381
 382   DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo);
 383
 384   // If the block has multiple predecessors, this would introduce computation on
 385   // a path that it doesn't already exist.  We could split the critical edge,
 386   // but for now we just punt.
 387   // FIXME: Split critical edges if not backedges.
 388   if (SuccToSinkTo->pred_size() > 1) {
 389     // We cannot sink a load across a critical edge - there may be stores in
 390     // other code paths.
 391     bool TryBreak = false;
 392     bool store = true;
 393     if (!MI->isSafeToMove(TII, AA, store)) {
 394       DEBUG(dbgs() << " *** PUNTING: Won't sink load along critical edge.\n");
 395       TryBreak = true;
 396     }
 397
 398     // We don't want to sink across a critical edge if we don't dominate the
 399     // successor. We could be introducing calculations to new code paths.
 400     if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) {
 401       DEBUG(dbgs() << " *** PUNTING: Critical edge found\n");
 402       TryBreak = true;
 403     }
 404
 405     // Don't sink instructions into a loop.
 406     if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
 407       DEBUG(dbgs() << " *** PUNTING: Loop header found\n");
 408       TryBreak = true;
 409     }
 410
 411     // Otherwise we are OK with sinking along a critical edge.
 412     if (!TryBreak)
 413       DEBUG(dbgs() << "Sinking along critical edge.\n");
 414     else {
 415       MachineBasicBlock *NewSucc = SplitCriticalEdge(ParentBlock, SuccToSinkTo);
 416       if (!NewSucc) {
 417         DEBUG(dbgs() <<
 418               " *** PUNTING: Not legal or profitable to break critical edge\n");
 419         return false;
 420       } else {
 421         DEBUG(dbgs() << "*** Splitting critical edge:"
 422               " BB#" << ParentBlock->getNumber()
 423               << " -- BB#" << NewSucc->getNumber()
 424               << " -- BB#" << SuccToSinkTo->getNumber() << '\n');
 425         SuccToSinkTo = NewSucc;
 426         ++NumSplit;
 427       }
 428     }
 429   }
 430
 431   // Determine where to insert into. Skip phi nodes.
 432   MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
 433   while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
 434     ++InsertPos;
 435
 436   // Move the instruction.
 437   SuccToSinkTo->splice(InsertPos, ParentBlock, MI,
 438                        ++MachineBasicBlock::iterator(MI));
 439
 440   // Conservatively, clear any kill flags, since it's possible that they are no
 441   // longer correct.
 442   MI->clearKillInfo();
 443
 444   return true;
 445 }