diff options
Diffstat (limited to 'llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp | 263 |
1 files changed, 161 insertions, 102 deletions
diff --git a/llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp b/llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp index 64023ecfad82..0e9c6e4fab9f 100644 --- a/llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp +++ b/llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp @@ -11,6 +11,7 @@ // //===------------------ #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h" +#include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/CodeGen/GlobalISel/Utils.h" #include "llvm/CodeGen/MachineFrameInfo.h" @@ -24,54 +25,50 @@ using namespace llvm; char llvm::GISelKnownBitsAnalysis::ID = 0; -INITIALIZE_PASS_BEGIN(GISelKnownBitsAnalysis, DEBUG_TYPE, - "Analysis for ComputingKnownBits", false, true) -INITIALIZE_PASS_END(GISelKnownBitsAnalysis, DEBUG_TYPE, - "Analysis for ComputingKnownBits", false, true) +INITIALIZE_PASS(GISelKnownBitsAnalysis, DEBUG_TYPE, + "Analysis for ComputingKnownBits", false, true) -GISelKnownBits::GISelKnownBits(MachineFunction &MF) +GISelKnownBits::GISelKnownBits(MachineFunction &MF, unsigned MaxDepth) : MF(MF), MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()), - DL(MF.getFunction().getParent()->getDataLayout()) {} + DL(MF.getFunction().getParent()->getDataLayout()), MaxDepth(MaxDepth) {} -Align GISelKnownBits::inferAlignmentForFrameIdx(int FrameIdx, int Offset, - const MachineFunction &MF) { - const MachineFrameInfo &MFI = MF.getFrameInfo(); - return commonAlignment(Align(MFI.getObjectAlignment(FrameIdx)), Offset); - // TODO: How to handle cases with Base + Offset? -} - -MaybeAlign GISelKnownBits::inferPtrAlignment(const MachineInstr &MI) { - if (MI.getOpcode() == TargetOpcode::G_FRAME_INDEX) { - int FrameIdx = MI.getOperand(1).getIndex(); - return inferAlignmentForFrameIdx(FrameIdx, 0, *MI.getMF()); +Align GISelKnownBits::computeKnownAlignment(Register R, unsigned Depth) { + const MachineInstr *MI = MRI.getVRegDef(R); + switch (MI->getOpcode()) { + case TargetOpcode::COPY: + return computeKnownAlignment(MI->getOperand(1).getReg(), Depth); + case TargetOpcode::G_FRAME_INDEX: { + int FrameIdx = MI->getOperand(1).getIndex(); + return MF.getFrameInfo().getObjectAlign(FrameIdx); + } + case TargetOpcode::G_INTRINSIC: + case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS: + default: + return TL.computeKnownAlignForTargetInstr(*this, R, MRI, Depth + 1); } - return None; -} - -void GISelKnownBits::computeKnownBitsForFrameIndex(Register R, KnownBits &Known, - const APInt &DemandedElts, - unsigned Depth) { - const MachineInstr &MI = *MRI.getVRegDef(R); - computeKnownBitsForAlignment(Known, inferPtrAlignment(MI)); -} - -void GISelKnownBits::computeKnownBitsForAlignment(KnownBits &Known, - MaybeAlign Alignment) { - if (Alignment) - // The low bits are known zero if the pointer is aligned. - Known.Zero.setLowBits(Log2(Alignment)); } KnownBits GISelKnownBits::getKnownBits(MachineInstr &MI) { + assert(MI.getNumExplicitDefs() == 1 && + "expected single return generic instruction"); return getKnownBits(MI.getOperand(0).getReg()); } KnownBits GISelKnownBits::getKnownBits(Register R) { - KnownBits Known; - LLT Ty = MRI.getType(R); + const LLT Ty = MRI.getType(R); APInt DemandedElts = Ty.isVector() ? APInt::getAllOnesValue(Ty.getNumElements()) : APInt(1, 1); + return getKnownBits(R, DemandedElts); +} + +KnownBits GISelKnownBits::getKnownBits(Register R, const APInt &DemandedElts, + unsigned Depth) { + // For now, we only maintain the cache during one request. + assert(ComputeKnownBitsCache.empty() && "Cache should have been cleared"); + + KnownBits Known; computeKnownBitsImpl(R, Known, DemandedElts); + ComputeKnownBitsCache.clear(); return Known; } @@ -87,6 +84,17 @@ APInt GISelKnownBits::getKnownZeroes(Register R) { APInt GISelKnownBits::getKnownOnes(Register R) { return getKnownBits(R).One; } +LLVM_ATTRIBUTE_UNUSED static void +dumpResult(const MachineInstr &MI, const KnownBits &Known, unsigned Depth) { + dbgs() << "[" << Depth << "] Compute known bits: " << MI << "[" << Depth + << "] Computed for: " << MI << "[" << Depth << "] Known: 0x" + << (Known.Zero | Known.One).toString(16, false) << "\n" + << "[" << Depth << "] Zero: 0x" << Known.Zero.toString(16, false) + << "\n" + << "[" << Depth << "] One: 0x" << Known.One.toString(16, false) + << "\n"; +} + void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, const APInt &DemandedElts, unsigned Depth) { @@ -104,12 +112,28 @@ void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, } unsigned BitWidth = DstTy.getSizeInBits(); + auto CacheEntry = ComputeKnownBitsCache.find(R); + if (CacheEntry != ComputeKnownBitsCache.end()) { + Known = CacheEntry->second; + LLVM_DEBUG(dbgs() << "Cache hit at "); + LLVM_DEBUG(dumpResult(MI, Known, Depth)); + assert(Known.getBitWidth() == BitWidth && "Cache entry size doesn't match"); + return; + } Known = KnownBits(BitWidth); // Don't know anything if (DstTy.isVector()) return; // TODO: Handle vectors. - if (Depth == getMaxDepth()) + // Depth may get bigger than max depth if it gets passed to a different + // GISelKnownBits object. + // This may happen when say a generic part uses a GISelKnownBits object + // with some max depth, but then we hit TL.computeKnownBitsForTargetInstr + // which creates a new GISelKnownBits object with a different and smaller + // depth. If we just check for equality, we would never exit if the depth + // that is passed down to the target specific GISelKnownBits object is + // already bigger than its max depth. + if (Depth >= getMaxDepth()) return; if (!DemandedElts) @@ -122,20 +146,53 @@ void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, TL.computeKnownBitsForTargetInstr(*this, R, Known, DemandedElts, MRI, Depth); break; - case TargetOpcode::COPY: { - MachineOperand Dst = MI.getOperand(0); - MachineOperand Src = MI.getOperand(1); - // Look through trivial copies but don't look through trivial copies of the - // form `%1:(s32) = OP %0:gpr32` known-bits analysis is currently unable to - // determine the bit width of a register class. - // - // We can't use NoSubRegister by name as it's defined by each target but - // it's always defined to be 0 by tablegen. - if (Dst.getSubReg() == 0 /*NoSubRegister*/ && Src.getReg().isVirtual() && - Src.getSubReg() == 0 /*NoSubRegister*/ && - MRI.getType(Src.getReg()).isValid()) { - // Don't increment Depth for this one since we didn't do any work. - computeKnownBitsImpl(Src.getReg(), Known, DemandedElts, Depth); + case TargetOpcode::COPY: + case TargetOpcode::G_PHI: + case TargetOpcode::PHI: { + Known.One = APInt::getAllOnesValue(BitWidth); + Known.Zero = APInt::getAllOnesValue(BitWidth); + // Destination registers should not have subregisters at this + // point of the pipeline, otherwise the main live-range will be + // defined more than once, which is against SSA. + assert(MI.getOperand(0).getSubReg() == 0 && "Is this code in SSA?"); + // Record in the cache that we know nothing for MI. + // This will get updated later and in the meantime, if we reach that + // phi again, because of a loop, we will cut the search thanks to this + // cache entry. + // We could actually build up more information on the phi by not cutting + // the search, but that additional information is more a side effect + // than an intended choice. + // Therefore, for now, save on compile time until we derive a proper way + // to derive known bits for PHIs within loops. + ComputeKnownBitsCache[R] = KnownBits(BitWidth); + // PHI's operand are a mix of registers and basic blocks interleaved. + // We only care about the register ones. + for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) { + const MachineOperand &Src = MI.getOperand(Idx); + Register SrcReg = Src.getReg(); + // Look through trivial copies and phis but don't look through trivial + // copies or phis of the form `%1:(s32) = OP %0:gpr32`, known-bits + // analysis is currently unable to determine the bit width of a + // register class. + // + // We can't use NoSubRegister by name as it's defined by each target but + // it's always defined to be 0 by tablegen. + if (SrcReg.isVirtual() && Src.getSubReg() == 0 /*NoSubRegister*/ && + MRI.getType(SrcReg).isValid()) { + // For COPYs we don't do anything, don't increase the depth. + computeKnownBitsImpl(SrcReg, Known2, DemandedElts, + Depth + (Opcode != TargetOpcode::COPY)); + Known.One &= Known2.One; + Known.Zero &= Known2.Zero; + // If we reach a point where we don't know anything + // just stop looking through the operands. + if (Known.One == 0 && Known.Zero == 0) + break; + } else { + // We know nothing. + Known = KnownBits(BitWidth); + break; + } } break; } @@ -148,22 +205,17 @@ void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, break; } case TargetOpcode::G_FRAME_INDEX: { - computeKnownBitsForFrameIndex(R, Known, DemandedElts); + int FrameIdx = MI.getOperand(1).getIndex(); + TL.computeKnownBitsForFrameIndex(FrameIdx, Known, MF); break; } case TargetOpcode::G_SUB: { - // If low bits are known to be zero in both operands, then we know they are - // going to be 0 in the result. Both addition and complement operations - // preserve the low zero bits. - computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts, + computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts, Depth + 1); - unsigned KnownZeroLow = Known2.countMinTrailingZeros(); - if (KnownZeroLow == 0) - break; computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts, Depth + 1); - KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros()); - Known.Zero.setLowBits(KnownZeroLow); + Known = KnownBits::computeForAddSub(/*Add*/ false, /*NSW*/ false, Known, + Known2); break; } case TargetOpcode::G_XOR: { @@ -172,11 +224,7 @@ void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts, Depth + 1); - // Output known-0 bits are known if clear or set in both the LHS & RHS. - APInt KnownZeroOut = (Known.Zero & Known2.Zero) | (Known.One & Known2.One); - // Output known-1 are known to be set if set in only one of the LHS, RHS. - Known.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero); - Known.Zero = KnownZeroOut; + Known ^= Known2; break; } case TargetOpcode::G_PTR_ADD: { @@ -187,24 +235,12 @@ void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, LLVM_FALLTHROUGH; } case TargetOpcode::G_ADD: { - // Output known-0 bits are known if clear or set in both the low clear bits - // common to both LHS & RHS. For example, 8+(X<<3) is known to have the - // low 3 bits clear. - // Output known-0 bits are also known if the top bits of each input are - // known to be clear. For example, if one input has the top 10 bits clear - // and the other has the top 8 bits clear, we know the top 7 bits of the - // output must be clear. - computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts, + computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts, Depth + 1); - unsigned KnownZeroHigh = Known2.countMinLeadingZeros(); - unsigned KnownZeroLow = Known2.countMinTrailingZeros(); computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts, Depth + 1); - KnownZeroHigh = std::min(KnownZeroHigh, Known2.countMinLeadingZeros()); - KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros()); - Known.Zero.setLowBits(KnownZeroLow); - if (KnownZeroHigh > 1) - Known.Zero.setHighBits(KnownZeroHigh - 1); + Known = + KnownBits::computeForAddSub(/*Add*/ true, /*NSW*/ false, Known, Known2); break; } case TargetOpcode::G_AND: { @@ -214,10 +250,7 @@ void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts, Depth + 1); - // Output known-1 bits are only known if set in both the LHS & RHS. - Known.One &= Known2.One; - // Output known-0 are known to be clear if zero in either the LHS | RHS. - Known.Zero |= Known2.Zero; + Known &= Known2; break; } case TargetOpcode::G_OR: { @@ -227,10 +260,7 @@ void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts, Depth + 1); - // Output known-0 bits are only known if clear in both the LHS & RHS. - Known.Zero &= Known2.Zero; - // Output known-1 are known to be set if set in either the LHS | RHS. - Known.One |= Known2.One; + Known |= Known2; break; } case TargetOpcode::G_MUL: { @@ -287,7 +317,7 @@ void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, case TargetOpcode::G_ANYEXT: { computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts, Depth + 1); - Known = Known.zext(BitWidth, true /* ExtendedBitsAreKnownZero */); + Known = Known.zext(BitWidth); break; } case TargetOpcode::G_LOAD: { @@ -353,9 +383,9 @@ void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, ? DL.getIndexSizeInBits(SrcTy.getAddressSpace()) : SrcTy.getSizeInBits(); assert(SrcBitWidth && "SrcBitWidth can't be zero"); - Known = Known.zextOrTrunc(SrcBitWidth, true); + Known = Known.zextOrTrunc(SrcBitWidth); computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1); - Known = Known.zextOrTrunc(BitWidth, true); + Known = Known.zextOrTrunc(BitWidth); if (BitWidth > SrcBitWidth) Known.Zero.setBitsFrom(SrcBitWidth); break; @@ -363,14 +393,10 @@ void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known, } assert(!Known.hasConflict() && "Bits known to be one AND zero?"); - LLVM_DEBUG(dbgs() << "[" << Depth << "] Compute known bits: " << MI << "[" - << Depth << "] Computed for: " << MI << "[" << Depth - << "] Known: 0x" - << (Known.Zero | Known.One).toString(16, false) << "\n" - << "[" << Depth << "] Zero: 0x" - << Known.Zero.toString(16, false) << "\n" - << "[" << Depth << "] One: 0x" - << Known.One.toString(16, false) << "\n"); + LLVM_DEBUG(dumpResult(MI, Known, Depth)); + + // Update the cache. + ComputeKnownBitsCache[R] = Known; } unsigned GISelKnownBits::computeNumSignBits(Register R, @@ -389,6 +415,7 @@ unsigned GISelKnownBits::computeNumSignBits(Register R, return 1; // No demanded elts, better to assume we don't know anything. LLT DstTy = MRI.getType(R); + const unsigned TyBits = DstTy.getScalarSizeInBits(); // Handle the case where this is called on a register that does not have a // type constraint. This is unlikely to occur except by looking through copies @@ -397,6 +424,7 @@ unsigned GISelKnownBits::computeNumSignBits(Register R, if (!DstTy.isValid()) return 1; + unsigned FirstAnswer = 1; switch (Opcode) { case TargetOpcode::COPY: { MachineOperand &Src = MI.getOperand(1); @@ -414,6 +442,16 @@ unsigned GISelKnownBits::computeNumSignBits(Register R, unsigned Tmp = DstTy.getScalarSizeInBits() - SrcTy.getScalarSizeInBits(); return computeNumSignBits(Src, DemandedElts, Depth + 1) + Tmp; } + case TargetOpcode::G_SEXTLOAD: { + Register Dst = MI.getOperand(0).getReg(); + LLT Ty = MRI.getType(Dst); + // TODO: add vector support + if (Ty.isVector()) + break; + if (MI.hasOneMemOperand()) + return Ty.getSizeInBits() - (*MI.memoperands_begin())->getSizeInBits(); + break; + } case TargetOpcode::G_TRUNC: { Register Src = MI.getOperand(1).getReg(); LLT SrcTy = MRI.getType(Src); @@ -426,13 +464,34 @@ unsigned GISelKnownBits::computeNumSignBits(Register R, return NumSrcSignBits - (NumSrcBits - DstTyBits); break; } - default: + case TargetOpcode::G_INTRINSIC: + case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS: + default: { + unsigned NumBits = + TL.computeNumSignBitsForTargetInstr(*this, R, DemandedElts, MRI, Depth); + if (NumBits > 1) + FirstAnswer = std::max(FirstAnswer, NumBits); break; } + } + + // Finally, if we can prove that the top bits of the result are 0's or 1's, + // use this information. + KnownBits Known = getKnownBits(R, DemandedElts, Depth); + APInt Mask; + if (Known.isNonNegative()) { // sign bit is 0 + Mask = Known.Zero; + } else if (Known.isNegative()) { // sign bit is 1; + Mask = Known.One; + } else { + // Nothing known. + return FirstAnswer; + } - // TODO: Handle target instructions - // TODO: Fall back to known bits - return 1; + // Okay, we know that the sign bit in Mask is set. Use CLO to determine + // the number of identical bits in the top of the input value. + Mask <<= Mask.getBitWidth() - TyBits; + return std::max(FirstAnswer, Mask.countLeadingOnes()); } unsigned GISelKnownBits::computeNumSignBits(Register R, unsigned Depth) { |