1 //===- ConstantHoisting.cpp - Prepare code for expensive constants --------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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.
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.
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.
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 //===----------------------------------------------------------------------===//
36 #include "llvm/Transforms/Scalar.h"
37 #include "llvm/ADT/SmallSet.h"
38 #include "llvm/ADT/SmallVector.h"
39 #include "llvm/ADT/Statistic.h"
40 #include "llvm/Analysis/TargetTransformInfo.h"
41 #include "llvm/IR/Constants.h"
42 #include "llvm/IR/Dominators.h"
43 #include "llvm/IR/IntrinsicInst.h"
44 #include "llvm/Pass.h"
45 #include "llvm/Support/Debug.h"
50 #define DEBUG_TYPE "consthoist"
52 STATISTIC(NumConstantsHoisted
, "Number of constants hoisted");
53 STATISTIC(NumConstantsRebased
, "Number of constants rebased");
57 struct RebasedConstantInfo
;
59 typedef SmallVector
<ConstantUser
, 8> ConstantUseListType
;
60 typedef SmallVector
<RebasedConstantInfo
, 4> RebasedConstantListType
;
62 /// \brief Keeps track of the user of a constant and the operand index where the
68 ConstantUser(Instruction
*Inst
, unsigned Idx
) : Inst(Inst
), OpndIdx(Idx
) { }
71 /// \brief Keeps track of a constant candidate and its uses.
72 struct ConstantCandidate
{
73 ConstantUseListType Uses
;
74 ConstantInt
*ConstInt
;
75 unsigned CumulativeCost
;
77 ConstantCandidate(ConstantInt
*ConstInt
)
78 : ConstInt(ConstInt
), CumulativeCost(0) { }
80 /// \brief Add the user to the use list and update the cost.
81 void addUser(Instruction
*Inst
, unsigned Idx
, unsigned Cost
) {
82 CumulativeCost
+= Cost
;
83 Uses
.push_back(ConstantUser(Inst
, Idx
));
87 /// \brief This represents a constant that has been rebased with respect to a
88 /// base constant. The difference to the base constant is recorded in Offset.
89 struct RebasedConstantInfo
{
90 ConstantUseListType Uses
;
93 RebasedConstantInfo(ConstantUseListType
&&Uses
, Constant
*Offset
)
94 : Uses(std::move(Uses
)), Offset(Offset
) { }
97 /// \brief A base constant and all its rebased constants.
99 ConstantInt
*BaseConstant
;
100 RebasedConstantListType RebasedConstants
;
103 /// \brief The constant hoisting pass.
104 class ConstantHoisting
: public FunctionPass
{
105 typedef DenseMap
<ConstantInt
*, unsigned> ConstCandMapType
;
106 typedef std::vector
<ConstantCandidate
> ConstCandVecType
;
108 const TargetTransformInfo
*TTI
;
112 /// Keeps track of constant candidates found in the function.
113 ConstCandVecType ConstCandVec
;
115 /// Keep track of cast instructions we already cloned.
116 SmallDenseMap
<Instruction
*, Instruction
*> ClonedCastMap
;
118 /// These are the final constants we decided to hoist.
119 SmallVector
<ConstantInfo
, 8> ConstantVec
;
121 static char ID
; // Pass identification, replacement for typeid
122 ConstantHoisting() : FunctionPass(ID
), TTI(nullptr), DT(nullptr),
124 initializeConstantHoistingPass(*PassRegistry::getPassRegistry());
127 bool runOnFunction(Function
&Fn
) override
;
129 const char *getPassName() const override
{ return "Constant Hoisting"; }
131 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
132 AU
.setPreservesCFG();
133 AU
.addRequired
<DominatorTreeWrapperPass
>();
134 AU
.addRequired
<TargetTransformInfo
>();
138 /// \brief Initialize the pass.
139 void setup(Function
&Fn
) {
140 DT
= &getAnalysis
<DominatorTreeWrapperPass
>().getDomTree();
141 TTI
= &getAnalysis
<TargetTransformInfo
>();
142 Entry
= &Fn
.getEntryBlock();
148 ClonedCastMap
.clear();
149 ConstCandVec
.clear();
156 Instruction
*findMatInsertPt(Instruction
*Inst
, unsigned Idx
= ~0U) const;
157 Instruction
*findConstantInsertionPoint(const ConstantInfo
&ConstInfo
) const;
158 void collectConstantCandidates(ConstCandMapType
&ConstCandMap
,
159 Instruction
*Inst
, unsigned Idx
,
160 ConstantInt
*ConstInt
);
161 void collectConstantCandidates(ConstCandMapType
&ConstCandMap
,
163 void collectConstantCandidates(Function
&Fn
);
164 void findAndMakeBaseConstant(ConstCandVecType::iterator S
,
165 ConstCandVecType::iterator E
);
166 void findBaseConstants();
167 void emitBaseConstants(Instruction
*Base
, Constant
*Offset
,
168 const ConstantUser
&ConstUser
);
169 bool emitBaseConstants();
170 void deleteDeadCastInst() const;
171 bool optimizeConstants(Function
&Fn
);
175 char ConstantHoisting::ID
= 0;
176 INITIALIZE_PASS_BEGIN(ConstantHoisting
, "consthoist", "Constant Hoisting",
178 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass
)
179 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo
)
180 INITIALIZE_PASS_END(ConstantHoisting
, "consthoist", "Constant Hoisting",
183 FunctionPass
*llvm::createConstantHoistingPass() {
184 return new ConstantHoisting();
187 /// \brief Perform the constant hoisting optimization for the given function.
188 bool ConstantHoisting::runOnFunction(Function
&Fn
) {
189 DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
190 DEBUG(dbgs() << "********** Function: " << Fn
.getName() << '\n');
194 bool MadeChange
= optimizeConstants(Fn
);
197 DEBUG(dbgs() << "********** Function after Constant Hoisting: "
198 << Fn
.getName() << '\n');
201 DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
209 /// \brief Find the constant materialization insertion point.
210 Instruction
*ConstantHoisting::findMatInsertPt(Instruction
*Inst
,
211 unsigned Idx
) const {
212 // If the operand is a cast instruction, then we have to materialize the
213 // constant before the cast instruction.
215 Value
*Opnd
= Inst
->getOperand(Idx
);
216 if (auto CastInst
= dyn_cast
<Instruction
>(Opnd
))
217 if (CastInst
->isCast())
221 // The simple and common case. This also includes constant expressions.
222 if (!isa
<PHINode
>(Inst
) && !isa
<LandingPadInst
>(Inst
))
225 // We can't insert directly before a phi node or landing pad. Insert before
226 // the terminator of the incoming or dominating block.
227 assert(Entry
!= Inst
->getParent() && "PHI or landing pad in entry block!");
228 if (Idx
!= ~0U && isa
<PHINode
>(Inst
))
229 return cast
<PHINode
>(Inst
)->getIncomingBlock(Idx
)->getTerminator();
231 BasicBlock
*IDom
= DT
->getNode(Inst
->getParent())->getIDom()->getBlock();
232 return IDom
->getTerminator();
235 /// \brief Find an insertion point that dominates all uses.
236 Instruction
*ConstantHoisting::
237 findConstantInsertionPoint(const ConstantInfo
&ConstInfo
) const {
238 assert(!ConstInfo
.RebasedConstants
.empty() && "Invalid constant info entry.");
239 // Collect all basic blocks.
240 SmallPtrSet
<BasicBlock
*, 8> BBs
;
241 for (auto const &RCI
: ConstInfo
.RebasedConstants
)
242 for (auto const &U
: RCI
.Uses
)
243 BBs
.insert(findMatInsertPt(U
.Inst
, U
.OpndIdx
)->getParent());
245 if (BBs
.count(Entry
))
246 return &Entry
->front();
248 while (BBs
.size() >= 2) {
249 BasicBlock
*BB
, *BB1
, *BB2
;
251 BB2
= *std::next(BBs
.begin());
252 BB
= DT
->findNearestCommonDominator(BB1
, BB2
);
254 return &Entry
->front();
259 assert((BBs
.size() == 1) && "Expected only one element.");
260 Instruction
&FirstInst
= (*BBs
.begin())->front();
261 return findMatInsertPt(&FirstInst
);
265 /// \brief Record constant integer ConstInt for instruction Inst at operand
268 /// The operand at index Idx is not necessarily the constant integer itself. It
269 /// could also be a cast instruction or a constant expression that uses the
271 void ConstantHoisting::collectConstantCandidates(ConstCandMapType
&ConstCandMap
,
274 ConstantInt
*ConstInt
) {
276 // Ask the target about the cost of materializing the constant for the given
277 // instruction and operand index.
278 if (auto IntrInst
= dyn_cast
<IntrinsicInst
>(Inst
))
279 Cost
= TTI
->getIntImmCost(IntrInst
->getIntrinsicID(), Idx
,
280 ConstInt
->getValue(), ConstInt
->getType());
282 Cost
= TTI
->getIntImmCost(Inst
->getOpcode(), Idx
, ConstInt
->getValue(),
283 ConstInt
->getType());
285 // Ignore cheap integer constants.
286 if (Cost
> TargetTransformInfo::TCC_Basic
) {
287 ConstCandMapType::iterator Itr
;
289 std::tie(Itr
, Inserted
) = ConstCandMap
.insert(std::make_pair(ConstInt
, 0));
291 ConstCandVec
.push_back(ConstantCandidate(ConstInt
));
292 Itr
->second
= ConstCandVec
.size() - 1;
294 ConstCandVec
[Itr
->second
].addUser(Inst
, Idx
, Cost
);
295 DEBUG(if (isa
<ConstantInt
>(Inst
->getOperand(Idx
)))
296 dbgs() << "Collect constant " << *ConstInt
<< " from " << *Inst
297 << " with cost " << Cost
<< '\n';
299 dbgs() << "Collect constant " << *ConstInt
<< " indirectly from "
300 << *Inst
<< " via " << *Inst
->getOperand(Idx
) << " with cost "
306 /// \brief Scan the instruction for expensive integer constants and record them
307 /// in the constant candidate vector.
308 void ConstantHoisting::collectConstantCandidates(ConstCandMapType
&ConstCandMap
,
310 // Skip all cast instructions. They are visited indirectly later on.
314 // Can't handle inline asm. Skip it.
315 if (auto Call
= dyn_cast
<CallInst
>(Inst
))
316 if (isa
<InlineAsm
>(Call
->getCalledValue()))
319 // Scan all operands.
320 for (unsigned Idx
= 0, E
= Inst
->getNumOperands(); Idx
!= E
; ++Idx
) {
321 Value
*Opnd
= Inst
->getOperand(Idx
);
323 // Visit constant integers.
324 if (auto ConstInt
= dyn_cast
<ConstantInt
>(Opnd
)) {
325 collectConstantCandidates(ConstCandMap
, Inst
, Idx
, ConstInt
);
329 // Visit cast instructions that have constant integers.
330 if (auto CastInst
= dyn_cast
<Instruction
>(Opnd
)) {
331 // Only visit cast instructions, which have been skipped. All other
332 // instructions should have already been visited.
333 if (!CastInst
->isCast())
336 if (auto *ConstInt
= dyn_cast
<ConstantInt
>(CastInst
->getOperand(0))) {
337 // Pretend the constant is directly used by the instruction and ignore
338 // the cast instruction.
339 collectConstantCandidates(ConstCandMap
, Inst
, Idx
, ConstInt
);
344 // Visit constant expressions that have constant integers.
345 if (auto ConstExpr
= dyn_cast
<ConstantExpr
>(Opnd
)) {
346 // Only visit constant cast expressions.
347 if (!ConstExpr
->isCast())
350 if (auto ConstInt
= dyn_cast
<ConstantInt
>(ConstExpr
->getOperand(0))) {
351 // Pretend the constant is directly used by the instruction and ignore
352 // the constant expression.
353 collectConstantCandidates(ConstCandMap
, Inst
, Idx
, ConstInt
);
357 } // end of for all operands
360 /// \brief Collect all integer constants in the function that cannot be folded
361 /// into an instruction itself.
362 void ConstantHoisting::collectConstantCandidates(Function
&Fn
) {
363 ConstCandMapType ConstCandMap
;
364 for (Function::iterator BB
: Fn
)
365 for (BasicBlock::iterator Inst
: *BB
)
366 collectConstantCandidates(ConstCandMap
, Inst
);
369 /// \brief Find the base constant within the given range and rebase all other
370 /// constants with respect to the base constant.
371 void ConstantHoisting::findAndMakeBaseConstant(ConstCandVecType::iterator S
,
372 ConstCandVecType::iterator E
) {
374 unsigned NumUses
= 0;
375 // Use the constant that has the maximum cost as base constant.
376 for (auto ConstCand
= S
; ConstCand
!= E
; ++ConstCand
) {
377 NumUses
+= ConstCand
->Uses
.size();
378 if (ConstCand
->CumulativeCost
> MaxCostItr
->CumulativeCost
)
379 MaxCostItr
= ConstCand
;
382 // Don't hoist constants that have only one use.
386 ConstantInfo ConstInfo
;
387 ConstInfo
.BaseConstant
= MaxCostItr
->ConstInt
;
388 Type
*Ty
= ConstInfo
.BaseConstant
->getType();
390 // Rebase the constants with respect to the base constant.
391 for (auto ConstCand
= S
; ConstCand
!= E
; ++ConstCand
) {
392 APInt Diff
= ConstCand
->ConstInt
->getValue() -
393 ConstInfo
.BaseConstant
->getValue();
394 Constant
*Offset
= Diff
== 0 ? nullptr : ConstantInt::get(Ty
, Diff
);
395 ConstInfo
.RebasedConstants
.push_back(
396 RebasedConstantInfo(std::move(ConstCand
->Uses
), Offset
));
398 ConstantVec
.push_back(std::move(ConstInfo
));
401 /// \brief Finds and combines constant candidates that can be easily
402 /// rematerialized with an add from a common base constant.
403 void ConstantHoisting::findBaseConstants() {
404 // Sort the constants by value and type. This invalidates the mapping!
405 std::sort(ConstCandVec
.begin(), ConstCandVec
.end(),
406 [](const ConstantCandidate
&LHS
, const ConstantCandidate
&RHS
) {
407 if (LHS
.ConstInt
->getType() != RHS
.ConstInt
->getType())
408 return LHS
.ConstInt
->getType()->getBitWidth() <
409 RHS
.ConstInt
->getType()->getBitWidth();
410 return LHS
.ConstInt
->getValue().ult(RHS
.ConstInt
->getValue());
413 // Simple linear scan through the sorted constant candidate vector for viable
415 auto MinValItr
= ConstCandVec
.begin();
416 for (auto CC
= std::next(ConstCandVec
.begin()), E
= ConstCandVec
.end();
418 if (MinValItr
->ConstInt
->getType() == CC
->ConstInt
->getType()) {
419 // Check if the constant is in range of an add with immediate.
420 APInt Diff
= CC
->ConstInt
->getValue() - MinValItr
->ConstInt
->getValue();
421 if ((Diff
.getBitWidth() <= 64) &&
422 TTI
->isLegalAddImmediate(Diff
.getSExtValue()))
425 // We either have now a different constant type or the constant is not in
426 // range of an add with immediate anymore.
427 findAndMakeBaseConstant(MinValItr
, CC
);
428 // Start a new base constant search.
431 // Finalize the last base constant search.
432 findAndMakeBaseConstant(MinValItr
, ConstCandVec
.end());
435 /// \brief Updates the operand at Idx in instruction Inst with the result of
436 /// instruction Mat. If the instruction is a PHI node then special
437 /// handling for duplicate values form the same incomming basic block is
439 /// \return The update will always succeed, but the return value indicated if
440 /// Mat was used for the update or not.
441 static bool updateOperand(Instruction
*Inst
, unsigned Idx
, Instruction
*Mat
) {
442 if (auto PHI
= dyn_cast
<PHINode
>(Inst
)) {
443 // Check if any previous operand of the PHI node has the same incoming basic
444 // block. This is a very odd case that happens when the incoming basic block
445 // has a switch statement. In this case use the same value as the previous
446 // operand(s), otherwise we will fail verification due to different values.
447 // The values are actually the same, but the variable names are different
448 // and the verifier doesn't like that.
449 BasicBlock
*IncomingBB
= PHI
->getIncomingBlock(Idx
);
450 for (unsigned i
= 0; i
< Idx
; ++i
) {
451 if (PHI
->getIncomingBlock(i
) == IncomingBB
) {
452 Value
*IncomingVal
= PHI
->getIncomingValue(i
);
453 Inst
->setOperand(Idx
, IncomingVal
);
459 Inst
->setOperand(Idx
, Mat
);
463 /// \brief Emit materialization code for all rebased constants and update their
465 void ConstantHoisting::emitBaseConstants(Instruction
*Base
, Constant
*Offset
,
466 const ConstantUser
&ConstUser
) {
467 Instruction
*Mat
= Base
;
469 Instruction
*InsertionPt
= findMatInsertPt(ConstUser
.Inst
,
471 Mat
= BinaryOperator::Create(Instruction::Add
, Base
, Offset
,
472 "const_mat", InsertionPt
);
474 DEBUG(dbgs() << "Materialize constant (" << *Base
->getOperand(0)
475 << " + " << *Offset
<< ") in BB "
476 << Mat
->getParent()->getName() << '\n' << *Mat
<< '\n');
477 Mat
->setDebugLoc(ConstUser
.Inst
->getDebugLoc());
479 Value
*Opnd
= ConstUser
.Inst
->getOperand(ConstUser
.OpndIdx
);
481 // Visit constant integer.
482 if (isa
<ConstantInt
>(Opnd
)) {
483 DEBUG(dbgs() << "Update: " << *ConstUser
.Inst
<< '\n');
484 if (!updateOperand(ConstUser
.Inst
, ConstUser
.OpndIdx
, Mat
) && Offset
)
485 Mat
->eraseFromParent();
486 DEBUG(dbgs() << "To : " << *ConstUser
.Inst
<< '\n');
490 // Visit cast instruction.
491 if (auto CastInst
= dyn_cast
<Instruction
>(Opnd
)) {
492 assert(CastInst
->isCast() && "Expected an cast instruction!");
493 // Check if we already have visited this cast instruction before to avoid
494 // unnecessary cloning.
495 Instruction
*&ClonedCastInst
= ClonedCastMap
[CastInst
];
496 if (!ClonedCastInst
) {
497 ClonedCastInst
= CastInst
->clone();
498 ClonedCastInst
->setOperand(0, Mat
);
499 ClonedCastInst
->insertAfter(CastInst
);
500 // Use the same debug location as the original cast instruction.
501 ClonedCastInst
->setDebugLoc(CastInst
->getDebugLoc());
502 DEBUG(dbgs() << "Clone instruction: " << *CastInst
<< '\n'
503 << "To : " << *ClonedCastInst
<< '\n');
506 DEBUG(dbgs() << "Update: " << *ConstUser
.Inst
<< '\n');
507 updateOperand(ConstUser
.Inst
, ConstUser
.OpndIdx
, ClonedCastInst
);
508 DEBUG(dbgs() << "To : " << *ConstUser
.Inst
<< '\n');
512 // Visit constant expression.
513 if (auto ConstExpr
= dyn_cast
<ConstantExpr
>(Opnd
)) {
514 Instruction
*ConstExprInst
= ConstExpr
->getAsInstruction();
515 ConstExprInst
->setOperand(0, Mat
);
516 ConstExprInst
->insertBefore(findMatInsertPt(ConstUser
.Inst
,
519 // Use the same debug location as the instruction we are about to update.
520 ConstExprInst
->setDebugLoc(ConstUser
.Inst
->getDebugLoc());
522 DEBUG(dbgs() << "Create instruction: " << *ConstExprInst
<< '\n'
523 << "From : " << *ConstExpr
<< '\n');
524 DEBUG(dbgs() << "Update: " << *ConstUser
.Inst
<< '\n');
525 if (!updateOperand(ConstUser
.Inst
, ConstUser
.OpndIdx
, ConstExprInst
)) {
526 ConstExprInst
->eraseFromParent();
528 Mat
->eraseFromParent();
530 DEBUG(dbgs() << "To : " << *ConstUser
.Inst
<< '\n');
535 /// \brief Hoist and hide the base constant behind a bitcast and emit
536 /// materialization code for derived constants.
537 bool ConstantHoisting::emitBaseConstants() {
538 bool MadeChange
= false;
539 for (auto const &ConstInfo
: ConstantVec
) {
540 // Hoist and hide the base constant behind a bitcast.
541 Instruction
*IP
= findConstantInsertionPoint(ConstInfo
);
542 IntegerType
*Ty
= ConstInfo
.BaseConstant
->getType();
544 new BitCastInst(ConstInfo
.BaseConstant
, Ty
, "const", IP
);
545 DEBUG(dbgs() << "Hoist constant (" << *ConstInfo
.BaseConstant
<< ") to BB "
546 << IP
->getParent()->getName() << '\n' << *Base
<< '\n');
547 NumConstantsHoisted
++;
549 // Emit materialization code for all rebased constants.
550 for (auto const &RCI
: ConstInfo
.RebasedConstants
) {
551 NumConstantsRebased
++;
552 for (auto const &U
: RCI
.Uses
)
553 emitBaseConstants(Base
, RCI
.Offset
, U
);
556 // Use the same debug location as the last user of the constant.
557 assert(!Base
->use_empty() && "The use list is empty!?");
558 assert(isa
<Instruction
>(Base
->user_back()) &&
559 "All uses should be instructions.");
560 Base
->setDebugLoc(cast
<Instruction
>(Base
->user_back())->getDebugLoc());
562 // Correct for base constant, which we counted above too.
563 NumConstantsRebased
--;
569 /// \brief Check all cast instructions we made a copy of and remove them if they
570 /// have no more users.
571 void ConstantHoisting::deleteDeadCastInst() const {
572 for (auto const &I
: ClonedCastMap
)
573 if (I
.first
->use_empty())
574 I
.first
->eraseFromParent();
577 /// \brief Optimize expensive integer constants in the given function.
578 bool ConstantHoisting::optimizeConstants(Function
&Fn
) {
579 // Collect all constant candidates.
580 collectConstantCandidates(Fn
);
582 // There are no constant candidates to worry about.
583 if (ConstCandVec
.empty())
586 // Combine constants that can be easily materialized with an add from a common
590 // There are no constants to emit.
591 if (ConstantVec
.empty())
594 // Finally hoist the base constant and emit materialization code for dependent
596 bool MadeChange
= emitBaseConstants();
598 // Cleanup dead instructions.
599 deleteDeadCastInst();