BranchFolding.cpp

  for (MBBI = MBB->begin(), MBBE = MBB->end(); MBBI!=MBBE; ++MBBI) {
    if (!MBBI->isDebugValue())
      break;
  }
  return (MBBI->isBranch());
}

/// IsBetterFallthrough - Return true if it would be clearly better to
/// fall-through to MBB1 than to fall through into MBB2.  This has to return
/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
/// result in infinite loops.
static bool IsBetterFallthrough(MachineBasicBlock *MBB1,
                                MachineBasicBlock *MBB2) {
  // Right now, we use a simple heuristic.  If MBB2 ends with a call, and
  // MBB1 doesn't, we prefer to fall through into MBB1.  This allows us to
  // optimize branches that branch to either a return block or an assert block
  // into a fallthrough to the return.
  if (IsEmptyBlock(MBB1) || IsEmptyBlock(MBB2)) return false;

  // If there is a clear successor ordering we make sure that one block
  // will fall through to the next
  if (MBB1->isSuccessor(MBB2)) return true;
  if (MBB2->isSuccessor(MBB1)) return false;

  // Neither block consists entirely of debug info (per IsEmptyBlock check),
  // so we needn't test for falling off the beginning here.
  MachineBasicBlock::iterator MBB1I = --MBB1->end();
  while (MBB1I->isDebugValue())
    --MBB1I;
  MachineBasicBlock::iterator MBB2I = --MBB2->end();
  while (MBB2I->isDebugValue())
    --MBB2I;
  return MBB2I->isCall() && !MBB1I->isCall();
}

/// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch
/// instructions on the block. Always use the DebugLoc of the first
/// branching instruction found unless its absent, in which case use the
/// DebugLoc of the second if present.
static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB) {
  MachineBasicBlock::iterator I = MBB.end();
  if (I == MBB.begin())
    return DebugLoc();
  --I;
  while (I->isDebugValue() && I != MBB.begin())
    --I;
  if (I->isBranch())
    return I->getDebugLoc();
  return DebugLoc();
}

/// OptimizeBlock - Analyze and optimize control flow related to the specified
/// block.  This is never called on the entry block.
bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
  bool MadeChange = false;
  MachineFunction &MF = *MBB->getParent();
ReoptimizeBlock:

  MachineFunction::iterator FallThrough = MBB;
  ++FallThrough;

  // If this block is empty, make everyone use its fall-through, not the block
  // explicitly.  Landing pads should not do this since the landing-pad table
  // points to this block.  Blocks with their addresses taken shouldn't be
  // optimized away.
  if (IsEmptyBlock(MBB) && !MBB->isLandingPad() && !MBB->hasAddressTaken()) {
    // Dead block?  Leave for cleanup later.
    if (MBB->pred_empty()) return MadeChange;

    if (FallThrough == MF.end()) {
      // TODO: Simplify preds to not branch here if possible!
    } else {
      // Rewrite all predecessors of the old block to go to the fallthrough
      // instead.
      while (!MBB->pred_empty()) {
        MachineBasicBlock *Pred = *(MBB->pred_end()-1);
        Pred->ReplaceUsesOfBlockWith(MBB, FallThrough);
      }
      // If MBB was the target of a jump table, update jump tables to go to the
      // fallthrough instead.
      if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
        MJTI->ReplaceMBBInJumpTables(MBB, FallThrough);
      MadeChange = true;
    }
    return MadeChange;
  }

  // Check to see if we can simplify the terminator of the block before this
  // one.
  MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB));

  MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
  SmallVector<MachineOperand, 4> PriorCond;
  bool PriorUnAnalyzable =
    TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
  if (!PriorUnAnalyzable) {
    // If the CFG for the prior block has extra edges, remove them.
    MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB,
                                              !PriorCond.empty());

    // If the previous branch is conditional and both conditions go to the same
    // destination, remove the branch, replacing it with an unconditional one or
    // a fall-through.
    if (PriorTBB && PriorTBB == PriorFBB) {
      DebugLoc dl = getBranchDebugLoc(PrevBB);
      TII->RemoveBranch(PrevBB);
      PriorCond.clear();
      if (PriorTBB != MBB)
        TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond, dl);
      MadeChange = true;
      ++NumBranchOpts;
      goto ReoptimizeBlock;
    }

    // If the previous block unconditionally falls through to this block and
    // this block has no other predecessors, move the contents of this block
    // into the prior block. This doesn't usually happen when SimplifyCFG
    // has been used, but it can happen if tail merging splits a fall-through
    // predecessor of a block.
    // This has to check PrevBB->succ_size() because EH edges are ignored by
    // AnalyzeBranch.
    if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
        PrevBB.succ_size() == 1 &&
        !MBB->hasAddressTaken() && !MBB->isLandingPad()) {
      DEBUG(dbgs() << "\nMerging into block: " << PrevBB
                   << "From MBB: " << *MBB);
      // Remove redundant DBG_VALUEs first.
      if (PrevBB.begin() != PrevBB.end()) {
        MachineBasicBlock::iterator PrevBBIter = PrevBB.end();
        --PrevBBIter;
        MachineBasicBlock::iterator MBBIter = MBB->begin();
        // Check if DBG_VALUE at the end of PrevBB is identical to the
        // DBG_VALUE at the beginning of MBB.
        while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()
               && PrevBBIter->isDebugValue() && MBBIter->isDebugValue()) {
          if (!MBBIter->isIdenticalTo(PrevBBIter))
            break;
          MachineInstr *DuplicateDbg = MBBIter;
          ++MBBIter; -- PrevBBIter;
          DuplicateDbg->eraseFromParent();
        }
      }
      PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
      PrevBB.removeSuccessor(PrevBB.succ_begin());
      assert(PrevBB.succ_empty());
      PrevBB.transferSuccessors(MBB);
      MadeChange = true;
      return MadeChange;
    }

    // If the previous branch *only* branches to *this* block (conditional or
    // not) remove the branch.
    if (PriorTBB == MBB && PriorFBB == 0) {
      TII->RemoveBranch(PrevBB);
      MadeChange = true;
      ++NumBranchOpts;
      goto ReoptimizeBlock;
    }

    // If the prior block branches somewhere else on the condition and here if
    // the condition is false, remove the uncond second branch.
    if (PriorFBB == MBB) {
      DebugLoc dl = getBranchDebugLoc(PrevBB);
      TII->RemoveBranch(PrevBB);
      TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond, dl);
      MadeChange = true;
      ++NumBranchOpts;
      goto ReoptimizeBlock;
    }

    // If the prior block branches here on true and somewhere else on false, and
    // if the branch condition is reversible, reverse the branch to create a
    // fall-through.
    if (PriorTBB == MBB) {
      SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
      if (!TII->ReverseBranchCondition(NewPriorCond)) {
        DebugLoc dl = getBranchDebugLoc(PrevBB);
        TII->RemoveBranch(PrevBB);
        TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond, dl);
        MadeChange = true;
        ++NumBranchOpts;
        goto ReoptimizeBlock;
      }
    }

    // If this block has no successors (e.g. it is a return block or ends with
    // a call to a no-return function like abort or __cxa_throw) and if the pred
    // falls through into this block, and if it would otherwise fall through
    // into the block after this, move this block to the end of the function.
    //
    // We consider it more likely that execution will stay in the function (e.g.
    // due to loops) than it is to exit it.  This asserts in loops etc, moving
    // the assert condition out of the loop body.
    if (MBB->succ_empty() && !PriorCond.empty() && PriorFBB == 0 &&
        MachineFunction::iterator(PriorTBB) == FallThrough &&
        !MBB->canFallThrough()) {
      bool DoTransform = true;

      // We have to be careful that the succs of PredBB aren't both no-successor
      // blocks.  If neither have successors and if PredBB is the second from
      // last block in the function, we'd just keep swapping the two blocks for
      // last.  Only do the swap if one is clearly better to fall through than
      // the other.
      if (FallThrough == --MF.end() &&
          !IsBetterFallthrough(PriorTBB, MBB))
        DoTransform = false;

      if (DoTransform) {
        // Reverse the branch so we will fall through on the previous true cond.
        SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
        if (!TII->ReverseBranchCondition(NewPriorCond)) {
          DEBUG(dbgs() << "\nMoving MBB: " << *MBB
                       << "To make fallthrough to: " << *PriorTBB << "\n");

          DebugLoc dl = getBranchDebugLoc(PrevBB);
          TII->RemoveBranch(PrevBB);
          TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond, dl);

          // Move this block to the end of the function.
          MBB->moveAfter(--MF.end());
          MadeChange = true;
          ++NumBranchOpts;
          return MadeChange;
        }
      }
    }
  }

  // Analyze the branch in the current block.
  MachineBasicBlock *CurTBB = 0, *CurFBB = 0;
  SmallVector<MachineOperand, 4> CurCond;
  bool CurUnAnalyzable= TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
  if (!CurUnAnalyzable) {
    // If the CFG for the prior block has extra edges, remove them.
    MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty());

    // If this is a two-way branch, and the FBB branches to this block, reverse
    // the condition so the single-basic-block loop is faster.  Instead of:
    //    Loop: xxx; jcc Out; jmp Loop
    // we want:
    //    Loop: xxx; jncc Loop; jmp Out
    if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
      SmallVector<MachineOperand, 4> NewCond(CurCond);
      if (!TII->ReverseBranchCondition(NewCond)) {
        DebugLoc dl = getBranchDebugLoc(*MBB);
        TII->RemoveBranch(*MBB);
        TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond, dl);
        MadeChange = true;
        ++NumBranchOpts;
        goto ReoptimizeBlock;
      }
    }

    // If this branch is the only thing in its block, see if we can forward
    // other blocks across it.
    if (CurTBB && CurCond.empty() && CurFBB == 0 &&
        IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
        !MBB->hasAddressTaken()) {
      DebugLoc dl = getBranchDebugLoc(*MBB);
      // This block may contain just an unconditional branch.  Because there can
      // be 'non-branch terminators' in the block, try removing the branch and
      // then seeing if the block is empty.
      TII->RemoveBranch(*MBB);
      // If the only things remaining in the block are debug info, remove these
      // as well, so this will behave the same as an empty block in non-debug
      // mode.
      if (!MBB->empty()) {
        bool NonDebugInfoFound = false;
        for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
             I != E; ++I) {
          if (!I->isDebugValue()) {
            NonDebugInfoFound = true;
            break;
          }
        }
        if (!NonDebugInfoFound)
          // Make the block empty, losing the debug info (we could probably
          // improve this in some cases.)
          MBB->erase(MBB->begin(), MBB->end());
      }
      // If this block is just an unconditional branch to CurTBB, we can
      // usually completely eliminate the block.  The only case we cannot
      // completely eliminate the block is when the block before this one
      // falls through into MBB and we can't understand the prior block's branch
      // condition.
      if (MBB->empty()) {
        bool PredHasNoFallThrough = !PrevBB.canFallThrough();
        if (PredHasNoFallThrough || !PriorUnAnalyzable ||
            !PrevBB.isSuccessor(MBB)) {
          // If the prior block falls through into us, turn it into an
          // explicit branch to us to make updates simpler.
          if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
              PriorTBB != MBB && PriorFBB != MBB) {
            if (PriorTBB == 0) {
              assert(PriorCond.empty() && PriorFBB == 0 &&
                     "Bad branch analysis");
              PriorTBB = MBB;
            } else {
              assert(PriorFBB == 0 && "Machine CFG out of date!");
              PriorFBB = MBB;
            }
            DebugLoc pdl = getBranchDebugLoc(PrevBB);
            TII->RemoveBranch(PrevBB);
            TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
          }

          // Iterate through all the predecessors, revectoring each in-turn.
          size_t PI = 0;
          bool DidChange = false;
          bool HasBranchToSelf = false;
          while(PI != MBB->pred_size()) {
            MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
            if (PMBB == MBB) {
              // If this block has an uncond branch to itself, leave it.
              ++PI;
              HasBranchToSelf = true;
            } else {
              DidChange = true;
              PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
              // If this change resulted in PMBB ending in a conditional
              // branch where both conditions go to the same destination,
              // change this to an unconditional branch (and fix the CFG).
              MachineBasicBlock *NewCurTBB = 0, *NewCurFBB = 0;
              SmallVector<MachineOperand, 4> NewCurCond;
              bool NewCurUnAnalyzable = TII->AnalyzeBranch(*PMBB, NewCurTBB,
                      NewCurFBB, NewCurCond, true);
              if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
                DebugLoc pdl = getBranchDebugLoc(*PMBB);
                TII->RemoveBranch(*PMBB);
                NewCurCond.clear();
                TII->InsertBranch(*PMBB, NewCurTBB, 0, NewCurCond, pdl);
                MadeChange = true;
                ++NumBranchOpts;
                PMBB->CorrectExtraCFGEdges(NewCurTBB, 0, false);
              }
            }
          }

          // Change any jumptables to go to the new MBB.
          if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
            MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
          if (DidChange) {
            ++NumBranchOpts;
            MadeChange = true;
            if (!HasBranchToSelf) return MadeChange;
          }
        }
      }

      // Add the branch back if the block is more than just an uncond branch.
      TII->InsertBranch(*MBB, CurTBB, 0, CurCond, dl);
    }
  }

  // If the prior block doesn't fall through into this block, and if this
  // block doesn't fall through into some other block, see if we can find a
  // place to move this block where a fall-through will happen.
  if (!PrevBB.canFallThrough()) {

    // Now we know that there was no fall-through into this block, check to
    // see if it has a fall-through into its successor.
    bool CurFallsThru = MBB->canFallThrough();

    if (!MBB->isLandingPad()) {
      // Check all the predecessors of this block.  If one of them has no fall
      // throughs, move this block right after it.
      for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
           E = MBB->pred_end(); PI != E; ++PI) {
        // Analyze the branch at the end of the pred.
        MachineBasicBlock *PredBB = *PI;
        MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
        MachineBasicBlock *PredTBB = 0, *PredFBB = 0;
        SmallVector<MachineOperand, 4> PredCond;
        if (PredBB != MBB && !PredBB->canFallThrough() &&
            !TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)
            && (!CurFallsThru || !CurTBB || !CurFBB)
            && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
          // If the current block doesn't fall through, just move it.
          // If the current block can fall through and does not end with a
          // conditional branch, we need to append an unconditional jump to
          // the (current) next block.  To avoid a possible compile-time
          // infinite loop, move blocks only backward in this case.
          // Also, if there are already 2 branches here, we cannot add a third;
          // this means we have the case
          // Bcc next
          // B elsewhere
          // next:
          if (CurFallsThru) {
            MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB));
            CurCond.clear();
            TII->InsertBranch(*MBB, NextBB, 0, CurCond, DebugLoc());
          }
          MBB->moveAfter(PredBB);
          MadeChange = true;
          goto ReoptimizeBlock;
        }
      }
    }

    if (!CurFallsThru) {
      // Check all successors to see if we can move this block before it.
      for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
           E = MBB->succ_end(); SI != E; ++SI) {
        // Analyze the branch at the end of the block before the succ.
        MachineBasicBlock *SuccBB = *SI;
        MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev;

        // If this block doesn't already fall-through to that successor, and if
        // the succ doesn't already have a block that can fall through into it,
        // and if the successor isn't an EH destination, we can arrange for the
        // fallthrough to happen.
        if (SuccBB != MBB && &*SuccPrev != MBB &&
            !SuccPrev->canFallThrough() && !CurUnAnalyzable &&
            !SuccBB->isLandingPad()) {
          MBB->moveBefore(SuccBB);
          MadeChange = true;
          goto ReoptimizeBlock;
        }
      }

      // Okay, there is no really great place to put this block.  If, however,
      // the block before this one would be a fall-through if this block were
      // removed, move this block to the end of the function.
      MachineBasicBlock *PrevTBB = 0, *PrevFBB = 0;
      SmallVector<MachineOperand, 4> PrevCond;
      if (FallThrough != MF.end() &&
          !TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
          PrevBB.isSuccessor(FallThrough)) {
        MBB->moveAfter(--MF.end());
        MadeChange = true;
        return MadeChange;
      }
    }
  }

  return MadeChange;
}

//===----------------------------------------------------------------------===//
//  Hoist Common Code
//===----------------------------------------------------------------------===//

/// HoistCommonCode - Hoist common instruction sequences at the start of basic
/// blocks to their common predecessor.
bool BranchFolder::HoistCommonCode(MachineFunction &MF) {
  bool MadeChange = false;
  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ) {
    MachineBasicBlock *MBB = I++;
    MadeChange |= HoistCommonCodeInSuccs(MBB);
  }

  return MadeChange;
}

/// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
/// its 'true' successor.
static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
                                         MachineBasicBlock *TrueBB) {
  for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
         E = BB->succ_end(); SI != E; ++SI) {
    MachineBasicBlock *SuccBB = *SI;
    if (SuccBB != TrueBB)
      return SuccBB;
  }
  return NULL;
}

/// findHoistingInsertPosAndDeps - Find the location to move common instructions
/// in successors to. The location is usually just before the terminator,
/// however if the terminator is a conditional branch and its previous
/// instruction is the flag setting instruction, the previous instruction is
/// the preferred location. This function also gathers uses and defs of the
/// instructions from the insertion point to the end of the block. The data is
/// used by HoistCommonCodeInSuccs to ensure safety.
static
MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
                                                  const TargetInstrInfo *TII,
                                                  const TargetRegisterInfo *TRI,
                                                  SmallSet<unsigned,4> &Uses,
                                                  SmallSet<unsigned,4> &Defs) {
  MachineBasicBlock::iterator Loc = MBB->getFirstTerminator();
  if (!TII->isUnpredicatedTerminator(Loc))
    return MBB->end();

  for (unsigned i = 0, e = Loc->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = Loc->getOperand(i);
    if (!MO.isReg())
      continue;
    unsigned Reg = MO.getReg();
    if (!Reg)
      continue;
    if (MO.isUse()) {
      for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
        Uses.insert(*AI);
    } else if (!MO.isDead())
      // Don't try to hoist code in the rare case the terminator defines a
      // register that is later used.
      return MBB->end();
  }

  if (Uses.empty())
    return Loc;
  if (Loc == MBB->begin())
    return MBB->end();

  // The terminator is probably a conditional branch, try not to separate the
  // branch from condition setting instruction.
  MachineBasicBlock::iterator PI = Loc;
  --PI;
  while (PI != MBB->begin() && Loc->isDebugValue())
    --PI;

  bool IsDef = false;
  for (unsigned i = 0, e = PI->getNumOperands(); !IsDef && i != e; ++i) {
    const MachineOperand &MO = PI->getOperand(i);
    // If PI has a regmask operand, it is probably a call. Separate away.
    if (MO.isRegMask())
      return Loc;
    if (!MO.isReg() || MO.isUse())
      continue;
    unsigned Reg = MO.getReg();
    if (!Reg)
      continue;
    if (Uses.count(Reg))
      IsDef = true;
  }
  if (!IsDef)
    // The condition setting instruction is not just before the conditional
    // branch.
    return Loc;

  // Be conservative, don't insert instruction above something that may have
  // side-effects. And since it's potentially bad to separate flag setting
  // instruction from the conditional branch, just abort the optimization
  // completely.
  // Also avoid moving code above predicated instruction since it's hard to
  // reason about register liveness with predicated instruction.
  bool DontMoveAcrossStore = true;
  if (!PI->isSafeToMove(TII, 0, DontMoveAcrossStore) ||
      TII->isPredicated(PI))
    return MBB->end();


  // Find out what registers are live. Note this routine is ignoring other live
  // registers which are only used by instructions in successor blocks.
  for (unsigned i = 0, e = PI->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = PI->getOperand(i);
    if (!MO.isReg())
      continue;
    unsigned Reg = MO.getReg();
    if (!Reg)
      continue;
    if (MO.isUse()) {
      for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
        Uses.insert(*AI);
    } else {
      if (Uses.count(Reg)) {
        Uses.erase(Reg);
        for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
          Uses.erase(*SubRegs); // Use sub-registers to be conservative
      }
      for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
        Defs.insert(*AI);
    }
  }

  return PI;
}

/// HoistCommonCodeInSuccs - If the successors of MBB has common instruction
/// sequence at the start of the function, move the instructions before MBB
/// terminator if it's legal.
bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
  MachineBasicBlock *TBB = 0, *FBB = 0;
  SmallVector<MachineOperand, 4> Cond;
  if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())
    return false;

  if (!FBB) FBB = findFalseBlock(MBB, TBB);
  if (!FBB)
    // Malformed bcc? True and false blocks are the same?
    return false;

  // Restrict the optimization to cases where MBB is the only predecessor,
  // it is an obvious win.
  if (TBB->pred_size() > 1 || FBB->pred_size() > 1)
    return false;

  // Find a suitable position to hoist the common instructions to. Also figure
  // out which registers are used or defined by instructions from the insertion
  // point to the end of the block.
  SmallSet<unsigned, 4> Uses, Defs;
  MachineBasicBlock::iterator Loc =
    findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs);
  if (Loc == MBB->end())
    return false;

  bool HasDups = false;
  SmallVector<unsigned, 4> LocalDefs;
  SmallSet<unsigned, 4> LocalDefsSet;
  MachineBasicBlock::iterator TIB = TBB->begin();
  MachineBasicBlock::iterator FIB = FBB->begin();
  MachineBasicBlock::iterator TIE = TBB->end();
  MachineBasicBlock::iterator FIE = FBB->end();
  while (TIB != TIE && FIB != FIE) {
    // Skip dbg_value instructions. These do not count.
    if (TIB->isDebugValue()) {
      while (TIB != TIE && TIB->isDebugValue())
        ++TIB;
      if (TIB == TIE)
        break;
    }
    if (FIB->isDebugValue()) {
      while (FIB != FIE && FIB->isDebugValue())
        ++FIB;
      if (FIB == FIE)
        break;
    }
    if (!TIB->isIdenticalTo(FIB, MachineInstr::CheckKillDead))
      break;

    if (TII->isPredicated(TIB))
      // Hard to reason about register liveness with predicated instruction.
      break;

    bool IsSafe = true;
    for (unsigned i = 0, e = TIB->getNumOperands(); i != e; ++i) {
      MachineOperand &MO = TIB->getOperand(i);
      // Don't attempt to hoist instructions with register masks.
      if (MO.isRegMask()) {
        IsSafe = false;
        break;
      }
      if (!MO.isReg())
        continue;
      unsigned Reg = MO.getReg();
      if (!Reg)
        continue;
      if (MO.isDef()) {
        if (Uses.count(Reg)) {
          // Avoid clobbering a register that's used by the instruction at
          // the point of insertion.
          IsSafe = false;
          break;
        }

        if (Defs.count(Reg) && !MO.isDead()) {
          // Don't hoist the instruction if the def would be clobber by the
          // instruction at the point insertion. FIXME: This is overly
          // conservative. It should be possible to hoist the instructions
          // in BB2 in the following example:
          // BB1:
          // r1, eflag = op1 r2, r3
          // brcc eflag
          //
          // BB2:
          // r1 = op2, ...
          //    = op3, r1<kill>
          IsSafe = false;
          break;
        }
      } else if (!LocalDefsSet.count(Reg)) {
        if (Defs.count(Reg)) {
          // Use is defined by the instruction at the point of insertion.
          IsSafe = false;
          break;
        }

        if (MO.isKill() && Uses.count(Reg))
          // Kills a register that's read by the instruction at the point of
          // insertion. Remove the kill marker.
          MO.setIsKill(false);
      }
    }
    if (!IsSafe)
      break;

    bool DontMoveAcrossStore = true;
    if (!TIB->isSafeToMove(TII, 0, DontMoveAcrossStore))
      break;

    // Remove kills from LocalDefsSet, these registers had short live ranges.
    for (unsigned i = 0, e = TIB->getNumOperands(); i != e; ++i) {
      MachineOperand &MO = TIB->getOperand(i);
      if (!MO.isReg() || !MO.isUse() || !MO.isKill())
        continue;
      unsigned Reg = MO.getReg();
      if (!Reg || !LocalDefsSet.count(Reg))
        continue;
      for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
        LocalDefsSet.erase(*AI);
    }

    // Track local defs so we can update liveins.
    for (unsigned i = 0, e = TIB->getNumOperands(); i != e; ++i) {
      MachineOperand &MO = TIB->getOperand(i);
      if (!MO.isReg() || !MO.isDef() || MO.isDead())
        continue;
      unsigned Reg = MO.getReg();
      if (!Reg)
        continue;
      LocalDefs.push_back(Reg);
      for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
        LocalDefsSet.insert(*AI);
    }

    HasDups = true;
    ++TIB;
    ++FIB;
  }

  if (!HasDups)
    return false;

  MBB->splice(Loc, TBB, TBB->begin(), TIB);
  FBB->erase(FBB->begin(), FIB);

  // Update livein's.
  for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
    unsigned Def = LocalDefs[i];
    if (LocalDefsSet.count(Def)) {
      TBB->addLiveIn(Def);
      FBB->addLiveIn(Def);
    }
  }

  ++NumHoist;
  return true;
}