← Back to branch summary

~ubuntu-branches/ubuntu/wily/clamav/wily-proposed

« back to all changes in this revision

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

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Sebastian Andrzej Siewior, Andreas Cadhalpun, Scott Kitterman, Javier Fernández-Sanguino
  • Date: 2015-01-28 00:25:13 UTC
  • mfrom: (0.48.14 sid)
  • Revision ID: package-import@ubuntu.com-20150128002513-lil2oi74cooy4lzr
Tags: 0.98.6+dfsg-1
http://bugs.debian.org/774686
http://bugs.debian.org/767350
http://bugs.debian.org/775400
http://bugs.debian.org/767353
http://bugs.debian.org/773563
[ Sebastian Andrzej Siewior ]
* update "fix-ssize_t-size_t-off_t-printf-modifier", include of misc.h was
  missing but was pulled in via the systemd patch.
* Don't leak return codes from libmspack to clamav API. (Closes: #774686).

[ Andreas Cadhalpun ]
* Add patch to avoid emitting incremental progress messages when not
  outputting to a terminal. (Closes: #767350)
* Update lintian-overrides for unused-file-paragraph-in-dep5-copyright.
* clamav-base.postinst: always chown /var/log/clamav and /var/lib/clamav
  to clamav:clamav, not only on fresh installations. (Closes: #775400)
* Adapt the clamav-daemon and clamav-freshclam logrotate scripts,
  so that they correctly work under systemd.
* Move the PidFile variable from the clamd/freshclam configuration files
  to the init scripts. This makes the init scripts more robust against
  misconfiguration and avoids error messages with systemd. (Closes: #767353)
* debian/copyright: drop files from Files-Excluded only present in github
  tarballs
* Drop Workaround-a-bug-in-libc-on-Hurd.patch, because hurd got fixed.
  (see #752237)
* debian/rules: Remove useless --with-system-tommath --without-included-ltdl
  configure options.

[ Scott Kitterman ]
* Stop stripping llvm when repacking the tarball as the system llvm on some
  releases is too old to use
* New upstream bugfix release
  - Library shared object revisions.
  - Includes a patch from Sebastian Andrzej Siewior making ClamAV pid files
    compatible with systemd.
  - Fix a heap out of bounds condition with crafted Yoda's crypter files.
    This issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted mew packer files. This
    issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted upx packer files. This
    issue was discovered by Kevin Szkudlapski of Quarkslab.
  - Fix a heap out of bounds condition with crafted upack packer files. This
    issue was discovered by Sebastian Andrzej Siewior. CVE-2014-9328.
  - Compensate a crash due to incorrect compiler optimization when handling
    crafted petite packer files. This issue was discovered by Sebastian
    Andrzej Siewior.
* Update lintian override for embedded zlib to match new so version

[ Javier Fernández-Sanguino ]
* Updated Spanish Debconf template translation (Closes: #773563)

Show diffs side-by-side

added added

removed removed

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