InstCombineShifts.cpp | Explore in Territory

//===- InstCombineShifts.cpp ----------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the visitShl, visitLShr, and visitAShr functions.
//
//===----------------------------------------------------------------------===//

#include "InstCombineInternal.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
usingnamespacellvm;
usingnamespacePatternMatch;

#define DEBUG_TYPE …

bool canTryToConstantAddTwoShiftAmounts(Value *Sh0, Value *ShAmt0, Value *Sh1,
                                        Value *ShAmt1) { … }

// Given pattern:
//   (x shiftopcode Q) shiftopcode K
// we should rewrite it as
//   x shiftopcode (Q+K)  iff (Q+K) u< bitwidth(x) and
//
// This is valid for any shift, but they must be identical, and we must be
// careful in case we have (zext(Q)+zext(K)) and look past extensions,
// (Q+K) must not overflow or else (Q+K) u< bitwidth(x) is bogus.
//
// AnalyzeForSignBitExtraction indicates that we will only analyze whether this
// pattern has any 2 right-shifts that sum to 1 less than original bit width.
Value *InstCombinerImpl::reassociateShiftAmtsOfTwoSameDirectionShifts(
    BinaryOperator *Sh0, const SimplifyQuery &SQ,
    bool AnalyzeForSignBitExtraction) { … }

// If we have some pattern that leaves only some low bits set, and then performs
// left-shift of those bits, if none of the bits that are left after the final
// shift are modified by the mask, we can omit the mask.
//
// There are many variants to this pattern:
//   a)  (x & ((1 << MaskShAmt) - 1)) << ShiftShAmt
//   b)  (x & (~(-1 << MaskShAmt))) << ShiftShAmt
//   c)  (x & (-1 l>> MaskShAmt)) << ShiftShAmt
//   d)  (x & ((-1 << MaskShAmt) l>> MaskShAmt)) << ShiftShAmt
//   e)  ((x << MaskShAmt) l>> MaskShAmt) << ShiftShAmt
//   f)  ((x << MaskShAmt) a>> MaskShAmt) << ShiftShAmt
// All these patterns can be simplified to just:
//   x << ShiftShAmt
// iff:
//   a,b)     (MaskShAmt+ShiftShAmt) u>= bitwidth(x)
//   c,d,e,f) (ShiftShAmt-MaskShAmt) s>= 0 (i.e. ShiftShAmt u>= MaskShAmt)
static Instruction *
dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift,
                                     const SimplifyQuery &Q,
                                     InstCombiner::BuilderTy &Builder) { … }

/// If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/
/// shl) that itself has a shift-by-constant operand with identical opcode, we
/// may be able to convert that into 2 independent shifts followed by the logic
/// op. This eliminates a use of an intermediate value (reduces dependency
/// chain).
static Instruction *foldShiftOfShiftedBinOp(BinaryOperator &I,
                                            InstCombiner::BuilderTy &Builder) { … }

Instruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) { … }

/// Return true if we can simplify two logical (either left or right) shifts
/// that have constant shift amounts: OuterShift (InnerShift X, C1), C2.
static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl,
                                    Instruction *InnerShift,
                                    InstCombinerImpl &IC, Instruction *CxtI) { … }

/// See if we can compute the specified value, but shifted logically to the left
/// or right by some number of bits. This should return true if the expression
/// can be computed for the same cost as the current expression tree. This is
/// used to eliminate extraneous shifting from things like:
///      %C = shl i128 %A, 64
///      %D = shl i128 %B, 96
///      %E = or i128 %C, %D
///      %F = lshr i128 %E, 64
/// where the client will ask if E can be computed shifted right by 64-bits. If
/// this succeeds, getShiftedValue() will be called to produce the value.
static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift,
                               InstCombinerImpl &IC, Instruction *CxtI) { … }

/// Fold OuterShift (InnerShift X, C1), C2.
/// See canEvaluateShiftedShift() for the constraints on these instructions.
static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt,
                               bool IsOuterShl,
                               InstCombiner::BuilderTy &Builder) { … }

/// When canEvaluateShifted() returns true for an expression, this function
/// inserts the new computation that produces the shifted value.
static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,
                              InstCombinerImpl &IC, const DataLayout &DL) { … }

// If this is a bitwise operator or add with a constant RHS we might be able
// to pull it through a shift.
static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift,
                                         BinaryOperator *BO) { … }

Instruction *InstCombinerImpl::FoldShiftByConstant(Value *Op0, Constant *C1,
                                                   BinaryOperator &I) { … }

// Tries to perform
//    (lshr (add (zext X), (zext Y)), K)
//      -> (icmp ult (add X, Y), X)
//    where
//      - The add's operands are zexts from a K-bits integer to a bigger type.
//      - The add is only used by the shr, or by iK (or narrower) truncates.
//      - The lshr type has more than 2 bits (other types are boolean math).
//      - K > 1
//    note that
//      - The resulting add cannot have nuw/nsw, else on overflow we get a
//        poison value and the transform isn't legal anymore.
Instruction *InstCombinerImpl::foldLShrOverflowBit(BinaryOperator &I) { … }

// Try to set nuw/nsw flags on shl or exact flag on lshr/ashr using knownbits.
static bool setShiftFlags(BinaryOperator &I, const SimplifyQuery &Q) { … }

Instruction *InstCombinerImpl::visitShl(BinaryOperator &I) { … }

Instruction *InstCombinerImpl::visitLShr(BinaryOperator &I) { … }

Instruction *
InstCombinerImpl::foldVariableSignZeroExtensionOfVariableHighBitExtract(
    BinaryOperator &OldAShr) { … }

Instruction *InstCombinerImpl::visitAShr(BinaryOperator &I) { … }
llvm/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
