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" 20a1514e24cc24b050f53a12650e047799358833a1Chandler Carruth#include "llvm/ADT/BitVector.h" 212e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/CodeGen/MachineBasicBlock.h" 222e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/CodeGen/MachineFrameInfo.h" 232e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/CodeGen/MachineFunction.h" 242e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/CodeGen/MachineRegisterInfo.h" 251525260b3e50cc578939ef41b60609689eecfdd2Andrew Trick#include "llvm/CodeGen/RegisterClassInfo.h" 262e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#include "llvm/CodeGen/ScheduleDAG.h" 27557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin#include <map> 282e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 292e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwinnamespace llvm { 30fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesenclass RegisterClassInfo; 3146df4eb46e784036cf895db271fe29e1cf2a975aEvan Chengclass TargetInstrInfo; 3246df4eb46e784036cf895db271fe29e1cf2a975aEvan Chengclass TargetRegisterInfo; 3346df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng 342e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin class CriticalAntiDepBreaker : public AntiDepBreaker { 352e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin MachineFunction& MF; 362e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin MachineRegisterInfo &MRI; 3746df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng const TargetInstrInfo *TII; 382e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin const TargetRegisterInfo *TRI; 39fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen const RegisterClassInfo &RegClassInfo; 402e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 412e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// AllocatableSet - The set of allocatable registers. 422e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// We'll be ignoring anti-dependencies on non-allocatable registers, 432e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// because they may not be safe to break. 442e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin const BitVector AllocatableSet; 452e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 462e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Classes - For live regs that are only used in one register class in a 472e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// live range, the register class. If the register is not live, the 482e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// corresponding value is null. If the register is live but used in 492e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// multiple register classes, the corresponding value is -1 casted to a 502e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// pointer. 519c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling std::vector<const TargetRegisterClass*> Classes; 522e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 5335edc42f9830af1a6ebf215d7635b04547e8e624Mikhail Glushenkov /// RegRefs - Map registers to all their references within a live range. 542e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin std::multimap<unsigned, MachineOperand *> RegRefs; 5546388526963aba92344ee8ebd9e86d3556baa088Andrew Trick typedef std::multimap<unsigned, MachineOperand *>::const_iterator 5646388526963aba92344ee8ebd9e86d3556baa088Andrew Trick RegRefIter; 572e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 58cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// KillIndices - The index of the most recent kill (proceeding bottom-up), 592e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// or ~0u if the register is not live. 609c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling std::vector<unsigned> KillIndices; 612e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 62cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// DefIndices - The index of the most recent complete def (proceeding 63cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// bottom up), or ~0u if the register is live. 649c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling std::vector<unsigned> DefIndices; 652e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 662e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// KeepRegs - A set of registers which are live and cannot be changed to 672e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// break anti-dependencies. 68cff4ad768ec721b72498dc6b605d882e36c1fb14Benjamin Kramer BitVector KeepRegs; 692e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 702e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin public: 71fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen CriticalAntiDepBreaker(MachineFunction& MFi, const RegisterClassInfo&); 722e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin ~CriticalAntiDepBreaker(); 732973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 742e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Start - Initialize anti-dep breaking for a new basic block. 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void StartBlock(MachineBasicBlock *BB) override; 762e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 772973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach /// BreakAntiDependencies - Identifiy anti-dependencies along the critical 782973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach /// path 792e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// of the ScheduleDAG and break them by renaming registers. 802e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// 8166db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman unsigned BreakAntiDependencies(const std::vector<SUnit>& SUnits, 8266db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman MachineBasicBlock::iterator Begin, 8366db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman MachineBasicBlock::iterator End, 84e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel unsigned InsertPosIndex, 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DbgValueVector &DbgValues) override; 862e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 872e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Observe - Update liveness information to account for the current 882e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// instruction, which will not be scheduled. 892e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void Observe(MachineInstr *MI, unsigned Count, 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned InsertPosIndex) override; 922e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 932e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin /// Finish - Finish anti-dep breaking for a basic block. 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void FinishBlock() override; 952e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 962e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin private: 972e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void PrescanInstruction(MachineInstr *MI); 982e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin void ScanInstruction(MachineInstr *MI, unsigned Count); 99bc4bd92d52be2f6707a8c311873ded27a8f2481fAndrew Trick bool isNewRegClobberedByRefs(RegRefIter RegRefBegin, 100bc4bd92d52be2f6707a8c311873ded27a8f2481fAndrew Trick RegRefIter RegRefEnd, 101bc4bd92d52be2f6707a8c311873ded27a8f2481fAndrew Trick unsigned NewReg); 10246388526963aba92344ee8ebd9e86d3556baa088Andrew Trick unsigned findSuitableFreeRegister(RegRefIter RegRefBegin, 10346388526963aba92344ee8ebd9e86d3556baa088Andrew Trick RegRefIter RegRefEnd, 10480c2b0d9efc951b23f90a3cf12b9853177994961Jim Grosbach unsigned AntiDepReg, 1052e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin unsigned LastNewReg, 1065ff776bfde2dd5d993e51f8f78904ce331b5528cBill Schmidt const TargetRegisterClass *RC, 10778477ffdfd63ddf1ba22d9d2121c8f6ed9f9efa1Craig Topper SmallVectorImpl<unsigned> &Forbid); 1082e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin }; 1092e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin} 1102e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin 1112e7be612d5d0eb42ee3ae08194dbb03b750cc6bfDavid Goodwin#endif 112