LLVM  13.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/Value.h"
56 #include "llvm/InitializePasses.h"
57 #include "llvm/Pass.h"
59 #include "llvm/Support/Casting.h"
61 #include "llvm/Support/Debug.h"
63 #include "llvm/Transforms/Scalar.h"
66 #include <algorithm>
67 #include <cassert>
68 #include <cstdint>
69 #include <iterator>
70 #include <tuple>
71 #include <utility>
72 
73 using namespace llvm;
74 using namespace consthoist;
75 
76 #define DEBUG_TYPE "consthoist"
77 
78 STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
79 STATISTIC(NumConstantsRebased, "Number of constants rebased");
80 
82  "consthoist-with-block-frequency", cl::init(true), cl::Hidden,
83  cl::desc("Enable the use of the block frequency analysis to reduce the "
84  "chance to execute const materialization more frequently than "
85  "without hoisting."));
86 
88  "consthoist-gep", cl::init(false), cl::Hidden,
89  cl::desc("Try hoisting constant gep expressions"));
90 
91 static cl::opt<unsigned>
92 MinNumOfDependentToRebase("consthoist-min-num-to-rebase",
93  cl::desc("Do not rebase if number of dependent constants of a Base is less "
94  "than this number."),
95  cl::init(0), cl::Hidden);
96 
97 namespace {
98 
99 /// The constant hoisting pass.
100 class ConstantHoistingLegacyPass : public FunctionPass {
101 public:
102  static char ID; // Pass identification, replacement for typeid
103 
104  ConstantHoistingLegacyPass() : FunctionPass(ID) {
106  }
107 
108  bool runOnFunction(Function &Fn) override;
109 
110  StringRef getPassName() const override { return "Constant Hoisting"; }
111 
112  void getAnalysisUsage(AnalysisUsage &AU) const override {
113  AU.setPreservesCFG();
119  }
120 
121 private:
123 };
124 
125 } // end anonymous namespace
126 
128 
129 INITIALIZE_PASS_BEGIN(ConstantHoistingLegacyPass, "consthoist",
130  "Constant Hoisting", false, false)
135 INITIALIZE_PASS_END(ConstantHoistingLegacyPass, "consthoist",
137 
139  return new ConstantHoistingLegacyPass();
140 }
141 
142 /// Perform the constant hoisting optimization for the given function.
144  if (skipFunction(Fn))
145  return false;
146 
147  LLVM_DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
148  LLVM_DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
149 
150  bool MadeChange =
151  Impl.runImpl(Fn, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn),
152  getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
154  ? &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI()
155  : nullptr,
156  Fn.getEntryBlock(),
157  &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
158 
159  if (MadeChange) {
160  LLVM_DEBUG(dbgs() << "********** Function after Constant Hoisting: "
161  << Fn.getName() << '\n');
162  LLVM_DEBUG(dbgs() << Fn);
163  }
164  LLVM_DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
165 
166  return MadeChange;
167 }
168 
169 /// Find the constant materialization insertion point.
170 Instruction *ConstantHoistingPass::findMatInsertPt(Instruction *Inst,
171  unsigned Idx) const {
172  // If the operand is a cast instruction, then we have to materialize the
173  // constant before the cast instruction.
174  if (Idx != ~0U) {
175  Value *Opnd = Inst->getOperand(Idx);
176  if (auto CastInst = dyn_cast<Instruction>(Opnd))
177  if (CastInst->isCast())
178  return CastInst;
179  }
180 
181  // The simple and common case. This also includes constant expressions.
182  if (!isa<PHINode>(Inst) && !Inst->isEHPad())
183  return Inst;
184 
185  // We can't insert directly before a phi node or an eh pad. Insert before
186  // the terminator of the incoming or dominating block.
187  assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!");
188  BasicBlock *InsertionBlock = nullptr;
189  if (Idx != ~0U && isa<PHINode>(Inst)) {
190  InsertionBlock = cast<PHINode>(Inst)->getIncomingBlock(Idx);
191  if (!InsertionBlock->isEHPad()) {
192  return InsertionBlock->getTerminator();
193  }
194  } else {
195  InsertionBlock = Inst->getParent();
196  }
197 
198  // This must be an EH pad. Iterate over immediate dominators until we find a
199  // non-EH pad. We need to skip over catchswitch blocks, which are both EH pads
200  // and terminators.
201  auto *IDom = DT->getNode(InsertionBlock)->getIDom();
202  while (IDom->getBlock()->isEHPad()) {
203  assert(Entry != IDom->getBlock() && "eh pad in entry block");
204  IDom = IDom->getIDom();
205  }
206 
207  return IDom->getBlock()->getTerminator();
208 }
209 
210 /// Given \p BBs as input, find another set of BBs which collectively
211 /// dominates \p BBs and have the minimal sum of frequencies. Return the BB
212 /// set found in \p BBs.
214  BasicBlock *Entry,
216  assert(!BBs.count(Entry) && "Assume Entry is not in BBs");
217  // Nodes on the current path to the root.
219  // Candidates includes any block 'BB' in set 'BBs' that is not strictly
220  // dominated by any other blocks in set 'BBs', and all nodes in the path
221  // in the dominator tree from Entry to 'BB'.
223  for (auto BB : BBs) {
224  // Ignore unreachable basic blocks.
225  if (!DT.isReachableFromEntry(BB))
226  continue;
227  Path.clear();
228  // Walk up the dominator tree until Entry or another BB in BBs
229  // is reached. Insert the nodes on the way to the Path.
230  BasicBlock *Node = BB;
231  // The "Path" is a candidate path to be added into Candidates set.
232  bool isCandidate = false;
233  do {
234  Path.insert(Node);
235  if (Node == Entry || Candidates.count(Node)) {
236  isCandidate = true;
237  break;
238  }
239  assert(DT.getNode(Node)->getIDom() &&
240  "Entry doens't dominate current Node");
241  Node = DT.getNode(Node)->getIDom()->getBlock();
242  } while (!BBs.count(Node));
243 
244  // If isCandidate is false, Node is another Block in BBs dominating
245  // current 'BB'. Drop the nodes on the Path.
246  if (!isCandidate)
247  continue;
248 
249  // Add nodes on the Path into Candidates.
250  Candidates.insert(Path.begin(), Path.end());
251  }
252 
253  // Sort the nodes in Candidates in top-down order and save the nodes
254  // in Orders.
255  unsigned Idx = 0;
257  Orders.push_back(Entry);
258  while (Idx != Orders.size()) {
259  BasicBlock *Node = Orders[Idx++];
260  for (auto ChildDomNode : DT.getNode(Node)->children()) {
261  if (Candidates.count(ChildDomNode->getBlock()))
262  Orders.push_back(ChildDomNode->getBlock());
263  }
264  }
265 
266  // Visit Orders in bottom-up order.
267  using InsertPtsCostPair =
268  std::pair<SetVector<BasicBlock *>, BlockFrequency>;
269 
270  // InsertPtsMap is a map from a BB to the best insertion points for the
271  // subtree of BB (subtree not including the BB itself).
273  InsertPtsMap.reserve(Orders.size() + 1);
274  for (auto RIt = Orders.rbegin(); RIt != Orders.rend(); RIt++) {
275  BasicBlock *Node = *RIt;
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) {
368  unsigned Cost;
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
376  Cost = TTI->getIntImmCostInst(
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);
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  if (!GEPO->accumulateConstantOffset(*DL, Offset))
419  return;
420 
421  if (!Offset.isIntN(32))
422  return;
423 
424  // A constant GEP expression that has a GlobalVariable as base pointer is
425  // usually lowered to a load from constant pool. Such operation is unlikely
426  // to be cheaper than compute it by <Base + Offset>, which can be lowered to
427  // an ADD instruction or folded into Load/Store instruction.
428  int Cost =
431  ConstCandVecType &ExprCandVec = ConstGEPCandMap[BaseGV];
432  ConstCandMapType::iterator Itr;
433  bool Inserted;
434  ConstPtrUnionType Cand = ConstExpr;
435  std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
436  if (Inserted) {
437  ExprCandVec.push_back(ConstantCandidate(
438  ConstantInt::get(Type::getInt32Ty(*Ctx), Offset.getLimitedValue()),
439  ConstExpr));
440  Itr->second = ExprCandVec.size() - 1;
441  }
442  ExprCandVec[Itr->second].addUser(Inst, Idx, Cost);
443 }
444 
445 /// Check the operand for instruction Inst at index Idx.
446 void ConstantHoistingPass::collectConstantCandidates(
447  ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx) {
448  Value *Opnd = Inst->getOperand(Idx);
449 
450  // Visit constant integers.
451  if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
452  collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
453  return;
454  }
455 
456  // Visit cast instructions that have constant integers.
457  if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
458  // Only visit cast instructions, which have been skipped. All other
459  // instructions should have already been visited.
460  if (!CastInst->isCast())
461  return;
462 
463  if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
464  // Pretend the constant is directly used by the instruction and ignore
465  // the cast instruction.
466  collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
467  return;
468  }
469  }
470 
471  // Visit constant expressions that have constant integers.
472  if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
473  // Handle constant gep expressions.
475  collectConstantCandidates(ConstCandMap, Inst, Idx, ConstExpr);
476 
477  // Only visit constant cast expressions.
478  if (!ConstExpr->isCast())
479  return;
480 
481  if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
482  // Pretend the constant is directly used by the instruction and ignore
483  // the constant expression.
484  collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
485  return;
486  }
487  }
488 }
489 
490 /// Scan the instruction for expensive integer constants and record them
491 /// in the constant candidate vector.
492 void ConstantHoistingPass::collectConstantCandidates(
493  ConstCandMapType &ConstCandMap, Instruction *Inst) {
494  // Skip all cast instructions. They are visited indirectly later on.
495  if (Inst->isCast())
496  return;
497 
498  // Scan all operands.
499  for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
500  // The cost of materializing the constants (defined in
501  // `TargetTransformInfo::getIntImmCostInst`) for instructions which only
502  // take constant variables is lower than `TargetTransformInfo::TCC_Basic`.
503  // So it's safe for us to collect constant candidates from all
504  // IntrinsicInsts.
505  if (canReplaceOperandWithVariable(Inst, Idx)) {
506  collectConstantCandidates(ConstCandMap, Inst, Idx);
507  }
508  } // end of for all operands
509 }
510 
511 /// Collect all integer constants in the function that cannot be folded
512 /// into an instruction itself.
513 void ConstantHoistingPass::collectConstantCandidates(Function &Fn) {
514  ConstCandMapType ConstCandMap;
515  for (BasicBlock &BB : Fn) {
516  // Ignore unreachable basic blocks.
517  if (!DT->isReachableFromEntry(&BB))
518  continue;
519  for (Instruction &Inst : BB)
520  collectConstantCandidates(ConstCandMap, &Inst);
521  }
522 }
523 
524 // This helper function is necessary to deal with values that have different
525 // bit widths (APInt Operator- does not like that). If the value cannot be
526 // represented in uint64 we return an "empty" APInt. This is then interpreted
527 // as the value is not in range.
528 static Optional<APInt> calculateOffsetDiff(const APInt &V1, const APInt &V2) {
529  Optional<APInt> Res = None;
530  unsigned BW = V1.getBitWidth() > V2.getBitWidth() ?
531  V1.getBitWidth() : V2.getBitWidth();
532  uint64_t LimVal1 = V1.getLimitedValue();
533  uint64_t LimVal2 = V2.getLimitedValue();
534 
535  if (LimVal1 == ~0ULL || LimVal2 == ~0ULL)
536  return Res;
537 
538  uint64_t Diff = LimVal1 - LimVal2;
539  return APInt(BW, Diff, true);
540 }
541 
542 // From a list of constants, one needs to picked as the base and the other
543 // constants will be transformed into an offset from that base constant. The
544 // question is which we can pick best? For example, consider these constants
545 // and their number of uses:
546 //
547 // Constants| 2 | 4 | 12 | 42 |
548 // NumUses | 3 | 2 | 8 | 7 |
549 //
550 // Selecting constant 12 because it has the most uses will generate negative
551 // offsets for constants 2 and 4 (i.e. -10 and -8 respectively). If negative
552 // offsets lead to less optimal code generation, then there might be better
553 // solutions. Suppose immediates in the range of 0..35 are most optimally
554 // supported by the architecture, then selecting constant 2 is most optimal
555 // because this will generate offsets: 0, 2, 10, 40. Offsets 0, 2 and 10 are in
556 // range 0..35, and thus 3 + 2 + 8 = 13 uses are in range. Selecting 12 would
557 // have only 8 uses in range, so choosing 2 as a base is more optimal. Thus, in
558 // selecting the base constant the range of the offsets is a very important
559 // factor too that we take into account here. This algorithm calculates a total
560 // costs for selecting a constant as the base and substract the costs if
561 // immediates are out of range. It has quadratic complexity, so we call this
562 // function only when we're optimising for size and there are less than 100
563 // constants, we fall back to the straightforward algorithm otherwise
564 // which does not do all the offset calculations.
565 unsigned
566 ConstantHoistingPass::maximizeConstantsInRange(ConstCandVecType::iterator S,
567  ConstCandVecType::iterator E,
568  ConstCandVecType::iterator &MaxCostItr) {
569  unsigned NumUses = 0;
570 
571  bool OptForSize = Entry->getParent()->hasOptSize() ||
572  llvm::shouldOptimizeForSize(Entry->getParent(), PSI, BFI,
574  if (!OptForSize || std::distance(S,E) > 100) {
575  for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
576  NumUses += ConstCand->Uses.size();
577  if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
578  MaxCostItr = ConstCand;
579  }
580  return NumUses;
581  }
582 
583  LLVM_DEBUG(dbgs() << "== Maximize constants in range ==\n");
584  int MaxCost = -1;
585  for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
586  auto Value = ConstCand->ConstInt->getValue();
587  Type *Ty = ConstCand->ConstInt->getType();
588  int Cost = 0;
589  NumUses += ConstCand->Uses.size();
590  LLVM_DEBUG(dbgs() << "= Constant: " << ConstCand->ConstInt->getValue()
591  << "\n");
592 
593  for (auto User : ConstCand->Uses) {
594  unsigned Opcode = User.Inst->getOpcode();
595  unsigned OpndIdx = User.OpndIdx;
596  Cost += TTI->getIntImmCostInst(Opcode, OpndIdx, Value, Ty,
598  LLVM_DEBUG(dbgs() << "Cost: " << Cost << "\n");
599 
600  for (auto C2 = S; C2 != E; ++C2) {
602  C2->ConstInt->getValue(),
603  ConstCand->ConstInt->getValue());
604  if (Diff) {
605  const int ImmCosts =
606  TTI->getIntImmCodeSizeCost(Opcode, OpndIdx, Diff.getValue(), Ty);
607  Cost -= ImmCosts;
608  LLVM_DEBUG(dbgs() << "Offset " << Diff.getValue() << " "
609  << "has penalty: " << ImmCosts << "\n"
610  << "Adjusted cost: " << Cost << "\n");
611  }
612  }
613  }
614  LLVM_DEBUG(dbgs() << "Cumulative cost: " << Cost << "\n");
615  if (Cost > MaxCost) {
616  MaxCost = Cost;
617  MaxCostItr = ConstCand;
618  LLVM_DEBUG(dbgs() << "New candidate: " << MaxCostItr->ConstInt->getValue()
619  << "\n");
620  }
621  }
622  return NumUses;
623 }
624 
625 /// Find the base constant within the given range and rebase all other
626 /// constants with respect to the base constant.
627 void ConstantHoistingPass::findAndMakeBaseConstant(
628  ConstCandVecType::iterator S, ConstCandVecType::iterator E,
630  auto MaxCostItr = S;
631  unsigned NumUses = maximizeConstantsInRange(S, E, MaxCostItr);
632 
633  // Don't hoist constants that have only one use.
634  if (NumUses <= 1)
635  return;
636 
637  ConstantInt *ConstInt = MaxCostItr->ConstInt;
638  ConstantExpr *ConstExpr = MaxCostItr->ConstExpr;
639  ConstantInfo ConstInfo;
640  ConstInfo.BaseInt = ConstInt;
641  ConstInfo.BaseExpr = ConstExpr;
642  Type *Ty = ConstInt->getType();
643 
644  // Rebase the constants with respect to the base constant.
645  for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
646  APInt Diff = ConstCand->ConstInt->getValue() - ConstInt->getValue();
647  Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
648  Type *ConstTy =
649  ConstCand->ConstExpr ? ConstCand->ConstExpr->getType() : nullptr;
650  ConstInfo.RebasedConstants.push_back(
651  RebasedConstantInfo(std::move(ConstCand->Uses), Offset, ConstTy));
652  }
653  ConstInfoVec.push_back(std::move(ConstInfo));
654 }
655 
656 /// Finds and combines constant candidates that can be easily
657 /// rematerialized with an add from a common base constant.
658 void ConstantHoistingPass::findBaseConstants(GlobalVariable *BaseGV) {
659  // If BaseGV is nullptr, find base among candidate constant integers;
660  // Otherwise find base among constant GEPs that share the same BaseGV.
661  ConstCandVecType &ConstCandVec = BaseGV ?
662  ConstGEPCandMap[BaseGV] : ConstIntCandVec;
663  ConstInfoVecType &ConstInfoVec = BaseGV ?
664  ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
665 
666  // Sort the constants by value and type. This invalidates the mapping!
667  llvm::stable_sort(ConstCandVec, [](const ConstantCandidate &LHS,
668  const ConstantCandidate &RHS) {
669  if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
670  return LHS.ConstInt->getType()->getBitWidth() <
671  RHS.ConstInt->getType()->getBitWidth();
672  return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
673  });
674 
675  // Simple linear scan through the sorted constant candidate vector for viable
676  // merge candidates.
677  auto MinValItr = ConstCandVec.begin();
678  for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
679  CC != E; ++CC) {
680  if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
681  Type *MemUseValTy = nullptr;
682  for (auto &U : CC->Uses) {
683  auto *UI = U.Inst;
684  if (LoadInst *LI = dyn_cast<LoadInst>(UI)) {
685  MemUseValTy = LI->getType();
686  break;
687  } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
688  // Make sure the constant is used as pointer operand of the StoreInst.
689  if (SI->getPointerOperand() == SI->getOperand(U.OpndIdx)) {
690  MemUseValTy = SI->getValueOperand()->getType();
691  break;
692  }
693  }
694  }
695 
696  // Check if the constant is in range of an add with immediate.
697  APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
698  if ((Diff.getBitWidth() <= 64) &&
700  // Check if Diff can be used as offset in addressing mode of the user
701  // memory instruction.
702  (!MemUseValTy || TTI->isLegalAddressingMode(MemUseValTy,
703  /*BaseGV*/nullptr, /*BaseOffset*/Diff.getSExtValue(),
704  /*HasBaseReg*/true, /*Scale*/0)))
705  continue;
706  }
707  // We either have now a different constant type or the constant is not in
708  // range of an add with immediate anymore.
709  findAndMakeBaseConstant(MinValItr, CC, ConstInfoVec);
710  // Start a new base constant search.
711  MinValItr = CC;
712  }
713  // Finalize the last base constant search.
714  findAndMakeBaseConstant(MinValItr, ConstCandVec.end(), ConstInfoVec);
715 }
716 
717 /// Updates the operand at Idx in instruction Inst with the result of
718 /// instruction Mat. If the instruction is a PHI node then special
719 /// handling for duplicate values form the same incoming basic block is
720 /// required.
721 /// \return The update will always succeed, but the return value indicated if
722 /// Mat was used for the update or not.
723 static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
724  if (auto PHI = dyn_cast<PHINode>(Inst)) {
725  // Check if any previous operand of the PHI node has the same incoming basic
726  // block. This is a very odd case that happens when the incoming basic block
727  // has a switch statement. In this case use the same value as the previous
728  // operand(s), otherwise we will fail verification due to different values.
729  // The values are actually the same, but the variable names are different
730  // and the verifier doesn't like that.
731  BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx);
732  for (unsigned i = 0; i < Idx; ++i) {
733  if (PHI->getIncomingBlock(i) == IncomingBB) {
734  Value *IncomingVal = PHI->getIncomingValue(i);
735  Inst->setOperand(Idx, IncomingVal);
736  return false;
737  }
738  }
739  }
740 
741  Inst->setOperand(Idx, Mat);
742  return true;
743 }
744 
745 /// Emit materialization code for all rebased constants and update their
746 /// users.
747 void ConstantHoistingPass::emitBaseConstants(Instruction *Base,
748  Constant *Offset,
749  Type *Ty,
750  const ConstantUser &ConstUser) {
751  Instruction *Mat = Base;
752 
753  // The same offset can be dereferenced to different types in nested struct.
754  if (!Offset && Ty && Ty != Base->getType())
756 
757  if (Offset) {
758  Instruction *InsertionPt = findMatInsertPt(ConstUser.Inst,
759  ConstUser.OpndIdx);
760  if (Ty) {
761  // Constant being rebased is a ConstantExpr.
762  PointerType *Int8PtrTy = Type::getInt8PtrTy(*Ctx,
763  cast<PointerType>(Ty)->getAddressSpace());
764  Base = new BitCastInst(Base, Int8PtrTy, "base_bitcast", InsertionPt);
765  Mat = GetElementPtrInst::Create(Int8PtrTy->getElementType(), Base,
766  Offset, "mat_gep", InsertionPt);
767  Mat = new BitCastInst(Mat, Ty, "mat_bitcast", InsertionPt);
768  } else
769  // Constant being rebased is a ConstantInt.
771  "const_mat", InsertionPt);
772 
773  LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
774  << " + " << *Offset << ") in BB "
775  << Mat->getParent()->getName() << '\n'
776  << *Mat << '\n');
777  Mat->setDebugLoc(ConstUser.Inst->getDebugLoc());
778  }
779  Value *Opnd = ConstUser.Inst->getOperand(ConstUser.OpndIdx);
780 
781  // Visit constant integer.
782  if (isa<ConstantInt>(Opnd)) {
783  LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
784  if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat) && Offset)
785  Mat->eraseFromParent();
786  LLVM_DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
787  return;
788  }
789 
790  // Visit cast instruction.
791  if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
792  assert(CastInst->isCast() && "Expected an cast instruction!");
793  // Check if we already have visited this cast instruction before to avoid
794  // unnecessary cloning.
795  Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
796  if (!ClonedCastInst) {
797  ClonedCastInst = CastInst->clone();
798  ClonedCastInst->setOperand(0, Mat);
799  ClonedCastInst->insertAfter(CastInst);
800  // Use the same debug location as the original cast instruction.
801  ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
802  LLVM_DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
803  << "To : " << *ClonedCastInst << '\n');
804  }
805 
806  LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
807  updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
808  LLVM_DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
809  return;
810  }
811 
812  // Visit constant expression.
813  if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
814  if (ConstExpr->isGEPWithNoNotionalOverIndexing()) {
815  // Operand is a ConstantGEP, replace it.
816  updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat);
817  return;
818  }
819 
820  // Aside from constant GEPs, only constant cast expressions are collected.
821  assert(ConstExpr->isCast() && "ConstExpr should be a cast");
822  Instruction *ConstExprInst = ConstExpr->getAsInstruction();
823  ConstExprInst->setOperand(0, Mat);
824  ConstExprInst->insertBefore(findMatInsertPt(ConstUser.Inst,
825  ConstUser.OpndIdx));
826 
827  // Use the same debug location as the instruction we are about to update.
828  ConstExprInst->setDebugLoc(ConstUser.Inst->getDebugLoc());
829 
830  LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
831  << "From : " << *ConstExpr << '\n');
832  LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
833  if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ConstExprInst)) {
834  ConstExprInst->eraseFromParent();
835  if (Offset)
836  Mat->eraseFromParent();
837  }
838  LLVM_DEBUG(dbgs() << "To : " << *ConstUser.Inst << '\n');
839  return;
840  }
841 }
842 
843 /// Hoist and hide the base constant behind a bitcast and emit
844 /// materialization code for derived constants.
845 bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
846  bool MadeChange = false;
848  BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
849  for (auto const &ConstInfo : ConstInfoVec) {
850  SetVector<Instruction *> IPSet = findConstantInsertionPoint(ConstInfo);
851  // We can have an empty set if the function contains unreachable blocks.
852  if (IPSet.empty())
853  continue;
854 
855  unsigned UsesNum = 0;
856  unsigned ReBasesNum = 0;
857  unsigned NotRebasedNum = 0;
858  for (Instruction *IP : IPSet) {
859  // First, collect constants depending on this IP of the base.
860  unsigned Uses = 0;
861  using RebasedUse = std::tuple<Constant *, Type *, ConstantUser>;
862  SmallVector<RebasedUse, 4> ToBeRebased;
863  for (auto const &RCI : ConstInfo.RebasedConstants) {
864  for (auto const &U : RCI.Uses) {
865  Uses++;
866  BasicBlock *OrigMatInsertBB =
867  findMatInsertPt(U.Inst, U.OpndIdx)->getParent();
868  // If Base constant is to be inserted in multiple places,
869  // generate rebase for U using the Base dominating U.
870  if (IPSet.size() == 1 ||
871  DT->dominates(IP->getParent(), OrigMatInsertBB))
872  ToBeRebased.push_back(RebasedUse(RCI.Offset, RCI.Ty, U));
873  }
874  }
875  UsesNum = Uses;
876 
877  // If only few constants depend on this IP of base, skip rebasing,
878  // assuming the base and the rebased have the same materialization cost.
879  if (ToBeRebased.size() < MinNumOfDependentToRebase) {
880  NotRebasedNum += ToBeRebased.size();
881  continue;
882  }
883 
884  // Emit an instance of the base at this IP.
885  Instruction *Base = nullptr;
886  // Hoist and hide the base constant behind a bitcast.
887  if (ConstInfo.BaseExpr) {
888  assert(BaseGV && "A base constant expression must have an base GV");
889  Type *Ty = ConstInfo.BaseExpr->getType();
890  Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const", IP);
891  } else {
892  IntegerType *Ty = ConstInfo.BaseInt->getType();
893  Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const", IP);
894  }
895 
896  Base->setDebugLoc(IP->getDebugLoc());
897 
898  LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt
899  << ") to BB " << IP->getParent()->getName() << '\n'
900  << *Base << '\n');
901 
902  // Emit materialization code for rebased constants depending on this IP.
903  for (auto const &R : ToBeRebased) {
904  Constant *Off = std::get<0>(R);
905  Type *Ty = std::get<1>(R);
906  ConstantUser U = std::get<2>(R);
907  emitBaseConstants(Base, Off, Ty, U);
908  ReBasesNum++;
909  // Use the same debug location as the last user of the constant.
911  Base->getDebugLoc(), U.Inst->getDebugLoc()));
912  }
913  assert(!Base->use_empty() && "The use list is empty!?");
914  assert(isa<Instruction>(Base->user_back()) &&
915  "All uses should be instructions.");
916  }
917  (void)UsesNum;
918  (void)ReBasesNum;
919  (void)NotRebasedNum;
920  // Expect all uses are rebased after rebase is done.
921  assert(UsesNum == (ReBasesNum + NotRebasedNum) &&
922  "Not all uses are rebased");
923 
924  NumConstantsHoisted++;
925 
926  // Base constant is also included in ConstInfo.RebasedConstants, so
927  // deduct 1 from ConstInfo.RebasedConstants.size().
928  NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1;
929 
930  MadeChange = true;
931  }
932  return MadeChange;
933 }
934 
935 /// Check all cast instructions we made a copy of and remove them if they
936 /// have no more users.
937 void ConstantHoistingPass::deleteDeadCastInst() const {
938  for (auto const &I : ClonedCastMap)
939  if (I.first->use_empty())
940  I.first->eraseFromParent();
941 }
942 
943 /// Optimize expensive integer constants in the given function.
946  BasicBlock &Entry, ProfileSummaryInfo *PSI) {
947  this->TTI = &TTI;
948  this->DT = &DT;
949  this->BFI = BFI;
950  this->DL = &Fn.getParent()->getDataLayout();
951  this->Ctx = &Fn.getContext();
952  this->Entry = &Entry;
953  this->PSI = PSI;
954  // Collect all constant candidates.
955  collectConstantCandidates(Fn);
956 
957  // Combine constants that can be easily materialized with an add from a common
958  // base constant.
959  if (!ConstIntCandVec.empty())
960  findBaseConstants(nullptr);
961  for (const auto &MapEntry : ConstGEPCandMap)
962  if (!MapEntry.second.empty())
963  findBaseConstants(MapEntry.first);
964 
965  // Finally hoist the base constant and emit materialization code for dependent
966  // constants.
967  bool MadeChange = false;
968  if (!ConstIntInfoVec.empty())
969  MadeChange = emitBaseConstants(nullptr);
970  for (const auto &MapEntry : ConstGEPInfoMap)
971  if (!MapEntry.second.empty())
972  MadeChange |= emitBaseConstants(MapEntry.first);
973 
974 
975  // Cleanup dead instructions.
976  deleteDeadCastInst();
977 
978  cleanup();
979 
980  return MadeChange;
981 }
982 
985  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
986  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
989  : nullptr;
990  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
991  auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
992  if (!runImpl(F, TTI, DT, BFI, F.getEntryBlock(), PSI))
993  return PreservedAnalyses::all();
994 
996  PA.preserveSet<CFGAnalyses>();
997  return PA;
998 }
i
i
Definition: README.txt:29
Hoisting
Constant Hoisting
Definition: ConstantHoisting.cpp:136
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1070
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2265
llvm
Definition: AllocatorList.h:23
Optional.h
llvm::Type::getInt8PtrTy
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:256
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::ConstantInt::getType
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
Definition: Constants.h:171
llvm::consthoist::ConstantCandidate
Keeps track of a constant candidate and its uses.
Definition: ConstantHoisting.h:80
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
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:93
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:785
DebugInfoMetadata.h
Scalar.h
llvm::PointerType::getElementType
Type * getElementType() const
Definition: DerivedTypes.h:653
llvm::Function
Definition: Function.h:61
llvm::Instruction::isCast
bool isCast() const
Definition: Instruction.h:168
llvm::consthoist::ConstantInfo::RebasedConstants
RebasedConstantListType RebasedConstants
Definition: ConstantHoisting.h:119
Pass.h
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:5136
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:131
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::APInt::getSExtValue
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1644
SizeOpts.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:752
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::PointerType::getAddressSpace
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:662
Local.h
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:84
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
cleanup
static void cleanup(BlockFrequencyInfoImplBase &BFI)
Clear all memory not needed downstream.
Definition: BlockFrequencyInfoImpl.cpp:288
APInt.h
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:316
BlockFrequency.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
DenseMap.h
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1582
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:34
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
consthoist
consthoist
Definition: ConstantHoisting.cpp:135
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:204
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::TargetTransformInfo::getIntImmCodeSizeCost
int 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:540
F
#define F(x, y, z)
Definition: MD5.cpp:56
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:583
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Instruction.h
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::Instruction::insertAfter
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Definition: Instruction.cpp:90
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
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:944
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::consthoist::ConstantUser::OpndIdx
unsigned OpndIdx
Definition: ConstantHoisting.h:72
Constants.h
llvm::createConstantHoistingPass
FunctionPass * createConstantHoistingPass()
Definition: ConstantHoisting.cpp:138
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:983
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:3289
SI
@ SI
Definition: SIInstrInfo.cpp:7342
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
runImpl
static bool runImpl(const TargetLibraryInfo &TLI, Function &F)
Definition: ReplaceWithVeclib.cpp:177
llvm::DomTreeNodeBase::children
iterator_range< iterator > children()
Definition: GenericDomTree.h:83
IP
Definition: NVPTXLowerArgs.cpp:166
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:488
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:235
false
Definition: StackSlotColoring.cpp:142
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction
Definition: Instruction.h:45
llvm::PGSOQueryType::IRPass
@ IRPass
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::TargetTransformInfo::getIntImmCostInst
int 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:555
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:885
llvm::ConstantExpr::getAsInstruction
Instruction * getAsInstruction() const
Returns an Instruction which implements the same operation as this ConstantExpr.
Definition: Constants.cpp:3469
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::None
const NoneType None
Definition: None.h:23
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:357
llvm::consthoist::ConstantInfo::BaseExpr
ConstantExpr * BaseExpr
Definition: ConstantHoisting.h:118
llvm::consthoist::ConstantUser
Keeps track of the user of a constant and the operand index where the constant is used.
Definition: ConstantHoisting.h:70
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::ConstantExpr::isCast
bool isCast() const
Return true if this is a convert constant expression.
Definition: Constants.cpp:1442
llvm::consthoist::ConstantInfo::BaseInt
ConstantInt * BaseInt
Definition: ConstantHoisting.h:117
BasicBlock.h
llvm::cl::opt< bool >
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:303
llvm::BlockFrequency
Definition: BlockFrequency.h:24
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:723
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:78
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:111
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)
ProfileSummaryInfo.h
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2321
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:407
llvm::Instruction::user_back
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:91
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:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
llvm::ProfileSummaryInfoWrapperPass
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:188
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:402
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:634
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:362
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:328
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:329
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:163
llvm::TargetTransformInfo::getIntImmCostIntrin
int getIntImmCostIntrin(Intrinsic::ID IID, unsigned Idx, const APInt &Imm, Type *Ty, TargetCostKind CostKind) const
Definition: TargetTransformInfo.cpp:565
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:382
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:71
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:931
llvm::ProfileSummaryAnalysis
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:206
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:821
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
None.h
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::TargetTransformInfo::TCK_SizeAndLatency
@ TCK_SizeAndLatency
The weighted sum of size and latency.
Definition: TargetTransformInfo.h:215
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
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
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:432
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:419
llvm::APInt::ult
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1206
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:298
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::consthoist::ConstantInfo
A base constant and all its rebased constants.
Definition: ConstantHoisting.h:113
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
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.cpp:148
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
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:213
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1640
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:931
llvm::initializeConstantHoistingLegacyPassPass
void initializeConstantHoistingLegacyPassPass(PassRegistry &)
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::consthoist::ConstantCandidate::ConstInt
ConstantInt * ConstInt
Definition: ConstantHoisting.h:85
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:644
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:184
llvm::consthoist::ConstantUser::Inst
Instruction * Inst
Definition: ConstantHoisting.h:71
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
Instructions.h
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:191
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:365
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::IntegerType::getBitWidth
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:71
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:104
llvm::consthoist::RebasedConstantInfo
This represents a constant that has been rebased with respect to a base constant.
Definition: ConstantHoisting.h:101
llvm::SmallVectorImpl< consthoist::ConstantInfo >
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:271
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:397
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
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:263
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:411
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:2549
Value.h
llvm::ConstantHoistingPass
Definition: ConstantHoisting.h:124
InitializePasses.h
llvm::BasicBlock::isEHPad
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:465
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
calculateOffsetDiff
static Optional< APInt > calculateOffsetDiff(const APInt &V1, const APInt &V2)
Definition: ConstantHoisting.cpp:528
llvm::Optional::getValue
constexpr const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:280
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:337
llvm::ConstantExpr::isGEPWithNoNotionalOverIndexing
bool isGEPWithNoNotionalOverIndexing() const
Return true if this is a getelementptr expression and all the index operands are compile-time known i...
Definition: Constants.cpp:1450
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38