Woot! Thanks!
Evan
On Jun 8, 2007, at 10:19 AM, David Greene wrote:
>
>
> Changes in directory llvm/include/llvm/CodeGen:
>
> SimpleRegisterCoalescing.h added (r1.1)
> Passes.h updated: 1.26 -> 1.27
> LiveIntervalAnalysis.h updated: 1.85 -> 1.86
> ---
> Log message:
>
> Factor live variable analysis so it does not do register coalescing
> simultaneously. Move that pass to SimpleRegisterCoalescing.
>
> This makes it easier to implement alternative register allocation and
> coalescing strategies while maintaining reuse of the existing live
> interval analysis.
>
>
> ---
> Diffs of the changes: (+195 -114)
>
> LiveIntervalAnalysis.h | 144 +++++++
> +--------------------------------
> Passes.h | 5 +
> SimpleRegisterCoalescing.h | 160 +++++++++++++++++++++++++++++++++
> ++++++++++++
> 3 files changed, 195 insertions(+), 114 deletions(-)
>
>
> Index: llvm/include/llvm/CodeGen/SimpleRegisterCoalescing.h
> diff -c /dev/null llvm/include/llvm/CodeGen/
> SimpleRegisterCoalescing.h:1.1
> *** /dev/null Fri Jun 8 12:19:06 2007
> --- llvm/include/llvm/CodeGen/SimpleRegisterCoalescing.h Fri Jun 8
> 12:18:56 2007
> ***************
> *** 0 ****
> --- 1,160 ----
> + //===-- SimpleRegisterCoalescing.h - Register Coalescing --------
> *- 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 file implements a simple register copy coalescing phase.
> + //
> + //
> ===-------------------------------------------------------------------
> ---===//
> +
> + #ifndef LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H
> + #define LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H
> +
> + #include "llvm/CodeGen/MachineFunctionPass.h"
> + #include "llvm/CodeGen/LiveInterval.h"
> + #include "llvm/CodeGen/LiveIntervalAnalysis.h"
> + #include "llvm/ADT/BitVector.h"
> + #include "llvm/ADT/IndexedMap.h"
> +
> + namespace llvm {
> +
> + class LiveVariables;
> + class MRegisterInfo;
> + class TargetInstrInfo;
> + class VirtRegMap;
> +
> + class SimpleRegisterCoalescing : public MachineFunctionPass {
> + MachineFunction* mf_;
> + const TargetMachine* tm_;
> + const MRegisterInfo* mri_;
> + const TargetInstrInfo* tii_;
> + LiveIntervals *li_;
> + LiveVariables *lv_;
> +
> + typedef IndexedMap<unsigned> Reg2RegMap;
> + Reg2RegMap r2rMap_;
> +
> + BitVector allocatableRegs_;
> + DenseMap<const TargetRegisterClass*, BitVector>
> allocatableRCRegs_;
> +
> + /// JoinedLIs - Keep track which register intervals have been
> coalesced
> + /// with other intervals.
> + BitVector JoinedLIs;
> +
> + public:
> + static char ID; // Pass identifcation, replacement for typeid
> + SimpleRegisterCoalescing() : MachineFunctionPass((intptr_t)
> &ID) {};
> +
> + struct CopyRec {
> + MachineInstr *MI;
> + unsigned SrcReg, DstReg;
> + };
> + CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg,
> unsigned DstReg) {
> + CopyRec R;
> + R.MI = MI;
> + R.SrcReg = SrcReg;
> + R.DstReg = DstReg;
> + return R;
> + }
> + struct InstrSlots {
> + enum {
> + LOAD = 0,
> + USE = 1,
> + DEF = 2,
> + STORE = 3,
> + NUM = 4
> + };
> + };
> +
> + virtual void getAnalysisUsage(AnalysisUsage &AU) const;
> + virtual void releaseMemory();
> +
> + /// runOnMachineFunction - pass entry point
> + virtual bool runOnMachineFunction(MachineFunction&);
> +
> + /// print - Implement the dump method.
> + virtual void print(std::ostream &O, const Module* = 0) const;
> + void print(std::ostream *O, const Module* M = 0) const {
> + if (O) print(*O, M);
> + }
> +
> + private:
> + /// joinIntervals - join compatible live intervals
> + void joinIntervals();
> +
> + /// CopyCoallesceInMBB - Coallsece copies in the specified
> MBB, putting
> + /// copies that cannot yet be coallesced into the "TryAgain"
> list.
> + void CopyCoallesceInMBB(MachineBasicBlock *MBB,
> + std::vector<CopyRec> *TryAgain, bool
> PhysOnly = false);
> +
> + /// JoinCopy - Attempt to join intervals corresponding to
> SrcReg/DstReg,
> + /// which are the src/dst of the copy instruction CopyMI.
> This returns true
> + /// if the copy was successfully coallesced away, or if it is
> never possible
> + /// to coallesce these this copy, due to register
> constraints. It returns
> + /// false if it is not currently possible to coallesce this
> interval, but
> + /// it may be possible if other things get coallesced.
> + bool JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned
> DstReg,
> + bool PhysOnly = false);
> +
> + /// JoinIntervals - Attempt to join these two intervals. On
> failure, this
> + /// returns false. Otherwise, if one of the intervals being
> joined is a
> + /// physreg, this method always canonicalizes DestInt to be
> it. The output
> + /// "SrcInt" will not have been modified, so we can use this
> information
> + /// below to update aliases.
> + bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS);
> +
> + /// SimpleJoin - Attempt to join the specified interval into
> this one. The
> + /// caller of this method must guarantee that the RHS only
> contains a single
> + /// value number and that the RHS is not defined by a copy
> from this
> + /// interval. This returns false if the intervals are not
> joinable, or it
> + /// joins them and returns true.
> + bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS);
> +
> + /// Return true if the two specified registers belong to
> different
> + /// register classes. The registers may be either phys or
> virt regs.
> + bool differingRegisterClasses(unsigned RegA, unsigned RegB)
> const;
> +
> +
> + bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval
> &IntB,
> + MachineInstr *CopyMI);
> +
> + /// lastRegisterUse - Returns the last use of the specific
> register between
> + /// cycles Start and End. It also returns the use operand by
> reference. It
> + /// returns NULL if there are no uses.
> + MachineInstr *lastRegisterUse(unsigned Start, unsigned End,
> unsigned Reg,
> + MachineOperand *&MOU);
> +
> + /// findDefOperand - Returns the MachineOperand that is a def
> of the specific
> + /// register. It returns NULL if the def is not found.
> + MachineOperand *findDefOperand(MachineInstr *MI, unsigned Reg);
> +
> + /// unsetRegisterKill - Unset IsKill property of all uses of
> the specific
> + /// register of the specific instruction.
> + void unsetRegisterKill(MachineInstr *MI, unsigned Reg);
> +
> + /// unsetRegisterKills - Unset IsKill property of all uses of
> specific register
> + /// between cycles Start and End.
> + void unsetRegisterKills(unsigned Start, unsigned End,
> unsigned Reg);
> +
> + /// hasRegisterDef - True if the instruction defines the
> specific register.
> + ///
> + bool hasRegisterDef(MachineInstr *MI, unsigned Reg);
> +
> + /// rep - returns the representative of this register
> + unsigned rep(unsigned Reg) {
> + unsigned Rep = r2rMap_[Reg];
> + if (Rep)
> + return r2rMap_[Reg] = rep(Rep);
> + return Reg;
> + }
> +
> + void printRegName(unsigned reg) const;
> + };
> +
> + } // End llvm namespace
> +
> + #endif
>
>
> Index: llvm/include/llvm/CodeGen/Passes.h
> diff -u llvm/include/llvm/CodeGen/Passes.h:1.26 llvm/include/llvm/
> CodeGen/Passes.h:1.27
> --- llvm/include/llvm/CodeGen/Passes.h:1.26 Tue May 22 12:14:46 2007
> +++ llvm/include/llvm/CodeGen/Passes.h Fri Jun 8 12:18:56 2007
> @@ -44,6 +44,11 @@
> ///
> extern const PassInfo *PHIEliminationID;
>
> + /// SimpleRegisterCoalescing pass. Aggressively coalesces every
> register
> + /// copy it can.
> + ///
> + extern const PassInfo *SimpleRegisterCoalescingID;
> +
> /// TwoAddressInstruction pass - This pass reduces two-address
> instructions to
> /// use two operands. This destroys SSA information but it is
> desired by
> /// register allocators.
>
>
> Index: llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h
> diff -u llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h:1.85 llvm/
> include/llvm/CodeGen/LiveIntervalAnalysis.h:1.86
> --- llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h:1.85 Mon May
> 14 16:10:05 2007
> +++ llvm/include/llvm/CodeGen/LiveIntervalAnalysis.h Fri Jun 8
> 12:18:56 2007
> @@ -44,7 +44,7 @@
> /// MBB2IdxMap - The index of the first instruction in the
> specified basic
> /// block.
> std::vector<unsigned> MBB2IdxMap;
> -
> +
> typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
> Mi2IndexMap mi2iMap_;
>
> @@ -54,31 +54,12 @@
> typedef std::map<unsigned, LiveInterval> Reg2IntervalMap;
> Reg2IntervalMap r2iMap_;
>
> - typedef IndexedMap<unsigned> Reg2RegMap;
> - Reg2RegMap r2rMap_;
> -
> BitVector allocatableRegs_;
> - DenseMap<const TargetRegisterClass*, BitVector>
> allocatableRCRegs_;
> -
> - /// JoinedLIs - Keep track which register intervals have been
> coalesced
> - /// with other intervals.
> - BitVector JoinedLIs;
>
> public:
> static char ID; // Pass identification, replacement for typeid
> LiveIntervals() : MachineFunctionPass((intptr_t)&ID) {}
>
> - struct CopyRec {
> - MachineInstr *MI;
> - unsigned SrcReg, DstReg;
> - };
> - CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg, unsigned
> DstReg) {
> - CopyRec R;
> - R.MI = MI;
> - R.SrcReg = SrcReg;
> - R.DstReg = DstReg;
> - return R;
> - }
> struct InstrSlots {
> enum {
> LOAD = 0,
> @@ -158,29 +139,31 @@
> "index does not correspond to an instruction");
> return i2miMap_[index];
> }
> -
> - std::vector<LiveInterval*> addIntervalsForSpills(const
> LiveInterval& i,
> - VirtRegMap& vrm,
> - int slot);
> +
> + // Interval creation
> +
> + LiveInterval &getOrCreateInterval(unsigned reg) {
> + Reg2IntervalMap::iterator I = r2iMap_.find(reg);
> + if (I == r2iMap_.end())
> + I = r2iMap_.insert(I, std::make_pair(reg, createInterval
> (reg)));
> + return I->second;
> + }
>
> /// CreateNewLiveInterval - Create a new live interval with
> the given live
> /// ranges. The new live interval will have an infinite spill
> weight.
> LiveInterval &CreateNewLiveInterval(const LiveInterval *LI,
> const
> std::vector<LiveRange> &LRs);
>
> - virtual void getAnalysisUsage(AnalysisUsage &AU) const;
> - virtual void releaseMemory();
> + std::vector<LiveInterval*> addIntervalsForSpills(const
> LiveInterval& i,
> + VirtRegMap& vrm,
> + int slot);
>
> - /// runOnMachineFunction - pass entry point
> - virtual bool runOnMachineFunction(MachineFunction&);
> + // Interval removal
>
> - /// print - Implement the dump method.
> - virtual void print(std::ostream &O, const Module* = 0) const;
> - void print(std::ostream *O, const Module* M = 0) const {
> - if (O) print(*O, M);
> + void removeInterval(unsigned Reg) {
> + r2iMap_.erase(Reg);
> }
>
> - private:
> /// isRemoved - returns true if the specified machine instr
> has been
> /// removed.
> bool isRemoved(MachineInstr* instr) const {
> @@ -198,40 +181,22 @@
> mi2iMap_.erase(mi2i);
> }
> }
> -
> - /// computeIntervals - Compute live intervals.
> - void computeIntervals();
>
> - /// joinIntervals - join compatible live intervals
> - void joinIntervals();
> + virtual void getAnalysisUsage(AnalysisUsage &AU) const;
> + virtual void releaseMemory();
>
> - /// CopyCoallesceInMBB - Coallsece copies in the specified
> MBB, putting
> - /// copies that cannot yet be coallesced into the "TryAgain"
> list.
> - void CopyCoallesceInMBB(MachineBasicBlock *MBB,
> - std::vector<CopyRec> *TryAgain, bool
> PhysOnly = false);
> -
> - /// JoinCopy - Attempt to join intervals corresponding to
> SrcReg/DstReg,
> - /// which are the src/dst of the copy instruction CopyMI.
> This returns true
> - /// if the copy was successfully coallesced away, or if it is
> never possible
> - /// to coallesce these this copy, due to register
> constraints. It returns
> - /// false if it is not currently possible to coallesce this
> interval, but
> - /// it may be possible if other things get coallesced.
> - bool JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned
> DstReg,
> - bool PhysOnly = false);
> -
> - /// JoinIntervals - Attempt to join these two intervals. On
> failure, this
> - /// returns false. Otherwise, if one of the intervals being
> joined is a
> - /// physreg, this method always canonicalizes DestInt to be
> it. The output
> - /// "SrcInt" will not have been modified, so we can use this
> information
> - /// below to update aliases.
> - bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS);
> -
> - /// SimpleJoin - Attempt to join the specified interval into
> this one. The
> - /// caller of this method must guarantee that the RHS only
> contains a single
> - /// value number and that the RHS is not defined by a copy
> from this
> - /// interval. This returns false if the intervals are not
> joinable, or it
> - /// joins them and returns true.
> - bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS);
> + /// runOnMachineFunction - pass entry point
> + virtual bool runOnMachineFunction(MachineFunction&);
> +
> + /// print - Implement the dump method.
> + virtual void print(std::ostream &O, const Module* = 0) const;
> + void print(std::ostream *O, const Module* M = 0) const {
> + if (O) print(*O, M);
> + }
> +
> + private:
> + /// computeIntervals - Compute live intervals.
> + void computeIntervals();
>
> /// handleRegisterDef - update intervals for a register def
> /// (calls handlePhysicalRegisterDef and
> @@ -260,57 +225,8 @@
> unsigned MIIdx,
> LiveInterval &interval, bool isAlias
> = false);
>
> - /// Return true if the two specified registers belong to
> different
> - /// register classes. The registers may be either phys or
> virt regs.
> - bool differingRegisterClasses(unsigned RegA, unsigned RegB)
> const;
> -
> -
> - bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
> - MachineInstr *CopyMI);
> -
> - /// lastRegisterUse - Returns the last use of the specific
> register between
> - /// cycles Start and End. It also returns the use operand by
> reference. It
> - /// returns NULL if there are no uses.
> - MachineInstr *lastRegisterUse(unsigned Start, unsigned End,
> unsigned Reg,
> - MachineOperand *&MOU);
> -
> - /// findDefOperand - Returns the MachineOperand that is a def
> of the specific
> - /// register. It returns NULL if the def is not found.
> - MachineOperand *findDefOperand(MachineInstr *MI, unsigned Reg);
> -
> - /// unsetRegisterKill - Unset IsKill property of all uses of
> the specific
> - /// register of the specific instruction.
> - void unsetRegisterKill(MachineInstr *MI, unsigned Reg);
> -
> - /// unsetRegisterKills - Unset IsKill property of all uses of
> specific register
> - /// between cycles Start and End.
> - void unsetRegisterKills(unsigned Start, unsigned End, unsigned
> Reg);
> -
> - /// hasRegisterDef - True if the instruction defines the
> specific register.
> - ///
> - bool hasRegisterDef(MachineInstr *MI, unsigned Reg);
> -
> static LiveInterval createInterval(unsigned Reg);
>
> - void removeInterval(unsigned Reg) {
> - r2iMap_.erase(Reg);
> - }
> -
> - LiveInterval &getOrCreateInterval(unsigned reg) {
> - Reg2IntervalMap::iterator I = r2iMap_.find(reg);
> - if (I == r2iMap_.end())
> - I = r2iMap_.insert(I, std::make_pair(reg, createInterval
> (reg)));
> - return I->second;
> - }
> -
> - /// rep - returns the representative of this register
> - unsigned rep(unsigned Reg) {
> - unsigned Rep = r2rMap_[Reg];
> - if (Rep)
> - return r2rMap_[Reg] = rep(Rep);
> - return Reg;
> - }
> -
> void printRegName(unsigned reg) const;
> };
>
>
>
>
> _______________________________________________
> llvm-commits mailing list
> llvm-commits@cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
