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"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/Analysis/BasicAliasAnalysis.h"
22 #include "llvm/Analysis/ConstantFolding.h"
23 #include "llvm/Analysis/GlobalsModRef.h"
24 #include "llvm/Analysis/TargetLibraryInfo.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 
52 class TruncInstCombine {
53   TargetLibraryInfo &TLI;
54   const DataLayout &DL;
55   const DominatorTree &DT;
56 
57   /// List of all TruncInst instructions to be processed.
58   SmallVector<TruncInst *, 4> Worklist;
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.
76   MapVector<Instruction *, Info> InstInfoMap;
77 
78 public:
79   TruncInstCombine(TargetLibraryInfo &TLI, const DataLayout &DL,
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
126