From 6d69ba8a6901c69d78488cbc41f8dbf080618fde Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Fri, 25 Jul 2008 00:02:30 +0000 Subject: [PATCH] Enable rematerialization of constants using AliasAnalysis::pointsToConstantMemory, and knowledge of PseudoSourceValues. This unfortunately isn't sufficient to allow constants to be rematerialized in PIC mode -- the extra indirection is a complication. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54000 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveIntervalAnalysis.h | 2 + include/llvm/CodeGen/MachineRegisterInfo.h | 8 ++ include/llvm/CodeGen/PseudoSourceValue.h | 6 ++ lib/CodeGen/LiveIntervalAnalysis.cpp | 104 +++++++++++++++++--- lib/CodeGen/PseudoSourceValue.cpp | 20 ++++ test/CodeGen/X86/remat-constant.ll | 15 +++ 6 files changed, 140 insertions(+), 15 deletions(-) create mode 100644 test/CodeGen/X86/remat-constant.ll diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index ebbcf63b700..c88c1ec6965 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -32,6 +32,7 @@ namespace llvm { + class AliasAnalysis; class LiveVariables; class MachineLoopInfo; class TargetRegisterInfo; @@ -61,6 +62,7 @@ namespace llvm { const TargetMachine* tm_; const TargetRegisterInfo* tri_; const TargetInstrInfo* tii_; + AliasAnalysis *aa_; LiveVariables* lv_; /// Special pool allocator for VNInfo's (LiveInterval val#). diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h index bfa6d1ccd0a..b851fdf66da 100644 --- a/include/llvm/CodeGen/MachineRegisterInfo.h +++ b/include/llvm/CodeGen/MachineRegisterInfo.h @@ -206,6 +206,14 @@ public: liveout_iterator liveout_begin() const { return LiveOuts.begin(); } liveout_iterator liveout_end() const { return LiveOuts.end(); } bool liveout_empty() const { return LiveOuts.empty(); } + + bool isLiveIn(unsigned Reg) const { + for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I) + if (I->first == Reg || I->second == Reg) + return true; + return false; + } + private: void HandleVRegListReallocation(); diff --git a/include/llvm/CodeGen/PseudoSourceValue.h b/include/llvm/CodeGen/PseudoSourceValue.h index 95ae1d43ab3..115e565b6b6 100644 --- a/include/llvm/CodeGen/PseudoSourceValue.h +++ b/include/llvm/CodeGen/PseudoSourceValue.h @@ -17,6 +17,8 @@ #include "llvm/Value.h" namespace llvm { + class MachineFrameInfo; + /// PseudoSourceValue - Special value supplied for machine level alias /// analysis. It indicates that the a memory access references the functions /// stack frame (e.g., a spill slot), below the stack frame (e.g., argument @@ -27,6 +29,10 @@ namespace llvm { virtual void print(std::ostream &OS) const; + /// isConstant - Test whether this PseudoSourceValue has a constant value. + /// + virtual bool isConstant(const MachineFrameInfo *) const; + /// classof - Methods for support type inquiry through isa, cast, and /// dyn_cast: /// diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 1f29055e2f7..adc1e207b50 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -19,12 +19,14 @@ #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "VirtRegMap.h" #include "llvm/Value.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" @@ -54,6 +56,8 @@ char LiveIntervals::ID = 0; static RegisterPass X("liveintervals", "Live Interval Analysis"); void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.addPreserved(); AU.addPreserved(); AU.addRequired(); AU.addPreservedID(MachineLoopInfoID); @@ -212,6 +216,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { tm_ = &fn.getTarget(); tri_ = tm_->getRegisterInfo(); tii_ = tm_->getInstrInfo(); + aa_ = &getAnalysis(); lv_ = &getAnalysis(); allocatableRegs_ = tri_->getAllocatableSet(fn); @@ -750,7 +755,9 @@ unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, assert(!RegOp && "Can't rematerialize instruction with multiple register operand!"); RegOp = MO.getReg(); +#ifndef NDEBUG break; +#endif } return RegOp; } @@ -773,7 +780,6 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, if (DisableReMat) return false; - isLoad = false; if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) return true; @@ -786,27 +792,95 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, // This is a load from fixed stack slot. It can be rematerialized. return true; - if (tii_->isTriviallyReMaterializable(MI)) { + // If the target-specific rules don't identify an instruction as + // being trivially rematerializable, use some target-independent + // rules. + if (!MI->getDesc().isRematerializable() || + !tii_->isTriviallyReMaterializable(MI)) { + + // If the instruction access memory but the memoperands have been lost, + // we can't analyze it. const TargetInstrDesc &TID = MI->getDesc(); - isLoad = TID.isSimpleLoad(); - - unsigned ImpUse = getReMatImplicitUse(li, MI); - if (ImpUse) { - const LiveInterval &ImpLi = getInterval(ImpUse); - for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), - re = mri_->use_end(); ri != re; ++ri) { - MachineInstr *UseMI = &*ri; - unsigned UseIdx = getInstructionIndex(UseMI); - if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) + if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty()) + return false; + + // Avoid instructions obviously unsafe for remat. + if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable()) + return false; + + // If the instruction accesses memory and the memory could be non-constant, + // assume the instruction is not rematerializable. + for (alist::const_iterator I = MI->memoperands_begin(), + E = MI->memoperands_end(); I != E; ++I) { + const MachineMemOperand &MMO = *I; + if (MMO.isVolatile() || MMO.isStore()) + return false; + const Value *V = MMO.getValue(); + if (!V) + return false; + if (const PseudoSourceValue *PSV = dyn_cast(V)) { + if (!PSV->isConstant(mf_->getFrameInfo())) + return false; + } else if (!aa_->pointsToConstantMemory(V)) + return false; + } + + // If any of the registers accessed are non-constant, conservatively assume + // the instruction is not rematerializable. + unsigned ImpUse = 0; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (MO.isReg()) { + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; - if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) + if (TargetRegisterInfo::isPhysicalRegister(Reg)) return false; + + // Only allow one def, and that in the first operand. + if (MO.isDef() != (i == 0)) + return false; + + // Only allow constant-valued registers. + bool IsLiveIn = mri_->isLiveIn(Reg); + MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg), + E = mri_->def_end(); + + // For the def, it should be the only def. + if (MO.isDef() && (next(I) != E || IsLiveIn)) + return false; + + if (MO.isUse()) { + // Only allow one use other register use, as that's all the + // remat mechanisms support currently. + if (Reg != li.reg) { + if (ImpUse == 0) + ImpUse = Reg; + else if (Reg != ImpUse) + return false; + } + // For uses, there should be only one associate def. + if (I != E && (next(I) != E || IsLiveIn)) + return false; + } } } - return true; } - return false; + unsigned ImpUse = getReMatImplicitUse(li, MI); + if (ImpUse) { + const LiveInterval &ImpLi = getInterval(ImpUse); + for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), + re = mri_->use_end(); ri != re; ++ri) { + MachineInstr *UseMI = &*ri; + unsigned UseIdx = getInstructionIndex(UseMI); + if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) + continue; + if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) + return false; + } + } + return true; } /// isReMaterializable - Returns true if every definition of MI of every diff --git a/lib/CodeGen/PseudoSourceValue.cpp b/lib/CodeGen/PseudoSourceValue.cpp index 27995547c60..bcf4ea8fb75 100644 --- a/lib/CodeGen/PseudoSourceValue.cpp +++ b/lib/CodeGen/PseudoSourceValue.cpp @@ -11,6 +11,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/DerivedTypes.h" #include "llvm/Support/Compiler.h" @@ -51,6 +52,9 @@ namespace llvm { const int FI; public: explicit FixedStackPseudoSourceValue(int fi) : FI(fi) {} + + virtual bool isConstant(const MachineFrameInfo *MFI) const; + virtual void print(std::ostream &OS) const { OS << "FixedStack" << FI; } @@ -64,4 +68,20 @@ namespace llvm { V = new FixedStackPseudoSourceValue(FI); return V; } + + bool PseudoSourceValue::isConstant(const MachineFrameInfo *) const { + if (this == getStack()) + return false; + if (this == getGOT() || + this == getConstantPool() || + this == getJumpTable()) + return true; + assert(0 && "Unknown PseudoSourceValue!"); + return false; + } + + bool + FixedStackPseudoSourceValue::isConstant(const MachineFrameInfo *MFI) const { + return MFI && MFI->isImmutableObjectIndex(FI); + } } diff --git a/test/CodeGen/X86/remat-constant.ll b/test/CodeGen/X86/remat-constant.ll new file mode 100644 index 00000000000..eb12c312e9b --- /dev/null +++ b/test/CodeGen/X86/remat-constant.ll @@ -0,0 +1,15 @@ +; RUN: llvm-as < %s | llc -march=x86-64 -relocation-model=static | grep xmm | count 2 + +declare void @bar() nounwind + +@a = external constant float + +declare void @qux(float %f) nounwind + +define void @foo() nounwind { + %f = load float* @a + call void @bar() + call void @qux(float %f) + call void @qux(float %f) + ret void +} -- 2.34.1