-/* Title: PhyRegAlloc.h
- Author: Ruchira Sasanka
- Date: Aug 20, 01
- Purpose: This is the main entry point for register allocation.
-
- Notes:
-
- * RegisterClasses: Each RegClass accepts a
- MachineRegClass which contains machine specific info about that register
- class. The code in the RegClass is machine independent and they use
- access functions in the MachineRegClass object passed into it to get
- machine specific info.
-
- * Machine dependent work: All parts of the register coloring algorithm
- except coloring of an individual node are machine independent.
-
- Register allocation must be done as:
-
- static const MachineRegInfo MRI = MachineRegInfo(); // machine reg info
-
- MethodLiveVarInfo LVI(*MethodI ); // compute LV info
- LVI.analyze();
-
- PhyRegAlloc PRA(*MethodI, &MRI, &LVI); // allocate regs
- PRA.allocateRegisters();
-
- Assumptions:
- All values in a live range will be of the same physical reg class.
-
-*/
-
+//===-- PhyRegAlloc.h - Graph Coloring Register Allocator -------*- c++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This is the main entry point for register allocation.
+//
+// Notes:
+// * RegisterClasses: Each RegClass accepts a
+// TargetRegClass which contains machine specific info about that register
+// class. The code in the RegClass is machine independent and they use
+// access functions in the TargetRegClass object passed into it to get
+// machine specific info.
+//
+// * Machine dependent work: All parts of the register coloring algorithm
+// except coloring of an individual node are machine independent.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef PHYREGALLOC_H
+#define PHYREGALLOC_H
+
+#include "LiveRangeInfo.h"
+#include "llvm/Pass.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/Target/TargetRegInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include <map>
+
+class MachineFunction;
+class FunctionLiveVarInfo;
+class MachineInstr;
+class LoopInfo;
+class RegClass;
+class Constant;
+
+//----------------------------------------------------------------------------
+// Class AddedInstrns:
+// When register allocator inserts new instructions in to the existing
+// instruction stream, it does NOT directly modify the instruction stream.
+// Rather, it creates an object of AddedInstrns and stick it in the
+// AddedInstrMap for an existing instruction. This class contains two vectors
+// to store such instructions added before and after an existing instruction.
+//----------------------------------------------------------------------------
+
+struct AddedInstrns {
+ std::vector<MachineInstr*> InstrnsBefore;//Insts added BEFORE an existing inst
+ std::vector<MachineInstr*> InstrnsAfter; //Insts added AFTER an existing inst
+ inline void clear () { InstrnsBefore.clear (); InstrnsAfter.clear (); }
+};
+//----------------------------------------------------------------------------
+// class PhyRegAlloc:
+// Main class the register allocator. Call runOnFunction() to allocate
+// registers for a Function.
+//----------------------------------------------------------------------------
-#ifndef PHY_REG_ALLOC_H
-#define PHY_REG_ALLOC_H
+class PhyRegAlloc : public FunctionPass {
+ std::vector<RegClass *> RegClassList; // vector of register classes
+ const TargetMachine &TM; // target machine
+ const Function *Fn; // name of the function we work on
+ MachineFunction *MF; // descriptor for method's native code
+ FunctionLiveVarInfo *LVI; // LV information for this method
+ // (already computed for BBs)
+ LiveRangeInfo *LRI; // LR info (will be computed)
+ const TargetRegInfo &MRI; // Machine Register information
+ const unsigned NumOfRegClasses; // recorded here for efficiency
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/CodeGen/RegClass.h"
-#include "llvm/CodeGen/LiveRangeInfo.h"
-#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
+ // Map to indicate whether operands of each MachineInstr have been
+ // updated according to their assigned colors. This is only used in
+ // assertion checking (debug builds).
+ std::map<const MachineInstr *, bool> OperandsColoredMap;
+
+ // AddedInstrMap - Used to store instrns added in this phase
+ std::map<const MachineInstr *, AddedInstrns> AddedInstrMap;
+ // ScratchRegsUsed - Contains scratch register uses for a particular MI.
+ typedef std::multimap<const MachineInstr*, int> ScratchRegsUsedTy;
+ ScratchRegsUsedTy ScratchRegsUsed;
-class AddedInstrns
-{
- public:
- vector<MachineInstr *> InstrnsBefore;
- vector<MachineInstr *> InstrnsAfter;
+ AddedInstrns AddedInstrAtEntry; // to store instrns added at entry
+ const LoopInfo *LoopDepthCalc; // to calculate loop depths
- AddedInstrns() : InstrnsBefore(), InstrnsAfter() { }
-};
+ std::map<const Function *, Constant *> FnAllocState;
-typedef hash_map<const MachineInstr *, AddedInstrns *> AddedInstrMapType;
+ PhyRegAlloc(const PhyRegAlloc&); // DO NOT IMPLEMENT
+ void operator=(const PhyRegAlloc&); // DO NOT IMPLEMENT
+public:
+ inline PhyRegAlloc (const TargetMachine &TM_) :
+ TM (TM_), MRI (TM.getRegInfo ()),
+ NumOfRegClasses (MRI.getNumOfRegClasses ()) { }
+ virtual ~PhyRegAlloc() { }
+ /// runOnFunction - Main method called for allocating registers.
+ ///
+ virtual bool runOnFunction (Function &F);
+ virtual bool doFinalization (Module &M);
-class PhyRegAlloc
-{
+ virtual void getAnalysisUsage (AnalysisUsage &AU) const;
- vector<RegClass *> RegClassList ; // vector of register classes
- const Method *const Meth; // name of the method we work on
- const TargetMachine &TM; // target machine
- MethodLiveVarInfo *const LVI; // LV information for this method
- // (already computed for BBs)
- LiveRangeInfo LRI; // LR info (will be computed)
- const MachineRegInfo &MRI; // Machine Register information
- const unsigned NumOfRegClasses; // recorded here for efficiency
+ const char *getPassName () const {
+ return "Traditional graph-coloring reg. allocator";
+ }
- //vector<const Instruction *> CallInstrList; // a list of all call instrs
- //vector<const Instruction *> RetInstrList; // a list of all return instrs
+ inline const RegClass* getRegClassByID(unsigned id) const {
+ return RegClassList[id];
+ }
+ inline RegClass *getRegClassByID(unsigned id) { return RegClassList[id]; }
- AddedInstrMapType AddedInstrMap; // to store instrns added in this phase
+private:
+ void addInterference(const Value *Def, const ValueSet *LVSet,
+ bool isCallInst);
+ bool markAllocatedRegs(MachineInstr* MInst);
+ void addInterferencesForArgs();
+ void createIGNodeListsAndIGs();
+ void buildInterferenceGraphs();
+ void saveState();
+ void setCallInterferences(const MachineInstr *MI,
+ const ValueSet *LVSetAft);
- //------- private methods ---------------------------------------------------
+ void move2DelayedInstr(const MachineInstr *OrigMI,
+ const MachineInstr *DelayedMI);
- void addInterference(const Value *const Def, const LiveVarSet *const LVSet,
- const bool isCallInst);
+ void markUnusableSugColors();
+ void allocateStackSpace4SpilledLRs();
- void addInterferencesForArgs();
- void createIGNodeListsAndIGs();
- void buildInterferenceGraphs();
+ void insertCode4SpilledLR(const LiveRange *LR,
+ MachineBasicBlock::iterator& MII,
+ MachineBasicBlock &MBB, unsigned OpNum);
- inline void constructLiveRanges()
- { LRI.constructLiveRanges(); }
+ // Method for inserting caller saving code. The caller must save all the
+ // volatile registers live across a call.
+ void insertCallerSavingCode(std::vector<MachineInstr*>& instrnsBefore,
+ std::vector<MachineInstr*>& instrnsAfter,
+ MachineInstr *CallMI,
+ const BasicBlock *BB);
void colorIncomingArgs();
void colorCallRetArgs();
void updateMachineCode();
+ void updateInstruction(MachineBasicBlock::iterator& MII,
+ MachineBasicBlock &MBB);
- void printLabel(const Value *const Val);
- void printMachineCode();
+ int getUsableUniRegAtMI(int RegType, const ValueSet *LVSetBef,
+ MachineInstr *MI,
+ std::vector<MachineInstr*>& MIBef,
+ std::vector<MachineInstr*>& MIAft);
+
+ // Callback method used to find unused registers.
+ // LVSetBef is the live variable set to search for an unused register.
+ // If it is not specified, the LV set before the current MI is used.
+ // This is sufficient as long as no new copy instructions are generated
+ // to copy the free register to memory.
+ //
+ int getUnusedUniRegAtMI(RegClass *RC, int RegType,
+ const MachineInstr *MI,
+ const ValueSet *LVSetBef = 0);
- public:
- PhyRegAlloc(const Method *const M, const TargetMachine& TM,
- MethodLiveVarInfo *const Lvi);
+ void setRelRegsUsedByThisInst(RegClass *RC, int RegType,
+ const MachineInstr *MI);
- void allocateRegisters(); // main method called for allocatin
+ int getUniRegNotUsedByThisInst(RegClass *RC, int RegType,
+ const MachineInstr *MI);
+ void addInterf4PseudoInstr(const MachineInstr *MI);
};
-
-
-
-
-
-
-
#endif
-
projects / oota-llvm.git / blobdiff