1 //=- llvm/CodeGen/AggressiveAntiDepBreaker.h - Anti-Dep Support -*- C++ -*-=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the AggressiveAntiDepBreaker class, which
11 // implements register anti-dependence breaking during post-RA
12 // scheduling. It attempts to break all anti-dependencies within a
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H
18 #define LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H
20 #include "llvm/CodeGen/AntiDepBreaker.h"
21 #include "llvm/CodeGen/MachineBasicBlock.h"
22 #include "llvm/CodeGen/MachineFrameInfo.h"
23 #include "llvm/CodeGen/MachineFunction.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/ScheduleDAG.h"
26 #include "llvm/Target/TargetRegisterInfo.h"
27 #include "llvm/ADT/BitVector.h"
28 #include "llvm/ADT/SmallSet.h"
31 class AggressiveAntiDepBreaker : public AntiDepBreaker {
33 MachineRegisterInfo &MRI;
34 const TargetRegisterInfo *TRI;
36 /// RegisterReference - Information about a register reference
37 /// within a liverange
39 /// Operand - The registers operand
40 MachineOperand *Operand;
41 /// RC - The register class
42 const TargetRegisterClass *RC;
45 /// AllocatableSet - The set of allocatable registers.
46 /// We'll be ignoring anti-dependencies on non-allocatable registers,
47 /// because they may not be safe to break.
48 const BitVector AllocatableSet;
50 /// GroupNodes - Implements a disjoint-union data structure to
51 /// form register groups. A node is represented by an index into
52 /// the vector. A node can "point to" itself to indicate that it
53 /// is the parent of a group, or point to another node to indicate
54 /// that it is a member of the same group as that node.
55 std::vector<unsigned> GroupNodes;
57 /// GroupNodeIndices - For each register, the index of the GroupNode
58 /// currently representing the group that the register belongs to.
59 /// Register 0 is always represented by the 0 group, a group
60 /// composed of registers that are not eligible for anti-aliasing.
61 unsigned GroupNodeIndices[TargetRegisterInfo::FirstVirtualRegister];
63 /// RegRegs - Map registers to all their references within a live range.
64 std::multimap<unsigned, RegisterReference> RegRefs;
66 /// KillIndices - The index of the most recent kill (proceding bottom-up),
67 /// or ~0u if the register is not live.
68 unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister];
70 /// DefIndices - The index of the most recent complete def (proceding bottom
71 /// up), or ~0u if the register is live.
72 unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister];
75 AggressiveAntiDepBreaker(MachineFunction& MFi);
76 ~AggressiveAntiDepBreaker();
78 /// Start - Initialize anti-dep breaking for a new basic block.
79 void StartBlock(MachineBasicBlock *BB);
81 /// BreakAntiDependencies - Identifiy anti-dependencies along the critical path
82 /// of the ScheduleDAG and break them by renaming registers.
84 unsigned BreakAntiDependencies(std::vector<SUnit>& SUnits,
85 MachineBasicBlock::iterator& Begin,
86 MachineBasicBlock::iterator& End,
87 unsigned InsertPosIndex);
89 /// Observe - Update liveness information to account for the current
90 /// instruction, which will not be scheduled.
92 void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex);
94 /// Finish - Finish anti-dep breaking for a basic block.
98 // GetGroup - Get the group for a register. The returned value is
99 // the index of the GroupNode representing the group.
100 unsigned GetGroup(unsigned Reg);
102 // GetGroupRegs - Return a vector of the registers belonging to a
104 void GetGroupRegs(unsigned Group, std::vector<unsigned> &Regs);
106 // UnionGroups - Union Reg1's and Reg2's groups to form a new
107 // group. Return the index of the GroupNode representing the
109 unsigned UnionGroups(unsigned Reg1, unsigned Reg2);
111 // LeaveGroup - Remove a register from its current group and place
112 // it alone in its own group. Return the index of the GroupNode
113 // representing the registers new group.
114 unsigned LeaveGroup(unsigned Reg);
116 /// IsLive - Return true if Reg is live
117 bool IsLive(unsigned Reg);
119 /// IsImplicitDefUse - Return true if MO represents a register
120 /// that is both implicitly used and defined in MI
121 bool IsImplicitDefUse(MachineInstr *MI, MachineOperand& MO);
123 /// GetPassthruRegs - If MI implicitly def/uses a register, then
124 /// return that register and all subregisters.
125 void GetPassthruRegs(MachineInstr *MI, std::set<unsigned>& PassthruRegs);
127 void PrescanInstruction(MachineInstr *MI, unsigned Count,
128 std::set<unsigned>& PassthruRegs);
129 void ScanInstruction(MachineInstr *MI, unsigned Count);
130 BitVector GetRenameRegisters(unsigned Reg);
131 bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex,
132 std::map<unsigned, unsigned> &RenameMap);