← Back to branch summary

~ubuntu-branches/ubuntu/maverick/clamav/maverick-security

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Marc Deslauriers
  • Date: 2011-02-23 14:27:51 UTC
  • mfrom: (0.35.17 sid)
  • Revision ID: james.westby@ubuntu.com-20110223142751-o9xb8jyvhkh75d0n
Tags: 0.96.5+dfsg-1ubuntu1.10.10.2
* SECURITY UPDATE: denial of service via double free in vba processing
  - libclamav/vba_extract.c: set buf to NULL when it gets freed.
  - http://git.clamav.net/gitweb?p=clamav-devel.git;a=commit;h=d21fb8d975f8c9688894a8cef4d50d977022e09f
  - CVE-2011-1003

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/IfConversion.cpp
20
20
#include "llvm/Target/TargetInstrInfo.h"
21
21
#include "llvm/Target/TargetLowering.h"
22
22
#include "llvm/Target/TargetMachine.h"
 
23
#include "llvm/Target/TargetRegisterInfo.h"
23
24
#include "llvm/Support/CommandLine.h"
24
25
#include "llvm/Support/Debug.h"
25
26
#include "llvm/Support/ErrorHandling.h"
33
34
static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
34
35
static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
35
36
static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
36
 
static cl::opt<bool> DisableSimple("disable-ifcvt-simple", 
 
37
static cl::opt<bool> DisableSimple("disable-ifcvt-simple",
37
38
                                   cl::init(false), cl::Hidden);
38
 
static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false", 
 
39
static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false",
39
40
                                    cl::init(false), cl::Hidden);
40
 
static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle", 
 
41
static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle",
41
42
                                     cl::init(false), cl::Hidden);
42
 
static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev", 
43
 
                                      cl::init(false), cl::Hidden);
44
 
static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false", 
45
 
                                      cl::init(false), cl::Hidden);
46
 
static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev", 
 
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",
47
48
                                       cl::init(false), cl::Hidden);
48
 
static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond", 
 
49
static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",
49
50
                                    cl::init(false), cl::Hidden);
 
51
static cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold",
 
52
                                     cl::init(true), cl::Hidden);
50
53
 
51
54
STATISTIC(NumSimple,       "Number of simple if-conversions performed");
52
55
STATISTIC(NumSimpleFalse,  "Number of simple (F) if-conversions performed");
115
118
                 BB(0), TrueBB(0), FalseBB(0) {}
116
119
    };
117
120
 
118
 
    /// IfcvtToken - Record information about pending if-conversions to attemp:
 
121
    /// IfcvtToken - Record information about pending if-conversions to attempt:
119
122
    /// BBI             - Corresponding BBInfo.
120
123
    /// Kind            - Type of block. See IfcvtKind.
121
124
    /// NeedSubsumption - True if the to-be-predicated BB has already been
146
149
 
147
150
    const TargetLowering *TLI;
148
151
    const TargetInstrInfo *TII;
 
152
    const TargetRegisterInfo *TRI;
149
153
    bool MadeChange;
150
154
    int FnNum;
151
155
  public:
152
156
    static char ID;
153
 
    IfConverter() : MachineFunctionPass(&ID), FnNum(-1) {}
 
157
    IfConverter() : MachineFunctionPass(ID), FnNum(-1) {}
154
158
 
155
159
    virtual bool runOnMachineFunction(MachineFunction &MF);
156
160
    virtual const char *getPassName() const { return "If Converter"; }
167
171
                         std::vector<IfcvtToken*> &Tokens);
168
172
    bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
169
173
                             bool isTriangle = false, bool RevBranch = false);
170
 
    bool AnalyzeBlocks(MachineFunction &MF,
171
 
                       std::vector<IfcvtToken*> &Tokens);
 
174
    void AnalyzeBlocks(MachineFunction &MF, std::vector<IfcvtToken*> &Tokens);
172
175
    void InvalidatePreds(MachineBasicBlock *BB);
173
176
    void RemoveExtraEdges(BBInfo &BBI);
174
177
    bool IfConvertSimple(BBInfo &BBI, IfcvtKind Kind);
177
180
                          unsigned NumDups1, unsigned NumDups2);
178
181
    void PredicateBlock(BBInfo &BBI,
179
182
                        MachineBasicBlock::iterator E,
180
 
                        SmallVectorImpl<MachineOperand> &Cond);
 
183
                        SmallVectorImpl<MachineOperand> &Cond,
 
184
                        SmallSet<unsigned, 4> &Redefs);
181
185
    void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
182
186
                               SmallVectorImpl<MachineOperand> &Cond,
 
187
                               SmallSet<unsigned, 4> &Redefs,
183
188
                               bool IgnoreBr = false);
184
 
    void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI);
185
 
 
186
 
    bool MeetIfcvtSizeLimit(unsigned Size) const {
187
 
      return Size > 0 && Size <= TLI->getIfCvtBlockSizeLimit();
 
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);
188
199
    }
189
200
 
190
201
    // blockAlwaysFallThrough - Block ends without a terminator.
219
230
  char IfConverter::ID = 0;
220
231
}
221
232
 
222
 
static RegisterPass<IfConverter>
223
 
X("if-converter", "If Converter");
 
233
INITIALIZE_PASS(IfConverter, "if-converter", "If Converter", false, false);
224
234
 
225
235
FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); }
226
236
 
227
237
bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
228
238
  TLI = MF.getTarget().getTargetLowering();
229
239
  TII = MF.getTarget().getInstrInfo();
 
240
  TRI = MF.getTarget().getRegisterInfo();
230
241
  if (!TII) return false;
231
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
 
232
249
  DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum <<  ") \'"
233
250
               << MF.getFunction()->getName() << "\'");
234
251
 
253
270
  while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) {
254
271
    // Do an initial analysis for each basic block and find all the potential
255
272
    // candidates to perform if-conversion.
256
 
    bool Change = AnalyzeBlocks(MF, Tokens);
 
273
    bool Change = false;
 
274
    AnalyzeBlocks(MF, Tokens);
257
275
    while (!Tokens.empty()) {
258
276
      IfcvtToken *Token = Tokens.back();
259
277
      Tokens.pop_back();
281
299
      case ICSimpleFalse: {
282
300
        bool isFalse = Kind == ICSimpleFalse;
283
301
        if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break;
284
 
        DEBUG(dbgs() << "Ifcvt (Simple" << (Kind == ICSimpleFalse ? " false" :"")
 
302
        DEBUG(dbgs() << "Ifcvt (Simple" << (Kind == ICSimpleFalse ?
 
303
                                            " false" : "")
285
304
                     << "): BB#" << BBI.BB->getNumber() << " ("
286
305
                     << ((Kind == ICSimpleFalse)
287
306
                         ? BBI.FalseBB->getNumber()
289
308
        RetVal = IfConvertSimple(BBI, Kind);
290
309
        DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
291
310
        if (RetVal) {
292
 
          if (isFalse) NumSimpleFalse++;
293
 
          else         NumSimple++;
 
311
          if (isFalse) ++NumSimpleFalse;
 
312
          else         ++NumSimple;
294
313
        }
295
314
       break;
296
315
      }
316
335
        DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
317
336
        if (RetVal) {
318
337
          if (isFalse) {
319
 
            if (isRev) NumTriangleFRev++;
320
 
            else       NumTriangleFalse++;
 
338
            if (isRev) ++NumTriangleFRev;
 
339
            else       ++NumTriangleFalse;
321
340
          } else {
322
 
            if (isRev) NumTriangleRev++;
323
 
            else       NumTriangle++;
 
341
            if (isRev) ++NumTriangleRev;
 
342
            else       ++NumTriangle;
324
343
          }
325
344
        }
326
345
        break;
332
351
                     << BBI.FalseBB->getNumber() << ") ");
333
352
        RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2);
334
353
        DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
335
 
        if (RetVal) NumDiamonds++;
 
354
        if (RetVal) ++NumDiamonds;
336
355
        break;
337
356
      }
338
357
      }
361
380
  Roots.clear();
362
381
  BBAnalysis.clear();
363
382
 
364
 
  if (MadeChange) {
 
383
  if (MadeChange && IfCvtBranchFold) {
365
384
    BranchFolder BF(false);
366
385
    BF.OptimizeFunction(MF, TII,
367
386
                        MF.getTarget().getRegisterInfo(),
368
387
                        getAnalysisIfAvailable<MachineModuleInfo>());
369
388
  }
370
389
 
 
390
  MadeChange |= BFChange;
371
391
  return MadeChange;
372
392
}
373
393
 
387
407
/// ReverseBranchCondition - Reverse the condition of the end of the block
388
408
/// branch. Swap block's 'true' and 'false' successors.
389
409
bool IfConverter::ReverseBranchCondition(BBInfo &BBI) {
 
410
  DebugLoc dl;  // FIXME: this is nowhere
390
411
  if (!TII->ReverseBranchCondition(BBI.BrCond)) {
391
412
    TII->RemoveBranch(*BBI.BB);
392
 
    TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond);
 
413
    TII->InsertBranch(*BBI.BB, BBI.FalseBB, BBI.TrueBB, BBI.BrCond, dl);
393
414
    std::swap(BBI.TrueBB, BBI.FalseBB);
394
415
    return true;
395
416
  }
420
441
 
421
442
  if (TrueBBI.BB->pred_size() > 1) {
422
443
    if (TrueBBI.CannotBeCopied ||
423
 
        TrueBBI.NonPredSize > TLI->getIfCvtDupBlockSizeLimit())
 
444
        !TII->isProfitableToDupForIfCvt(*TrueBBI.BB, TrueBBI.NonPredSize))
424
445
      return false;
425
446
    Dups = TrueBBI.NonPredSize;
426
447
  }
431
452
/// ValidTriangle - Returns true if the 'true' and 'false' blocks (along
432
453
/// with their common predecessor) forms a valid triangle shape for ifcvt.
433
454
/// If 'FalseBranch' is true, it checks if 'true' block's false branch
434
 
/// branches to the false branch rather than the other way around. It also
 
455
/// branches to the 'false' block rather than the other way around. It also
435
456
/// returns the number of instructions that the ifcvt would need to duplicate
436
457
/// if performed in 'Dups'.
437
458
bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
457
478
          ++Size;
458
479
      }
459
480
    }
460
 
    if (Size > TLI->getIfCvtDupBlockSizeLimit())
 
481
    if (!TII->isProfitableToDupForIfCvt(*TrueBBI.BB, Size))
461
482
      return false;
462
483
    Dups = Size;
463
484
  }
514
535
 
515
536
  MachineBasicBlock::iterator TI = TrueBBI.BB->begin();
516
537
  MachineBasicBlock::iterator FI = FalseBBI.BB->begin();
517
 
  while (TI != TrueBBI.BB->end() && FI != FalseBBI.BB->end()) {
 
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
    }
518
559
    if (!TI->isIdenticalTo(FI))
519
560
      break;
520
561
    ++Dups1;
524
565
 
525
566
  TI = firstNonBranchInst(TrueBBI.BB, TII);
526
567
  FI = firstNonBranchInst(FalseBBI.BB, TII);
527
 
  while (TI != TrueBBI.BB->begin() && FI != FalseBBI.BB->begin()) {
 
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
    }
528
589
    if (!TI->isIdenticalTo(FI))
529
590
      break;
530
591
    ++Dups2;
556
617
    // No false branch. This BB must end with a conditional branch and a
557
618
    // fallthrough.
558
619
    if (!BBI.FalseBB)
559
 
      BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);  
 
620
      BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);
560
621
    if (!BBI.FalseBB) {
561
622
      // Malformed bcc? True and false blocks are the same?
562
623
      BBI.IsUnpredicable = true;
569
630
  BBI.ClobbersPred = false;
570
631
  for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
571
632
       I != E; ++I) {
 
633
    if (I->isDebugValue())
 
634
      continue;
 
635
 
572
636
    const TargetInstrDesc &TID = I->getDesc();
573
637
    if (TID.isNotDuplicable())
574
638
      BBI.CannotBeCopied = true;
702
766
  bool FNeedSub = FalseBBI.Predicate.size() > 0;
703
767
  bool Enqueued = false;
704
768
  if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) &&
705
 
      MeetIfcvtSizeLimit(TrueBBI.NonPredSize - (Dups + Dups2)) &&
706
 
      MeetIfcvtSizeLimit(FalseBBI.NonPredSize - (Dups + Dups2)) &&
 
769
      MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize - (Dups + Dups2),
 
770
                         *FalseBBI.BB, FalseBBI.NonPredSize - (Dups + Dups2)) &&
707
771
      FeasibilityAnalysis(TrueBBI, BBI.BrCond) &&
708
772
      FeasibilityAnalysis(FalseBBI, RevCond)) {
709
773
    // Diamond:
720
784
  }
721
785
 
722
786
  if (ValidTriangle(TrueBBI, FalseBBI, false, Dups) &&
723
 
      MeetIfcvtSizeLimit(TrueBBI.NonPredSize) &&
 
787
      MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize) &&
724
788
      FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
725
789
    // Triangle:
726
790
    //   EBB
732
796
    Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups));
733
797
    Enqueued = true;
734
798
  }
735
 
  
 
799
 
736
800
  if (ValidTriangle(TrueBBI, FalseBBI, true, Dups) &&
737
 
      MeetIfcvtSizeLimit(TrueBBI.NonPredSize) &&
 
801
      MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize) &&
738
802
      FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
739
803
    Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups));
740
804
    Enqueued = true;
741
805
  }
742
806
 
743
807
  if (ValidSimple(TrueBBI, Dups) &&
744
 
      MeetIfcvtSizeLimit(TrueBBI.NonPredSize) &&
 
808
      MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize) &&
745
809
      FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
746
810
    // Simple (split, no rejoin):
747
811
    //   EBB
748
812
    //   | \_
749
813
    //   |  |
750
814
    //   | TBB---> exit
751
 
    //   |    
 
815
    //   |
752
816
    //   FBB
753
817
    Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups));
754
818
    Enqueued = true;
757
821
  if (CanRevCond) {
758
822
    // Try the other path...
759
823
    if (ValidTriangle(FalseBBI, TrueBBI, false, Dups) &&
760
 
        MeetIfcvtSizeLimit(FalseBBI.NonPredSize) &&
 
824
        MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize) &&
761
825
        FeasibilityAnalysis(FalseBBI, RevCond, true)) {
762
826
      Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups));
763
827
      Enqueued = true;
764
828
    }
765
829
 
766
830
    if (ValidTriangle(FalseBBI, TrueBBI, true, Dups) &&
767
 
        MeetIfcvtSizeLimit(FalseBBI.NonPredSize) &&
 
831
        MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize) &&
768
832
        FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
769
833
      Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups));
770
834
      Enqueued = true;
771
835
    }
772
836
 
773
837
    if (ValidSimple(FalseBBI, Dups) &&
774
 
        MeetIfcvtSizeLimit(FalseBBI.NonPredSize) &&
 
838
        MeetIfcvtSizeLimit(*FalseBBI.BB, FalseBBI.NonPredSize) &&
775
839
        FeasibilityAnalysis(FalseBBI, RevCond)) {
776
840
      Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups));
777
841
      Enqueued = true;
785
849
}
786
850
 
787
851
/// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
788
 
/// candidates. It returns true if any CFG restructuring is done to expose more
789
 
/// if-conversion opportunities.
790
 
bool IfConverter::AnalyzeBlocks(MachineFunction &MF,
 
852
/// candidates.
 
853
void IfConverter::AnalyzeBlocks(MachineFunction &MF,
791
854
                                std::vector<IfcvtToken*> &Tokens) {
792
 
  bool Change = false;
793
855
  std::set<MachineBasicBlock*> Visited;
794
856
  for (unsigned i = 0, e = Roots.size(); i != e; ++i) {
795
857
    for (idf_ext_iterator<MachineBasicBlock*> I=idf_ext_begin(Roots[i],Visited),
801
863
 
802
864
  // Sort to favor more complex ifcvt scheme.
803
865
  std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp);
804
 
 
805
 
  return Change;
806
866
}
807
867
 
808
868
/// canFallThroughTo - Returns true either if ToBB is the next block after BB or
809
869
/// that all the intervening blocks are empty (given BB can fall through to its
810
870
/// next block).
811
871
static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) {
812
 
  MachineFunction::iterator I = BB;
 
872
  MachineFunction::iterator PI = BB;
 
873
  MachineFunction::iterator I = llvm::next(PI);
813
874
  MachineFunction::iterator TI = ToBB;
814
875
  MachineFunction::iterator E = BB->getParent()->end();
815
 
  while (++I != TI)
816
 
    if (I == E || !I->empty())
 
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))
817
880
      return false;
 
881
    PI = I++;
 
882
  }
818
883
  return true;
819
884
}
820
885
 
836
901
///
837
902
static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB,
838
903
                               const TargetInstrInfo *TII) {
 
904
  DebugLoc dl;  // FIXME: this is nowhere
839
905
  SmallVector<MachineOperand, 0> NoCond;
840
 
  TII->InsertBranch(*BB, ToBB, NULL, NoCond);
 
906
  TII->InsertBranch(*BB, ToBB, NULL, NoCond, dl);
841
907
}
842
908
 
843
909
/// RemoveExtraEdges - Remove true / false edges if either / both are no longer
849
915
    BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
850
916
}
851
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
 
852
978
/// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG.
853
979
///
854
980
bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
873
999
    if (TII->ReverseBranchCondition(Cond))
874
1000
      assert(false && "Unable to reverse branch condition!");
875
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
 
876
1008
  if (CvtBBI->BB->pred_size() > 1) {
877
1009
    BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
878
1010
    // Copy instructions in the true block, predicate them, and add them to
879
1011
    // the entry block.
880
 
    CopyAndPredicateBlock(BBI, *CvtBBI, Cond);
 
1012
    CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs);
881
1013
  } else {
882
 
    PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
 
1014
    PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
883
1015
 
884
1016
    // Merge converted block into entry block.
885
1017
    BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
922
1054
  BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
923
1055
  BBInfo *CvtBBI = &TrueBBI;
924
1056
  BBInfo *NextBBI = &FalseBBI;
 
1057
  DebugLoc dl;  // FIXME: this is nowhere
925
1058
 
926
1059
  SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
927
1060
  if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
957
1090
    }
958
1091
  }
959
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
 
960
1099
  bool HasEarlyExit = CvtBBI->FalseBB != NULL;
961
 
  bool DupBB = CvtBBI->BB->pred_size() > 1;
962
 
  if (DupBB) {
 
1100
  if (CvtBBI->BB->pred_size() > 1) {
963
1101
    BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
964
1102
    // Copy instructions in the true block, predicate them, and add them to
965
1103
    // the entry block.
966
 
    CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);
 
1104
    CopyAndPredicateBlock(BBI, *CvtBBI, Cond, Redefs, true);
967
1105
  } else {
968
1106
    // Predicate the 'true' block after removing its branch.
969
1107
    CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
970
 
    PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
 
1108
    PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond, Redefs);
971
1109
 
972
1110
    // Now merge the entry of the triangle with the true block.
973
1111
    BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
974
 
    MergeBlocks(BBI, *CvtBBI);
 
1112
    MergeBlocks(BBI, *CvtBBI, false);
975
1113
  }
976
1114
 
977
1115
  // If 'true' block has a 'false' successor, add an exit branch to it.
980
1118
                                           CvtBBI->BrCond.end());
981
1119
    if (TII->ReverseBranchCondition(RevCond))
982
1120
      assert(false && "Unable to reverse branch condition!");
983
 
    TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond);
 
1121
    TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond, dl);
984
1122
    BBI.BB->addSuccessor(CvtBBI->FalseBB);
985
1123
  }
986
1124
 
1009
1147
  RemoveExtraEdges(BBI);
1010
1148
 
1011
1149
  // Update block info. BB can be iteratively if-converted.
1012
 
  if (!IterIfcvt) 
 
1150
  if (!IterIfcvt)
1013
1151
    BBI.IsDone = true;
1014
1152
  InvalidatePreds(BBI.BB);
1015
1153
  CvtBBI->IsDone = true;
1044
1182
    return false;
1045
1183
  }
1046
1184
 
1047
 
  // Merge the 'true' and 'false' blocks by copying the instructions
1048
 
  // from the 'false' block to the 'true' block. That is, unless the true
1049
 
  // block would clobber the predicate, in that case, do the opposite.
 
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.
1050
1188
  BBInfo *BBI1 = &TrueBBI;
1051
1189
  BBInfo *BBI2 = &FalseBBI;
1052
1190
  SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
1071
1209
  // Remove the conditional branch from entry to the blocks.
1072
1210
  BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
1073
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
 
1074
1217
  // Remove the duplicated instructions at the beginnings of both paths.
1075
1218
  MachineBasicBlock::iterator DI1 = BBI1->BB->begin();
1076
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;
1077
1227
  BBI1->NonPredSize -= NumDups1;
1078
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
  }
1079
1236
  while (NumDups1 != 0) {
1080
 
    ++DI1;
1081
1237
    ++DI2;
1082
 
    --NumDups1;
 
1238
    if (!DI2->isDebugValue())
 
1239
      --NumDups1;
1083
1240
  }
 
1241
 
 
1242
  UpdatePredRedefs(BBI1->BB->begin(), DI1, Redefs, TRI);
1084
1243
  BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
1085
1244
  BBI2->BB->erase(BBI2->BB->begin(), DI2);
1086
1245
 
1087
1246
  // Predicate the 'true' block after removing its branch.
1088
1247
  BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
1089
1248
  DI1 = BBI1->BB->end();
1090
 
  for (unsigned i = 0; i != NumDups2; ++i)
 
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());
1091
1253
    --DI1;
 
1254
    // skip dbg_value instructions
 
1255
    if (!DI1->isDebugValue())
 
1256
      ++i;
 
1257
  }
1092
1258
  BBI1->BB->erase(DI1, BBI1->BB->end());
1093
 
  PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1);
 
1259
  PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1, Redefs);
1094
1260
 
1095
1261
  // Predicate the 'false' block.
1096
1262
  BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
1097
1263
  DI2 = BBI2->BB->end();
1098
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());
1099
1268
    --DI2;
1100
 
    --NumDups2;
 
1269
    // skip dbg_value instructions
 
1270
    if (!DI2->isDebugValue())
 
1271
      --NumDups2;
1101
1272
  }
1102
 
  PredicateBlock(*BBI2, DI2, *Cond2);
 
1273
  PredicateBlock(*BBI2, DI2, *Cond2, Redefs);
1103
1274
 
1104
1275
  // Merge the true block into the entry of the diamond.
1105
 
  MergeBlocks(BBI, *BBI1);
1106
 
  MergeBlocks(BBI, *BBI2);
 
1276
  MergeBlocks(BBI, *BBI1, TailBB == 0);
 
1277
  MergeBlocks(BBI, *BBI2, TailBB == 0);
1107
1278
 
1108
1279
  // If the if-converted block falls through or unconditionally branches into
1109
1280
  // the tail block, and the tail block does not have other predecessors, then
1111
1282
  // tail, add a unconditional branch to it.
1112
1283
  if (TailBB) {
1113
1284
    BBInfo TailBBI = BBAnalysis[TailBB->getNumber()];
1114
 
    if (TailBB->pred_size() == 1 && !TailBBI.HasFallThrough) {
1115
 
      BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
 
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) {
1116
1297
      MergeBlocks(BBI, TailBBI);
1117
1298
      TailBBI.IsDone = true;
1118
1299
    } else {
 
1300
      BBI.BB->addSuccessor(TailBB);
1119
1301
      InsertUncondBranch(BBI.BB, TailBB, TII);
1120
1302
      BBI.HasFallThrough = false;
1121
1303
    }
1122
1304
  }
1123
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);
1124
1311
  RemoveExtraEdges(BBI);
1125
1312
 
1126
1313
  // Update block info.
1135
1322
/// specified end with the specified condition.
1136
1323
void IfConverter::PredicateBlock(BBInfo &BBI,
1137
1324
                                 MachineBasicBlock::iterator E,
1138
 
                                 SmallVectorImpl<MachineOperand> &Cond) {
 
1325
                                 SmallVectorImpl<MachineOperand> &Cond,
 
1326
                                 SmallSet<unsigned, 4> &Redefs) {
1139
1327
  for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
1140
 
    if (TII->isPredicated(I))
 
1328
    if (I->isDebugValue() || TII->isPredicated(I))
1141
1329
      continue;
1142
1330
    if (!TII->PredicateInstruction(I, Cond)) {
1143
1331
#ifndef NDEBUG
1145
1333
#endif
1146
1334
      llvm_unreachable(0);
1147
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);
1148
1340
  }
1149
1341
 
1150
1342
  std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
1152
1344
  BBI.IsAnalyzed = false;
1153
1345
  BBI.NonPredSize = 0;
1154
1346
 
1155
 
  NumIfConvBBs++;
 
1347
  ++NumIfConvBBs;
1156
1348
}
1157
1349
 
1158
1350
/// CopyAndPredicateBlock - Copy and predicate instructions from source BB to
1159
1351
/// the destination block. Skip end of block branches if IgnoreBr is true.
1160
1352
void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
1161
1353
                                        SmallVectorImpl<MachineOperand> &Cond,
 
1354
                                        SmallSet<unsigned, 4> &Redefs,
1162
1355
                                        bool IgnoreBr) {
1163
1356
  MachineFunction &MF = *ToBBI.BB->getParent();
1164
1357
 
1165
1358
  for (MachineBasicBlock::iterator I = FromBBI.BB->begin(),
1166
1359
         E = FromBBI.BB->end(); I != E; ++I) {
1167
1360
    const TargetInstrDesc &TID = I->getDesc();
1168
 
    bool isPredicated = TII->isPredicated(I);
1169
1361
    // Do not copy the end of the block branches.
1170
 
    if (IgnoreBr && !isPredicated && TID.isBranch())
 
1362
    if (IgnoreBr && TID.isBranch())
1171
1363
      break;
1172
1364
 
1173
1365
    MachineInstr *MI = MF.CloneMachineInstr(I);
1174
1366
    ToBBI.BB->insert(ToBBI.BB->end(), MI);
1175
1367
    ToBBI.NonPredSize++;
1176
1368
 
1177
 
    if (!isPredicated)
 
1369
    if (!TII->isPredicated(I) && !MI->isDebugValue()) {
1178
1370
      if (!TII->PredicateInstruction(MI, Cond)) {
1179
1371
#ifndef NDEBUG
1180
1372
        dbgs() << "Unable to predicate " << *I << "!\n";
1181
1373
#endif
1182
1374
        llvm_unreachable(0);
1183
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);
1184
1381
  }
1185
1382
 
1186
 
  std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1187
 
                                         FromBBI.BB->succ_end());
1188
 
  MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1189
 
  MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
 
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;
1190
1388
 
1191
 
  for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1192
 
    MachineBasicBlock *Succ = Succs[i];
1193
 
    // Fallthrough edge can't be transferred.
1194
 
    if (Succ == FallThrough)
1195
 
      continue;
1196
 
    ToBBI.BB->addSuccessor(Succ);
 
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
    }
1197
1396
  }
1198
1397
 
1199
1398
  std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
1203
1402
  ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
1204
1403
  ToBBI.IsAnalyzed = false;
1205
1404
 
1206
 
  NumDupBBs++;
 
1405
  ++NumDupBBs;
1207
1406
}
1208
1407
 
1209
1408
/// MergeBlocks - Move all instructions from FromBB to the end of ToBB.
1210
 
///
1211
 
void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI) {
 
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) {
1212
1414
  ToBBI.BB->splice(ToBBI.BB->end(),
1213
1415
                   FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
1214
1416
 
1215
 
  // Redirect all branches to FromBB to ToBB.
1216
 
  std::vector<MachineBasicBlock *> Preds(FromBBI.BB->pred_begin(),
1217
 
                                         FromBBI.BB->pred_end());
1218
 
  for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
1219
 
    MachineBasicBlock *Pred = Preds[i];
1220
 
    if (Pred == ToBBI.BB)
1221
 
      continue;
1222
 
    Pred->ReplaceUsesOfBlockWith(FromBBI.BB, ToBBI.BB);
1223
 
  }
1224
 
 
1225
1417
  std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
1226
1418
                                         FromBBI.BB->succ_end());
1227
1419
  MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
1233
1425
    if (Succ == FallThrough)
1234
1426
      continue;
1235
1427
    FromBBI.BB->removeSuccessor(Succ);
1236
 
    ToBBI.BB->addSuccessor(Succ);
 
1428
    if (AddEdges)
 
1429
      ToBBI.BB->addSuccessor(Succ);
1237
1430
  }
1238
1431
 
1239
1432
  // Now FromBBI always falls through to the next block!