Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombineInternal.h
Line
Count
Source
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
454k
      : 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