1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
| //===- llvm/CodeGen/TailDuplicator.h ----------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the TailDuplicator class. Used by the
// TailDuplication pass, and MachineBlockPlacement.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_TAILDUPLICATOR_H
#define LLVM_CODEGEN_TAILDUPLICATOR_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include <utility>
#include <vector>
namespace llvm {
class MachineBasicBlock;
class MachineBranchProbabilityInfo;
class MachineFunction;
class MachineInstr;
class MachineModuleInfo;
class MachineRegisterInfo;
class TargetRegisterInfo;
/// Utility class to perform tail duplication.
class TailDuplicator {
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
const MachineBranchProbabilityInfo *MBPI;
const MachineModuleInfo *MMI;
MachineRegisterInfo *MRI;
MachineFunction *MF;
bool PreRegAlloc;
bool LayoutMode;
unsigned TailDupSize;
// A list of virtual registers for which to update SSA form.
SmallVector<unsigned, 16> SSAUpdateVRs;
// For each virtual register in SSAUpdateVals keep a list of source virtual
// registers.
using AvailableValsTy = std::vector<std::pair<MachineBasicBlock *, unsigned>>;
DenseMap<unsigned, AvailableValsTy> SSAUpdateVals;
public:
/// Prepare to run on a specific machine function.
/// @param MF - Function that will be processed
/// @param PreRegAlloc - true if used before register allocation
/// @param MBPI - Branch Probability Info. Used to propagate correct
/// probabilities when modifying the CFG.
/// @param LayoutMode - When true, don't use the existing layout to make
/// decisions.
/// @param TailDupSize - Maxmimum size of blocks to tail-duplicate. Zero
/// default implies using the command line value TailDupSize.
void initMF(MachineFunction &MF, bool PreRegAlloc,
const MachineBranchProbabilityInfo *MBPI,
bool LayoutMode, unsigned TailDupSize = 0);
bool tailDuplicateBlocks();
static bool isSimpleBB(MachineBasicBlock *TailBB);
bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
/// Returns true if TailBB can successfully be duplicated into PredBB
bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB);
/// Tail duplicate a single basic block into its predecessors, and then clean
/// up.
/// If \p DuplicatePreds is not null, it will be updated to contain the list
/// of predecessors that received a copy of \p MBB.
/// If \p RemovalCallback is non-null. It will be called before MBB is
/// deleted.
bool tailDuplicateAndUpdate(
bool IsSimple, MachineBasicBlock *MBB,
MachineBasicBlock *ForcedLayoutPred,
SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr,
function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
private:
using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
void addSSAUpdateEntry(unsigned OrigReg, unsigned NewReg,
MachineBasicBlock *BB);
void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
MachineBasicBlock *PredBB,
DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
SmallVectorImpl<std::pair<unsigned, RegSubRegPair>> &Copies,
const DenseSet<unsigned> &UsedByPhi, bool Remove);
void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
MachineBasicBlock *PredBB,
DenseMap<unsigned, RegSubRegPair> &LocalVRMap,
const DenseSet<unsigned> &UsedByPhi);
void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
SmallVectorImpl<MachineBasicBlock *> &TDBBs,
SmallSetVector<MachineBasicBlock *, 8> &Succs);
bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
bool duplicateSimpleBB(MachineBasicBlock *TailBB,
SmallVectorImpl<MachineBasicBlock *> &TDBBs,
const DenseSet<unsigned> &RegsUsedByPhi,
SmallVectorImpl<MachineInstr *> &Copies);
bool tailDuplicate(bool IsSimple,
MachineBasicBlock *TailBB,
MachineBasicBlock *ForcedLayoutPred,
SmallVectorImpl<MachineBasicBlock *> &TDBBs,
SmallVectorImpl<MachineInstr *> &Copies);
void appendCopies(MachineBasicBlock *MBB,
SmallVectorImpl<std::pair<unsigned,RegSubRegPair>> &CopyInfos,
SmallVectorImpl<MachineInstr *> &Copies);
void removeDeadBlock(
MachineBasicBlock *MBB,
function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
};
} // end namespace llvm
#endif // LLVM_CODEGEN_TAILDUPLICATOR_H
|