1//===- AggressiveInstCombineInternal.h --------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the instruction pattern combiner classes.
10// Currently, it handles pattern expressions for:
11//  * Truncate instruction
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_LIB_TRANSFORMS_AGGRESSIVEINSTCOMBINE_COMBINEINTERNAL_H
16#define LLVM_LIB_TRANSFORMS_AGGRESSIVEINSTCOMBINE_COMBINEINTERNAL_H
17
18#include "llvm/ADT/MapVector.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/Analysis/ValueTracking.h"
21#include "llvm/Support/KnownBits.h"
22
23using namespace llvm;
24
25//===----------------------------------------------------------------------===//
26// TruncInstCombine - looks for expression graphs dominated by trunc
27// instructions and for each eligible graph, it will create a reduced bit-width
28// expression and replace the old expression with this new one and remove the
29// old one. Eligible expression graph is such that:
30//   1. Contains only supported instructions.
31//   2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.
32//   3. Can be evaluated into type with reduced legal bit-width (or Trunc type).
33//   4. All instructions in the graph must not have users outside the graph.
34//      Only exception is for {ZExt, SExt}Inst with operand type equal to the
35//      new reduced type chosen in (3).
36//
37// The motivation for this optimization is that evaluating and expression using
38// smaller bit-width is preferable, especially for vectorization where we can
39// fit more values in one vectorized instruction. In addition, this optimization
40// may decrease the number of cast instructions, but will not increase it.
41//===----------------------------------------------------------------------===//
42
43namespace llvm {
44class AssumptionCache;
45class DataLayout;
46class DominatorTree;
47class Function;
48class Instruction;
49class TargetLibraryInfo;
50class TruncInst;
51class Type;
52class Value;
53
54class TruncInstCombine {
55  AssumptionCache ∾
56  TargetLibraryInfo &TLI;
57  const DataLayout &DL;
58  const DominatorTree &DT;
59
60  /// List of all TruncInst instructions to be processed.
61  SmallVector<TruncInst *, 4> Worklist;
62
63  /// Current processed TruncInst instruction.
64  TruncInst *CurrentTruncInst = nullptr;
65
66  /// Information per each instruction in the expression graph.
67  struct Info {
68    /// Number of LSBs that are needed to generate a valid expression.
69    unsigned ValidBitWidth = 0;
70    /// Minimum number of LSBs needed to generate the ValidBitWidth.
71    unsigned MinBitWidth = 0;
72    /// The reduced value generated to replace the old instruction.
73    Value *NewValue = nullptr;
74  };
75  /// An ordered map representing expression graph post-dominated by current
76  /// processed TruncInst. It maps each instruction in the graph to its Info
77  /// structure. The map is ordered such that each instruction appears before
78  /// all other instructions in the graph that uses it.
79  MapVector<Instruction *, Info> InstInfoMap;
80
81public:
82  TruncInstCombine(AssumptionCache &AC, TargetLibraryInfo &TLI,
83                   const DataLayout &DL, const DominatorTree &DT)
84      : AC(AC), TLI(TLI), DL(DL), DT(DT) {}
85
86  /// Perform TruncInst pattern optimization on given function.
87  bool run(Function &F);
88
89private:
90  /// Build expression graph dominated by the /p CurrentTruncInst and append it
91  /// to the InstInfoMap container.
92  ///
93  /// \return true only if succeed to generate an eligible sub expression graph.
94  bool buildTruncExpressionGraph();
95
96  /// Calculate the minimal allowed bit-width of the chain ending with the
97  /// currently visited truncate's operand.
98  ///
99  /// \return minimum number of bits to which the chain ending with the
100  /// truncate's operand can be shrunk to.
101  unsigned getMinBitWidth();
102
103  /// Build an expression graph dominated by the current processed TruncInst and
104  /// Check if it is eligible to be reduced to a smaller type.
105  ///
106  /// \return the scalar version of the new type to be used for the reduced
107  ///         expression graph, or nullptr if the expression graph is not
108  ///         eligible to be reduced.
109  Type *getBestTruncatedType();
110
111  KnownBits computeKnownBits(const Value *V) const {
112    return llvm::computeKnownBits(V, DL, /*Depth=*/0, &AC,
113                                  /*CtxI=*/cast<Instruction>(CurrentTruncInst),
114                                  &DT);
115  }
116
117  unsigned ComputeNumSignBits(const Value *V) const {
118    return llvm::ComputeNumSignBits(
119        V, DL, /*Depth=*/0, &AC, /*CtxI=*/cast<Instruction>(CurrentTruncInst),
120        &DT);
121  }
122
123  /// Given a \p V value and a \p SclTy scalar type return the generated reduced
124  /// value of \p V based on the type \p SclTy.
125  ///
126  /// \param V value to be reduced.
127  /// \param SclTy scalar version of new type to reduce to.
128  /// \return the new reduced value.
129  Value *getReducedOperand(Value *V, Type *SclTy);
130
131  /// Create a new expression graph using the reduced /p SclTy type and replace
132  /// the old expression graph with it. Also erase all instructions in the old
133  /// graph, except those that are still needed outside the graph.
134  ///
135  /// \param SclTy scalar version of new type to reduce expression graph into.
136  void ReduceExpressionGraph(Type *SclTy);
137};
138} // end namespace llvm.
139
140#endif
141