/// IsBrAnalyzable - True if AnalyzeBranch() returns false.
/// HasFallThrough - True if BB may fallthrough to the following BB.
/// IsUnpredicable - True if BB is known to be unpredicable.
- /// ClobbersPredicate- True if BB would modify the predicate (e.g. has
+ /// ClobbersPred - True if BB could modify predicates (e.g. has
/// cmp, call, etc.)
/// NonPredSize - Number of non-predicated instructions.
/// BB - Corresponding MachineBasicBlock.
if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
return false;
+ if (TrueBBI.IsBrAnalyzable)
+ return false;
+
if (TrueBBI.BB->pred_size() > 1) {
if (TrueBBI.CannotBeCopied ||
TrueBBI.NonPredSize > TLI->getIfCvtDupBlockSizeLimit())
Dups = TrueBBI.NonPredSize;
}
- return !blockAlwaysFallThrough(TrueBBI) && TrueBBI.BrCond.size() == 0;
+ return true;
}
/// ValidTriangle - Returns true if the 'true' and 'false' blocks (along
return false;
if (TT == NULL && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
return false;
- // FIXME: Allow false block to have an early exit?
- if (TrueBBI.BB->pred_size() > 1 ||
- FalseBBI.BB->pred_size() > 1 ||
- TrueBBI.FalseBB || FalseBBI.FalseBB ||
- (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred))
+ if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
+ return false;
+
+ // FIXME: Allow true block to have an early exit?
+ if (TrueBBI.FalseBB || FalseBBI.FalseBB ||
+ (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred))
return false;
MachineBasicBlock::iterator TI = TrueBBI.BB->begin();
if (BBI.IsDone)
return;
+ bool AlreadyPredicated = BBI.Predicate.size() > 0;
// First analyze the end of BB branches.
BBI.TrueBB = BBI.FalseBB = NULL;
BBI.BrCond.clear();
bool SeenCondBr = false;
for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
I != E; ++I) {
- if (!BBI.CannotBeCopied && !TII->CanBeDuplicated(I))
+ const TargetInstrDescriptor *TID = I->getInstrDescriptor();
+ if ((TID->Flags & M_NOT_DUPLICABLE) != 0)
BBI.CannotBeCopied = true;
- const TargetInstrDescriptor *TID = I->getInstrDescriptor();
bool isPredicated = TII->isPredicated(I);
bool isCondBr = BBI.IsBrAnalyzable &&
(TID->Flags & M_BRANCH_FLAG) != 0 && (TID->Flags & M_BARRIER_FLAG) == 0;
- if (!isPredicated && !isCondBr)
- BBI.NonPredSize++;
+ if (!isCondBr) {
+ if (!isPredicated)
+ BBI.NonPredSize++;
+ else if (!AlreadyPredicated) {
+ // FIXME: This instruction is already predicated before the
+ // if-conversion pass. It's probably something like a conditional move.
+ // Mark this block unpredicable for now.
+ BBI.IsUnpredicable = true;
+ return;
+ }
+
+ }
if (BBI.ClobbersPred && !isPredicated) {
// Predicate modification instruction should end the block (except for
}
// Predicate may have been modified, the subsequent (currently)
- // unpredocated instructions cannot be correctly predicated.
+ // unpredicated instructions cannot be correctly predicated.
BBI.IsUnpredicable = true;
return;
}
- if (TID->Flags & M_CLOBBERS_PRED)
+ // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are
+ // still potentially predicable.
+ std::vector<MachineOperand> PredDefs;
+ if (TII->DefinesPredicate(I, PredDefs))
BBI.ClobbersPred = true;
if ((TID->Flags & M_PREDICABLE) == 0) {
void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
MachineBasicBlock *TBB = NULL, *FBB = NULL;
std::vector<MachineOperand> Cond;
- bool isAnalyzable = !TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond);
- bool CanFallthrough = isAnalyzable && (TBB == NULL || FBB == NULL);
- if (BBI.TrueBB && BBI.BB->isSuccessor(BBI.TrueBB))
- if (!(BBI.TrueBB == TBB || BBI.TrueBB == FBB ||
- (CanFallthrough && getNextBlock(BBI.BB) == BBI.TrueBB)))
- BBI.BB->removeSuccessor(BBI.TrueBB);
- if (BBI.FalseBB && BBI.BB->isSuccessor(BBI.FalseBB))
- if (!(BBI.FalseBB == TBB || BBI.FalseBB == FBB ||
- (CanFallthrough && getNextBlock(BBI.BB) == BBI.FalseBB)))
- BBI.BB->removeSuccessor(BBI.FalseBB);
+ if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond))
+ BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
}
/// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG.
PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
}
+ if (!DupBB) {
+ // Now merge the entry of the triangle with the true block.
+ BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
+ MergeBlocks(BBI, *CvtBBI);
+ }
+
// If 'true' block has a 'false' successor, add an exit branch to it.
if (HasEarlyExit) {
std::vector<MachineOperand> RevCond(CvtBBI->BrCond);
if (TII->ReverseBranchCondition(RevCond))
assert(false && "Unable to reverse branch condition!");
- if (DupBB) {
- TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond);
- BBI.BB->addSuccessor(CvtBBI->FalseBB);
- } else {
- TII->InsertBranch(*CvtBBI->BB, CvtBBI->FalseBB, NULL, RevCond);
- }
- }
-
- if (!DupBB) {
- // Now merge the entry of the triangle with the true block.
- BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
- MergeBlocks(BBI, *CvtBBI);
+ TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond);
+ BBI.BB->addSuccessor(CvtBBI->FalseBB);
}
// Merge in the 'false' block if the 'false' block has no other
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)
+ if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
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.
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();
}
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.
+ // Merge the true 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;
- }
+ MergeBlocks(BBI, *BBI2);
// If the if-converted block fallthrough or unconditionally branch into the
// tail block, and the tail block does not have other predecessors, then
// 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);
+ if (TailBB->pred_size() == 1 && !TailBBI.HasFallThrough) {
+ BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
+ MergeBlocks(BBI, TailBBI);
TailBBI.IsDone = true;
} else {
- bool isFallThrough = canFallThroughTo(LastBBI->BB, TailBB);
- if (!isFallThrough) {
- InsertUncondBranch(LastBBI->BB, TailBB, TII);
- LastBBI->HasFallThrough = false;
- }
+ InsertUncondBranch(BBI.BB, TailBB, TII);
+ BBI.HasFallThrough = false;
}
}
}
}
+ 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;
+ if (!ToBBI.BB->isSuccessor(Succ))
+ ToBBI.BB->addSuccessor(Succ);
+ }
+
std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
std::back_inserter(ToBBI.Predicate));
std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate));
}
// Now FromBBI always fall through to the next block!
- if (NBB)
+ if (NBB && !FromBBI.BB->isSuccessor(NBB))
FromBBI.BB->addSuccessor(NBB);
std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
projects / oota-llvm.git / blobdiff