BranchFolding.h revision cd4f04d6bcb7aefa24d92582fbadfe17519f4756 
1//===-- BranchFolding.h - Fold machine code branch instructions --*- C++ -*===//
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#ifndef LLVM_CODEGEN_BRANCHFOLDING_HPP
11#define LLVM_CODEGEN_BRANCHFOLDING_HPP
12
13#include "llvm/CodeGen/MachineBasicBlock.h"
14#include "llvm/CodeGen/MachineFunctionPass.h"
15#include "llvm/Target/TargetMachine.h"
16#include <vector>
17
18namespace llvm {
19  class MachineFunction;
20  class MachineModuleInfo;
21  class RegScavenger;
22  class TargetInstrInfo;
23  class TargetRegisterInfo;
24
25  class BranchFolder {
26  public:
27    explicit BranchFolder(bool defaultEnableTailMerge, CodeGenOpt::Level OL);
28
29    bool OptimizeFunction(MachineFunction &MF,
30                          const TargetInstrInfo *tii,
31                          const TargetRegisterInfo *tri,
32                          MachineModuleInfo *mmi);
33  private:
34    typedef std::pair<unsigned,MachineBasicBlock*> MergePotentialsElt;
35    typedef std::vector<MergePotentialsElt>::iterator MPIterator;
36    std::vector<MergePotentialsElt> MergePotentials;
37
38    typedef std::pair<MPIterator, MachineBasicBlock::iterator> SameTailElt;
39    std::vector<SameTailElt> SameTails;
40
41    CodeGenOpt::Level OptLevel;
42    bool EnableTailMerge;
43    const TargetInstrInfo *TII;
44    const TargetRegisterInfo *TRI;
45    MachineModuleInfo *MMI;
46    RegScavenger *RS;
47
48    bool TailMergeBlocks(MachineFunction &MF);
49    bool TryMergeBlocks(MachineBasicBlock* SuccBB,
50                        MachineBasicBlock* PredBB);
51    void ReplaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
52                                 MachineBasicBlock *NewDest);
53    MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
54                                  MachineBasicBlock::iterator BBI1);
55    unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength);
56    void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
57                                                MachineBasicBlock* PredBB);
58    unsigned CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
59                                       unsigned maxCommonTailLength);
60
61    bool OptimizeBranches(MachineFunction &MF);
62    bool OptimizeBlock(MachineBasicBlock *MBB);
63    void RemoveDeadBlock(MachineBasicBlock *MBB);
64    bool OptimizeImpDefsBlock(MachineBasicBlock *MBB);
65
66    bool CanFallThrough(MachineBasicBlock *CurBB);
67    bool CanFallThrough(MachineBasicBlock *CurBB, bool BranchUnAnalyzable,
68                        MachineBasicBlock *TBB, MachineBasicBlock *FBB,
69                        const SmallVectorImpl<MachineOperand> &Cond);
70  };
71
72
73  /// BranchFolderPass - Wrap branch folder in a machine function pass.
74  class BranchFolderPass : public MachineFunctionPass,
75                           public BranchFolder {
76  public:
77    static char ID;
78    explicit BranchFolderPass(bool defaultEnableTailMerge,
79                              CodeGenOpt::Level OptLevel)
80      :  MachineFunctionPass(&ID),
81      BranchFolder(defaultEnableTailMerge, OptLevel) {}
82
83    virtual bool runOnMachineFunction(MachineFunction &MF);
84    virtual const char *getPassName() const { return "Control Flow Optimizer"; }
85  };
86}
87
88#endif /* LLVM_CODEGEN_BRANCHFOLDING_HPP */
89