From 36489bbbacb2adf0d639faa2d1bc2bbde9936396 Mon Sep 17 00:00:00 2001
From: Evan Cheng <evan.cheng@apple.com>
Date: Fri, 18 May 2007 19:26:33 +0000
Subject: [PATCH] Change to depth-first traversal.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37236 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/IfConversion.cpp | 33 ++++++++++++++++++++++-----------
 1 file changed, 22 insertions(+), 11 deletions(-)

diff --git a/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp
index 75ded08b740..50dfde999de 100644
--- a/lib/CodeGen/IfConversion.cpp
+++ b/lib/CodeGen/IfConversion.cpp
@@ -19,6 +19,7 @@
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Statistic.h"
 using namespace llvm;
 
@@ -237,8 +238,11 @@ void IfConverter::FeasibilityAnalysis(BBInfo &BBI) {
 /// if-conversion candidates.
 void IfConverter::InitialFunctionAnalysis(MachineFunction &MF,
                                           std::vector<int> &Candidates) {
-  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
-    MachineBasicBlock *BB = I;
+  std::set<MachineBasicBlock*> Visited;
+  MachineBasicBlock *Entry = MF.begin();
+  for (df_ext_iterator<MachineBasicBlock*> DFI = df_ext_begin(Entry, Visited),
+         E = df_ext_end(Entry, Visited); DFI != E; ++DFI) {
+    MachineBasicBlock *BB = *DFI;
     StructuralAnalysis(BB);
     BBInfo &BBI = BBAnalysis[BB->getNumber()];
     if (BBI.Kind == ICTriangleEntry || BBI.Kind == ICDiamondEntry)
@@ -379,23 +383,30 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI) {
       TII->InsertBranch(*BBI.FalseBB, *BBI.FalseBB->succ_begin(), NULL,NewCond);
 
     // Merge the 'true' and 'false' blocks by copying the instructions
-    // from the 'false' block to the 'true' block.
-    MergeBlocks(TrueBBI, FalseBBI);
+    // 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 *CvtBBI;
+    if (!TrueBBI.ClobbersPred) {
+      MergeBlocks(TrueBBI, FalseBBI);
+      CvtBBI = &TrueBBI;
+    } else {
+      MergeBlocks(FalseBBI, TrueBBI);
+      CvtBBI = &FalseBBI;
+    }
 
     // Remove the conditional branch from entry to the blocks.
     BBI.Size -= TII->RemoveBranch(*BBI.BB);
 
     // Merge the combined block into the entry of the diamond if the entry
-    // block is the only predecessor. Otherwise, insert an unconditional
-    // branch.
-    BBInfo *CvtBBI = &TrueBBI;
-    if (BBI.TrueBB->pred_size() == 1) {
-      BBI.BB->removeSuccessor(BBI.TrueBB);
-      MergeBlocks(BBI, TrueBBI);
+    // block is its only predecessor. Otherwise, insert an unconditional
+    // branch from entry to the if-converted block.
+    if (CvtBBI->BB->pred_size() == 1) {
+      BBI.BB->removeSuccessor(CvtBBI->BB);
+      MergeBlocks(BBI, *CvtBBI);
       CvtBBI = &BBI;
     } else {
       std::vector<MachineOperand> NoCond;
-      TII->InsertBranch(*BBI.BB, BBI.TrueBB, NULL, NoCond);
+      TII->InsertBranch(*BBI.BB, CvtBBI->BB, NULL, NoCond);
     }
 
     // If the if-converted block fallthrough into the tail block, then
-- 
2.34.1