Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Transforms/Scalar/ConstantHoisting.h
Line
Count
Source
1
//==- ConstantHoisting.h - Prepare code for expensive constants --*- C++ -*-==//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// This pass identifies expensive constants to hoist and coalesces them to
11
// better prepare it for SelectionDAG-based code generation. This works around
12
// the limitations of the basic-block-at-a-time approach.
13
//
14
// First it scans all instructions for integer constants and calculates its
15
// cost. If the constant can be folded into the instruction (the cost is
16
// TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
17
// consider it expensive and leave it alone. This is the default behavior and
18
// the default implementation of getIntImmCost will always return TCC_Free.
19
//
20
// If the cost is more than TCC_BASIC, then the integer constant can't be folded
21
// into the instruction and it might be beneficial to hoist the constant.
22
// Similar constants are coalesced to reduce register pressure and
23
// materialization code.
24
//
25
// When a constant is hoisted, it is also hidden behind a bitcast to force it to
26
// be live-out of the basic block. Otherwise the constant would be just
27
// duplicated and each basic block would have its own copy in the SelectionDAG.
28
// The SelectionDAG recognizes such constants as opaque and doesn't perform
29
// certain transformations on them, which would create a new expensive constant.
30
//
31
// This optimization is only applied to integer constants in instructions and
32
// simple (this means not nested) constant cast expressions. For example:
33
// %0 = load i64* inttoptr (i64 big_constant to i64*)
34
//
35
//===----------------------------------------------------------------------===//
36
37
#ifndef LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
38
#define LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H
39
40
#include "llvm/ADT/DenseMap.h"
41
#include "llvm/ADT/SmallPtrSet.h"
42
#include "llvm/ADT/SmallVector.h"
43
#include "llvm/IR/PassManager.h"
44
#include <algorithm>
45
#include <vector>
46
47
namespace llvm {
48
49
class BasicBlock;
50
class BlockFrequencyInfo;
51
class Constant;
52
class ConstantInt;
53
class DominatorTree;
54
class Function;
55
class Instruction;
56
class TargetTransformInfo;
57
58
/// A private "module" namespace for types and utilities used by
59
/// ConstantHoisting. These are implementation details and should not be used by
60
/// clients.
61
namespace consthoist {
62
63
/// \brief Keeps track of the user of a constant and the operand index where the
64
/// constant is used.
65
struct ConstantUser {
66
  Instruction *Inst;
67
  unsigned OpndIdx;
68
69
58.0k
  ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) {}
70
};
71
72
using ConstantUseListType = SmallVector<ConstantUser, 8>;
73
74
/// \brief Keeps track of a constant candidate and its uses.
75
struct ConstantCandidate {
76
  ConstantUseListType Uses;
77
  ConstantInt *ConstInt;
78
  unsigned CumulativeCost = 0;
79
80
29.1k
  ConstantCandidate(ConstantInt *ConstInt) : ConstInt(ConstInt) {}
81
82
  /// \brief Add the user to the use list and update the cost.
83
58.0k
  void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
84
58.0k
    CumulativeCost += Cost;
85
58.0k
    Uses.push_back(ConstantUser(Inst, Idx));
86
58.0k
  }
87
};
88
89
/// \brief This represents a constant that has been rebased with respect to a
90
/// base constant. The difference to the base constant is recorded in Offset.
91
struct RebasedConstantInfo {
92
  ConstantUseListType Uses;
93
  Constant *Offset;
94
95
  RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
96
12.3k
    : Uses(std::move(Uses)), Offset(Offset) {}
97
};
98
99
using RebasedConstantListType = SmallVector<RebasedConstantInfo, 4>;
100
101
/// \brief A base constant and all its rebased constants.
102
struct ConstantInfo {
103
  ConstantInt *BaseConstant;
104
  RebasedConstantListType RebasedConstants;
105
};
106
107
} // end namespace consthoist
108
109
class ConstantHoistingPass : public PassInfoMixin<ConstantHoistingPass> {
110
public:
111
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
112
113
  // Glue for old PM.
114
  bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT,
115
               BlockFrequencyInfo *BFI, BasicBlock &Entry);
116
117
588k
  void releaseMemory() {
118
588k
    ConstantVec.clear();
119
588k
    ClonedCastMap.clear();
120
588k
    ConstCandVec.clear();
121
588k
  }
122
123
private:
124
  using ConstCandMapType = DenseMap<ConstantInt *, unsigned>;
125
  using ConstCandVecType = std::vector<consthoist::ConstantCandidate>;
126
127
  const TargetTransformInfo *TTI;
128
  DominatorTree *DT;
129
  BlockFrequencyInfo *BFI;
130
  BasicBlock *Entry;
131
132
  /// Keeps track of constant candidates found in the function.
133
  ConstCandVecType ConstCandVec;
134
135
  /// Keep track of cast instructions we already cloned.
136
  SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
137
138
  /// These are the final constants we decided to hoist.
139
  SmallVector<consthoist::ConstantInfo, 8> ConstantVec;
140
141
  Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
142
  SmallPtrSet<Instruction *, 8>
143
  findConstantInsertionPoint(const consthoist::ConstantInfo &ConstInfo) const;
144
  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
145
                                 Instruction *Inst, unsigned Idx,
146
                                 ConstantInt *ConstInt);
147
  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
148
                                 Instruction *Inst, unsigned Idx);
149
  void collectConstantCandidates(ConstCandMapType &ConstCandMap,
150
                                 Instruction *Inst);
151
  void collectConstantCandidates(Function &Fn);
152
  void findAndMakeBaseConstant(ConstCandVecType::iterator S,
153
                               ConstCandVecType::iterator E);
154
  unsigned maximizeConstantsInRange(ConstCandVecType::iterator S,
155
                                    ConstCandVecType::iterator E,
156
                                    ConstCandVecType::iterator &MaxCostItr);
157
  void findBaseConstants();
158
  void emitBaseConstants(Instruction *Base, Constant *Offset,
159
                         const consthoist::ConstantUser &ConstUser);
160
  bool emitBaseConstants();
161
  void deleteDeadCastInst() const;
162
  bool optimizeConstants(Function &Fn);
163
};
164
165
} // end namespace llvm
166
167
#endif // LLVM_TRANSFORMS_SCALAR_CONSTANTHOISTING_H