LLVM 19.0.0git
ConstantHoisting.cpp
Go to the documentation of this file.
1//===- ConstantHoisting.cpp - Prepare code for expensive constants --------===//
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 pass identifies expensive constants to hoist and coalesces them to
10// better prepare it for SelectionDAG-based code generation. This works around
11// the limitations of the basic-block-at-a-time approach.
12//
13// First it scans all instructions for integer constants and calculates its
14// cost. If the constant can be folded into the instruction (the cost is
15// TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
16// consider it expensive and leave it alone. This is the default behavior and
17// the default implementation of getIntImmCostInst will always return TCC_Free.
18//
19// If the cost is more than TCC_BASIC, then the integer constant can't be folded
20// into the instruction and it might be beneficial to hoist the constant.
21// Similar constants are coalesced to reduce register pressure and
22// materialization code.
23//
24// When a constant is hoisted, it is also hidden behind a bitcast to force it to
25// be live-out of the basic block. Otherwise the constant would be just
26// duplicated and each basic block would have its own copy in the SelectionDAG.
27// The SelectionDAG recognizes such constants as opaque and doesn't perform
28// certain transformations on them, which would create a new expensive constant.
29//
30// This optimization is only applied to integer constants in instructions and
31// simple (this means not nested) constant cast expressions. For example:
32// %0 = load i64* inttoptr (i64 big_constant to i64*)
33//===----------------------------------------------------------------------===//
34
36#include "llvm/ADT/APInt.h"
37#include "llvm/ADT/DenseMap.h"
40#include "llvm/ADT/Statistic.h"
44#include "llvm/IR/BasicBlock.h"
45#include "llvm/IR/Constants.h"
47#include "llvm/IR/Dominators.h"
48#include "llvm/IR/Function.h"
49#include "llvm/IR/InstrTypes.h"
50#include "llvm/IR/Instruction.h"
53#include "llvm/IR/Operator.h"
54#include "llvm/IR/Value.h"
56#include "llvm/Pass.h"
60#include "llvm/Support/Debug.h"
65#include <algorithm>
66#include <cassert>
67#include <cstdint>
68#include <iterator>
69#include <tuple>
70#include <utility>
71
72using namespace llvm;
73using namespace consthoist;
74
75#define DEBUG_TYPE "consthoist"
76
77STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
78STATISTIC(NumConstantsRebased, "Number of constants rebased");
79
81 "consthoist-with-block-frequency", cl::init(true), cl::Hidden,
82 cl::desc("Enable the use of the block frequency analysis to reduce the "
83 "chance to execute const materialization more frequently than "
84 "without hoisting."));
85
87 "consthoist-gep", cl::init(false), cl::Hidden,
88 cl::desc("Try hoisting constant gep expressions"));
89
91MinNumOfDependentToRebase("consthoist-min-num-to-rebase",
92 cl::desc("Do not rebase if number of dependent constants of a Base is less "
93 "than this number."),
95
96namespace {
97
98/// The constant hoisting pass.
99class ConstantHoistingLegacyPass : public FunctionPass {
100public:
101 static char ID; // Pass identification, replacement for typeid
102
103 ConstantHoistingLegacyPass() : FunctionPass(ID) {
105 }
106
107 bool runOnFunction(Function &Fn) override;
108
109 StringRef getPassName() const override { return "Constant Hoisting"; }
110
111 void getAnalysisUsage(AnalysisUsage &AU) const override {
112 AU.setPreservesCFG();
118 }
119
120private:
122};
123
124} // end anonymous namespace
125
126char ConstantHoistingLegacyPass::ID = 0;
127
128INITIALIZE_PASS_BEGIN(ConstantHoistingLegacyPass, "consthoist",
129 "Constant Hoisting", false, false)
134INITIALIZE_PASS_END(ConstantHoistingLegacyPass, "consthoist",
136
138 return new ConstantHoistingLegacyPass();
139}
140
141/// Perform the constant hoisting optimization for the given function.
142bool ConstantHoistingLegacyPass::runOnFunction(Function &Fn) {
143 if (skipFunction(Fn))
144 return false;
145
146 LLVM_DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
147 LLVM_DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
148
149 bool MadeChange =
150 Impl.runImpl(Fn, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn),
151 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
153 ? &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI()
154 : nullptr,
155 Fn.getEntryBlock(),
156 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
157
158 LLVM_DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
159
160 return MadeChange;
161}
162
163void ConstantHoistingPass::collectMatInsertPts(
164 const RebasedConstantListType &RebasedConstants,
165 SmallVectorImpl<BasicBlock::iterator> &MatInsertPts) const {
166 for (const RebasedConstantInfo &RCI : RebasedConstants)
167 for (const ConstantUser &U : RCI.Uses)
168 MatInsertPts.emplace_back(findMatInsertPt(U.Inst, U.OpndIdx));
169}
170
171/// Find the constant materialization insertion point.
172BasicBlock::iterator ConstantHoistingPass::findMatInsertPt(Instruction *Inst,
173 unsigned Idx) const {
174 // If the operand is a cast instruction, then we have to materialize the
175 // constant before the cast instruction.
176 if (Idx != ~0U) {
177 Value *Opnd = Inst->getOperand(Idx);
178 if (auto CastInst = dyn_cast<Instruction>(Opnd))
179 if (CastInst->isCast())
180 return CastInst->getIterator();
181 }
182
183 // The simple and common case. This also includes constant expressions.
184 if (!isa<PHINode>(Inst) && !Inst->isEHPad())
185 return Inst->getIterator();
186
187 // We can't insert directly before a phi node or an eh pad. Insert before
188 // the terminator of the incoming or dominating block.
189 assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!");
190 BasicBlock *InsertionBlock = nullptr;
191 if (Idx != ~0U && isa<PHINode>(Inst)) {
192 InsertionBlock = cast<PHINode>(Inst)->getIncomingBlock(Idx);
193 if (!InsertionBlock->isEHPad()) {
194 return InsertionBlock->getTerminator()->getIterator();
195 }
196 } else {
197 InsertionBlock = Inst->getParent();
198 }
199
200 // This must be an EH pad. Iterate over immediate dominators until we find a
201 // non-EH pad. We need to skip over catchswitch blocks, which are both EH pads
202 // and terminators.
203 auto *IDom = DT->getNode(InsertionBlock)->getIDom();
204 while (IDom->getBlock()->isEHPad()) {
205 assert(Entry != IDom->getBlock() && "eh pad in entry block");
206 IDom = IDom->getIDom();
207 }
208
209 return IDom->getBlock()->getTerminator()->getIterator();
210}
211
212/// Given \p BBs as input, find another set of BBs which collectively
213/// dominates \p BBs and have the minimal sum of frequencies. Return the BB
214/// set found in \p BBs.
216 BasicBlock *Entry,
218 assert(!BBs.count(Entry) && "Assume Entry is not in BBs");
219 // Nodes on the current path to the root.
221 // Candidates includes any block 'BB' in set 'BBs' that is not strictly
222 // dominated by any other blocks in set 'BBs', and all nodes in the path
223 // in the dominator tree from Entry to 'BB'.
225 for (auto *BB : BBs) {
226 // Ignore unreachable basic blocks.
227 if (!DT.isReachableFromEntry(BB))
228 continue;
229 Path.clear();
230 // Walk up the dominator tree until Entry or another BB in BBs
231 // is reached. Insert the nodes on the way to the Path.
232 BasicBlock *Node = BB;
233 // The "Path" is a candidate path to be added into Candidates set.
234 bool isCandidate = false;
235 do {
236 Path.insert(Node);
237 if (Node == Entry || Candidates.count(Node)) {
238 isCandidate = true;
239 break;
240 }
241 assert(DT.getNode(Node)->getIDom() &&
242 "Entry doens't dominate current Node");
243 Node = DT.getNode(Node)->getIDom()->getBlock();
244 } while (!BBs.count(Node));
245
246 // If isCandidate is false, Node is another Block in BBs dominating
247 // current 'BB'. Drop the nodes on the Path.
248 if (!isCandidate)
249 continue;
250
251 // Add nodes on the Path into Candidates.
252 Candidates.insert(Path.begin(), Path.end());
253 }
254
255 // Sort the nodes in Candidates in top-down order and save the nodes
256 // in Orders.
257 unsigned Idx = 0;
259 Orders.push_back(Entry);
260 while (Idx != Orders.size()) {
261 BasicBlock *Node = Orders[Idx++];
262 for (auto *ChildDomNode : DT.getNode(Node)->children()) {
263 if (Candidates.count(ChildDomNode->getBlock()))
264 Orders.push_back(ChildDomNode->getBlock());
265 }
266 }
267
268 // Visit Orders in bottom-up order.
269 using InsertPtsCostPair =
270 std::pair<SetVector<BasicBlock *>, BlockFrequency>;
271
272 // InsertPtsMap is a map from a BB to the best insertion points for the
273 // subtree of BB (subtree not including the BB itself).
275 InsertPtsMap.reserve(Orders.size() + 1);
276 for (BasicBlock *Node : llvm::reverse(Orders)) {
277 bool NodeInBBs = BBs.count(Node);
278 auto &InsertPts = InsertPtsMap[Node].first;
279 BlockFrequency &InsertPtsFreq = InsertPtsMap[Node].second;
280
281 // Return the optimal insert points in BBs.
282 if (Node == Entry) {
283 BBs.clear();
284 if (InsertPtsFreq > BFI.getBlockFreq(Node) ||
285 (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1))
286 BBs.insert(Entry);
287 else
288 BBs.insert(InsertPts.begin(), InsertPts.end());
289 break;
290 }
291
292 BasicBlock *Parent = DT.getNode(Node)->getIDom()->getBlock();
293 // Initially, ParentInsertPts is empty and ParentPtsFreq is 0. Every child
294 // will update its parent's ParentInsertPts and ParentPtsFreq.
295 auto &ParentInsertPts = InsertPtsMap[Parent].first;
296 BlockFrequency &ParentPtsFreq = InsertPtsMap[Parent].second;
297 // Choose to insert in Node or in subtree of Node.
298 // Don't hoist to EHPad because we may not find a proper place to insert
299 // in EHPad.
300 // If the total frequency of InsertPts is the same as the frequency of the
301 // target Node, and InsertPts contains more than one nodes, choose hoisting
302 // to reduce code size.
303 if (NodeInBBs ||
304 (!Node->isEHPad() &&
305 (InsertPtsFreq > BFI.getBlockFreq(Node) ||
306 (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1)))) {
307 ParentInsertPts.insert(Node);
308 ParentPtsFreq += BFI.getBlockFreq(Node);
309 } else {
310 ParentInsertPts.insert(InsertPts.begin(), InsertPts.end());
311 ParentPtsFreq += InsertPtsFreq;
312 }
313 }
314}
315
316/// Find an insertion point that dominates all uses.
318ConstantHoistingPass::findConstantInsertionPoint(
319 const ConstantInfo &ConstInfo,
320 const ArrayRef<BasicBlock::iterator> MatInsertPts) const {
321 assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
322 // Collect all basic blocks.
325
326 for (BasicBlock::iterator MatInsertPt : MatInsertPts)
327 BBs.insert(MatInsertPt->getParent());
328
329 if (BBs.count(Entry)) {
330 InsertPts.insert(Entry->begin());
331 return InsertPts;
332 }
333
334 if (BFI) {
335 findBestInsertionSet(*DT, *BFI, Entry, BBs);
336 for (BasicBlock *BB : BBs)
337 InsertPts.insert(BB->getFirstInsertionPt());
338 return InsertPts;
339 }
340
341 while (BBs.size() >= 2) {
342 BasicBlock *BB, *BB1, *BB2;
343 BB1 = BBs.pop_back_val();
344 BB2 = BBs.pop_back_val();
345 BB = DT->findNearestCommonDominator(BB1, BB2);
346 if (BB == Entry) {
347 InsertPts.insert(Entry->begin());
348 return InsertPts;
349 }
350 BBs.insert(BB);
351 }
352 assert((BBs.size() == 1) && "Expected only one element.");
353 Instruction &FirstInst = (*BBs.begin())->front();
354 InsertPts.insert(findMatInsertPt(&FirstInst));
355 return InsertPts;
356}
357
358/// Record constant integer ConstInt for instruction Inst at operand
359/// index Idx.
360///
361/// The operand at index Idx is not necessarily the constant integer itself. It
362/// could also be a cast instruction or a constant expression that uses the
363/// constant integer.
364void ConstantHoistingPass::collectConstantCandidates(
365 ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
366 ConstantInt *ConstInt) {
367 if (ConstInt->getType()->isVectorTy())
368 return;
369
371 // Ask the target about the cost of materializing the constant for the given
372 // instruction and operand index.
373 if (auto IntrInst = dyn_cast<IntrinsicInst>(Inst))
374 Cost = TTI->getIntImmCostIntrin(IntrInst->getIntrinsicID(), Idx,
375 ConstInt->getValue(), ConstInt->getType(),
377 else
379 Inst->getOpcode(), Idx, ConstInt->getValue(), ConstInt->getType(),
381
382 // Ignore cheap integer constants.
385 bool Inserted;
386 ConstPtrUnionType Cand = ConstInt;
387 std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
388 if (Inserted) {
389 ConstIntCandVec.push_back(ConstantCandidate(ConstInt));
390 Itr->second = ConstIntCandVec.size() - 1;
391 }
392 ConstIntCandVec[Itr->second].addUser(Inst, Idx, *Cost.getValue());
393 LLVM_DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx))) dbgs()
394 << "Collect constant " << *ConstInt << " from " << *Inst
395 << " with cost " << Cost << '\n';
396 else dbgs() << "Collect constant " << *ConstInt
397 << " indirectly from " << *Inst << " via "
398 << *Inst->getOperand(Idx) << " with cost " << Cost
399 << '\n';);
400 }
401}
402
403/// Record constant GEP expression for instruction Inst at operand index Idx.
404void ConstantHoistingPass::collectConstantCandidates(
405 ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
406 ConstantExpr *ConstExpr) {
407 // TODO: Handle vector GEPs
408 if (ConstExpr->getType()->isVectorTy())
409 return;
410
411 GlobalVariable *BaseGV = dyn_cast<GlobalVariable>(ConstExpr->getOperand(0));
412 if (!BaseGV)
413 return;
414
415 // Get offset from the base GV.
416 PointerType *GVPtrTy = cast<PointerType>(BaseGV->getType());
417 IntegerType *OffsetTy = DL->getIndexType(*Ctx, GVPtrTy->getAddressSpace());
418 APInt Offset(DL->getTypeSizeInBits(OffsetTy), /*val*/ 0, /*isSigned*/ true);
419 auto *GEPO = cast<GEPOperator>(ConstExpr);
420
421 // TODO: If we have a mix of inbounds and non-inbounds GEPs, then basing a
422 // non-inbounds GEP on an inbounds GEP is potentially incorrect. Restrict to
423 // inbounds GEP for now -- alternatively, we could drop inbounds from the
424 // constant expression,
425 if (!GEPO->isInBounds())
426 return;
427
428 if (!GEPO->accumulateConstantOffset(*DL, Offset))
429 return;
430
431 if (!Offset.isIntN(32))
432 return;
433
434 // A constant GEP expression that has a GlobalVariable as base pointer is
435 // usually lowered to a load from constant pool. Such operation is unlikely
436 // to be cheaper than compute it by <Base + Offset>, which can be lowered to
437 // an ADD instruction or folded into Load/Store instruction.
439 TTI->getIntImmCostInst(Instruction::Add, 1, Offset, OffsetTy,
441 ConstCandVecType &ExprCandVec = ConstGEPCandMap[BaseGV];
443 bool Inserted;
444 ConstPtrUnionType Cand = ConstExpr;
445 std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
446 if (Inserted) {
447 ExprCandVec.push_back(ConstantCandidate(
448 ConstantInt::get(Type::getInt32Ty(*Ctx), Offset.getLimitedValue()),
449 ConstExpr));
450 Itr->second = ExprCandVec.size() - 1;
451 }
452 ExprCandVec[Itr->second].addUser(Inst, Idx, *Cost.getValue());
453}
454
455/// Check the operand for instruction Inst at index Idx.
456void ConstantHoistingPass::collectConstantCandidates(
457 ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx) {
458 Value *Opnd = Inst->getOperand(Idx);
459
460 // Visit constant integers.
461 if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
462 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
463 return;
464 }
465
466 // Visit cast instructions that have constant integers.
467 if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
468 // Only visit cast instructions, which have been skipped. All other
469 // instructions should have already been visited.
470 if (!CastInst->isCast())
471 return;
472
473 if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
474 // Pretend the constant is directly used by the instruction and ignore
475 // the cast instruction.
476 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
477 return;
478 }
479 }
480
481 // Visit constant expressions that have constant integers.
482 if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
483 // Handle constant gep expressions.
484 if (ConstHoistGEP && isa<GEPOperator>(ConstExpr))
485 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstExpr);
486
487 // Only visit constant cast expressions.
488 if (!ConstExpr->isCast())
489 return;
490
491 if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
492 // Pretend the constant is directly used by the instruction and ignore
493 // the constant expression.
494 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
495 return;
496 }
497 }
498}
499
500/// Scan the instruction for expensive integer constants and record them
501/// in the constant candidate vector.
502void ConstantHoistingPass::collectConstantCandidates(
503 ConstCandMapType &ConstCandMap, Instruction *Inst) {
504 // Skip all cast instructions. They are visited indirectly later on.
505 if (Inst->isCast())
506 return;
507
508 // Scan all operands.
509 for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
510 // The cost of materializing the constants (defined in
511 // `TargetTransformInfo::getIntImmCostInst`) for instructions which only
512 // take constant variables is lower than `TargetTransformInfo::TCC_Basic`.
513 // So it's safe for us to collect constant candidates from all
514 // IntrinsicInsts.
516 collectConstantCandidates(ConstCandMap, Inst, Idx);
517 }
518 } // end of for all operands
519}
520
521/// Collect all integer constants in the function that cannot be folded
522/// into an instruction itself.
523void ConstantHoistingPass::collectConstantCandidates(Function &Fn) {
524 ConstCandMapType ConstCandMap;
525 for (BasicBlock &BB : Fn) {
526 // Ignore unreachable basic blocks.
527 if (!DT->isReachableFromEntry(&BB))
528 continue;
529 for (Instruction &Inst : BB)
530 if (!TTI->preferToKeepConstantsAttached(Inst, Fn))
531 collectConstantCandidates(ConstCandMap, &Inst);
532 }
533}
534
535// This helper function is necessary to deal with values that have different
536// bit widths (APInt Operator- does not like that). If the value cannot be
537// represented in uint64 we return an "empty" APInt. This is then interpreted
538// as the value is not in range.
539static std::optional<APInt> calculateOffsetDiff(const APInt &V1,
540 const APInt &V2) {
541 std::optional<APInt> Res;
542 unsigned BW = V1.getBitWidth() > V2.getBitWidth() ?
543 V1.getBitWidth() : V2.getBitWidth();
544 uint64_t LimVal1 = V1.getLimitedValue();
545 uint64_t LimVal2 = V2.getLimitedValue();
546
547 if (LimVal1 == ~0ULL || LimVal2 == ~0ULL)
548 return Res;
549
550 uint64_t Diff = LimVal1 - LimVal2;
551 return APInt(BW, Diff, true);
552}
553
554// From a list of constants, one needs to picked as the base and the other
555// constants will be transformed into an offset from that base constant. The
556// question is which we can pick best? For example, consider these constants
557// and their number of uses:
558//
559// Constants| 2 | 4 | 12 | 42 |
560// NumUses | 3 | 2 | 8 | 7 |
561//
562// Selecting constant 12 because it has the most uses will generate negative
563// offsets for constants 2 and 4 (i.e. -10 and -8 respectively). If negative
564// offsets lead to less optimal code generation, then there might be better
565// solutions. Suppose immediates in the range of 0..35 are most optimally
566// supported by the architecture, then selecting constant 2 is most optimal
567// because this will generate offsets: 0, 2, 10, 40. Offsets 0, 2 and 10 are in
568// range 0..35, and thus 3 + 2 + 8 = 13 uses are in range. Selecting 12 would
569// have only 8 uses in range, so choosing 2 as a base is more optimal. Thus, in
570// selecting the base constant the range of the offsets is a very important
571// factor too that we take into account here. This algorithm calculates a total
572// costs for selecting a constant as the base and substract the costs if
573// immediates are out of range. It has quadratic complexity, so we call this
574// function only when we're optimising for size and there are less than 100
575// constants, we fall back to the straightforward algorithm otherwise
576// which does not do all the offset calculations.
577unsigned
578ConstantHoistingPass::maximizeConstantsInRange(ConstCandVecType::iterator S,
579 ConstCandVecType::iterator E,
580 ConstCandVecType::iterator &MaxCostItr) {
581 unsigned NumUses = 0;
582
583 if (!OptForSize || std::distance(S,E) > 100) {
584 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
585 NumUses += ConstCand->Uses.size();
586 if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
587 MaxCostItr = ConstCand;
588 }
589 return NumUses;
590 }
591
592 LLVM_DEBUG(dbgs() << "== Maximize constants in range ==\n");
593 InstructionCost MaxCost = -1;
594 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
595 auto Value = ConstCand->ConstInt->getValue();
596 Type *Ty = ConstCand->ConstInt->getType();
598 NumUses += ConstCand->Uses.size();
599 LLVM_DEBUG(dbgs() << "= Constant: " << ConstCand->ConstInt->getValue()
600 << "\n");
601
602 for (auto User : ConstCand->Uses) {
603 unsigned Opcode = User.Inst->getOpcode();
604 unsigned OpndIdx = User.OpndIdx;
605 Cost += TTI->getIntImmCostInst(Opcode, OpndIdx, Value, Ty,
607 LLVM_DEBUG(dbgs() << "Cost: " << Cost << "\n");
608
609 for (auto C2 = S; C2 != E; ++C2) {
610 std::optional<APInt> Diff = calculateOffsetDiff(
611 C2->ConstInt->getValue(), ConstCand->ConstInt->getValue());
612 if (Diff) {
613 const InstructionCost ImmCosts =
614 TTI->getIntImmCodeSizeCost(Opcode, OpndIdx, *Diff, Ty);
615 Cost -= ImmCosts;
616 LLVM_DEBUG(dbgs() << "Offset " << *Diff << " "
617 << "has penalty: " << ImmCosts << "\n"
618 << "Adjusted cost: " << Cost << "\n");
619 }
620 }
621 }
622 LLVM_DEBUG(dbgs() << "Cumulative cost: " << Cost << "\n");
623 if (Cost > MaxCost) {
624 MaxCost = Cost;
625 MaxCostItr = ConstCand;
626 LLVM_DEBUG(dbgs() << "New candidate: " << MaxCostItr->ConstInt->getValue()
627 << "\n");
628 }
629 }
630 return NumUses;
631}
632
633/// Find the base constant within the given range and rebase all other
634/// constants with respect to the base constant.
635void ConstantHoistingPass::findAndMakeBaseConstant(
636 ConstCandVecType::iterator S, ConstCandVecType::iterator E,
638 auto MaxCostItr = S;
639 unsigned NumUses = maximizeConstantsInRange(S, E, MaxCostItr);
640
641 // Don't hoist constants that have only one use.
642 if (NumUses <= 1)
643 return;
644
645 ConstantInt *ConstInt = MaxCostItr->ConstInt;
646 ConstantExpr *ConstExpr = MaxCostItr->ConstExpr;
647 ConstantInfo ConstInfo;
648 ConstInfo.BaseInt = ConstInt;
649 ConstInfo.BaseExpr = ConstExpr;
650 Type *Ty = ConstInt->getType();
651
652 // Rebase the constants with respect to the base constant.
653 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
654 APInt Diff = ConstCand->ConstInt->getValue() - ConstInt->getValue();
655 Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
656 Type *ConstTy =
657 ConstCand->ConstExpr ? ConstCand->ConstExpr->getType() : nullptr;
658 ConstInfo.RebasedConstants.push_back(
659 RebasedConstantInfo(std::move(ConstCand->Uses), Offset, ConstTy));
660 }
661 ConstInfoVec.push_back(std::move(ConstInfo));
662}
663
664/// Finds and combines constant candidates that can be easily
665/// rematerialized with an add from a common base constant.
666void ConstantHoistingPass::findBaseConstants(GlobalVariable *BaseGV) {
667 // If BaseGV is nullptr, find base among candidate constant integers;
668 // Otherwise find base among constant GEPs that share the same BaseGV.
669 ConstCandVecType &ConstCandVec = BaseGV ?
670 ConstGEPCandMap[BaseGV] : ConstIntCandVec;
671 ConstInfoVecType &ConstInfoVec = BaseGV ?
672 ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
673
674 // Sort the constants by value and type. This invalidates the mapping!
675 llvm::stable_sort(ConstCandVec, [](const ConstantCandidate &LHS,
676 const ConstantCandidate &RHS) {
677 if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
678 return LHS.ConstInt->getBitWidth() < RHS.ConstInt->getBitWidth();
679 return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
680 });
681
682 // Simple linear scan through the sorted constant candidate vector for viable
683 // merge candidates.
684 auto MinValItr = ConstCandVec.begin();
685 for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
686 CC != E; ++CC) {
687 if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
688 Type *MemUseValTy = nullptr;
689 for (auto &U : CC->Uses) {
690 auto *UI = U.Inst;
691 if (LoadInst *LI = dyn_cast<LoadInst>(UI)) {
692 MemUseValTy = LI->getType();
693 break;
694 } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
695 // Make sure the constant is used as pointer operand of the StoreInst.
696 if (SI->getPointerOperand() == SI->getOperand(U.OpndIdx)) {
697 MemUseValTy = SI->getValueOperand()->getType();
698 break;
699 }
700 }
701 }
702
703 // Check if the constant is in range of an add with immediate.
704 APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
705 if ((Diff.getBitWidth() <= 64) &&
707 // Check if Diff can be used as offset in addressing mode of the user
708 // memory instruction.
709 (!MemUseValTy || TTI->isLegalAddressingMode(MemUseValTy,
710 /*BaseGV*/nullptr, /*BaseOffset*/Diff.getSExtValue(),
711 /*HasBaseReg*/true, /*Scale*/0)))
712 continue;
713 }
714 // We either have now a different constant type or the constant is not in
715 // range of an add with immediate anymore.
716 findAndMakeBaseConstant(MinValItr, CC, ConstInfoVec);
717 // Start a new base constant search.
718 MinValItr = CC;
719 }
720 // Finalize the last base constant search.
721 findAndMakeBaseConstant(MinValItr, ConstCandVec.end(), ConstInfoVec);
722}
723
724/// Updates the operand at Idx in instruction Inst with the result of
725/// instruction Mat. If the instruction is a PHI node then special
726/// handling for duplicate values from the same incoming basic block is
727/// required.
728/// \return The update will always succeed, but the return value indicated if
729/// Mat was used for the update or not.
730static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
731 if (auto PHI = dyn_cast<PHINode>(Inst)) {
732 // Check if any previous operand of the PHI node has the same incoming basic
733 // block. This is a very odd case that happens when the incoming basic block
734 // has a switch statement. In this case use the same value as the previous
735 // operand(s), otherwise we will fail verification due to different values.
736 // The values are actually the same, but the variable names are different
737 // and the verifier doesn't like that.
738 BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx);
739 for (unsigned i = 0; i < Idx; ++i) {
740 if (PHI->getIncomingBlock(i) == IncomingBB) {
741 Value *IncomingVal = PHI->getIncomingValue(i);
742 Inst->setOperand(Idx, IncomingVal);
743 return false;
744 }
745 }
746 }
747
748 Inst->setOperand(Idx, Mat);
749 return true;
750}
751
752/// Emit materialization code for all rebased constants and update their
753/// users.
754void ConstantHoistingPass::emitBaseConstants(Instruction *Base,
755 UserAdjustment *Adj) {
756 Instruction *Mat = Base;
757
758 // The same offset can be dereferenced to different types in nested struct.
759 if (!Adj->Offset && Adj->Ty && Adj->Ty != Base->getType())
760 Adj->Offset = ConstantInt::get(Type::getInt32Ty(*Ctx), 0);
761
762 if (Adj->Offset) {
763 if (Adj->Ty) {
764 // Constant being rebased is a ConstantExpr.
765 Mat = GetElementPtrInst::Create(Type::getInt8Ty(*Ctx), Base, Adj->Offset,
766 "mat_gep", Adj->MatInsertPt);
767 // Hide it behind a bitcast.
768 Mat = new BitCastInst(Mat, Adj->Ty, "mat_bitcast",
769 Adj->MatInsertPt->getIterator());
770 } else
771 // Constant being rebased is a ConstantInt.
772 Mat =
773 BinaryOperator::Create(Instruction::Add, Base, Adj->Offset,
774 "const_mat", Adj->MatInsertPt->getIterator());
775
776 LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
777 << " + " << *Adj->Offset << ") in BB "
778 << Mat->getParent()->getName() << '\n'
779 << *Mat << '\n');
780 Mat->setDebugLoc(Adj->User.Inst->getDebugLoc());
781 }
782 Value *Opnd = Adj->User.Inst->getOperand(Adj->User.OpndIdx);
783
784 // Visit constant integer.
785 if (isa<ConstantInt>(Opnd)) {
786 LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
787 if (!updateOperand(Adj->User.Inst, Adj->User.OpndIdx, Mat) && Adj->Offset)
788 Mat->eraseFromParent();
789 LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n');
790 return;
791 }
792
793 // Visit cast instruction.
794 if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
795 assert(CastInst->isCast() && "Expected an cast instruction!");
796 // Check if we already have visited this cast instruction before to avoid
797 // unnecessary cloning.
798 Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
799 if (!ClonedCastInst) {
800 ClonedCastInst = CastInst->clone();
801 ClonedCastInst->setOperand(0, Mat);
802 ClonedCastInst->insertAfter(CastInst);
803 // Use the same debug location as the original cast instruction.
804 ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
805 LLVM_DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
806 << "To : " << *ClonedCastInst << '\n');
807 }
808
809 LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
810 updateOperand(Adj->User.Inst, Adj->User.OpndIdx, ClonedCastInst);
811 LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n');
812 return;
813 }
814
815 // Visit constant expression.
816 if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
817 if (isa<GEPOperator>(ConstExpr)) {
818 // Operand is a ConstantGEP, replace it.
819 updateOperand(Adj->User.Inst, Adj->User.OpndIdx, Mat);
820 return;
821 }
822
823 // Aside from constant GEPs, only constant cast expressions are collected.
824 assert(ConstExpr->isCast() && "ConstExpr should be a cast");
825 Instruction *ConstExprInst = ConstExpr->getAsInstruction();
826 ConstExprInst->insertBefore(Adj->MatInsertPt);
827 ConstExprInst->setOperand(0, Mat);
828
829 // Use the same debug location as the instruction we are about to update.
830 ConstExprInst->setDebugLoc(Adj->User.Inst->getDebugLoc());
831
832 LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
833 << "From : " << *ConstExpr << '\n');
834 LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
835 if (!updateOperand(Adj->User.Inst, Adj->User.OpndIdx, ConstExprInst)) {
836 ConstExprInst->eraseFromParent();
837 if (Adj->Offset)
838 Mat->eraseFromParent();
839 }
840 LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n');
841 return;
842 }
843}
844
845/// Hoist and hide the base constant behind a bitcast and emit
846/// materialization code for derived constants.
847bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
848 bool MadeChange = false;
850 BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
851 for (const consthoist::ConstantInfo &ConstInfo : ConstInfoVec) {
853 collectMatInsertPts(ConstInfo.RebasedConstants, MatInsertPts);
855 findConstantInsertionPoint(ConstInfo, MatInsertPts);
856 // We can have an empty set if the function contains unreachable blocks.
857 if (IPSet.empty())
858 continue;
859
860 unsigned UsesNum = 0;
861 unsigned ReBasesNum = 0;
862 unsigned NotRebasedNum = 0;
863 for (const BasicBlock::iterator &IP : IPSet) {
864 // First, collect constants depending on this IP of the base.
865 UsesNum = 0;
867 unsigned MatCtr = 0;
868 for (auto const &RCI : ConstInfo.RebasedConstants) {
869 UsesNum += RCI.Uses.size();
870 for (auto const &U : RCI.Uses) {
871 const BasicBlock::iterator &MatInsertPt = MatInsertPts[MatCtr++];
872 BasicBlock *OrigMatInsertBB = MatInsertPt->getParent();
873 // If Base constant is to be inserted in multiple places,
874 // generate rebase for U using the Base dominating U.
875 if (IPSet.size() == 1 ||
876 DT->dominates(IP->getParent(), OrigMatInsertBB))
877 ToBeRebased.emplace_back(RCI.Offset, RCI.Ty, MatInsertPt, U);
878 }
879 }
880
881 // If only few constants depend on this IP of base, skip rebasing,
882 // assuming the base and the rebased have the same materialization cost.
883 if (ToBeRebased.size() < MinNumOfDependentToRebase) {
884 NotRebasedNum += ToBeRebased.size();
885 continue;
886 }
887
888 // Emit an instance of the base at this IP.
889 Instruction *Base = nullptr;
890 // Hoist and hide the base constant behind a bitcast.
891 if (ConstInfo.BaseExpr) {
892 assert(BaseGV && "A base constant expression must have an base GV");
893 Type *Ty = ConstInfo.BaseExpr->getType();
894 Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const", IP);
895 } else {
896 IntegerType *Ty = ConstInfo.BaseInt->getIntegerType();
897 Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const", IP);
898 }
899
900 Base->setDebugLoc(IP->getDebugLoc());
901
902 LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt
903 << ") to BB " << IP->getParent()->getName() << '\n'
904 << *Base << '\n');
905
906 // Emit materialization code for rebased constants depending on this IP.
907 for (UserAdjustment &R : ToBeRebased) {
908 emitBaseConstants(Base, &R);
909 ReBasesNum++;
910 // Use the same debug location as the last user of the constant.
912 Base->getDebugLoc(), R.User.Inst->getDebugLoc()));
913 }
914 assert(!Base->use_empty() && "The use list is empty!?");
915 assert(isa<Instruction>(Base->user_back()) &&
916 "All uses should be instructions.");
917 }
918 (void)UsesNum;
919 (void)ReBasesNum;
920 (void)NotRebasedNum;
921 // Expect all uses are rebased after rebase is done.
922 assert(UsesNum == (ReBasesNum + NotRebasedNum) &&
923 "Not all uses are rebased");
924
925 NumConstantsHoisted++;
926
927 // Base constant is also included in ConstInfo.RebasedConstants, so
928 // deduct 1 from ConstInfo.RebasedConstants.size().
929 NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1;
930
931 MadeChange = true;
932 }
933 return MadeChange;
934}
935
936/// Check all cast instructions we made a copy of and remove them if they
937/// have no more users.
938void ConstantHoistingPass::deleteDeadCastInst() const {
939 for (auto const &I : ClonedCastMap)
940 if (I.first->use_empty())
941 I.first->eraseFromParent();
942}
943
944/// Optimize expensive integer constants in the given function.
947 BasicBlock &Entry, ProfileSummaryInfo *PSI) {
948 this->TTI = &TTI;
949 this->DT = &DT;
950 this->BFI = BFI;
951 this->DL = &Fn.getParent()->getDataLayout();
952 this->Ctx = &Fn.getContext();
953 this->Entry = &Entry;
954 this->PSI = PSI;
955 this->OptForSize = Entry.getParent()->hasOptSize() ||
956 llvm::shouldOptimizeForSize(Entry.getParent(), PSI, BFI,
958
959 // Collect all constant candidates.
960 collectConstantCandidates(Fn);
961
962 // Combine constants that can be easily materialized with an add from a common
963 // base constant.
964 if (!ConstIntCandVec.empty())
965 findBaseConstants(nullptr);
966 for (const auto &MapEntry : ConstGEPCandMap)
967 if (!MapEntry.second.empty())
968 findBaseConstants(MapEntry.first);
969
970 // Finally hoist the base constant and emit materialization code for dependent
971 // constants.
972 bool MadeChange = false;
973 if (!ConstIntInfoVec.empty())
974 MadeChange = emitBaseConstants(nullptr);
975 for (const auto &MapEntry : ConstGEPInfoMap)
976 if (!MapEntry.second.empty())
977 MadeChange |= emitBaseConstants(MapEntry.first);
978
979
980 // Cleanup dead instructions.
981 deleteDeadCastInst();
982
983 cleanup();
984
985 return MadeChange;
986}
987
990 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
991 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
994 : nullptr;
995 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
996 auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
997 if (!runImpl(F, TTI, DT, BFI, F.getEntryBlock(), PSI))
998 return PreservedAnalyses::all();
999
1002 return PA;
1003}
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat)
Updates the operand at Idx in instruction Inst with the result of instruction Mat.
static void findBestInsertionSet(DominatorTree &DT, BlockFrequencyInfo &BFI, BasicBlock *Entry, SetVector< BasicBlock * > &BBs)
Given BBs as input, find another set of BBs which collectively dominates BBs and have the minimal sum...
static cl::opt< unsigned > MinNumOfDependentToRebase("consthoist-min-num-to-rebase", cl::desc("Do not rebase if number of dependent constants of a Base is less " "than this number."), cl::init(0), cl::Hidden)
static cl::opt< bool > ConstHoistWithBlockFrequency("consthoist-with-block-frequency", cl::init(true), cl::Hidden, cl::desc("Enable the use of the block frequency analysis to reduce the " "chance to execute const materialization more frequently than " "without hoisting."))
static cl::opt< bool > ConstHoistGEP("consthoist-gep", cl::init(false), cl::Hidden, cl::desc("Try hoisting constant gep expressions"))
Constant Hoisting
static std::optional< APInt > calculateOffsetDiff(const APInt &V1, const APInt &V2)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static bool isCandidate(const MachineInstr *MI, Register &DefedReg, Register FrameReg)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:76
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1446
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition: APInt.h:453
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1520
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:269
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:430
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:165
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:657
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:221
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
This class represents a no-op cast from one type to another.
Analysis pass which computes BlockFrequencyInfo.
Legacy analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:601
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:1018
bool isCast() const
Return true if this is a convert constant expression.
Definition: Constants.cpp:1514
Instruction * getAsInstruction() const
Returns an Instruction which implements the same operation as this ConstantExpr.
Definition: Constants.cpp:3310
bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, BlockFrequencyInfo *BFI, BasicBlock &Entry, ProfileSummaryInfo *PSI)
Optimize expensive integer constants in the given function.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
Definition: Constants.h:185
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:146
This is an important base class in LLVM.
Definition: Constant.h:41
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
Definition: DataLayout.cpp:905
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:672
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Definition: DenseMap.h:71
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Definition: DenseMap.h:103
iterator_range< iterator > children()
DomTreeNodeBase * getIDom() const
NodeT * getBlock() const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
Definition: Dominators.cpp:344
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
const BasicBlock & getEntryBlock() const
Definition: Function.h:787
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:356
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:655
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:293
std::optional< CostType > getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
bool isCast() const
Definition: Instruction.h:260
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:454
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:812
const BasicBlock * getParent() const
Definition: Instruction.h:152
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:252
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:451
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Class to represent integer types.
Definition: DerivedTypes.h:40
An instruction for reading from memory.
Definition: Instructions.h:185
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:293
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:756
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
A vector that has set insertion semantics.
Definition: SetVector.h:57
void clear()
Completely clear the SetVector.
Definition: SetVector.h:273
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:264
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
An instruction for storing to memory.
Definition: Instructions.h:318
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Analysis pass providing the TargetTransformInfo.
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset, bool HasBaseReg, int64_t Scale, unsigned AddrSpace=0, Instruction *I=nullptr, int64_t ScalableOffset=0) const
Return true if the addressing mode represented by AM is legal for this target, for a load/store of th...
InstructionCost getIntImmCostIntrin(Intrinsic::ID IID, unsigned Idx, const APInt &Imm, Type *Ty, TargetCostKind CostKind) const
InstructionCost getIntImmCostInst(unsigned Opc, unsigned Idx, const APInt &Imm, Type *Ty, TargetCostKind CostKind, Instruction *Inst=nullptr) const
Return the expected cost of materialization for the given integer immediate of the specified type for...
@ TCK_SizeAndLatency
The weighted sum of size and latency.
bool isLegalAddImmediate(int64_t Imm) const
Return true if the specified immediate is legal add immediate, that is the target has add instruction...
bool preferToKeepConstantsAttached(const Instruction &Inst, const Function &Fn) const
It can be advantageous to detach complex constants from their uses to make their generation cheaper.
InstructionCost getIntImmCodeSizeCost(unsigned Opc, unsigned Idx, const APInt &Imm, Type *Ty) const
Return the expected cost for the given integer when optimising for size.
@ TCC_Basic
The cost of a typical 'add' instruction.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:265
static IntegerType * getInt8Ty(LLVMContext &C)
static IntegerType * getInt32Ty(LLVMContext &C)
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Value * getOperand(unsigned i) const
Definition: User.h:169
unsigned getNumOperands() const
Definition: User.h:191
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
self_iterator getIterator()
Definition: ilist_node.h:109
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:456
void stable_sort(R &&Range)
Definition: STLExtras.h:1995
FunctionPass * createConstantHoistingPass()
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
Definition: Local.cpp:4109
InstructionCost Cost
void initializeConstantHoistingLegacyPassPass(PassRegistry &)
Keeps track of a constant candidate and its uses.
A base constant and all its rebased constants.
RebasedConstantListType RebasedConstants
Keeps track of the user of a constant and the operand index where the constant is used.
This represents a constant that has been rebased with respect to a base constant.