LLVM 17.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 if (MadeChange) {
159 LLVM_DEBUG(dbgs() << "********** Function after Constant Hoisting: "
160 << Fn.getName() << '\n');
161 LLVM_DEBUG(dbgs() << Fn);
162 }
163 LLVM_DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
164
165 return MadeChange;
166}
167
168/// Find the constant materialization insertion point.
169Instruction *ConstantHoistingPass::findMatInsertPt(Instruction *Inst,
170 unsigned Idx) const {
171 // If the operand is a cast instruction, then we have to materialize the
172 // constant before the cast instruction.
173 if (Idx != ~0U) {
174 Value *Opnd = Inst->getOperand(Idx);
175 if (auto CastInst = dyn_cast<Instruction>(Opnd))
176 if (CastInst->isCast())
177 return CastInst;
178 }
179
180 // The simple and common case. This also includes constant expressions.
181 if (!isa<PHINode>(Inst) && !Inst->isEHPad())
182 return Inst;
183
184 // We can't insert directly before a phi node or an eh pad. Insert before
185 // the terminator of the incoming or dominating block.
186 assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!");
187 BasicBlock *InsertionBlock = nullptr;
188 if (Idx != ~0U && isa<PHINode>(Inst)) {
189 InsertionBlock = cast<PHINode>(Inst)->getIncomingBlock(Idx);
190 if (!InsertionBlock->isEHPad()) {
191 return InsertionBlock->getTerminator();
192 }
193 } else {
194 InsertionBlock = Inst->getParent();
195 }
196
197 // This must be an EH pad. Iterate over immediate dominators until we find a
198 // non-EH pad. We need to skip over catchswitch blocks, which are both EH pads
199 // and terminators.
200 auto *IDom = DT->getNode(InsertionBlock)->getIDom();
201 while (IDom->getBlock()->isEHPad()) {
202 assert(Entry != IDom->getBlock() && "eh pad in entry block");
203 IDom = IDom->getIDom();
204 }
205
206 return IDom->getBlock()->getTerminator();
207}
208
209/// Given \p BBs as input, find another set of BBs which collectively
210/// dominates \p BBs and have the minimal sum of frequencies. Return the BB
211/// set found in \p BBs.
213 BasicBlock *Entry,
215 assert(!BBs.count(Entry) && "Assume Entry is not in BBs");
216 // Nodes on the current path to the root.
218 // Candidates includes any block 'BB' in set 'BBs' that is not strictly
219 // dominated by any other blocks in set 'BBs', and all nodes in the path
220 // in the dominator tree from Entry to 'BB'.
222 for (auto *BB : BBs) {
223 // Ignore unreachable basic blocks.
224 if (!DT.isReachableFromEntry(BB))
225 continue;
226 Path.clear();
227 // Walk up the dominator tree until Entry or another BB in BBs
228 // is reached. Insert the nodes on the way to the Path.
229 BasicBlock *Node = BB;
230 // The "Path" is a candidate path to be added into Candidates set.
231 bool isCandidate = false;
232 do {
233 Path.insert(Node);
234 if (Node == Entry || Candidates.count(Node)) {
235 isCandidate = true;
236 break;
237 }
238 assert(DT.getNode(Node)->getIDom() &&
239 "Entry doens't dominate current Node");
240 Node = DT.getNode(Node)->getIDom()->getBlock();
241 } while (!BBs.count(Node));
242
243 // If isCandidate is false, Node is another Block in BBs dominating
244 // current 'BB'. Drop the nodes on the Path.
245 if (!isCandidate)
246 continue;
247
248 // Add nodes on the Path into Candidates.
249 Candidates.insert(Path.begin(), Path.end());
250 }
251
252 // Sort the nodes in Candidates in top-down order and save the nodes
253 // in Orders.
254 unsigned Idx = 0;
256 Orders.push_back(Entry);
257 while (Idx != Orders.size()) {
258 BasicBlock *Node = Orders[Idx++];
259 for (auto *ChildDomNode : DT.getNode(Node)->children()) {
260 if (Candidates.count(ChildDomNode->getBlock()))
261 Orders.push_back(ChildDomNode->getBlock());
262 }
263 }
264
265 // Visit Orders in bottom-up order.
266 using InsertPtsCostPair =
267 std::pair<SetVector<BasicBlock *>, BlockFrequency>;
268
269 // InsertPtsMap is a map from a BB to the best insertion points for the
270 // subtree of BB (subtree not including the BB itself).
272 InsertPtsMap.reserve(Orders.size() + 1);
273 for (BasicBlock *Node : llvm::reverse(Orders)) {
274 bool NodeInBBs = BBs.count(Node);
275 auto &InsertPts = InsertPtsMap[Node].first;
276 BlockFrequency &InsertPtsFreq = InsertPtsMap[Node].second;
277
278 // Return the optimal insert points in BBs.
279 if (Node == Entry) {
280 BBs.clear();
281 if (InsertPtsFreq > BFI.getBlockFreq(Node) ||
282 (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1))
283 BBs.insert(Entry);
284 else
285 BBs.insert(InsertPts.begin(), InsertPts.end());
286 break;
287 }
288
289 BasicBlock *Parent = DT.getNode(Node)->getIDom()->getBlock();
290 // Initially, ParentInsertPts is empty and ParentPtsFreq is 0. Every child
291 // will update its parent's ParentInsertPts and ParentPtsFreq.
292 auto &ParentInsertPts = InsertPtsMap[Parent].first;
293 BlockFrequency &ParentPtsFreq = InsertPtsMap[Parent].second;
294 // Choose to insert in Node or in subtree of Node.
295 // Don't hoist to EHPad because we may not find a proper place to insert
296 // in EHPad.
297 // If the total frequency of InsertPts is the same as the frequency of the
298 // target Node, and InsertPts contains more than one nodes, choose hoisting
299 // to reduce code size.
300 if (NodeInBBs ||
301 (!Node->isEHPad() &&
302 (InsertPtsFreq > BFI.getBlockFreq(Node) ||
303 (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1)))) {
304 ParentInsertPts.insert(Node);
305 ParentPtsFreq += BFI.getBlockFreq(Node);
306 } else {
307 ParentInsertPts.insert(InsertPts.begin(), InsertPts.end());
308 ParentPtsFreq += InsertPtsFreq;
309 }
310 }
311}
312
313/// Find an insertion point that dominates all uses.
314SetVector<Instruction *> ConstantHoistingPass::findConstantInsertionPoint(
315 const ConstantInfo &ConstInfo) const {
316 assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
317 // Collect all basic blocks.
319 SetVector<Instruction *> InsertPts;
320 for (auto const &RCI : ConstInfo.RebasedConstants)
321 for (auto const &U : RCI.Uses)
322 BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());
323
324 if (BBs.count(Entry)) {
325 InsertPts.insert(&Entry->front());
326 return InsertPts;
327 }
328
329 if (BFI) {
330 findBestInsertionSet(*DT, *BFI, Entry, BBs);
331 for (auto *BB : BBs) {
332 BasicBlock::iterator InsertPt = BB->begin();
333 for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
334 ;
335 InsertPts.insert(&*InsertPt);
336 }
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 *PtrIntTy = DL->getIntPtrType(*Ctx, GVPtrTy->getAddressSpace());
414 APInt Offset(DL->getTypeSizeInBits(PtrIntTy), /*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, PtrIntTy,
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,
755 Type *Ty,
756 const ConstantUser &ConstUser) {
757 Instruction *Mat = Base;
758
759 // The same offset can be dereferenced to different types in nested struct.
760 if (!Offset && Ty && Ty != Base->getType())
762
763 if (Offset) {
764 Instruction *InsertionPt = findMatInsertPt(ConstUser.Inst,
765 ConstUser.OpndIdx);
766 if (Ty) {
767 // Constant being rebased is a ConstantExpr.
768 PointerType *Int8PtrTy = Type::getInt8PtrTy(*Ctx,
769 cast<PointerType>(Ty)->getAddressSpace());
770 Base = new BitCastInst(Base, Int8PtrTy, "base_bitcast", InsertionPt);
772 Offset, "mat_gep", InsertionPt);
773 Mat = new BitCastInst(Mat, Ty, "mat_bitcast", InsertionPt);
774 } else
775 // Constant being rebased is a ConstantInt.
776 Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
777 "const_mat", InsertionPt);
778
779 LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
780 << " + " << *Offset << ") in BB "
781 << Mat->getParent()->getName() << '\n'
782 << *Mat << '\n');
783 Mat->setDebugLoc(ConstUser.Inst->getDebugLoc());
784 }
785 Value *Opnd = ConstUser.Inst->getOperand(ConstUser.OpndIdx);
786
787 // Visit constant integer.
788 if (isa<ConstantInt>(Opnd)) {
789 LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
790 if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat) && Offset)
791 Mat->eraseFromParent();
792 LLVM_DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
793 return;
794 }
795
796 // Visit cast instruction.
797 if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
798 assert(CastInst->isCast() && "Expected an cast instruction!");
799 // Check if we already have visited this cast instruction before to avoid
800 // unnecessary cloning.
801 Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
802 if (!ClonedCastInst) {
803 ClonedCastInst = CastInst->clone();
804 ClonedCastInst->setOperand(0, Mat);
805 ClonedCastInst->insertAfter(CastInst);
806 // Use the same debug location as the original cast instruction.
807 ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
808 LLVM_DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
809 << "To : " << *ClonedCastInst << '\n');
810 }
811
812 LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
813 updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
814 LLVM_DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
815 return;
816 }
817
818 // Visit constant expression.
819 if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
820 if (isa<GEPOperator>(ConstExpr)) {
821 // Operand is a ConstantGEP, replace it.
822 updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat);
823 return;
824 }
825
826 // Aside from constant GEPs, only constant cast expressions are collected.
827 assert(ConstExpr->isCast() && "ConstExpr should be a cast");
828 Instruction *ConstExprInst = ConstExpr->getAsInstruction(
829 findMatInsertPt(ConstUser.Inst, ConstUser.OpndIdx));
830 ConstExprInst->setOperand(0, Mat);
831
832 // Use the same debug location as the instruction we are about to update.
833 ConstExprInst->setDebugLoc(ConstUser.Inst->getDebugLoc());
834
835 LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
836 << "From : " << *ConstExpr << '\n');
837 LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
838 if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ConstExprInst)) {
839 ConstExprInst->eraseFromParent();
840 if (Offset)
841 Mat->eraseFromParent();
842 }
843 LLVM_DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
844 return;
845 }
846}
847
848/// Hoist and hide the base constant behind a bitcast and emit
849/// materialization code for derived constants.
850bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
851 bool MadeChange = false;
853 BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
854 for (auto const &ConstInfo : ConstInfoVec) {
855 SetVector<Instruction *> IPSet = findConstantInsertionPoint(ConstInfo);
856 // We can have an empty set if the function contains unreachable blocks.
857 if (IPSet.empty())
858 continue;
859
860 unsigned UsesNum = 0;
861 unsigned ReBasesNum = 0;
862 unsigned NotRebasedNum = 0;
863 for (Instruction *IP : IPSet) {
864 // First, collect constants depending on this IP of the base.
865 unsigned Uses = 0;
866 using RebasedUse = std::tuple<Constant *, Type *, ConstantUser>;
867 SmallVector<RebasedUse, 4> ToBeRebased;
868 for (auto const &RCI : ConstInfo.RebasedConstants) {
869 for (auto const &U : RCI.Uses) {
870 Uses++;
871 BasicBlock *OrigMatInsertBB =
872 findMatInsertPt(U.Inst, U.OpndIdx)->getParent();
873 // If Base constant is to be inserted in multiple places,
874 // generate rebase for U using the Base dominating U.
875 if (IPSet.size() == 1 ||
876 DT->dominates(IP->getParent(), OrigMatInsertBB))
877 ToBeRebased.push_back(RebasedUse(RCI.Offset, RCI.Ty, U));
878 }
879 }
880 UsesNum = Uses;
881
882 // If only few constants depend on this IP of base, skip rebasing,
883 // assuming the base and the rebased have the same materialization cost.
884 if (ToBeRebased.size() < MinNumOfDependentToRebase) {
885 NotRebasedNum += ToBeRebased.size();
886 continue;
887 }
888
889 // Emit an instance of the base at this IP.
890 Instruction *Base = nullptr;
891 // Hoist and hide the base constant behind a bitcast.
892 if (ConstInfo.BaseExpr) {
893 assert(BaseGV && "A base constant expression must have an base GV");
894 Type *Ty = ConstInfo.BaseExpr->getType();
895 Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const", IP);
896 } else {
897 IntegerType *Ty = ConstInfo.BaseInt->getType();
898 Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const", IP);
899 }
900
901 Base->setDebugLoc(IP->getDebugLoc());
902
903 LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt
904 << ") to BB " << IP->getParent()->getName() << '\n'
905 << *Base << '\n');
906
907 // Emit materialization code for rebased constants depending on this IP.
908 for (auto const &R : ToBeRebased) {
909 Constant *Off = std::get<0>(R);
910 Type *Ty = std::get<1>(R);
911 ConstantUser U = std::get<2>(R);
912 emitBaseConstants(Base, Off, Ty, U);
913 ReBasesNum++;
914 // Use the same debug location as the last user of the constant.
916 Base->getDebugLoc(), U.Inst->getDebugLoc()));
917 }
918 assert(!Base->use_empty() && "The use list is empty!?");
919 assert(isa<Instruction>(Base->user_back()) &&
920 "All uses should be instructions.");
921 }
922 (void)UsesNum;
923 (void)ReBasesNum;
924 (void)NotRebasedNum;
925 // Expect all uses are rebased after rebase is done.
926 assert(UsesNum == (ReBasesNum + NotRebasedNum) &&
927 "Not all uses are rebased");
928
929 NumConstantsHoisted++;
930
931 // Base constant is also included in ConstInfo.RebasedConstants, so
932 // deduct 1 from ConstInfo.RebasedConstants.size().
933 NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1;
934
935 MadeChange = true;
936 }
937 return MadeChange;
938}
939
940/// Check all cast instructions we made a copy of and remove them if they
941/// have no more users.
942void ConstantHoistingPass::deleteDeadCastInst() const {
943 for (auto const &I : ClonedCastMap)
944 if (I.first->use_empty())
945 I.first->eraseFromParent();
946}
947
948/// Optimize expensive integer constants in the given function.
951 BasicBlock &Entry, ProfileSummaryInfo *PSI) {
952 this->TTI = &TTI;
953 this->DT = &DT;
954 this->BFI = BFI;
955 this->DL = &Fn.getParent()->getDataLayout();
956 this->Ctx = &Fn.getContext();
957 this->Entry = &Entry;
958 this->PSI = PSI;
959 // Collect all constant candidates.
960 collectConstantCandidates(Fn);
961
962 // Combine constants that can be easily materialized with an add from a common
963 // base constant.
964 if (!ConstIntCandVec.empty())
965 findBaseConstants(nullptr);
966 for (const auto &MapEntry : ConstGEPCandMap)
967 if (!MapEntry.second.empty())
968 findBaseConstants(MapEntry.first);
969
970 // Finally hoist the base constant and emit materialization code for dependent
971 // constants.
972 bool MadeChange = false;
973 if (!ConstIntInfoVec.empty())
974 MadeChange = emitBaseConstants(nullptr);
975 for (const auto &MapEntry : ConstGEPInfoMap)
976 if (!MapEntry.second.empty())
977 MadeChange |= emitBaseConstants(MapEntry.first);
978
979
980 // Cleanup dead instructions.
981 deleteDeadCastInst();
982
983 cleanup();
984
985 return MadeChange;
986}
987
990 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
991 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
994 : nullptr;
995 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
996 auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
997 if (!runImpl(F, TTI, DT, BFI, F.getEntryBlock(), PSI))
998 return PreservedAnalyses::all();
999
1002 return PA;
1003}
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
SmallPtrSet< MachineInstr *, 2 > Uses
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
@ SI
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:75
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:463
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1516
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
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:265
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
const Instruction & front() const
Definition: BasicBlock.h:326
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:512
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:127
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:113
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:428
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:998
bool isCast() const
Return true if this is a convert constant expression.
Definition: Constants.cpp:1444
Instruction * getAsInstruction(Instruction *InsertBefore=nullptr) const
Returns an Instruction which implements the same operation as this ConstantExpr.
Definition: Constants.cpp:3423
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:172
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:887
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:132
This is an important base class in LLVM.
Definition: Constant.h:41
static const DILocation * getMergedLocation(const DILocation *LocA, const DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
Definition: DataLayout.cpp:849
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:676
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Definition: DenseMap.h:71
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
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:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
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:358
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:308
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:735
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:644
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:315
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
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
bool isCast() const
Definition: Instruction.h:176
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:358
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:685
const BasicBlock * getParent() const
Definition: Instruction.h:90
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:168
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:355
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Definition: Instruction.cpp:94
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.cpp:398
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1058
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:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
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:40
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:208
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
void clear()
Completely clear the SetVector.
Definition: SetVector.h:213
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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:258
static IntegerType * getInt8Ty(LLVMContext &C)
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
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:308
AddressSpace getAddressSpace(T *V)
Definition: AVR.h:66
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:406
void stable_sort(R &&Range)
Definition: STLExtras.h:1948
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:484
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:3398
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.