AggressiveAntiDepBreaker.h revision 348777110a960f0e017025dd5141cb29472c3984
1//=- llvm/CodeGen/AggressiveAntiDepBreaker.h - Anti-Dep Support -*- 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// 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 13// block. 14// 15//===----------------------------------------------------------------------===// 16 17#ifndef LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 18#define LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 19 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" 29 30namespace llvm { 31 class AggressiveAntiDepBreaker : public AntiDepBreaker { 32 MachineFunction& MF; 33 MachineRegisterInfo &MRI; 34 const TargetRegisterInfo *TRI; 35 36 /// RegisterReference - Information about a register reference 37 /// within a liverange 38 typedef struct { 39 /// Operand - The registers operand 40 MachineOperand *Operand; 41 /// RC - The register class 42 const TargetRegisterClass *RC; 43 } RegisterReference; 44 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; 49 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; 56 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]; 62 63 /// RegRegs - Map registers to all their references within a live range. 64 std::multimap<unsigned, RegisterReference> RegRefs; 65 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]; 69 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]; 73 74 public: 75 AggressiveAntiDepBreaker(MachineFunction& MFi); 76 ~AggressiveAntiDepBreaker(); 77 78 /// Start - Initialize anti-dep breaking for a new basic block. 79 void StartBlock(MachineBasicBlock *BB); 80 81 /// BreakAntiDependencies - Identifiy anti-dependencies along the critical path 82 /// of the ScheduleDAG and break them by renaming registers. 83 /// 84 unsigned BreakAntiDependencies(std::vector<SUnit>& SUnits, 85 MachineBasicBlock::iterator& Begin, 86 MachineBasicBlock::iterator& End, 87 unsigned InsertPosIndex); 88 89 /// Observe - Update liveness information to account for the current 90 /// instruction, which will not be scheduled. 91 /// 92 void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex); 93 94 /// Finish - Finish anti-dep breaking for a basic block. 95 void FinishBlock(); 96 97 private: 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); 101 102 // GetGroupRegs - Return a vector of the registers belonging to a 103 // group. 104 void GetGroupRegs(unsigned Group, std::vector<unsigned> &Regs); 105 106 // UnionGroups - Union Reg1's and Reg2's groups to form a new 107 // group. Return the index of the GroupNode representing the 108 // group. 109 unsigned UnionGroups(unsigned Reg1, unsigned Reg2); 110 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); 115 116 /// IsLive - Return true if Reg is live 117 bool IsLive(unsigned Reg); 118 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); 122 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); 126 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); 133 }; 134} 135 136#endif 137