LLVM  12.0.0git
AggressiveInstCombineInternal.h
Go to the documentation of this file.
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 
21 using namespace llvm;
22 
23 //===----------------------------------------------------------------------===//
24 // TruncInstCombine - looks for expression dags dominated by trunc instructions
25 // and for each eligible dag, it will create a reduced bit-width expression and
26 // replace the old expression with this new one and remove the old one.
27 // Eligible expression dag is such that:
28 // 1. Contains only supported instructions.
29 // 2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.
30 // 3. Can be evaluated into type with reduced legal bit-width (or Trunc type).
31 // 4. All instructions in the dag must not have users outside the dag.
32 // Only exception is for {ZExt, SExt}Inst with operand type equal to the
33 // new reduced type chosen in (3).
34 //
35 // The motivation for this optimization is that evaluating and expression using
36 // smaller bit-width is preferable, especially for vectorization where we can
37 // fit more values in one vectorized instruction. In addition, this optimization
38 // may decrease the number of cast instructions, but will not increase it.
39 //===----------------------------------------------------------------------===//
40 
41 namespace llvm {
42  class DataLayout;
43  class DominatorTree;
44  class Function;
45  class Instruction;
46  class TargetLibraryInfo;
47  class TruncInst;
48  class Type;
49  class Value;
50 
52  TargetLibraryInfo &TLI;
53  const DataLayout &DL;
54  const DominatorTree &DT;
55 
56  /// List of all TruncInst instructions to be processed.
58 
59  /// Current processed TruncInst instruction.
60  TruncInst *CurrentTruncInst;
61 
62  /// Information per each instruction in the expression dag.
63  struct Info {
64  /// Number of LSBs that are needed to generate a valid expression.
65  unsigned ValidBitWidth = 0;
66  /// Minimum number of LSBs needed to generate the ValidBitWidth.
67  unsigned MinBitWidth = 0;
68  /// The reduced value generated to replace the old instruction.
69  Value *NewValue = nullptr;
70  };
71  /// An ordered map representing expression dag post-dominated by current
72  /// processed TruncInst. It maps each instruction in the dag to its Info
73  /// structure. The map is ordered such that each instruction appears before
74  /// all other instructions in the dag that uses it.
76 
77 public:
79  const DominatorTree &DT)
80  : TLI(TLI), DL(DL), DT(DT), CurrentTruncInst(nullptr) {}
81 
82  /// Perform TruncInst pattern optimization on given function.
83  bool run(Function &F);
84 
85 private:
86  /// Build expression dag dominated by the /p CurrentTruncInst and append it to
87  /// the InstInfoMap container.
88  ///
89  /// \return true only if succeed to generate an eligible sub expression dag.
90  bool buildTruncExpressionDag();
91 
92  /// Calculate the minimal allowed bit-width of the chain ending with the
93  /// currently visited truncate's operand.
94  ///
95  /// \return minimum number of bits to which the chain ending with the
96  /// truncate's operand can be shrunk to.
97  unsigned getMinBitWidth();
98 
99  /// Build an expression dag dominated by the current processed TruncInst and
100  /// Check if it is eligible to be reduced to a smaller type.
101  ///
102  /// \return the scalar version of the new type to be used for the reduced
103  /// expression dag, or nullptr if the expression dag is not eligible
104  /// to be reduced.
105  Type *getBestTruncatedType();
106 
107  /// Given a \p V value and a \p SclTy scalar type return the generated reduced
108  /// value of \p V based on the type \p SclTy.
109  ///
110  /// \param V value to be reduced.
111  /// \param SclTy scalar version of new type to reduce to.
112  /// \return the new reduced value.
113  Value *getReducedOperand(Value *V, Type *SclTy);
114 
115  /// Create a new expression dag using the reduced /p SclTy type and replace
116  /// the old expression dag with it. Also erase all instructions in the old
117  /// dag, except those that are still needed outside the dag.
118  ///
119  /// \param SclTy scalar version of new type to reduce expression dag into.
120  void ReduceExpressionDag(Type *SclTy);
121 };
122 } // end namespace llvm.
123 
124 #endif
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:37
F(f)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
This class represents a truncation of integer types.
Analysis containing CSE Info
Definition: CSEInfo.cpp:25
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
bool run(Function &F)
Perform TruncInst pattern optimization on given function.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
Provides information about what library functions are available for the current target.
LLVM Value Representation.
Definition: Value.h:74
TruncInstCombine(TargetLibraryInfo &TLI, const DataLayout &DL, const DominatorTree &DT)