LLVM  16.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"
38 #include "llvm/ADT/None.h"
39 #include "llvm/ADT/Optional.h"
40 #include "llvm/ADT/SmallPtrSet.h"
41 #include "llvm/ADT/SmallVector.h"
42 #include "llvm/ADT/Statistic.h"
46 #include "llvm/IR/BasicBlock.h"
47 #include "llvm/IR/Constants.h"
49 #include "llvm/IR/Dominators.h"
50 #include "llvm/IR/Function.h"
51 #include "llvm/IR/InstrTypes.h"
52 #include "llvm/IR/Instruction.h"
53 #include "llvm/IR/Instructions.h"
54 #include "llvm/IR/IntrinsicInst.h"
55 #include "llvm/IR/Operator.h"
56 #include "llvm/IR/Value.h"
57 #include "llvm/InitializePasses.h"
58 #include "llvm/Pass.h"
60 #include "llvm/Support/Casting.h"
62 #include "llvm/Support/Debug.h"
64 #include "llvm/Transforms/Scalar.h"
67 #include <algorithm>
68 #include <cassert>
69 #include <cstdint>
70 #include <iterator>
71 #include <tuple>
72 #include <utility>
73 
74 using namespace llvm;
75 using namespace consthoist;
76 
77 #define DEBUG_TYPE "consthoist"
78 
79 STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
80 STATISTIC(NumConstantsRebased, "Number of constants rebased");
81 
83  "consthoist-with-block-frequency", cl::init(true), cl::Hidden,
84  cl::desc("Enable the use of the block frequency analysis to reduce the "
85  "chance to execute const materialization more frequently than "
86  "without hoisting."));
87 
89  "consthoist-gep", cl::init(false), cl::Hidden,
90  cl::desc("Try hoisting constant gep expressions"));
91 
92 static cl::opt<unsigned>
93 MinNumOfDependentToRebase("consthoist-min-num-to-rebase",
94  cl::desc("Do not rebase if number of dependent constants of a Base is less "
95  "than this number."),
96  cl::init(0), cl::Hidden);
97 
98 namespace {
99 
100 /// The constant hoisting pass.
101 class ConstantHoistingLegacyPass : public FunctionPass {
102 public:
103  static char ID; // Pass identification, replacement for typeid
104 
105  ConstantHoistingLegacyPass() : FunctionPass(ID) {
107  }
108 
109  bool runOnFunction(Function &Fn) override;
110 
111  StringRef getPassName() const override { return "Constant Hoisting"; }
112 
113  void getAnalysisUsage(AnalysisUsage &AU) const override {
114  AU.setPreservesCFG();
120  }
121 
122 private:
124 };
125 
126 } // end anonymous namespace
127 
129 
130 INITIALIZE_PASS_BEGIN(ConstantHoistingLegacyPass, "consthoist",
131  "Constant Hoisting", false, false)
136 INITIALIZE_PASS_END(ConstantHoistingLegacyPass, "consthoist",
138 
140  return new ConstantHoistingLegacyPass();
141 }
142 
143 /// Perform the constant hoisting optimization for the given function.
145  if (skipFunction(Fn))
146  return false;
147 
148  LLVM_DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
149  LLVM_DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
150 
151  bool MadeChange =
152  Impl.runImpl(Fn, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn),
153  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
155  ? &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI()
156  : nullptr,
157  Fn.getEntryBlock(),
158  &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
159 
160  if (MadeChange) {
161  LLVM_DEBUG(dbgs() << "********** Function after Constant Hoisting: "
162  << Fn.getName() << '\n');
163  LLVM_DEBUG(dbgs() << Fn);
164  }
165  LLVM_DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
166 
167  return MadeChange;
168 }
169 
170 /// Find the constant materialization insertion point.
171 Instruction *ConstantHoistingPass::findMatInsertPt(Instruction *Inst,
172  unsigned Idx) const {
173  // If the operand is a cast instruction, then we have to materialize the
174  // constant before the cast instruction.
175  if (Idx != ~0U) {
176  Value *Opnd = Inst->getOperand(Idx);
177  if (auto CastInst = dyn_cast<Instruction>(Opnd))
178  if (CastInst->isCast())
179  return CastInst;
180  }
181 
182  // The simple and common case. This also includes constant expressions.
183  if (!isa<PHINode>(Inst) && !Inst->isEHPad())
184  return Inst;
185 
186  // We can't insert directly before a phi node or an eh pad. Insert before
187  // the terminator of the incoming or dominating block.
188  assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!");
189  BasicBlock *InsertionBlock = nullptr;
190  if (Idx != ~0U && isa<PHINode>(Inst)) {
191  InsertionBlock = cast<PHINode>(Inst)->getIncomingBlock(Idx);
192  if (!InsertionBlock->isEHPad()) {
193  return InsertionBlock->getTerminator();
194  }
195  } else {
196  InsertionBlock = Inst->getParent();
197  }
198 
199  // This must be an EH pad. Iterate over immediate dominators until we find a
200  // non-EH pad. We need to skip over catchswitch blocks, which are both EH pads
201  // and terminators.
202  auto *IDom = DT->getNode(InsertionBlock)->getIDom();
203  while (IDom->getBlock()->isEHPad()) {
204  assert(Entry != IDom->getBlock() && "eh pad in entry block");
205  IDom = IDom->getIDom();
206  }
207 
208  return IDom->getBlock()->getTerminator();
209 }
210 
211 /// Given \p BBs as input, find another set of BBs which collectively
212 /// dominates \p BBs and have the minimal sum of frequencies. Return the BB
213 /// set found in \p BBs.
215  BasicBlock *Entry,
217  assert(!BBs.count(Entry) && "Assume Entry is not in BBs");
218  // Nodes on the current path to the root.
220  // Candidates includes any block 'BB' in set 'BBs' that is not strictly
221  // dominated by any other blocks in set 'BBs', and all nodes in the path
222  // in the dominator tree from Entry to 'BB'.
224  for (auto *BB : BBs) {
225  // Ignore unreachable basic blocks.
226  if (!DT.isReachableFromEntry(BB))
227  continue;
228  Path.clear();
229  // Walk up the dominator tree until Entry or another BB in BBs
230  // is reached. Insert the nodes on the way to the Path.
231  BasicBlock *Node = BB;
232  // The "Path" is a candidate path to be added into Candidates set.
233  bool isCandidate = false;
234  do {
235  Path.insert(Node);
236  if (Node == Entry || Candidates.count(Node)) {
237  isCandidate = true;
238  break;
239  }
240  assert(DT.getNode(Node)->getIDom() &&
241  "Entry doens't dominate current Node");
242  Node = DT.getNode(Node)->getIDom()->getBlock();
243  } while (!BBs.count(Node));
244 
245  // If isCandidate is false, Node is another Block in BBs dominating
246  // current 'BB'. Drop the nodes on the Path.
247  if (!isCandidate)
248  continue;
249 
250  // Add nodes on the Path into Candidates.
251  Candidates.insert(Path.begin(), Path.end());
252  }
253 
254  // Sort the nodes in Candidates in top-down order and save the nodes
255  // in Orders.
256  unsigned Idx = 0;
258  Orders.push_back(Entry);
259  while (Idx != Orders.size()) {
260  BasicBlock *Node = Orders[Idx++];
261  for (auto *ChildDomNode : DT.getNode(Node)->children()) {
262  if (Candidates.count(ChildDomNode->getBlock()))
263  Orders.push_back(ChildDomNode->getBlock());
264  }
265  }
266 
267  // Visit Orders in bottom-up order.
268  using InsertPtsCostPair =
269  std::pair<SetVector<BasicBlock *>, BlockFrequency>;
270 
271  // InsertPtsMap is a map from a BB to the best insertion points for the
272  // subtree of BB (subtree not including the BB itself).
274  InsertPtsMap.reserve(Orders.size() + 1);
275  for (BasicBlock *Node : llvm::reverse(Orders)) {
276  bool NodeInBBs = BBs.count(Node);
277  auto &InsertPts = InsertPtsMap[Node].first;
278  BlockFrequency &InsertPtsFreq = InsertPtsMap[Node].second;
279 
280  // Return the optimal insert points in BBs.
281  if (Node == Entry) {
282  BBs.clear();
283  if (InsertPtsFreq > BFI.getBlockFreq(Node) ||
284  (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1))
285  BBs.insert(Entry);
286  else
287  BBs.insert(InsertPts.begin(), InsertPts.end());
288  break;
289  }
290 
291  BasicBlock *Parent = DT.getNode(Node)->getIDom()->getBlock();
292  // Initially, ParentInsertPts is empty and ParentPtsFreq is 0. Every child
293  // will update its parent's ParentInsertPts and ParentPtsFreq.
294  auto &ParentInsertPts = InsertPtsMap[Parent].first;
295  BlockFrequency &ParentPtsFreq = InsertPtsMap[Parent].second;
296  // Choose to insert in Node or in subtree of Node.
297  // Don't hoist to EHPad because we may not find a proper place to insert
298  // in EHPad.
299  // If the total frequency of InsertPts is the same as the frequency of the
300  // target Node, and InsertPts contains more than one nodes, choose hoisting
301  // to reduce code size.
302  if (NodeInBBs ||
303  (!Node->isEHPad() &&
304  (InsertPtsFreq > BFI.getBlockFreq(Node) ||
305  (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1)))) {
306  ParentInsertPts.insert(Node);
307  ParentPtsFreq += BFI.getBlockFreq(Node);
308  } else {
309  ParentInsertPts.insert(InsertPts.begin(), InsertPts.end());
310  ParentPtsFreq += InsertPtsFreq;
311  }
312  }
313 }
314 
315 /// Find an insertion point that dominates all uses.
316 SetVector<Instruction *> ConstantHoistingPass::findConstantInsertionPoint(
317  const ConstantInfo &ConstInfo) const {
318  assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
319  // Collect all basic blocks.
321  SetVector<Instruction *> InsertPts;
322  for (auto const &RCI : ConstInfo.RebasedConstants)
323  for (auto const &U : RCI.Uses)
324  BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());
325 
326  if (BBs.count(Entry)) {
327  InsertPts.insert(&Entry->front());
328  return InsertPts;
329  }
330 
331  if (BFI) {
332  findBestInsertionSet(*DT, *BFI, Entry, BBs);
333  for (auto *BB : BBs) {
334  BasicBlock::iterator InsertPt = BB->begin();
335  for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
336  ;
337  InsertPts.insert(&*InsertPt);
338  }
339  return InsertPts;
340  }
341 
342  while (BBs.size() >= 2) {
343  BasicBlock *BB, *BB1, *BB2;
344  BB1 = BBs.pop_back_val();
345  BB2 = BBs.pop_back_val();
346  BB = DT->findNearestCommonDominator(BB1, BB2);
347  if (BB == Entry) {
348  InsertPts.insert(&Entry->front());
349  return InsertPts;
350  }
351  BBs.insert(BB);
352  }
353  assert((BBs.size() == 1) && "Expected only one element.");
354  Instruction &FirstInst = (*BBs.begin())->front();
355  InsertPts.insert(findMatInsertPt(&FirstInst));
356  return InsertPts;
357 }
358 
359 /// Record constant integer ConstInt for instruction Inst at operand
360 /// index Idx.
361 ///
362 /// The operand at index Idx is not necessarily the constant integer itself. It
363 /// could also be a cast instruction or a constant expression that uses the
364 /// constant integer.
365 void ConstantHoistingPass::collectConstantCandidates(
366  ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
367  ConstantInt *ConstInt) {
369  // Ask the target about the cost of materializing the constant for the given
370  // instruction and operand index.
371  if (auto IntrInst = dyn_cast<IntrinsicInst>(Inst))
372  Cost = TTI->getIntImmCostIntrin(IntrInst->getIntrinsicID(), Idx,
373  ConstInt->getValue(), ConstInt->getType(),
375  else
377  Inst->getOpcode(), Idx, ConstInt->getValue(), ConstInt->getType(),
379 
380  // Ignore cheap integer constants.
381  if (Cost > TargetTransformInfo::TCC_Basic) {
382  ConstCandMapType::iterator Itr;
383  bool Inserted;
384  ConstPtrUnionType Cand = ConstInt;
385  std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
386  if (Inserted) {
387  ConstIntCandVec.push_back(ConstantCandidate(ConstInt));
388  Itr->second = ConstIntCandVec.size() - 1;
389  }
390  ConstIntCandVec[Itr->second].addUser(Inst, Idx, *Cost.getValue());
391  LLVM_DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx))) dbgs()
392  << "Collect constant " << *ConstInt << " from " << *Inst
393  << " with cost " << Cost << '\n';
394  else dbgs() << "Collect constant " << *ConstInt
395  << " indirectly from " << *Inst << " via "
396  << *Inst->getOperand(Idx) << " with cost " << Cost
397  << '\n';);
398  }
399 }
400 
401 /// Record constant GEP expression for instruction Inst at operand index Idx.
402 void ConstantHoistingPass::collectConstantCandidates(
403  ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
404  ConstantExpr *ConstExpr) {
405  // TODO: Handle vector GEPs
406  if (ConstExpr->getType()->isVectorTy())
407  return;
408 
409  GlobalVariable *BaseGV = dyn_cast<GlobalVariable>(ConstExpr->getOperand(0));
410  if (!BaseGV)
411  return;
412 
413  // Get offset from the base GV.
414  PointerType *GVPtrTy = cast<PointerType>(BaseGV->getType());
415  IntegerType *PtrIntTy = DL->getIntPtrType(*Ctx, GVPtrTy->getAddressSpace());
416  APInt Offset(DL->getTypeSizeInBits(PtrIntTy), /*val*/0, /*isSigned*/true);
417  auto *GEPO = cast<GEPOperator>(ConstExpr);
418 
419  // TODO: If we have a mix of inbounds and non-inbounds GEPs, then basing a
420  // non-inbounds GEP on an inbounds GEP is potentially incorrect. Restrict to
421  // inbounds GEP for now -- alternatively, we could drop inbounds from the
422  // constant expression,
423  if (!GEPO->isInBounds())
424  return;
425 
426  if (!GEPO->accumulateConstantOffset(*DL, Offset))
427  return;
428 
429  if (!Offset.isIntN(32))
430  return;
431 
432  // A constant GEP expression that has a GlobalVariable as base pointer is
433  // usually lowered to a load from constant pool. Such operation is unlikely
434  // to be cheaper than compute it by <Base + Offset>, which can be lowered to
435  // an ADD instruction or folded into Load/Store instruction.
437  TTI->getIntImmCostInst(Instruction::Add, 1, Offset, PtrIntTy,
439  ConstCandVecType &ExprCandVec = ConstGEPCandMap[BaseGV];
440  ConstCandMapType::iterator Itr;
441  bool Inserted;
442  ConstPtrUnionType Cand = ConstExpr;
443  std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
444  if (Inserted) {
445  ExprCandVec.push_back(ConstantCandidate(
446  ConstantInt::get(Type::getInt32Ty(*Ctx), Offset.getLimitedValue()),
447  ConstExpr));
448  Itr->second = ExprCandVec.size() - 1;
449  }
450  ExprCandVec[Itr->second].addUser(Inst, Idx, *Cost.getValue());
451 }
452 
453 /// Check the operand for instruction Inst at index Idx.
454 void ConstantHoistingPass::collectConstantCandidates(
455  ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx) {
456  Value *Opnd = Inst->getOperand(Idx);
457 
458  // Visit constant integers.
459  if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
460  collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
461  return;
462  }
463 
464  // Visit cast instructions that have constant integers.
465  if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
466  // Only visit cast instructions, which have been skipped. All other
467  // instructions should have already been visited.
468  if (!CastInst->isCast())
469  return;
470 
471  if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
472  // Pretend the constant is directly used by the instruction and ignore
473  // the cast instruction.
474  collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
475  return;
476  }
477  }
478 
479  // Visit constant expressions that have constant integers.
480  if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
481  // Handle constant gep expressions.
482  if (ConstHoistGEP && isa<GEPOperator>(ConstExpr))
483  collectConstantCandidates(ConstCandMap, Inst, Idx, ConstExpr);
484 
485  // Only visit constant cast expressions.
486  if (!ConstExpr->isCast())
487  return;
488 
489  if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
490  // Pretend the constant is directly used by the instruction and ignore
491  // the constant expression.
492  collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
493  return;
494  }
495  }
496 }
497 
498 /// Scan the instruction for expensive integer constants and record them
499 /// in the constant candidate vector.
500 void ConstantHoistingPass::collectConstantCandidates(
501  ConstCandMapType &ConstCandMap, Instruction *Inst) {
502  // Skip all cast instructions. They are visited indirectly later on.
503  if (Inst->isCast())
504  return;
505 
506  // Scan all operands.
507  for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
508  // The cost of materializing the constants (defined in
509  // `TargetTransformInfo::getIntImmCostInst`) for instructions which only
510  // take constant variables is lower than `TargetTransformInfo::TCC_Basic`.
511  // So it's safe for us to collect constant candidates from all
512  // IntrinsicInsts.
513  if (canReplaceOperandWithVariable(Inst, Idx)) {
514  collectConstantCandidates(ConstCandMap, Inst, Idx);
515  }
516  } // end of for all operands
517 }
518 
519 /// Collect all integer constants in the function that cannot be folded
520 /// into an instruction itself.
521 void ConstantHoistingPass::collectConstantCandidates(Function &Fn) {
522  ConstCandMapType ConstCandMap;
523  for (BasicBlock &BB : Fn) {
524  // Ignore unreachable basic blocks.
525  if (!DT->isReachableFromEntry(&BB))
526  continue;
527  for (Instruction &Inst : BB)
528  collectConstantCandidates(ConstCandMap, &Inst);
529  }
530 }
531 
532 // This helper function is necessary to deal with values that have different
533 // bit widths (APInt Operator- does not like that). If the value cannot be
534 // represented in uint64 we return an "empty" APInt. This is then interpreted
535 // as the value is not in range.
536 static Optional<APInt> calculateOffsetDiff(const APInt &V1, const APInt &V2) {
537  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.
573 unsigned
574 ConstantHoistingPass::maximizeConstantsInRange(ConstCandVecType::iterator S,
575  ConstCandVecType::iterator E,
576  ConstCandVecType::iterator &MaxCostItr) {
577  unsigned NumUses = 0;
578 
579  bool OptForSize = Entry->getParent()->hasOptSize() ||
580  llvm::shouldOptimizeForSize(Entry->getParent(), PSI, BFI,
582  if (!OptForSize || std::distance(S,E) > 100) {
583  for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
584  NumUses += ConstCand->Uses.size();
585  if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
586  MaxCostItr = ConstCand;
587  }
588  return NumUses;
589  }
590 
591  LLVM_DEBUG(dbgs() << "== Maximize constants in range ==\n");
592  InstructionCost MaxCost = -1;
593  for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
594  auto Value = ConstCand->ConstInt->getValue();
595  Type *Ty = ConstCand->ConstInt->getType();
596  InstructionCost Cost = 0;
597  NumUses += ConstCand->Uses.size();
598  LLVM_DEBUG(dbgs() << "= Constant: " << ConstCand->ConstInt->getValue()
599  << "\n");
600 
601  for (auto User : ConstCand->Uses) {
602  unsigned Opcode = User.Inst->getOpcode();
603  unsigned OpndIdx = User.OpndIdx;
604  Cost += TTI->getIntImmCostInst(Opcode, OpndIdx, Value, Ty,
606  LLVM_DEBUG(dbgs() << "Cost: " << Cost << "\n");
607 
608  for (auto C2 = S; C2 != E; ++C2) {
610  C2->ConstInt->getValue(),
611  ConstCand->ConstInt->getValue());
612  if (Diff) {
613  const InstructionCost ImmCosts =
614  TTI->getIntImmCodeSizeCost(Opcode, OpndIdx, Diff.value(), Ty);
615  Cost -= ImmCosts;
616  LLVM_DEBUG(dbgs() << "Offset " << Diff.value() << " "
617  << "has penalty: " << ImmCosts << "\n"
618  << "Adjusted cost: " << Cost << "\n");
619  }
620  }
621  }
622  LLVM_DEBUG(dbgs() << "Cumulative cost: " << Cost << "\n");
623  if (Cost > MaxCost) {
624  MaxCost = Cost;
625  MaxCostItr = ConstCand;
626  LLVM_DEBUG(dbgs() << "New candidate: " << MaxCostItr->ConstInt->getValue()
627  << "\n");
628  }
629  }
630  return NumUses;
631 }
632 
633 /// Find the base constant within the given range and rebase all other
634 /// constants with respect to the base constant.
635 void ConstantHoistingPass::findAndMakeBaseConstant(
636  ConstCandVecType::iterator S, ConstCandVecType::iterator E,
638  auto MaxCostItr = S;
639  unsigned NumUses = maximizeConstantsInRange(S, E, MaxCostItr);
640 
641  // Don't hoist constants that have only one use.
642  if (NumUses <= 1)
643  return;
644 
645  ConstantInt *ConstInt = MaxCostItr->ConstInt;
646  ConstantExpr *ConstExpr = MaxCostItr->ConstExpr;
647  ConstantInfo ConstInfo;
648  ConstInfo.BaseInt = ConstInt;
649  ConstInfo.BaseExpr = ConstExpr;
650  Type *Ty = ConstInt->getType();
651 
652  // Rebase the constants with respect to the base constant.
653  for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
654  APInt Diff = ConstCand->ConstInt->getValue() - ConstInt->getValue();
655  Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
656  Type *ConstTy =
657  ConstCand->ConstExpr ? ConstCand->ConstExpr->getType() : nullptr;
658  ConstInfo.RebasedConstants.push_back(
659  RebasedConstantInfo(std::move(ConstCand->Uses), Offset, ConstTy));
660  }
661  ConstInfoVec.push_back(std::move(ConstInfo));
662 }
663 
664 /// Finds and combines constant candidates that can be easily
665 /// rematerialized with an add from a common base constant.
666 void ConstantHoistingPass::findBaseConstants(GlobalVariable *BaseGV) {
667  // If BaseGV is nullptr, find base among candidate constant integers;
668  // Otherwise find base among constant GEPs that share the same BaseGV.
669  ConstCandVecType &ConstCandVec = BaseGV ?
670  ConstGEPCandMap[BaseGV] : ConstIntCandVec;
671  ConstInfoVecType &ConstInfoVec = BaseGV ?
672  ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
673 
674  // Sort the constants by value and type. This invalidates the mapping!
675  llvm::stable_sort(ConstCandVec, [](const ConstantCandidate &LHS,
676  const ConstantCandidate &RHS) {
677  if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
678  return LHS.ConstInt->getType()->getBitWidth() <
679  RHS.ConstInt->getType()->getBitWidth();
680  return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
681  });
682 
683  // Simple linear scan through the sorted constant candidate vector for viable
684  // merge candidates.
685  auto MinValItr = ConstCandVec.begin();
686  for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
687  CC != E; ++CC) {
688  if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
689  Type *MemUseValTy = nullptr;
690  for (auto &U : CC->Uses) {
691  auto *UI = U.Inst;
692  if (LoadInst *LI = dyn_cast<LoadInst>(UI)) {
693  MemUseValTy = LI->getType();
694  break;
695  } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
696  // Make sure the constant is used as pointer operand of the StoreInst.
697  if (SI->getPointerOperand() == SI->getOperand(U.OpndIdx)) {
698  MemUseValTy = SI->getValueOperand()->getType();
699  break;
700  }
701  }
702  }
703 
704  // Check if the constant is in range of an add with immediate.
705  APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
706  if ((Diff.getBitWidth() <= 64) &&
708  // Check if Diff can be used as offset in addressing mode of the user
709  // memory instruction.
710  (!MemUseValTy || TTI->isLegalAddressingMode(MemUseValTy,
711  /*BaseGV*/nullptr, /*BaseOffset*/Diff.getSExtValue(),
712  /*HasBaseReg*/true, /*Scale*/0)))
713  continue;
714  }
715  // We either have now a different constant type or the constant is not in
716  // range of an add with immediate anymore.
717  findAndMakeBaseConstant(MinValItr, CC, ConstInfoVec);
718  // Start a new base constant search.
719  MinValItr = CC;
720  }
721  // Finalize the last base constant search.
722  findAndMakeBaseConstant(MinValItr, ConstCandVec.end(), ConstInfoVec);
723 }
724 
725 /// Updates the operand at Idx in instruction Inst with the result of
726 /// instruction Mat. If the instruction is a PHI node then special
727 /// handling for duplicate values form the same incoming basic block is
728 /// required.
729 /// \return The update will always succeed, but the return value indicated if
730 /// Mat was used for the update or not.
731 static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
732  if (auto PHI = dyn_cast<PHINode>(Inst)) {
733  // Check if any previous operand of the PHI node has the same incoming basic
734  // block. This is a very odd case that happens when the incoming basic block
735  // has a switch statement. In this case use the same value as the previous
736  // operand(s), otherwise we will fail verification due to different values.
737  // The values are actually the same, but the variable names are different
738  // and the verifier doesn't like that.
739  BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx);
740  for (unsigned i = 0; i < Idx; ++i) {
741  if (PHI->getIncomingBlock(i) == IncomingBB) {
742  Value *IncomingVal = PHI->getIncomingValue(i);
743  Inst->setOperand(Idx, IncomingVal);
744  return false;
745  }
746  }
747  }
748 
749  Inst->setOperand(Idx, Mat);
750  return true;
751 }
752 
753 /// Emit materialization code for all rebased constants and update their
754 /// users.
755 void ConstantHoistingPass::emitBaseConstants(Instruction *Base,
756  Constant *Offset,
757  Type *Ty,
758  const ConstantUser &ConstUser) {
759  Instruction *Mat = Base;
760 
761  // The same offset can be dereferenced to different types in nested struct.
762  if (!Offset && Ty && Ty != Base->getType())
764 
765  if (Offset) {
766  Instruction *InsertionPt = findMatInsertPt(ConstUser.Inst,
767  ConstUser.OpndIdx);
768  if (Ty) {
769  // Constant being rebased is a ConstantExpr.
770  PointerType *Int8PtrTy = Type::getInt8PtrTy(*Ctx,
771  cast<PointerType>(Ty)->getAddressSpace());
772  Base = new BitCastInst(Base, Int8PtrTy, "base_bitcast", InsertionPt);
773  Mat = GetElementPtrInst::Create(Type::getInt8Ty(*Ctx), Base,
774  Offset, "mat_gep", InsertionPt);
775  Mat = new BitCastInst(Mat, Ty, "mat_bitcast", InsertionPt);
776  } else
777  // Constant being rebased is a ConstantInt.
778  Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
779  "const_mat", InsertionPt);
780 
781  LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
782  << " + " << *Offset << ") in BB "
783  << Mat->getParent()->getName() << '\n'
784  << *Mat << '\n');
785  Mat->setDebugLoc(ConstUser.Inst->getDebugLoc());
786  }
787  Value *Opnd = ConstUser.Inst->getOperand(ConstUser.OpndIdx);
788 
789  // Visit constant integer.
790  if (isa<ConstantInt>(Opnd)) {
791  LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
792  if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat) && Offset)
793  Mat->eraseFromParent();
794  LLVM_DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
795  return;
796  }
797 
798  // Visit cast instruction.
799  if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
800  assert(CastInst->isCast() && "Expected an cast instruction!");
801  // Check if we already have visited this cast instruction before to avoid
802  // unnecessary cloning.
803  Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
804  if (!ClonedCastInst) {
805  ClonedCastInst = CastInst->clone();
806  ClonedCastInst->setOperand(0, Mat);
807  ClonedCastInst->insertAfter(CastInst);
808  // Use the same debug location as the original cast instruction.
809  ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
810  LLVM_DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
811  << "To : " << *ClonedCastInst << '\n');
812  }
813 
814  LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
815  updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
816  LLVM_DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
817  return;
818  }
819 
820  // Visit constant expression.
821  if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
822  if (isa<GEPOperator>(ConstExpr)) {
823  // Operand is a ConstantGEP, replace it.
824  updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat);
825  return;
826  }
827 
828  // Aside from constant GEPs, only constant cast expressions are collected.
829  assert(ConstExpr->isCast() && "ConstExpr should be a cast");
830  Instruction *ConstExprInst = ConstExpr->getAsInstruction(
831  findMatInsertPt(ConstUser.Inst, ConstUser.OpndIdx));
832  ConstExprInst->setOperand(0, Mat);
833 
834  // Use the same debug location as the instruction we are about to update.
835  ConstExprInst->setDebugLoc(ConstUser.Inst->getDebugLoc());
836 
837  LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
838  << "From : " << *ConstExpr << '\n');
839  LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
840  if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ConstExprInst)) {
841  ConstExprInst->eraseFromParent();
842  if (Offset)
843  Mat->eraseFromParent();
844  }
845  LLVM_DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
846  return;
847  }
848 }
849 
850 /// Hoist and hide the base constant behind a bitcast and emit
851 /// materialization code for derived constants.
852 bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
853  bool MadeChange = false;
855  BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
856  for (auto const &ConstInfo : ConstInfoVec) {
857  SetVector<Instruction *> IPSet = findConstantInsertionPoint(ConstInfo);
858  // We can have an empty set if the function contains unreachable blocks.
859  if (IPSet.empty())
860  continue;
861 
862  unsigned UsesNum = 0;
863  unsigned ReBasesNum = 0;
864  unsigned NotRebasedNum = 0;
865  for (Instruction *IP : IPSet) {
866  // First, collect constants depending on this IP of the base.
867  unsigned Uses = 0;
868  using RebasedUse = std::tuple<Constant *, Type *, ConstantUser>;
869  SmallVector<RebasedUse, 4> ToBeRebased;
870  for (auto const &RCI : ConstInfo.RebasedConstants) {
871  for (auto const &U : RCI.Uses) {
872  Uses++;
873  BasicBlock *OrigMatInsertBB =
874  findMatInsertPt(U.Inst, U.OpndIdx)->getParent();
875  // If Base constant is to be inserted in multiple places,
876  // generate rebase for U using the Base dominating U.
877  if (IPSet.size() == 1 ||
878  DT->dominates(IP->getParent(), OrigMatInsertBB))
879  ToBeRebased.push_back(RebasedUse(RCI.Offset, RCI.Ty, U));
880  }
881  }
882  UsesNum = Uses;
883 
884  // If only few constants depend on this IP of base, skip rebasing,
885  // assuming the base and the rebased have the same materialization cost.
886  if (ToBeRebased.size() < MinNumOfDependentToRebase) {
887  NotRebasedNum += ToBeRebased.size();
888  continue;
889  }
890 
891  // Emit an instance of the base at this IP.
892  Instruction *Base = nullptr;
893  // Hoist and hide the base constant behind a bitcast.
894  if (ConstInfo.BaseExpr) {
895  assert(BaseGV && "A base constant expression must have an base GV");
896  Type *Ty = ConstInfo.BaseExpr->getType();
897  Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const", IP);
898  } else {
899  IntegerType *Ty = ConstInfo.BaseInt->getType();
900  Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const", IP);
901  }
902 
903  Base->setDebugLoc(IP->getDebugLoc());
904 
905  LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt
906  << ") to BB " << IP->getParent()->getName() << '\n'
907  << *Base << '\n');
908 
909  // Emit materialization code for rebased constants depending on this IP.
910  for (auto const &R : ToBeRebased) {
911  Constant *Off = std::get<0>(R);
912  Type *Ty = std::get<1>(R);
913  ConstantUser U = std::get<2>(R);
914  emitBaseConstants(Base, Off, Ty, U);
915  ReBasesNum++;
916  // Use the same debug location as the last user of the constant.
917  Base->setDebugLoc(DILocation::getMergedLocation(
918  Base->getDebugLoc(), U.Inst->getDebugLoc()));
919  }
920  assert(!Base->use_empty() && "The use list is empty!?");
921  assert(isa<Instruction>(Base->user_back()) &&
922  "All uses should be instructions.");
923  }
924  (void)UsesNum;
925  (void)ReBasesNum;
926  (void)NotRebasedNum;
927  // Expect all uses are rebased after rebase is done.
928  assert(UsesNum == (ReBasesNum + NotRebasedNum) &&
929  "Not all uses are rebased");
930 
931  NumConstantsHoisted++;
932 
933  // Base constant is also included in ConstInfo.RebasedConstants, so
934  // deduct 1 from ConstInfo.RebasedConstants.size().
935  NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1;
936 
937  MadeChange = true;
938  }
939  return MadeChange;
940 }
941 
942 /// Check all cast instructions we made a copy of and remove them if they
943 /// have no more users.
944 void ConstantHoistingPass::deleteDeadCastInst() const {
945  for (auto const &I : ClonedCastMap)
946  if (I.first->use_empty())
947  I.first->eraseFromParent();
948 }
949 
950 /// Optimize expensive integer constants in the given function.
953  BasicBlock &Entry, ProfileSummaryInfo *PSI) {
954  this->TTI = &TTI;
955  this->DT = &DT;
956  this->BFI = BFI;
957  this->DL = &Fn.getParent()->getDataLayout();
958  this->Ctx = &Fn.getContext();
959  this->Entry = &Entry;
960  this->PSI = PSI;
961  // Collect all constant candidates.
962  collectConstantCandidates(Fn);
963 
964  // Combine constants that can be easily materialized with an add from a common
965  // base constant.
966  if (!ConstIntCandVec.empty())
967  findBaseConstants(nullptr);
968  for (const auto &MapEntry : ConstGEPCandMap)
969  if (!MapEntry.second.empty())
970  findBaseConstants(MapEntry.first);
971 
972  // Finally hoist the base constant and emit materialization code for dependent
973  // constants.
974  bool MadeChange = false;
975  if (!ConstIntInfoVec.empty())
976  MadeChange = emitBaseConstants(nullptr);
977  for (const auto &MapEntry : ConstGEPInfoMap)
978  if (!MapEntry.second.empty())
979  MadeChange |= emitBaseConstants(MapEntry.first);
980 
981 
982  // Cleanup dead instructions.
983  deleteDeadCastInst();
984 
985  cleanup();
986 
987  return MadeChange;
988 }
989 
992  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
993  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
996  : nullptr;
997  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
998  auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
999  if (!runImpl(F, TTI, DT, BFI, F.getEntryBlock(), PSI))
1000  return PreservedAnalyses::all();
1001 
1002  PreservedAnalyses PA;
1003  PA.preserveSet<CFGAnalyses>();
1004  return PA;
1005 }
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:30
Hoisting
Constant Hoisting
Definition: ConstantHoisting.cpp:137
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1056
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2586
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Optional.h
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:291
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::ConstantInt::getType
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:173
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
llvm::consthoist::ConstantCandidate
Keeps track of a constant candidate and its uses.
Definition: ConstantHoisting.h:79
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
llvm::DILocation::getMergedLocation
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...
Definition: DebugInfoMetadata.cpp:107
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
DebugInfoMetadata.h
Scalar.h
llvm::Function
Definition: Function.h:60
llvm::Instruction::isCast
bool isCast() const
Definition: Instruction.h:172
llvm::consthoist::ConstantInfo::RebasedConstants
RebasedConstantListType RebasedConstants
Definition: ConstantHoisting.h:118
Pass.h
llvm::ConstantExpr::getAsInstruction
Instruction * getAsInstruction(Instruction *InsertBefore=nullptr) const
Returns an Instruction which implements the same operation as this ConstantExpr.
Definition: Constants.cpp:3396
llvm::BlockFrequencyInfoWrapperPass
Legacy analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:138
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5255
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::APInt::getSExtValue
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1498
SizeOpts.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:173
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:691
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::PointerType::getAddressSpace
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:682
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
cleanup
static void cleanup(BlockFrequencyInfoImplBase &BFI)
Clear all memory not needed downstream.
Definition: BlockFrequencyInfoImpl.cpp:303
APInt.h
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:321
BlockFrequency.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1431
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
Operator.h
llvm::TargetTransformInfo::getIntImmCodeSizeCost
InstructionCost getIntImmCodeSizeCost(unsigned Opc, unsigned Idx, const APInt &Imm, Type *Ty) const
Return the expected cost for the given integer when optimising for size.
Definition: TargetTransformInfo.cpp:595
llvm::TargetTransformInfo::getIntImmCostIntrin
InstructionCost getIntImmCostIntrin(Intrinsic::ID IID, unsigned Idx, const APInt &Imm, Type *Ty, TargetCostKind CostKind) const
Definition: TargetTransformInfo.cpp:622
consthoist
consthoist
Definition: ConstantHoisting.cpp:136
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::TargetTransformInfo::getIntImmCostInst
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...
Definition: TargetTransformInfo.cpp:612
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::Type::getInt8Ty
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:237
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:239
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:590
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::AVR::getAddressSpace
AddressSpace getAddressSpace(T *V)
Definition: AVR.h:64
Instruction.h
CommandLine.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::Instruction::insertAfter
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Definition: Instruction.cpp:93
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:164
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::shouldOptimizeForSize
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.
Definition: MachineSizeOpts.cpp:183
llvm::ConstantHoistingPass::runImpl
bool runImpl(Function &F, TargetTransformInfo &TTI, DominatorTree &DT, BlockFrequencyInfo *BFI, BasicBlock &Entry, ProfileSummaryInfo *PSI)
Optimize expensive integer constants in the given function.
Definition: ConstantHoisting.cpp:951
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::consthoist::ConstantUser::OpndIdx
unsigned OpndIdx
Definition: ConstantHoisting.h:71
Constants.h
llvm::createConstantHoistingPass
FunctionPass * createConstantHoistingPass()
Definition: ConstantHoisting.cpp:139
InlinePriorityMode::Cost
@ Cost
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
InstrTypes.h
llvm::ConstantHoistingPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: ConstantHoisting.cpp:990
llvm::canReplaceOperandWithVariable
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:3366
SI
@ SI
Definition: SIInstrInfo.cpp:7882
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::DomTreeNodeBase::children
iterator_range< iterator > children()
Definition: GenericDomTree.h:83
IP
Definition: NVPTXLowerArgs.cpp:168
llvm::APInt::getLimitedValue
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:456
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:246
false
Definition: StackSlotColoring.cpp:141
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction
Definition: Instruction.h:42
llvm::PGSOQueryType::IRPass
@ IRPass
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::ConstantInt::get
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:879
SmallPtrSet.h
ConstantHoisting.h
llvm::BlockFrequencyAnalysis
Analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:112
llvm::SetVector::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::consthoist::ConstantInfo::BaseExpr
ConstantExpr * BaseExpr
Definition: ConstantHoisting.h:117
llvm::consthoist::ConstantUser
Keeps track of the user of a constant and the operand index where the constant is used.
Definition: ConstantHoisting.h:69
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:40
llvm::ConstantExpr::isCast
bool isCast() const
Return true if this is a convert constant expression.
Definition: Constants.cpp:1436
llvm::consthoist::ConstantInfo::BaseInt
ConstantInt * BaseInt
Definition: ConstantHoisting.h:116
BasicBlock.h
llvm::cl::opt< bool >
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::BlockFrequency
Definition: BlockFrequency.h:23
updateOperand
static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat)
Updates the operand at Idx in instruction Inst with the result of instruction Mat.
Definition: ConstantHoisting.cpp:731
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:416
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:110
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
MinNumOfDependentToRebase
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)
uint64_t
ProfileSummaryInfo.h
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2642
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:650
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::ProfileSummaryInfoWrapperPass
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:194
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::TargetTransformInfo::isLegalAddImmediate
bool isLegalAddImmediate(int64_t Imm) const
Return true if the specified immediate is legal add immediate, that is the target has add instruction...
Definition: TargetTransformInfo.cpp:345
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:168
llvm::AMDGPU::IsaInfo::TargetIDSetting::Off
@ Off
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::GetElementPtrInst::Create
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:954
llvm::ProfileSummaryAnalysis
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:212
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:892
None.h
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::TargetTransformInfo::TCK_SizeAndLatency
@ TCK_SizeAndLatency
The weighted sum of size and latency.
Definition: TargetTransformInfo.h:222
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:113
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(ConstantHoistingLegacyPass, "consthoist", "Constant Hoisting", false, false) INITIALIZE_PASS_END(ConstantHoistingLegacyPass
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
CC
auto CC
Definition: RISCVRedundantCopyElimination.cpp:79
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:429
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:432
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::consthoist::ConstantInfo
A base constant and all its rebased constants.
Definition: ConstantHoisting.h:112
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
findBestInsertionSet
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...
Definition: ConstantHoisting.cpp:214
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1922
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:972
llvm::initializeConstantHoistingLegacyPassPass
void initializeConstantHoistingLegacyPassPass(PassRegistry &)
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Casting.h
Function.h
llvm::SetVector::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:664
runImpl
static bool runImpl(Function &F, const TargetLowering &TLI)
Definition: ExpandLargeDivRem.cpp:56
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::logicalview::LVAttributeKind::Inserted
@ Inserted
llvm::consthoist::ConstantUser::Inst
Instruction * Inst
Definition: ConstantHoisting.h:70
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
SmallVector.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:354
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
TargetTransformInfo.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::reserve
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Definition: DenseMap.h:103
llvm::consthoist::RebasedConstantInfo
This represents a constant that has been rebased with respect to a base constant.
Definition: ConstantHoisting.h:100
llvm::BasicBlock::getTerminator
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:119
llvm::Optional::value
constexpr const T & value() const &
Definition: Optional.h:281
llvm::SmallVectorImpl< consthoist::ConstantInfo >
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
ConstHoistGEP
static cl::opt< bool > ConstHoistGEP("consthoist-gep", cl::init(false), cl::Hidden, cl::desc("Try hoisting constant gep expressions"))
llvm::GlobalValue::getType
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:288
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:399
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::TargetTransformInfo::TCC_Basic
@ TCC_Basic
The cost of a typical 'add' instruction.
Definition: TargetTransformInfo.h:245
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:413
ConstHoistWithBlockFrequency
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."))
raw_ostream.h
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::BinaryOperator::Create
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.
Definition: Instructions.cpp:2936
Value.h
llvm::ConstantHoistingPass
Definition: ConstantHoisting.h:123
InitializePasses.h
llvm::BasicBlock::isEHPad
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:475
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
calculateOffsetDiff
static Optional< APInt > calculateOffsetDiff(const APInt &V1, const APInt &V2)
Definition: ConstantHoisting.cpp:536
llvm::TargetTransformInfo::isLegalAddressingMode
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...
Definition: TargetTransformInfo.cpp:353
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::SmallPtrSetImpl::insert
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