Fix some typos and spelling and grammar, mostly in comments, but also one
[oota-llvm.git] / lib / CodeGen / IfConversion.cpp
1 //===-- IfConversion.cpp - Machine code if conversion pass. ---------------===//
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 file implements the machine instruction level if-conversion pass.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #define DEBUG_TYPE "ifcvt"
15 #include "llvm/Function.h"
16 #include "llvm/CodeGen/Passes.h"
17 #include "llvm/CodeGen/MachineModuleInfo.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/Target/TargetInstrInfo.h"
20 #include "llvm/Target/TargetLowering.h"
21 #include "llvm/Target/TargetMachine.h"
22 #include "llvm/Support/CommandLine.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/ADT/DepthFirstIterator.h"
25 #include "llvm/ADT/Statistic.h"
26 #include "llvm/ADT/STLExtras.h"
27 using namespace llvm;
28
29 // Hidden options for help debugging.
30 static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
31 static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
32 static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
33 static cl::opt<bool> DisableSimple("disable-ifcvt-simple", 
34                                    cl::init(false), cl::Hidden);
35 static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false", 
36                                     cl::init(false), cl::Hidden);
37 static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle", 
38                                      cl::init(false), cl::Hidden);
39 static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev", 
40                                       cl::init(false), cl::Hidden);
41 static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false", 
42                                       cl::init(false), cl::Hidden);
43 static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev", 
44                                        cl::init(false), cl::Hidden);
45 static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond", 
46                                     cl::init(false), cl::Hidden);
47
48 STATISTIC(NumSimple,       "Number of simple if-conversions performed");
49 STATISTIC(NumSimpleFalse,  "Number of simple (F) if-conversions performed");
50 STATISTIC(NumTriangle,     "Number of triangle if-conversions performed");
51 STATISTIC(NumTriangleRev,  "Number of triangle (R) if-conversions performed");
52 STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed");
53 STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed");
54 STATISTIC(NumDiamonds,     "Number of diamond if-conversions performed");
55 STATISTIC(NumIfConvBBs,    "Number of if-converted blocks");
56 STATISTIC(NumDupBBs,       "Number of duplicated blocks");
57
58 namespace {
59   class VISIBILITY_HIDDEN IfConverter : public MachineFunctionPass {
60     enum IfcvtKind {
61       ICNotClassfied,  // BB data valid, but not classified.
62       ICSimpleFalse,   // Same as ICSimple, but on the false path.
63       ICSimple,        // BB is entry of an one split, no rejoin sub-CFG.
64       ICTriangleFRev,  // Same as ICTriangleFalse, but false path rev condition.
65       ICTriangleRev,   // Same as ICTriangle, but true path rev condition.
66       ICTriangleFalse, // Same as ICTriangle, but on the false path.
67       ICTriangle,      // BB is entry of a triangle sub-CFG.
68       ICDiamond        // BB is entry of a diamond sub-CFG.
69     };
70
71     /// BBInfo - One per MachineBasicBlock, this is used to cache the result
72     /// if-conversion feasibility analysis. This includes results from
73     /// TargetInstrInfo::AnalyzeBranch() (i.e. TBB, FBB, and Cond), and its
74     /// classification, and common tail block of its successors (if it's a
75     /// diamond shape), its size, whether it's predicable, and whether any
76     /// instruction can clobber the 'would-be' predicate.
77     ///
78     /// IsDone          - True if BB is not to be considered for ifcvt.
79     /// IsBeingAnalyzed - True if BB is currently being analyzed.
80     /// IsAnalyzed      - True if BB has been analyzed (info is still valid).
81     /// IsEnqueued      - True if BB has been enqueued to be ifcvt'ed.
82     /// IsBrAnalyzable  - True if AnalyzeBranch() returns false.
83     /// HasFallThrough  - True if BB may fallthrough to the following BB.
84     /// IsUnpredicable  - True if BB is known to be unpredicable.
85     /// ClobbersPred    - True if BB could modify predicates (e.g. has
86     ///                   cmp, call, etc.)
87     /// NonPredSize     - Number of non-predicated instructions.
88     /// BB              - Corresponding MachineBasicBlock.
89     /// TrueBB / FalseBB- See AnalyzeBranch().
90     /// BrCond          - Conditions for end of block conditional branches.
91     /// Predicate       - Predicate used in the BB.
92     struct BBInfo {
93       bool IsDone          : 1;
94       bool IsBeingAnalyzed : 1;
95       bool IsAnalyzed      : 1;
96       bool IsEnqueued      : 1;
97       bool IsBrAnalyzable  : 1;
98       bool HasFallThrough  : 1;
99       bool IsUnpredicable  : 1;
100       bool CannotBeCopied  : 1;
101       bool ClobbersPred    : 1;
102       unsigned NonPredSize;
103       MachineBasicBlock *BB;
104       MachineBasicBlock *TrueBB;
105       MachineBasicBlock *FalseBB;
106       SmallVector<MachineOperand, 4> BrCond;
107       SmallVector<MachineOperand, 4> Predicate;
108       BBInfo() : IsDone(false), IsBeingAnalyzed(false),
109                  IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),
110                  HasFallThrough(false), IsUnpredicable(false),
111                  CannotBeCopied(false), ClobbersPred(false), NonPredSize(0),
112                  BB(0), TrueBB(0), FalseBB(0) {}
113     };
114
115     /// IfcvtToken - Record information about pending if-conversions to attemp:
116     /// BBI             - Corresponding BBInfo.
117     /// Kind            - Type of block. See IfcvtKind.
118     /// NeedSubsumption - True if the to-be-predicated BB has already been
119     ///                   predicated.
120     /// NumDups      - Number of instructions that would be duplicated due
121     ///                   to this if-conversion. (For diamonds, the number of
122     ///                   identical instructions at the beginnings of both
123     ///                   paths).
124     /// NumDups2     - For diamonds, the number of identical instructions
125     ///                   at the ends of both paths.
126     struct IfcvtToken {
127       BBInfo &BBI;
128       IfcvtKind Kind;
129       bool NeedSubsumption;
130       unsigned NumDups;
131       unsigned NumDups2;
132       IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0)
133         : BBI(b), Kind(k), NeedSubsumption(s), NumDups(d), NumDups2(d2) {}
134     };
135
136     /// Roots - Basic blocks that do not have successors. These are the starting
137     /// points of Graph traversal.
138     std::vector<MachineBasicBlock*> Roots;
139
140     /// BBAnalysis - Results of if-conversion feasibility analysis indexed by
141     /// basic block number.
142     std::vector<BBInfo> BBAnalysis;
143
144     const TargetLowering *TLI;
145     const TargetInstrInfo *TII;
146     bool MadeChange;
147   public:
148     static char ID;
149     IfConverter() : MachineFunctionPass(&ID) {}
150
151     virtual bool runOnMachineFunction(MachineFunction &MF);
152     virtual const char *getPassName() const { return "If Converter"; }
153
154   private:
155     bool ReverseBranchCondition(BBInfo &BBI);
156     bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const;
157     bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
158                        bool FalseBranch, unsigned &Dups) const;
159     bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
160                       unsigned &Dups1, unsigned &Dups2) const;
161     void ScanInstructions(BBInfo &BBI);
162     BBInfo &AnalyzeBlock(MachineBasicBlock *BB,
163                          std::vector<IfcvtToken*> &Tokens);
164     bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
165                              bool isTriangle = false, bool RevBranch = false);
166     bool AnalyzeBlocks(MachineFunction &MF,
167                        std::vector<IfcvtToken*> &Tokens);
168     void InvalidatePreds(MachineBasicBlock *BB);
169     void RemoveExtraEdges(BBInfo &BBI);
170     bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
171     bool IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind);
172     bool IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
173                           unsigned NumDups1, unsigned NumDups2);
174     void PredicateBlock(BBInfo &BBI,
175                         MachineBasicBlock::iterator E,
176                         SmallVectorImpl<MachineOperand> &Cond);
177     void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
178                                SmallVectorImpl<MachineOperand> &Cond,
179                                bool IgnoreBr = false);
180     void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI);
181
182     bool MeetIfcvtSizeLimit(unsigned Size) const {
183       return Size > 0 && Size <= TLI->getIfCvtBlockSizeLimit();
184     }
185
186     // blockAlwaysFallThrough - Block ends without a terminator.
187     bool blockAlwaysFallThrough(BBInfo &BBI) const {
188       return BBI.IsBrAnalyzable && BBI.TrueBB == NULL;
189     }
190
191     // IfcvtTokenCmp - Used to sort if-conversion candidates.
192     static bool IfcvtTokenCmp(IfcvtToken *C1, IfcvtToken *C2) {
193       int Incr1 = (C1->Kind == ICDiamond)
194         ? -(int)(C1->NumDups + C1->NumDups2) : (int)C1->NumDups;
195       int Incr2 = (C2->Kind == ICDiamond)
196         ? -(int)(C2->NumDups + C2->NumDups2) : (int)C2->NumDups;
197       if (Incr1 > Incr2)
198         return true;
199       else if (Incr1 == Incr2) {
200         // Favors subsumption.
201         if (C1->NeedSubsumption == false && C2->NeedSubsumption == true)
202           return true;
203         else if (C1->NeedSubsumption == C2->NeedSubsumption) {
204           // Favors diamond over triangle, etc.
205           if ((unsigned)C1->Kind < (unsigned)C2->Kind)
206             return true;
207           else if (C1->Kind == C2->Kind)
208             return C1->BBI.BB->getNumber() < C2->BBI.BB->getNumber();
209         }
210       }
211       return false;
212     }
213   };
214
215   char IfConverter::ID = 0;
216 }
217
218 static RegisterPass<IfConverter>
219 X("if-converter", "If Converter");
220
221 FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); }
222
223 bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
224   TLI = MF.getTarget().getTargetLowering();
225   TII = MF.getTarget().getInstrInfo();
226   if (!TII) return false;
227
228   static int FnNum = -1;
229   DOUT << "\nIfcvt: function (" << ++FnNum <<  ") \'"
230        << MF.getFunction()->getName() << "\'";
231
232   if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) {
233     DOUT << " skipped\n";
234     return false;
235   }
236   DOUT << "\n";
237
238   MF.RenumberBlocks();
239   BBAnalysis.resize(MF.getNumBlockIDs());
240
241   // Look for root nodes, i.e. blocks without successors.
242   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
243     if (I->succ_empty())
244       Roots.push_back(I);
245
246   std::vector<IfcvtToken*> Tokens;
247   MadeChange = false;
248   unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +
249     NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;
250   while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) {
251     // Do an initial analysis for each basic block and find all the potential
252     // candidates to perform if-conversion.
253     bool Change = AnalyzeBlocks(MF, Tokens);
254     while (!Tokens.empty()) {
255       IfcvtToken *Token = Tokens.back();
256       Tokens.pop_back();
257       BBInfo &BBI = Token->BBI;
258       IfcvtKind Kind = Token->Kind;
259       unsigned NumDups = Token->NumDups;
260       unsigned NumDups2 = Token->NumDups2;
261
262       delete Token;
263
264       // If the block has been evicted out of the queue or it has already been
265       // marked dead (due to it being predicated), then skip it.
266       if (BBI.IsDone)
267         BBI.IsEnqueued = false;
268       if (!BBI.IsEnqueued)
269         continue;
270
271       BBI.IsEnqueued = false;
272
273       bool RetVal = false;
274       switch (Kind) {
275       default: assert(false && "Unexpected!");
276         break;
277       case ICSimple:
278       case ICSimpleFalse: {
279         bool isFalse = Kind == ICSimpleFalse;
280         if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break;
281         DOUT << "Ifcvt (Simple" << (Kind == ICSimpleFalse ? " false" :"")
282              << "): BB#" << BBI.BB->getNumber() << " ("
283              << ((Kind == ICSimpleFalse)
284                  ? BBI.FalseBB->getNumber()
285                  : BBI.TrueBB->getNumber()) << ") ";
286         RetVal = IfConvertSimple(BBI, Kind);
287         DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
288         if (RetVal) {
289           if (isFalse) NumSimpleFalse++;
290           else         NumSimple++;
291         }
292        break;
293       }
294       case ICTriangle:
295       case ICTriangleRev:
296       case ICTriangleFalse:
297       case ICTriangleFRev: {
298         bool isFalse = Kind == ICTriangleFalse;
299         bool isRev   = (Kind == ICTriangleRev || Kind == ICTriangleFRev);
300         if (DisableTriangle && !isFalse && !isRev) break;
301         if (DisableTriangleR && !isFalse && isRev) break;
302         if (DisableTriangleF && isFalse && !isRev) break;
303         if (DisableTriangleFR && isFalse && isRev) break;
304         DOUT << "Ifcvt (Triangle";
305         if (isFalse)
306           DOUT << " false";
307         if (isRev)
308           DOUT << " rev";
309         DOUT << "): BB#" << BBI.BB->getNumber() << " (T:"
310              << BBI.TrueBB->getNumber() << ",F:"
311              << BBI.FalseBB->getNumber() << ") ";
312         RetVal = IfConvertTriangle(BBI, Kind);
313         DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
314         if (RetVal) {
315           if (isFalse) {
316             if (isRev) NumTriangleFRev++;
317             else       NumTriangleFalse++;
318           } else {
319             if (isRev) NumTriangleRev++;
320             else       NumTriangle++;
321           }
322         }
323         break;
324       }
325       case ICDiamond: {
326         if (DisableDiamond) break;
327         DOUT << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:"
328              << BBI.TrueBB->getNumber() << ",F:"
329              << BBI.FalseBB->getNumber() << ") ";
330         RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2);
331         DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
332         if (RetVal) NumDiamonds++;
333         break;
334       }
335       }
336
337       Change |= RetVal;
338
339       NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +
340         NumTriangleFalse + NumTriangleFRev + NumDiamonds;
341       if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit)
342         break;
343     }
344
345     if (!Change)
346       break;
347     MadeChange |= Change;
348   }
349
350   // Delete tokens in case of early exit.
351   while (!Tokens.empty()) {
352     IfcvtToken *Token = Tokens.back();
353     Tokens.pop_back();
354     delete Token;
355   }
356
357   Tokens.clear();
358   Roots.clear();
359   BBAnalysis.clear();
360
361   return MadeChange;
362 }
363
364 /// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
365 /// its 'true' successor.
366 static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
367                                          MachineBasicBlock *TrueBB) {
368   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
369          E = BB->succ_end(); SI != E; ++SI) {
370     MachineBasicBlock *SuccBB = *SI;
371     if (SuccBB != TrueBB)
372       return SuccBB;
373   }
374   return NULL;
375 }
376
377 /// ReverseBranchCondition - Reverse the condition of the end of the block
378 /// branch. Swap block's 'true' and 'false' successors.
379 bool IfConverter::ReverseBranchCondition(BBInfo &BBI) {
380   if (!TII->ReverseBranchCondition(BBI.BrCond)) {
381     TII->RemoveBranch(*BBI.BB);
382     TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond);
383     std::swap(BBI.TrueBB, BBI.FalseBB);
384     return true;
385   }
386   return false;
387 }
388
389 /// getNextBlock - Returns the next block in the function blocks ordering. If
390 /// it is the end, returns NULL.
391 static inline MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) {
392   MachineFunction::iterator I = BB;
393   MachineFunction::iterator E = BB->getParent()->end();
394   if (++I == E)
395     return NULL;
396   return I;
397 }
398
399 /// ValidSimple - Returns true if the 'true' block (along with its
400 /// predecessor) forms a valid simple shape for ifcvt. It also returns the
401 /// number of instructions that the ifcvt would need to duplicate if performed
402 /// in Dups.
403 bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups) const {
404   Dups = 0;
405   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
406     return false;
407
408   if (TrueBBI.IsBrAnalyzable)
409     return false;
410
411   if (TrueBBI.BB->pred_size() > 1) {
412     if (TrueBBI.CannotBeCopied ||
413         TrueBBI.NonPredSize > TLI->getIfCvtDupBlockSizeLimit())
414       return false;
415     Dups = TrueBBI.NonPredSize;
416   }
417
418   return true;
419 }
420
421 /// ValidTriangle - Returns true if the 'true' and 'false' blocks (along
422 /// with their common predecessor) forms a valid triangle shape for ifcvt.
423 /// If 'FalseBranch' is true, it checks if 'true' block's false branch
424 /// branches to the false branch rather than the other way around. It also
425 /// returns the number of instructions that the ifcvt would need to duplicate
426 /// if performed in 'Dups'.
427 bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
428                                 bool FalseBranch, unsigned &Dups) const {
429   Dups = 0;
430   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
431     return false;
432
433   if (TrueBBI.BB->pred_size() > 1) {
434     if (TrueBBI.CannotBeCopied)
435       return false;
436
437     unsigned Size = TrueBBI.NonPredSize;
438     if (TrueBBI.IsBrAnalyzable) {
439       if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())
440         // Ends with an unconditional branch. It will be removed.
441         --Size;
442       else {
443         MachineBasicBlock *FExit = FalseBranch
444           ? TrueBBI.TrueBB : TrueBBI.FalseBB;
445         if (FExit)
446           // Require a conditional branch
447           ++Size;
448       }
449     }
450     if (Size > TLI->getIfCvtDupBlockSizeLimit())
451       return false;
452     Dups = Size;
453   }
454
455   MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;
456   if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
457     MachineFunction::iterator I = TrueBBI.BB;
458     if (++I == TrueBBI.BB->getParent()->end())
459       return false;
460     TExit = I;
461   }
462   return TExit && TExit == FalseBBI.BB;
463 }
464
465 static
466 MachineBasicBlock::iterator firstNonBranchInst(MachineBasicBlock *BB,
467                                                const TargetInstrInfo *TII) {
468   MachineBasicBlock::iterator I = BB->end();
469   while (I != BB->begin()) {
470     --I;
471     if (!I->getDesc().isBranch())
472       break;
473   }
474   return I;
475 }
476
477 /// ValidDiamond - Returns true if the 'true' and 'false' blocks (along
478 /// with their common predecessor) forms a valid diamond shape for ifcvt.
479 bool IfConverter::ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
480                                unsigned &Dups1, unsigned &Dups2) const {
481   Dups1 = Dups2 = 0;
482   if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone ||
483       FalseBBI.IsBeingAnalyzed || FalseBBI.IsDone)
484     return false;
485
486   MachineBasicBlock *TT = TrueBBI.TrueBB;
487   MachineBasicBlock *FT = FalseBBI.TrueBB;
488
489   if (!TT && blockAlwaysFallThrough(TrueBBI))
490     TT = getNextBlock(TrueBBI.BB);
491   if (!FT && blockAlwaysFallThrough(FalseBBI))
492     FT = getNextBlock(FalseBBI.BB);
493   if (TT != FT)
494     return false;
495   if (TT == NULL && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
496     return false;
497   if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
498     return false;
499
500   // FIXME: Allow true block to have an early exit?
501   if (TrueBBI.FalseBB || FalseBBI.FalseBB ||
502       (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred))
503     return false;
504
505   MachineBasicBlock::iterator TI = TrueBBI.BB->begin();
506   MachineBasicBlock::iterator FI = FalseBBI.BB->begin();
507   while (TI != TrueBBI.BB->end() && FI != FalseBBI.BB->end()) {
508     if (!TI->isIdenticalTo(FI))
509       break;
510     ++Dups1;
511     ++TI;
512     ++FI;
513   }
514
515   TI = firstNonBranchInst(TrueBBI.BB, TII);
516   FI = firstNonBranchInst(FalseBBI.BB, TII);
517   while (TI != TrueBBI.BB->begin() && FI != FalseBBI.BB->begin()) {
518     if (!TI->isIdenticalTo(FI))
519       break;
520     ++Dups2;
521     --TI;
522     --FI;
523   }
524
525   return true;
526 }
527
528 /// ScanInstructions - Scan all the instructions in the block to determine if
529 /// the block is predicable. In most cases, that means all the instructions
530 /// in the block are isPredicable(). Also checks if the block contains any
531 /// instruction which can clobber a predicate (e.g. condition code register).
532 /// If so, the block is not predicable unless it's the last instruction.
533 void IfConverter::ScanInstructions(BBInfo &BBI) {
534   if (BBI.IsDone)
535     return;
536
537   bool AlreadyPredicated = BBI.Predicate.size() > 0;
538   // First analyze the end of BB branches.
539   BBI.TrueBB = BBI.FalseBB = NULL;
540   BBI.BrCond.clear();
541   BBI.IsBrAnalyzable =
542     !TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
543   BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == NULL;
544
545   if (BBI.BrCond.size()) {
546     // No false branch. This BB must end with a conditional branch and a
547     // fallthrough.
548     if (!BBI.FalseBB)
549       BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);  
550     assert(BBI.FalseBB && "Expected to find the fallthrough block!");
551   }
552
553   // Then scan all the instructions.
554   BBI.NonPredSize = 0;
555   BBI.ClobbersPred = false;
556   bool SeenCondBr = false;
557   for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
558        I != E; ++I) {
559     const TargetInstrDesc &TID = I->getDesc();
560     if (TID.isNotDuplicable())
561       BBI.CannotBeCopied = true;
562
563     bool isPredicated = TII->isPredicated(I);
564     bool isCondBr = BBI.IsBrAnalyzable && TID.isConditionalBranch();
565
566     if (!isCondBr) {
567       if (!isPredicated)
568         BBI.NonPredSize++;
569       else if (!AlreadyPredicated) {
570         // FIXME: This instruction is already predicated before the
571         // if-conversion pass. It's probably something like a conditional move.
572         // Mark this block unpredicable for now.
573         BBI.IsUnpredicable = true;
574         return;
575       }
576     }
577
578     if (BBI.ClobbersPred && !isPredicated) {
579       // Predicate modification instruction should end the block (except for
580       // already predicated instructions and end of block branches).
581       if (isCondBr) {
582         SeenCondBr = true;
583
584         // A conditional branch is not predicable, but it may be eliminated.
585         continue;
586       }
587
588       // Predicate may have been modified, the subsequent (currently)
589       // unpredicated instructions cannot be correctly predicated.
590       BBI.IsUnpredicable = true;
591       return;
592     }
593
594     // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are
595     // still potentially predicable.
596     std::vector<MachineOperand> PredDefs;
597     if (TII->DefinesPredicate(I, PredDefs))
598       BBI.ClobbersPred = true;
599
600     if (!TID.isPredicable()) {
601       BBI.IsUnpredicable = true;
602       return;
603     }
604   }
605 }
606
607 /// FeasibilityAnalysis - Determine if the block is a suitable candidate to be
608 /// predicated by the specified predicate.
609 bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
610                                       SmallVectorImpl<MachineOperand> &Pred,
611                                       bool isTriangle, bool RevBranch) {
612   // If the block is dead or unpredicable, then it cannot be predicated.
613   if (BBI.IsDone || BBI.IsUnpredicable)
614     return false;
615
616   // If it is already predicated, check if its predicate subsumes the new
617   // predicate.
618   if (BBI.Predicate.size() && !TII->SubsumesPredicate(BBI.Predicate, Pred))
619     return false;
620
621   if (BBI.BrCond.size()) {
622     if (!isTriangle)
623       return false;
624
625     // Test predicate subsumption.
626     SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end());
627     SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
628     if (RevBranch) {
629       if (TII->ReverseBranchCondition(Cond))
630         return false;
631     }
632     if (TII->ReverseBranchCondition(RevPred) ||
633         !TII->SubsumesPredicate(Cond, RevPred))
634       return false;
635   }
636
637   return true;
638 }
639
640 /// AnalyzeBlock - Analyze the structure of the sub-CFG starting from
641 /// the specified block. Record its successors and whether it looks like an
642 /// if-conversion candidate.
643 IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB,
644                                              std::vector<IfcvtToken*> &Tokens) {
645   BBInfo &BBI = BBAnalysis[BB->getNumber()];
646
647   if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed)
648     return BBI;
649
650   BBI.BB = BB;
651   BBI.IsBeingAnalyzed = true;
652
653   ScanInstructions(BBI);
654
655   // Unanalyzable or ends with fallthrough or unconditional branch.
656   if (!BBI.IsBrAnalyzable || BBI.BrCond.empty()) {
657     BBI.IsBeingAnalyzed = false;
658     BBI.IsAnalyzed = true;
659     return BBI;
660   }
661
662   // Do not ifcvt if either path is a back edge to the entry block.
663   if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
664     BBI.IsBeingAnalyzed = false;
665     BBI.IsAnalyzed = true;
666     return BBI;
667   }
668
669   BBInfo &TrueBBI  = AnalyzeBlock(BBI.TrueBB, Tokens);
670   BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens);
671
672   if (TrueBBI.IsDone && FalseBBI.IsDone) {
673     BBI.IsBeingAnalyzed = false;
674     BBI.IsAnalyzed = true;
675     return BBI;
676   }
677
678   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
679   bool CanRevCond = !TII->ReverseBranchCondition(RevCond);
680
681   unsigned Dups = 0;
682   unsigned Dups2 = 0;
683   bool TNeedSub = TrueBBI.Predicate.size() > 0;
684   bool FNeedSub = FalseBBI.Predicate.size() > 0;
685   bool Enqueued = false;
686   if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) &&
687       MeetIfcvtSizeLimit(TrueBBI.NonPredSize - (Dups + Dups2)) &&
688       MeetIfcvtSizeLimit(FalseBBI.NonPredSize - (Dups + Dups2)) &&
689       FeasibilityAnalysis(TrueBBI, BBI.BrCond) &&
690       FeasibilityAnalysis(FalseBBI, RevCond)) {
691     // Diamond:
692     //   EBB
693     //   / \_
694     //  |   |
695     // TBB FBB
696     //   \ /
697     //  TailBB
698     // Note TailBB can be empty.
699     Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups,
700                                     Dups2));
701     Enqueued = true;
702   }
703
704   if (ValidTriangle(TrueBBI, FalseBBI, false, Dups) &&
705       MeetIfcvtSizeLimit(TrueBBI.NonPredSize) &&
706       FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
707     // Triangle:
708     //   EBB
709     //   | \_
710     //   |  |
711     //   | TBB
712     //   |  /
713     //   FBB
714     Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups));
715     Enqueued = true;
716   }
717   
718   if (ValidTriangle(TrueBBI, FalseBBI, true, Dups) &&
719       MeetIfcvtSizeLimit(TrueBBI.NonPredSize) &&
720       FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
721     Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups));
722     Enqueued = true;
723   }
724
725   if (ValidSimple(TrueBBI, Dups) &&
726       MeetIfcvtSizeLimit(TrueBBI.NonPredSize) &&
727       FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
728     // Simple (split, no rejoin):
729     //   EBB
730     //   | \_
731     //   |  |
732     //   | TBB---> exit
733     //   |    
734     //   FBB
735     Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups));
736     Enqueued = true;
737   }
738
739   if (CanRevCond) {
740     // Try the other path...
741     if (ValidTriangle(FalseBBI, TrueBBI, false, Dups) &&
742         MeetIfcvtSizeLimit(FalseBBI.NonPredSize) &&
743         FeasibilityAnalysis(FalseBBI, RevCond, true)) {
744       Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups));
745       Enqueued = true;
746     }
747
748     if (ValidTriangle(FalseBBI, TrueBBI, true, Dups) &&
749         MeetIfcvtSizeLimit(FalseBBI.NonPredSize) &&
750         FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
751       Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups));
752       Enqueued = true;
753     }
754
755     if (ValidSimple(FalseBBI, Dups) &&
756         MeetIfcvtSizeLimit(FalseBBI.NonPredSize) &&
757         FeasibilityAnalysis(FalseBBI, RevCond)) {
758       Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups));
759       Enqueued = true;
760     }
761   }
762
763   BBI.IsEnqueued = Enqueued;
764   BBI.IsBeingAnalyzed = false;
765   BBI.IsAnalyzed = true;
766   return BBI;
767 }
768
769 /// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
770 /// candidates. It returns true if any CFG restructuring is done to expose more
771 /// if-conversion opportunities.
772 bool IfConverter::AnalyzeBlocks(MachineFunction &MF,
773                                 std::vector<IfcvtToken*> &Tokens) {
774   bool Change = false;
775   std::set<MachineBasicBlock*> Visited;
776   for (unsigned i = 0, e = Roots.size(); i != e; ++i) {
777     for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited),
778            E = idf_ext_end(Roots[i], Visited); I != E; ++I) {
779       MachineBasicBlock *BB = *I;
780       AnalyzeBlock(BB, Tokens);
781     }
782   }
783
784   // Sort to favor more complex ifcvt scheme.
785   std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp);
786
787   return Change;
788 }
789
790 /// canFallThroughTo - Returns true either if ToBB is the next block after BB or
791 /// that all the intervening blocks are empty (given BB can fall through to its
792 /// next block).
793 static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) {
794   MachineFunction::iterator I = BB;
795   MachineFunction::iterator TI = ToBB;
796   MachineFunction::iterator E = BB->getParent()->end();
797   while (++I != TI)
798     if (I == E || !I->empty())
799       return false;
800   return true;
801 }
802
803 /// InvalidatePreds - Invalidate predecessor BB info so it would be re-analyzed
804 /// to determine if it can be if-converted. If predecessor is already enqueued,
805 /// dequeue it!
806 void IfConverter::InvalidatePreds(MachineBasicBlock *BB) {
807   for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
808          E = BB->pred_end(); PI != E; ++PI) {
809     BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()];
810     if (PBBI.IsDone || PBBI.BB == BB)
811       continue;
812     PBBI.IsAnalyzed = false;
813     PBBI.IsEnqueued = false;
814   }
815 }
816
817 /// InsertUncondBranch - Inserts an unconditional branch from BB to ToBB.
818 ///
819 static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB,
820                                const TargetInstrInfo *TII) {
821   SmallVector<MachineOperand, 0> NoCond;
822   TII->InsertBranch(*BB, ToBB, NULL, NoCond);
823 }
824
825 /// RemoveExtraEdges - Remove true / false edges if either / both are no longer
826 /// successors.
827 void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
828   MachineBasicBlock *TBB = NULL, *FBB = NULL;
829   SmallVector<MachineOperand, 4> Cond;
830   if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond))
831     BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
832 }
833
834 /// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG.
835 ///
836 bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
837   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
838   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
839   BBInfo *CvtBBI = &TrueBBI;
840   BBInfo *NextBBI = &FalseBBI;
841
842   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
843   if (Kind == ICSimpleFalse)
844     std::swap(CvtBBI, NextBBI);
845
846   if (CvtBBI->IsDone ||
847       (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
848     // Something has changed. It's no longer safe to predicate this block.
849     BBI.IsAnalyzed = false;
850     CvtBBI->IsAnalyzed = false;
851     return false;
852   }
853
854   if (Kind == ICSimpleFalse)
855     if (TII->ReverseBranchCondition(Cond))
856       assert(false && "Unable to reverse branch condition!");
857
858   if (CvtBBI->BB->pred_size() > 1) {
859     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
860     // Copy instructions in the true block, predicate them, and add them to
861     // the entry block.
862     CopyAndPredicateBlock(BBI, *CvtBBI, Cond);
863   } else {
864     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
865
866     // Merge converted block into entry block.
867     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
868     MergeBlocks(BBI, *CvtBBI);
869   }
870
871   bool IterIfcvt = true;
872   if (!canFallThroughTo(BBI.BB, NextBBI->BB)) {
873     InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
874     BBI.HasFallThrough = false;
875     // Now ifcvt'd block will look like this:
876     // BB:
877     // ...
878     // t, f = cmp
879     // if t op
880     // b BBf
881     //
882     // We cannot further ifcvt this block because the unconditional branch
883     // will have to be predicated on the new condition, that will not be
884     // available if cmp executes.
885     IterIfcvt = false;
886   }
887
888   RemoveExtraEdges(BBI);
889
890   // Update block info. BB can be iteratively if-converted.
891   if (!IterIfcvt)
892     BBI.IsDone = true;
893   InvalidatePreds(BBI.BB);
894   CvtBBI->IsDone = true;
895
896   // FIXME: Must maintain LiveIns.
897   return true;
898 }
899
900 /// IfConvertTriangle - If convert a triangle sub-CFG.
901 ///
902 bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
903   BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
904   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
905   BBInfo *CvtBBI = &TrueBBI;
906   BBInfo *NextBBI = &FalseBBI;
907
908   SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
909   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
910     std::swap(CvtBBI, NextBBI);
911
912   if (CvtBBI->IsDone ||
913       (CvtBBI->CannotBeCopied && CvtBBI->BB->pred_size() > 1)) {
914     // Something has changed. It's no longer safe to predicate this block.
915     BBI.IsAnalyzed = false;
916     CvtBBI->IsAnalyzed = false;
917     return false;
918   }
919
920   if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
921     if (TII->ReverseBranchCondition(Cond))
922       assert(false && "Unable to reverse branch condition!");
923
924   if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
925     if (ReverseBranchCondition(*CvtBBI)) {
926       // BB has been changed, modify its predecessors (except for this
927       // one) so they don't get ifcvt'ed based on bad intel.
928       for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(),
929              E = CvtBBI->BB->pred_end(); PI != E; ++PI) {
930         MachineBasicBlock *PBB = *PI;
931         if (PBB == BBI.BB)
932           continue;
933         BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
934         if (PBBI.IsEnqueued) {
935           PBBI.IsAnalyzed = false;
936           PBBI.IsEnqueued = false;
937         }
938       }
939     }
940   }
941
942   bool HasEarlyExit = CvtBBI->FalseBB != NULL;
943   bool DupBB = CvtBBI->BB->pred_size() > 1;
944   if (DupBB) {
945     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
946     // Copy instructions in the true block, predicate them, and add them to
947     // the entry block.
948     CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);
949   } else {
950     // Predicate the 'true' block after removing its branch.
951     CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
952     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
953   }
954
955   if (!DupBB) {
956     // Now merge the entry of the triangle with the true block.
957     BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
958     MergeBlocks(BBI, *CvtBBI);
959   }
960
961   // If 'true' block has a 'false' successor, add an exit branch to it.
962   if (HasEarlyExit) {
963     SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
964                                            CvtBBI->BrCond.end());
965     if (TII->ReverseBranchCondition(RevCond))
966       assert(false && "Unable to reverse branch condition!");
967     TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond);
968     BBI.BB->addSuccessor(CvtBBI->FalseBB);
969   }
970
971   // Merge in the 'false' block if the 'false' block has no other
972   // predecessors. Otherwise, add an unconditional branch to 'false'.
973   bool FalseBBDead = false;
974   bool IterIfcvt = true;
975   bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB);
976   if (!isFallThrough) {
977     // Only merge them if the true block does not fallthrough to the false
978     // block. By not merging them, we make it possible to iteratively
979     // ifcvt the blocks.
980     if (!HasEarlyExit &&
981         NextBBI->BB->pred_size() == 1 && !NextBBI->HasFallThrough) {
982       MergeBlocks(BBI, *NextBBI);
983       FalseBBDead = true;
984     } else {
985       InsertUncondBranch(BBI.BB, NextBBI->BB, TII);
986       BBI.HasFallThrough = false;
987     }
988     // Mixed predicated and unpredicated code. This cannot be iteratively
989     // predicated.
990     IterIfcvt = false;
991   }
992
993   RemoveExtraEdges(BBI);
994
995   // Update block info. BB can be iteratively if-converted.
996   if (!IterIfcvt) 
997     BBI.IsDone = true;
998   InvalidatePreds(BBI.BB);
999   CvtBBI->IsDone = true;
1000   if (FalseBBDead)
1001     NextBBI->IsDone = true;
1002
1003   // FIXME: Must maintain LiveIns.
1004   return true;
1005 }
1006
1007 /// IfConvertDiamond - If convert a diamond sub-CFG.
1008 ///
1009 bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
1010                                    unsigned NumDups1, unsigned NumDups2) {
1011   BBInfo &TrueBBI  = BBAnalysis[BBI.TrueBB->getNumber()];
1012   BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
1013   MachineBasicBlock *TailBB = TrueBBI.TrueBB;
1014   // True block must fall through or end with an unanalyzable terminator.
1015   if (!TailBB) {
1016     if (blockAlwaysFallThrough(TrueBBI))
1017       TailBB = FalseBBI.TrueBB;
1018     assert((TailBB || !TrueBBI.IsBrAnalyzable) && "Unexpected!");
1019   }
1020
1021   if (TrueBBI.IsDone || FalseBBI.IsDone ||
1022       TrueBBI.BB->pred_size() > 1 ||
1023       FalseBBI.BB->pred_size() > 1) {
1024     // Something has changed. It's no longer safe to predicate these blocks.
1025     BBI.IsAnalyzed = false;
1026     TrueBBI.IsAnalyzed = false;
1027     FalseBBI.IsAnalyzed = false;
1028     return false;
1029   }
1030
1031   // Merge the 'true' and 'false' blocks by copying the instructions
1032   // from the 'false' block to the 'true' block. That is, unless the true
1033   // block would clobber the predicate, in that case, do the opposite.
1034   BBInfo *BBI1 = &TrueBBI;
1035   BBInfo *BBI2 = &FalseBBI;
1036   SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1037   if (TII->ReverseBranchCondition(RevCond))
1038     assert(false && "Unable to reverse branch condition!");
1039   SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
1040   SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
1041
1042   // Figure out the more profitable ordering.
1043   bool DoSwap = false;
1044   if (TrueBBI.ClobbersPred && !FalseBBI.ClobbersPred)
1045     DoSwap = true;
1046   else if (TrueBBI.ClobbersPred == FalseBBI.ClobbersPred) {
1047     if (TrueBBI.NonPredSize > FalseBBI.NonPredSize)
1048       DoSwap = true;
1049   }
1050   if (DoSwap) {
1051     std::swap(BBI1, BBI2);
1052     std::swap(Cond1, Cond2);
1053   }
1054
1055   // Remove the conditional branch from entry to the blocks.
1056   BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1057
1058   // Remove the duplicated instructions at the beginnings of both paths.
1059   MachineBasicBlock::iterator DI1 = BBI1->BB->begin();
1060   MachineBasicBlock::iterator DI2 = BBI2->BB->begin();
1061   BBI1->NonPredSize -= NumDups1;
1062   BBI2->NonPredSize -= NumDups1;
1063   while (NumDups1 != 0) {
1064     ++DI1;
1065     ++DI2;
1066     --NumDups1;
1067   }
1068   BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
1069   BBI2->BB->erase(BBI2->BB->begin(), DI2);
1070
1071   // Predicate the 'true' block after removing its branch.
1072   BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
1073   DI1 = BBI1->BB->end();
1074   for (unsigned i = 0; i != NumDups2; ++i)
1075     --DI1;
1076   BBI1->BB->erase(DI1, BBI1->BB->end());
1077   PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1);
1078
1079   // Predicate the 'false' block.
1080   BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
1081   DI2 = BBI2->BB->end();
1082   while (NumDups2 != 0) {
1083     --DI2;
1084     --NumDups2;
1085   }
1086   PredicateBlock(*BBI2, DI2, *Cond2);
1087
1088   // Merge the true block into the entry of the diamond.
1089   MergeBlocks(BBI, *BBI1);
1090   MergeBlocks(BBI, *BBI2);
1091
1092   // If the if-converted block falls through or unconditionally branches into
1093   // the tail block, and the tail block does not have other predecessors, then
1094   // fold the tail block in as well. Otherwise, unless it falls through to the
1095   // tail, add a unconditional branch to it.
1096   if (TailBB) {
1097     BBInfo TailBBI = BBAnalysis[TailBB->getNumber()];
1098     if (TailBB->pred_size() == 1 && !TailBBI.HasFallThrough) {
1099       BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1100       MergeBlocks(BBI, TailBBI);
1101       TailBBI.IsDone = true;
1102     } else {
1103       InsertUncondBranch(BBI.BB, TailBB, TII);
1104       BBI.HasFallThrough = false;
1105     }
1106   }
1107
1108   RemoveExtraEdges(BBI);
1109
1110   // Update block info.
1111   BBI.IsDone = TrueBBI.IsDone = FalseBBI.IsDone = true;
1112   InvalidatePreds(BBI.BB);
1113
1114   // FIXME: Must maintain LiveIns.
1115   return true;
1116 }
1117
1118 /// PredicateBlock - Predicate instructions from the start of the block to the
1119 /// specified end with the specified condition.
1120 void IfConverter::PredicateBlock(BBInfo &BBI,
1121                                  MachineBasicBlock::iterator E,
1122                                  SmallVectorImpl<MachineOperand> &Cond) {
1123   for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
1124     if (TII->isPredicated(I))
1125       continue;
1126     if (!TII->PredicateInstruction(I, Cond)) {
1127       cerr << "Unable to predicate " << *I << "!\n";
1128       abort();
1129     }
1130   }
1131
1132   std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
1133
1134   BBI.IsAnalyzed = false;
1135   BBI.NonPredSize = 0;
1136
1137   NumIfConvBBs++;
1138 }
1139
1140 /// CopyAndPredicateBlock - Copy and predicate instructions from source BB to
1141 /// the destination block. Skip end of block branches if IgnoreBr is true.
1142 void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
1143                                         SmallVectorImpl<MachineOperand> &Cond,
1144                                         bool IgnoreBr) {
1145   MachineFunction &MF = *ToBBI.BB->getParent();
1146
1147   for (MachineBasicBlock::iterator I = FromBBI.BB->begin(),
1148          E = FromBBI.BB->end(); I != E; ++I) {
1149     const TargetInstrDesc &TID = I->getDesc();
1150     bool isPredicated = TII->isPredicated(I);
1151     // Do not copy the end of the block branches.
1152     if (IgnoreBr && !isPredicated && TID.isBranch())
1153       break;
1154
1155     MachineInstr *MI = MF.CloneMachineInstr(I);
1156     ToBBI.BB->insert(ToBBI.BB->end(), MI);
1157     ToBBI.NonPredSize++;
1158
1159     if (!isPredicated)
1160       if (!TII->PredicateInstruction(MI, Cond)) {
1161         cerr << "Unable to predicate " << *MI << "!\n";
1162         abort();
1163       }
1164   }
1165
1166   std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1167                                          FromBBI.BB->succ_end());
1168   MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1169   MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
1170
1171   for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1172     MachineBasicBlock *Succ = Succs[i];
1173     // Fallthrough edge can't be transferred.
1174     if (Succ == FallThrough)
1175       continue;
1176     ToBBI.BB->addSuccessor(Succ);
1177   }
1178
1179   std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1180             std::back_inserter(ToBBI.Predicate));
1181   std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate));
1182
1183   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1184   ToBBI.IsAnalyzed = false;
1185
1186   NumDupBBs++;
1187 }
1188
1189 /// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
1190 ///
1191 void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) {
1192   ToBBI.BB->splice(ToBBI.BB->end(),
1193                    FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
1194
1195   // Redirect all branches to FromBB to ToBB.
1196   std::vector<MachineBasicBlock *> Preds(FromBBI.BB->pred_begin(),
1197                                          FromBBI.BB->pred_end());
1198   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
1199     MachineBasicBlock *Pred = Preds[i];
1200     if (Pred == ToBBI.BB)
1201       continue;
1202     Pred->ReplaceUsesOfBlockWith(FromBBI.BB, ToBBI.BB);
1203   }
1204  
1205   std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1206                                          FromBBI.BB->succ_end());
1207   MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1208   MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
1209
1210   for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1211     MachineBasicBlock *Succ = Succs[i];
1212     // Fallthrough edge can't be transferred.
1213     if (Succ == FallThrough)
1214       continue;
1215     FromBBI.BB->removeSuccessor(Succ);
1216     ToBBI.BB->addSuccessor(Succ);
1217   }
1218
1219   // Now FromBBI always falls through to the next block!
1220   if (NBB)
1221     FromBBI.BB->addSuccessor(NBB);
1222
1223   std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1224             std::back_inserter(ToBBI.Predicate));
1225   FromBBI.Predicate.clear();
1226
1227   ToBBI.NonPredSize += FromBBI.NonPredSize;
1228   FromBBI.NonPredSize = 0;
1229
1230   ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1231   ToBBI.HasFallThrough = FromBBI.HasFallThrough;
1232   ToBBI.IsAnalyzed = false;
1233   FromBBI.IsAnalyzed = false;
1234 }