LLVM 18.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<Instruction *> &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.
172Instruction *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;
181 }
182
183 // The simple and common case. This also includes constant expressions.
184 if (!isa<PHINode>(Inst) && !Inst->isEHPad())
185 return Inst;
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();
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();
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.
317SetVector<Instruction *> ConstantHoistingPass::findConstantInsertionPoint(
318 const ConstantInfo &ConstInfo,
319 const ArrayRef<Instruction *> MatInsertPts) const {
320 assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
321 // Collect all basic blocks.
323 SetVector<Instruction *> InsertPts;
324
325 for (Instruction *MatInsertPt : MatInsertPts)
326 BBs.insert(MatInsertPt->getParent());
327
328 if (BBs.count(Entry)) {
329 InsertPts.insert(&Entry->front());
330 return InsertPts;
331 }
332
333 if (BFI) {
334 findBestInsertionSet(*DT, *BFI, Entry, BBs);
335 for (BasicBlock *BB : BBs)
336 InsertPts.insert(&*BB->getFirstInsertionPt());
337 return InsertPts;
338 }
339
340 while (BBs.size() >= 2) {
341 BasicBlock *BB, *BB1, *BB2;
342 BB1 = BBs.pop_back_val();
343 BB2 = BBs.pop_back_val();
344 BB = DT->findNearestCommonDominator(BB1, BB2);
345 if (BB == Entry) {
346 InsertPts.insert(&Entry->front());
347 return InsertPts;
348 }
349 BBs.insert(BB);
350 }
351 assert((BBs.size() == 1) && "Expected only one element.");
352 Instruction &FirstInst = (*BBs.begin())->front();
353 InsertPts.insert(findMatInsertPt(&FirstInst));
354 return InsertPts;
355}
356
357/// Record constant integer ConstInt for instruction Inst at operand
358/// index Idx.
359///
360/// The operand at index Idx is not necessarily the constant integer itself. It
361/// could also be a cast instruction or a constant expression that uses the
362/// constant integer.
363void ConstantHoistingPass::collectConstantCandidates(
364 ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
365 ConstantInt *ConstInt) {
367 // Ask the target about the cost of materializing the constant for the given
368 // instruction and operand index.
369 if (auto IntrInst = dyn_cast<IntrinsicInst>(Inst))
370 Cost = TTI->getIntImmCostIntrin(IntrInst->getIntrinsicID(), Idx,
371 ConstInt->getValue(), ConstInt->getType(),
373 else
375 Inst->getOpcode(), Idx, ConstInt->getValue(), ConstInt->getType(),
377
378 // Ignore cheap integer constants.
381 bool Inserted;
382 ConstPtrUnionType Cand = ConstInt;
383 std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
384 if (Inserted) {
385 ConstIntCandVec.push_back(ConstantCandidate(ConstInt));
386 Itr->second = ConstIntCandVec.size() - 1;
387 }
388 ConstIntCandVec[Itr->second].addUser(Inst, Idx, *Cost.getValue());
389 LLVM_DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx))) dbgs()
390 << "Collect constant " << *ConstInt << " from " << *Inst
391 << " with cost " << Cost << '\n';
392 else dbgs() << "Collect constant " << *ConstInt
393 << " indirectly from " << *Inst << " via "
394 << *Inst->getOperand(Idx) << " with cost " << Cost
395 << '\n';);
396 }
397}
398
399/// Record constant GEP expression for instruction Inst at operand index Idx.
400void ConstantHoistingPass::collectConstantCandidates(
401 ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
402 ConstantExpr *ConstExpr) {
403 // TODO: Handle vector GEPs
404 if (ConstExpr->getType()->isVectorTy())
405 return;
406
407 GlobalVariable *BaseGV = dyn_cast<GlobalVariable>(ConstExpr->getOperand(0));
408 if (!BaseGV)
409 return;
410
411 // Get offset from the base GV.
412 PointerType *GVPtrTy = cast<PointerType>(BaseGV->getType());
413 IntegerType *OffsetTy = DL->getIndexType(*Ctx, GVPtrTy->getAddressSpace());
414 APInt Offset(DL->getTypeSizeInBits(OffsetTy), /*val*/ 0, /*isSigned*/ true);
415 auto *GEPO = cast<GEPOperator>(ConstExpr);
416
417 // TODO: If we have a mix of inbounds and non-inbounds GEPs, then basing a
418 // non-inbounds GEP on an inbounds GEP is potentially incorrect. Restrict to
419 // inbounds GEP for now -- alternatively, we could drop inbounds from the
420 // constant expression,
421 if (!GEPO->isInBounds())
422 return;
423
424 if (!GEPO->accumulateConstantOffset(*DL, Offset))
425 return;
426
427 if (!Offset.isIntN(32))
428 return;
429
430 // A constant GEP expression that has a GlobalVariable as base pointer is
431 // usually lowered to a load from constant pool. Such operation is unlikely
432 // to be cheaper than compute it by <Base + Offset>, which can be lowered to
433 // an ADD instruction or folded into Load/Store instruction.
435 TTI->getIntImmCostInst(Instruction::Add, 1, Offset, OffsetTy,
437 ConstCandVecType &ExprCandVec = ConstGEPCandMap[BaseGV];
439 bool Inserted;
440 ConstPtrUnionType Cand = ConstExpr;
441 std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
442 if (Inserted) {
443 ExprCandVec.push_back(ConstantCandidate(
444 ConstantInt::get(Type::getInt32Ty(*Ctx), Offset.getLimitedValue()),
445 ConstExpr));
446 Itr->second = ExprCandVec.size() - 1;
447 }
448 ExprCandVec[Itr->second].addUser(Inst, Idx, *Cost.getValue());
449}
450
451/// Check the operand for instruction Inst at index Idx.
452void ConstantHoistingPass::collectConstantCandidates(
453 ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx) {
454 Value *Opnd = Inst->getOperand(Idx);
455
456 // Visit constant integers.
457 if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
458 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
459 return;
460 }
461
462 // Visit cast instructions that have constant integers.
463 if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
464 // Only visit cast instructions, which have been skipped. All other
465 // instructions should have already been visited.
466 if (!CastInst->isCast())
467 return;
468
469 if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
470 // Pretend the constant is directly used by the instruction and ignore
471 // the cast instruction.
472 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
473 return;
474 }
475 }
476
477 // Visit constant expressions that have constant integers.
478 if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
479 // Handle constant gep expressions.
480 if (ConstHoistGEP && isa<GEPOperator>(ConstExpr))
481 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstExpr);
482
483 // Only visit constant cast expressions.
484 if (!ConstExpr->isCast())
485 return;
486
487 if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
488 // Pretend the constant is directly used by the instruction and ignore
489 // the constant expression.
490 collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
491 return;
492 }
493 }
494}
495
496/// Scan the instruction for expensive integer constants and record them
497/// in the constant candidate vector.
498void ConstantHoistingPass::collectConstantCandidates(
499 ConstCandMapType &ConstCandMap, Instruction *Inst) {
500 // Skip all cast instructions. They are visited indirectly later on.
501 if (Inst->isCast())
502 return;
503
504 // Scan all operands.
505 for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
506 // The cost of materializing the constants (defined in
507 // `TargetTransformInfo::getIntImmCostInst`) for instructions which only
508 // take constant variables is lower than `TargetTransformInfo::TCC_Basic`.
509 // So it's safe for us to collect constant candidates from all
510 // IntrinsicInsts.
512 collectConstantCandidates(ConstCandMap, Inst, Idx);
513 }
514 } // end of for all operands
515}
516
517/// Collect all integer constants in the function that cannot be folded
518/// into an instruction itself.
519void ConstantHoistingPass::collectConstantCandidates(Function &Fn) {
520 ConstCandMapType ConstCandMap;
521 for (BasicBlock &BB : Fn) {
522 // Ignore unreachable basic blocks.
523 if (!DT->isReachableFromEntry(&BB))
524 continue;
525 for (Instruction &Inst : BB)
526 collectConstantCandidates(ConstCandMap, &Inst);
527 }
528}
529
530// This helper function is necessary to deal with values that have different
531// bit widths (APInt Operator- does not like that). If the value cannot be
532// represented in uint64 we return an "empty" APInt. This is then interpreted
533// as the value is not in range.
534static std::optional<APInt> calculateOffsetDiff(const APInt &V1,
535 const APInt &V2) {
536 std::optional<APInt> Res;
537 unsigned BW = V1.getBitWidth() > V2.getBitWidth() ?
538 V1.getBitWidth() : V2.getBitWidth();
539 uint64_t LimVal1 = V1.getLimitedValue();
540 uint64_t LimVal2 = V2.getLimitedValue();
541
542 if (LimVal1 == ~0ULL || LimVal2 == ~0ULL)
543 return Res;
544
545 uint64_t Diff = LimVal1 - LimVal2;
546 return APInt(BW, Diff, true);
547}
548
549// From a list of constants, one needs to picked as the base and the other
550// constants will be transformed into an offset from that base constant. The
551// question is which we can pick best? For example, consider these constants
552// and their number of uses:
553//
554// Constants| 2 | 4 | 12 | 42 |
555// NumUses | 3 | 2 | 8 | 7 |
556//
557// Selecting constant 12 because it has the most uses will generate negative
558// offsets for constants 2 and 4 (i.e. -10 and -8 respectively). If negative
559// offsets lead to less optimal code generation, then there might be better
560// solutions. Suppose immediates in the range of 0..35 are most optimally
561// supported by the architecture, then selecting constant 2 is most optimal
562// because this will generate offsets: 0, 2, 10, 40. Offsets 0, 2 and 10 are in
563// range 0..35, and thus 3 + 2 + 8 = 13 uses are in range. Selecting 12 would
564// have only 8 uses in range, so choosing 2 as a base is more optimal. Thus, in
565// selecting the base constant the range of the offsets is a very important
566// factor too that we take into account here. This algorithm calculates a total
567// costs for selecting a constant as the base and substract the costs if
568// immediates are out of range. It has quadratic complexity, so we call this
569// function only when we're optimising for size and there are less than 100
570// constants, we fall back to the straightforward algorithm otherwise
571// which does not do all the offset calculations.
572unsigned
573ConstantHoistingPass::maximizeConstantsInRange(ConstCandVecType::iterator S,
574 ConstCandVecType::iterator E,
575 ConstCandVecType::iterator &MaxCostItr) {
576 unsigned NumUses = 0;
577
578 bool OptForSize = Entry->getParent()->hasOptSize() ||
579 llvm::shouldOptimizeForSize(Entry->getParent(), PSI, BFI,
581 if (!OptForSize || std::distance(S,E) > 100) {
582 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
583 NumUses += ConstCand->Uses.size();
584 if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
585 MaxCostItr = ConstCand;
586 }
587 return NumUses;
588 }
589
590 LLVM_DEBUG(dbgs() << "== Maximize constants in range ==\n");
591 InstructionCost MaxCost = -1;
592 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
593 auto Value = ConstCand->ConstInt->getValue();
594 Type *Ty = ConstCand->ConstInt->getType();
596 NumUses += ConstCand->Uses.size();
597 LLVM_DEBUG(dbgs() << "= Constant: " << ConstCand->ConstInt->getValue()
598 << "\n");
599
600 for (auto User : ConstCand->Uses) {
601 unsigned Opcode = User.Inst->getOpcode();
602 unsigned OpndIdx = User.OpndIdx;
603 Cost += TTI->getIntImmCostInst(Opcode, OpndIdx, Value, Ty,
605 LLVM_DEBUG(dbgs() << "Cost: " << Cost << "\n");
606
607 for (auto C2 = S; C2 != E; ++C2) {
608 std::optional<APInt> Diff = calculateOffsetDiff(
609 C2->ConstInt->getValue(), ConstCand->ConstInt->getValue());
610 if (Diff) {
611 const InstructionCost ImmCosts =
612 TTI->getIntImmCodeSizeCost(Opcode, OpndIdx, *Diff, Ty);
613 Cost -= ImmCosts;
614 LLVM_DEBUG(dbgs() << "Offset " << *Diff << " "
615 << "has penalty: " << ImmCosts << "\n"
616 << "Adjusted cost: " << Cost << "\n");
617 }
618 }
619 }
620 LLVM_DEBUG(dbgs() << "Cumulative cost: " << Cost << "\n");
621 if (Cost > MaxCost) {
622 MaxCost = Cost;
623 MaxCostItr = ConstCand;
624 LLVM_DEBUG(dbgs() << "New candidate: " << MaxCostItr->ConstInt->getValue()
625 << "\n");
626 }
627 }
628 return NumUses;
629}
630
631/// Find the base constant within the given range and rebase all other
632/// constants with respect to the base constant.
633void ConstantHoistingPass::findAndMakeBaseConstant(
634 ConstCandVecType::iterator S, ConstCandVecType::iterator E,
636 auto MaxCostItr = S;
637 unsigned NumUses = maximizeConstantsInRange(S, E, MaxCostItr);
638
639 // Don't hoist constants that have only one use.
640 if (NumUses <= 1)
641 return;
642
643 ConstantInt *ConstInt = MaxCostItr->ConstInt;
644 ConstantExpr *ConstExpr = MaxCostItr->ConstExpr;
645 ConstantInfo ConstInfo;
646 ConstInfo.BaseInt = ConstInt;
647 ConstInfo.BaseExpr = ConstExpr;
648 Type *Ty = ConstInt->getType();
649
650 // Rebase the constants with respect to the base constant.
651 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
652 APInt Diff = ConstCand->ConstInt->getValue() - ConstInt->getValue();
653 Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
654 Type *ConstTy =
655 ConstCand->ConstExpr ? ConstCand->ConstExpr->getType() : nullptr;
656 ConstInfo.RebasedConstants.push_back(
657 RebasedConstantInfo(std::move(ConstCand->Uses), Offset, ConstTy));
658 }
659 ConstInfoVec.push_back(std::move(ConstInfo));
660}
661
662/// Finds and combines constant candidates that can be easily
663/// rematerialized with an add from a common base constant.
664void ConstantHoistingPass::findBaseConstants(GlobalVariable *BaseGV) {
665 // If BaseGV is nullptr, find base among candidate constant integers;
666 // Otherwise find base among constant GEPs that share the same BaseGV.
667 ConstCandVecType &ConstCandVec = BaseGV ?
668 ConstGEPCandMap[BaseGV] : ConstIntCandVec;
669 ConstInfoVecType &ConstInfoVec = BaseGV ?
670 ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
671
672 // Sort the constants by value and type. This invalidates the mapping!
673 llvm::stable_sort(ConstCandVec, [](const ConstantCandidate &LHS,
674 const ConstantCandidate &RHS) {
675 if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
676 return LHS.ConstInt->getType()->getBitWidth() <
677 RHS.ConstInt->getType()->getBitWidth();
678 return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
679 });
680
681 // Simple linear scan through the sorted constant candidate vector for viable
682 // merge candidates.
683 auto MinValItr = ConstCandVec.begin();
684 for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
685 CC != E; ++CC) {
686 if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
687 Type *MemUseValTy = nullptr;
688 for (auto &U : CC->Uses) {
689 auto *UI = U.Inst;
690 if (LoadInst *LI = dyn_cast<LoadInst>(UI)) {
691 MemUseValTy = LI->getType();
692 break;
693 } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
694 // Make sure the constant is used as pointer operand of the StoreInst.
695 if (SI->getPointerOperand() == SI->getOperand(U.OpndIdx)) {
696 MemUseValTy = SI->getValueOperand()->getType();
697 break;
698 }
699 }
700 }
701
702 // Check if the constant is in range of an add with immediate.
703 APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
704 if ((Diff.getBitWidth() <= 64) &&
706 // Check if Diff can be used as offset in addressing mode of the user
707 // memory instruction.
708 (!MemUseValTy || TTI->isLegalAddressingMode(MemUseValTy,
709 /*BaseGV*/nullptr, /*BaseOffset*/Diff.getSExtValue(),
710 /*HasBaseReg*/true, /*Scale*/0)))
711 continue;
712 }
713 // We either have now a different constant type or the constant is not in
714 // range of an add with immediate anymore.
715 findAndMakeBaseConstant(MinValItr, CC, ConstInfoVec);
716 // Start a new base constant search.
717 MinValItr = CC;
718 }
719 // Finalize the last base constant search.
720 findAndMakeBaseConstant(MinValItr, ConstCandVec.end(), ConstInfoVec);
721}
722
723/// Updates the operand at Idx in instruction Inst with the result of
724/// instruction Mat. If the instruction is a PHI node then special
725/// handling for duplicate values from the same incoming basic block is
726/// required.
727/// \return The update will always succeed, but the return value indicated if
728/// Mat was used for the update or not.
729static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
730 if (auto PHI = dyn_cast<PHINode>(Inst)) {
731 // Check if any previous operand of the PHI node has the same incoming basic
732 // block. This is a very odd case that happens when the incoming basic block
733 // has a switch statement. In this case use the same value as the previous
734 // operand(s), otherwise we will fail verification due to different values.
735 // The values are actually the same, but the variable names are different
736 // and the verifier doesn't like that.
737 BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx);
738 for (unsigned i = 0; i < Idx; ++i) {
739 if (PHI->getIncomingBlock(i) == IncomingBB) {
740 Value *IncomingVal = PHI->getIncomingValue(i);
741 Inst->setOperand(Idx, IncomingVal);
742 return false;
743 }
744 }
745 }
746
747 Inst->setOperand(Idx, Mat);
748 return true;
749}
750
751/// Emit materialization code for all rebased constants and update their
752/// users.
753void ConstantHoistingPass::emitBaseConstants(Instruction *Base,
754 UserAdjustment *Adj) {
755 Instruction *Mat = Base;
756
757 // The same offset can be dereferenced to different types in nested struct.
758 if (!Adj->Offset && Adj->Ty && Adj->Ty != Base->getType())
759 Adj->Offset = ConstantInt::get(Type::getInt32Ty(*Ctx), 0);
760
761 if (Adj->Offset) {
762 if (Adj->Ty) {
763 // Constant being rebased is a ConstantExpr.
764 Mat = GetElementPtrInst::Create(Type::getInt8Ty(*Ctx), Base, Adj->Offset,
765 "mat_gep", Adj->MatInsertPt);
766 // Hide it behind a bitcast.
767 Mat = new BitCastInst(Mat, Adj->Ty, "mat_bitcast", Adj->MatInsertPt);
768 } else
769 // Constant being rebased is a ConstantInt.
770 Mat = BinaryOperator::Create(Instruction::Add, Base, Adj->Offset,
771 "const_mat", Adj->MatInsertPt);
772
773 LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
774 << " + " << *Adj->Offset << ") in BB "
775 << Mat->getParent()->getName() << '\n'
776 << *Mat << '\n');
777 Mat->setDebugLoc(Adj->User.Inst->getDebugLoc());
778 }
779 Value *Opnd = Adj->User.Inst->getOperand(Adj->User.OpndIdx);
780
781 // Visit constant integer.
782 if (isa<ConstantInt>(Opnd)) {
783 LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
784 if (!updateOperand(Adj->User.Inst, Adj->User.OpndIdx, Mat) && Adj->Offset)
785 Mat->eraseFromParent();
786 LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n');
787 return;
788 }
789
790 // Visit cast instruction.
791 if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
792 assert(CastInst->isCast() && "Expected an cast instruction!");
793 // Check if we already have visited this cast instruction before to avoid
794 // unnecessary cloning.
795 Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
796 if (!ClonedCastInst) {
797 ClonedCastInst = CastInst->clone();
798 ClonedCastInst->setOperand(0, Mat);
799 ClonedCastInst->insertAfter(CastInst);
800 // Use the same debug location as the original cast instruction.
801 ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
802 LLVM_DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
803 << "To : " << *ClonedCastInst << '\n');
804 }
805
806 LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
807 updateOperand(Adj->User.Inst, Adj->User.OpndIdx, ClonedCastInst);
808 LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n');
809 return;
810 }
811
812 // Visit constant expression.
813 if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
814 if (isa<GEPOperator>(ConstExpr)) {
815 // Operand is a ConstantGEP, replace it.
816 updateOperand(Adj->User.Inst, Adj->User.OpndIdx, Mat);
817 return;
818 }
819
820 // Aside from constant GEPs, only constant cast expressions are collected.
821 assert(ConstExpr->isCast() && "ConstExpr should be a cast");
822 Instruction *ConstExprInst = ConstExpr->getAsInstruction(Adj->MatInsertPt);
823 ConstExprInst->setOperand(0, Mat);
824
825 // Use the same debug location as the instruction we are about to update.
826 ConstExprInst->setDebugLoc(Adj->User.Inst->getDebugLoc());
827
828 LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
829 << "From : " << *ConstExpr << '\n');
830 LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
831 if (!updateOperand(Adj->User.Inst, Adj->User.OpndIdx, ConstExprInst)) {
832 ConstExprInst->eraseFromParent();
833 if (Adj->Offset)
834 Mat->eraseFromParent();
835 }
836 LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n');
837 return;
838 }
839}
840
841/// Hoist and hide the base constant behind a bitcast and emit
842/// materialization code for derived constants.
843bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
844 bool MadeChange = false;
846 BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
847 for (const consthoist::ConstantInfo &ConstInfo : ConstInfoVec) {
849 collectMatInsertPts(ConstInfo.RebasedConstants, MatInsertPts);
851 findConstantInsertionPoint(ConstInfo, MatInsertPts);
852 // We can have an empty set if the function contains unreachable blocks.
853 if (IPSet.empty())
854 continue;
855
856 unsigned UsesNum = 0;
857 unsigned ReBasesNum = 0;
858 unsigned NotRebasedNum = 0;
859 for (Instruction *IP : IPSet) {
860 // First, collect constants depending on this IP of the base.
861 UsesNum = 0;
863 unsigned MatCtr = 0;
864 for (auto const &RCI : ConstInfo.RebasedConstants) {
865 UsesNum += RCI.Uses.size();
866 for (auto const &U : RCI.Uses) {
867 Instruction *MatInsertPt = MatInsertPts[MatCtr++];
868 BasicBlock *OrigMatInsertBB = MatInsertPt->getParent();
869 // If Base constant is to be inserted in multiple places,
870 // generate rebase for U using the Base dominating U.
871 if (IPSet.size() == 1 ||
872 DT->dominates(IP->getParent(), OrigMatInsertBB))
873 ToBeRebased.emplace_back(RCI.Offset, RCI.Ty, MatInsertPt, U);
874 }
875 }
876
877 // If only few constants depend on this IP of base, skip rebasing,
878 // assuming the base and the rebased have the same materialization cost.
879 if (ToBeRebased.size() < MinNumOfDependentToRebase) {
880 NotRebasedNum += ToBeRebased.size();
881 continue;
882 }
883
884 // Emit an instance of the base at this IP.
885 Instruction *Base = nullptr;
886 // Hoist and hide the base constant behind a bitcast.
887 if (ConstInfo.BaseExpr) {
888 assert(BaseGV && "A base constant expression must have an base GV");
889 Type *Ty = ConstInfo.BaseExpr->getType();
890 Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const", IP);
891 } else {
892 IntegerType *Ty = ConstInfo.BaseInt->getType();
893 Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const", IP);
894 }
895
896 Base->setDebugLoc(IP->getDebugLoc());
897
898 LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt
899 << ") to BB " << IP->getParent()->getName() << '\n'
900 << *Base << '\n');
901
902 // Emit materialization code for rebased constants depending on this IP.
903 for (UserAdjustment &R : ToBeRebased) {
904 emitBaseConstants(Base, &R);
905 ReBasesNum++;
906 // Use the same debug location as the last user of the constant.
908 Base->getDebugLoc(), R.User.Inst->getDebugLoc()));
909 }
910 assert(!Base->use_empty() && "The use list is empty!?");
911 assert(isa<Instruction>(Base->user_back()) &&
912 "All uses should be instructions.");
913 }
914 (void)UsesNum;
915 (void)ReBasesNum;
916 (void)NotRebasedNum;
917 // Expect all uses are rebased after rebase is done.
918 assert(UsesNum == (ReBasesNum + NotRebasedNum) &&
919 "Not all uses are rebased");
920
921 NumConstantsHoisted++;
922
923 // Base constant is also included in ConstInfo.RebasedConstants, so
924 // deduct 1 from ConstInfo.RebasedConstants.size().
925 NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1;
926
927 MadeChange = true;
928 }
929 return MadeChange;
930}
931
932/// Check all cast instructions we made a copy of and remove them if they
933/// have no more users.
934void ConstantHoistingPass::deleteDeadCastInst() const {
935 for (auto const &I : ClonedCastMap)
936 if (I.first->use_empty())
937 I.first->eraseFromParent();
938}
939
940/// Optimize expensive integer constants in the given function.
943 BasicBlock &Entry, ProfileSummaryInfo *PSI) {
944 this->TTI = &TTI;
945 this->DT = &DT;
946 this->BFI = BFI;
947 this->DL = &Fn.getParent()->getDataLayout();
948 this->Ctx = &Fn.getContext();
949 this->Entry = &Entry;
950 this->PSI = PSI;
951 // Collect all constant candidates.
952 collectConstantCandidates(Fn);
953
954 // Combine constants that can be easily materialized with an add from a common
955 // base constant.
956 if (!ConstIntCandVec.empty())
957 findBaseConstants(nullptr);
958 for (const auto &MapEntry : ConstGEPCandMap)
959 if (!MapEntry.second.empty())
960 findBaseConstants(MapEntry.first);
961
962 // Finally hoist the base constant and emit materialization code for dependent
963 // constants.
964 bool MadeChange = false;
965 if (!ConstIntInfoVec.empty())
966 MadeChange = emitBaseConstants(nullptr);
967 for (const auto &MapEntry : ConstGEPInfoMap)
968 if (!MapEntry.second.empty())
969 MadeChange |= emitBaseConstants(MapEntry.first);
970
971
972 // Cleanup dead instructions.
973 deleteDeadCastInst();
974
975 cleanup();
976
977 return MadeChange;
978}
979
982 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
983 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
986 : nullptr;
987 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
988 auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
989 if (!runImpl(F, TTI, DT, BFI, F.getEntryBlock(), PSI))
990 return PreservedAnalyses::all();
991
994 return PA;
995}
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
static constexpr uint32_t Opcode
Definition: aarch32.h:200
Class for arbitrary precision integers.
Definition: APInt.h:76
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1433
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:1507
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:649
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:803
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
const Instruction & front() const
Definition: BasicBlock.h:452
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:205
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:653
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:220
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
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: PassManager.h:133
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:451
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:1002
bool isCast() const
Return true if this is a convert constant expression.
Definition: Constants.cpp:1430
Instruction * getAsInstruction(Instruction *InsertBefore=nullptr) const
Returns an Instruction which implements the same operation as this ConstantExpr.
Definition: Constants.cpp:3196
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:78
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:176
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:136
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:278
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:313
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:165
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:322
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:345
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:123
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:778
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:677
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:341
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:966
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:652
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:290
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:242
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:433
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:781
const BasicBlock * getParent() const
Definition: Instruction.h:134
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:93
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:234
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:430
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:177
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:275
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1087
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: PassManager.h:172
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:178
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:208
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:384
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:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
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:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void push_back(const T &Elt)
Definition: SmallVector.h:416
An instruction for storing to memory.
Definition: Instructions.h:301
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) 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...
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
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:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:440
void stable_sort(R &&Range)
Definition: STLExtras.h:1970
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:428
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:3990
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.