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<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 if (!TTI->preferToKeepConstantsAttached(Inst, Fn))
527 collectConstantCandidates(ConstCandMap, &Inst);
528 }
529}
530
531// This helper function is necessary to deal with values that have different
532// bit widths (APInt Operator- does not like that). If the value cannot be
533// represented in uint64 we return an "empty" APInt. This is then interpreted
534// as the value is not in range.
535static std::optional<APInt> calculateOffsetDiff(const APInt &V1,
536 const APInt &V2) {
537 std::optional<APInt> Res;
538 unsigned BW = V1.getBitWidth() > V2.getBitWidth() ?
539 V1.getBitWidth() : V2.getBitWidth();
540 uint64_t LimVal1 = V1.getLimitedValue();
541 uint64_t LimVal2 = V2.getLimitedValue();
542
543 if (LimVal1 == ~0ULL || LimVal2 == ~0ULL)
544 return Res;
545
546 uint64_t Diff = LimVal1 - LimVal2;
547 return APInt(BW, Diff, true);
548}
549
550// From a list of constants, one needs to picked as the base and the other
551// constants will be transformed into an offset from that base constant. The
552// question is which we can pick best? For example, consider these constants
553// and their number of uses:
554//
555// Constants| 2 | 4 | 12 | 42 |
556// NumUses | 3 | 2 | 8 | 7 |
557//
558// Selecting constant 12 because it has the most uses will generate negative
559// offsets for constants 2 and 4 (i.e. -10 and -8 respectively). If negative
560// offsets lead to less optimal code generation, then there might be better
561// solutions. Suppose immediates in the range of 0..35 are most optimally
562// supported by the architecture, then selecting constant 2 is most optimal
563// because this will generate offsets: 0, 2, 10, 40. Offsets 0, 2 and 10 are in
564// range 0..35, and thus 3 + 2 + 8 = 13 uses are in range. Selecting 12 would
565// have only 8 uses in range, so choosing 2 as a base is more optimal. Thus, in
566// selecting the base constant the range of the offsets is a very important
567// factor too that we take into account here. This algorithm calculates a total
568// costs for selecting a constant as the base and substract the costs if
569// immediates are out of range. It has quadratic complexity, so we call this
570// function only when we're optimising for size and there are less than 100
571// constants, we fall back to the straightforward algorithm otherwise
572// which does not do all the offset calculations.
573unsigned
574ConstantHoistingPass::maximizeConstantsInRange(ConstCandVecType::iterator S,
575 ConstCandVecType::iterator E,
576 ConstCandVecType::iterator &MaxCostItr) {
577 unsigned NumUses = 0;
578
579 if (!OptForSize || std::distance(S,E) > 100) {
580 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
581 NumUses += ConstCand->Uses.size();
582 if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
583 MaxCostItr = ConstCand;
584 }
585 return NumUses;
586 }
587
588 LLVM_DEBUG(dbgs() << "== Maximize constants in range ==\n");
589 InstructionCost MaxCost = -1;
590 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
591 auto Value = ConstCand->ConstInt->getValue();
592 Type *Ty = ConstCand->ConstInt->getType();
594 NumUses += ConstCand->Uses.size();
595 LLVM_DEBUG(dbgs() << "= Constant: " << ConstCand->ConstInt->getValue()
596 << "\n");
597
598 for (auto User : ConstCand->Uses) {
599 unsigned Opcode = User.Inst->getOpcode();
600 unsigned OpndIdx = User.OpndIdx;
601 Cost += TTI->getIntImmCostInst(Opcode, OpndIdx, Value, Ty,
603 LLVM_DEBUG(dbgs() << "Cost: " << Cost << "\n");
604
605 for (auto C2 = S; C2 != E; ++C2) {
606 std::optional<APInt> Diff = calculateOffsetDiff(
607 C2->ConstInt->getValue(), ConstCand->ConstInt->getValue());
608 if (Diff) {
609 const InstructionCost ImmCosts =
610 TTI->getIntImmCodeSizeCost(Opcode, OpndIdx, *Diff, Ty);
611 Cost -= ImmCosts;
612 LLVM_DEBUG(dbgs() << "Offset " << *Diff << " "
613 << "has penalty: " << ImmCosts << "\n"
614 << "Adjusted cost: " << Cost << "\n");
615 }
616 }
617 }
618 LLVM_DEBUG(dbgs() << "Cumulative cost: " << Cost << "\n");
619 if (Cost > MaxCost) {
620 MaxCost = Cost;
621 MaxCostItr = ConstCand;
622 LLVM_DEBUG(dbgs() << "New candidate: " << MaxCostItr->ConstInt->getValue()
623 << "\n");
624 }
625 }
626 return NumUses;
627}
628
629/// Find the base constant within the given range and rebase all other
630/// constants with respect to the base constant.
631void ConstantHoistingPass::findAndMakeBaseConstant(
632 ConstCandVecType::iterator S, ConstCandVecType::iterator E,
634 auto MaxCostItr = S;
635 unsigned NumUses = maximizeConstantsInRange(S, E, MaxCostItr);
636
637 // Don't hoist constants that have only one use.
638 if (NumUses <= 1)
639 return;
640
641 ConstantInt *ConstInt = MaxCostItr->ConstInt;
642 ConstantExpr *ConstExpr = MaxCostItr->ConstExpr;
643 ConstantInfo ConstInfo;
644 ConstInfo.BaseInt = ConstInt;
645 ConstInfo.BaseExpr = ConstExpr;
646 Type *Ty = ConstInt->getType();
647
648 // Rebase the constants with respect to the base constant.
649 for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
650 APInt Diff = ConstCand->ConstInt->getValue() - ConstInt->getValue();
651 Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
652 Type *ConstTy =
653 ConstCand->ConstExpr ? ConstCand->ConstExpr->getType() : nullptr;
654 ConstInfo.RebasedConstants.push_back(
655 RebasedConstantInfo(std::move(ConstCand->Uses), Offset, ConstTy));
656 }
657 ConstInfoVec.push_back(std::move(ConstInfo));
658}
659
660/// Finds and combines constant candidates that can be easily
661/// rematerialized with an add from a common base constant.
662void ConstantHoistingPass::findBaseConstants(GlobalVariable *BaseGV) {
663 // If BaseGV is nullptr, find base among candidate constant integers;
664 // Otherwise find base among constant GEPs that share the same BaseGV.
665 ConstCandVecType &ConstCandVec = BaseGV ?
666 ConstGEPCandMap[BaseGV] : ConstIntCandVec;
667 ConstInfoVecType &ConstInfoVec = BaseGV ?
668 ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
669
670 // Sort the constants by value and type. This invalidates the mapping!
671 llvm::stable_sort(ConstCandVec, [](const ConstantCandidate &LHS,
672 const ConstantCandidate &RHS) {
673 if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
674 return LHS.ConstInt->getBitWidth() < RHS.ConstInt->getBitWidth();
675 return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
676 });
677
678 // Simple linear scan through the sorted constant candidate vector for viable
679 // merge candidates.
680 auto MinValItr = ConstCandVec.begin();
681 for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
682 CC != E; ++CC) {
683 if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
684 Type *MemUseValTy = nullptr;
685 for (auto &U : CC->Uses) {
686 auto *UI = U.Inst;
687 if (LoadInst *LI = dyn_cast<LoadInst>(UI)) {
688 MemUseValTy = LI->getType();
689 break;
690 } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
691 // Make sure the constant is used as pointer operand of the StoreInst.
692 if (SI->getPointerOperand() == SI->getOperand(U.OpndIdx)) {
693 MemUseValTy = SI->getValueOperand()->getType();
694 break;
695 }
696 }
697 }
698
699 // Check if the constant is in range of an add with immediate.
700 APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
701 if ((Diff.getBitWidth() <= 64) &&
703 // Check if Diff can be used as offset in addressing mode of the user
704 // memory instruction.
705 (!MemUseValTy || TTI->isLegalAddressingMode(MemUseValTy,
706 /*BaseGV*/nullptr, /*BaseOffset*/Diff.getSExtValue(),
707 /*HasBaseReg*/true, /*Scale*/0)))
708 continue;
709 }
710 // We either have now a different constant type or the constant is not in
711 // range of an add with immediate anymore.
712 findAndMakeBaseConstant(MinValItr, CC, ConstInfoVec);
713 // Start a new base constant search.
714 MinValItr = CC;
715 }
716 // Finalize the last base constant search.
717 findAndMakeBaseConstant(MinValItr, ConstCandVec.end(), ConstInfoVec);
718}
719
720/// Updates the operand at Idx in instruction Inst with the result of
721/// instruction Mat. If the instruction is a PHI node then special
722/// handling for duplicate values from the same incoming basic block is
723/// required.
724/// \return The update will always succeed, but the return value indicated if
725/// Mat was used for the update or not.
726static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
727 if (auto PHI = dyn_cast<PHINode>(Inst)) {
728 // Check if any previous operand of the PHI node has the same incoming basic
729 // block. This is a very odd case that happens when the incoming basic block
730 // has a switch statement. In this case use the same value as the previous
731 // operand(s), otherwise we will fail verification due to different values.
732 // The values are actually the same, but the variable names are different
733 // and the verifier doesn't like that.
734 BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx);
735 for (unsigned i = 0; i < Idx; ++i) {
736 if (PHI->getIncomingBlock(i) == IncomingBB) {
737 Value *IncomingVal = PHI->getIncomingValue(i);
738 Inst->setOperand(Idx, IncomingVal);
739 return false;
740 }
741 }
742 }
743
744 Inst->setOperand(Idx, Mat);
745 return true;
746}
747
748/// Emit materialization code for all rebased constants and update their
749/// users.
750void ConstantHoistingPass::emitBaseConstants(Instruction *Base,
751 UserAdjustment *Adj) {
752 Instruction *Mat = Base;
753
754 // The same offset can be dereferenced to different types in nested struct.
755 if (!Adj->Offset && Adj->Ty && Adj->Ty != Base->getType())
756 Adj->Offset = ConstantInt::get(Type::getInt32Ty(*Ctx), 0);
757
758 if (Adj->Offset) {
759 if (Adj->Ty) {
760 // Constant being rebased is a ConstantExpr.
761 Mat = GetElementPtrInst::Create(Type::getInt8Ty(*Ctx), Base, Adj->Offset,
762 "mat_gep", Adj->MatInsertPt);
763 // Hide it behind a bitcast.
764 Mat = new BitCastInst(Mat, Adj->Ty, "mat_bitcast", Adj->MatInsertPt);
765 } else
766 // Constant being rebased is a ConstantInt.
767 Mat = BinaryOperator::Create(Instruction::Add, Base, Adj->Offset,
768 "const_mat", Adj->MatInsertPt);
769
770 LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
771 << " + " << *Adj->Offset << ") in BB "
772 << Mat->getParent()->getName() << '\n'
773 << *Mat << '\n');
774 Mat->setDebugLoc(Adj->User.Inst->getDebugLoc());
775 }
776 Value *Opnd = Adj->User.Inst->getOperand(Adj->User.OpndIdx);
777
778 // Visit constant integer.
779 if (isa<ConstantInt>(Opnd)) {
780 LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
781 if (!updateOperand(Adj->User.Inst, Adj->User.OpndIdx, Mat) && Adj->Offset)
782 Mat->eraseFromParent();
783 LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n');
784 return;
785 }
786
787 // Visit cast instruction.
788 if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
789 assert(CastInst->isCast() && "Expected an cast instruction!");
790 // Check if we already have visited this cast instruction before to avoid
791 // unnecessary cloning.
792 Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
793 if (!ClonedCastInst) {
794 ClonedCastInst = CastInst->clone();
795 ClonedCastInst->setOperand(0, Mat);
796 ClonedCastInst->insertAfter(CastInst);
797 // Use the same debug location as the original cast instruction.
798 ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
799 LLVM_DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
800 << "To : " << *ClonedCastInst << '\n');
801 }
802
803 LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
804 updateOperand(Adj->User.Inst, Adj->User.OpndIdx, ClonedCastInst);
805 LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n');
806 return;
807 }
808
809 // Visit constant expression.
810 if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
811 if (isa<GEPOperator>(ConstExpr)) {
812 // Operand is a ConstantGEP, replace it.
813 updateOperand(Adj->User.Inst, Adj->User.OpndIdx, Mat);
814 return;
815 }
816
817 // Aside from constant GEPs, only constant cast expressions are collected.
818 assert(ConstExpr->isCast() && "ConstExpr should be a cast");
819 Instruction *ConstExprInst = ConstExpr->getAsInstruction(Adj->MatInsertPt);
820 ConstExprInst->setOperand(0, Mat);
821
822 // Use the same debug location as the instruction we are about to update.
823 ConstExprInst->setDebugLoc(Adj->User.Inst->getDebugLoc());
824
825 LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
826 << "From : " << *ConstExpr << '\n');
827 LLVM_DEBUG(dbgs() << "Update: " << *Adj->User.Inst << '\n');
828 if (!updateOperand(Adj->User.Inst, Adj->User.OpndIdx, ConstExprInst)) {
829 ConstExprInst->eraseFromParent();
830 if (Adj->Offset)
831 Mat->eraseFromParent();
832 }
833 LLVM_DEBUG(dbgs() << "To : " << *Adj->User.Inst << '\n');
834 return;
835 }
836}
837
838/// Hoist and hide the base constant behind a bitcast and emit
839/// materialization code for derived constants.
840bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
841 bool MadeChange = false;
843 BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
844 for (const consthoist::ConstantInfo &ConstInfo : ConstInfoVec) {
846 collectMatInsertPts(ConstInfo.RebasedConstants, MatInsertPts);
848 findConstantInsertionPoint(ConstInfo, MatInsertPts);
849 // We can have an empty set if the function contains unreachable blocks.
850 if (IPSet.empty())
851 continue;
852
853 unsigned UsesNum = 0;
854 unsigned ReBasesNum = 0;
855 unsigned NotRebasedNum = 0;
856 for (Instruction *IP : IPSet) {
857 // First, collect constants depending on this IP of the base.
858 UsesNum = 0;
860 unsigned MatCtr = 0;
861 for (auto const &RCI : ConstInfo.RebasedConstants) {
862 UsesNum += RCI.Uses.size();
863 for (auto const &U : RCI.Uses) {
864 Instruction *MatInsertPt = MatInsertPts[MatCtr++];
865 BasicBlock *OrigMatInsertBB = MatInsertPt->getParent();
866 // If Base constant is to be inserted in multiple places,
867 // generate rebase for U using the Base dominating U.
868 if (IPSet.size() == 1 ||
869 DT->dominates(IP->getParent(), OrigMatInsertBB))
870 ToBeRebased.emplace_back(RCI.Offset, RCI.Ty, MatInsertPt, U);
871 }
872 }
873
874 // If only few constants depend on this IP of base, skip rebasing,
875 // assuming the base and the rebased have the same materialization cost.
876 if (ToBeRebased.size() < MinNumOfDependentToRebase) {
877 NotRebasedNum += ToBeRebased.size();
878 continue;
879 }
880
881 // Emit an instance of the base at this IP.
882 Instruction *Base = nullptr;
883 // Hoist and hide the base constant behind a bitcast.
884 if (ConstInfo.BaseExpr) {
885 assert(BaseGV && "A base constant expression must have an base GV");
886 Type *Ty = ConstInfo.BaseExpr->getType();
887 Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const", IP);
888 } else {
889 IntegerType *Ty = ConstInfo.BaseInt->getIntegerType();
890 Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const", IP);
891 }
892
893 Base->setDebugLoc(IP->getDebugLoc());
894
895 LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt
896 << ") to BB " << IP->getParent()->getName() << '\n'
897 << *Base << '\n');
898
899 // Emit materialization code for rebased constants depending on this IP.
900 for (UserAdjustment &R : ToBeRebased) {
901 emitBaseConstants(Base, &R);
902 ReBasesNum++;
903 // Use the same debug location as the last user of the constant.
905 Base->getDebugLoc(), R.User.Inst->getDebugLoc()));
906 }
907 assert(!Base->use_empty() && "The use list is empty!?");
908 assert(isa<Instruction>(Base->user_back()) &&
909 "All uses should be instructions.");
910 }
911 (void)UsesNum;
912 (void)ReBasesNum;
913 (void)NotRebasedNum;
914 // Expect all uses are rebased after rebase is done.
915 assert(UsesNum == (ReBasesNum + NotRebasedNum) &&
916 "Not all uses are rebased");
917
918 NumConstantsHoisted++;
919
920 // Base constant is also included in ConstInfo.RebasedConstants, so
921 // deduct 1 from ConstInfo.RebasedConstants.size().
922 NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1;
923
924 MadeChange = true;
925 }
926 return MadeChange;
927}
928
929/// Check all cast instructions we made a copy of and remove them if they
930/// have no more users.
931void ConstantHoistingPass::deleteDeadCastInst() const {
932 for (auto const &I : ClonedCastMap)
933 if (I.first->use_empty())
934 I.first->eraseFromParent();
935}
936
937/// Optimize expensive integer constants in the given function.
940 BasicBlock &Entry, ProfileSummaryInfo *PSI) {
941 this->TTI = &TTI;
942 this->DT = &DT;
943 this->BFI = BFI;
944 this->DL = &Fn.getParent()->getDataLayout();
945 this->Ctx = &Fn.getContext();
946 this->Entry = &Entry;
947 this->PSI = PSI;
948 this->OptForSize = Entry.getParent()->hasOptSize() ||
949 llvm::shouldOptimizeForSize(Entry.getParent(), PSI, BFI,
951
952 // Collect all constant candidates.
953 collectConstantCandidates(Fn);
954
955 // Combine constants that can be easily materialized with an add from a common
956 // base constant.
957 if (!ConstIntCandVec.empty())
958 findBaseConstants(nullptr);
959 for (const auto &MapEntry : ConstGEPCandMap)
960 if (!MapEntry.second.empty())
961 findBaseConstants(MapEntry.first);
962
963 // Finally hoist the base constant and emit materialization code for dependent
964 // constants.
965 bool MadeChange = false;
966 if (!ConstIntInfoVec.empty())
967 MadeChange = emitBaseConstants(nullptr);
968 for (const auto &MapEntry : ConstGEPInfoMap)
969 if (!MapEntry.second.empty())
970 MadeChange |= emitBaseConstants(MapEntry.first);
971
972
973 // Cleanup dead instructions.
974 deleteDeadCastInst();
975
976 cleanup();
977
978 return MadeChange;
979}
980
983 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
984 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
987 : nullptr;
988 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
989 auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
990 if (!runImpl(F, TTI, DT, BFI, F.getEntryBlock(), PSI))
991 return PreservedAnalyses::all();
992
995 return PA;
996}
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
Class for arbitrary precision integers.
Definition: APInt.h:76
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1439
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:1513
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
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
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:656
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, 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:579
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:1016
bool isCast() const
Return true if this is a convert constant expression.
Definition: Constants.cpp:1514
Instruction * getAsInstruction(Instruction *InsertBefore=nullptr) const
Returns an Instruction which implements the same operation as this ConstantExpr.
Definition: Constants.cpp:3306
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:79
IntegerType * getIntegerType() const
Variant of the getType() method to always return an IntegerType, which reduces the amount of casting ...
Definition: Constants.h:183
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:144
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:782
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:342
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:294
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:259
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:453
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:801
const BasicBlock * getParent() const
Definition: Instruction.h:151
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:251
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:450
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:184
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:287
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:783
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:317
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...
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
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:2004
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:4031
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.