From 789162a30971c3071a6c9edff3bc32084410e9dc Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Mon, 11 Jan 2010 03:32:00 +0000 Subject: [PATCH] Remove the dead TD argument to CanEvaluateZExtd, and add a new BitsToClear result which allows us to start promoting expressions that end with a lshr-by-constant. This is conservatively correct and better than what we had before (see testcases) but still needs to be extended further. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@93144 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstCombineCasts.cpp | 71 +++++++++++++++---- test/Transforms/InstCombine/cast.ll | 25 ++++++- 2 files changed, 81 insertions(+), 15 deletions(-) diff --git a/lib/Transforms/InstCombine/InstCombineCasts.cpp b/lib/Transforms/InstCombine/InstCombineCasts.cpp index c4678868f1d..be0734c7a43 100644 --- a/lib/Transforms/InstCombine/InstCombineCasts.cpp +++ b/lib/Transforms/InstCombine/InstCombineCasts.cpp @@ -582,8 +582,23 @@ Instruction *InstCombiner::transformZExtICmp(ICmpInst *ICI, Instruction &CI, /// CanEvaluateZExtd - Determine if the specified value can be computed in the /// specified wider type and produce the same low bits. If not, return false. /// +/// If this function returns true, it can also return a non-zero number of bits +/// (in BitsToClear) which indicates that the value it computes is correct for +/// the zero extend, but that the additional BitsToClear bits need to be zero'd +/// out. For example, to promote something like: +/// +/// %B = trunc i64 %A to i32 +/// %C = lshr i32 %B, 8 +/// %E = zext i32 %C to i64 +/// +/// CanEvaluateZExtd for the 'lshr' will return true, and BitsToClear will be +/// set to 8 to indicate that the promoted value needs to have bits 24-31 +/// cleared in addition to bits 32-63. Since an 'and' will be generated to +/// clear the top bits anyway, doing this has no extra cost. +/// /// This function works on both vectors and scalars. -static bool CanEvaluateZExtd(Value *V, const Type *Ty, const TargetData *TD) { +static bool CanEvaluateZExtd(Value *V, const Type *Ty, unsigned &BitsToClear) { + BitsToClear = 0; if (isa(V)) return true; @@ -599,7 +614,7 @@ static bool CanEvaluateZExtd(Value *V, const Type *Ty, const TargetData *TD) { // require duplicating the instruction in general, which isn't profitable. if (!I->hasOneUse()) return false; - unsigned Opc = I->getOpcode(); + unsigned Opc = I->getOpcode(), Tmp; switch (Opc) { case Instruction::ZExt: // zext(zext(x)) -> zext(x). case Instruction::SExt: // zext(sext(x)) -> sext(x). @@ -612,23 +627,46 @@ static bool CanEvaluateZExtd(Value *V, const Type *Ty, const TargetData *TD) { case Instruction::Sub: case Instruction::Mul: case Instruction::Shl: - return CanEvaluateZExtd(I->getOperand(0), Ty, TD) && - CanEvaluateZExtd(I->getOperand(1), Ty, TD); + if (!CanEvaluateZExtd(I->getOperand(0), Ty, BitsToClear) || + !CanEvaluateZExtd(I->getOperand(1), Ty, Tmp)) + return false; + // These can all be promoted if neither operand has 'bits to clear'. + if (BitsToClear == 0 && Tmp == 0) + return true; - //case Instruction::LShr: + return false; + case Instruction::LShr: + // We can promote lshr(x, cst) if we can promote x. This requires the + // ultimate 'and' to clear out the high zero bits we're clearing out though. + if (ConstantInt *Amt = dyn_cast(I->getOperand(1))) { + if (!CanEvaluateZExtd(I->getOperand(0), Ty, BitsToClear)) + return false; + BitsToClear += Amt->getZExtValue(); + if (BitsToClear > V->getType()->getScalarSizeInBits()) + BitsToClear = V->getType()->getScalarSizeInBits(); + return true; + } + // Cannot promote variable LSHR. + return false; case Instruction::Select: - return CanEvaluateZExtd(I->getOperand(1), Ty, TD) && - CanEvaluateZExtd(I->getOperand(2), Ty, TD); + if (!CanEvaluateZExtd(I->getOperand(1), Ty, Tmp) || + !CanEvaluateZExtd(I->getOperand(2), Ty, BitsToClear) || + Tmp != BitsToClear) + return false; + return true; case Instruction::PHI: { // We can change a phi if we can change all operands. Note that we never // get into trouble with cyclic PHIs here because we only consider // instructions with a single use. PHINode *PN = cast(I); - if (!CanEvaluateZExtd(PN->getIncomingValue(0), Ty, TD)) return false; + if (!CanEvaluateZExtd(PN->getIncomingValue(0), Ty, BitsToClear)) + return false; for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) - if (!CanEvaluateZExtd(PN->getIncomingValue(i), Ty, TD)) return false; + if (!CanEvaluateZExtd(PN->getIncomingValue(i), Ty, Tmp) || + Tmp != BitsToClear) + return false; return true; } default: @@ -659,25 +697,30 @@ Instruction *InstCombiner::visitZExt(ZExtInst &CI) { // type. Only do this if the dest type is a simple type, don't convert the // expression tree to something weird like i93 unless the source is also // strange. + unsigned BitsToClear; if ((isa(DestTy) || ShouldChangeType(SrcTy, DestTy)) && - CanEvaluateZExtd(Src, DestTy, TD)) { + CanEvaluateZExtd(Src, DestTy, BitsToClear)) { + assert(BitsToClear < SrcTy->getScalarSizeInBits() && + "Unreasonable BitsToClear"); + // Okay, we can transform this! Insert the new expression now. DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type" " to avoid zero extend: " << CI); Value *Res = EvaluateInDifferentType(Src, DestTy, false); assert(Res->getType() == DestTy); + uint32_t SrcBitsKept = SrcTy->getScalarSizeInBits()-BitsToClear; + uint32_t DestBitSize = DestTy->getScalarSizeInBits(); + // If the high bits are already filled with zeros, just replace this // cast with the result. - uint32_t SrcBitSize = SrcTy->getScalarSizeInBits(); - uint32_t DestBitSize = DestTy->getScalarSizeInBits(); if (MaskedValueIsZero(Res, APInt::getHighBitsSet(DestBitSize, - DestBitSize-SrcBitSize))) + DestBitSize-SrcBitsKept))) return ReplaceInstUsesWith(CI, Res); // We need to emit an AND to clear the high bits. Constant *C = ConstantInt::get(Res->getType(), - APInt::getLowBitsSet(DestBitSize, SrcBitSize)); + APInt::getLowBitsSet(DestBitSize, SrcBitsKept)); return BinaryOperator::CreateAnd(Res, C); } diff --git a/test/Transforms/InstCombine/cast.ll b/test/Transforms/InstCombine/cast.ll index d624f342b9b..3bfed2af284 100644 --- a/test/Transforms/InstCombine/cast.ll +++ b/test/Transforms/InstCombine/cast.ll @@ -548,4 +548,27 @@ define i64 @test55(i32 %A) { ; CHECK-NEXT: %C = or i64 %B, -32574 ; CHECK-NEXT: %D = and i64 %C, -25350 ; CHECK-NEXT: ret i64 %D -} \ No newline at end of file +} + +define i64 @test56(i16 %A) nounwind { + %tmp353 = sext i16 %A to i32 + %tmp354 = lshr i32 %tmp353, 5 + %tmp355 = zext i32 %tmp354 to i64 + ret i64 %tmp355 +; CHECK: @test56 +; CHECK-NEXT: %tmp353 = sext i16 %A to i64 +; CHECK-NEXT: %tmp354 = lshr i64 %tmp353, 5 +; CHECK-NEXT: %tmp355 = and i64 %tmp354, 134217727 +; CHECK-NEXT: ret i64 %tmp355 +} + +define i64 @test57(i64 %A) nounwind { + %B = trunc i64 %A to i32 + %C = lshr i32 %B, 8 + %E = zext i32 %C to i64 + ret i64 %E +; CHECK: @test57 +; CHECK-NEXT: %C = lshr i64 %A, 8 +; CHECK-NEXT: %E = and i64 %C, 16777215 +; CHECK-NEXT: ret i64 %E +} -- 2.34.1