IfConversion.cpp

  // True block must fall through or ended with unanalyzable terminator.
  if (!TailBB) {
    if (blockAlwaysFallThrough(TrueBBI))
      TailBB = FalseBBI.TrueBB;
    assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
  }

  if (TrueBBI.IsDone || FalseBBI.IsDone ||
      TrueBBI.BB->pred_size() > 1 ||
      FalseBBI.BB->pred_size() > 1) {
    // Something has changed. It's no longer safe to predicate these blocks.
    BBI.IsAnalyzed = false;
    TrueBBI.IsAnalyzed = false;
    FalseBBI.IsAnalyzed = false;
    return false;
  }

  // Merge the 'true' and 'false' blocks by copying the instructions
  // from the 'false' block to the 'true' block. That is, unless the true
  // block would clobber the predicate, in that case, do the opposite.
  BBInfo *BBI1 = &TrueBBI;
  BBInfo *BBI2 = &FalseBBI;
  std::vector<MachineOperand> RevCond(BBI.BrCond);
  TII->ReverseBranchCondition(RevCond);
  std::vector<MachineOperand> *Cond1 = &BBI.BrCond;
  std::vector<MachineOperand> *Cond2 = &RevCond;
  bool NeedBr1 = BBI1->FalseBB != NULL;
  bool NeedBr2 = BBI2->FalseBB != NULL; 

  // Figure out the more profitable ordering.
  bool DoSwap = false;
  if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred)
    DoSwap = true;
  else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) {
    if (!NeedBr1 && NeedBr2)
      DoSwap = true;
    else if (NeedBr1 == NeedBr2) {
      if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
        DoSwap = true;
    }
  }
  if (DoSwap) {
    std::swap(BBI1, BBI2);
    std::swap(Cond1, Cond2);
    std::swap(NeedBr1, NeedBr2);
  }

  // Remove the conditional branch from entry to the blocks.
  BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);

  // Remove the duplicated instructions at the beginnings of both paths.
  MachineBasicBlock::iterator DI1 = BBI1->BB->begin();
  MachineBasicBlock::iterator DI2 = BBI2->BB->begin();
  BBI1->NonPredSize -= NumDups1;
  BBI2->NonPredSize -= NumDups1;
  while (NumDups1 != 0) {
    ++DI1;
    ++DI2;
    --NumDups1;
  }
  BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
  BBI2->BB->erase(BBI2->BB->begin(), DI2);

  // Predicate the 'true' block after removing its branch.
  BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
  DI1 = BBI1->BB->end();
  for (unsigned i = 0; i != NumDups2; ++i)
    --DI1;
  BBI1->BB->erase(DI1, BBI1->BB->end());
  PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1);

  // Add an early exit branch if needed.
  if (NeedBr1)
    TII->InsertBranch(*BBI1->BB, BBI1->FalseBB, NULL, *Cond1);

  // Predicate the 'false' block.
  BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
  DI2 = BBI2->BB->end();
  while (NumDups2 != 0) {
    --DI2;
    --NumDups2;
  }
  PredicateBlock(*BBI2, DI2, *Cond2);

  // Add an unconditional branch from 'false' to to 'false' successor if it
  // will not be the fallthrough block.
  if (NeedBr2 && !NeedBr1) {
    // If BBI2 isn't going to be merged in, then the existing fallthrough
    // or branch is fine.
    if (!canFallThroughTo(BBI.BB, BBI2->FalseBB)) {
      InsertUncondBranch(BBI2->BB, BBI2->FalseBB, TII);
      BBI2->HasFallThrough = false;
    }
  }

  // Keep them as two separate blocks if there is an early exit.
  if (!NeedBr1)
    MergeBlocks(*BBI1, *BBI2);

  // Merge the combined block into the entry of the diamond.
  MergeBlocks(BBI, *BBI1);

  // 'True' and 'false' aren't combined, see if we need to add a unconditional
  // branch to the 'false' block.
  if (NeedBr1 && !canFallThroughTo(BBI.BB, BBI2->BB)) {
    InsertUncondBranch(BBI.BB, BBI2->BB, TII);
    BBI1->HasFallThrough = false;
  }

  // If the if-converted block fallthrough or unconditionally branch into the
  // tail block, and the tail block does not have other predecessors, then
  // fold the tail block in as well. Otherwise, unless it falls through to the
  // tail, add a unconditional branch to it.
  if (TailBB) {
    BBInfo TailBBI = BBAnalysis[TailBB->getNumber()];
    BBInfo *LastBBI = NeedBr1 ? BBI2 : &BBI;
    bool HasEarlyExit = NeedBr1 ? NeedBr2 : false;
    if (!HasEarlyExit &&
        TailBB->pred_size() == 1 && !TailBBI.HasFallThrough) {
      LastBBI->NonPredSize -= TII->RemoveBranch(*LastBBI->BB);
      MergeBlocks(*LastBBI, TailBBI);
      TailBBI.IsDone = true;
    } else {
      bool isFallThrough = canFallThroughTo(LastBBI->BB, TailBB);
      if (!isFallThrough) {
        InsertUncondBranch(LastBBI->BB, TailBB, TII);
        LastBBI->HasFallThrough = false;
      }
    }
  }

  RemoveExtraEdges(BBI);

  // Update block info.
  BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
  InvalidatePreds(BBI.BB);

  // FIXME: Must maintain LiveIns.
  return true;
}

/// PredicateBlock - Predicate instructions from the start of the block to the
/// specified end with the specified condition.
void IfConverter::PredicateBlock(BBInfo &BBI,
                                 MachineBasicBlock::iterator E,
                                 std::vector<MachineOperand> &Cond) {
  for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
    if (TII->isPredicated(I))
      continue;
    if (!TII->PredicateInstruction(I, Cond)) {
      cerr << "Unable to predicate " << *I << "!\n";
      abort();
    }
  }

  std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));

  BBI.IsAnalyzed = false;
  BBI.NonPredSize = 0;

  NumIfConvBBs++;
}

/// CopyAndPredicateBlock - Copy and predicate instructions from source BB to
/// the destination block. Skip end of block branches if IgnoreBr is true.
void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
                                        std::vector<MachineOperand> &Cond,
                                        bool IgnoreBr) {
  for (MachineBasicBlock::iterator I = FromBBI.BB->begin(),
         E = FromBBI.BB->end(); I != E; ++I) {
    const TargetInstrDescriptor *TID = I->getInstrDescriptor();
    bool isPredicated = TII->isPredicated(I);
    // Do not copy the end of the block branches.
    if (IgnoreBr && !isPredicated && (TID->Flags & M_BRANCH_FLAG) != 0)
      break;

    MachineInstr *MI = I->clone();
    ToBBI.BB->insert(ToBBI.BB->end(), MI);
    ToBBI.NonPredSize++;

    if (!isPredicated)
      if (!TII->PredicateInstruction(MI, Cond)) {
        cerr << "Unable to predicate " << *MI << "!\n";
        abort();
      }
  }

  std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
            std::back_inserter(ToBBI.Predicate));
  std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate));

  ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
  ToBBI.IsAnalyzed = false;

  NumDupBBs++;
}

/// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
///
void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) {
  ToBBI.BB->splice(ToBBI.BB->end(),
                   FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());

  // Redirect all branches to FromBB to ToBB.
  std::vector<MachineBasicBlock *> Preds(FromBBI.BB->pred_begin(),
                                         FromBBI.BB->pred_end());
  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
    MachineBasicBlock *Pred = Preds[i];
    if (Pred == ToBBI.BB)
      continue;
    Pred->ReplaceUsesOfBlockWith(FromBBI.BB, ToBBI.BB);
  }
 
  std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
                                         FromBBI.BB->succ_end());
  MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
  MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;

  for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
    MachineBasicBlock *Succ = Succs[i];
    // Fallthrough edge can't be transferred.
    if (Succ == FallThrough)
      continue;
    FromBBI.BB->removeSuccessor(Succ);
    if (!ToBBI.BB->isSuccessor(Succ))
      ToBBI.BB->addSuccessor(Succ);
  }

  // Now FromBBI always fall through to the next block!
  if (NBB)
    FromBBI.BB->addSuccessor(NBB);

  std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
            std::back_inserter(ToBBI.Predicate));
  FromBBI.Predicate.clear();

  ToBBI.NonPredSize += FromBBI.NonPredSize;
  FromBBI.NonPredSize = 0;

  ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
  ToBBI.HasFallThrough = FromBBI.HasFallThrough;
  ToBBI.IsAnalyzed = false;
  FromBBI.IsAnalyzed = false;
}