rename isStore -> mayStore to more accurately reflect what it captures.
[oota-llvm.git] / lib / CodeGen / BranchFolding.cpp
1 //===-- BranchFolding.cpp - Fold machine code branch instructions ---------===//
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 pass forwards branches to unconditional branches to make them branch
11 // directly to the target block.  This pass often results in dead MBB's, which
12 // it then removes.
13 //
14 // Note that this pass must be run after register allocation, it cannot handle
15 // SSA form.
16 //
17 //===----------------------------------------------------------------------===//
18
19 #define DEBUG_TYPE "branchfolding"
20 #include "llvm/CodeGen/Passes.h"
21 #include "llvm/CodeGen/MachineModuleInfo.h"
22 #include "llvm/CodeGen/MachineFunctionPass.h"
23 #include "llvm/CodeGen/MachineJumpTableInfo.h"
24 #include "llvm/CodeGen/RegisterScavenging.h"
25 #include "llvm/Target/TargetInstrInfo.h"
26 #include "llvm/Target/TargetMachine.h"
27 #include "llvm/Target/MRegisterInfo.h"
28 #include "llvm/Support/CommandLine.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/ADT/STLExtras.h"
32 #include <algorithm>
33 using namespace llvm;
34
35 STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
36 STATISTIC(NumBranchOpts, "Number of branches optimized");
37 STATISTIC(NumTailMerge , "Number of block tails merged");
38 static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge", 
39                               cl::init(cl::BOU_UNSET), cl::Hidden);
40 namespace {
41   // Throttle for huge numbers of predecessors (compile speed problems)
42   cl::opt<unsigned>
43   TailMergeThreshold("tail-merge-threshold", 
44             cl::desc("Max number of predecessors to consider tail merging"),
45             cl::init(100), cl::Hidden);
46
47   struct BranchFolder : public MachineFunctionPass {
48     static char ID;
49     explicit BranchFolder(bool defaultEnableTailMerge) : 
50         MachineFunctionPass((intptr_t)&ID) {
51           switch (FlagEnableTailMerge) {
52           case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break;
53           case cl::BOU_TRUE: EnableTailMerge = true; break;
54           case cl::BOU_FALSE: EnableTailMerge = false; break;
55           }
56     }
57
58     virtual bool runOnMachineFunction(MachineFunction &MF);
59     virtual const char *getPassName() const { return "Control Flow Optimizer"; }
60     const TargetInstrInfo *TII;
61     MachineModuleInfo *MMI;
62     bool MadeChange;
63   private:
64     // Tail Merging.
65     bool EnableTailMerge;
66     bool TailMergeBlocks(MachineFunction &MF);
67     bool TryMergeBlocks(MachineBasicBlock* SuccBB,
68                         MachineBasicBlock* PredBB);
69     void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
70                                  MachineBasicBlock *NewDest);
71     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
72                                   MachineBasicBlock::iterator BBI1);
73
74     std::vector<std::pair<unsigned,MachineBasicBlock*> > MergePotentials;
75     const MRegisterInfo *RegInfo;
76     RegScavenger *RS;
77     // Branch optzn.
78     bool OptimizeBranches(MachineFunction &MF);
79     void OptimizeBlock(MachineBasicBlock *MBB);
80     void RemoveDeadBlock(MachineBasicBlock *MBB);
81     
82     bool CanFallThrough(MachineBasicBlock *CurBB);
83     bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable,
84                         MachineBasicBlock *TBB, MachineBasicBlock *FBB,
85                         const std::vector<MachineOperand> &Cond);
86   };
87   char BranchFolder::ID = 0;
88 }
89
90 FunctionPass *llvm::createBranchFoldingPass(bool DefaultEnableTailMerge) { 
91       return new BranchFolder(DefaultEnableTailMerge); }
92
93 /// RemoveDeadBlock - Remove the specified dead machine basic block from the
94 /// function, updating the CFG.
95 void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
96   assert(MBB->pred_empty() && "MBB must be dead!");
97   DOUT << "\nRemoving MBB: " << *MBB;
98   
99   MachineFunction *MF = MBB->getParent();
100   // drop all successors.
101   while (!MBB->succ_empty())
102     MBB->removeSuccessor(MBB->succ_end()-1);
103   
104   // If there is DWARF info to active, check to see if there are any LABEL
105   // records in the basic block.  If so, unregister them from MachineModuleInfo.
106   if (MMI && !MBB->empty()) {
107     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
108          I != E; ++I) {
109       if ((unsigned)I->getOpcode() == TargetInstrInfo::LABEL) {
110         // The label ID # is always operand #0, an immediate.
111         MMI->InvalidateLabel(I->getOperand(0).getImm());
112       }
113     }
114   }
115   
116   // Remove the block.
117   MF->getBasicBlockList().erase(MBB);
118 }
119
120 bool BranchFolder::runOnMachineFunction(MachineFunction &MF) {
121   TII = MF.getTarget().getInstrInfo();
122   if (!TII) return false;
123
124   // Fix CFG.  The later algorithms expect it to be right.
125   bool EverMadeChange = false;
126   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) {
127     MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0;
128     std::vector<MachineOperand> Cond;
129     if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
130       EverMadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
131   }
132
133   RegInfo = MF.getTarget().getRegisterInfo();
134   RS = RegInfo->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL;
135
136   MMI = getAnalysisToUpdate<MachineModuleInfo>();
137
138   bool MadeChangeThisIteration = true;
139   while (MadeChangeThisIteration) {
140     MadeChangeThisIteration = false;
141     MadeChangeThisIteration |= TailMergeBlocks(MF);
142     MadeChangeThisIteration |= OptimizeBranches(MF);
143     EverMadeChange |= MadeChangeThisIteration;
144   }
145
146   // See if any jump tables have become mergable or dead as the code generator
147   // did its thing.
148   MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
149   const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables();
150   if (!JTs.empty()) {
151     // Figure out how these jump tables should be merged.
152     std::vector<unsigned> JTMapping;
153     JTMapping.reserve(JTs.size());
154     
155     // We always keep the 0th jump table.
156     JTMapping.push_back(0);
157
158     // Scan the jump tables, seeing if there are any duplicates.  Note that this
159     // is N^2, which should be fixed someday.
160     for (unsigned i = 1, e = JTs.size(); i != e; ++i)
161       JTMapping.push_back(JTI->getJumpTableIndex(JTs[i].MBBs));
162     
163     // If a jump table was merge with another one, walk the function rewriting
164     // references to jump tables to reference the new JT ID's.  Keep track of
165     // whether we see a jump table idx, if not, we can delete the JT.
166     std::vector<bool> JTIsLive;
167     JTIsLive.resize(JTs.size());
168     for (MachineFunction::iterator BB = MF.begin(), E = MF.end();
169          BB != E; ++BB) {
170       for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end();
171            I != E; ++I)
172         for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) {
173           MachineOperand &Op = I->getOperand(op);
174           if (!Op.isJumpTableIndex()) continue;
175           unsigned NewIdx = JTMapping[Op.getIndex()];
176           Op.setIndex(NewIdx);
177
178           // Remember that this JT is live.
179           JTIsLive[NewIdx] = true;
180         }
181     }
182    
183     // Finally, remove dead jump tables.  This happens either because the
184     // indirect jump was unreachable (and thus deleted) or because the jump
185     // table was merged with some other one.
186     for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
187       if (!JTIsLive[i]) {
188         JTI->RemoveJumpTable(i);
189         EverMadeChange = true;
190       }
191   }
192   
193   delete RS;
194   return EverMadeChange;
195 }
196
197 //===----------------------------------------------------------------------===//
198 //  Tail Merging of Blocks
199 //===----------------------------------------------------------------------===//
200
201 /// HashMachineInstr - Compute a hash value for MI and its operands.
202 static unsigned HashMachineInstr(const MachineInstr *MI) {
203   unsigned Hash = MI->getOpcode();
204   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
205     const MachineOperand &Op = MI->getOperand(i);
206     
207     // Merge in bits from the operand if easy.
208     unsigned OperandHash = 0;
209     switch (Op.getType()) {
210     case MachineOperand::MO_Register:          OperandHash = Op.getReg(); break;
211     case MachineOperand::MO_Immediate:         OperandHash = Op.getImm(); break;
212     case MachineOperand::MO_MachineBasicBlock:
213       OperandHash = Op.getMBB()->getNumber();
214       break;
215     case MachineOperand::MO_FrameIndex:
216     case MachineOperand::MO_ConstantPoolIndex:
217     case MachineOperand::MO_JumpTableIndex:
218       OperandHash = Op.getIndex();
219       break;
220     case MachineOperand::MO_GlobalAddress:
221     case MachineOperand::MO_ExternalSymbol:
222       // Global address / external symbol are too hard, don't bother, but do
223       // pull in the offset.
224       OperandHash = Op.getOffset();
225       break;
226     default: break;
227     }
228     
229     Hash += ((OperandHash << 3) | Op.getType()) << (i&31);
230   }
231   return Hash;
232 }
233
234 /// HashEndOfMBB - Hash the last few instructions in the MBB.  For blocks
235 /// with no successors, we hash two instructions, because cross-jumping 
236 /// only saves code when at least two instructions are removed (since a 
237 /// branch must be inserted).  For blocks with a successor, one of the
238 /// two blocks to be tail-merged will end with a branch already, so
239 /// it gains to cross-jump even for one instruction.
240
241 static unsigned HashEndOfMBB(const MachineBasicBlock *MBB,
242                              unsigned minCommonTailLength) {
243   MachineBasicBlock::const_iterator I = MBB->end();
244   if (I == MBB->begin())
245     return 0;   // Empty MBB.
246   
247   --I;
248   unsigned Hash = HashMachineInstr(I);
249     
250   if (I == MBB->begin() || minCommonTailLength == 1)
251     return Hash;   // Single instr MBB.
252   
253   --I;
254   // Hash in the second-to-last instruction.
255   Hash ^= HashMachineInstr(I) << 2;
256   return Hash;
257 }
258
259 /// ComputeCommonTailLength - Given two machine basic blocks, compute the number
260 /// of instructions they actually have in common together at their end.  Return
261 /// iterators for the first shared instruction in each block.
262 static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
263                                         MachineBasicBlock *MBB2,
264                                         MachineBasicBlock::iterator &I1,
265                                         MachineBasicBlock::iterator &I2) {
266   I1 = MBB1->end();
267   I2 = MBB2->end();
268   
269   unsigned TailLen = 0;
270   while (I1 != MBB1->begin() && I2 != MBB2->begin()) {
271     --I1; --I2;
272     if (!I1->isIdenticalTo(I2) || 
273         // FIXME: This check is dubious. It's used to get around a problem where
274         // people incorrectly expect inline asm directives to remain in the same
275         // relative order. This is untenable because normal compiler
276         // optimizations (like this one) may reorder and/or merge these
277         // directives.
278         I1->getOpcode() == TargetInstrInfo::INLINEASM) {
279       ++I1; ++I2;
280       break;
281     }
282     ++TailLen;
283   }
284   return TailLen;
285 }
286
287 /// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything
288 /// after it, replacing it with an unconditional branch to NewDest.  This
289 /// returns true if OldInst's block is modified, false if NewDest is modified.
290 void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
291                                            MachineBasicBlock *NewDest) {
292   MachineBasicBlock *OldBB = OldInst->getParent();
293   
294   // Remove all the old successors of OldBB from the CFG.
295   while (!OldBB->succ_empty())
296     OldBB->removeSuccessor(OldBB->succ_begin());
297   
298   // Remove all the dead instructions from the end of OldBB.
299   OldBB->erase(OldInst, OldBB->end());
300
301   // If OldBB isn't immediately before OldBB, insert a branch to it.
302   if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest))
303     TII->InsertBranch(*OldBB, NewDest, 0, std::vector<MachineOperand>());
304   OldBB->addSuccessor(NewDest);
305   ++NumTailMerge;
306 }
307
308 /// SplitMBBAt - Given a machine basic block and an iterator into it, split the
309 /// MBB so that the part before the iterator falls into the part starting at the
310 /// iterator.  This returns the new MBB.
311 MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
312                                             MachineBasicBlock::iterator BBI1) {
313   // Create the fall-through block.
314   MachineFunction::iterator MBBI = &CurMBB;
315   MachineBasicBlock *NewMBB = new MachineBasicBlock(CurMBB.getBasicBlock());
316   CurMBB.getParent()->getBasicBlockList().insert(++MBBI, NewMBB);
317
318   // Move all the successors of this block to the specified block.
319   while (!CurMBB.succ_empty()) {
320     MachineBasicBlock *S = *(CurMBB.succ_end()-1);
321     NewMBB->addSuccessor(S);
322     CurMBB.removeSuccessor(S);
323   }
324  
325   // Add an edge from CurMBB to NewMBB for the fall-through.
326   CurMBB.addSuccessor(NewMBB);
327   
328   // Splice the code over.
329   NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());
330
331   // For targets that use the register scavenger, we must maintain LiveIns.
332   if (RS) {
333     RS->enterBasicBlock(&CurMBB);
334     if (!CurMBB.empty())
335       RS->forward(prior(CurMBB.end()));
336     BitVector RegsLiveAtExit(RegInfo->getNumRegs());
337     RS->getRegsUsed(RegsLiveAtExit, false);
338     for (unsigned int i=0, e=RegInfo->getNumRegs(); i!=e; i++)
339       if (RegsLiveAtExit[i])
340         NewMBB->addLiveIn(i);
341   }
342
343   return NewMBB;
344 }
345
346 /// EstimateRuntime - Make a rough estimate for how long it will take to run
347 /// the specified code.
348 static unsigned EstimateRuntime(MachineBasicBlock::iterator I,
349                                 MachineBasicBlock::iterator E,
350                                 const TargetInstrInfo *TII) {
351   unsigned Time = 0;
352   for (; I != E; ++I) {
353     const TargetInstrDescriptor &TID = TII->get(I->getOpcode());
354     if (TID.Flags & M_CALL_FLAG)
355       Time += 10;
356     else if (TID.Flags & (M_LOAD_FLAG|M_MAY_STORE_FLAG))
357       Time += 2;
358     else
359       ++Time;
360   }
361   return Time;
362 }
363
364 /// ShouldSplitFirstBlock - We need to either split MBB1 at MBB1I or MBB2 at
365 /// MBB2I and then insert an unconditional branch in the other block.  Determine
366 /// which is the best to split
367 static bool ShouldSplitFirstBlock(MachineBasicBlock *MBB1,
368                                   MachineBasicBlock::iterator MBB1I,
369                                   MachineBasicBlock *MBB2,
370                                   MachineBasicBlock::iterator MBB2I,
371                                   const TargetInstrInfo *TII,
372                                   MachineBasicBlock *PredBB) {
373   // If one block is the entry block, split the other one; we can't generate
374   // a branch to the entry block, as its label is not emitted.
375   MachineBasicBlock *Entry = MBB1->getParent()->begin();
376   if (MBB1 == Entry)
377     return false;
378   if (MBB2 == Entry)
379     return true;
380
381   // If one block falls through into the common successor, choose that
382   // one to split; it is one instruction less to do that.
383   if (PredBB) {
384     if (MBB1 == PredBB)
385       return true;
386     else if (MBB2 == PredBB)
387       return false;
388   }
389   // TODO: if we had some notion of which block was hotter, we could split
390   // the hot block, so it is the fall-through.  Since we don't have profile info
391   // make a decision based on which will hurt most to split.
392   unsigned MBB1Time = EstimateRuntime(MBB1->begin(), MBB1I, TII);
393   unsigned MBB2Time = EstimateRuntime(MBB2->begin(), MBB2I, TII);
394   
395   // If the MBB1 prefix takes "less time" to run than the MBB2 prefix, split the
396   // MBB1 block so it falls through.  This will penalize the MBB2 path, but will
397   // have a lower overall impact on the program execution.
398   return MBB1Time < MBB2Time;
399 }
400
401 // CurMBB needs to add an unconditional branch to SuccMBB (we removed these
402 // branches temporarily for tail merging).  In the case where CurMBB ends
403 // with a conditional branch to the next block, optimize by reversing the
404 // test and conditionally branching to SuccMBB instead.
405
406 static void FixTail(MachineBasicBlock* CurMBB, MachineBasicBlock *SuccBB,
407                     const TargetInstrInfo *TII) {
408   MachineFunction *MF = CurMBB->getParent();
409   MachineFunction::iterator I = next(MachineFunction::iterator(CurMBB));
410   MachineBasicBlock *TBB = 0, *FBB = 0;
411   std::vector<MachineOperand> Cond;
412   if (I != MF->end() &&
413       !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond)) {
414     MachineBasicBlock *NextBB = I;
415     if (TBB == NextBB && Cond.size() && !FBB) {
416       if (!TII->ReverseBranchCondition(Cond)) {
417         TII->RemoveBranch(*CurMBB);
418         TII->InsertBranch(*CurMBB, SuccBB, NULL, Cond);
419         return;
420       }
421     }
422   }
423   TII->InsertBranch(*CurMBB, SuccBB, NULL, std::vector<MachineOperand>());
424 }
425
426 static bool MergeCompare(const std::pair<unsigned,MachineBasicBlock*> &p,
427                          const std::pair<unsigned,MachineBasicBlock*> &q) {
428     if (p.first < q.first)
429       return true;
430      else if (p.first > q.first)
431       return false;
432     else if (p.second->getNumber() < q.second->getNumber())
433       return true;
434     else if (p.second->getNumber() > q.second->getNumber())
435       return false;
436     else {
437       // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
438       // an object with itself.
439 #ifndef _GLIBCXX_DEBUG
440       assert(0 && "Predecessor appears twice");
441 #endif
442       return(false);
443     }
444 }
445
446 // See if any of the blocks in MergePotentials (which all have a common single
447 // successor, or all have no successor) can be tail-merged.  If there is a
448 // successor, any blocks in MergePotentials that are not tail-merged and
449 // are not immediately before Succ must have an unconditional branch to
450 // Succ added (but the predecessor/successor lists need no adjustment).  
451 // The lone predecessor of Succ that falls through into Succ,
452 // if any, is given in PredBB.
453
454 bool BranchFolder::TryMergeBlocks(MachineBasicBlock *SuccBB,
455                                   MachineBasicBlock* PredBB) {
456   unsigned minCommonTailLength = (SuccBB ? 1 : 2);
457   MadeChange = false;
458   
459   // Sort by hash value so that blocks with identical end sequences sort
460   // together.
461   std::stable_sort(MergePotentials.begin(), MergePotentials.end(), MergeCompare);
462
463   // Walk through equivalence sets looking for actual exact matches.
464   while (MergePotentials.size() > 1) {
465     unsigned CurHash  = (MergePotentials.end()-1)->first;
466     unsigned PrevHash = (MergePotentials.end()-2)->first;
467     MachineBasicBlock *CurMBB = (MergePotentials.end()-1)->second;
468     
469     // If there is nothing that matches the hash of the current basic block,
470     // give up.
471     if (CurHash != PrevHash) {
472       if (SuccBB && CurMBB != PredBB)
473         FixTail(CurMBB, SuccBB, TII);
474       MergePotentials.pop_back();
475       continue;
476     }
477     
478     // Look through all the pairs of blocks that have the same hash as this
479     // one, and find the pair that has the largest number of instructions in
480     // common.
481      // Since instructions may get combined later (e.g. single stores into
482     // store multiple) this measure is not particularly accurate.
483    MachineBasicBlock::iterator BBI1, BBI2;
484     
485     unsigned FoundI = ~0U, FoundJ = ~0U;
486     unsigned maxCommonTailLength = 0U;
487     for (int i = MergePotentials.size()-1;
488          i != -1 && MergePotentials[i].first == CurHash; --i) {
489       for (int j = i-1; 
490            j != -1 && MergePotentials[j].first == CurHash; --j) {
491         MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
492         unsigned CommonTailLen = ComputeCommonTailLength(
493                                                 MergePotentials[i].second,
494                                                 MergePotentials[j].second,
495                                                 TrialBBI1, TrialBBI2);
496         if (CommonTailLen >= minCommonTailLength &&
497             CommonTailLen > maxCommonTailLength) {
498           FoundI = i;
499           FoundJ = j;
500           maxCommonTailLength = CommonTailLen;
501           BBI1 = TrialBBI1;
502           BBI2 = TrialBBI2;
503         }
504       }
505     }
506
507     // If we didn't find any pair that has at least minCommonTailLength 
508     // instructions in common, bail out.  All entries with this
509     // hash code can go away now.
510     if (FoundI == ~0U) {
511       for (int i = MergePotentials.size()-1;
512            i != -1 && MergePotentials[i].first == CurHash; --i) {
513         // Put the unconditional branch back, if we need one.
514         CurMBB = MergePotentials[i].second;
515         if (SuccBB && CurMBB != PredBB)
516           FixTail(CurMBB, SuccBB, TII);
517         MergePotentials.pop_back();
518       }
519       continue;
520     }
521
522     // Otherwise, move the block(s) to the right position(s).  So that
523     // BBI1/2 will be valid, the last must be I and the next-to-last J.
524     if (FoundI != MergePotentials.size()-1)
525       std::swap(MergePotentials[FoundI], *(MergePotentials.end()-1));
526     if (FoundJ != MergePotentials.size()-2)
527       std::swap(MergePotentials[FoundJ], *(MergePotentials.end()-2));
528
529     CurMBB = (MergePotentials.end()-1)->second;
530     MachineBasicBlock *MBB2 = (MergePotentials.end()-2)->second;
531
532     // If neither block is the entire common tail, split the tail of one block
533     // to make it redundant with the other tail.  Also, we cannot jump to the
534     // entry block, so if one block is the entry block, split the other one.
535     MachineBasicBlock *Entry = CurMBB->getParent()->begin();
536     if (CurMBB->begin() == BBI1 && CurMBB != Entry)
537       ;   // CurMBB is common tail
538     else if (MBB2->begin() == BBI2 && MBB2 != Entry)
539       ;   // MBB2 is common tail
540     else {
541       if (0) { // Enable this to disable partial tail merges.
542         MergePotentials.pop_back();
543         continue;
544       }
545       
546       // Decide whether we want to split CurMBB or MBB2.
547       if (ShouldSplitFirstBlock(CurMBB, BBI1, MBB2, BBI2, TII, PredBB)) {
548         CurMBB = SplitMBBAt(*CurMBB, BBI1);
549         BBI1 = CurMBB->begin();
550         MergePotentials.back().second = CurMBB;
551       } else {
552         MBB2 = SplitMBBAt(*MBB2, BBI2);
553         BBI2 = MBB2->begin();
554         (MergePotentials.end()-2)->second = MBB2;
555       }
556     }
557     
558     if (MBB2->begin() == BBI2 && MBB2 != Entry) {
559       // Hack the end off CurMBB, making it jump to MBBI@ instead.
560       ReplaceTailWithBranchTo(BBI1, MBB2);
561       // This modifies CurMBB, so remove it from the worklist.
562       MergePotentials.pop_back();
563     } else {
564       assert(CurMBB->begin() == BBI1 && CurMBB != Entry && 
565              "Didn't split block correctly?");
566       // Hack the end off MBB2, making it jump to CurMBB instead.
567       ReplaceTailWithBranchTo(BBI2, CurMBB);
568       // This modifies MBB2, so remove it from the worklist.
569       MergePotentials.erase(MergePotentials.end()-2);
570     }
571     MadeChange = true;
572   }
573   return MadeChange;
574 }
575
576 bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
577
578   if (!EnableTailMerge) return false;
579  
580   MadeChange = false;
581
582   // First find blocks with no successors.
583   MergePotentials.clear();
584   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
585     if (I->succ_empty())
586       MergePotentials.push_back(std::make_pair(HashEndOfMBB(I, 2U), I));
587   }
588   // See if we can do any tail merging on those.
589   if (MergePotentials.size() < TailMergeThreshold)
590     MadeChange |= TryMergeBlocks(NULL, NULL);
591
592   // Look at blocks (IBB) with multiple predecessors (PBB).
593   // We change each predecessor to a canonical form, by
594   // (1) temporarily removing any unconditional branch from the predecessor
595   // to IBB, and
596   // (2) alter conditional branches so they branch to the other block
597   // not IBB; this may require adding back an unconditional branch to IBB 
598   // later, where there wasn't one coming in.  E.g.
599   //   Bcc IBB
600   //   fallthrough to QBB
601   // here becomes
602   //   Bncc QBB
603   // with a conceptual B to IBB after that, which never actually exists.
604   // With those changes, we see whether the predecessors' tails match,
605   // and merge them if so.  We change things out of canonical form and
606   // back to the way they were later in the process.  (OptimizeBranches
607   // would undo some of this, but we can't use it, because we'd get into
608   // a compile-time infinite loop repeatedly doing and undoing the same
609   // transformations.)
610
611   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
612     if (!I->succ_empty() && I->pred_size() >= 2 && 
613          I->pred_size() < TailMergeThreshold) {
614       MachineBasicBlock *IBB = I;
615       MachineBasicBlock *PredBB = prior(I);
616       MergePotentials.clear();
617       for (MachineBasicBlock::pred_iterator P = I->pred_begin(), 
618                                             E2 = I->pred_end();
619            P != E2; ++P) {
620         MachineBasicBlock* PBB = *P;
621         // Skip blocks that loop to themselves, can't tail merge these.
622         if (PBB==IBB)
623           continue;
624         MachineBasicBlock *TBB = 0, *FBB = 0;
625         std::vector<MachineOperand> Cond;
626         if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond)) {
627           // Failing case:  IBB is the target of a cbr, and
628           // we cannot reverse the branch.
629           std::vector<MachineOperand> NewCond(Cond);
630           if (Cond.size() && TBB==IBB) {
631             if (TII->ReverseBranchCondition(NewCond))
632               continue;
633             // This is the QBB case described above
634             if (!FBB)
635               FBB = next(MachineFunction::iterator(PBB));
636           }
637           // Failing case:  the only way IBB can be reached from PBB is via
638           // exception handling.  Happens for landing pads.  Would be nice
639           // to have a bit in the edge so we didn't have to do all this.
640           if (IBB->isLandingPad()) {
641             MachineFunction::iterator IP = PBB;  IP++;
642             MachineBasicBlock* PredNextBB = NULL;
643             if (IP!=MF.end())
644               PredNextBB = IP;
645             if (TBB==NULL) {
646               if (IBB!=PredNextBB)      // fallthrough
647                 continue;
648             } else if (FBB) {
649               if (TBB!=IBB && FBB!=IBB)   // cbr then ubr
650                 continue;
651             } else if (Cond.size() == 0) {
652               if (TBB!=IBB)               // ubr
653                 continue;
654             } else {
655               if (TBB!=IBB && IBB!=PredNextBB)  // cbr
656                 continue;
657             }
658           }
659           // Remove the unconditional branch at the end, if any.
660           if (TBB && (Cond.size()==0 || FBB)) {
661             TII->RemoveBranch(*PBB);
662             if (Cond.size())
663               // reinsert conditional branch only, for now
664               TII->InsertBranch(*PBB, (TBB==IBB) ? FBB : TBB, 0, NewCond);
665           }
666           MergePotentials.push_back(std::make_pair(HashEndOfMBB(PBB, 1U), *P));
667         }
668       }
669     if (MergePotentials.size() >= 2)
670       MadeChange |= TryMergeBlocks(I, PredBB);
671     // Reinsert an unconditional branch if needed.
672     // The 1 below can be either an original single predecessor, or a result
673     // of removing blocks in TryMergeBlocks.
674     PredBB = prior(I);      // this may have been changed in TryMergeBlocks
675     if (MergePotentials.size()==1 && 
676         (MergePotentials.begin())->second != PredBB)
677       FixTail((MergePotentials.begin())->second, I, TII);
678     }
679   }
680   return MadeChange;
681 }
682
683 //===----------------------------------------------------------------------===//
684 //  Branch Optimization
685 //===----------------------------------------------------------------------===//
686
687 bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
688   MadeChange = false;
689   
690   // Make sure blocks are numbered in order
691   MF.RenumberBlocks();
692
693   for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
694     MachineBasicBlock *MBB = I++;
695     OptimizeBlock(MBB);
696     
697     // If it is dead, remove it.
698     if (MBB->pred_empty()) {
699       RemoveDeadBlock(MBB);
700       MadeChange = true;
701       ++NumDeadBlocks;
702     }
703   }
704   return MadeChange;
705 }
706
707
708 /// CanFallThrough - Return true if the specified block (with the specified
709 /// branch condition) can implicitly transfer control to the block after it by
710 /// falling off the end of it.  This should return false if it can reach the
711 /// block after it, but it uses an explicit branch to do so (e.g. a table jump).
712 ///
713 /// True is a conservative answer.
714 ///
715 bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB,
716                                   bool BranchUnAnalyzable,
717                                   MachineBasicBlock *TBB, MachineBasicBlock *FBB,
718                                   const std::vector<MachineOperand> &Cond) {
719   MachineFunction::iterator Fallthrough = CurBB;
720   ++Fallthrough;
721   // If FallthroughBlock is off the end of the function, it can't fall through.
722   if (Fallthrough == CurBB->getParent()->end())
723     return false;
724   
725   // If FallthroughBlock isn't a successor of CurBB, no fallthrough is possible.
726   if (!CurBB->isSuccessor(Fallthrough))
727     return false;
728   
729   // If we couldn't analyze the branch, assume it could fall through.
730   if (BranchUnAnalyzable) return true;
731   
732   // If there is no branch, control always falls through.
733   if (TBB == 0) return true;
734
735   // If there is some explicit branch to the fallthrough block, it can obviously
736   // reach, even though the branch should get folded to fall through implicitly.
737   if (MachineFunction::iterator(TBB) == Fallthrough ||
738       MachineFunction::iterator(FBB) == Fallthrough)
739     return true;
740   
741   // If it's an unconditional branch to some block not the fall through, it 
742   // doesn't fall through.
743   if (Cond.empty()) return false;
744   
745   // Otherwise, if it is conditional and has no explicit false block, it falls
746   // through.
747   return FBB == 0;
748 }
749
750 /// CanFallThrough - Return true if the specified can implicitly transfer
751 /// control to the block after it by falling off the end of it.  This should
752 /// return false if it can reach the block after it, but it uses an explicit
753 /// branch to do so (e.g. a table jump).
754 ///
755 /// True is a conservative answer.
756 ///
757 bool BranchFolder::CanFallThrough(MachineBasicBlock *CurBB) {
758   MachineBasicBlock *TBB = 0, *FBB = 0;
759   std::vector<MachineOperand> Cond;
760   bool CurUnAnalyzable = TII->AnalyzeBranch(*CurBB, TBB, FBB, Cond);
761   return CanFallThrough(CurBB, CurUnAnalyzable, TBB, FBB, Cond);
762 }
763
764 /// IsBetterFallthrough - Return true if it would be clearly better to
765 /// fall-through to MBB1 than to fall through into MBB2.  This has to return
766 /// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
767 /// result in infinite loops.
768 static bool IsBetterFallthrough(MachineBasicBlock *MBB1, 
769                                 MachineBasicBlock *MBB2,
770                                 const TargetInstrInfo &TII) {
771   // Right now, we use a simple heuristic.  If MBB2 ends with a call, and
772   // MBB1 doesn't, we prefer to fall through into MBB1.  This allows us to
773   // optimize branches that branch to either a return block or an assert block
774   // into a fallthrough to the return.
775   if (MBB1->empty() || MBB2->empty()) return false;
776  
777   // If there is a clear successor ordering we make sure that one block
778   // will fall through to the next
779   if (MBB1->isSuccessor(MBB2)) return true;
780   if (MBB2->isSuccessor(MBB1)) return false;
781
782   MachineInstr *MBB1I = --MBB1->end();
783   MachineInstr *MBB2I = --MBB2->end();
784   return TII.isCall(MBB2I->getOpcode()) && !TII.isCall(MBB1I->getOpcode());
785 }
786
787 /// OptimizeBlock - Analyze and optimize control flow related to the specified
788 /// block.  This is never called on the entry block.
789 void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
790   MachineFunction::iterator FallThrough = MBB;
791   ++FallThrough;
792   
793   // If this block is empty, make everyone use its fall-through, not the block
794   // explicitly.  Landing pads should not do this since the landing-pad table
795   // points to this block.
796   if (MBB->empty() && !MBB->isLandingPad()) {
797     // Dead block?  Leave for cleanup later.
798     if (MBB->pred_empty()) return;
799     
800     if (FallThrough == MBB->getParent()->end()) {
801       // TODO: Simplify preds to not branch here if possible!
802     } else {
803       // Rewrite all predecessors of the old block to go to the fallthrough
804       // instead.
805       while (!MBB->pred_empty()) {
806         MachineBasicBlock *Pred = *(MBB->pred_end()-1);
807         Pred->ReplaceUsesOfBlockWith(MBB, FallThrough);
808       }
809       
810       // If MBB was the target of a jump table, update jump tables to go to the
811       // fallthrough instead.
812       MBB->getParent()->getJumpTableInfo()->
813         ReplaceMBBInJumpTables(MBB, FallThrough);
814       MadeChange = true;
815     }
816     return;
817   }
818
819   // Check to see if we can simplify the terminator of the block before this
820   // one.
821   MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB));
822
823   MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
824   std::vector<MachineOperand> PriorCond;
825   bool PriorUnAnalyzable =
826     TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
827   if (!PriorUnAnalyzable) {
828     // If the CFG for the prior block has extra edges, remove them.
829     MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB,
830                                               !PriorCond.empty());
831     
832     // If the previous branch is conditional and both conditions go to the same
833     // destination, remove the branch, replacing it with an unconditional one or
834     // a fall-through.
835     if (PriorTBB && PriorTBB == PriorFBB) {
836       TII->RemoveBranch(PrevBB);
837       PriorCond.clear(); 
838       if (PriorTBB != MBB)
839         TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
840       MadeChange = true;
841       ++NumBranchOpts;
842       return OptimizeBlock(MBB);
843     }
844     
845     // If the previous branch *only* branches to *this* block (conditional or
846     // not) remove the branch.
847     if (PriorTBB == MBB && PriorFBB == 0) {
848       TII->RemoveBranch(PrevBB);
849       MadeChange = true;
850       ++NumBranchOpts;
851       return OptimizeBlock(MBB);
852     }
853     
854     // If the prior block branches somewhere else on the condition and here if
855     // the condition is false, remove the uncond second branch.
856     if (PriorFBB == MBB) {
857       TII->RemoveBranch(PrevBB);
858       TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
859       MadeChange = true;
860       ++NumBranchOpts;
861       return OptimizeBlock(MBB);
862     }
863     
864     // If the prior block branches here on true and somewhere else on false, and
865     // if the branch condition is reversible, reverse the branch to create a
866     // fall-through.
867     if (PriorTBB == MBB) {
868       std::vector<MachineOperand> NewPriorCond(PriorCond);
869       if (!TII->ReverseBranchCondition(NewPriorCond)) {
870         TII->RemoveBranch(PrevBB);
871         TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond);
872         MadeChange = true;
873         ++NumBranchOpts;
874         return OptimizeBlock(MBB);
875       }
876     }
877     
878     // If this block doesn't fall through (e.g. it ends with an uncond branch or
879     // has no successors) and if the pred falls through into this block, and if
880     // it would otherwise fall through into the block after this, move this
881     // block to the end of the function.
882     //
883     // We consider it more likely that execution will stay in the function (e.g.
884     // due to loops) than it is to exit it.  This asserts in loops etc, moving
885     // the assert condition out of the loop body.
886     if (!PriorCond.empty() && PriorFBB == 0 &&
887         MachineFunction::iterator(PriorTBB) == FallThrough &&
888         !CanFallThrough(MBB)) {
889       bool DoTransform = true;
890       
891       // We have to be careful that the succs of PredBB aren't both no-successor
892       // blocks.  If neither have successors and if PredBB is the second from
893       // last block in the function, we'd just keep swapping the two blocks for
894       // last.  Only do the swap if one is clearly better to fall through than
895       // the other.
896       if (FallThrough == --MBB->getParent()->end() &&
897           !IsBetterFallthrough(PriorTBB, MBB, *TII))
898         DoTransform = false;
899
900       // We don't want to do this transformation if we have control flow like:
901       //   br cond BB2
902       // BB1:
903       //   ..
904       //   jmp BBX
905       // BB2:
906       //   ..
907       //   ret
908       //
909       // In this case, we could actually be moving the return block *into* a
910       // loop!
911       if (DoTransform && !MBB->succ_empty() &&
912           (!CanFallThrough(PriorTBB) || PriorTBB->empty()))
913         DoTransform = false;
914       
915       
916       if (DoTransform) {
917         // Reverse the branch so we will fall through on the previous true cond.
918         std::vector<MachineOperand> NewPriorCond(PriorCond);
919         if (!TII->ReverseBranchCondition(NewPriorCond)) {
920           DOUT << "\nMoving MBB: " << *MBB;
921           DOUT << "To make fallthrough to: " << *PriorTBB << "\n";
922           
923           TII->RemoveBranch(PrevBB);
924           TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond);
925
926           // Move this block to the end of the function.
927           MBB->moveAfter(--MBB->getParent()->end());
928           MadeChange = true;
929           ++NumBranchOpts;
930           return;
931         }
932       }
933     }
934   }
935   
936   // Analyze the branch in the current block.
937   MachineBasicBlock *CurTBB = 0, *CurFBB = 0;
938   std::vector<MachineOperand> CurCond;
939   bool CurUnAnalyzable = TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond);
940   if (!CurUnAnalyzable) {
941     // If the CFG for the prior block has extra edges, remove them.
942     MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty());
943
944     // If this is a two-way branch, and the FBB branches to this block, reverse 
945     // the condition so the single-basic-block loop is faster.  Instead of:
946     //    Loop: xxx; jcc Out; jmp Loop
947     // we want:
948     //    Loop: xxx; jncc Loop; jmp Out
949     if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
950       std::vector<MachineOperand> NewCond(CurCond);
951       if (!TII->ReverseBranchCondition(NewCond)) {
952         TII->RemoveBranch(*MBB);
953         TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond);
954         MadeChange = true;
955         ++NumBranchOpts;
956         return OptimizeBlock(MBB);
957       }
958     }
959     
960     
961     // If this branch is the only thing in its block, see if we can forward
962     // other blocks across it.
963     if (CurTBB && CurCond.empty() && CurFBB == 0 && 
964         TII->isBranch(MBB->begin()->getOpcode()) && CurTBB != MBB) {
965       // This block may contain just an unconditional branch.  Because there can
966       // be 'non-branch terminators' in the block, try removing the branch and
967       // then seeing if the block is empty.
968       TII->RemoveBranch(*MBB);
969
970       // If this block is just an unconditional branch to CurTBB, we can
971       // usually completely eliminate the block.  The only case we cannot
972       // completely eliminate the block is when the block before this one
973       // falls through into MBB and we can't understand the prior block's branch
974       // condition.
975       if (MBB->empty()) {
976         bool PredHasNoFallThrough = TII->BlockHasNoFallThrough(PrevBB);
977         if (PredHasNoFallThrough || !PriorUnAnalyzable ||
978             !PrevBB.isSuccessor(MBB)) {
979           // If the prior block falls through into us, turn it into an
980           // explicit branch to us to make updates simpler.
981           if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) && 
982               PriorTBB != MBB && PriorFBB != MBB) {
983             if (PriorTBB == 0) {
984               assert(PriorCond.empty() && PriorFBB == 0 &&
985                      "Bad branch analysis");
986               PriorTBB = MBB;
987             } else {
988               assert(PriorFBB == 0 && "Machine CFG out of date!");
989               PriorFBB = MBB;
990             }
991             TII->RemoveBranch(PrevBB);
992             TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
993           }
994
995           // Iterate through all the predecessors, revectoring each in-turn.
996           size_t PI = 0;
997           bool DidChange = false;
998           bool HasBranchToSelf = false;
999           while(PI != MBB->pred_size()) {
1000             MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
1001             if (PMBB == MBB) {
1002               // If this block has an uncond branch to itself, leave it.
1003               ++PI;
1004               HasBranchToSelf = true;
1005             } else {
1006               DidChange = true;
1007               PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
1008             }
1009           }
1010
1011           // Change any jumptables to go to the new MBB.
1012           MBB->getParent()->getJumpTableInfo()->
1013             ReplaceMBBInJumpTables(MBB, CurTBB);
1014           if (DidChange) {
1015             ++NumBranchOpts;
1016             MadeChange = true;
1017             if (!HasBranchToSelf) return;
1018           }
1019         }
1020       }
1021       
1022       // Add the branch back if the block is more than just an uncond branch.
1023       TII->InsertBranch(*MBB, CurTBB, 0, CurCond);
1024     }
1025   }
1026
1027   // If the prior block doesn't fall through into this block, and if this
1028   // block doesn't fall through into some other block, see if we can find a
1029   // place to move this block where a fall-through will happen.
1030   if (!CanFallThrough(&PrevBB, PriorUnAnalyzable,
1031                       PriorTBB, PriorFBB, PriorCond)) {
1032     // Now we know that there was no fall-through into this block, check to
1033     // see if it has a fall-through into its successor.
1034     bool CurFallsThru = CanFallThrough(MBB, CurUnAnalyzable, CurTBB, CurFBB, 
1035                                        CurCond);
1036
1037     if (!MBB->isLandingPad()) {
1038       // Check all the predecessors of this block.  If one of them has no fall
1039       // throughs, move this block right after it.
1040       for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
1041            E = MBB->pred_end(); PI != E; ++PI) {
1042         // Analyze the branch at the end of the pred.
1043         MachineBasicBlock *PredBB = *PI;
1044         MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
1045         if (PredBB != MBB && !CanFallThrough(PredBB)
1046             && (!CurFallsThru || !CurTBB || !CurFBB)
1047             && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
1048           // If the current block doesn't fall through, just move it.
1049           // If the current block can fall through and does not end with a
1050           // conditional branch, we need to append an unconditional jump to 
1051           // the (current) next block.  To avoid a possible compile-time
1052           // infinite loop, move blocks only backward in this case.
1053           // Also, if there are already 2 branches here, we cannot add a third;
1054           // this means we have the case
1055           // Bcc next
1056           // B elsewhere
1057           // next:
1058           if (CurFallsThru) {
1059             MachineBasicBlock *NextBB = next(MachineFunction::iterator(MBB));
1060             CurCond.clear();
1061             TII->InsertBranch(*MBB, NextBB, 0, CurCond);
1062           }
1063           MBB->moveAfter(PredBB);
1064           MadeChange = true;
1065           return OptimizeBlock(MBB);
1066         }
1067       }
1068     }
1069         
1070     if (!CurFallsThru) {
1071       // Check all successors to see if we can move this block before it.
1072       for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
1073            E = MBB->succ_end(); SI != E; ++SI) {
1074         // Analyze the branch at the end of the block before the succ.
1075         MachineBasicBlock *SuccBB = *SI;
1076         MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev;
1077         std::vector<MachineOperand> SuccPrevCond;
1078         
1079         // If this block doesn't already fall-through to that successor, and if
1080         // the succ doesn't already have a block that can fall through into it,
1081         // and if the successor isn't an EH destination, we can arrange for the
1082         // fallthrough to happen.
1083         if (SuccBB != MBB && !CanFallThrough(SuccPrev) &&
1084             !SuccBB->isLandingPad()) {
1085           MBB->moveBefore(SuccBB);
1086           MadeChange = true;
1087           return OptimizeBlock(MBB);
1088         }
1089       }
1090       
1091       // Okay, there is no really great place to put this block.  If, however,
1092       // the block before this one would be a fall-through if this block were
1093       // removed, move this block to the end of the function.
1094       if (FallThrough != MBB->getParent()->end() &&
1095           PrevBB.isSuccessor(FallThrough)) {
1096         MBB->moveAfter(--MBB->getParent()->end());
1097         MadeChange = true;
1098         return;
1099       }
1100     }
1101   }
1102 }