← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/BranchFolding.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/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 "BranchFolding.h"
 
21
#include "llvm/Function.h"
 
22
#include "llvm/CodeGen/Passes.h"
 
23
#include "llvm/CodeGen/MachineModuleInfo.h"
 
24
#include "llvm/CodeGen/MachineFunctionPass.h"
 
25
#include "llvm/CodeGen/MachineJumpTableInfo.h"
 
26
#include "llvm/CodeGen/RegisterScavenging.h"
 
27
#include "llvm/Target/TargetInstrInfo.h"
 
28
#include "llvm/Target/TargetMachine.h"
 
29
#include "llvm/Target/TargetRegisterInfo.h"
 
30
#include "llvm/Support/CommandLine.h"
 
31
#include "llvm/Support/Debug.h"
 
32
#include "llvm/Support/ErrorHandling.h"
 
33
#include "llvm/Support/raw_ostream.h"
 
34
#include "llvm/ADT/SmallSet.h"
 
35
#include "llvm/ADT/SetVector.h"
 
36
#include "llvm/ADT/Statistic.h"
 
37
#include "llvm/ADT/STLExtras.h"
 
38
#include <algorithm>
 
39
using namespace llvm;
 
40
 
 
41
STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
 
42
STATISTIC(NumBranchOpts, "Number of branches optimized");
 
43
STATISTIC(NumTailMerge , "Number of block tails merged");
 
44
 
 
45
static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge",
 
46
                              cl::init(cl::BOU_UNSET), cl::Hidden);
 
47
 
 
48
// Throttle for huge numbers of predecessors (compile speed problems)
 
49
static cl::opt<unsigned>
 
50
TailMergeThreshold("tail-merge-threshold",
 
51
          cl::desc("Max number of predecessors to consider tail merging"),
 
52
          cl::init(150), cl::Hidden);
 
53
 
 
54
// Heuristic for tail merging (and, inversely, tail duplication).
 
55
// TODO: This should be replaced with a target query.
 
56
static cl::opt<unsigned>
 
57
TailMergeSize("tail-merge-size",
 
58
          cl::desc("Min number of instructions to consider tail merging"),
 
59
                              cl::init(3), cl::Hidden);
 
60
 
 
61
namespace {
 
62
  /// BranchFolderPass - Wrap branch folder in a machine function pass.
 
63
  class BranchFolderPass : public MachineFunctionPass,
 
64
                           public BranchFolder {
 
65
  public:
 
66
    static char ID;
 
67
    explicit BranchFolderPass(bool defaultEnableTailMerge)
 
68
      : MachineFunctionPass(&ID), BranchFolder(defaultEnableTailMerge) {}
 
69
 
 
70
    virtual bool runOnMachineFunction(MachineFunction &MF);
 
71
    virtual const char *getPassName() const { return "Control Flow Optimizer"; }
 
72
  };
 
73
}
 
74
 
 
75
char BranchFolderPass::ID = 0;
 
76
 
 
77
FunctionPass *llvm::createBranchFoldingPass(bool DefaultEnableTailMerge) {
 
78
  return new BranchFolderPass(DefaultEnableTailMerge);
 
79
}
 
80
 
 
81
bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) {
 
82
  return OptimizeFunction(MF,
 
83
                          MF.getTarget().getInstrInfo(),
 
84
                          MF.getTarget().getRegisterInfo(),
 
85
                          getAnalysisIfAvailable<MachineModuleInfo>());
 
86
}
 
87
 
 
88
 
 
89
BranchFolder::BranchFolder(bool defaultEnableTailMerge) {
 
90
  switch (FlagEnableTailMerge) {
 
91
  case cl::BOU_UNSET: EnableTailMerge = defaultEnableTailMerge; break;
 
92
  case cl::BOU_TRUE: EnableTailMerge = true; break;
 
93
  case cl::BOU_FALSE: EnableTailMerge = false; break;
 
94
  }
 
95
}
 
96
 
 
97
/// RemoveDeadBlock - Remove the specified dead machine basic block from the
 
98
/// function, updating the CFG.
 
99
void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
 
100
  assert(MBB->pred_empty() && "MBB must be dead!");
 
101
  DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
 
102
 
 
103
  MachineFunction *MF = MBB->getParent();
 
104
  // drop all successors.
 
105
  while (!MBB->succ_empty())
 
106
    MBB->removeSuccessor(MBB->succ_end()-1);
 
107
 
 
108
  // If there are any labels in the basic block, unregister them from
 
109
  // MachineModuleInfo.
 
110
  if (MMI && !MBB->empty()) {
 
111
    for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 
112
         I != E; ++I) {
 
113
      if (I->isLabel())
 
114
        // The label ID # is always operand #0, an immediate.
 
115
        MMI->InvalidateLabel(I->getOperand(0).getImm());
 
116
    }
 
117
  }
 
118
 
 
119
  // Remove the block.
 
120
  MF->erase(MBB);
 
121
}
 
122
 
 
123
/// OptimizeImpDefsBlock - If a basic block is just a bunch of implicit_def
 
124
/// followed by terminators, and if the implicitly defined registers are not
 
125
/// used by the terminators, remove those implicit_def's. e.g.
 
126
/// BB1:
 
127
///   r0 = implicit_def
 
128
///   r1 = implicit_def
 
129
///   br
 
130
/// This block can be optimized away later if the implicit instructions are
 
131
/// removed.
 
132
bool BranchFolder::OptimizeImpDefsBlock(MachineBasicBlock *MBB) {
 
133
  SmallSet<unsigned, 4> ImpDefRegs;
 
134
  MachineBasicBlock::iterator I = MBB->begin();
 
135
  while (I != MBB->end()) {
 
136
    if (!I->isImplicitDef())
 
137
      break;
 
138
    unsigned Reg = I->getOperand(0).getReg();
 
139
    ImpDefRegs.insert(Reg);
 
140
    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 
141
         unsigned SubReg = *SubRegs; ++SubRegs)
 
142
      ImpDefRegs.insert(SubReg);
 
143
    ++I;
 
144
  }
 
145
  if (ImpDefRegs.empty())
 
146
    return false;
 
147
 
 
148
  MachineBasicBlock::iterator FirstTerm = I;
 
149
  while (I != MBB->end()) {
 
150
    if (!TII->isUnpredicatedTerminator(I))
 
151
      return false;
 
152
    // See if it uses any of the implicitly defined registers.
 
153
    for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 
154
      MachineOperand &MO = I->getOperand(i);
 
155
      if (!MO.isReg() || !MO.isUse())
 
156
        continue;
 
157
      unsigned Reg = MO.getReg();
 
158
      if (ImpDefRegs.count(Reg))
 
159
        return false;
 
160
    }
 
161
    ++I;
 
162
  }
 
163
 
 
164
  I = MBB->begin();
 
165
  while (I != FirstTerm) {
 
166
    MachineInstr *ImpDefMI = &*I;
 
167
    ++I;
 
168
    MBB->erase(ImpDefMI);
 
169
  }
 
170
 
 
171
  return true;
 
172
}
 
173
 
 
174
/// OptimizeFunction - Perhaps branch folding, tail merging and other
 
175
/// CFG optimizations on the given function.
 
176
bool BranchFolder::OptimizeFunction(MachineFunction &MF,
 
177
                                    const TargetInstrInfo *tii,
 
178
                                    const TargetRegisterInfo *tri,
 
179
                                    MachineModuleInfo *mmi) {
 
180
  if (!tii) return false;
 
181
 
 
182
  TII = tii;
 
183
  TRI = tri;
 
184
  MMI = mmi;
 
185
 
 
186
  RS = TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : NULL;
 
187
 
 
188
  // Fix CFG.  The later algorithms expect it to be right.
 
189
  bool MadeChange = false;
 
190
  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) {
 
191
    MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0;
 
192
    SmallVector<MachineOperand, 4> Cond;
 
193
    if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true))
 
194
      MadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
 
195
    MadeChange |= OptimizeImpDefsBlock(MBB);
 
196
  }
 
197
 
 
198
  bool MadeChangeThisIteration = true;
 
199
  while (MadeChangeThisIteration) {
 
200
    MadeChangeThisIteration = false;
 
201
    MadeChangeThisIteration |= TailMergeBlocks(MF);
 
202
    MadeChangeThisIteration |= OptimizeBranches(MF);
 
203
    MadeChange |= MadeChangeThisIteration;
 
204
  }
 
205
 
 
206
  // See if any jump tables have become mergable or dead as the code generator
 
207
  // did its thing.
 
208
  MachineJumpTableInfo *JTI = MF.getJumpTableInfo();
 
209
  if (JTI == 0) {
 
210
    delete RS;
 
211
    return MadeChange;
 
212
  }
 
213
  
 
214
  const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables();
 
215
  // Figure out how these jump tables should be merged.
 
216
  std::vector<unsigned> JTMapping;
 
217
  JTMapping.reserve(JTs.size());
 
218
 
 
219
  // We always keep the 0th jump table.
 
220
  JTMapping.push_back(0);
 
221
 
 
222
  // Scan the jump tables, seeing if there are any duplicates.  Note that this
 
223
  // is N^2, which should be fixed someday.
 
224
  for (unsigned i = 1, e = JTs.size(); i != e; ++i) {
 
225
    if (JTs[i].MBBs.empty())
 
226
      JTMapping.push_back(i);
 
227
    else
 
228
      JTMapping.push_back(JTI->getJumpTableIndex(JTs[i].MBBs));
 
229
  }
 
230
 
 
231
  // If a jump table was merge with another one, walk the function rewriting
 
232
  // references to jump tables to reference the new JT ID's.  Keep track of
 
233
  // whether we see a jump table idx, if not, we can delete the JT.
 
234
  BitVector JTIsLive(JTs.size());
 
235
  for (MachineFunction::iterator BB = MF.begin(), E = MF.end();
 
236
       BB != E; ++BB) {
 
237
    for (MachineBasicBlock::iterator I = BB->begin(), E = BB->end();
 
238
         I != E; ++I)
 
239
      for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op) {
 
240
        MachineOperand &Op = I->getOperand(op);
 
241
        if (!Op.isJTI()) continue;
 
242
        unsigned NewIdx = JTMapping[Op.getIndex()];
 
243
        Op.setIndex(NewIdx);
 
244
 
 
245
        // Remember that this JT is live.
 
246
        JTIsLive.set(NewIdx);
 
247
      }
 
248
  }
 
249
 
 
250
  // Finally, remove dead jump tables.  This happens either because the
 
251
  // indirect jump was unreachable (and thus deleted) or because the jump
 
252
  // table was merged with some other one.
 
253
  for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
 
254
    if (!JTIsLive.test(i)) {
 
255
      JTI->RemoveJumpTable(i);
 
256
      MadeChange = true;
 
257
    }
 
258
 
 
259
  delete RS;
 
260
  return MadeChange;
 
261
}
 
262
 
 
263
//===----------------------------------------------------------------------===//
 
264
//  Tail Merging of Blocks
 
265
//===----------------------------------------------------------------------===//
 
266
 
 
267
/// HashMachineInstr - Compute a hash value for MI and its operands.
 
268
static unsigned HashMachineInstr(const MachineInstr *MI) {
 
269
  unsigned Hash = MI->getOpcode();
 
270
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 
271
    const MachineOperand &Op = MI->getOperand(i);
 
272
 
 
273
    // Merge in bits from the operand if easy.
 
274
    unsigned OperandHash = 0;
 
275
    switch (Op.getType()) {
 
276
    case MachineOperand::MO_Register:          OperandHash = Op.getReg(); break;
 
277
    case MachineOperand::MO_Immediate:         OperandHash = Op.getImm(); break;
 
278
    case MachineOperand::MO_MachineBasicBlock:
 
279
      OperandHash = Op.getMBB()->getNumber();
 
280
      break;
 
281
    case MachineOperand::MO_FrameIndex:
 
282
    case MachineOperand::MO_ConstantPoolIndex:
 
283
    case MachineOperand::MO_JumpTableIndex:
 
284
      OperandHash = Op.getIndex();
 
285
      break;
 
286
    case MachineOperand::MO_GlobalAddress:
 
287
    case MachineOperand::MO_ExternalSymbol:
 
288
      // Global address / external symbol are too hard, don't bother, but do
 
289
      // pull in the offset.
 
290
      OperandHash = Op.getOffset();
 
291
      break;
 
292
    default: break;
 
293
    }
 
294
 
 
295
    Hash += ((OperandHash << 3) | Op.getType()) << (i&31);
 
296
  }
 
297
  return Hash;
 
298
}
 
299
 
 
300
/// HashEndOfMBB - Hash the last few instructions in the MBB.  For blocks
 
301
/// with no successors, we hash two instructions, because cross-jumping
 
302
/// only saves code when at least two instructions are removed (since a
 
303
/// branch must be inserted).  For blocks with a successor, one of the
 
304
/// two blocks to be tail-merged will end with a branch already, so
 
305
/// it gains to cross-jump even for one instruction.
 
306
static unsigned HashEndOfMBB(const MachineBasicBlock *MBB,
 
307
                             unsigned minCommonTailLength) {
 
308
  MachineBasicBlock::const_iterator I = MBB->end();
 
309
  if (I == MBB->begin())
 
310
    return 0;   // Empty MBB.
 
311
 
 
312
  --I;
 
313
  unsigned Hash = HashMachineInstr(I);
 
314
 
 
315
  if (I == MBB->begin() || minCommonTailLength == 1)
 
316
    return Hash;   // Single instr MBB.
 
317
 
 
318
  --I;
 
319
  // Hash in the second-to-last instruction.
 
320
  Hash ^= HashMachineInstr(I) << 2;
 
321
  return Hash;
 
322
}
 
323
 
 
324
/// ComputeCommonTailLength - Given two machine basic blocks, compute the number
 
325
/// of instructions they actually have in common together at their end.  Return
 
326
/// iterators for the first shared instruction in each block.
 
327
static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
 
328
                                        MachineBasicBlock *MBB2,
 
329
                                        MachineBasicBlock::iterator &I1,
 
330
                                        MachineBasicBlock::iterator &I2) {
 
331
  I1 = MBB1->end();
 
332
  I2 = MBB2->end();
 
333
 
 
334
  unsigned TailLen = 0;
 
335
  while (I1 != MBB1->begin() && I2 != MBB2->begin()) {
 
336
    --I1; --I2;
 
337
    // Don't merge debugging pseudos.
 
338
    if (I1->isDebugValue() || I2->isDebugValue() ||
 
339
        !I1->isIdenticalTo(I2) ||
 
340
        // FIXME: This check is dubious. It's used to get around a problem where
 
341
        // people incorrectly expect inline asm directives to remain in the same
 
342
        // relative order. This is untenable because normal compiler
 
343
        // optimizations (like this one) may reorder and/or merge these
 
344
        // directives.
 
345
        I1->isInlineAsm()) {
 
346
      ++I1; ++I2;
 
347
      break;
 
348
    }
 
349
    ++TailLen;
 
350
  }
 
351
  return TailLen;
 
352
}
 
353
 
 
354
/// ReplaceTailWithBranchTo - Delete the instruction OldInst and everything
 
355
/// after it, replacing it with an unconditional branch to NewDest.  This
 
356
/// returns true if OldInst's block is modified, false if NewDest is modified.
 
357
void BranchFolder::ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
 
358
                                           MachineBasicBlock *NewDest) {
 
359
  MachineBasicBlock *OldBB = OldInst->getParent();
 
360
 
 
361
  // Remove all the old successors of OldBB from the CFG.
 
362
  while (!OldBB->succ_empty())
 
363
    OldBB->removeSuccessor(OldBB->succ_begin());
 
364
 
 
365
  // Remove all the dead instructions from the end of OldBB.
 
366
  OldBB->erase(OldInst, OldBB->end());
 
367
 
 
368
  // If OldBB isn't immediately before OldBB, insert a branch to it.
 
369
  if (++MachineFunction::iterator(OldBB) != MachineFunction::iterator(NewDest))
 
370
    TII->InsertBranch(*OldBB, NewDest, 0, SmallVector<MachineOperand, 0>());
 
371
  OldBB->addSuccessor(NewDest);
 
372
  ++NumTailMerge;
 
373
}
 
374
 
 
375
/// SplitMBBAt - Given a machine basic block and an iterator into it, split the
 
376
/// MBB so that the part before the iterator falls into the part starting at the
 
377
/// iterator.  This returns the new MBB.
 
378
MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
 
379
                                            MachineBasicBlock::iterator BBI1) {
 
380
  MachineFunction &MF = *CurMBB.getParent();
 
381
 
 
382
  // Create the fall-through block.
 
383
  MachineFunction::iterator MBBI = &CurMBB;
 
384
  MachineBasicBlock *NewMBB =MF.CreateMachineBasicBlock(CurMBB.getBasicBlock());
 
385
  CurMBB.getParent()->insert(++MBBI, NewMBB);
 
386
 
 
387
  // Move all the successors of this block to the specified block.
 
388
  NewMBB->transferSuccessors(&CurMBB);
 
389
 
 
390
  // Add an edge from CurMBB to NewMBB for the fall-through.
 
391
  CurMBB.addSuccessor(NewMBB);
 
392
 
 
393
  // Splice the code over.
 
394
  NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());
 
395
 
 
396
  // For targets that use the register scavenger, we must maintain LiveIns.
 
397
  if (RS) {
 
398
    RS->enterBasicBlock(&CurMBB);
 
399
    if (!CurMBB.empty())
 
400
      RS->forward(prior(CurMBB.end()));
 
401
    BitVector RegsLiveAtExit(TRI->getNumRegs());
 
402
    RS->getRegsUsed(RegsLiveAtExit, false);
 
403
    for (unsigned int i = 0, e = TRI->getNumRegs(); i != e; i++)
 
404
      if (RegsLiveAtExit[i])
 
405
        NewMBB->addLiveIn(i);
 
406
  }
 
407
 
 
408
  return NewMBB;
 
409
}
 
410
 
 
411
/// EstimateRuntime - Make a rough estimate for how long it will take to run
 
412
/// the specified code.
 
413
static unsigned EstimateRuntime(MachineBasicBlock::iterator I,
 
414
                                MachineBasicBlock::iterator E) {
 
415
  unsigned Time = 0;
 
416
  for (; I != E; ++I) {
 
417
    if (I->isDebugValue())
 
418
      continue;
 
419
    const TargetInstrDesc &TID = I->getDesc();
 
420
    if (TID.isCall())
 
421
      Time += 10;
 
422
    else if (TID.mayLoad() || TID.mayStore())
 
423
      Time += 2;
 
424
    else
 
425
      ++Time;
 
426
  }
 
427
  return Time;
 
428
}
 
429
 
 
430
// CurMBB needs to add an unconditional branch to SuccMBB (we removed these
 
431
// branches temporarily for tail merging).  In the case where CurMBB ends
 
432
// with a conditional branch to the next block, optimize by reversing the
 
433
// test and conditionally branching to SuccMBB instead.
 
434
static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB,
 
435
                    const TargetInstrInfo *TII) {
 
436
  MachineFunction *MF = CurMBB->getParent();
 
437
  MachineFunction::iterator I = llvm::next(MachineFunction::iterator(CurMBB));
 
438
  MachineBasicBlock *TBB = 0, *FBB = 0;
 
439
  SmallVector<MachineOperand, 4> Cond;
 
440
  if (I != MF->end() &&
 
441
      !TII->AnalyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {
 
442
    MachineBasicBlock *NextBB = I;
 
443
    if (TBB == NextBB && !Cond.empty() && !FBB) {
 
444
      if (!TII->ReverseBranchCondition(Cond)) {
 
445
        TII->RemoveBranch(*CurMBB);
 
446
        TII->InsertBranch(*CurMBB, SuccBB, NULL, Cond);
 
447
        return;
 
448
      }
 
449
    }
 
450
  }
 
451
  TII->InsertBranch(*CurMBB, SuccBB, NULL, SmallVector<MachineOperand, 0>());
 
452
}
 
453
 
 
454
bool
 
455
BranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const {
 
456
  if (getHash() < o.getHash())
 
457
    return true;
 
458
   else if (getHash() > o.getHash())
 
459
    return false;
 
460
  else if (getBlock()->getNumber() < o.getBlock()->getNumber())
 
461
    return true;
 
462
  else if (getBlock()->getNumber() > o.getBlock()->getNumber())
 
463
    return false;
 
464
  else {
 
465
    // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
 
466
    // an object with itself.
 
467
#ifndef _GLIBCXX_DEBUG
 
468
    llvm_unreachable("Predecessor appears twice");
 
469
#endif
 
470
    return false;
 
471
  }
 
472
}
 
473
 
 
474
/// CountTerminators - Count the number of terminators in the given
 
475
/// block and set I to the position of the first non-terminator, if there
 
476
/// is one, or MBB->end() otherwise.
 
477
static unsigned CountTerminators(MachineBasicBlock *MBB,
 
478
                                 MachineBasicBlock::iterator &I) {
 
479
  I = MBB->end();
 
480
  unsigned NumTerms = 0;
 
481
  for (;;) {
 
482
    if (I == MBB->begin()) {
 
483
      I = MBB->end();
 
484
      break;
 
485
    }
 
486
    --I;
 
487
    if (!I->getDesc().isTerminator()) break;
 
488
    ++NumTerms;
 
489
  }
 
490
  return NumTerms;
 
491
}
 
492
 
 
493
/// ProfitableToMerge - Check if two machine basic blocks have a common tail
 
494
/// and decide if it would be profitable to merge those tails.  Return the
 
495
/// length of the common tail and iterators to the first common instruction
 
496
/// in each block.
 
497
static bool ProfitableToMerge(MachineBasicBlock *MBB1,
 
498
                              MachineBasicBlock *MBB2,
 
499
                              unsigned minCommonTailLength,
 
500
                              unsigned &CommonTailLen,
 
501
                              MachineBasicBlock::iterator &I1,
 
502
                              MachineBasicBlock::iterator &I2,
 
503
                              MachineBasicBlock *SuccBB,
 
504
                              MachineBasicBlock *PredBB) {
 
505
  CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2);
 
506
  MachineFunction *MF = MBB1->getParent();
 
507
 
 
508
  if (CommonTailLen == 0)
 
509
    return false;
 
510
 
 
511
  // It's almost always profitable to merge any number of non-terminator
 
512
  // instructions with the block that falls through into the common successor.
 
513
  if (MBB1 == PredBB || MBB2 == PredBB) {
 
514
    MachineBasicBlock::iterator I;
 
515
    unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I);
 
516
    if (CommonTailLen > NumTerms)
 
517
      return true;
 
518
  }
 
519
 
 
520
  // If one of the blocks can be completely merged and happens to be in
 
521
  // a position where the other could fall through into it, merge any number
 
522
  // of instructions, because it can be done without a branch.
 
523
  // TODO: If the blocks are not adjacent, move one of them so that they are?
 
524
  if (MBB1->isLayoutSuccessor(MBB2) && I2 == MBB2->begin())
 
525
    return true;
 
526
  if (MBB2->isLayoutSuccessor(MBB1) && I1 == MBB1->begin())
 
527
    return true;
 
528
 
 
529
  // If both blocks have an unconditional branch temporarily stripped out,
 
530
  // count that as an additional common instruction for the following
 
531
  // heuristics.
 
532
  unsigned EffectiveTailLen = CommonTailLen;
 
533
  if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
 
534
      !MBB1->back().getDesc().isBarrier() &&
 
535
      !MBB2->back().getDesc().isBarrier())
 
536
    ++EffectiveTailLen;
 
537
 
 
538
  // Check if the common tail is long enough to be worthwhile.
 
539
  if (EffectiveTailLen >= minCommonTailLength)
 
540
    return true;
 
541
 
 
542
  // If we are optimizing for code size, 2 instructions in common is enough if
 
543
  // we don't have to split a block.  At worst we will be introducing 1 new
 
544
  // branch instruction, which is likely to be smaller than the 2
 
545
  // instructions that would be deleted in the merge.
 
546
  if (EffectiveTailLen >= 2 &&
 
547
      MF->getFunction()->hasFnAttr(Attribute::OptimizeForSize) &&
 
548
      (I1 == MBB1->begin() || I2 == MBB2->begin()))
 
549
    return true;
 
550
 
 
551
  return false;
 
552
}
 
553
 
 
554
/// ComputeSameTails - Look through all the blocks in MergePotentials that have
 
555
/// hash CurHash (guaranteed to match the last element).  Build the vector
 
556
/// SameTails of all those that have the (same) largest number of instructions
 
557
/// in common of any pair of these blocks.  SameTails entries contain an
 
558
/// iterator into MergePotentials (from which the MachineBasicBlock can be
 
559
/// found) and a MachineBasicBlock::iterator into that MBB indicating the
 
560
/// instruction where the matching code sequence begins.
 
561
/// Order of elements in SameTails is the reverse of the order in which
 
562
/// those blocks appear in MergePotentials (where they are not necessarily
 
563
/// consecutive).
 
564
unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
 
565
                                        unsigned minCommonTailLength,
 
566
                                        MachineBasicBlock *SuccBB,
 
567
                                        MachineBasicBlock *PredBB) {
 
568
  unsigned maxCommonTailLength = 0U;
 
569
  SameTails.clear();
 
570
  MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
 
571
  MPIterator HighestMPIter = prior(MergePotentials.end());
 
572
  for (MPIterator CurMPIter = prior(MergePotentials.end()),
 
573
                  B = MergePotentials.begin();
 
574
       CurMPIter != B && CurMPIter->getHash() == CurHash;
 
575
       --CurMPIter) {
 
576
    for (MPIterator I = prior(CurMPIter); I->getHash() == CurHash ; --I) {
 
577
      unsigned CommonTailLen;
 
578
      if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
 
579
                            minCommonTailLength,
 
580
                            CommonTailLen, TrialBBI1, TrialBBI2,
 
581
                            SuccBB, PredBB)) {
 
582
        if (CommonTailLen > maxCommonTailLength) {
 
583
          SameTails.clear();
 
584
          maxCommonTailLength = CommonTailLen;
 
585
          HighestMPIter = CurMPIter;
 
586
          SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));
 
587
        }
 
588
        if (HighestMPIter == CurMPIter &&
 
589
            CommonTailLen == maxCommonTailLength)
 
590
          SameTails.push_back(SameTailElt(I, TrialBBI2));
 
591
      }
 
592
      if (I == B)
 
593
        break;
 
594
    }
 
595
  }
 
596
  return maxCommonTailLength;
 
597
}
 
598
 
 
599
/// RemoveBlocksWithHash - Remove all blocks with hash CurHash from
 
600
/// MergePotentials, restoring branches at ends of blocks as appropriate.
 
601
void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,
 
602
                                        MachineBasicBlock *SuccBB,
 
603
                                        MachineBasicBlock *PredBB) {
 
604
  MPIterator CurMPIter, B;
 
605
  for (CurMPIter = prior(MergePotentials.end()), B = MergePotentials.begin();
 
606
       CurMPIter->getHash() == CurHash;
 
607
       --CurMPIter) {
 
608
    // Put the unconditional branch back, if we need one.
 
609
    MachineBasicBlock *CurMBB = CurMPIter->getBlock();
 
610
    if (SuccBB && CurMBB != PredBB)
 
611
      FixTail(CurMBB, SuccBB, TII);
 
612
    if (CurMPIter == B)
 
613
      break;
 
614
  }
 
615
  if (CurMPIter->getHash() != CurHash)
 
616
    CurMPIter++;
 
617
  MergePotentials.erase(CurMPIter, MergePotentials.end());
 
618
}
 
619
 
 
620
/// CreateCommonTailOnlyBlock - None of the blocks to be tail-merged consist
 
621
/// only of the common tail.  Create a block that does by splitting one.
 
622
unsigned BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
 
623
                                             unsigned maxCommonTailLength) {
 
624
  unsigned commonTailIndex = 0;
 
625
  unsigned TimeEstimate = ~0U;
 
626
  for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
 
627
    // Use PredBB if possible; that doesn't require a new branch.
 
628
    if (SameTails[i].getBlock() == PredBB) {
 
629
      commonTailIndex = i;
 
630
      break;
 
631
    }
 
632
    // Otherwise, make a (fairly bogus) choice based on estimate of
 
633
    // how long it will take the various blocks to execute.
 
634
    unsigned t = EstimateRuntime(SameTails[i].getBlock()->begin(),
 
635
                                 SameTails[i].getTailStartPos());
 
636
    if (t <= TimeEstimate) {
 
637
      TimeEstimate = t;
 
638
      commonTailIndex = i;
 
639
    }
 
640
  }
 
641
 
 
642
  MachineBasicBlock::iterator BBI =
 
643
    SameTails[commonTailIndex].getTailStartPos();
 
644
  MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
 
645
 
 
646
  DEBUG(dbgs() << "\nSplitting BB#" << MBB->getNumber() << ", size "
 
647
               << maxCommonTailLength);
 
648
 
 
649
  MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI);
 
650
  SameTails[commonTailIndex].setBlock(newMBB);
 
651
  SameTails[commonTailIndex].setTailStartPos(newMBB->begin());
 
652
 
 
653
  // If we split PredBB, newMBB is the new predecessor.
 
654
  if (PredBB == MBB)
 
655
    PredBB = newMBB;
 
656
 
 
657
  return commonTailIndex;
 
658
}
 
659
 
 
660
// See if any of the blocks in MergePotentials (which all have a common single
 
661
// successor, or all have no successor) can be tail-merged.  If there is a
 
662
// successor, any blocks in MergePotentials that are not tail-merged and
 
663
// are not immediately before Succ must have an unconditional branch to
 
664
// Succ added (but the predecessor/successor lists need no adjustment).
 
665
// The lone predecessor of Succ that falls through into Succ,
 
666
// if any, is given in PredBB.
 
667
 
 
668
bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
 
669
                                      MachineBasicBlock *PredBB) {
 
670
  bool MadeChange = false;
 
671
 
 
672
  // Except for the special cases below, tail-merge if there are at least
 
673
  // this many instructions in common.
 
674
  unsigned minCommonTailLength = TailMergeSize;
 
675
 
 
676
  DEBUG(dbgs() << "\nTryTailMergeBlocks: ";
 
677
        for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
 
678
          dbgs() << "BB#" << MergePotentials[i].getBlock()->getNumber()
 
679
                 << (i == e-1 ? "" : ", ");
 
680
        dbgs() << "\n";
 
681
        if (SuccBB) {
 
682
          dbgs() << "  with successor BB#" << SuccBB->getNumber() << '\n';
 
683
          if (PredBB)
 
684
            dbgs() << "  which has fall-through from BB#"
 
685
                   << PredBB->getNumber() << "\n";
 
686
        }
 
687
        dbgs() << "Looking for common tails of at least "
 
688
               << minCommonTailLength << " instruction"
 
689
               << (minCommonTailLength == 1 ? "" : "s") << '\n';
 
690
       );
 
691
 
 
692
  // Sort by hash value so that blocks with identical end sequences sort
 
693
  // together.
 
694
  std::stable_sort(MergePotentials.begin(), MergePotentials.end());
 
695
 
 
696
  // Walk through equivalence sets looking for actual exact matches.
 
697
  while (MergePotentials.size() > 1) {
 
698
    unsigned CurHash = MergePotentials.back().getHash();
 
699
 
 
700
    // Build SameTails, identifying the set of blocks with this hash code
 
701
    // and with the maximum number of instructions in common.
 
702
    unsigned maxCommonTailLength = ComputeSameTails(CurHash,
 
703
                                                    minCommonTailLength,
 
704
                                                    SuccBB, PredBB);
 
705
 
 
706
    // If we didn't find any pair that has at least minCommonTailLength
 
707
    // instructions in common, remove all blocks with this hash code and retry.
 
708
    if (SameTails.empty()) {
 
709
      RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
 
710
      continue;
 
711
    }
 
712
 
 
713
    // If one of the blocks is the entire common tail (and not the entry
 
714
    // block, which we can't jump to), we can treat all blocks with this same
 
715
    // tail at once.  Use PredBB if that is one of the possibilities, as that
 
716
    // will not introduce any extra branches.
 
717
    MachineBasicBlock *EntryBB = MergePotentials.begin()->getBlock()->
 
718
                                 getParent()->begin();
 
719
    unsigned commonTailIndex = SameTails.size();
 
720
    // If there are two blocks, check to see if one can be made to fall through
 
721
    // into the other.
 
722
    if (SameTails.size() == 2 &&
 
723
        SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
 
724
        SameTails[1].tailIsWholeBlock())
 
725
      commonTailIndex = 1;
 
726
    else if (SameTails.size() == 2 &&
 
727
             SameTails[1].getBlock()->isLayoutSuccessor(
 
728
                                                     SameTails[0].getBlock()) &&
 
729
             SameTails[0].tailIsWholeBlock())
 
730
      commonTailIndex = 0;
 
731
    else {
 
732
      // Otherwise just pick one, favoring the fall-through predecessor if
 
733
      // there is one.
 
734
      for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
 
735
        MachineBasicBlock *MBB = SameTails[i].getBlock();
 
736
        if (MBB == EntryBB && SameTails[i].tailIsWholeBlock())
 
737
          continue;
 
738
        if (MBB == PredBB) {
 
739
          commonTailIndex = i;
 
740
          break;
 
741
        }
 
742
        if (SameTails[i].tailIsWholeBlock())
 
743
          commonTailIndex = i;
 
744
      }
 
745
    }
 
746
 
 
747
    if (commonTailIndex == SameTails.size() ||
 
748
        (SameTails[commonTailIndex].getBlock() == PredBB &&
 
749
         !SameTails[commonTailIndex].tailIsWholeBlock())) {
 
750
      // None of the blocks consist entirely of the common tail.
 
751
      // Split a block so that one does.
 
752
      commonTailIndex = CreateCommonTailOnlyBlock(PredBB, maxCommonTailLength);
 
753
    }
 
754
 
 
755
    MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
 
756
    // MBB is common tail.  Adjust all other BB's to jump to this one.
 
757
    // Traversal must be forwards so erases work.
 
758
    DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber()
 
759
                 << " for ");
 
760
    for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
 
761
      if (commonTailIndex == i)
 
762
        continue;
 
763
      DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber()
 
764
                   << (i == e-1 ? "" : ", "));
 
765
      // Hack the end off BB i, making it jump to BB commonTailIndex instead.
 
766
      ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB);
 
767
      // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
 
768
      MergePotentials.erase(SameTails[i].getMPIter());
 
769
    }
 
770
    DEBUG(dbgs() << "\n");
 
771
    // We leave commonTailIndex in the worklist in case there are other blocks
 
772
    // that match it with a smaller number of instructions.
 
773
    MadeChange = true;
 
774
  }
 
775
  return MadeChange;
 
776
}
 
777
 
 
778
bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
 
779
 
 
780
  if (!EnableTailMerge) return false;
 
781
 
 
782
  bool MadeChange = false;
 
783
 
 
784
  // First find blocks with no successors.
 
785
  MergePotentials.clear();
 
786
  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 
787
    if (I->succ_empty())
 
788
      MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(I, 2U), I));
 
789
  }
 
790
 
 
791
  // See if we can do any tail merging on those.
 
792
  if (MergePotentials.size() < TailMergeThreshold &&
 
793
      MergePotentials.size() >= 2)
 
794
    MadeChange |= TryTailMergeBlocks(NULL, NULL);
 
795
 
 
796
  // Look at blocks (IBB) with multiple predecessors (PBB).
 
797
  // We change each predecessor to a canonical form, by
 
798
  // (1) temporarily removing any unconditional branch from the predecessor
 
799
  // to IBB, and
 
800
  // (2) alter conditional branches so they branch to the other block
 
801
  // not IBB; this may require adding back an unconditional branch to IBB
 
802
  // later, where there wasn't one coming in.  E.g.
 
803
  //   Bcc IBB
 
804
  //   fallthrough to QBB
 
805
  // here becomes
 
806
  //   Bncc QBB
 
807
  // with a conceptual B to IBB after that, which never actually exists.
 
808
  // With those changes, we see whether the predecessors' tails match,
 
809
  // and merge them if so.  We change things out of canonical form and
 
810
  // back to the way they were later in the process.  (OptimizeBranches
 
811
  // would undo some of this, but we can't use it, because we'd get into
 
812
  // a compile-time infinite loop repeatedly doing and undoing the same
 
813
  // transformations.)
 
814
 
 
815
  for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end();
 
816
       I != E; ++I) {
 
817
    if (I->pred_size() >= 2 && I->pred_size() < TailMergeThreshold) {
 
818
      SmallPtrSet<MachineBasicBlock *, 8> UniquePreds;
 
819
      MachineBasicBlock *IBB = I;
 
820
      MachineBasicBlock *PredBB = prior(I);
 
821
      MergePotentials.clear();
 
822
      for (MachineBasicBlock::pred_iterator P = I->pred_begin(),
 
823
                                            E2 = I->pred_end();
 
824
           P != E2; ++P) {
 
825
        MachineBasicBlock *PBB = *P;
 
826
        // Skip blocks that loop to themselves, can't tail merge these.
 
827
        if (PBB == IBB)
 
828
          continue;
 
829
        // Visit each predecessor only once.
 
830
        if (!UniquePreds.insert(PBB))
 
831
          continue;
 
832
        MachineBasicBlock *TBB = 0, *FBB = 0;
 
833
        SmallVector<MachineOperand, 4> Cond;
 
834
        if (!TII->AnalyzeBranch(*PBB, TBB, FBB, Cond, true)) {
 
835
          // Failing case:  IBB is the target of a cbr, and
 
836
          // we cannot reverse the branch.
 
837
          SmallVector<MachineOperand, 4> NewCond(Cond);
 
838
          if (!Cond.empty() && TBB == IBB) {
 
839
            if (TII->ReverseBranchCondition(NewCond))
 
840
              continue;
 
841
            // This is the QBB case described above
 
842
            if (!FBB)
 
843
              FBB = llvm::next(MachineFunction::iterator(PBB));
 
844
          }
 
845
          // Failing case:  the only way IBB can be reached from PBB is via
 
846
          // exception handling.  Happens for landing pads.  Would be nice
 
847
          // to have a bit in the edge so we didn't have to do all this.
 
848
          if (IBB->isLandingPad()) {
 
849
            MachineFunction::iterator IP = PBB;  IP++;
 
850
            MachineBasicBlock *PredNextBB = NULL;
 
851
            if (IP != MF.end())
 
852
              PredNextBB = IP;
 
853
            if (TBB == NULL) {
 
854
              if (IBB != PredNextBB)      // fallthrough
 
855
                continue;
 
856
            } else if (FBB) {
 
857
              if (TBB != IBB && FBB != IBB)   // cbr then ubr
 
858
                continue;
 
859
            } else if (Cond.empty()) {
 
860
              if (TBB != IBB)               // ubr
 
861
                continue;
 
862
            } else {
 
863
              if (TBB != IBB && IBB != PredNextBB)  // cbr
 
864
                continue;
 
865
            }
 
866
          }
 
867
          // Remove the unconditional branch at the end, if any.
 
868
          if (TBB && (Cond.empty() || FBB)) {
 
869
            TII->RemoveBranch(*PBB);
 
870
            if (!Cond.empty())
 
871
              // reinsert conditional branch only, for now
 
872
              TII->InsertBranch(*PBB, (TBB == IBB) ? FBB : TBB, 0, NewCond);
 
873
          }
 
874
          MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(PBB, 1U),
 
875
                                                       *P));
 
876
        }
 
877
      }
 
878
      if (MergePotentials.size() >= 2)
 
879
        MadeChange |= TryTailMergeBlocks(IBB, PredBB);
 
880
      // Reinsert an unconditional branch if needed.
 
881
      // The 1 below can occur as a result of removing blocks in TryTailMergeBlocks.
 
882
      PredBB = prior(I);      // this may have been changed in TryTailMergeBlocks
 
883
      if (MergePotentials.size() == 1 &&
 
884
          MergePotentials.begin()->getBlock() != PredBB)
 
885
        FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
 
886
    }
 
887
  }
 
888
  return MadeChange;
 
889
}
 
890
 
 
891
//===----------------------------------------------------------------------===//
 
892
//  Branch Optimization
 
893
//===----------------------------------------------------------------------===//
 
894
 
 
895
bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
 
896
  bool MadeChange = false;
 
897
 
 
898
  // Make sure blocks are numbered in order
 
899
  MF.RenumberBlocks();
 
900
 
 
901
  for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) {
 
902
    MachineBasicBlock *MBB = I++;
 
903
    MadeChange |= OptimizeBlock(MBB);
 
904
 
 
905
    // If it is dead, remove it.
 
906
    if (MBB->pred_empty()) {
 
907
      RemoveDeadBlock(MBB);
 
908
      MadeChange = true;
 
909
      ++NumDeadBlocks;
 
910
    }
 
911
  }
 
912
  return MadeChange;
 
913
}
 
914
 
 
915
 
 
916
/// IsBetterFallthrough - Return true if it would be clearly better to
 
917
/// fall-through to MBB1 than to fall through into MBB2.  This has to return
 
918
/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
 
919
/// result in infinite loops.
 
920
static bool IsBetterFallthrough(MachineBasicBlock *MBB1,
 
921
                                MachineBasicBlock *MBB2) {
 
922
  // Right now, we use a simple heuristic.  If MBB2 ends with a call, and
 
923
  // MBB1 doesn't, we prefer to fall through into MBB1.  This allows us to
 
924
  // optimize branches that branch to either a return block or an assert block
 
925
  // into a fallthrough to the return.
 
926
  if (MBB1->empty() || MBB2->empty()) return false;
 
927
 
 
928
  // If there is a clear successor ordering we make sure that one block
 
929
  // will fall through to the next
 
930
  if (MBB1->isSuccessor(MBB2)) return true;
 
931
  if (MBB2->isSuccessor(MBB1)) return false;
 
932
 
 
933
  MachineInstr *MBB1I = --MBB1->end();
 
934
  MachineInstr *MBB2I = --MBB2->end();
 
935
  return MBB2I->getDesc().isCall() && !MBB1I->getDesc().isCall();
 
936
}
 
937
 
 
938
/// OptimizeBlock - Analyze and optimize control flow related to the specified
 
939
/// block.  This is never called on the entry block.
 
940
bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
 
941
  bool MadeChange = false;
 
942
  MachineFunction &MF = *MBB->getParent();
 
943
ReoptimizeBlock:
 
944
 
 
945
  MachineFunction::iterator FallThrough = MBB;
 
946
  ++FallThrough;
 
947
 
 
948
  // If this block is empty, make everyone use its fall-through, not the block
 
949
  // explicitly.  Landing pads should not do this since the landing-pad table
 
950
  // points to this block.  Blocks with their addresses taken shouldn't be
 
951
  // optimized away.
 
952
  if (MBB->empty() && !MBB->isLandingPad() && !MBB->hasAddressTaken()) {
 
953
    // Dead block?  Leave for cleanup later.
 
954
    if (MBB->pred_empty()) return MadeChange;
 
955
 
 
956
    if (FallThrough == MF.end()) {
 
957
      // TODO: Simplify preds to not branch here if possible!
 
958
    } else {
 
959
      // Rewrite all predecessors of the old block to go to the fallthrough
 
960
      // instead.
 
961
      while (!MBB->pred_empty()) {
 
962
        MachineBasicBlock *Pred = *(MBB->pred_end()-1);
 
963
        Pred->ReplaceUsesOfBlockWith(MBB, FallThrough);
 
964
      }
 
965
      // If MBB was the target of a jump table, update jump tables to go to the
 
966
      // fallthrough instead.
 
967
      if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
 
968
        MJTI->ReplaceMBBInJumpTables(MBB, FallThrough);
 
969
      MadeChange = true;
 
970
    }
 
971
    return MadeChange;
 
972
  }
 
973
 
 
974
  // Check to see if we can simplify the terminator of the block before this
 
975
  // one.
 
976
  MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(MBB));
 
977
 
 
978
  MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0;
 
979
  SmallVector<MachineOperand, 4> PriorCond;
 
980
  bool PriorUnAnalyzable =
 
981
    TII->AnalyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
 
982
  if (!PriorUnAnalyzable) {
 
983
    // If the CFG for the prior block has extra edges, remove them.
 
984
    MadeChange |= PrevBB.CorrectExtraCFGEdges(PriorTBB, PriorFBB,
 
985
                                              !PriorCond.empty());
 
986
 
 
987
    // If the previous branch is conditional and both conditions go to the same
 
988
    // destination, remove the branch, replacing it with an unconditional one or
 
989
    // a fall-through.
 
990
    if (PriorTBB && PriorTBB == PriorFBB) {
 
991
      TII->RemoveBranch(PrevBB);
 
992
      PriorCond.clear();
 
993
      if (PriorTBB != MBB)
 
994
        TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
 
995
      MadeChange = true;
 
996
      ++NumBranchOpts;
 
997
      goto ReoptimizeBlock;
 
998
    }
 
999
 
 
1000
    // If the previous block unconditionally falls through to this block and
 
1001
    // this block has no other predecessors, move the contents of this block
 
1002
    // into the prior block. This doesn't usually happen when SimplifyCFG
 
1003
    // has been used, but it can happen if tail merging splits a fall-through
 
1004
    // predecessor of a block.
 
1005
    // This has to check PrevBB->succ_size() because EH edges are ignored by
 
1006
    // AnalyzeBranch.
 
1007
    if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
 
1008
        PrevBB.succ_size() == 1 &&
 
1009
        !MBB->hasAddressTaken()) {
 
1010
      DEBUG(dbgs() << "\nMerging into block: " << PrevBB
 
1011
                   << "From MBB: " << *MBB);
 
1012
      PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
 
1013
      PrevBB.removeSuccessor(PrevBB.succ_begin());;
 
1014
      assert(PrevBB.succ_empty());
 
1015
      PrevBB.transferSuccessors(MBB);
 
1016
      MadeChange = true;
 
1017
      return MadeChange;
 
1018
    }
 
1019
 
 
1020
    // If the previous branch *only* branches to *this* block (conditional or
 
1021
    // not) remove the branch.
 
1022
    if (PriorTBB == MBB && PriorFBB == 0) {
 
1023
      TII->RemoveBranch(PrevBB);
 
1024
      MadeChange = true;
 
1025
      ++NumBranchOpts;
 
1026
      goto ReoptimizeBlock;
 
1027
    }
 
1028
 
 
1029
    // If the prior block branches somewhere else on the condition and here if
 
1030
    // the condition is false, remove the uncond second branch.
 
1031
    if (PriorFBB == MBB) {
 
1032
      TII->RemoveBranch(PrevBB);
 
1033
      TII->InsertBranch(PrevBB, PriorTBB, 0, PriorCond);
 
1034
      MadeChange = true;
 
1035
      ++NumBranchOpts;
 
1036
      goto ReoptimizeBlock;
 
1037
    }
 
1038
 
 
1039
    // If the prior block branches here on true and somewhere else on false, and
 
1040
    // if the branch condition is reversible, reverse the branch to create a
 
1041
    // fall-through.
 
1042
    if (PriorTBB == MBB) {
 
1043
      SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
 
1044
      if (!TII->ReverseBranchCondition(NewPriorCond)) {
 
1045
        TII->RemoveBranch(PrevBB);
 
1046
        TII->InsertBranch(PrevBB, PriorFBB, 0, NewPriorCond);
 
1047
        MadeChange = true;
 
1048
        ++NumBranchOpts;
 
1049
        goto ReoptimizeBlock;
 
1050
      }
 
1051
    }
 
1052
 
 
1053
    // If this block has no successors (e.g. it is a return block or ends with
 
1054
    // a call to a no-return function like abort or __cxa_throw) and if the pred
 
1055
    // falls through into this block, and if it would otherwise fall through
 
1056
    // into the block after this, move this block to the end of the function.
 
1057
    //
 
1058
    // We consider it more likely that execution will stay in the function (e.g.
 
1059
    // due to loops) than it is to exit it.  This asserts in loops etc, moving
 
1060
    // the assert condition out of the loop body.
 
1061
    if (MBB->succ_empty() && !PriorCond.empty() && PriorFBB == 0 &&
 
1062
        MachineFunction::iterator(PriorTBB) == FallThrough &&
 
1063
        !MBB->canFallThrough()) {
 
1064
      bool DoTransform = true;
 
1065
 
 
1066
      // We have to be careful that the succs of PredBB aren't both no-successor
 
1067
      // blocks.  If neither have successors and if PredBB is the second from
 
1068
      // last block in the function, we'd just keep swapping the two blocks for
 
1069
      // last.  Only do the swap if one is clearly better to fall through than
 
1070
      // the other.
 
1071
      if (FallThrough == --MF.end() &&
 
1072
          !IsBetterFallthrough(PriorTBB, MBB))
 
1073
        DoTransform = false;
 
1074
 
 
1075
      // We don't want to do this transformation if we have control flow like:
 
1076
      //   br cond BB2
 
1077
      // BB1:
 
1078
      //   ..
 
1079
      //   jmp BBX
 
1080
      // BB2:
 
1081
      //   ..
 
1082
      //   ret
 
1083
      //
 
1084
      // In this case, we could actually be moving the return block *into* a
 
1085
      // loop!
 
1086
      if (DoTransform && !MBB->succ_empty() &&
 
1087
          (!PriorTBB->canFallThrough() || PriorTBB->empty()))
 
1088
        DoTransform = false;
 
1089
 
 
1090
 
 
1091
      if (DoTransform) {
 
1092
        // Reverse the branch so we will fall through on the previous true cond.
 
1093
        SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
 
1094
        if (!TII->ReverseBranchCondition(NewPriorCond)) {
 
1095
          DEBUG(dbgs() << "\nMoving MBB: " << *MBB
 
1096
                       << "To make fallthrough to: " << *PriorTBB << "\n");
 
1097
 
 
1098
          TII->RemoveBranch(PrevBB);
 
1099
          TII->InsertBranch(PrevBB, MBB, 0, NewPriorCond);
 
1100
 
 
1101
          // Move this block to the end of the function.
 
1102
          MBB->moveAfter(--MF.end());
 
1103
          MadeChange = true;
 
1104
          ++NumBranchOpts;
 
1105
          return MadeChange;
 
1106
        }
 
1107
      }
 
1108
    }
 
1109
  }
 
1110
 
 
1111
  // Analyze the branch in the current block.
 
1112
  MachineBasicBlock *CurTBB = 0, *CurFBB = 0;
 
1113
  SmallVector<MachineOperand, 4> CurCond;
 
1114
  bool CurUnAnalyzable= TII->AnalyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
 
1115
  if (!CurUnAnalyzable) {
 
1116
    // If the CFG for the prior block has extra edges, remove them.
 
1117
    MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty());
 
1118
 
 
1119
    // If this is a two-way branch, and the FBB branches to this block, reverse
 
1120
    // the condition so the single-basic-block loop is faster.  Instead of:
 
1121
    //    Loop: xxx; jcc Out; jmp Loop
 
1122
    // we want:
 
1123
    //    Loop: xxx; jncc Loop; jmp Out
 
1124
    if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
 
1125
      SmallVector<MachineOperand, 4> NewCond(CurCond);
 
1126
      if (!TII->ReverseBranchCondition(NewCond)) {
 
1127
        TII->RemoveBranch(*MBB);
 
1128
        TII->InsertBranch(*MBB, CurFBB, CurTBB, NewCond);
 
1129
        MadeChange = true;
 
1130
        ++NumBranchOpts;
 
1131
        goto ReoptimizeBlock;
 
1132
      }
 
1133
    }
 
1134
 
 
1135
    // If this branch is the only thing in its block, see if we can forward
 
1136
    // other blocks across it.
 
1137
    if (CurTBB && CurCond.empty() && CurFBB == 0 &&
 
1138
        MBB->begin()->getDesc().isBranch() && CurTBB != MBB &&
 
1139
        !MBB->hasAddressTaken()) {
 
1140
      // This block may contain just an unconditional branch.  Because there can
 
1141
      // be 'non-branch terminators' in the block, try removing the branch and
 
1142
      // then seeing if the block is empty.
 
1143
      TII->RemoveBranch(*MBB);
 
1144
 
 
1145
      // If this block is just an unconditional branch to CurTBB, we can
 
1146
      // usually completely eliminate the block.  The only case we cannot
 
1147
      // completely eliminate the block is when the block before this one
 
1148
      // falls through into MBB and we can't understand the prior block's branch
 
1149
      // condition.
 
1150
      if (MBB->empty()) {
 
1151
        bool PredHasNoFallThrough = !PrevBB.canFallThrough();
 
1152
        if (PredHasNoFallThrough || !PriorUnAnalyzable ||
 
1153
            !PrevBB.isSuccessor(MBB)) {
 
1154
          // If the prior block falls through into us, turn it into an
 
1155
          // explicit branch to us to make updates simpler.
 
1156
          if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
 
1157
              PriorTBB != MBB && PriorFBB != MBB) {
 
1158
            if (PriorTBB == 0) {
 
1159
              assert(PriorCond.empty() && PriorFBB == 0 &&
 
1160
                     "Bad branch analysis");
 
1161
              PriorTBB = MBB;
 
1162
            } else {
 
1163
              assert(PriorFBB == 0 && "Machine CFG out of date!");
 
1164
              PriorFBB = MBB;
 
1165
            }
 
1166
            TII->RemoveBranch(PrevBB);
 
1167
            TII->InsertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond);
 
1168
          }
 
1169
 
 
1170
          // Iterate through all the predecessors, revectoring each in-turn.
 
1171
          size_t PI = 0;
 
1172
          bool DidChange = false;
 
1173
          bool HasBranchToSelf = false;
 
1174
          while(PI != MBB->pred_size()) {
 
1175
            MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
 
1176
            if (PMBB == MBB) {
 
1177
              // If this block has an uncond branch to itself, leave it.
 
1178
              ++PI;
 
1179
              HasBranchToSelf = true;
 
1180
            } else {
 
1181
              DidChange = true;
 
1182
              PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
 
1183
              // If this change resulted in PMBB ending in a conditional
 
1184
              // branch where both conditions go to the same destination,
 
1185
              // change this to an unconditional branch (and fix the CFG).
 
1186
              MachineBasicBlock *NewCurTBB = 0, *NewCurFBB = 0;
 
1187
              SmallVector<MachineOperand, 4> NewCurCond;
 
1188
              bool NewCurUnAnalyzable = TII->AnalyzeBranch(*PMBB, NewCurTBB,
 
1189
                      NewCurFBB, NewCurCond, true);
 
1190
              if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
 
1191
                TII->RemoveBranch(*PMBB);
 
1192
                NewCurCond.clear();
 
1193
                TII->InsertBranch(*PMBB, NewCurTBB, 0, NewCurCond);
 
1194
                MadeChange = true;
 
1195
                ++NumBranchOpts;
 
1196
                PMBB->CorrectExtraCFGEdges(NewCurTBB, 0, false);
 
1197
              }
 
1198
            }
 
1199
          }
 
1200
 
 
1201
          // Change any jumptables to go to the new MBB.
 
1202
          if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
 
1203
            MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
 
1204
          if (DidChange) {
 
1205
            ++NumBranchOpts;
 
1206
            MadeChange = true;
 
1207
            if (!HasBranchToSelf) return MadeChange;
 
1208
          }
 
1209
        }
 
1210
      }
 
1211
 
 
1212
      // Add the branch back if the block is more than just an uncond branch.
 
1213
      TII->InsertBranch(*MBB, CurTBB, 0, CurCond);
 
1214
    }
 
1215
  }
 
1216
 
 
1217
  // If the prior block doesn't fall through into this block, and if this
 
1218
  // block doesn't fall through into some other block, see if we can find a
 
1219
  // place to move this block where a fall-through will happen.
 
1220
  if (!PrevBB.canFallThrough()) {
 
1221
 
 
1222
    // Now we know that there was no fall-through into this block, check to
 
1223
    // see if it has a fall-through into its successor.
 
1224
    bool CurFallsThru = MBB->canFallThrough();
 
1225
 
 
1226
    if (!MBB->isLandingPad()) {
 
1227
      // Check all the predecessors of this block.  If one of them has no fall
 
1228
      // throughs, move this block right after it.
 
1229
      for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 
1230
           E = MBB->pred_end(); PI != E; ++PI) {
 
1231
        // Analyze the branch at the end of the pred.
 
1232
        MachineBasicBlock *PredBB = *PI;
 
1233
        MachineFunction::iterator PredFallthrough = PredBB; ++PredFallthrough;
 
1234
        MachineBasicBlock *PredTBB = 0, *PredFBB = 0;
 
1235
        SmallVector<MachineOperand, 4> PredCond;
 
1236
        if (PredBB != MBB && !PredBB->canFallThrough() &&
 
1237
            !TII->AnalyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true)
 
1238
            && (!CurFallsThru || !CurTBB || !CurFBB)
 
1239
            && (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
 
1240
          // If the current block doesn't fall through, just move it.
 
1241
          // If the current block can fall through and does not end with a
 
1242
          // conditional branch, we need to append an unconditional jump to
 
1243
          // the (current) next block.  To avoid a possible compile-time
 
1244
          // infinite loop, move blocks only backward in this case.
 
1245
          // Also, if there are already 2 branches here, we cannot add a third;
 
1246
          // this means we have the case
 
1247
          // Bcc next
 
1248
          // B elsewhere
 
1249
          // next:
 
1250
          if (CurFallsThru) {
 
1251
            MachineBasicBlock *NextBB = llvm::next(MachineFunction::iterator(MBB));
 
1252
            CurCond.clear();
 
1253
            TII->InsertBranch(*MBB, NextBB, 0, CurCond);
 
1254
          }
 
1255
          MBB->moveAfter(PredBB);
 
1256
          MadeChange = true;
 
1257
          goto ReoptimizeBlock;
 
1258
        }
 
1259
      }
 
1260
    }
 
1261
 
 
1262
    if (!CurFallsThru) {
 
1263
      // Check all successors to see if we can move this block before it.
 
1264
      for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 
1265
           E = MBB->succ_end(); SI != E; ++SI) {
 
1266
        // Analyze the branch at the end of the block before the succ.
 
1267
        MachineBasicBlock *SuccBB = *SI;
 
1268
        MachineFunction::iterator SuccPrev = SuccBB; --SuccPrev;
 
1269
 
 
1270
        // If this block doesn't already fall-through to that successor, and if
 
1271
        // the succ doesn't already have a block that can fall through into it,
 
1272
        // and if the successor isn't an EH destination, we can arrange for the
 
1273
        // fallthrough to happen.
 
1274
        if (SuccBB != MBB && &*SuccPrev != MBB &&
 
1275
            !SuccPrev->canFallThrough() && !CurUnAnalyzable &&
 
1276
            !SuccBB->isLandingPad()) {
 
1277
          MBB->moveBefore(SuccBB);
 
1278
          MadeChange = true;
 
1279
          goto ReoptimizeBlock;
 
1280
        }
 
1281
      }
 
1282
 
 
1283
      // Okay, there is no really great place to put this block.  If, however,
 
1284
      // the block before this one would be a fall-through if this block were
 
1285
      // removed, move this block to the end of the function.
 
1286
      MachineBasicBlock *PrevTBB = 0, *PrevFBB = 0;
 
1287
      SmallVector<MachineOperand, 4> PrevCond;
 
1288
      if (FallThrough != MF.end() &&
 
1289
          !TII->AnalyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
 
1290
          PrevBB.isSuccessor(FallThrough)) {
 
1291
        MBB->moveAfter(--MF.end());
 
1292
        MadeChange = true;
 
1293
        return MadeChange;
 
1294
      }
 
1295
    }
 
1296
  }
 
1297
 
 
1298
  return MadeChange;
 
1299
}