Index: llvm/lib/Analysis/ValueTracking.cpp =================================================================== --- llvm/lib/Analysis/ValueTracking.cpp +++ llvm/lib/Analysis/ValueTracking.cpp @@ -967,6 +967,85 @@ } } +/// Match a small linear recurrence cycle involving shift opcodes. +/// Specifically, recognize the following: +/// %iv = phi iN [%start, %?], [%iv.next, %backedge] +/// %iv.next = shift_op %iv, %step +/// +/// TODO: This can fairly trivially be generalized for other +/// binary instructions if that were useful. +static bool MatchShiftRecurrence(const Operator *O, + Value *&StartV, Value *&StepV) { + PHINode* PN = nullptr; + switch (O->getOpcode()) { + case Instruction::Shl: + case Instruction::AShr: + case Instruction::LShr: + PN = dyn_cast(O->getOperand(0)); + StepV = O->getOperand(1); + break; + default: + return false; + } + if (!PN) + return false; + + if (PN->getNumIncomingValues() != 2) + return false; + + StartV = nullptr; + for (Value *IncV : PN->incoming_values()) { + if (IncV == O) + continue; + if (!StartV) { + StartV = IncV; + continue; + } + if (StartV != IncV) + return false; + } + + if (!StartV) + return false; + + return true; +} + +/// If operator is part of a small recurrence cycle, use facts about the +/// recurrence itself to refine the known bits of the result. +/// As is idiomatic, Known2 is used as scratch. Known is refined. +static void RefineRecurrence(const Operator *O, const APInt &DemandedElts, + KnownBits &Known, KnownBits &Known2, + unsigned Depth, const Query &Q) { + unsigned Opcode = O->getOpcode(); + + // For the moment, we only handle the shift cases here. This can + // probably be extended to most binary instructions. + if (Opcode != Instruction::LShr && + Opcode != Instruction::AShr && + Opcode != Instruction::Shl) + return; + + Value *StartV = nullptr, *StepV = nullptr; + if (MatchShiftRecurrence(O, StartV, StepV)) { + computeKnownBits(StartV, DemandedElts, Known2, Depth + 1, Q); + switch(Opcode) { + case Instruction::Shl: + // A shl recurrence will only increase the tailing zeros + Known.Zero.setLowBits(Known2.countMinTrailingZeros()); + break; + case Instruction::LShr: + // A lshr recurrence will preserve the leading zeros of the start value + Known.Zero.setHighBits(Known2.countMinLeadingZeros()); + break; + case Instruction::AShr: + // An ashr recurrence will extend the initial sign bit + Known.Zero.setHighBits(Known2.countMinLeadingZeros()); + Known.One.setHighBits(Known2.countMinLeadingOnes()); + }; + } +} + /// Compute known bits from a shift operator, including those with a /// non-constant shift amount. Known is the output of this function. Known2 is a /// pre-allocated temporary with the same bit width as Known and on return @@ -1381,6 +1460,11 @@ if (!LU) continue; unsigned Opcode = LU->getOpcode(); + + // If this is an small recurrence cycle, use facts about the + // recurrence itself to refine the result. + RefineRecurrence(LU, DemandedElts, Known, Known2, Depth, Q); + // Check for operations that have the property that if // both their operands have low zero bits, the result // will have low zero bits. Index: llvm/test/Analysis/ValueTracking/shift-recurrence-knownbits.ll =================================================================== --- /dev/null +++ llvm/test/Analysis/ValueTracking/shift-recurrence-knownbits.ll @@ -0,0 +1,106 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -instcombine -S | FileCheck %s + +define i64 @test_lshr() { +; CHECK-LABEL: @test_lshr( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: br i1 undef, label [[EXIT:%.*]], label [[LOOP]] +; CHECK: exit: +; CHECK-NEXT: ret i64 1023 +; +entry: + br label %loop +loop: + %iv.lshr = phi i64 [1023, %entry], [%iv.lshr.next, %loop] + %iv.lshr.next = lshr i64 %iv.lshr, 1 + br i1 undef, label %exit, label %loop +exit: + %res = or i64 %iv.lshr, 1023 + ret i64 %res +} + +define i64 @test_ashr_zeros() { +; CHECK-LABEL: @test_ashr_zeros( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: br i1 undef, label [[EXIT:%.*]], label [[LOOP]] +; CHECK: exit: +; CHECK-NEXT: ret i64 1023 +; +entry: + br label %loop +loop: + %iv.ashr = phi i64 [1023, %entry], [%iv.ashr.next, %loop] + %iv.ashr.next = ashr i64 %iv.ashr, 1 + br i1 undef, label %exit, label %loop +exit: + %res = or i64 %iv.ashr, 1023 + ret i64 %res +} + +define i64 @test_ashr_ones() { +; CHECK-LABEL: @test_ashr_ones( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: br i1 undef, label [[EXIT:%.*]], label [[LOOP]] +; CHECK: exit: +; CHECK-NEXT: ret i64 -1 +; +entry: + br label %loop +loop: + %iv.ashr = phi i64 [-1023, %entry], [%iv.ashr.next, %loop] + %iv.ashr.next = ashr i64 %iv.ashr, 1 + br i1 undef, label %exit, label %loop +exit: + %res = or i64 %iv.ashr, 1023 + ret i64 %res +} + +; negative case for when start is unknown +define i64 @test_ashr_unknown(i64 %start) { +; CHECK-LABEL: @test_ashr_unknown( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV_ASHR:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_ASHR_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[IV_ASHR_NEXT]] = ashr i64 [[IV_ASHR]], 1 +; CHECK-NEXT: br i1 undef, label [[EXIT:%.*]], label [[LOOP]] +; CHECK: exit: +; CHECK-NEXT: [[RES:%.*]] = or i64 [[IV_ASHR]], 1023 +; CHECK-NEXT: ret i64 [[RES]] +; +entry: + br label %loop +loop: + %iv.ashr = phi i64 [%start, %entry], [%iv.ashr.next, %loop] + %iv.ashr.next = ashr i64 %iv.ashr, 1 + br i1 undef, label %exit, label %loop +exit: + %res = or i64 %iv.ashr, 1023 + ret i64 %res +} + +define i64 @test_shl() { +; CHECK-LABEL: @test_shl( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: br i1 undef, label [[EXIT:%.*]], label [[LOOP]] +; CHECK: exit: +; CHECK-NEXT: ret i64 0 +; +entry: + br label %loop +loop: + %iv.shl = phi i64 [8, %entry], [%iv.shl.next, %loop] + %iv.shl.next = shl i64 %iv.shl, 1 + br i1 undef, label %exit, label %loop +exit: + %res = and i64 %iv.shl, 7 + ret i64 %res +}