Newer
Older
David Goodwin
committed
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
128
129
130
131
132
133
134
135
136
//=- llvm/CodeGen/AggressiveAntiDepBreaker.h - Anti-Dep Support -*- C++ -*-=//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the AggressiveAntiDepBreaker class, which
// implements register anti-dependence breaking during post-RA
// scheduling. It attempts to break all anti-dependencies within a
// block.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H
#define LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H
#include "llvm/CodeGen/AntiDepBreaker.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/SmallSet.h"
namespace llvm {
class AggressiveAntiDepBreaker : public AntiDepBreaker {
MachineFunction& MF;
MachineRegisterInfo &MRI;
const TargetRegisterInfo *TRI;
/// RegisterReference - Information about a register reference
/// within a liverange
typedef struct {
/// Operand - The registers operand
MachineOperand *Operand;
/// RC - The register class
const TargetRegisterClass *RC;
} RegisterReference;
/// AllocatableSet - The set of allocatable registers.
/// We'll be ignoring anti-dependencies on non-allocatable registers,
/// because they may not be safe to break.
const BitVector AllocatableSet;
/// GroupNodes - Implements a disjoint-union data structure to
/// form register groups. A node is represented by an index into
/// the vector. A node can "point to" itself to indicate that it
/// is the parent of a group, or point to another node to indicate
/// that it is a member of the same group as that node.
std::vector<unsigned> GroupNodes;
/// GroupNodeIndices - For each register, the index of the GroupNode
/// currently representing the group that the register belongs to.
/// Register 0 is always represented by the 0 group, a group
/// composed of registers that are not eligible for anti-aliasing.
unsigned GroupNodeIndices[TargetRegisterInfo::FirstVirtualRegister];
/// RegRegs - Map registers to all their references within a live range.
std::multimap<unsigned, RegisterReference> RegRefs;
/// KillIndices - The index of the most recent kill (proceding bottom-up),
/// or ~0u if the register is not live.
unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister];
/// DefIndices - The index of the most recent complete def (proceding bottom
/// up), or ~0u if the register is live.
unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister];
public:
AggressiveAntiDepBreaker(MachineFunction& MFi);
~AggressiveAntiDepBreaker();
/// Start - Initialize anti-dep breaking for a new basic block.
void StartBlock(MachineBasicBlock *BB);
/// BreakAntiDependencies - Identifiy anti-dependencies along the critical path
/// of the ScheduleDAG and break them by renaming registers.
///
unsigned BreakAntiDependencies(std::vector<SUnit>& SUnits,
MachineBasicBlock::iterator& Begin,
MachineBasicBlock::iterator& End,
unsigned InsertPosIndex);
/// Observe - Update liveness information to account for the current
/// instruction, which will not be scheduled.
///
void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex);
/// Finish - Finish anti-dep breaking for a basic block.
void FinishBlock();
private:
// GetGroup - Get the group for a register. The returned value is
// the index of the GroupNode representing the group.
unsigned GetGroup(unsigned Reg);
// GetGroupRegs - Return a vector of the registers belonging to a
// group.
void GetGroupRegs(unsigned Group, std::vector<unsigned> &Regs);
// UnionGroups - Union Reg1's and Reg2's groups to form a new
// group. Return the index of the GroupNode representing the
// group.
unsigned UnionGroups(unsigned Reg1, unsigned Reg2);
// LeaveGroup - Remove a register from its current group and place
// it alone in its own group. Return the index of the GroupNode
// representing the registers new group.
unsigned LeaveGroup(unsigned Reg);
/// IsLive - Return true if Reg is live
bool IsLive(unsigned Reg);
/// IsImplicitDefUse - Return true if MO represents a register
/// that is both implicitly used and defined in MI
bool IsImplicitDefUse(MachineInstr *MI, MachineOperand& MO);
/// GetPassthruRegs - If MI implicitly def/uses a register, then
/// return that register and all subregisters.
void GetPassthruRegs(MachineInstr *MI, std::set<unsigned>& PassthruRegs);
void PrescanInstruction(MachineInstr *MI, unsigned Count,
std::set<unsigned>& PassthruRegs);
void ScanInstruction(MachineInstr *MI, unsigned Count);
BitVector GetRenameRegisters(unsigned Reg);
bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex,
std::map<unsigned, unsigned> &RenameMap);
};
}
#endif