diff options
| author | Dimitry Andric <dim@FreeBSD.org> | 2020-07-26 19:36:28 +0000 | 
|---|---|---|
| committer | Dimitry Andric <dim@FreeBSD.org> | 2020-07-26 19:36:28 +0000 | 
| commit | cfca06d7963fa0909f90483b42a6d7d194d01e08 (patch) | |
| tree | 209fb2a2d68f8f277793fc8df46c753d31bc853b /llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp | |
| parent | 706b4fc47bbc608932d3b491ae19a3b9cde9497b (diff) | |
Notes
Diffstat (limited to 'llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp')
| -rw-r--r-- | llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp | 498 | 
1 files changed, 288 insertions, 210 deletions
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp index f38dc436722d..f1233b62445d 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -897,7 +897,7 @@ Instruction *InstCombiner::foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,      // For vectors, we apply the same reasoning on a per-lane basis.      auto *Base = GEPLHS->getPointerOperand();      if (GEPLHS->getType()->isVectorTy() && Base->getType()->isPointerTy()) { -      int NumElts = GEPLHS->getType()->getVectorNumElements(); +      int NumElts = cast<VectorType>(GEPLHS->getType())->getNumElements();        Base = Builder.CreateVectorSplat(NumElts, Base);      }      return new ICmpInst(Cond, Base, @@ -1330,6 +1330,7 @@ static Instruction *processUGT_ADDCST_ADD(ICmpInst &I, Value *A, Value *B,    // The inner add was the result of the narrow add, zero extended to the    // wider type.  Replace it with the result computed by the intrinsic.    IC.replaceInstUsesWith(*OrigAdd, ZExt); +  IC.eraseInstFromFunction(*OrigAdd);    // The original icmp gets replaced with the overflow value.    return ExtractValueInst::Create(Call, 1, "sadd.overflow"); @@ -1451,6 +1452,27 @@ Instruction *InstCombiner::foldICmpWithConstant(ICmpInst &Cmp) {      if (Instruction *Res = processUGT_ADDCST_ADD(Cmp, A, B, CI2, CI, *this))        return Res; +  // icmp(phi(C1, C2, ...), C) -> phi(icmp(C1, C), icmp(C2, C), ...). +  Constant *C = dyn_cast<Constant>(Op1); +  if (!C) +    return nullptr; + +  if (auto *Phi = dyn_cast<PHINode>(Op0)) +    if (all_of(Phi->operands(), [](Value *V) { return isa<Constant>(V); })) { +      Type *Ty = Cmp.getType(); +      Builder.SetInsertPoint(Phi); +      PHINode *NewPhi = +          Builder.CreatePHI(Ty, Phi->getNumOperands()); +      for (BasicBlock *Predecessor : predecessors(Phi->getParent())) { +        auto *Input = +            cast<Constant>(Phi->getIncomingValueForBlock(Predecessor)); +        auto *BoolInput = ConstantExpr::getCompare(Pred, Input, C); +        NewPhi->addIncoming(BoolInput, Predecessor); +      } +      NewPhi->takeName(&Cmp); +      return replaceInstUsesWith(Cmp, NewPhi); +    } +    return nullptr;  } @@ -1575,11 +1597,8 @@ Instruction *InstCombiner::foldICmpXorConstant(ICmpInst &Cmp,      // If the sign bit of the XorCst is not set, there is no change to      // the operation, just stop using the Xor. -    if (!XorC->isNegative()) { -      Cmp.setOperand(0, X); -      Worklist.Add(Xor); -      return &Cmp; -    } +    if (!XorC->isNegative()) +      return replaceOperand(Cmp, 0, X);      // Emit the opposite comparison.      if (TrueIfSigned) @@ -1645,51 +1664,53 @@ Instruction *InstCombiner::foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,    bool IsShl = ShiftOpcode == Instruction::Shl;    const APInt *C3;    if (match(Shift->getOperand(1), m_APInt(C3))) { -    bool CanFold = false; +    APInt NewAndCst, NewCmpCst; +    bool AnyCmpCstBitsShiftedOut;      if (ShiftOpcode == Instruction::Shl) {        // For a left shift, we can fold if the comparison is not signed. We can        // also fold a signed comparison if the mask value and comparison value        // are not negative. These constraints may not be obvious, but we can        // prove that they are correct using an SMT solver. -      if (!Cmp.isSigned() || (!C2.isNegative() && !C1.isNegative())) -        CanFold = true; -    } else { -      bool IsAshr = ShiftOpcode == Instruction::AShr; +      if (Cmp.isSigned() && (C2.isNegative() || C1.isNegative())) +        return nullptr; + +      NewCmpCst = C1.lshr(*C3); +      NewAndCst = C2.lshr(*C3); +      AnyCmpCstBitsShiftedOut = NewCmpCst.shl(*C3) != C1; +    } else if (ShiftOpcode == Instruction::LShr) {        // For a logical right shift, we can fold if the comparison is not signed.        // We can also fold a signed comparison if the shifted mask value and the        // shifted comparison value are not negative. These constraints may not be        // obvious, but we can prove that they are correct using an SMT solver. -      // For an arithmetic shift right we can do the same, if we ensure -      // the And doesn't use any bits being shifted in. Normally these would -      // be turned into lshr by SimplifyDemandedBits, but not if there is an -      // additional user. -      if (!IsAshr || (C2.shl(*C3).lshr(*C3) == C2)) { -        if (!Cmp.isSigned() || -            (!C2.shl(*C3).isNegative() && !C1.shl(*C3).isNegative())) -          CanFold = true; -      } +      NewCmpCst = C1.shl(*C3); +      NewAndCst = C2.shl(*C3); +      AnyCmpCstBitsShiftedOut = NewCmpCst.lshr(*C3) != C1; +      if (Cmp.isSigned() && (NewAndCst.isNegative() || NewCmpCst.isNegative())) +        return nullptr; +    } else { +      // For an arithmetic shift, check that both constants don't use (in a +      // signed sense) the top bits being shifted out. +      assert(ShiftOpcode == Instruction::AShr && "Unknown shift opcode"); +      NewCmpCst = C1.shl(*C3); +      NewAndCst = C2.shl(*C3); +      AnyCmpCstBitsShiftedOut = NewCmpCst.ashr(*C3) != C1; +      if (NewAndCst.ashr(*C3) != C2) +        return nullptr;      } -    if (CanFold) { -      APInt NewCst = IsShl ? C1.lshr(*C3) : C1.shl(*C3); -      APInt SameAsC1 = IsShl ? NewCst.shl(*C3) : NewCst.lshr(*C3); -      // Check to see if we are shifting out any of the bits being compared. -      if (SameAsC1 != C1) { -        // If we shifted bits out, the fold is not going to work out. As a -        // special case, check to see if this means that the result is always -        // true or false now. -        if (Cmp.getPredicate() == ICmpInst::ICMP_EQ) -          return replaceInstUsesWith(Cmp, ConstantInt::getFalse(Cmp.getType())); -        if (Cmp.getPredicate() == ICmpInst::ICMP_NE) -          return replaceInstUsesWith(Cmp, ConstantInt::getTrue(Cmp.getType())); -      } else { -        Cmp.setOperand(1, ConstantInt::get(And->getType(), NewCst)); -        APInt NewAndCst = IsShl ? C2.lshr(*C3) : C2.shl(*C3); -        And->setOperand(1, ConstantInt::get(And->getType(), NewAndCst)); -        And->setOperand(0, Shift->getOperand(0)); -        Worklist.Add(Shift); // Shift is dead. -        return &Cmp; -      } +    if (AnyCmpCstBitsShiftedOut) { +      // If we shifted bits out, the fold is not going to work out. As a +      // special case, check to see if this means that the result is always +      // true or false now. +      if (Cmp.getPredicate() == ICmpInst::ICMP_EQ) +        return replaceInstUsesWith(Cmp, ConstantInt::getFalse(Cmp.getType())); +      if (Cmp.getPredicate() == ICmpInst::ICMP_NE) +        return replaceInstUsesWith(Cmp, ConstantInt::getTrue(Cmp.getType())); +    } else { +      Value *NewAnd = Builder.CreateAnd( +          Shift->getOperand(0), ConstantInt::get(And->getType(), NewAndCst)); +      return new ICmpInst(Cmp.getPredicate(), +          NewAnd, ConstantInt::get(And->getType(), NewCmpCst));      }    } @@ -1705,8 +1726,7 @@ Instruction *InstCombiner::foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,      // Compute X & (C2 << Y).      Value *NewAnd = Builder.CreateAnd(Shift->getOperand(0), NewShift); -    Cmp.setOperand(0, NewAnd); -    return &Cmp; +    return replaceOperand(Cmp, 0, NewAnd);    }    return nullptr; @@ -1812,8 +1832,7 @@ Instruction *InstCombiner::foldICmpAndConstConst(ICmpInst &Cmp,        }        if (NewOr) {          Value *NewAnd = Builder.CreateAnd(A, NewOr, And->getName()); -        Cmp.setOperand(0, NewAnd); -        return &Cmp; +        return replaceOperand(Cmp, 0, NewAnd);        }      }    } @@ -1863,8 +1882,8 @@ Instruction *InstCombiner::foldICmpAndConstant(ICmpInst &Cmp,      int32_t ExactLogBase2 = C2->exactLogBase2();      if (ExactLogBase2 != -1 && DL.isLegalInteger(ExactLogBase2 + 1)) {        Type *NTy = IntegerType::get(Cmp.getContext(), ExactLogBase2 + 1); -      if (And->getType()->isVectorTy()) -        NTy = VectorType::get(NTy, And->getType()->getVectorNumElements()); +      if (auto *AndVTy = dyn_cast<VectorType>(And->getType())) +        NTy = FixedVectorType::get(NTy, AndVTy->getNumElements());        Value *Trunc = Builder.CreateTrunc(X, NTy);        auto NewPred = Cmp.getPredicate() == CmpInst::ICMP_EQ ? CmpInst::ICMP_SGE                                                              : CmpInst::ICMP_SLT; @@ -1888,20 +1907,24 @@ Instruction *InstCombiner::foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,    }    Value *OrOp0 = Or->getOperand(0), *OrOp1 = Or->getOperand(1); -  if (Cmp.isEquality() && Cmp.getOperand(1) == OrOp1) { -    // X | C == C --> X <=u C -    // X | C != C --> X  >u C -    //   iff C+1 is a power of 2 (C is a bitmask of the low bits) -    if ((C + 1).isPowerOf2()) { +  const APInt *MaskC; +  if (match(OrOp1, m_APInt(MaskC)) && Cmp.isEquality()) { +    if (*MaskC == C && (C + 1).isPowerOf2()) { +      // X | C == C --> X <=u C +      // X | C != C --> X  >u C +      //   iff C+1 is a power of 2 (C is a bitmask of the low bits)        Pred = (Pred == CmpInst::ICMP_EQ) ? CmpInst::ICMP_ULE : CmpInst::ICMP_UGT;        return new ICmpInst(Pred, OrOp0, OrOp1);      } -    // More general: are all bits outside of a mask constant set or not set? -    // X | C == C --> (X & ~C) == 0 -    // X | C != C --> (X & ~C) != 0 + +    // More general: canonicalize 'equality with set bits mask' to +    // 'equality with clear bits mask'. +    // (X | MaskC) == C --> (X & ~MaskC) == C ^ MaskC +    // (X | MaskC) != C --> (X & ~MaskC) != C ^ MaskC      if (Or->hasOneUse()) { -      Value *A = Builder.CreateAnd(OrOp0, ~C); -      return new ICmpInst(Pred, A, ConstantInt::getNullValue(OrOp0->getType())); +      Value *And = Builder.CreateAnd(OrOp0, ~(*MaskC)); +      Constant *NewC = ConstantInt::get(Or->getType(), C ^ (*MaskC)); +      return new ICmpInst(Pred, And, NewC);      }    } @@ -2149,8 +2172,8 @@ Instruction *InstCombiner::foldICmpShlConstant(ICmpInst &Cmp,    if (Shl->hasOneUse() && Amt != 0 && C.countTrailingZeros() >= Amt &&        DL.isLegalInteger(TypeBits - Amt)) {      Type *TruncTy = IntegerType::get(Cmp.getContext(), TypeBits - Amt); -    if (ShType->isVectorTy()) -      TruncTy = VectorType::get(TruncTy, ShType->getVectorNumElements()); +    if (auto *ShVTy = dyn_cast<VectorType>(ShType)) +      TruncTy = FixedVectorType::get(TruncTy, ShVTy->getNumElements());      Constant *NewC =          ConstantInt::get(TruncTy, C.ashr(*ShiftAmt).trunc(TypeBits - Amt));      return new ICmpInst(Pred, Builder.CreateTrunc(X, TruncTy), NewC); @@ -2763,6 +2786,37 @@ static Instruction *foldICmpBitCast(ICmpInst &Cmp,      if (match(BCSrcOp, m_UIToFP(m_Value(X))))        if (Cmp.isEquality() && match(Op1, m_Zero()))          return new ICmpInst(Pred, X, ConstantInt::getNullValue(X->getType())); + +    // If this is a sign-bit test of a bitcast of a casted FP value, eliminate +    // the FP extend/truncate because that cast does not change the sign-bit. +    // This is true for all standard IEEE-754 types and the X86 80-bit type. +    // The sign-bit is always the most significant bit in those types. +    const APInt *C; +    bool TrueIfSigned; +    if (match(Op1, m_APInt(C)) && Bitcast->hasOneUse() && +        isSignBitCheck(Pred, *C, TrueIfSigned)) { +      if (match(BCSrcOp, m_FPExt(m_Value(X))) || +          match(BCSrcOp, m_FPTrunc(m_Value(X)))) { +        // (bitcast (fpext/fptrunc X)) to iX) < 0 --> (bitcast X to iY) < 0 +        // (bitcast (fpext/fptrunc X)) to iX) > -1 --> (bitcast X to iY) > -1 +        Type *XType = X->getType(); + +        // We can't currently handle Power style floating point operations here. +        if (!(XType->isPPC_FP128Ty() || BCSrcOp->getType()->isPPC_FP128Ty())) { + +          Type *NewType = Builder.getIntNTy(XType->getScalarSizeInBits()); +          if (auto *XVTy = dyn_cast<VectorType>(XType)) +            NewType = FixedVectorType::get(NewType, XVTy->getNumElements()); +          Value *NewBitcast = Builder.CreateBitCast(X, NewType); +          if (TrueIfSigned) +            return new ICmpInst(ICmpInst::ICMP_SLT, NewBitcast, +                                ConstantInt::getNullValue(NewType)); +          else +            return new ICmpInst(ICmpInst::ICMP_SGT, NewBitcast, +                                ConstantInt::getAllOnesValue(NewType)); +        } +      } +    }    }    // Test to see if the operands of the icmp are casted versions of other @@ -2792,11 +2846,10 @@ static Instruction *foldICmpBitCast(ICmpInst &Cmp,      return nullptr;    Value *Vec; -  Constant *Mask; -  if (match(BCSrcOp, -            m_ShuffleVector(m_Value(Vec), m_Undef(), m_Constant(Mask)))) { +  ArrayRef<int> Mask; +  if (match(BCSrcOp, m_Shuffle(m_Value(Vec), m_Undef(), m_Mask(Mask)))) {      // Check whether every element of Mask is the same constant -    if (auto *Elem = dyn_cast_or_null<ConstantInt>(Mask->getSplatValue())) { +    if (is_splat(Mask)) {        auto *VecTy = cast<VectorType>(BCSrcOp->getType());        auto *EltTy = cast<IntegerType>(VecTy->getElementType());        if (C->isSplat(EltTy->getBitWidth())) { @@ -2805,6 +2858,7 @@ static Instruction *foldICmpBitCast(ICmpInst &Cmp,          // then:          //   =>  %E = extractelement <N x iK> %vec, i32 Elem          //       icmp <pred> iK %SplatVal, <pattern> +        Value *Elem = Builder.getInt32(Mask[0]);          Value *Extract = Builder.CreateExtractElement(Vec, Elem);          Value *NewC = ConstantInt::get(EltTy, C->trunc(EltTy->getBitWidth()));          return new ICmpInst(Pred, Extract, NewC); @@ -2928,12 +2982,9 @@ Instruction *InstCombiner::foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,      break;    case Instruction::Add: {      // Replace ((add A, B) != C) with (A != C-B) if B & C are constants. -    const APInt *BOC; -    if (match(BOp1, m_APInt(BOC))) { -      if (BO->hasOneUse()) { -        Constant *SubC = ConstantExpr::getSub(RHS, cast<Constant>(BOp1)); -        return new ICmpInst(Pred, BOp0, SubC); -      } +    if (Constant *BOC = dyn_cast<Constant>(BOp1)) { +      if (BO->hasOneUse()) +        return new ICmpInst(Pred, BOp0, ConstantExpr::getSub(RHS, BOC));      } else if (C.isNullValue()) {        // Replace ((add A, B) != 0) with (A != -B) if A or B is        // efficiently invertible, or if the add has just this one use. @@ -2963,11 +3014,11 @@ Instruction *InstCombiner::foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,      break;    case Instruction::Sub:      if (BO->hasOneUse()) { -      const APInt *BOC; -      if (match(BOp0, m_APInt(BOC))) { +      // Only check for constant LHS here, as constant RHS will be canonicalized +      // to add and use the fold above. +      if (Constant *BOC = dyn_cast<Constant>(BOp0)) {          // Replace ((sub BOC, B) != C) with (B != BOC-C). -        Constant *SubC = ConstantExpr::getSub(cast<Constant>(BOp0), RHS); -        return new ICmpInst(Pred, BOp1, SubC); +        return new ICmpInst(Pred, BOp1, ConstantExpr::getSub(BOC, RHS));        } else if (C.isNullValue()) {          // Replace ((sub A, B) != 0) with (A != B).          return new ICmpInst(Pred, BOp0, BOp1); @@ -3028,20 +3079,16 @@ Instruction *InstCombiner::foldICmpEqIntrinsicWithConstant(ICmpInst &Cmp,    unsigned BitWidth = C.getBitWidth();    switch (II->getIntrinsicID()) {    case Intrinsic::bswap: -    Worklist.Add(II); -    Cmp.setOperand(0, II->getArgOperand(0)); -    Cmp.setOperand(1, ConstantInt::get(Ty, C.byteSwap())); -    return &Cmp; +    // bswap(A) == C  ->  A == bswap(C) +    return new ICmpInst(Cmp.getPredicate(), II->getArgOperand(0), +                        ConstantInt::get(Ty, C.byteSwap()));    case Intrinsic::ctlz:    case Intrinsic::cttz: {      // ctz(A) == bitwidth(A)  ->  A == 0 and likewise for != -    if (C == BitWidth) { -      Worklist.Add(II); -      Cmp.setOperand(0, II->getArgOperand(0)); -      Cmp.setOperand(1, ConstantInt::getNullValue(Ty)); -      return &Cmp; -    } +    if (C == BitWidth) +      return new ICmpInst(Cmp.getPredicate(), II->getArgOperand(0), +                          ConstantInt::getNullValue(Ty));      // ctz(A) == C -> A & Mask1 == Mask2, where Mask2 only has bit C set      // and Mask1 has bits 0..C+1 set. Similar for ctl, but for high bits. @@ -3054,10 +3101,9 @@ Instruction *InstCombiner::foldICmpEqIntrinsicWithConstant(ICmpInst &Cmp,        APInt Mask2 = IsTrailing          ? APInt::getOneBitSet(BitWidth, Num)          : APInt::getOneBitSet(BitWidth, BitWidth - Num - 1); -      Cmp.setOperand(0, Builder.CreateAnd(II->getArgOperand(0), Mask1)); -      Cmp.setOperand(1, ConstantInt::get(Ty, Mask2)); -      Worklist.Add(II); -      return &Cmp; +      return new ICmpInst(Cmp.getPredicate(), +          Builder.CreateAnd(II->getArgOperand(0), Mask1), +          ConstantInt::get(Ty, Mask2));      }      break;    } @@ -3066,14 +3112,10 @@ Instruction *InstCombiner::foldICmpEqIntrinsicWithConstant(ICmpInst &Cmp,      // popcount(A) == 0  ->  A == 0 and likewise for !=      // popcount(A) == bitwidth(A)  ->  A == -1 and likewise for !=      bool IsZero = C.isNullValue(); -    if (IsZero || C == BitWidth) { -      Worklist.Add(II); -      Cmp.setOperand(0, II->getArgOperand(0)); -      auto *NewOp = -          IsZero ? Constant::getNullValue(Ty) : Constant::getAllOnesValue(Ty); -      Cmp.setOperand(1, NewOp); -      return &Cmp; -    } +    if (IsZero || C == BitWidth) +      return new ICmpInst(Cmp.getPredicate(), II->getArgOperand(0), +          IsZero ? Constant::getNullValue(Ty) : Constant::getAllOnesValue(Ty)); +      break;    } @@ -3081,9 +3123,7 @@ Instruction *InstCombiner::foldICmpEqIntrinsicWithConstant(ICmpInst &Cmp,      // uadd.sat(a, b) == 0  ->  (a | b) == 0      if (C.isNullValue()) {        Value *Or = Builder.CreateOr(II->getArgOperand(0), II->getArgOperand(1)); -      return replaceInstUsesWith(Cmp, Builder.CreateICmp( -          Cmp.getPredicate(), Or, Constant::getNullValue(Ty))); - +      return new ICmpInst(Cmp.getPredicate(), Or, Constant::getNullValue(Ty));      }      break;    } @@ -3093,8 +3133,7 @@ Instruction *InstCombiner::foldICmpEqIntrinsicWithConstant(ICmpInst &Cmp,      if (C.isNullValue()) {        ICmpInst::Predicate NewPred = Cmp.getPredicate() == ICmpInst::ICMP_EQ            ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_UGT; -      return ICmpInst::Create(Instruction::ICmp, NewPred, -                              II->getArgOperand(0), II->getArgOperand(1)); +      return new ICmpInst(NewPred, II->getArgOperand(0), II->getArgOperand(1));      }      break;    } @@ -3300,30 +3339,19 @@ static Value *foldICmpWithLowBitMaskedVal(ICmpInst &I,      //  x & (-1 >> y) != x    ->    x u> (-1 >> y)      DstPred = ICmpInst::Predicate::ICMP_UGT;      break; -  case ICmpInst::Predicate::ICMP_UGT: +  case ICmpInst::Predicate::ICMP_ULT: +    //  x & (-1 >> y) u< x    ->    x u> (-1 >> y)      //  x u> x & (-1 >> y)    ->    x u> (-1 >> y) -    assert(X == I.getOperand(0) && "instsimplify took care of commut. variant");      DstPred = ICmpInst::Predicate::ICMP_UGT;      break;    case ICmpInst::Predicate::ICMP_UGE:      //  x & (-1 >> y) u>= x    ->    x u<= (-1 >> y) -    assert(X == I.getOperand(1) && "instsimplify took care of commut. variant"); -    DstPred = ICmpInst::Predicate::ICMP_ULE; -    break; -  case ICmpInst::Predicate::ICMP_ULT: -    //  x & (-1 >> y) u< x    ->    x u> (-1 >> y) -    assert(X == I.getOperand(1) && "instsimplify took care of commut. variant"); -    DstPred = ICmpInst::Predicate::ICMP_UGT; -    break; -  case ICmpInst::Predicate::ICMP_ULE:      //  x u<= x & (-1 >> y)    ->    x u<= (-1 >> y) -    assert(X == I.getOperand(0) && "instsimplify took care of commut. variant");      DstPred = ICmpInst::Predicate::ICMP_ULE;      break; -  case ICmpInst::Predicate::ICMP_SGT: +  case ICmpInst::Predicate::ICMP_SLT: +    //  x & (-1 >> y) s< x    ->    x s> (-1 >> y)      //  x s> x & (-1 >> y)    ->    x s> (-1 >> y) -    if (X != I.getOperand(0)) // X must be on LHS of comparison! -      return nullptr;         // Ignore the other case.      if (!match(M, m_Constant())) // Can not do this fold with non-constant.        return nullptr;      if (!match(M, m_NonNegative())) // Must not have any -1 vector elements. @@ -3332,33 +3360,19 @@ static Value *foldICmpWithLowBitMaskedVal(ICmpInst &I,      break;    case ICmpInst::Predicate::ICMP_SGE:      //  x & (-1 >> y) s>= x    ->    x s<= (-1 >> y) -    if (X != I.getOperand(1)) // X must be on RHS of comparison! -      return nullptr;         // Ignore the other case. +    //  x s<= x & (-1 >> y)    ->    x s<= (-1 >> y)      if (!match(M, m_Constant())) // Can not do this fold with non-constant.        return nullptr;      if (!match(M, m_NonNegative())) // Must not have any -1 vector elements.        return nullptr;      DstPred = ICmpInst::Predicate::ICMP_SLE;      break; -  case ICmpInst::Predicate::ICMP_SLT: -    //  x & (-1 >> y) s< x    ->    x s> (-1 >> y) -    if (X != I.getOperand(1)) // X must be on RHS of comparison! -      return nullptr;         // Ignore the other case. -    if (!match(M, m_Constant())) // Can not do this fold with non-constant. -      return nullptr; -    if (!match(M, m_NonNegative())) // Must not have any -1 vector elements. -      return nullptr; -    DstPred = ICmpInst::Predicate::ICMP_SGT; -    break; +  case ICmpInst::Predicate::ICMP_SGT:    case ICmpInst::Predicate::ICMP_SLE: -    //  x s<= x & (-1 >> y)    ->    x s<= (-1 >> y) -    if (X != I.getOperand(0)) // X must be on LHS of comparison! -      return nullptr;         // Ignore the other case. -    if (!match(M, m_Constant())) // Can not do this fold with non-constant. -      return nullptr; -    if (!match(M, m_NonNegative())) // Must not have any -1 vector elements. -      return nullptr; -    DstPred = ICmpInst::Predicate::ICMP_SLE; +    return nullptr; +  case ICmpInst::Predicate::ICMP_UGT: +  case ICmpInst::Predicate::ICMP_ULE: +    llvm_unreachable("Instsimplify took care of commut. variant");      break;    default:      llvm_unreachable("All possible folds are handled."); @@ -3370,8 +3384,9 @@ static Value *foldICmpWithLowBitMaskedVal(ICmpInst &I,    Type *OpTy = M->getType();    auto *VecC = dyn_cast<Constant>(M);    if (OpTy->isVectorTy() && VecC && VecC->containsUndefElement()) { +    auto *OpVTy = cast<VectorType>(OpTy);      Constant *SafeReplacementConstant = nullptr; -    for (unsigned i = 0, e = OpTy->getVectorNumElements(); i != e; ++i) { +    for (unsigned i = 0, e = OpVTy->getNumElements(); i != e; ++i) {        if (!isa<UndefValue>(VecC->getAggregateElement(i))) {          SafeReplacementConstant = VecC->getAggregateElement(i);          break; @@ -3494,7 +3509,8 @@ foldShiftIntoShiftInAnotherHandOfAndInICmp(ICmpInst &I, const SimplifyQuery SQ,    Instruction *NarrowestShift = XShift;    Type *WidestTy = WidestShift->getType(); -  assert(NarrowestShift->getType() == I.getOperand(0)->getType() && +  Type *NarrowestTy = NarrowestShift->getType(); +  assert(NarrowestTy == I.getOperand(0)->getType() &&           "We did not look past any shifts while matching XShift though.");    bool HadTrunc = WidestTy != I.getOperand(0)->getType(); @@ -3533,6 +3549,23 @@ foldShiftIntoShiftInAnotherHandOfAndInICmp(ICmpInst &I, const SimplifyQuery SQ,    if (XShAmt->getType() != YShAmt->getType())      return nullptr; +  // As input, we have the following pattern: +  //   icmp eq/ne (and ((x shift Q), (y oppositeshift K))), 0 +  // We want to rewrite that as: +  //   icmp eq/ne (and (x shift (Q+K)), y), 0  iff (Q+K) u< bitwidth(x) +  // While we know that originally (Q+K) would not overflow +  // (because  2 * (N-1) u<= iN -1), we have looked past extensions of +  // shift amounts. so it may now overflow in smaller bitwidth. +  // To ensure that does not happen, we need to ensure that the total maximal +  // shift amount is still representable in that smaller bit width. +  unsigned MaximalPossibleTotalShiftAmount = +      (WidestTy->getScalarSizeInBits() - 1) + +      (NarrowestTy->getScalarSizeInBits() - 1); +  APInt MaximalRepresentableShiftAmount = +      APInt::getAllOnesValue(XShAmt->getType()->getScalarSizeInBits()); +  if (MaximalRepresentableShiftAmount.ult(MaximalPossibleTotalShiftAmount)) +    return nullptr; +    // Can we fold (XShAmt+YShAmt) ?    auto *NewShAmt = dyn_cast_or_null<Constant>(        SimplifyAddInst(XShAmt, YShAmt, /*isNSW=*/false, @@ -3627,9 +3660,6 @@ Value *InstCombiner::foldUnsignedMultiplicationOverflowCheck(ICmpInst &I) {        match(&I, m_c_ICmp(Pred, m_OneUse(m_UDiv(m_AllOnes(), m_Value(X))),                           m_Value(Y)))) {      Mul = nullptr; -    // Canonicalize as-if y was on RHS. -    if (I.getOperand(1) != Y) -      Pred = I.getSwappedPredicate();      // Are we checking that overflow does not happen, or does happen?      switch (Pred) { @@ -3674,6 +3704,11 @@ Value *InstCombiner::foldUnsignedMultiplicationOverflowCheck(ICmpInst &I) {    if (NeedNegation) // This technically increases instruction count.      Res = Builder.CreateNot(Res, "umul.not.ov"); +  // If we replaced the mul, erase it. Do this after all uses of Builder, +  // as the mul is used as insertion point. +  if (MulHadOtherUses) +    eraseInstFromFunction(*Mul); +    return Res;  } @@ -4202,9 +4237,7 @@ Instruction *InstCombiner::foldICmpEquality(ICmpInst &I) {      if (X) { // Build (X^Y) & Z        Op1 = Builder.CreateXor(X, Y);        Op1 = Builder.CreateAnd(Op1, Z); -      I.setOperand(0, Op1); -      I.setOperand(1, Constant::getNullValue(Op1->getType())); -      return &I; +      return new ICmpInst(Pred, Op1, Constant::getNullValue(Op1->getType()));      }    } @@ -4613,17 +4646,6 @@ static Instruction *processUMulZExtIdiom(ICmpInst &I, Value *MulVal,    case ICmpInst::ICMP_NE:      // Recognize pattern:      //   mulval = mul(zext A, zext B) -    //   cmp eq/neq mulval, zext trunc mulval -    if (ZExtInst *Zext = dyn_cast<ZExtInst>(OtherVal)) -      if (Zext->hasOneUse()) { -        Value *ZextArg = Zext->getOperand(0); -        if (TruncInst *Trunc = dyn_cast<TruncInst>(ZextArg)) -          if (Trunc->getType()->getPrimitiveSizeInBits() == MulWidth) -            break; //Recognized -      } - -    // Recognize pattern: -    //   mulval = mul(zext A, zext B)      //   cmp eq/neq mulval, and(mulval, mask), mask selects low MulWidth bits.      ConstantInt *CI;      Value *ValToMask; @@ -4701,7 +4723,7 @@ static Instruction *processUMulZExtIdiom(ICmpInst &I, Value *MulVal,    Function *F = Intrinsic::getDeclaration(        I.getModule(), Intrinsic::umul_with_overflow, MulType);    CallInst *Call = Builder.CreateCall(F, {MulA, MulB}, "umul"); -  IC.Worklist.Add(MulInstr); +  IC.Worklist.push(MulInstr);    // If there are uses of mul result other than the comparison, we know that    // they are truncation or binary AND. Change them to use result of @@ -4723,18 +4745,16 @@ static Instruction *processUMulZExtIdiom(ICmpInst &I, Value *MulVal,          ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1));          APInt ShortMask = CI->getValue().trunc(MulWidth);          Value *ShortAnd = Builder.CreateAnd(Mul, ShortMask); -        Instruction *Zext = -            cast<Instruction>(Builder.CreateZExt(ShortAnd, BO->getType())); -        IC.Worklist.Add(Zext); +        Value *Zext = Builder.CreateZExt(ShortAnd, BO->getType());          IC.replaceInstUsesWith(*BO, Zext);        } else {          llvm_unreachable("Unexpected Binary operation");        } -      IC.Worklist.Add(cast<Instruction>(U)); +      IC.Worklist.push(cast<Instruction>(U));      }    }    if (isa<Instruction>(OtherVal)) -    IC.Worklist.Add(cast<Instruction>(OtherVal)); +    IC.Worklist.push(cast<Instruction>(OtherVal));    // The original icmp gets replaced with the overflow value, maybe inverted    // depending on predicate. @@ -5189,8 +5209,8 @@ llvm::getFlippedStrictnessPredicateAndConstant(CmpInst::Predicate Pred,      // Bail out if the constant can't be safely incremented/decremented.      if (!ConstantIsOk(CI))        return llvm::None; -  } else if (Type->isVectorTy()) { -    unsigned NumElts = Type->getVectorNumElements(); +  } else if (auto *VTy = dyn_cast<VectorType>(Type)) { +    unsigned NumElts = VTy->getNumElements();      for (unsigned i = 0; i != NumElts; ++i) {        Constant *Elt = C->getAggregateElement(i);        if (!Elt) @@ -5252,6 +5272,47 @@ static ICmpInst *canonicalizeCmpWithConstant(ICmpInst &I) {    return new ICmpInst(FlippedStrictness->first, Op0, FlippedStrictness->second);  } +/// If we have a comparison with a non-canonical predicate, if we can update +/// all the users, invert the predicate and adjust all the users. +static CmpInst *canonicalizeICmpPredicate(CmpInst &I) { +  // Is the predicate already canonical? +  CmpInst::Predicate Pred = I.getPredicate(); +  if (isCanonicalPredicate(Pred)) +    return nullptr; + +  // Can all users be adjusted to predicate inversion? +  if (!canFreelyInvertAllUsersOf(&I, /*IgnoredUser=*/nullptr)) +    return nullptr; + +  // Ok, we can canonicalize comparison! +  // Let's first invert the comparison's predicate. +  I.setPredicate(CmpInst::getInversePredicate(Pred)); +  I.setName(I.getName() + ".not"); + +  // And now let's adjust every user. +  for (User *U : I.users()) { +    switch (cast<Instruction>(U)->getOpcode()) { +    case Instruction::Select: { +      auto *SI = cast<SelectInst>(U); +      SI->swapValues(); +      SI->swapProfMetadata(); +      break; +    } +    case Instruction::Br: +      cast<BranchInst>(U)->swapSuccessors(); // swaps prof metadata too +      break; +    case Instruction::Xor: +      U->replaceAllUsesWith(&I); +      break; +    default: +      llvm_unreachable("Got unexpected user - out of sync with " +                       "canFreelyInvertAllUsersOf() ?"); +    } +  } + +  return &I; +} +  /// Integer compare with boolean values can always be turned into bitwise ops.  static Instruction *canonicalizeICmpBool(ICmpInst &I,                                           InstCombiner::BuilderTy &Builder) { @@ -5338,10 +5399,6 @@ static Instruction *foldICmpWithHighBitMask(ICmpInst &Cmp,    Value *X, *Y;    if (match(&Cmp,              m_c_ICmp(Pred, m_OneUse(m_Shl(m_One(), m_Value(Y))), m_Value(X)))) { -    // We want X to be the icmp's second operand, so swap predicate if it isn't. -    if (Cmp.getOperand(0) == X) -      Pred = Cmp.getSwappedPredicate(); -      switch (Pred) {      case ICmpInst::ICMP_ULE:        NewPred = ICmpInst::ICMP_NE; @@ -5361,10 +5418,6 @@ static Instruction *foldICmpWithHighBitMask(ICmpInst &Cmp,      // The variant with 'add' is not canonical, (the variant with 'not' is)      // we only get it because it has extra uses, and can't be canonicalized, -    // We want X to be the icmp's second operand, so swap predicate if it isn't. -    if (Cmp.getOperand(0) == X) -      Pred = Cmp.getSwappedPredicate(); -      switch (Pred) {      case ICmpInst::ICMP_ULT:        NewPred = ICmpInst::ICMP_NE; @@ -5385,21 +5438,45 @@ static Instruction *foldICmpWithHighBitMask(ICmpInst &Cmp,  static Instruction *foldVectorCmp(CmpInst &Cmp,                                    InstCombiner::BuilderTy &Builder) { -  // If both arguments of the cmp are shuffles that use the same mask and -  // shuffle within a single vector, move the shuffle after the cmp. +  const CmpInst::Predicate Pred = Cmp.getPredicate();    Value *LHS = Cmp.getOperand(0), *RHS = Cmp.getOperand(1);    Value *V1, *V2; -  Constant *M; -  if (match(LHS, m_ShuffleVector(m_Value(V1), m_Undef(), m_Constant(M))) && -      match(RHS, m_ShuffleVector(m_Value(V2), m_Undef(), m_Specific(M))) && -      V1->getType() == V2->getType() && -      (LHS->hasOneUse() || RHS->hasOneUse())) { -    // cmp (shuffle V1, M), (shuffle V2, M) --> shuffle (cmp V1, V2), M -    CmpInst::Predicate P = Cmp.getPredicate(); -    Value *NewCmp = isa<ICmpInst>(Cmp) ? Builder.CreateICmp(P, V1, V2) -                                       : Builder.CreateFCmp(P, V1, V2); +  ArrayRef<int> M; +  if (!match(LHS, m_Shuffle(m_Value(V1), m_Undef(), m_Mask(M)))) +    return nullptr; + +  // If both arguments of the cmp are shuffles that use the same mask and +  // shuffle within a single vector, move the shuffle after the cmp: +  // cmp (shuffle V1, M), (shuffle V2, M) --> shuffle (cmp V1, V2), M +  Type *V1Ty = V1->getType(); +  if (match(RHS, m_Shuffle(m_Value(V2), m_Undef(), m_SpecificMask(M))) && +      V1Ty == V2->getType() && (LHS->hasOneUse() || RHS->hasOneUse())) { +    Value *NewCmp = Builder.CreateCmp(Pred, V1, V2);      return new ShuffleVectorInst(NewCmp, UndefValue::get(NewCmp->getType()), M);    } + +  // Try to canonicalize compare with splatted operand and splat constant. +  // TODO: We could generalize this for more than splats. See/use the code in +  //       InstCombiner::foldVectorBinop(). +  Constant *C; +  if (!LHS->hasOneUse() || !match(RHS, m_Constant(C))) +    return nullptr; + +  // Length-changing splats are ok, so adjust the constants as needed: +  // cmp (shuffle V1, M), C --> shuffle (cmp V1, C'), M +  Constant *ScalarC = C->getSplatValue(/* AllowUndefs */ true); +  int MaskSplatIndex; +  if (ScalarC && match(M, m_SplatOrUndefMask(MaskSplatIndex))) { +    // We allow undefs in matching, but this transform removes those for safety. +    // Demanded elements analysis should be able to recover some/all of that. +    C = ConstantVector::getSplat(cast<VectorType>(V1Ty)->getElementCount(), +                                 ScalarC); +    SmallVector<int, 8> NewM(M.size(), MaskSplatIndex); +    Value *NewCmp = Builder.CreateCmp(Pred, V1, C); +    return new ShuffleVectorInst(NewCmp, UndefValue::get(NewCmp->getType()), +                                 NewM); +  } +    return nullptr;  } @@ -5474,8 +5551,11 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {      if (Instruction *Res = canonicalizeICmpBool(I, Builder))        return Res; -  if (ICmpInst *NewICmp = canonicalizeCmpWithConstant(I)) -    return NewICmp; +  if (Instruction *Res = canonicalizeCmpWithConstant(I)) +    return Res; + +  if (Instruction *Res = canonicalizeICmpPredicate(I)) +    return Res;    if (Instruction *Res = foldICmpWithConstant(I))      return Res; @@ -5565,6 +5645,7 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {    if (Instruction *Res = foldICmpBitCast(I, Builder))      return Res; +  // TODO: Hoist this above the min/max bailout.    if (Instruction *R = foldICmpWithCastOp(I))      return R; @@ -5600,9 +5681,13 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {          isa<IntegerType>(A->getType())) {        Value *Result;        Constant *Overflow; -      if (OptimizeOverflowCheck(Instruction::Add, /*Signed*/false, A, B, -                                *AddI, Result, Overflow)) { +      // m_UAddWithOverflow can match patterns that do not include  an explicit +      // "add" instruction, so check the opcode of the matched op. +      if (AddI->getOpcode() == Instruction::Add && +          OptimizeOverflowCheck(Instruction::Add, /*Signed*/ false, A, B, *AddI, +                                Result, Overflow)) {          replaceInstUsesWith(*AddI, Result); +        eraseInstFromFunction(*AddI);          return replaceInstUsesWith(I, Overflow);        }      } @@ -5689,7 +5774,7 @@ Instruction *InstCombiner::foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,        // TODO: Can never be -0.0 and other non-representable values        APFloat RHSRoundInt(RHS);        RHSRoundInt.roundToIntegral(APFloat::rmNearestTiesToEven); -      if (RHS.compare(RHSRoundInt) != APFloat::cmpEqual) { +      if (RHS != RHSRoundInt) {          if (P == FCmpInst::FCMP_OEQ || P == FCmpInst::FCMP_UEQ)            return replaceInstUsesWith(I, Builder.getFalse()); @@ -5777,7 +5862,7 @@ Instruction *InstCombiner::foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,      APFloat SMax(RHS.getSemantics());      SMax.convertFromAPInt(APInt::getSignedMaxValue(IntWidth), true,                            APFloat::rmNearestTiesToEven); -    if (SMax.compare(RHS) == APFloat::cmpLessThan) {  // smax < 13123.0 +    if (SMax < RHS) { // smax < 13123.0        if (Pred == ICmpInst::ICMP_NE  || Pred == ICmpInst::ICMP_SLT ||            Pred == ICmpInst::ICMP_SLE)          return replaceInstUsesWith(I, Builder.getTrue()); @@ -5789,7 +5874,7 @@ Instruction *InstCombiner::foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,      APFloat UMax(RHS.getSemantics());      UMax.convertFromAPInt(APInt::getMaxValue(IntWidth), false,                            APFloat::rmNearestTiesToEven); -    if (UMax.compare(RHS) == APFloat::cmpLessThan) {  // umax < 13123.0 +    if (UMax < RHS) { // umax < 13123.0        if (Pred == ICmpInst::ICMP_NE  || Pred == ICmpInst::ICMP_ULT ||            Pred == ICmpInst::ICMP_ULE)          return replaceInstUsesWith(I, Builder.getTrue()); @@ -5802,7 +5887,7 @@ Instruction *InstCombiner::foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,      APFloat SMin(RHS.getSemantics());      SMin.convertFromAPInt(APInt::getSignedMinValue(IntWidth), true,                            APFloat::rmNearestTiesToEven); -    if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { // smin > 12312.0 +    if (SMin > RHS) { // smin > 12312.0        if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_SGT ||            Pred == ICmpInst::ICMP_SGE)          return replaceInstUsesWith(I, Builder.getTrue()); @@ -5810,10 +5895,10 @@ Instruction *InstCombiner::foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,      }    } else {      // See if the RHS value is < UnsignedMin. -    APFloat SMin(RHS.getSemantics()); -    SMin.convertFromAPInt(APInt::getMinValue(IntWidth), true, +    APFloat UMin(RHS.getSemantics()); +    UMin.convertFromAPInt(APInt::getMinValue(IntWidth), false,                            APFloat::rmNearestTiesToEven); -    if (SMin.compare(RHS) == APFloat::cmpGreaterThan) { // umin > 12312.0 +    if (UMin > RHS) { // umin > 12312.0        if (Pred == ICmpInst::ICMP_NE || Pred == ICmpInst::ICMP_UGT ||            Pred == ICmpInst::ICMP_UGE)          return replaceInstUsesWith(I, Builder.getTrue()); @@ -5949,16 +6034,15 @@ static Instruction *foldFCmpReciprocalAndZero(FCmpInst &I, Instruction *LHSI,  }  /// Optimize fabs(X) compared with zero. -static Instruction *foldFabsWithFcmpZero(FCmpInst &I) { +static Instruction *foldFabsWithFcmpZero(FCmpInst &I, InstCombiner &IC) {    Value *X;    if (!match(I.getOperand(0), m_Intrinsic<Intrinsic::fabs>(m_Value(X))) ||        !match(I.getOperand(1), m_PosZeroFP()))      return nullptr; -  auto replacePredAndOp0 = [](FCmpInst *I, FCmpInst::Predicate P, Value *X) { +  auto replacePredAndOp0 = [&IC](FCmpInst *I, FCmpInst::Predicate P, Value *X) {      I->setPredicate(P); -    I->setOperand(0, X); -    return I; +    return IC.replaceOperand(*I, 0, X);    };    switch (I.getPredicate()) { @@ -6058,14 +6142,11 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) {    // If we're just checking for a NaN (ORD/UNO) and have a non-NaN operand,    // then canonicalize the operand to 0.0.    if (Pred == CmpInst::FCMP_ORD || Pred == CmpInst::FCMP_UNO) { -    if (!match(Op0, m_PosZeroFP()) && isKnownNeverNaN(Op0, &TLI)) { -      I.setOperand(0, ConstantFP::getNullValue(OpType)); -      return &I; -    } -    if (!match(Op1, m_PosZeroFP()) && isKnownNeverNaN(Op1, &TLI)) { -      I.setOperand(1, ConstantFP::getNullValue(OpType)); -      return &I; -    } +    if (!match(Op0, m_PosZeroFP()) && isKnownNeverNaN(Op0, &TLI)) +      return replaceOperand(I, 0, ConstantFP::getNullValue(OpType)); + +    if (!match(Op1, m_PosZeroFP()) && isKnownNeverNaN(Op1, &TLI)) +      return replaceOperand(I, 1, ConstantFP::getNullValue(OpType));    }    // fcmp pred (fneg X), (fneg Y) -> fcmp swap(pred) X, Y @@ -6090,10 +6171,8 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) {    // The sign of 0.0 is ignored by fcmp, so canonicalize to +0.0:    // fcmp Pred X, -0.0 --> fcmp Pred X, 0.0 -  if (match(Op1, m_AnyZeroFP()) && !match(Op1, m_PosZeroFP())) { -    I.setOperand(1, ConstantFP::getNullValue(OpType)); -    return &I; -  } +  if (match(Op1, m_AnyZeroFP()) && !match(Op1, m_PosZeroFP())) +    return replaceOperand(I, 1, ConstantFP::getNullValue(OpType));    // Handle fcmp with instruction LHS and constant RHS.    Instruction *LHSI; @@ -6128,7 +6207,7 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) {    }    } -  if (Instruction *R = foldFabsWithFcmpZero(I)) +  if (Instruction *R = foldFabsWithFcmpZero(I, *this))      return R;    if (match(Op0, m_FNeg(m_Value(X)))) { @@ -6159,8 +6238,7 @@ Instruction *InstCombiner::visitFCmpInst(FCmpInst &I) {        APFloat Fabs = TruncC;        Fabs.clearSign();        if (!Lossy && -          ((Fabs.compare(APFloat::getSmallestNormalized(FPSem)) != -            APFloat::cmpLessThan) || Fabs.isZero())) { +          (!(Fabs < APFloat::getSmallestNormalized(FPSem)) || Fabs.isZero())) {          Constant *NewC = ConstantFP::get(X->getType(), TruncC);          return new FCmpInst(Pred, X, NewC, "", &I);        }  | 
