From 92efda7e9183ae16bde7a3ad96b682e779d89cf3 Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Tue, 22 Feb 2011 00:46:27 +0000 Subject: 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@126170 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/FunctionLoweringInfo.h | 20 +++++++++- lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp | 8 +++- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 8 +++- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 45 ++++++++++++++++++++--- test/CodeGen/X86/phi-constants.ll | 35 ++++++++++++++++++ 5 files changed, 107 insertions(+), 9 deletions(-) create mode 100644 test/CodeGen/X86/phi-constants.ll diff --git a/include/llvm/CodeGen/FunctionLoweringInfo.h b/include/llvm/CodeGen/FunctionLoweringInfo.h index 27631b7..6bc10df 100644 --- a/include/llvm/CodeGen/FunctionLoweringInfo.h +++ b/include/llvm/CodeGen/FunctionLoweringInfo.h @@ -101,14 +101,30 @@ public: #endif struct LiveOutInfo { - unsigned NumSignBits; + unsigned NumSignBits : 31; + bool IsValid : 1; APInt KnownOne, KnownZero; - LiveOutInfo() : NumSignBits(0), KnownOne(1, 0), KnownZero(1, 0) {} + LiveOutInfo() : NumSignBits(0), IsValid(false), KnownOne(1, 0), + KnownZero(1, 0) {} }; /// LiveOutRegInfo - Information about live out vregs. IndexedMap LiveOutRegInfo; + /// VisitedBBs - Basic blocks that have been visited by reverse postorder. + DenseSet VisitedBBs; + + /// AllPredsVisited - Tracks whether all predecessors of the current basic + /// block have already been visited. + bool AllPredsVisited; + + /// PHIDestRegs - Virtual registers that are the destinations of PHIs. + DenseSet PHIDestRegs; + + /// PHISrcToDestMap - Maps the virtual register defining a PHI's source to the + /// virtual register defining its destination. + DenseMap PHISrcToDestMap; + /// PHINodesToUpdate - A list of phi instructions whose operand list will /// be updated after processing the current basic block. /// TODO: This isn't per-function state, it's per-basic-block state. But diff --git a/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp b/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp index 98582ba..8adaf05 100644 --- a/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp +++ b/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp @@ -127,10 +127,13 @@ void FunctionLoweringInfo::set(const Function &fn, MachineFunction &mf) { for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) { // Mark values used outside their block as exported, by allocating // a virtual register for them. - if (isUsedOutsideOfDefiningBlock(I)) + if (!EnableFastISel && isa(I)) { + PHIDestRegs.insert(InitializeRegForValue(I)); + } else if (isUsedOutsideOfDefiningBlock(I)) { if (!isa(I) || !StaticAllocaMap.count(cast(I))) InitializeRegForValue(I); + } // Collect llvm.dbg.declare information. This is done now instead of // during the initial isel pass through the IR so that it is done @@ -219,6 +222,9 @@ void FunctionLoweringInfo::clear() { CatchInfoFound.clear(); #endif LiveOutRegInfo.clear(); + VisitedBBs.clear(); + PHIDestRegs.clear(); + PHISrcToDestMap.clear(); ArgDbgValues.clear(); ByValArgFrameIndexMap.clear(); RegFixups.clear(); diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 452f561..c1be3e9 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -644,7 +644,10 @@ SDValue RegsForValue::getCopyFromRegs(SelectionDAG &DAG, !RegisterVT.isInteger() || RegisterVT.isVector() || !FuncInfo.LiveOutRegInfo.inBounds(Regs[Part+i])) continue; - + + if (FuncInfo.PHIDestRegs.count(Regs[Part+i]) && !FuncInfo.AllPredsVisited) + continue; + const FunctionLoweringInfo::LiveOutInfo &LOI = FuncInfo.LiveOutRegInfo[Regs[Part+i]]; @@ -6466,6 +6469,9 @@ SelectionDAGBuilder::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) { } } + if (!EnableFastISel) + FuncInfo.PHISrcToDestMap[Reg] = FuncInfo.ValueMap[PN]; + // Remember that this register needs to added to the machine PHI node as // the input for this MBB. SmallVector ValueVTs; diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index bbc62d8..450757f 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -471,6 +471,13 @@ void SelectionDAGISel::ComputeLiveOutVRegInfo() { if (!TargetRegisterInfo::isVirtualRegister(DestReg)) continue; + bool IsPHI = false; + DenseMap::const_iterator It = FuncInfo->PHISrcToDestMap.find(DestReg); + if (It != FuncInfo->PHISrcToDestMap.end()) { + IsPHI = true; + DestReg = It->second; + } + // Ignore non-scalar or non-integer values. SDValue Src = N->getOperand(2); EVT SrcVT = Src.getValueType(); @@ -482,14 +489,27 @@ void SelectionDAGISel::ComputeLiveOutVRegInfo() { CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne); // Only install this information if it tells us something. - if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) { - FuncInfo->LiveOutRegInfo.grow(DestReg); + if (!IsPHI && NumSignBits == 1 && KnownZero == 0 && KnownOne == 0) + continue; + + FuncInfo->LiveOutRegInfo.grow(DestReg); + FunctionLoweringInfo::LiveOutInfo &LOI = FuncInfo->LiveOutRegInfo[DestReg]; + + // If this is a PHI and there is existing information, merge it with the + // information from this block. + if (IsPHI && LOI.IsValid) { FunctionLoweringInfo::LiveOutInfo &LOI = FuncInfo->LiveOutRegInfo[DestReg]; - LOI.NumSignBits = NumSignBits; - LOI.KnownOne = KnownOne; - LOI.KnownZero = KnownZero; + LOI.NumSignBits = std::min(LOI.NumSignBits, NumSignBits); + LOI.KnownOne &= KnownOne; + LOI.KnownZero &= KnownZero; + continue; } + + LOI.NumSignBits = NumSignBits; + LOI.KnownOne = KnownOne; + LOI.KnownZero = KnownZero; + LOI.IsValid = true; } while (!Worklist.empty()); } @@ -840,6 +860,21 @@ void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { #ifndef NDEBUG CheckLineNumbers(LLVMBB); #endif + + if (EnableFastISel) { + FuncInfo->AllPredsVisited = false; + } else { + FuncInfo->AllPredsVisited = true; + for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB); + PI != PE; ++PI) { + if (!FuncInfo->VisitedBBs.count(*PI)) { + FuncInfo->AllPredsVisited = false; + break; + } + } + FuncInfo->VisitedBBs.insert(LLVMBB); + } + FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB]; FuncInfo->InsertPt = FuncInfo->MBB->getFirstNonPHI(); diff --git a/test/CodeGen/X86/phi-constants.ll b/test/CodeGen/X86/phi-constants.ll new file mode 100644 index 0000000..da9652f --- /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 +} -- cgit v1.1