CriticalAntiDepBreaker.h revision 9c2a034730b289a2cf48bc91aa2ef69737a7afbb
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/ADT/BitVector.h" 262e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/ADT/SmallSet.h" 27557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin#include <map> 282e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 292e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwinnamespace llvm { 3046df4eb46e784036cf895db271fe29e1cf2a975aEvan Chengclass TargetInstrInfo; 3146df4eb46e784036cf895db271fe29e1cf2a975aEvan Chengclass TargetRegisterInfo; 3246df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng 332e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin class CriticalAntiDepBreaker : public AntiDepBreaker { 342e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin MachineFunction& MF; 352e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin MachineRegisterInfo &MRI; 3646df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng const TargetInstrInfo *TII; 372e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin const TargetRegisterInfo *TRI; 382e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 392e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// AllocatableSet - The set of allocatable registers. 402e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// We'll be ignoring anti-dependencies on non-allocatable registers, 412e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// because they may not be safe to break. 422e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin const BitVector AllocatableSet; 432e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 442e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Classes - For live regs that are only used in one register class in a 452e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// live range, the register class. If the register is not live, the 462e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// corresponding value is null. If the register is live but used in 472e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// multiple register classes, the corresponding value is -1 casted to a 482e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// pointer. 499c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling std::vector<const TargetRegisterClass*> Classes; 502e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 512e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// RegRegs - Map registers to all their references within a live range. 522e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin std::multimap<unsigned, MachineOperand *> RegRefs; 532e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 542e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// KillIndices - The index of the most recent kill (proceding bottom-up), 552e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// or ~0u if the register is not live. 569c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling std::vector<unsigned> KillIndices; 572e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 582e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// DefIndices - The index of the most recent complete def (proceding bottom 592e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// up), or ~0u if the register is live. 609c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling std::vector<unsigned> DefIndices; 612e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 622e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// KeepRegs - A set of registers which are live and cannot be changed to 632e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// break anti-dependencies. 642e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin SmallSet<unsigned, 4> KeepRegs; 652e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 662e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin public: 672e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin CriticalAntiDepBreaker(MachineFunction& MFi); 682e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin ~CriticalAntiDepBreaker(); 692973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 702e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Start - Initialize anti-dep breaking for a new basic block. 712e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void StartBlock(MachineBasicBlock *BB); 722e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 732973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach /// BreakAntiDependencies - Identifiy anti-dependencies along the critical 742973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach /// path 752e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// of the ScheduleDAG and break them by renaming registers. 762e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// 7766db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman unsigned BreakAntiDependencies(const std::vector<SUnit>& SUnits, 7866db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman MachineBasicBlock::iterator Begin, 7966db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman MachineBasicBlock::iterator End, 802e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin unsigned InsertPosIndex); 812e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 822e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Observe - Update liveness information to account for the current 832e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// instruction, which will not be scheduled. 842e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// 852e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex); 862e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 872e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Finish - Finish anti-dep breaking for a basic block. 882e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void FinishBlock(); 892e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 902e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin private: 912e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void PrescanInstruction(MachineInstr *MI); 922e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void ScanInstruction(MachineInstr *MI, unsigned Count); 9380c2b0d9efc951b23f90a3cf12b9853177994961Jim Grosbach unsigned findSuitableFreeRegister(MachineInstr *MI, 9480c2b0d9efc951b23f90a3cf12b9853177994961Jim Grosbach unsigned AntiDepReg, 952e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin unsigned LastNewReg, 962e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin const TargetRegisterClass *); 972e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin }; 982e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin} 992e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 1002e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#endif 101