CriticalAntiDepBreaker.h revision 2973b57093b017f2e3b5f5edd0be9d4ea180f0e9
12e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin//=- llvm/CodeGen/CriticalAntiDepBreaker.h - Anti-Dep Support -*- C++ -*-=// 22e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// 32e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// The LLVM Compiler Infrastructure 42e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// 52e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// This file is distributed under the University of Illinois Open Source 62e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// License. See LICENSE.TXT for details. 72e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// 82e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin//===----------------------------------------------------------------------===// 92e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// 102e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// This file implements the CriticalAntiDepBreaker class, which 112e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// implements register anti-dependence breaking along a blocks 122e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// critical path during post-RA scheduler. 132e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin// 142e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin//===----------------------------------------------------------------------===// 152e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 162e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#ifndef LLVM_CODEGEN_CRITICALANTIDEPBREAKER_H 172e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#define LLVM_CODEGEN_CRITICALANTIDEPBREAKER_H 182e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 1982c7248518a8b759a567fbb4b3176542ad2cf414David Goodwin#include "AntiDepBreaker.h" 202e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/CodeGen/MachineBasicBlock.h" 212e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/CodeGen/MachineFrameInfo.h" 222e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/CodeGen/MachineFunction.h" 232e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/CodeGen/MachineRegisterInfo.h" 242e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/CodeGen/ScheduleDAG.h" 252e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/Target/TargetRegisterInfo.h" 262e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/ADT/BitVector.h" 272e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/ADT/SmallSet.h" 28557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin#include <map> 292e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 302e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwinnamespace llvm { 312e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin class CriticalAntiDepBreaker : public AntiDepBreaker { 322e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin MachineFunction& MF; 332e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin MachineRegisterInfo &MRI; 342e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin const TargetRegisterInfo *TRI; 352e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 362e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// AllocatableSet - The set of allocatable registers. 372e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// We'll be ignoring anti-dependencies on non-allocatable registers, 382e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// because they may not be safe to break. 392e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin const BitVector AllocatableSet; 402e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 412e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Classes - For live regs that are only used in one register class in a 422e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// live range, the register class. If the register is not live, the 432e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// corresponding value is null. If the register is live but used in 442e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// multiple register classes, the corresponding value is -1 casted to a 452e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// pointer. 462e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin const TargetRegisterClass * 472e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin Classes[TargetRegisterInfo::FirstVirtualRegister]; 482e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 492e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// RegRegs - Map registers to all their references within a live range. 502e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin std::multimap<unsigned, MachineOperand *> RegRefs; 512e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 522e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// KillIndices - The index of the most recent kill (proceding bottom-up), 532e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// or ~0u if the register is not live. 542e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; 552e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 562e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// DefIndices - The index of the most recent complete def (proceding bottom 572e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// up), or ~0u if the register is live. 582e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister]; 592e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 602e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// KeepRegs - A set of registers which are live and cannot be changed to 612e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// break anti-dependencies. 622e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin SmallSet<unsigned, 4> KeepRegs; 632e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 642e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin public: 652e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin CriticalAntiDepBreaker(MachineFunction& MFi); 662e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin ~CriticalAntiDepBreaker(); 672973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 682e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Start - Initialize anti-dep breaking for a new basic block. 692e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void StartBlock(MachineBasicBlock *BB); 702e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 712973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach /// BreakAntiDependencies - Identifiy anti-dependencies along the critical 722973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach /// path 732e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// of the ScheduleDAG and break them by renaming registers. 742e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// 752e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin unsigned BreakAntiDependencies(std::vector<SUnit>& SUnits, 762e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin MachineBasicBlock::iterator& Begin, 772e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin MachineBasicBlock::iterator& End, 782e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin unsigned InsertPosIndex); 792e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 802e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Observe - Update liveness information to account for the current 812e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// instruction, which will not be scheduled. 822e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// 832e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex); 842e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 852e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Finish - Finish anti-dep breaking for a basic block. 862e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void FinishBlock(); 872e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 882e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin private: 892e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void PrescanInstruction(MachineInstr *MI); 902e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void ScanInstruction(MachineInstr *MI, unsigned Count); 912e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin unsigned findSuitableFreeRegister(unsigned AntiDepReg, 922e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin unsigned LastNewReg, 932e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin const TargetRegisterClass *); 942e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin }; 952e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin} 962e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 972e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#endif 98