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