llvm.org GIT mirror llvm / 7716d65 lib / Transforms / Scalar / ConstantHoisting.cpp
7716d65

Tree @7716d65 (Download .tar.gz)

ConstantHoisting.cpp @7716d65raw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
//===- ConstantHoisting.cpp - Prepare code for expensive constants --------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This pass identifies expensive constants to hoist and coalesces them to
// better prepare it for SelectionDAG-based code generation. This works around
// the limitations of the basic-block-at-a-time approach.
//
// First it scans all instructions for integer constants and calculates its
// cost. If the constant can be folded into the instruction (the cost is
// TCC_Free) or the cost is just a simple operation (TCC_BASIC), then we don't
// consider it expensive and leave it alone. This is the default behavior and
// the default implementation of getIntImmCost will always return TCC_Free.
//
// If the cost is more than TCC_BASIC, then the integer constant can't be folded
// into the instruction and it might be beneficial to hoist the constant.
// Similar constants are coalesced to reduce register pressure and
// materialization code.
//
// When a constant is hoisted, it is also hidden behind a bitcast to force it to
// be live-out of the basic block. Otherwise the constant would be just
// duplicated and each basic block would have its own copy in the SelectionDAG.
// The SelectionDAG recognizes such constants as opaque and doesn't perform
// certain transformations on them, which would create a new expensive constant.
//
// This optimization is only applied to integer constants in instructions and
// simple (this means not nested) constant cast expressions. For example:
// %0 = load i64* inttoptr (i64 big_constant to i64*)
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/ConstantHoisting.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/SizeOpts.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <tuple>
#include <utility>

using namespace llvm;
using namespace consthoist;

#define DEBUG_TYPE "consthoist"

STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
STATISTIC(NumConstantsRebased, "Number of constants rebased");

static cl::opt<bool> ConstHoistWithBlockFrequency(
    "consthoist-with-block-frequency", cl::init(true), cl::Hidden,
    cl::desc("Enable the use of the block frequency analysis to reduce the "
             "chance to execute const materialization more frequently than "
             "without hoisting."));

static cl::opt<bool> ConstHoistGEP(
    "consthoist-gep", cl::init(false), cl::Hidden,
    cl::desc("Try hoisting constant gep expressions"));

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);

namespace {

/// The constant hoisting pass.
class ConstantHoistingLegacyPass : public FunctionPass {
public:
  static char ID; // Pass identification, replacement for typeid

  ConstantHoistingLegacyPass() : FunctionPass(ID) {
    initializeConstantHoistingLegacyPassPass(*PassRegistry::getPassRegistry());
  }

  bool runOnFunction(Function &Fn) override;

  StringRef getPassName() const override { return "Constant Hoisting"; }

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.setPreservesCFG();
    if (ConstHoistWithBlockFrequency)
      AU.addRequired<BlockFrequencyInfoWrapperPass>();
    AU.addRequired<DominatorTreeWrapperPass>();
    AU.addRequired<ProfileSummaryInfoWrapperPass>();
    AU.addRequired<TargetTransformInfoWrapperPass>();
  }

private:
  ConstantHoistingPass Impl;
};

} // end anonymous namespace

char ConstantHoistingLegacyPass::ID = 0;

INITIALIZE_PASS_BEGIN(ConstantHoistingLegacyPass, "consthoist",
                      "Constant Hoisting", false, false)
INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_END(ConstantHoistingLegacyPass, "consthoist",
                    "Constant Hoisting", false, false)

FunctionPass *llvm::createConstantHoistingPass() {
  return new ConstantHoistingLegacyPass();
}

/// Perform the constant hoisting optimization for the given function.
bool ConstantHoistingLegacyPass::runOnFunction(Function &Fn) {
  if (skipFunction(Fn))
    return false;

  LLVM_DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
  LLVM_DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');

  bool MadeChange =
      Impl.runImpl(Fn, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn),
                   getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
                   ConstHoistWithBlockFrequency
                       ? &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI()
                       : nullptr,
                   Fn.getEntryBlock(),
                   &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());

  if (MadeChange) {
    LLVM_DEBUG(dbgs() << "********** Function after Constant Hoisting: "
                      << Fn.getName() << '\n');
    LLVM_DEBUG(dbgs() << Fn);
  }
  LLVM_DEBUG(dbgs() << "********** End Constant Hoisting **********\n");

  return MadeChange;
}

/// Find the constant materialization insertion point.
Instruction *ConstantHoistingPass::findMatInsertPt(Instruction *Inst,
                                                   unsigned Idx) const {
  // If the operand is a cast instruction, then we have to materialize the
  // constant before the cast instruction.
  if (Idx != ~0U) {
    Value *Opnd = Inst->getOperand(Idx);
    if (auto CastInst = dyn_cast<Instruction>(Opnd))
      if (CastInst->isCast())
        return CastInst;
  }

  // The simple and common case. This also includes constant expressions.
  if (!isa<PHINode>(Inst) && !Inst->isEHPad())
    return Inst;

  // We can't insert directly before a phi node or an eh pad. Insert before
  // the terminator of the incoming or dominating block.
  assert(Entry != Inst->getParent() && "PHI or landing pad in entry block!");
  if (Idx != ~0U && isa<PHINode>(Inst))
    return cast<PHINode>(Inst)->getIncomingBlock(Idx)->getTerminator();

  // This must be an EH pad. Iterate over immediate dominators until we find a
  // non-EH pad. We need to skip over catchswitch blocks, which are both EH pads
  // and terminators.
  auto IDom = DT->getNode(Inst->getParent())->getIDom();
  while (IDom->getBlock()->isEHPad()) {
    assert(Entry != IDom->getBlock() && "eh pad in entry block");
    IDom = IDom->getIDom();
  }

  return IDom->getBlock()->getTerminator();
}

/// Given \p BBs as input, find another set of BBs which collectively
/// dominates \p BBs and have the minimal sum of frequencies. Return the BB
/// set found in \p BBs.
static void findBestInsertionSet(DominatorTree &DT, BlockFrequencyInfo &BFI,
                                 BasicBlock *Entry,
                                 SmallPtrSet<BasicBlock *, 8> &BBs) {
  assert(!BBs.count(Entry) && "Assume Entry is not in BBs");
  // Nodes on the current path to the root.
  SmallPtrSet<BasicBlock *, 8> Path;
  // Candidates includes any block 'BB' in set 'BBs' that is not strictly
  // dominated by any other blocks in set 'BBs', and all nodes in the path
  // in the dominator tree from Entry to 'BB'.
  SmallPtrSet<BasicBlock *, 16> Candidates;
  for (auto BB : BBs) {
    // Ignore unreachable basic blocks.
    if (!DT.isReachableFromEntry(BB))
      continue;
    Path.clear();
    // Walk up the dominator tree until Entry or another BB in BBs
    // is reached. Insert the nodes on the way to the Path.
    BasicBlock *Node = BB;
    // The "Path" is a candidate path to be added into Candidates set.
    bool isCandidate = false;
    do {
      Path.insert(Node);
      if (Node == Entry || Candidates.count(Node)) {
        isCandidate = true;
        break;
      }
      assert(DT.getNode(Node)->getIDom() &&
             "Entry doens't dominate current Node");
      Node = DT.getNode(Node)->getIDom()->getBlock();
    } while (!BBs.count(Node));

    // If isCandidate is false, Node is another Block in BBs dominating
    // current 'BB'. Drop the nodes on the Path.
    if (!isCandidate)
      continue;

    // Add nodes on the Path into Candidates.
    Candidates.insert(Path.begin(), Path.end());
  }

  // Sort the nodes in Candidates in top-down order and save the nodes
  // in Orders.
  unsigned Idx = 0;
  SmallVector<BasicBlock *, 16> Orders;
  Orders.push_back(Entry);
  while (Idx != Orders.size()) {
    BasicBlock *Node = Orders[Idx++];
    for (auto ChildDomNode : DT.getNode(Node)->getChildren()) {
      if (Candidates.count(ChildDomNode->getBlock()))
        Orders.push_back(ChildDomNode->getBlock());
    }
  }

  // Visit Orders in bottom-up order.
  using InsertPtsCostPair =
      std::pair<SmallPtrSet<BasicBlock *, 16>, BlockFrequency>;

  // InsertPtsMap is a map from a BB to the best insertion points for the
  // subtree of BB (subtree not including the BB itself).
  DenseMap<BasicBlock *, InsertPtsCostPair> InsertPtsMap;
  InsertPtsMap.reserve(Orders.size() + 1);
  for (auto RIt = Orders.rbegin(); RIt != Orders.rend(); RIt++) {
    BasicBlock *Node = *RIt;
    bool NodeInBBs = BBs.count(Node);
    SmallPtrSet<BasicBlock *, 16> &InsertPts = InsertPtsMap[Node].first;
    BlockFrequency &InsertPtsFreq = InsertPtsMap[Node].second;

    // Return the optimal insert points in BBs.
    if (Node == Entry) {
      BBs.clear();
      if (InsertPtsFreq > BFI.getBlockFreq(Node) ||
          (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1))
        BBs.insert(Entry);
      else
        BBs.insert(InsertPts.begin(), InsertPts.end());
      break;
    }

    BasicBlock *Parent = DT.getNode(Node)->getIDom()->getBlock();
    // Initially, ParentInsertPts is empty and ParentPtsFreq is 0. Every child
    // will update its parent's ParentInsertPts and ParentPtsFreq.
    SmallPtrSet<BasicBlock *, 16> &ParentInsertPts = InsertPtsMap[Parent].first;
    BlockFrequency &ParentPtsFreq = InsertPtsMap[Parent].second;
    // Choose to insert in Node or in subtree of Node.
    // Don't hoist to EHPad because we may not find a proper place to insert
    // in EHPad.
    // If the total frequency of InsertPts is the same as the frequency of the
    // target Node, and InsertPts contains more than one nodes, choose hoisting
    // to reduce code size.
    if (NodeInBBs ||
        (!Node->isEHPad() &&
         (InsertPtsFreq > BFI.getBlockFreq(Node) ||
          (InsertPtsFreq == BFI.getBlockFreq(Node) && InsertPts.size() > 1)))) {
      ParentInsertPts.insert(Node);
      ParentPtsFreq += BFI.getBlockFreq(Node);
    } else {
      ParentInsertPts.insert(InsertPts.begin(), InsertPts.end());
      ParentPtsFreq += InsertPtsFreq;
    }
  }
}

/// Find an insertion point that dominates all uses.
SmallPtrSet<Instruction *, 8> ConstantHoistingPass::findConstantInsertionPoint(
    const ConstantInfo &ConstInfo) const {
  assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
  // Collect all basic blocks.
  SmallPtrSet<BasicBlock *, 8> BBs;
  SmallPtrSet<Instruction *, 8> InsertPts;
  for (auto const &RCI : ConstInfo.RebasedConstants)
    for (auto const &U : RCI.Uses)
      BBs.insert(findMatInsertPt(U.Inst, U.OpndIdx)->getParent());

  if (BBs.count(Entry)) {
    InsertPts.insert(&Entry->front());
    return InsertPts;
  }

  if (BFI) {
    findBestInsertionSet(*DT, *BFI, Entry, BBs);
    for (auto BB : BBs) {
      BasicBlock::iterator InsertPt = BB->begin();
      for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
        ;
      InsertPts.insert(&*InsertPt);
    }
    return InsertPts;
  }

  while (BBs.size() >= 2) {
    BasicBlock *BB, *BB1, *BB2;
    BB1 = *BBs.begin();
    BB2 = *std::next(BBs.begin());
    BB = DT->findNearestCommonDominator(BB1, BB2);
    if (BB == Entry) {
      InsertPts.insert(&Entry->front());
      return InsertPts;
    }
    BBs.erase(BB1);
    BBs.erase(BB2);
    BBs.insert(BB);
  }
  assert((BBs.size() == 1) && "Expected only one element.");
  Instruction &FirstInst = (*BBs.begin())->front();
  InsertPts.insert(findMatInsertPt(&FirstInst));
  return InsertPts;
}

/// Record constant integer ConstInt for instruction Inst at operand
/// index Idx.
///
/// The operand at index Idx is not necessarily the constant integer itself. It
/// could also be a cast instruction or a constant expression that uses the
/// constant integer.
void ConstantHoistingPass::collectConstantCandidates(
    ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
    ConstantInt *ConstInt) {
  unsigned Cost;
  // Ask the target about the cost of materializing the constant for the given
  // instruction and operand index.
  if (auto IntrInst = dyn_cast<IntrinsicInst>(Inst))
    Cost = TTI->getIntImmCost(IntrInst->getIntrinsicID(), Idx,
                              ConstInt->getValue(), ConstInt->getType());
  else
    Cost = TTI->getIntImmCost(Inst->getOpcode(), Idx, ConstInt->getValue(),
                              ConstInt->getType());

  // Ignore cheap integer constants.
  if (Cost > TargetTransformInfo::TCC_Basic) {
    ConstCandMapType::iterator Itr;
    bool Inserted;
    ConstPtrUnionType Cand = ConstInt;
    std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
    if (Inserted) {
      ConstIntCandVec.push_back(ConstantCandidate(ConstInt));
      Itr->second = ConstIntCandVec.size() - 1;
    }
    ConstIntCandVec[Itr->second].addUser(Inst, Idx, Cost);
    LLVM_DEBUG(if (isa<ConstantInt>(Inst->getOperand(Idx))) dbgs()
                   << "Collect constant " << *ConstInt << " from " << *Inst
                   << " with cost " << Cost << '\n';
               else dbgs() << "Collect constant " << *ConstInt
                           << " indirectly from " << *Inst << " via "
                           << *Inst->getOperand(Idx) << " with cost " << Cost
                           << '\n';);
  }
}

/// Record constant GEP expression for instruction Inst at operand index Idx.
void ConstantHoistingPass::collectConstantCandidates(
    ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
    ConstantExpr *ConstExpr) {
  // TODO: Handle vector GEPs
  if (ConstExpr->getType()->isVectorTy())
    return;

  GlobalVariable *BaseGV = dyn_cast<GlobalVariable>(ConstExpr->getOperand(0));
  if (!BaseGV)
    return;

  // Get offset from the base GV.
  PointerType *GVPtrTy = dyn_cast<PointerType>(BaseGV->getType());
  IntegerType *PtrIntTy = DL->getIntPtrType(*Ctx, GVPtrTy->getAddressSpace());
  APInt Offset(DL->getTypeSizeInBits(PtrIntTy), /*val*/0, /*isSigned*/true);
  auto *GEPO = cast<GEPOperator>(ConstExpr);
  if (!GEPO->accumulateConstantOffset(*DL, Offset))
    return;

  if (!Offset.isIntN(32))
    return;

  // A constant GEP expression that has a GlobalVariable as base pointer is
  // usually lowered to a load from constant pool. Such operation is unlikely
  // to be cheaper than compute it by <Base + Offset>, which can be lowered to
  // an ADD instruction or folded into Load/Store instruction.
  int Cost = TTI->getIntImmCost(Instruction::Add, 1, Offset, PtrIntTy);
  ConstCandVecType &ExprCandVec = ConstGEPCandMap[BaseGV];
  ConstCandMapType::iterator Itr;
  bool Inserted;
  ConstPtrUnionType Cand = ConstExpr;
  std::tie(Itr, Inserted) = ConstCandMap.insert(std::make_pair(Cand, 0));
  if (Inserted) {
    ExprCandVec.push_back(ConstantCandidate(
        ConstantInt::get(Type::getInt32Ty(*Ctx), Offset.getLimitedValue()),
        ConstExpr));
    Itr->second = ExprCandVec.size() - 1;
  }
  ExprCandVec[Itr->second].addUser(Inst, Idx, Cost);
}

/// Check the operand for instruction Inst at index Idx.
void ConstantHoistingPass::collectConstantCandidates(
    ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx) {
  Value *Opnd = Inst->getOperand(Idx);

  // Visit constant integers.
  if (auto ConstInt = dyn_cast<ConstantInt>(Opnd)) {
    collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
    return;
  }

  // Visit cast instructions that have constant integers.
  if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
    // Only visit cast instructions, which have been skipped. All other
    // instructions should have already been visited.
    if (!CastInst->isCast())
      return;

    if (auto *ConstInt = dyn_cast<ConstantInt>(CastInst->getOperand(0))) {
      // Pretend the constant is directly used by the instruction and ignore
      // the cast instruction.
      collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
      return;
    }
  }

  // Visit constant expressions that have constant integers.
  if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
    // Handle constant gep expressions.
    if (ConstHoistGEP && ConstExpr->isGEPWithNoNotionalOverIndexing())
      collectConstantCandidates(ConstCandMap, Inst, Idx, ConstExpr);

    // Only visit constant cast expressions.
    if (!ConstExpr->isCast())
      return;

    if (auto ConstInt = dyn_cast<ConstantInt>(ConstExpr->getOperand(0))) {
      // Pretend the constant is directly used by the instruction and ignore
      // the constant expression.
      collectConstantCandidates(ConstCandMap, Inst, Idx, ConstInt);
      return;
    }
  }
}

/// Scan the instruction for expensive integer constants and record them
/// in the constant candidate vector.
void ConstantHoistingPass::collectConstantCandidates(
    ConstCandMapType &ConstCandMap, Instruction *Inst) {
  // Skip all cast instructions. They are visited indirectly later on.
  if (Inst->isCast())
    return;

  // Scan all operands.
  for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
    // The cost of materializing the constants (defined in
    // `TargetTransformInfo::getIntImmCost`) for instructions which only take
    // constant variables is lower than `TargetTransformInfo::TCC_Basic`. So
    // it's safe for us to collect constant candidates from all IntrinsicInsts.
    if (canReplaceOperandWithVariable(Inst, Idx) || isa<IntrinsicInst>(Inst)) {
      collectConstantCandidates(ConstCandMap, Inst, Idx);
    }
  } // end of for all operands
}

/// Collect all integer constants in the function that cannot be folded
/// into an instruction itself.
void ConstantHoistingPass::collectConstantCandidates(Function &Fn) {
  ConstCandMapType ConstCandMap;
  for (BasicBlock &BB : Fn)
    for (Instruction &Inst : BB)
      collectConstantCandidates(ConstCandMap, &Inst);
}

// This helper function is necessary to deal with values that have different
// bit widths (APInt Operator- does not like that). If the value cannot be
// represented in uint64 we return an "empty" APInt. This is then interpreted
// as the value is not in range.
static Optional<APInt> calculateOffsetDiff(const APInt &V1, const APInt &V2) {
  Optional<APInt> Res = None;
  unsigned BW = V1.getBitWidth() > V2.getBitWidth() ?
                V1.getBitWidth() : V2.getBitWidth();
  uint64_t LimVal1 = V1.getLimitedValue();
  uint64_t LimVal2 = V2.getLimitedValue();

  if (LimVal1 == ~0ULL || LimVal2 == ~0ULL)
    return Res;

  uint64_t Diff = LimVal1 - LimVal2;
  return APInt(BW, Diff, true);
}

// From a list of constants, one needs to picked as the base and the other
// constants will be transformed into an offset from that base constant. The
// question is which we can pick best? For example, consider these constants
// and their number of uses:
//
//  Constants| 2 | 4 | 12 | 42 |
//  NumUses  | 3 | 2 |  8 |  7 |
//
// Selecting constant 12 because it has the most uses will generate negative
// offsets for constants 2 and 4 (i.e. -10 and -8 respectively). If negative
// offsets lead to less optimal code generation, then there might be better
// solutions. Suppose immediates in the range of 0..35 are most optimally
// supported by the architecture, then selecting constant 2 is most optimal
// because this will generate offsets: 0, 2, 10, 40. Offsets 0, 2 and 10 are in
// range 0..35, and thus 3 + 2 + 8 = 13 uses are in range. Selecting 12 would
// have only 8 uses in range, so choosing 2 as a base is more optimal. Thus, in
// selecting the base constant the range of the offsets is a very important
// factor too that we take into account here. This algorithm calculates a total
// costs for selecting a constant as the base and substract the costs if
// immediates are out of range. It has quadratic complexity, so we call this
// function only when we're optimising for size and there are less than 100
// constants, we fall back to the straightforward algorithm otherwise
// which does not do all the offset calculations.
unsigned
ConstantHoistingPass::maximizeConstantsInRange(ConstCandVecType::iterator S,
                                           ConstCandVecType::iterator E,
                                           ConstCandVecType::iterator &MaxCostItr) {
  unsigned NumUses = 0;

  bool OptForSize = Entry->getParent()->hasOptSize() ||
                    llvm::shouldOptimizeForSize(Entry->getParent(), PSI, BFI);
  if (!OptForSize || std::distance(S,E) > 100) {
    for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
      NumUses += ConstCand->Uses.size();
      if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
        MaxCostItr = ConstCand;
    }
    return NumUses;
  }

  LLVM_DEBUG(dbgs() << "== Maximize constants in range ==\n");
  int MaxCost = -1;
  for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
    auto Value = ConstCand->ConstInt->getValue();
    Type *Ty = ConstCand->ConstInt->getType();
    int Cost = 0;
    NumUses += ConstCand->Uses.size();
    LLVM_DEBUG(dbgs() << "= Constant: " << ConstCand->ConstInt->getValue()
                      << "\n");

    for (auto User : ConstCand->Uses) {
      unsigned Opcode = User.Inst->getOpcode();
      unsigned OpndIdx = User.OpndIdx;
      Cost += TTI->getIntImmCost(Opcode, OpndIdx, Value, Ty);
      LLVM_DEBUG(dbgs() << "Cost: " << Cost << "\n");

      for (auto C2 = S; C2 != E; ++C2) {
        Optional<APInt> Diff = calculateOffsetDiff(
                                   C2->ConstInt->getValue(),
                                   ConstCand->ConstInt->getValue());
        if (Diff) {
          const int ImmCosts =
            TTI->getIntImmCodeSizeCost(Opcode, OpndIdx, Diff.getValue(), Ty);
          Cost -= ImmCosts;
          LLVM_DEBUG(dbgs() << "Offset " << Diff.getValue() << " "
                            << "has penalty: " << ImmCosts << "\n"
                            << "Adjusted cost: " << Cost << "\n");
        }
      }
    }
    LLVM_DEBUG(dbgs() << "Cumulative cost: " << Cost << "\n");
    if (Cost > MaxCost) {
      MaxCost = Cost;
      MaxCostItr = ConstCand;
      LLVM_DEBUG(dbgs() << "New candidate: " << MaxCostItr->ConstInt->getValue()
                        << "\n");
    }
  }
  return NumUses;
}

/// Find the base constant within the given range and rebase all other
/// constants with respect to the base constant.
void ConstantHoistingPass::findAndMakeBaseConstant(
    ConstCandVecType::iterator S, ConstCandVecType::iterator E,
    SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec) {
  auto MaxCostItr = S;
  unsigned NumUses = maximizeConstantsInRange(S, E, MaxCostItr);

  // Don't hoist constants that have only one use.
  if (NumUses <= 1)
    return;

  ConstantInt *ConstInt = MaxCostItr->ConstInt;
  ConstantExpr *ConstExpr = MaxCostItr->ConstExpr;
  ConstantInfo ConstInfo;
  ConstInfo.BaseInt = ConstInt;
  ConstInfo.BaseExpr = ConstExpr;
  Type *Ty = ConstInt->getType();

  // Rebase the constants with respect to the base constant.
  for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
    APInt Diff = ConstCand->ConstInt->getValue() - ConstInt->getValue();
    Constant *Offset = Diff == 0 ? nullptr : ConstantInt::get(Ty, Diff);
    Type *ConstTy =
        ConstCand->ConstExpr ? ConstCand->ConstExpr->getType() : nullptr;
    ConstInfo.RebasedConstants.push_back(
      RebasedConstantInfo(std::move(ConstCand->Uses), Offset, ConstTy));
  }
  ConstInfoVec.push_back(std::move(ConstInfo));
}

/// Finds and combines constant candidates that can be easily
/// rematerialized with an add from a common base constant.
void ConstantHoistingPass::findBaseConstants(GlobalVariable *BaseGV) {
  // If BaseGV is nullptr, find base among candidate constant integers;
  // Otherwise find base among constant GEPs that share the same BaseGV.
  ConstCandVecType &ConstCandVec = BaseGV ?
      ConstGEPCandMap[BaseGV] : ConstIntCandVec;
  ConstInfoVecType &ConstInfoVec = BaseGV ?
      ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;

  // Sort the constants by value and type. This invalidates the mapping!
  std::stable_sort(ConstCandVec.begin(), ConstCandVec.end(),
             [](const ConstantCandidate &LHS, const ConstantCandidate &RHS) {
    if (LHS.ConstInt->getType() != RHS.ConstInt->getType())
      return LHS.ConstInt->getType()->getBitWidth() <
             RHS.ConstInt->getType()->getBitWidth();
    return LHS.ConstInt->getValue().ult(RHS.ConstInt->getValue());
  });

  // Simple linear scan through the sorted constant candidate vector for viable
  // merge candidates.
  auto MinValItr = ConstCandVec.begin();
  for (auto CC = std::next(ConstCandVec.begin()), E = ConstCandVec.end();
       CC != E; ++CC) {
    if (MinValItr->ConstInt->getType() == CC->ConstInt->getType()) {
      Type *MemUseValTy = nullptr;
      for (auto &U : CC->Uses) {
        auto *UI = U.Inst;
        if (LoadInst *LI = dyn_cast<LoadInst>(UI)) {
          MemUseValTy = LI->getType();
          break;
        } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
          // Make sure the constant is used as pointer operand of the StoreInst.
          if (SI->getPointerOperand() == SI->getOperand(U.OpndIdx)) {
            MemUseValTy = SI->getValueOperand()->getType();
            break;
          }
        }
      }

      // Check if the constant is in range of an add with immediate.
      APInt Diff = CC->ConstInt->getValue() - MinValItr->ConstInt->getValue();
      if ((Diff.getBitWidth() <= 64) &&
          TTI->isLegalAddImmediate(Diff.getSExtValue()) &&
          // Check if Diff can be used as offset in addressing mode of the user
          // memory instruction.
          (!MemUseValTy || TTI->isLegalAddressingMode(MemUseValTy,
           /*BaseGV*/nullptr, /*BaseOffset*/Diff.getSExtValue(),
           /*HasBaseReg*/true, /*Scale*/0)))
        continue;
    }
    // We either have now a different constant type or the constant is not in
    // range of an add with immediate anymore.
    findAndMakeBaseConstant(MinValItr, CC, ConstInfoVec);
    // Start a new base constant search.
    MinValItr = CC;
  }
  // Finalize the last base constant search.
  findAndMakeBaseConstant(MinValItr, ConstCandVec.end(), ConstInfoVec);
}

/// Updates the operand at Idx in instruction Inst with the result of
///        instruction Mat. If the instruction is a PHI node then special
///        handling for duplicate values form the same incoming basic block is
///        required.
/// \return The update will always succeed, but the return value indicated if
///         Mat was used for the update or not.
static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
  if (auto PHI = dyn_cast<PHINode>(Inst)) {
    // Check if any previous operand of the PHI node has the same incoming basic
    // block. This is a very odd case that happens when the incoming basic block
    // has a switch statement. In this case use the same value as the previous
    // operand(s), otherwise we will fail verification due to different values.
    // The values are actually the same, but the variable names are different
    // and the verifier doesn't like that.
    BasicBlock *IncomingBB = PHI->getIncomingBlock(Idx);
    for (unsigned i = 0; i < Idx; ++i) {
      if (PHI->getIncomingBlock(i) == IncomingBB) {
        Value *IncomingVal = PHI->getIncomingValue(i);
        Inst->setOperand(Idx, IncomingVal);
        return false;
      }
    }
  }

  Inst->setOperand(Idx, Mat);
  return true;
}

/// Emit materialization code for all rebased constants and update their
/// users.
void ConstantHoistingPass::emitBaseConstants(Instruction *Base,
                                             Constant *Offset,
                                             Type *Ty,
                                             const ConstantUser &ConstUser) {
  Instruction *Mat = Base;

  // The same offset can be dereferenced to different types in nested struct.
  if (!Offset && Ty && Ty != Base->getType())
    Offset = ConstantInt::get(Type::getInt32Ty(*Ctx), 0);

  if (Offset) {
    Instruction *InsertionPt = findMatInsertPt(ConstUser.Inst,
                                               ConstUser.OpndIdx);
    if (Ty) {
      // Constant being rebased is a ConstantExpr.
      PointerType *Int8PtrTy = Type::getInt8PtrTy(*Ctx,
          cast<PointerType>(Ty)->getAddressSpace());
      Base = new BitCastInst(Base, Int8PtrTy, "base_bitcast", InsertionPt);
      Mat = GetElementPtrInst::Create(Int8PtrTy->getElementType(), Base,
          Offset, "mat_gep", InsertionPt);
      Mat = new BitCastInst(Mat, Ty, "mat_bitcast", InsertionPt);
    } else
      // Constant being rebased is a ConstantInt.
      Mat = BinaryOperator::Create(Instruction::Add, Base, Offset,
                                 "const_mat", InsertionPt);

    LLVM_DEBUG(dbgs() << "Materialize constant (" << *Base->getOperand(0)
                      << " + " << *Offset << ") in BB "
                      << Mat->getParent()->getName() << '\n'
                      << *Mat << '\n');
    Mat->setDebugLoc(ConstUser.Inst->getDebugLoc());
  }
  Value *Opnd = ConstUser.Inst->getOperand(ConstUser.OpndIdx);

  // Visit constant integer.
  if (isa<ConstantInt>(Opnd)) {
    LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
    if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat) && Offset)
      Mat->eraseFromParent();
    LLVM_DEBUG(dbgs() << "To    : " << *ConstUser.Inst << '\n');
    return;
  }

  // Visit cast instruction.
  if (auto CastInst = dyn_cast<Instruction>(Opnd)) {
    assert(CastInst->isCast() && "Expected an cast instruction!");
    // Check if we already have visited this cast instruction before to avoid
    // unnecessary cloning.
    Instruction *&ClonedCastInst = ClonedCastMap[CastInst];
    if (!ClonedCastInst) {
      ClonedCastInst = CastInst->clone();
      ClonedCastInst->setOperand(0, Mat);
      ClonedCastInst->insertAfter(CastInst);
      // Use the same debug location as the original cast instruction.
      ClonedCastInst->setDebugLoc(CastInst->getDebugLoc());
      LLVM_DEBUG(dbgs() << "Clone instruction: " << *CastInst << '\n'
                        << "To               : " << *ClonedCastInst << '\n');
    }

    LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
    updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ClonedCastInst);
    LLVM_DEBUG(dbgs() << "To    : " << *ConstUser.Inst << '\n');
    return;
  }

  // Visit constant expression.
  if (auto ConstExpr = dyn_cast<ConstantExpr>(Opnd)) {
    if (ConstExpr->isGEPWithNoNotionalOverIndexing()) {
      // Operand is a ConstantGEP, replace it.
      updateOperand(ConstUser.Inst, ConstUser.OpndIdx, Mat);
      return;
    }

    // Aside from constant GEPs, only constant cast expressions are collected.
    assert(ConstExpr->isCast() && "ConstExpr should be a cast");
    Instruction *ConstExprInst = ConstExpr->getAsInstruction();
    ConstExprInst->setOperand(0, Mat);
    ConstExprInst->insertBefore(findMatInsertPt(ConstUser.Inst,
                                                ConstUser.OpndIdx));

    // Use the same debug location as the instruction we are about to update.
    ConstExprInst->setDebugLoc(ConstUser.Inst->getDebugLoc());

    LLVM_DEBUG(dbgs() << "Create instruction: " << *ConstExprInst << '\n'
                      << "From              : " << *ConstExpr << '\n');
    LLVM_DEBUG(dbgs() << "Update: " << *ConstUser.Inst << '\n');
    if (!updateOperand(ConstUser.Inst, ConstUser.OpndIdx, ConstExprInst)) {
      ConstExprInst->eraseFromParent();
      if (Offset)
        Mat->eraseFromParent();
    }
    LLVM_DEBUG(dbgs() << "To    : " << *ConstUser.Inst << '\n');
    return;
  }
}

/// Hoist and hide the base constant behind a bitcast and emit
/// materialization code for derived constants.
bool ConstantHoistingPass::emitBaseConstants(GlobalVariable *BaseGV) {
  bool MadeChange = false;
  SmallVectorImpl<consthoist::ConstantInfo> &ConstInfoVec =
      BaseGV ? ConstGEPInfoMap[BaseGV] : ConstIntInfoVec;
  for (auto const &ConstInfo : ConstInfoVec) {
    SmallPtrSet<Instruction *, 8> IPSet = findConstantInsertionPoint(ConstInfo);
    // We can have an empty set if the function contains unreachable blocks.
    if (IPSet.empty())
      continue;

    unsigned UsesNum = 0;
    unsigned ReBasesNum = 0;
    unsigned NotRebasedNum = 0;
    for (Instruction *IP : IPSet) {
      // First, collect constants depending on this IP of the base.
      unsigned Uses = 0;
      using RebasedUse = std::tuple<Constant *, Type *, ConstantUser>;
      SmallVector<RebasedUse, 4> ToBeRebased;
      for (auto const &RCI : ConstInfo.RebasedConstants) {
        for (auto const &U : RCI.Uses) {
          Uses++;
          BasicBlock *OrigMatInsertBB =
              findMatInsertPt(U.Inst, U.OpndIdx)->getParent();
          // If Base constant is to be inserted in multiple places,
          // generate rebase for U using the Base dominating U.
          if (IPSet.size() == 1 ||
              DT->dominates(IP->getParent(), OrigMatInsertBB))
            ToBeRebased.push_back(RebasedUse(RCI.Offset, RCI.Ty, U));
        }
      }
      UsesNum = Uses;

      // If only few constants depend on this IP of base, skip rebasing,
      // assuming the base and the rebased have the same materialization cost.
      if (ToBeRebased.size() < MinNumOfDependentToRebase) {
        NotRebasedNum += ToBeRebased.size();
        continue;
      }

      // Emit an instance of the base at this IP.
      Instruction *Base = nullptr;
      // Hoist and hide the base constant behind a bitcast.
      if (ConstInfo.BaseExpr) {
        assert(BaseGV && "A base constant expression must have an base GV");
        Type *Ty = ConstInfo.BaseExpr->getType();
        Base = new BitCastInst(ConstInfo.BaseExpr, Ty, "const", IP);
      } else {
        IntegerType *Ty = ConstInfo.BaseInt->getType();
        Base = new BitCastInst(ConstInfo.BaseInt, Ty, "const", IP);
      }

      Base->setDebugLoc(IP->getDebugLoc());

      LLVM_DEBUG(dbgs() << "Hoist constant (" << *ConstInfo.BaseInt
                        << ") to BB " << IP->getParent()->getName() << '\n'
                        << *Base << '\n');

      // Emit materialization code for rebased constants depending on this IP.
      for (auto const &R : ToBeRebased) {
        Constant *Off = std::get<0>(R);
        Type *Ty = std::get<1>(R);
        ConstantUser U = std::get<2>(R);
        emitBaseConstants(Base, Off, Ty, U);
        ReBasesNum++;
        // Use the same debug location as the last user of the constant.
        Base->setDebugLoc(DILocation::getMergedLocation(
            Base->getDebugLoc(), U.Inst->getDebugLoc()));
      }
      assert(!Base->use_empty() && "The use list is empty!?");
      assert(isa<Instruction>(Base->user_back()) &&
             "All uses should be instructions.");
    }
    (void)UsesNum;
    (void)ReBasesNum;
    (void)NotRebasedNum;
    // Expect all uses are rebased after rebase is done.
    assert(UsesNum == (ReBasesNum + NotRebasedNum) &&
           "Not all uses are rebased");

    NumConstantsHoisted++;

    // Base constant is also included in ConstInfo.RebasedConstants, so
    // deduct 1 from ConstInfo.RebasedConstants.size().
    NumConstantsRebased += ConstInfo.RebasedConstants.size() - 1;

    MadeChange = true;
  }
  return MadeChange;
}

/// Check all cast instructions we made a copy of and remove them if they
/// have no more users.
void ConstantHoistingPass::deleteDeadCastInst() const {
  for (auto const &I : ClonedCastMap)
    if (I.first->use_empty())
      I.first->eraseFromParent();
}

/// Optimize expensive integer constants in the given function.
bool ConstantHoistingPass::runImpl(Function &Fn, TargetTransformInfo &TTI,
                                   DominatorTree &DT, BlockFrequencyInfo *BFI,
                                   BasicBlock &Entry, ProfileSummaryInfo *PSI) {
  this->TTI = &TTI;
  this->DT = &DT;
  this->BFI = BFI;
  this->DL = &Fn.getParent()->getDataLayout();
  this->Ctx = &Fn.getContext();
  this->Entry = &Entry;
  this->PSI = PSI;
  // Collect all constant candidates.
  collectConstantCandidates(Fn);

  // Combine constants that can be easily materialized with an add from a common
  // base constant.
  if (!ConstIntCandVec.empty())
    findBaseConstants(nullptr);
  for (auto &MapEntry : ConstGEPCandMap)
    if (!MapEntry.second.empty())
      findBaseConstants(MapEntry.first);

  // Finally hoist the base constant and emit materialization code for dependent
  // constants.
  bool MadeChange = false;
  if (!ConstIntInfoVec.empty())
    MadeChange = emitBaseConstants(nullptr);
  for (auto MapEntry : ConstGEPInfoMap)
    if (!MapEntry.second.empty())
      MadeChange |= emitBaseConstants(MapEntry.first);


  // Cleanup dead instructions.
  deleteDeadCastInst();

  cleanup();

  return MadeChange;
}

PreservedAnalyses ConstantHoistingPass::run(Function &F,
                                            FunctionAnalysisManager &AM) {
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
  auto BFI = ConstHoistWithBlockFrequency
                 ? &AM.getResult<BlockFrequencyAnalysis>(F)
                 : nullptr;
  auto &MAM = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
  auto *PSI = MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
  if (!runImpl(F, TTI, DT, BFI, F.getEntryBlock(), PSI))
    return PreservedAnalyses::all();

  PreservedAnalyses PA;
  PA.preserveSet<CFGAnalyses>();
  return PA;
}