From 8ca814c4e0a39e1fcac023f0fb014917da07a796 Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Thu, 24 Feb 2011 10:00:25 +0000 Subject: [PATCH] Merge information about the number of zero, one, and sign bits of live-out registers at phis. This enables us to eliminate a lot of pointless zexts during the DAGCombine phase. This fixes . git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126380 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/FunctionLoweringInfo.h | 11 ++ .../SelectionDAG/FunctionLoweringInfo.cpp | 116 ++++++++++++++++++ lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 7 +- test/CodeGen/X86/phi-constants.ll | 35 ++++++ 4 files changed, 168 insertions(+), 1 deletion(-) create mode 100644 test/CodeGen/X86/phi-constants.ll diff --git a/include/llvm/CodeGen/FunctionLoweringInfo.h b/include/llvm/CodeGen/FunctionLoweringInfo.h index 2d44a8beed4..b41f30d8251 100644 --- a/include/llvm/CodeGen/FunctionLoweringInfo.h +++ b/include/llvm/CodeGen/FunctionLoweringInfo.h @@ -159,6 +159,13 @@ public: return LOI; } + /// GetLiveOutRegInfo - Gets LiveOutInfo for a register, returning NULL if the + /// register is a PHI destination and the PHI's LiveOutInfo is not valid. If + /// the register's LiveOutInfo is for a smaller bit width, it is extended to + /// the larger bit width by zero extension. The bit width must be no smaller + /// than the LiveOutInfo's existing bit width. + const LiveOutInfo *GetLiveOutRegInfo(unsigned Reg, unsigned BitWidth); + /// AddLiveOutRegInfo - Adds LiveOutInfo for a register. void AddLiveOutRegInfo(unsigned Reg, unsigned NumSignBits, const APInt &KnownZero, const APInt &KnownOne) { @@ -173,6 +180,10 @@ public: LOI.KnownZero = KnownZero; } + /// ComputePHILiveOutRegInfo - Compute LiveOutInfo for a PHI's destination + /// register based on the LiveOutInfo of its operands. + void ComputePHILiveOutRegInfo(const PHINode*); + /// InvalidatePHILiveOutRegInfo - Invalidates a PHI's LiveOutInfo, to be /// called when a block is visited before all of its predecessors. void InvalidatePHILiveOutRegInfo(const PHINode *PN) { diff --git a/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp b/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp index c55cf85a6d2..82b6c4022d7 100644 --- a/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp +++ b/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp @@ -255,6 +255,122 @@ unsigned FunctionLoweringInfo::CreateRegs(const Type *Ty) { return FirstReg; } +/// GetLiveOutRegInfo - Gets LiveOutInfo for a register, returning NULL if the +/// register is a PHI destination and the PHI's LiveOutInfo is not valid. If +/// the register's LiveOutInfo is for a smaller bit width, it is extended to +/// the larger bit width by zero extension. The bit width must be no smaller +/// than the LiveOutInfo's existing bit width. +const FunctionLoweringInfo::LiveOutInfo * +FunctionLoweringInfo::GetLiveOutRegInfo(unsigned Reg, unsigned BitWidth) { + if (!LiveOutRegInfo.inBounds(Reg)) + return NULL; + + LiveOutInfo *LOI = &LiveOutRegInfo[Reg]; + if (!LOI->IsValid) + return NULL; + + if (BitWidth >= LOI->KnownZero.getBitWidth()) { + LOI->KnownZero = LOI->KnownZero.zextOrTrunc(BitWidth); + LOI->KnownOne = LOI->KnownOne.zextOrTrunc(BitWidth); + } + + return LOI; +} + +/// ComputePHILiveOutRegInfo - Compute LiveOutInfo for a PHI's destination +/// register based on the LiveOutInfo of its operands. +void FunctionLoweringInfo::ComputePHILiveOutRegInfo(const PHINode *PN) { + const Type *Ty = PN->getType(); + if (!Ty->isIntegerTy() || Ty->isVectorTy()) + return; + + SmallVector ValueVTs; + ComputeValueVTs(TLI, Ty, ValueVTs); + assert(ValueVTs.size() == 1 && + "PHIs with non-vector integer types should have a single VT."); + EVT IntVT = ValueVTs[0]; + + if (TLI.getNumRegisters(PN->getContext(), IntVT) != 1) + return; + IntVT = TLI.getTypeToTransformTo(PN->getContext(), IntVT); + unsigned BitWidth = IntVT.getSizeInBits(); + + unsigned DestReg = ValueMap[PN]; + if (!TargetRegisterInfo::isVirtualRegister(DestReg)) + return; + LiveOutRegInfo.grow(DestReg); + LiveOutInfo &DestLOI = LiveOutRegInfo[DestReg]; + + Value *V = PN->getIncomingValue(0); + if (isa(V) || isa(V)) { + DestLOI.NumSignBits = 1; + APInt Zero(BitWidth, 0); + DestLOI.KnownZero = Zero; + DestLOI.KnownOne = Zero; + return; + } + + if (ConstantInt *CI = dyn_cast(V)) { + APInt Val = CI->getValue().zextOrTrunc(BitWidth); + DestLOI.NumSignBits = Val.getNumSignBits(); + DestLOI.KnownZero = ~Val; + DestLOI.KnownOne = Val; + } else { + assert(ValueMap.count(V) && "V should have been placed in ValueMap when its" + "CopyToReg node was created."); + unsigned SrcReg = ValueMap[V]; + if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) { + DestLOI.IsValid = false; + return; + } + const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth); + if (!SrcLOI) { + DestLOI.IsValid = false; + return; + } + DestLOI = *SrcLOI; + } + + assert(DestLOI.KnownZero.getBitWidth() == BitWidth && + DestLOI.KnownOne.getBitWidth() == BitWidth && + "Masks should have the same bit width as the type."); + + for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { + Value *V = PN->getIncomingValue(i); + if (isa(V) || isa(V)) { + DestLOI.NumSignBits = 1; + APInt Zero(BitWidth, 0); + DestLOI.KnownZero = Zero; + DestLOI.KnownOne = Zero; + return; + } + + if (ConstantInt *CI = dyn_cast(V)) { + APInt Val = CI->getValue().zextOrTrunc(BitWidth); + DestLOI.NumSignBits = std::min(DestLOI.NumSignBits, Val.getNumSignBits()); + DestLOI.KnownZero &= ~Val; + DestLOI.KnownOne &= Val; + continue; + } + + assert(ValueMap.count(V) && "V should have been placed in ValueMap when " + "its CopyToReg node was created."); + unsigned SrcReg = ValueMap[V]; + if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) { + DestLOI.IsValid = false; + return; + } + const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth); + if (!SrcLOI) { + DestLOI.IsValid = false; + return; + } + DestLOI.NumSignBits = std::min(DestLOI.NumSignBits, SrcLOI->NumSignBits); + DestLOI.KnownZero &= SrcLOI->KnownZero; + DestLOI.KnownOne &= SrcLOI->KnownOne; + } +} + /// setByValArgumentFrameIndex - Record frame index for the byval /// argument. This overrides previous frame index entry for this argument, /// if any. diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index d5400630835..68ba966d268 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -842,7 +842,12 @@ void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { } } - if (!AllPredsVisited) { + if (AllPredsVisited) { + for (BasicBlock::const_iterator I = LLVMBB->begin(), E = LLVMBB->end(); + I != E && isa(I); ++I) { + FuncInfo->ComputePHILiveOutRegInfo(cast(I)); + } + } else { for (BasicBlock::const_iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E && isa(I); ++I) { FuncInfo->InvalidatePHILiveOutRegInfo(cast(I)); diff --git a/test/CodeGen/X86/phi-constants.ll b/test/CodeGen/X86/phi-constants.ll new file mode 100644 index 00000000000..da9652f7340 --- /dev/null +++ b/test/CodeGen/X86/phi-constants.ll @@ -0,0 +1,35 @@ +; RUN: llc < %s -march=x86-64 | FileCheck %s + +%"class.std::bitset" = type { [8 x i8] } + +define zeroext i1 @_Z3fooPjmS_mRSt6bitsetILm32EE(i32* nocapture %a, i64 %asize, i32* nocapture %b, i64 %bsize, %"class.std::bitset"* %bits) nounwind readonly ssp noredzone { +entry: + %tmp.i.i.i.i = bitcast %"class.std::bitset"* %bits to i64* + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %conv = zext i32 %0 to i64 + %cmp = icmp eq i64 %conv, %bsize + br i1 %cmp, label %return, label %for.body + +for.body: ; preds = %for.cond + %arrayidx = getelementptr inbounds i32* %b, i64 %conv + %tmp5 = load i32* %arrayidx, align 4 + %conv6 = zext i32 %tmp5 to i64 + %rem.i.i.i.i = and i64 %conv6, 63 + %tmp3.i = load i64* %tmp.i.i.i.i, align 8 + %shl.i.i = shl i64 1, %rem.i.i.i.i + %and.i = and i64 %shl.i.i, %tmp3.i + %cmp.i = icmp eq i64 %and.i, 0 + br i1 %cmp.i, label %for.inc, label %return + +for.inc: ; preds = %for.body + %inc = add i32 %0, 1 + br label %for.cond + +return: ; preds = %for.body, %for.cond +; CHECK-NOT: and + %retval.0 = phi i1 [ true, %for.body ], [ false, %for.cond ] + ret i1 %retval.0 +} -- 2.34.1