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     if (UseBlock == DefMBB) {
 107       LocalUse = true;
 108       return false;
 109     }
 110
 111     if (UseInst->isPHI()) {
 112       // PHI nodes use the operand in the predecessor block, not the block with
 113       // the PHI.
 114       UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB();
 115     }
 116
 117     // Check that it dominates.
 118     if (!DT->dominates(MBB, UseBlock))
 119       return false;
 120   }
 121
 122   return true;
 123 }
 124
 125 bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
 126   DEBUG(dbgs() << "******** Machine Sinking ********\n");
 127
 128   const TargetMachine &TM = MF.getTarget();
 129   TII = TM.getInstrInfo();
 130   TRI = TM.getRegisterInfo();
 131   RegInfo = &MF.getRegInfo();
 132   DT = &getAnalysis<MachineDominatorTree>();
 133   LI = &getAnalysis<MachineLoopInfo>();
 134   AA = &getAnalysis<AliasAnalysis>();
 135   AllocatableSet = TRI->getAllocatableSet(MF);
 136
 137   bool EverMadeChange = false;
 138
 139   while (1) {
 140     bool MadeChange = false;
 141
 142     // Process all basic blocks.
 143     for (MachineFunction::iterator I = MF.begin(), E = MF.end();
 144          I != E; ++I)
 145       MadeChange |= ProcessBlock(*I);
 146
 147     // If this iteration over the code changed anything, keep iterating.
 148     if (!MadeChange) break;
 149     EverMadeChange = true;
 150   }
 151   return EverMadeChange;
 152 }
 153
 154 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
 155   // Can't sink anything out of a block that has less than two successors.
 156   if (MBB.succ_size() <= 1 || MBB.empty()) return false;
 157
 158   // Don't bother sinking code out of unreachable blocks. In addition to being
 159   // unprofitable, it can also lead to infinite looping, because in an
 160   // unreachable loop there may be nowhere to stop.
 161   if (!DT->isReachableFromEntry(&MBB)) return false;
 162
 163   bool MadeChange = false;
 164
 165   // Walk the basic block bottom-up.  Remember if we saw a store.
 166   MachineBasicBlock::iterator I = MBB.end();
 167   --I;
 168   bool ProcessedBegin, SawStore = false;
 169   do {
 170     MachineInstr *MI = I;  // The instruction to sink.
 171
 172     // Predecrement I (if it's not begin) so that it isn't invalidated by
 173     // sinking.
 174     ProcessedBegin = I == MBB.begin();
 175     if (!ProcessedBegin)
 176       --I;
 177
 178     if (MI->isDebugValue())
 179       continue;
 180
 181     if (SinkInstruction(MI, SawStore))
 182       ++NumSunk, MadeChange = true;
 183
 184     // If we just processed the first instruction in the block, we're done.
 185   } while (!ProcessedBegin);
 186
 187   return MadeChange;
 188 }
 189
 190 MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineBasicBlock *FromBB,
 191                                                      MachineBasicBlock *ToBB) {
 192   // Avoid breaking back edge. From == To means backedge for single BB loop.
 193   if (!SplitEdges || NumSplit == SplitLimit || FromBB == ToBB)
 194     return 0;
 195
 196   // Check for more "complex" loops.
 197   if (LI->getLoopFor(FromBB) != LI->getLoopFor(ToBB) ||
 198       !LI->isLoopHeader(ToBB)) {
 199     // It's not always legal to break critical edges and sink the computation
 200     // to the edge.
 201     //
 202     // BB#1:
 203     // v1024
 204     // Beq BB#3
 205     // <fallthrough>
 206     // BB#2:
 207     // ... no uses of v1024
 208     // <fallthrough>
 209     // BB#3:
 210     // ...
 211     //       = v1024
 212     //
 213     // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted:
 214     //
 215     // BB#1:
 216     // ...
 217     // Bne BB#2
 218     // BB#4:
 219     // v1024 =
 220     // B BB#3
 221     // BB#2:
 222     // ... no uses of v1024
 223     // <fallthrough>
 224     // BB#3:
 225     // ...
 226     //       = v1024
 227     //
 228     // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3
 229     // flow. We need to ensure the new basic block where the computation is
 230     // sunk to dominates all the uses.
 231     // It's only legal to break critical edge and sink the computation to the
 232     // new block if all the predecessors of "To", except for "From", are
 233     // not dominated by "From". Given SSA property, this means these
 234     // predecessors are dominated by "To".
 235     for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(),
 236            E = ToBB->pred_end(); PI != E; ++PI) {
 237       if (*PI == FromBB)
 238         continue;
 239       if (!DT->dominates(ToBB, *PI))
 240         return 0;
 241     }
 242
 243     // FIXME: Determine if it's cost effective to break this edge.
 244     return FromBB->SplitCriticalEdge(ToBB, this);
 245   }
 246
 247   return 0;
 248 }
 249
 250 /// SinkInstruction - Determine whether it is safe to sink the specified machine
 251 /// instruction out of its current block into a successor.
 252 bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) {
 253   // Check if it's safe to move the instruction.
 254   if (!MI->isSafeToMove(TII, AA, SawStore))
 255     return false;
 256
 257   // FIXME: This should include support for sinking instructions within the
 258   // block they are currently in to shorten the live ranges.  We often get
 259   // instructions sunk into the top of a large block, but it would be better to
 260   // also sink them down before their first use in the block.  This xform has to
 261   // be careful not to *increase* register pressure though, e.g. sinking
 262   // "x = y + z" down if it kills y and z would increase the live ranges of y
 263   // and z and only shrink the live range of x.
 264
 265   // Loop over all the operands of the specified instruction.  If there is
 266   // anything we can't handle, bail out.
 267   MachineBasicBlock *ParentBlock = MI->getParent();
 268
 269   // SuccToSinkTo - This is the successor to sink this instruction to, once we
 270   // decide.
 271   MachineBasicBlock *SuccToSinkTo = 0;
 272
 273   bool LocalUse = false;
 274   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 275     const MachineOperand &MO = MI->getOperand(i);
 276     if (!MO.isReg()) continue;  // Ignore non-register operands.
 277
 278     unsigned Reg = MO.getReg();
 279     if (Reg == 0) continue;
 280
 281     if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 282       if (MO.isUse()) {
 283         // If the physreg has no defs anywhere, it's just an ambient register
 284         // and we can freely move its uses. Alternatively, if it's allocatable,
 285         // it could get allocated to something with a def during allocation.
 286         if (!RegInfo->def_empty(Reg))
 287           return false;
 288
 289         if (AllocatableSet.test(Reg))
 290           return false;
 291
 292         // Check for a def among the register's aliases too.
 293         for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
 294           unsigned AliasReg = *Alias;
 295           if (!RegInfo->def_empty(AliasReg))
 296             return false;
 297
 298           if (AllocatableSet.test(AliasReg))
 299             return false;
 300         }
 301       } else if (!MO.isDead()) {
 302         // A def that isn't dead. We can't move it.
 303         return false;
 304       }
 305     } else {
 306       // Virtual register uses are always safe to sink.
 307       if (MO.isUse()) continue;
 308
 309       // If it's not safe to move defs of the register class, then abort.
 310       if (!TII->isSafeToMoveRegClassDefs(RegInfo->getRegClass(Reg)))
 311         return false;
 312
 313       // FIXME: This picks a successor to sink into based on having one
 314       // successor that dominates all the uses.  However, there are cases where
 315       // sinking can happen but where the sink point isn't a successor.  For
 316       // example:
 317       //
 318       //   x = computation
 319       //   if () {} else {}
 320       //   use x
 321       //
 322       // the instruction could be sunk over the whole diamond for the
 323       // if/then/else (or loop, etc), allowing it to be sunk into other blocks
 324       // after that.
 325
 326       // Virtual register defs can only be sunk if all their uses are in blocks
 327       // dominated by one of the successors.
 328       if (SuccToSinkTo) {
 329         // If a previous operand picked a block to sink to, then this operand
 330         // must be sinkable to the same block.
 331         if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, ParentBlock, LocalUse))
 332           return false;
 333
 334         continue;
 335       }
 336
 337       // Otherwise, we should look at all the successors and decide which one
 338       // we should sink to.
 339       for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(),
 340            E = ParentBlock->succ_end(); SI != E; ++SI) {
 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 }