LLVM  mainline
CodeGenPrepare.cpp
Go to the documentation of this file.
00001 //===- CodeGenPrepare.cpp - Prepare a function for code generation --------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass munges the code in the input function to better prepare it for
00011 // SelectionDAG-based code generation. This works around limitations in it's
00012 // basic-block-at-a-time approach. It should eventually be removed.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/CodeGen/Passes.h"
00017 #include "llvm/ADT/DenseMap.h"
00018 #include "llvm/ADT/SmallSet.h"
00019 #include "llvm/ADT/Statistic.h"
00020 #include "llvm/Analysis/InstructionSimplify.h"
00021 #include "llvm/Analysis/TargetLibraryInfo.h"
00022 #include "llvm/Analysis/TargetTransformInfo.h"
00023 #include "llvm/IR/CallSite.h"
00024 #include "llvm/IR/Constants.h"
00025 #include "llvm/IR/DataLayout.h"
00026 #include "llvm/IR/DerivedTypes.h"
00027 #include "llvm/IR/Dominators.h"
00028 #include "llvm/IR/Function.h"
00029 #include "llvm/IR/GetElementPtrTypeIterator.h"
00030 #include "llvm/IR/IRBuilder.h"
00031 #include "llvm/IR/InlineAsm.h"
00032 #include "llvm/IR/Instructions.h"
00033 #include "llvm/IR/IntrinsicInst.h"
00034 #include "llvm/IR/MDBuilder.h"
00035 #include "llvm/IR/PatternMatch.h"
00036 #include "llvm/IR/Statepoint.h"
00037 #include "llvm/IR/ValueHandle.h"
00038 #include "llvm/IR/ValueMap.h"
00039 #include "llvm/Pass.h"
00040 #include "llvm/Support/CommandLine.h"
00041 #include "llvm/Support/Debug.h"
00042 #include "llvm/Support/raw_ostream.h"
00043 #include "llvm/Target/TargetLowering.h"
00044 #include "llvm/Target/TargetSubtargetInfo.h"
00045 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00046 #include "llvm/Transforms/Utils/BuildLibCalls.h"
00047 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
00048 #include "llvm/Transforms/Utils/Local.h"
00049 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
00050 using namespace llvm;
00051 using namespace llvm::PatternMatch;
00052 
00053 #define DEBUG_TYPE "codegenprepare"
00054 
00055 STATISTIC(NumBlocksElim, "Number of blocks eliminated");
00056 STATISTIC(NumPHIsElim,   "Number of trivial PHIs eliminated");
00057 STATISTIC(NumGEPsElim,   "Number of GEPs converted to casts");
00058 STATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of "
00059                       "sunken Cmps");
00060 STATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses "
00061                        "of sunken Casts");
00062 STATISTIC(NumMemoryInsts, "Number of memory instructions whose address "
00063                           "computations were sunk");
00064 STATISTIC(NumExtsMoved,  "Number of [s|z]ext instructions combined with loads");
00065 STATISTIC(NumExtUses,    "Number of uses of [s|z]ext instructions optimized");
00066 STATISTIC(NumRetsDup,    "Number of return instructions duplicated");
00067 STATISTIC(NumDbgValueMoved, "Number of debug value instructions moved");
00068 STATISTIC(NumSelectsExpanded, "Number of selects turned into branches");
00069 STATISTIC(NumAndCmpsMoved, "Number of and/cmp's pushed into branches");
00070 STATISTIC(NumStoreExtractExposed, "Number of store(extractelement) exposed");
00071 
00072 static cl::opt<bool> DisableBranchOpts(
00073   "disable-cgp-branch-opts", cl::Hidden, cl::init(false),
00074   cl::desc("Disable branch optimizations in CodeGenPrepare"));
00075 
00076 static cl::opt<bool>
00077     DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false),
00078                   cl::desc("Disable GC optimizations in CodeGenPrepare"));
00079 
00080 static cl::opt<bool> DisableSelectToBranch(
00081   "disable-cgp-select2branch", cl::Hidden, cl::init(false),
00082   cl::desc("Disable select to branch conversion."));
00083 
00084 static cl::opt<bool> AddrSinkUsingGEPs(
00085   "addr-sink-using-gep", cl::Hidden, cl::init(false),
00086   cl::desc("Address sinking in CGP using GEPs."));
00087 
00088 static cl::opt<bool> EnableAndCmpSinking(
00089    "enable-andcmp-sinking", cl::Hidden, cl::init(true),
00090    cl::desc("Enable sinkinig and/cmp into branches."));
00091 
00092 static cl::opt<bool> DisableStoreExtract(
00093     "disable-cgp-store-extract", cl::Hidden, cl::init(false),
00094     cl::desc("Disable store(extract) optimizations in CodeGenPrepare"));
00095 
00096 static cl::opt<bool> StressStoreExtract(
00097     "stress-cgp-store-extract", cl::Hidden, cl::init(false),
00098     cl::desc("Stress test store(extract) optimizations in CodeGenPrepare"));
00099 
00100 static cl::opt<bool> DisableExtLdPromotion(
00101     "disable-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
00102     cl::desc("Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
00103              "CodeGenPrepare"));
00104 
00105 static cl::opt<bool> StressExtLdPromotion(
00106     "stress-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
00107     cl::desc("Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
00108              "optimization in CodeGenPrepare"));
00109 
00110 namespace {
00111 typedef SmallPtrSet<Instruction *, 16> SetOfInstrs;
00112 struct TypeIsSExt {
00113   Type *Ty;
00114   bool IsSExt;
00115   TypeIsSExt(Type *Ty, bool IsSExt) : Ty(Ty), IsSExt(IsSExt) {}
00116 };
00117 typedef DenseMap<Instruction *, TypeIsSExt> InstrToOrigTy;
00118 class TypePromotionTransaction;
00119 
00120   class CodeGenPrepare : public FunctionPass {
00121     /// TLI - Keep a pointer of a TargetLowering to consult for determining
00122     /// transformation profitability.
00123     const TargetMachine *TM;
00124     const TargetLowering *TLI;
00125     const TargetTransformInfo *TTI;
00126     const TargetLibraryInfo *TLInfo;
00127 
00128     /// CurInstIterator - As we scan instructions optimizing them, this is the
00129     /// next instruction to optimize.  Xforms that can invalidate this should
00130     /// update it.
00131     BasicBlock::iterator CurInstIterator;
00132 
00133     /// Keeps track of non-local addresses that have been sunk into a block.
00134     /// This allows us to avoid inserting duplicate code for blocks with
00135     /// multiple load/stores of the same address.
00136     ValueMap<Value*, Value*> SunkAddrs;
00137 
00138     /// Keeps track of all truncates inserted for the current function.
00139     SetOfInstrs InsertedTruncsSet;
00140     /// Keeps track of the type of the related instruction before their
00141     /// promotion for the current function.
00142     InstrToOrigTy PromotedInsts;
00143 
00144     /// ModifiedDT - If CFG is modified in anyway.
00145     bool ModifiedDT;
00146 
00147     /// OptSize - True if optimizing for size.
00148     bool OptSize;
00149 
00150   public:
00151     static char ID; // Pass identification, replacement for typeid
00152     explicit CodeGenPrepare(const TargetMachine *TM = nullptr)
00153         : FunctionPass(ID), TM(TM), TLI(nullptr), TTI(nullptr) {
00154         initializeCodeGenPreparePass(*PassRegistry::getPassRegistry());
00155       }
00156     bool runOnFunction(Function &F) override;
00157 
00158     const char *getPassName() const override { return "CodeGen Prepare"; }
00159 
00160     void getAnalysisUsage(AnalysisUsage &AU) const override {
00161       AU.addPreserved<DominatorTreeWrapperPass>();
00162       AU.addRequired<TargetLibraryInfoWrapperPass>();
00163       AU.addRequired<TargetTransformInfoWrapperPass>();
00164     }
00165 
00166   private:
00167     bool EliminateFallThrough(Function &F);
00168     bool EliminateMostlyEmptyBlocks(Function &F);
00169     bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
00170     void EliminateMostlyEmptyBlock(BasicBlock *BB);
00171     bool OptimizeBlock(BasicBlock &BB, bool& ModifiedDT);
00172     bool OptimizeInst(Instruction *I, bool& ModifiedDT);
00173     bool OptimizeMemoryInst(Instruction *I, Value *Addr, Type *AccessTy);
00174     bool OptimizeInlineAsmInst(CallInst *CS);
00175     bool OptimizeCallInst(CallInst *CI, bool& ModifiedDT);
00176     bool MoveExtToFormExtLoad(Instruction *&I);
00177     bool OptimizeExtUses(Instruction *I);
00178     bool OptimizeSelectInst(SelectInst *SI);
00179     bool OptimizeShuffleVectorInst(ShuffleVectorInst *SI);
00180     bool OptimizeExtractElementInst(Instruction *Inst);
00181     bool DupRetToEnableTailCallOpts(BasicBlock *BB);
00182     bool PlaceDbgValues(Function &F);
00183     bool sinkAndCmp(Function &F);
00184     bool ExtLdPromotion(TypePromotionTransaction &TPT, LoadInst *&LI,
00185                         Instruction *&Inst,
00186                         const SmallVectorImpl<Instruction *> &Exts,
00187                         unsigned CreatedInstCost);
00188     bool splitBranchCondition(Function &F);
00189     bool simplifyOffsetableRelocate(Instruction &I);
00190   };
00191 }
00192 
00193 char CodeGenPrepare::ID = 0;
00194 INITIALIZE_TM_PASS(CodeGenPrepare, "codegenprepare",
00195                    "Optimize for code generation", false, false)
00196 
00197 FunctionPass *llvm::createCodeGenPreparePass(const TargetMachine *TM) {
00198   return new CodeGenPrepare(TM);
00199 }
00200 
00201 bool CodeGenPrepare::runOnFunction(Function &F) {
00202   if (skipOptnoneFunction(F))
00203     return false;
00204 
00205   bool EverMadeChange = false;
00206   // Clear per function information.
00207   InsertedTruncsSet.clear();
00208   PromotedInsts.clear();
00209 
00210   ModifiedDT = false;
00211   if (TM)
00212     TLI = TM->getSubtargetImpl(F)->getTargetLowering();
00213   TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
00214   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
00215   OptSize = F.hasFnAttribute(Attribute::OptimizeForSize);
00216 
00217   /// This optimization identifies DIV instructions that can be
00218   /// profitably bypassed and carried out with a shorter, faster divide.
00219   if (!OptSize && TLI && TLI->isSlowDivBypassed()) {
00220     const DenseMap<unsigned int, unsigned int> &BypassWidths =
00221        TLI->getBypassSlowDivWidths();
00222     for (Function::iterator I = F.begin(); I != F.end(); I++)
00223       EverMadeChange |= bypassSlowDivision(F, I, BypassWidths);
00224   }
00225 
00226   // Eliminate blocks that contain only PHI nodes and an
00227   // unconditional branch.
00228   EverMadeChange |= EliminateMostlyEmptyBlocks(F);
00229 
00230   // llvm.dbg.value is far away from the value then iSel may not be able
00231   // handle it properly. iSel will drop llvm.dbg.value if it can not
00232   // find a node corresponding to the value.
00233   EverMadeChange |= PlaceDbgValues(F);
00234 
00235   // If there is a mask, compare against zero, and branch that can be combined
00236   // into a single target instruction, push the mask and compare into branch
00237   // users. Do this before OptimizeBlock -> OptimizeInst ->
00238   // OptimizeCmpExpression, which perturbs the pattern being searched for.
00239   if (!DisableBranchOpts) {
00240     EverMadeChange |= sinkAndCmp(F);
00241     EverMadeChange |= splitBranchCondition(F);
00242   }
00243 
00244   bool MadeChange = true;
00245   while (MadeChange) {
00246     MadeChange = false;
00247     for (Function::iterator I = F.begin(); I != F.end(); ) {
00248       BasicBlock *BB = I++;
00249       bool ModifiedDTOnIteration = false;
00250       MadeChange |= OptimizeBlock(*BB, ModifiedDTOnIteration);
00251 
00252       // Restart BB iteration if the dominator tree of the Function was changed
00253       if (ModifiedDTOnIteration)
00254         break;
00255     }
00256     EverMadeChange |= MadeChange;
00257   }
00258 
00259   SunkAddrs.clear();
00260 
00261   if (!DisableBranchOpts) {
00262     MadeChange = false;
00263     SmallPtrSet<BasicBlock*, 8> WorkList;
00264     for (BasicBlock &BB : F) {
00265       SmallVector<BasicBlock *, 2> Successors(succ_begin(&BB), succ_end(&BB));
00266       MadeChange |= ConstantFoldTerminator(&BB, true);
00267       if (!MadeChange) continue;
00268 
00269       for (SmallVectorImpl<BasicBlock*>::iterator
00270              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
00271         if (pred_begin(*II) == pred_end(*II))
00272           WorkList.insert(*II);
00273     }
00274 
00275     // Delete the dead blocks and any of their dead successors.
00276     MadeChange |= !WorkList.empty();
00277     while (!WorkList.empty()) {
00278       BasicBlock *BB = *WorkList.begin();
00279       WorkList.erase(BB);
00280       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
00281 
00282       DeleteDeadBlock(BB);
00283 
00284       for (SmallVectorImpl<BasicBlock*>::iterator
00285              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
00286         if (pred_begin(*II) == pred_end(*II))
00287           WorkList.insert(*II);
00288     }
00289 
00290     // Merge pairs of basic blocks with unconditional branches, connected by
00291     // a single edge.
00292     if (EverMadeChange || MadeChange)
00293       MadeChange |= EliminateFallThrough(F);
00294 
00295     EverMadeChange |= MadeChange;
00296   }
00297 
00298   if (!DisableGCOpts) {
00299     SmallVector<Instruction *, 2> Statepoints;
00300     for (BasicBlock &BB : F)
00301       for (Instruction &I : BB)
00302         if (isStatepoint(I))
00303           Statepoints.push_back(&I);
00304     for (auto &I : Statepoints)
00305       EverMadeChange |= simplifyOffsetableRelocate(*I);
00306   }
00307 
00308   return EverMadeChange;
00309 }
00310 
00311 /// EliminateFallThrough - Merge basic blocks which are connected
00312 /// by a single edge, where one of the basic blocks has a single successor
00313 /// pointing to the other basic block, which has a single predecessor.
00314 bool CodeGenPrepare::EliminateFallThrough(Function &F) {
00315   bool Changed = false;
00316   // Scan all of the blocks in the function, except for the entry block.
00317   for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
00318     BasicBlock *BB = I++;
00319     // If the destination block has a single pred, then this is a trivial
00320     // edge, just collapse it.
00321     BasicBlock *SinglePred = BB->getSinglePredecessor();
00322 
00323     // Don't merge if BB's address is taken.
00324     if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
00325 
00326     BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
00327     if (Term && !Term->isConditional()) {
00328       Changed = true;
00329       DEBUG(dbgs() << "To merge:\n"<< *SinglePred << "\n\n\n");
00330       // Remember if SinglePred was the entry block of the function.
00331       // If so, we will need to move BB back to the entry position.
00332       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
00333       MergeBasicBlockIntoOnlyPred(BB, nullptr);
00334 
00335       if (isEntry && BB != &BB->getParent()->getEntryBlock())
00336         BB->moveBefore(&BB->getParent()->getEntryBlock());
00337 
00338       // We have erased a block. Update the iterator.
00339       I = BB;
00340     }
00341   }
00342   return Changed;
00343 }
00344 
00345 /// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes,
00346 /// debug info directives, and an unconditional branch.  Passes before isel
00347 /// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for
00348 /// isel.  Start by eliminating these blocks so we can split them the way we
00349 /// want them.
00350 bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) {
00351   bool MadeChange = false;
00352   // Note that this intentionally skips the entry block.
00353   for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
00354     BasicBlock *BB = I++;
00355 
00356     // If this block doesn't end with an uncond branch, ignore it.
00357     BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
00358     if (!BI || !BI->isUnconditional())
00359       continue;
00360 
00361     // If the instruction before the branch (skipping debug info) isn't a phi
00362     // node, then other stuff is happening here.
00363     BasicBlock::iterator BBI = BI;
00364     if (BBI != BB->begin()) {
00365       --BBI;
00366       while (isa<DbgInfoIntrinsic>(BBI)) {
00367         if (BBI == BB->begin())
00368           break;
00369         --BBI;
00370       }
00371       if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
00372         continue;
00373     }
00374 
00375     // Do not break infinite loops.
00376     BasicBlock *DestBB = BI->getSuccessor(0);
00377     if (DestBB == BB)
00378       continue;
00379 
00380     if (!CanMergeBlocks(BB, DestBB))
00381       continue;
00382 
00383     EliminateMostlyEmptyBlock(BB);
00384     MadeChange = true;
00385   }
00386   return MadeChange;
00387 }
00388 
00389 /// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a
00390 /// single uncond branch between them, and BB contains no other non-phi
00391 /// instructions.
00392 bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB,
00393                                     const BasicBlock *DestBB) const {
00394   // We only want to eliminate blocks whose phi nodes are used by phi nodes in
00395   // the successor.  If there are more complex condition (e.g. preheaders),
00396   // don't mess around with them.
00397   BasicBlock::const_iterator BBI = BB->begin();
00398   while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
00399     for (const User *U : PN->users()) {
00400       const Instruction *UI = cast<Instruction>(U);
00401       if (UI->getParent() != DestBB || !isa<PHINode>(UI))
00402         return false;
00403       // If User is inside DestBB block and it is a PHINode then check
00404       // incoming value. If incoming value is not from BB then this is
00405       // a complex condition (e.g. preheaders) we want to avoid here.
00406       if (UI->getParent() == DestBB) {
00407         if (const PHINode *UPN = dyn_cast<PHINode>(UI))
00408           for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) {
00409             Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I));
00410             if (Insn && Insn->getParent() == BB &&
00411                 Insn->getParent() != UPN->getIncomingBlock(I))
00412               return false;
00413           }
00414       }
00415     }
00416   }
00417 
00418   // If BB and DestBB contain any common predecessors, then the phi nodes in BB
00419   // and DestBB may have conflicting incoming values for the block.  If so, we
00420   // can't merge the block.
00421   const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin());
00422   if (!DestBBPN) return true;  // no conflict.
00423 
00424   // Collect the preds of BB.
00425   SmallPtrSet<const BasicBlock*, 16> BBPreds;
00426   if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
00427     // It is faster to get preds from a PHI than with pred_iterator.
00428     for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
00429       BBPreds.insert(BBPN->getIncomingBlock(i));
00430   } else {
00431     BBPreds.insert(pred_begin(BB), pred_end(BB));
00432   }
00433 
00434   // Walk the preds of DestBB.
00435   for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) {
00436     BasicBlock *Pred = DestBBPN->getIncomingBlock(i);
00437     if (BBPreds.count(Pred)) {   // Common predecessor?
00438       BBI = DestBB->begin();
00439       while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
00440         const Value *V1 = PN->getIncomingValueForBlock(Pred);
00441         const Value *V2 = PN->getIncomingValueForBlock(BB);
00442 
00443         // If V2 is a phi node in BB, look up what the mapped value will be.
00444         if (const PHINode *V2PN = dyn_cast<PHINode>(V2))
00445           if (V2PN->getParent() == BB)
00446             V2 = V2PN->getIncomingValueForBlock(Pred);
00447 
00448         // If there is a conflict, bail out.
00449         if (V1 != V2) return false;
00450       }
00451     }
00452   }
00453 
00454   return true;
00455 }
00456 
00457 
00458 /// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and
00459 /// an unconditional branch in it.
00460 void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) {
00461   BranchInst *BI = cast<BranchInst>(BB->getTerminator());
00462   BasicBlock *DestBB = BI->getSuccessor(0);
00463 
00464   DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB);
00465 
00466   // If the destination block has a single pred, then this is a trivial edge,
00467   // just collapse it.
00468   if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
00469     if (SinglePred != DestBB) {
00470       // Remember if SinglePred was the entry block of the function.  If so, we
00471       // will need to move BB back to the entry position.
00472       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
00473       MergeBasicBlockIntoOnlyPred(DestBB, nullptr);
00474 
00475       if (isEntry && BB != &BB->getParent()->getEntryBlock())
00476         BB->moveBefore(&BB->getParent()->getEntryBlock());
00477 
00478       DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
00479       return;
00480     }
00481   }
00482 
00483   // Otherwise, we have multiple predecessors of BB.  Update the PHIs in DestBB
00484   // to handle the new incoming edges it is about to have.
00485   PHINode *PN;
00486   for (BasicBlock::iterator BBI = DestBB->begin();
00487        (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
00488     // Remove the incoming value for BB, and remember it.
00489     Value *InVal = PN->removeIncomingValue(BB, false);
00490 
00491     // Two options: either the InVal is a phi node defined in BB or it is some
00492     // value that dominates BB.
00493     PHINode *InValPhi = dyn_cast<PHINode>(InVal);
00494     if (InValPhi && InValPhi->getParent() == BB) {
00495       // Add all of the input values of the input PHI as inputs of this phi.
00496       for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i)
00497         PN->addIncoming(InValPhi->getIncomingValue(i),
00498                         InValPhi->getIncomingBlock(i));
00499     } else {
00500       // Otherwise, add one instance of the dominating value for each edge that
00501       // we will be adding.
00502       if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
00503         for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
00504           PN->addIncoming(InVal, BBPN->getIncomingBlock(i));
00505       } else {
00506         for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
00507           PN->addIncoming(InVal, *PI);
00508       }
00509     }
00510   }
00511 
00512   // The PHIs are now updated, change everything that refers to BB to use
00513   // DestBB and remove BB.
00514   BB->replaceAllUsesWith(DestBB);
00515   BB->eraseFromParent();
00516   ++NumBlocksElim;
00517 
00518   DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
00519 }
00520 
00521 // Computes a map of base pointer relocation instructions to corresponding
00522 // derived pointer relocation instructions given a vector of all relocate calls
00523 static void computeBaseDerivedRelocateMap(
00524     const SmallVectorImpl<User *> &AllRelocateCalls,
00525     DenseMap<IntrinsicInst *, SmallVector<IntrinsicInst *, 2>> &
00526         RelocateInstMap) {
00527   // Collect information in two maps: one primarily for locating the base object
00528   // while filling the second map; the second map is the final structure holding
00529   // a mapping between Base and corresponding Derived relocate calls
00530   DenseMap<std::pair<unsigned, unsigned>, IntrinsicInst *> RelocateIdxMap;
00531   for (auto &U : AllRelocateCalls) {
00532     GCRelocateOperands ThisRelocate(U);
00533     IntrinsicInst *I = cast<IntrinsicInst>(U);
00534     auto K = std::make_pair(ThisRelocate.getBasePtrIndex(),
00535                             ThisRelocate.getDerivedPtrIndex());
00536     RelocateIdxMap.insert(std::make_pair(K, I));
00537   }
00538   for (auto &Item : RelocateIdxMap) {
00539     std::pair<unsigned, unsigned> Key = Item.first;
00540     if (Key.first == Key.second)
00541       // Base relocation: nothing to insert
00542       continue;
00543 
00544     IntrinsicInst *I = Item.second;
00545     auto BaseKey = std::make_pair(Key.first, Key.first);
00546 
00547     // We're iterating over RelocateIdxMap so we cannot modify it.
00548     auto MaybeBase = RelocateIdxMap.find(BaseKey);
00549     if (MaybeBase == RelocateIdxMap.end())
00550       // TODO: We might want to insert a new base object relocate and gep off
00551       // that, if there are enough derived object relocates.
00552       continue;
00553 
00554     RelocateInstMap[MaybeBase->second].push_back(I);
00555   }
00556 }
00557 
00558 // Accepts a GEP and extracts the operands into a vector provided they're all
00559 // small integer constants
00560 static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP,
00561                                           SmallVectorImpl<Value *> &OffsetV) {
00562   for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
00563     // Only accept small constant integer operands
00564     auto Op = dyn_cast<ConstantInt>(GEP->getOperand(i));
00565     if (!Op || Op->getZExtValue() > 20)
00566       return false;
00567   }
00568 
00569   for (unsigned i = 1; i < GEP->getNumOperands(); i++)
00570     OffsetV.push_back(GEP->getOperand(i));
00571   return true;
00572 }
00573 
00574 // Takes a RelocatedBase (base pointer relocation instruction) and Targets to
00575 // replace, computes a replacement, and affects it.
00576 static bool
00577 simplifyRelocatesOffABase(IntrinsicInst *RelocatedBase,
00578                           const SmallVectorImpl<IntrinsicInst *> &Targets) {
00579   bool MadeChange = false;
00580   for (auto &ToReplace : Targets) {
00581     GCRelocateOperands MasterRelocate(RelocatedBase);
00582     GCRelocateOperands ThisRelocate(ToReplace);
00583 
00584     assert(ThisRelocate.getBasePtrIndex() == MasterRelocate.getBasePtrIndex() &&
00585            "Not relocating a derived object of the original base object");
00586     if (ThisRelocate.getBasePtrIndex() == ThisRelocate.getDerivedPtrIndex()) {
00587       // A duplicate relocate call. TODO: coalesce duplicates.
00588       continue;
00589     }
00590 
00591     Value *Base = ThisRelocate.getBasePtr();
00592     auto Derived = dyn_cast<GetElementPtrInst>(ThisRelocate.getDerivedPtr());
00593     if (!Derived || Derived->getPointerOperand() != Base)
00594       continue;
00595 
00596     SmallVector<Value *, 2> OffsetV;
00597     if (!getGEPSmallConstantIntOffsetV(Derived, OffsetV))
00598       continue;
00599 
00600     // Create a Builder and replace the target callsite with a gep
00601     assert(RelocatedBase->getNextNode() && "Should always have one since it's not a terminator");
00602 
00603     // Insert after RelocatedBase
00604     IRBuilder<> Builder(RelocatedBase->getNextNode());
00605     Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
00606 
00607     // If gc_relocate does not match the actual type, cast it to the right type.
00608     // In theory, there must be a bitcast after gc_relocate if the type does not
00609     // match, and we should reuse it to get the derived pointer. But it could be
00610     // cases like this:
00611     // bb1:
00612     //  ...
00613     //  %g1 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...)
00614     //  br label %merge
00615     //
00616     // bb2:
00617     //  ...
00618     //  %g2 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...)
00619     //  br label %merge
00620     //
00621     // merge:
00622     //  %p1 = phi i8 addrspace(1)* [ %g1, %bb1 ], [ %g2, %bb2 ]
00623     //  %cast = bitcast i8 addrspace(1)* %p1 in to i32 addrspace(1)*
00624     //
00625     // In this case, we can not find the bitcast any more. So we insert a new bitcast
00626     // no matter there is already one or not. In this way, we can handle all cases, and
00627     // the extra bitcast should be optimized away in later passes.
00628     Instruction *ActualRelocatedBase = RelocatedBase;
00629     if (RelocatedBase->getType() != Base->getType()) {
00630       ActualRelocatedBase =
00631           cast<Instruction>(Builder.CreateBitCast(RelocatedBase, Base->getType()));
00632     }
00633     Value *Replacement = Builder.CreateGEP(
00634         Derived->getSourceElementType(), ActualRelocatedBase, makeArrayRef(OffsetV));
00635     Instruction *ReplacementInst = cast<Instruction>(Replacement);
00636     Replacement->takeName(ToReplace);
00637     // If the newly generated derived pointer's type does not match the original derived
00638     // pointer's type, cast the new derived pointer to match it. Same reasoning as above.
00639     Instruction *ActualReplacement = ReplacementInst;
00640     if (ReplacementInst->getType() != ToReplace->getType()) {
00641       ActualReplacement =
00642           cast<Instruction>(Builder.CreateBitCast(ReplacementInst, ToReplace->getType()));
00643     }
00644     ToReplace->replaceAllUsesWith(ActualReplacement);
00645     ToReplace->eraseFromParent();
00646 
00647     MadeChange = true;
00648   }
00649   return MadeChange;
00650 }
00651 
00652 // Turns this:
00653 //
00654 // %base = ...
00655 // %ptr = gep %base + 15
00656 // %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
00657 // %base' = relocate(%tok, i32 4, i32 4)
00658 // %ptr' = relocate(%tok, i32 4, i32 5)
00659 // %val = load %ptr'
00660 //
00661 // into this:
00662 //
00663 // %base = ...
00664 // %ptr = gep %base + 15
00665 // %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
00666 // %base' = gc.relocate(%tok, i32 4, i32 4)
00667 // %ptr' = gep %base' + 15
00668 // %val = load %ptr'
00669 bool CodeGenPrepare::simplifyOffsetableRelocate(Instruction &I) {
00670   bool MadeChange = false;
00671   SmallVector<User *, 2> AllRelocateCalls;
00672 
00673   for (auto *U : I.users())
00674     if (isGCRelocate(dyn_cast<Instruction>(U)))
00675       // Collect all the relocate calls associated with a statepoint
00676       AllRelocateCalls.push_back(U);
00677 
00678   // We need atleast one base pointer relocation + one derived pointer
00679   // relocation to mangle
00680   if (AllRelocateCalls.size() < 2)
00681     return false;
00682 
00683   // RelocateInstMap is a mapping from the base relocate instruction to the
00684   // corresponding derived relocate instructions
00685   DenseMap<IntrinsicInst *, SmallVector<IntrinsicInst *, 2>> RelocateInstMap;
00686   computeBaseDerivedRelocateMap(AllRelocateCalls, RelocateInstMap);
00687   if (RelocateInstMap.empty())
00688     return false;
00689 
00690   for (auto &Item : RelocateInstMap)
00691     // Item.first is the RelocatedBase to offset against
00692     // Item.second is the vector of Targets to replace
00693     MadeChange = simplifyRelocatesOffABase(Item.first, Item.second);
00694   return MadeChange;
00695 }
00696 
00697 /// SinkCast - Sink the specified cast instruction into its user blocks
00698 static bool SinkCast(CastInst *CI) {
00699   BasicBlock *DefBB = CI->getParent();
00700 
00701   /// InsertedCasts - Only insert a cast in each block once.
00702   DenseMap<BasicBlock*, CastInst*> InsertedCasts;
00703 
00704   bool MadeChange = false;
00705   for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
00706        UI != E; ) {
00707     Use &TheUse = UI.getUse();
00708     Instruction *User = cast<Instruction>(*UI);
00709 
00710     // Figure out which BB this cast is used in.  For PHI's this is the
00711     // appropriate predecessor block.
00712     BasicBlock *UserBB = User->getParent();
00713     if (PHINode *PN = dyn_cast<PHINode>(User)) {
00714       UserBB = PN->getIncomingBlock(TheUse);
00715     }
00716 
00717     // Preincrement use iterator so we don't invalidate it.
00718     ++UI;
00719 
00720     // If this user is in the same block as the cast, don't change the cast.
00721     if (UserBB == DefBB) continue;
00722 
00723     // If we have already inserted a cast into this block, use it.
00724     CastInst *&InsertedCast = InsertedCasts[UserBB];
00725 
00726     if (!InsertedCast) {
00727       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
00728       InsertedCast =
00729         CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "",
00730                          InsertPt);
00731     }
00732 
00733     // Replace a use of the cast with a use of the new cast.
00734     TheUse = InsertedCast;
00735     MadeChange = true;
00736     ++NumCastUses;
00737   }
00738 
00739   // If we removed all uses, nuke the cast.
00740   if (CI->use_empty()) {
00741     CI->eraseFromParent();
00742     MadeChange = true;
00743   }
00744 
00745   return MadeChange;
00746 }
00747 
00748 /// OptimizeNoopCopyExpression - If the specified cast instruction is a noop
00749 /// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC),
00750 /// sink it into user blocks to reduce the number of virtual
00751 /// registers that must be created and coalesced.
00752 ///
00753 /// Return true if any changes are made.
00754 ///
00755 static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){
00756   // If this is a noop copy,
00757   EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType());
00758   EVT DstVT = TLI.getValueType(CI->getType());
00759 
00760   // This is an fp<->int conversion?
00761   if (SrcVT.isInteger() != DstVT.isInteger())
00762     return false;
00763 
00764   // If this is an extension, it will be a zero or sign extension, which
00765   // isn't a noop.
00766   if (SrcVT.bitsLT(DstVT)) return false;
00767 
00768   // If these values will be promoted, find out what they will be promoted
00769   // to.  This helps us consider truncates on PPC as noop copies when they
00770   // are.
00771   if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
00772       TargetLowering::TypePromoteInteger)
00773     SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
00774   if (TLI.getTypeAction(CI->getContext(), DstVT) ==
00775       TargetLowering::TypePromoteInteger)
00776     DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
00777 
00778   // If, after promotion, these are the same types, this is a noop copy.
00779   if (SrcVT != DstVT)
00780     return false;
00781 
00782   return SinkCast(CI);
00783 }
00784 
00785 /// CombineUAddWithOverflow - try to combine CI into a call to the
00786 /// llvm.uadd.with.overflow intrinsic if possible.
00787 ///
00788 /// Return true if any changes were made.
00789 static bool CombineUAddWithOverflow(CmpInst *CI) {
00790   Value *A, *B;
00791   Instruction *AddI;
00792   if (!match(CI,
00793              m_UAddWithOverflow(m_Value(A), m_Value(B), m_Instruction(AddI))))
00794     return false;
00795 
00796   Type *Ty = AddI->getType();
00797   if (!isa<IntegerType>(Ty))
00798     return false;
00799 
00800   // We don't want to move around uses of condition values this late, so we we
00801   // check if it is legal to create the call to the intrinsic in the basic
00802   // block containing the icmp:
00803 
00804   if (AddI->getParent() != CI->getParent() && !AddI->hasOneUse())
00805     return false;
00806 
00807 #ifndef NDEBUG
00808   // Someday m_UAddWithOverflow may get smarter, but this is a safe assumption
00809   // for now:
00810   if (AddI->hasOneUse())
00811     assert(*AddI->user_begin() == CI && "expected!");
00812 #endif
00813 
00814   Module *M = CI->getParent()->getParent()->getParent();
00815   Value *F = Intrinsic::getDeclaration(M, Intrinsic::uadd_with_overflow, Ty);
00816 
00817   auto *InsertPt = AddI->hasOneUse() ? CI : AddI;
00818 
00819   auto *UAddWithOverflow =
00820       CallInst::Create(F, {A, B}, "uadd.overflow", InsertPt);
00821   auto *UAdd = ExtractValueInst::Create(UAddWithOverflow, 0, "uadd", InsertPt);
00822   auto *Overflow =
00823       ExtractValueInst::Create(UAddWithOverflow, 1, "overflow", InsertPt);
00824 
00825   CI->replaceAllUsesWith(Overflow);
00826   AddI->replaceAllUsesWith(UAdd);
00827   CI->eraseFromParent();
00828   AddI->eraseFromParent();
00829   return true;
00830 }
00831 
00832 /// SinkCmpExpression - Sink the given CmpInst into user blocks to reduce
00833 /// the number of virtual registers that must be created and coalesced.  This is
00834 /// a clear win except on targets with multiple condition code registers
00835 ///  (PowerPC), where it might lose; some adjustment may be wanted there.
00836 ///
00837 /// Return true if any changes are made.
00838 static bool SinkCmpExpression(CmpInst *CI) {
00839   BasicBlock *DefBB = CI->getParent();
00840 
00841   /// InsertedCmp - Only insert a cmp in each block once.
00842   DenseMap<BasicBlock*, CmpInst*> InsertedCmps;
00843 
00844   bool MadeChange = false;
00845   for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
00846        UI != E; ) {
00847     Use &TheUse = UI.getUse();
00848     Instruction *User = cast<Instruction>(*UI);
00849 
00850     // Preincrement use iterator so we don't invalidate it.
00851     ++UI;
00852 
00853     // Don't bother for PHI nodes.
00854     if (isa<PHINode>(User))
00855       continue;
00856 
00857     // Figure out which BB this cmp is used in.
00858     BasicBlock *UserBB = User->getParent();
00859 
00860     // If this user is in the same block as the cmp, don't change the cmp.
00861     if (UserBB == DefBB) continue;
00862 
00863     // If we have already inserted a cmp into this block, use it.
00864     CmpInst *&InsertedCmp = InsertedCmps[UserBB];
00865 
00866     if (!InsertedCmp) {
00867       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
00868       InsertedCmp =
00869         CmpInst::Create(CI->getOpcode(),
00870                         CI->getPredicate(),  CI->getOperand(0),
00871                         CI->getOperand(1), "", InsertPt);
00872     }
00873 
00874     // Replace a use of the cmp with a use of the new cmp.
00875     TheUse = InsertedCmp;
00876     MadeChange = true;
00877     ++NumCmpUses;
00878   }
00879 
00880   // If we removed all uses, nuke the cmp.
00881   if (CI->use_empty()) {
00882     CI->eraseFromParent();
00883     MadeChange = true;
00884   }
00885 
00886   return MadeChange;
00887 }
00888 
00889 static bool OptimizeCmpExpression(CmpInst *CI) {
00890   if (SinkCmpExpression(CI))
00891     return true;
00892 
00893   if (CombineUAddWithOverflow(CI))
00894     return true;
00895 
00896   return false;
00897 }
00898 
00899 /// isExtractBitsCandidateUse - Check if the candidates could
00900 /// be combined with shift instruction, which includes:
00901 /// 1. Truncate instruction
00902 /// 2. And instruction and the imm is a mask of the low bits:
00903 /// imm & (imm+1) == 0
00904 static bool isExtractBitsCandidateUse(Instruction *User) {
00905   if (!isa<TruncInst>(User)) {
00906     if (User->getOpcode() != Instruction::And ||
00907         !isa<ConstantInt>(User->getOperand(1)))
00908       return false;
00909 
00910     const APInt &Cimm = cast<ConstantInt>(User->getOperand(1))->getValue();
00911 
00912     if ((Cimm & (Cimm + 1)).getBoolValue())
00913       return false;
00914   }
00915   return true;
00916 }
00917 
00918 /// SinkShiftAndTruncate - sink both shift and truncate instruction
00919 /// to the use of truncate's BB.
00920 static bool
00921 SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI,
00922                      DenseMap<BasicBlock *, BinaryOperator *> &InsertedShifts,
00923                      const TargetLowering &TLI) {
00924   BasicBlock *UserBB = User->getParent();
00925   DenseMap<BasicBlock *, CastInst *> InsertedTruncs;
00926   TruncInst *TruncI = dyn_cast<TruncInst>(User);
00927   bool MadeChange = false;
00928 
00929   for (Value::user_iterator TruncUI = TruncI->user_begin(),
00930                             TruncE = TruncI->user_end();
00931        TruncUI != TruncE;) {
00932 
00933     Use &TruncTheUse = TruncUI.getUse();
00934     Instruction *TruncUser = cast<Instruction>(*TruncUI);
00935     // Preincrement use iterator so we don't invalidate it.
00936 
00937     ++TruncUI;
00938 
00939     int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode());
00940     if (!ISDOpcode)
00941       continue;
00942 
00943     // If the use is actually a legal node, there will not be an
00944     // implicit truncate.
00945     // FIXME: always querying the result type is just an
00946     // approximation; some nodes' legality is determined by the
00947     // operand or other means. There's no good way to find out though.
00948     if (TLI.isOperationLegalOrCustom(
00949             ISDOpcode, TLI.getValueType(TruncUser->getType(), true)))
00950       continue;
00951 
00952     // Don't bother for PHI nodes.
00953     if (isa<PHINode>(TruncUser))
00954       continue;
00955 
00956     BasicBlock *TruncUserBB = TruncUser->getParent();
00957 
00958     if (UserBB == TruncUserBB)
00959       continue;
00960 
00961     BinaryOperator *&InsertedShift = InsertedShifts[TruncUserBB];
00962     CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
00963 
00964     if (!InsertedShift && !InsertedTrunc) {
00965       BasicBlock::iterator InsertPt = TruncUserBB->getFirstInsertionPt();
00966       // Sink the shift
00967       if (ShiftI->getOpcode() == Instruction::AShr)
00968         InsertedShift =
00969             BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, "", InsertPt);
00970       else
00971         InsertedShift =
00972             BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "", InsertPt);
00973 
00974       // Sink the trunc
00975       BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt();
00976       TruncInsertPt++;
00977 
00978       InsertedTrunc = CastInst::Create(TruncI->getOpcode(), InsertedShift,
00979                                        TruncI->getType(), "", TruncInsertPt);
00980 
00981       MadeChange = true;
00982 
00983       TruncTheUse = InsertedTrunc;
00984     }
00985   }
00986   return MadeChange;
00987 }
00988 
00989 /// OptimizeExtractBits - sink the shift *right* instruction into user blocks if
00990 /// the uses could potentially be combined with this shift instruction and
00991 /// generate BitExtract instruction. It will only be applied if the architecture
00992 /// supports BitExtract instruction. Here is an example:
00993 /// BB1:
00994 ///   %x.extract.shift = lshr i64 %arg1, 32
00995 /// BB2:
00996 ///   %x.extract.trunc = trunc i64 %x.extract.shift to i16
00997 /// ==>
00998 ///
00999 /// BB2:
01000 ///   %x.extract.shift.1 = lshr i64 %arg1, 32
01001 ///   %x.extract.trunc = trunc i64 %x.extract.shift.1 to i16
01002 ///
01003 /// CodeGen will recoginze the pattern in BB2 and generate BitExtract
01004 /// instruction.
01005 /// Return true if any changes are made.
01006 static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI,
01007                                 const TargetLowering &TLI) {
01008   BasicBlock *DefBB = ShiftI->getParent();
01009 
01010   /// Only insert instructions in each block once.
01011   DenseMap<BasicBlock *, BinaryOperator *> InsertedShifts;
01012 
01013   bool shiftIsLegal = TLI.isTypeLegal(TLI.getValueType(ShiftI->getType()));
01014 
01015   bool MadeChange = false;
01016   for (Value::user_iterator UI = ShiftI->user_begin(), E = ShiftI->user_end();
01017        UI != E;) {
01018     Use &TheUse = UI.getUse();
01019     Instruction *User = cast<Instruction>(*UI);
01020     // Preincrement use iterator so we don't invalidate it.
01021     ++UI;
01022 
01023     // Don't bother for PHI nodes.
01024     if (isa<PHINode>(User))
01025       continue;
01026 
01027     if (!isExtractBitsCandidateUse(User))
01028       continue;
01029 
01030     BasicBlock *UserBB = User->getParent();
01031 
01032     if (UserBB == DefBB) {
01033       // If the shift and truncate instruction are in the same BB. The use of
01034       // the truncate(TruncUse) may still introduce another truncate if not
01035       // legal. In this case, we would like to sink both shift and truncate
01036       // instruction to the BB of TruncUse.
01037       // for example:
01038       // BB1:
01039       // i64 shift.result = lshr i64 opnd, imm
01040       // trunc.result = trunc shift.result to i16
01041       //
01042       // BB2:
01043       //   ----> We will have an implicit truncate here if the architecture does
01044       //   not have i16 compare.
01045       // cmp i16 trunc.result, opnd2
01046       //
01047       if (isa<TruncInst>(User) && shiftIsLegal
01048           // If the type of the truncate is legal, no trucate will be
01049           // introduced in other basic blocks.
01050           && (!TLI.isTypeLegal(TLI.getValueType(User->getType()))))
01051         MadeChange =
01052             SinkShiftAndTruncate(ShiftI, User, CI, InsertedShifts, TLI);
01053 
01054       continue;
01055     }
01056     // If we have already inserted a shift into this block, use it.
01057     BinaryOperator *&InsertedShift = InsertedShifts[UserBB];
01058 
01059     if (!InsertedShift) {
01060       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
01061 
01062       if (ShiftI->getOpcode() == Instruction::AShr)
01063         InsertedShift =
01064             BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, "", InsertPt);
01065       else
01066         InsertedShift =
01067             BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "", InsertPt);
01068 
01069       MadeChange = true;
01070     }
01071 
01072     // Replace a use of the shift with a use of the new shift.
01073     TheUse = InsertedShift;
01074   }
01075 
01076   // If we removed all uses, nuke the shift.
01077   if (ShiftI->use_empty())
01078     ShiftI->eraseFromParent();
01079 
01080   return MadeChange;
01081 }
01082 
01083 //  ScalarizeMaskedLoad() translates masked load intrinsic, like 
01084 // <16 x i32 > @llvm.masked.load( <16 x i32>* %addr, i32 align,
01085 //                               <16 x i1> %mask, <16 x i32> %passthru)
01086 // to a chain of basic blocks, whith loading element one-by-one if
01087 // the appropriate mask bit is set
01088 // 
01089 //  %1 = bitcast i8* %addr to i32*
01090 //  %2 = extractelement <16 x i1> %mask, i32 0
01091 //  %3 = icmp eq i1 %2, true
01092 //  br i1 %3, label %cond.load, label %else
01093 //
01094 //cond.load:                                        ; preds = %0
01095 //  %4 = getelementptr i32* %1, i32 0
01096 //  %5 = load i32* %4
01097 //  %6 = insertelement <16 x i32> undef, i32 %5, i32 0
01098 //  br label %else
01099 //
01100 //else:                                             ; preds = %0, %cond.load
01101 //  %res.phi.else = phi <16 x i32> [ %6, %cond.load ], [ undef, %0 ]
01102 //  %7 = extractelement <16 x i1> %mask, i32 1
01103 //  %8 = icmp eq i1 %7, true
01104 //  br i1 %8, label %cond.load1, label %else2
01105 //
01106 //cond.load1:                                       ; preds = %else
01107 //  %9 = getelementptr i32* %1, i32 1
01108 //  %10 = load i32* %9
01109 //  %11 = insertelement <16 x i32> %res.phi.else, i32 %10, i32 1
01110 //  br label %else2
01111 //
01112 //else2:                                            ; preds = %else, %cond.load1
01113 //  %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else, %else ]
01114 //  %12 = extractelement <16 x i1> %mask, i32 2
01115 //  %13 = icmp eq i1 %12, true
01116 //  br i1 %13, label %cond.load4, label %else5
01117 //
01118 static void ScalarizeMaskedLoad(CallInst *CI) {
01119   Value *Ptr  = CI->getArgOperand(0);
01120   Value *Src0 = CI->getArgOperand(3);
01121   Value *Mask = CI->getArgOperand(2);
01122   VectorType *VecType = dyn_cast<VectorType>(CI->getType());
01123   Type *EltTy = VecType->getElementType();
01124 
01125   assert(VecType && "Unexpected return type of masked load intrinsic");
01126 
01127   IRBuilder<> Builder(CI->getContext());
01128   Instruction *InsertPt = CI;
01129   BasicBlock *IfBlock = CI->getParent();
01130   BasicBlock *CondBlock = nullptr;
01131   BasicBlock *PrevIfBlock = CI->getParent();
01132   Builder.SetInsertPoint(InsertPt);
01133 
01134   Builder.SetCurrentDebugLocation(CI->getDebugLoc());
01135 
01136   // Bitcast %addr fron i8* to EltTy*
01137   Type *NewPtrType =
01138     EltTy->getPointerTo(cast<PointerType>(Ptr->getType())->getAddressSpace());
01139   Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType);
01140   Value *UndefVal = UndefValue::get(VecType);
01141 
01142   // The result vector
01143   Value *VResult = UndefVal;
01144 
01145   PHINode *Phi = nullptr;
01146   Value *PrevPhi = UndefVal;
01147 
01148   unsigned VectorWidth = VecType->getNumElements();
01149   for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
01150 
01151     // Fill the "else" block, created in the previous iteration
01152     //
01153     //  %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else, %else ]
01154     //  %mask_1 = extractelement <16 x i1> %mask, i32 Idx
01155     //  %to_load = icmp eq i1 %mask_1, true
01156     //  br i1 %to_load, label %cond.load, label %else
01157     //
01158     if (Idx > 0) {
01159       Phi = Builder.CreatePHI(VecType, 2, "res.phi.else");
01160       Phi->addIncoming(VResult, CondBlock);
01161       Phi->addIncoming(PrevPhi, PrevIfBlock);
01162       PrevPhi = Phi;
01163       VResult = Phi;
01164     }
01165 
01166     Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx));
01167     Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
01168                                     ConstantInt::get(Predicate->getType(), 1));
01169 
01170     // Create "cond" block
01171     //
01172     //  %EltAddr = getelementptr i32* %1, i32 0
01173     //  %Elt = load i32* %EltAddr
01174     //  VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx
01175     //
01176     CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.load");
01177     Builder.SetInsertPoint(InsertPt);
01178 
01179     Value *Gep =
01180         Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
01181     LoadInst* Load = Builder.CreateLoad(Gep, false);
01182     VResult = Builder.CreateInsertElement(VResult, Load, Builder.getInt32(Idx));
01183 
01184     // Create "else" block, fill it in the next iteration
01185     BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
01186     Builder.SetInsertPoint(InsertPt);
01187     Instruction *OldBr = IfBlock->getTerminator();
01188     BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
01189     OldBr->eraseFromParent();
01190     PrevIfBlock = IfBlock;
01191     IfBlock = NewIfBlock;
01192   }
01193 
01194   Phi = Builder.CreatePHI(VecType, 2, "res.phi.select");
01195   Phi->addIncoming(VResult, CondBlock);
01196   Phi->addIncoming(PrevPhi, PrevIfBlock);
01197   Value *NewI = Builder.CreateSelect(Mask, Phi, Src0);
01198   CI->replaceAllUsesWith(NewI);
01199   CI->eraseFromParent();
01200 }
01201 
01202 //  ScalarizeMaskedStore() translates masked store intrinsic, like
01203 // void @llvm.masked.store(<16 x i32> %src, <16 x i32>* %addr, i32 align,
01204 //                               <16 x i1> %mask)
01205 // to a chain of basic blocks, that stores element one-by-one if
01206 // the appropriate mask bit is set
01207 //
01208 //   %1 = bitcast i8* %addr to i32*
01209 //   %2 = extractelement <16 x i1> %mask, i32 0
01210 //   %3 = icmp eq i1 %2, true
01211 //   br i1 %3, label %cond.store, label %else
01212 //
01213 // cond.store:                                       ; preds = %0
01214 //   %4 = extractelement <16 x i32> %val, i32 0
01215 //   %5 = getelementptr i32* %1, i32 0
01216 //   store i32 %4, i32* %5
01217 //   br label %else
01218 // 
01219 // else:                                             ; preds = %0, %cond.store
01220 //   %6 = extractelement <16 x i1> %mask, i32 1
01221 //   %7 = icmp eq i1 %6, true
01222 //   br i1 %7, label %cond.store1, label %else2
01223 // 
01224 // cond.store1:                                      ; preds = %else
01225 //   %8 = extractelement <16 x i32> %val, i32 1
01226 //   %9 = getelementptr i32* %1, i32 1
01227 //   store i32 %8, i32* %9
01228 //   br label %else2
01229 //   . . .
01230 static void ScalarizeMaskedStore(CallInst *CI) {
01231   Value *Ptr  = CI->getArgOperand(1);
01232   Value *Src = CI->getArgOperand(0);
01233   Value *Mask = CI->getArgOperand(3);
01234 
01235   VectorType *VecType = dyn_cast<VectorType>(Src->getType());
01236   Type *EltTy = VecType->getElementType();
01237 
01238   assert(VecType && "Unexpected data type in masked store intrinsic");
01239 
01240   IRBuilder<> Builder(CI->getContext());
01241   Instruction *InsertPt = CI;
01242   BasicBlock *IfBlock = CI->getParent();
01243   Builder.SetInsertPoint(InsertPt);
01244   Builder.SetCurrentDebugLocation(CI->getDebugLoc());
01245 
01246   // Bitcast %addr fron i8* to EltTy*
01247   Type *NewPtrType =
01248     EltTy->getPointerTo(cast<PointerType>(Ptr->getType())->getAddressSpace());
01249   Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType);
01250 
01251   unsigned VectorWidth = VecType->getNumElements();
01252   for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
01253 
01254     // Fill the "else" block, created in the previous iteration
01255     //
01256     //  %mask_1 = extractelement <16 x i1> %mask, i32 Idx
01257     //  %to_store = icmp eq i1 %mask_1, true
01258     //  br i1 %to_load, label %cond.store, label %else
01259     //
01260     Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx));
01261     Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
01262                                     ConstantInt::get(Predicate->getType(), 1));
01263 
01264     // Create "cond" block
01265     //
01266     //  %OneElt = extractelement <16 x i32> %Src, i32 Idx
01267     //  %EltAddr = getelementptr i32* %1, i32 0
01268     //  %store i32 %OneElt, i32* %EltAddr
01269     //
01270     BasicBlock *CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store");
01271     Builder.SetInsertPoint(InsertPt);
01272     
01273     Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx));
01274     Value *Gep =
01275         Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
01276     Builder.CreateStore(OneElt, Gep);
01277 
01278     // Create "else" block, fill it in the next iteration
01279     BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
01280     Builder.SetInsertPoint(InsertPt);
01281     Instruction *OldBr = IfBlock->getTerminator();
01282     BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
01283     OldBr->eraseFromParent();
01284     IfBlock = NewIfBlock;
01285   }
01286   CI->eraseFromParent();
01287 }
01288 
01289 bool CodeGenPrepare::OptimizeCallInst(CallInst *CI, bool& ModifiedDT) {
01290   BasicBlock *BB = CI->getParent();
01291 
01292   // Lower inline assembly if we can.
01293   // If we found an inline asm expession, and if the target knows how to
01294   // lower it to normal LLVM code, do so now.
01295   if (TLI && isa<InlineAsm>(CI->getCalledValue())) {
01296     if (TLI->ExpandInlineAsm(CI)) {
01297       // Avoid invalidating the iterator.
01298       CurInstIterator = BB->begin();
01299       // Avoid processing instructions out of order, which could cause
01300       // reuse before a value is defined.
01301       SunkAddrs.clear();
01302       return true;
01303     }
01304     // Sink address computing for memory operands into the block.
01305     if (OptimizeInlineAsmInst(CI))
01306       return true;
01307   }
01308 
01309   const DataLayout *TD = TLI ? TLI->getDataLayout() : nullptr;
01310 
01311   // Align the pointer arguments to this call if the target thinks it's a good
01312   // idea
01313   unsigned MinSize, PrefAlign;
01314   if (TLI && TD && TLI->shouldAlignPointerArgs(CI, MinSize, PrefAlign)) {
01315     for (auto &Arg : CI->arg_operands()) {
01316       // We want to align both objects whose address is used directly and
01317       // objects whose address is used in casts and GEPs, though it only makes
01318       // sense for GEPs if the offset is a multiple of the desired alignment and
01319       // if size - offset meets the size threshold.
01320       if (!Arg->getType()->isPointerTy())
01321         continue;
01322       APInt Offset(TD->getPointerSizeInBits(
01323                      cast<PointerType>(Arg->getType())->getAddressSpace()), 0);
01324       Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*TD, Offset);
01325       uint64_t Offset2 = Offset.getLimitedValue();
01326       if ((Offset2 & (PrefAlign-1)) != 0)
01327         continue;
01328       AllocaInst *AI;
01329       if ((AI = dyn_cast<AllocaInst>(Val)) &&
01330           AI->getAlignment() < PrefAlign &&
01331           TD->getTypeAllocSize(AI->getAllocatedType()) >= MinSize + Offset2)
01332         AI->setAlignment(PrefAlign);
01333       // Global variables can only be aligned if they are defined in this
01334       // object (i.e. they are uniquely initialized in this object), and
01335       // over-aligning global variables that have an explicit section is
01336       // forbidden.
01337       GlobalVariable *GV;
01338       if ((GV = dyn_cast<GlobalVariable>(Val)) &&
01339           GV->hasUniqueInitializer() &&
01340           !GV->hasSection() &&
01341           GV->getAlignment() < PrefAlign &&
01342           TD->getTypeAllocSize(
01343             GV->getType()->getElementType()) >= MinSize + Offset2)
01344         GV->setAlignment(PrefAlign);
01345     }
01346     // If this is a memcpy (or similar) then we may be able to improve the
01347     // alignment
01348     if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(CI)) {
01349       unsigned Align = getKnownAlignment(MI->getDest(), *TD);
01350       if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
01351         Align = std::min(Align, getKnownAlignment(MTI->getSource(), *TD));
01352       if (Align > MI->getAlignment())
01353         MI->setAlignment(ConstantInt::get(MI->getAlignmentType(), Align));
01354     }
01355   }
01356 
01357   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
01358   if (II) {
01359     switch (II->getIntrinsicID()) {
01360     default: break;
01361     case Intrinsic::objectsize: {
01362       // Lower all uses of llvm.objectsize.*
01363       bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1);
01364       Type *ReturnTy = CI->getType();
01365       Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL);
01366 
01367       // Substituting this can cause recursive simplifications, which can
01368       // invalidate our iterator.  Use a WeakVH to hold onto it in case this
01369       // happens.
01370       WeakVH IterHandle(CurInstIterator);
01371 
01372       replaceAndRecursivelySimplify(CI, RetVal,
01373                                     TLInfo, nullptr);
01374 
01375       // If the iterator instruction was recursively deleted, start over at the
01376       // start of the block.
01377       if (IterHandle != CurInstIterator) {
01378         CurInstIterator = BB->begin();
01379         SunkAddrs.clear();
01380       }
01381       return true;
01382     }
01383     case Intrinsic::masked_load: {
01384       // Scalarize unsupported vector masked load
01385       if (!TTI->isLegalMaskedLoad(CI->getType(), 1)) {
01386         ScalarizeMaskedLoad(CI);
01387         ModifiedDT = true;
01388         return true;
01389       }
01390       return false;
01391     }
01392     case Intrinsic::masked_store: {
01393       if (!TTI->isLegalMaskedStore(CI->getArgOperand(0)->getType(), 1)) {
01394         ScalarizeMaskedStore(CI);
01395         ModifiedDT = true;
01396         return true;
01397       }
01398       return false;
01399     }
01400     case Intrinsic::aarch64_stlxr:
01401     case Intrinsic::aarch64_stxr: {
01402       ZExtInst *ExtVal = dyn_cast<ZExtInst>(CI->getArgOperand(0));
01403       if (!ExtVal || !ExtVal->hasOneUse() ||
01404           ExtVal->getParent() == CI->getParent())
01405         return false;
01406       // Sink a zext feeding stlxr/stxr before it, so it can be folded into it.
01407       ExtVal->moveBefore(CI);
01408       return true;
01409     }
01410     }
01411 
01412     if (TLI) {
01413       SmallVector<Value*, 2> PtrOps;
01414       Type *AccessTy;
01415       if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy))
01416         while (!PtrOps.empty())
01417           if (OptimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy))
01418             return true;
01419     }
01420   }
01421 
01422   // From here on out we're working with named functions.
01423   if (!CI->getCalledFunction()) return false;
01424 
01425   // Lower all default uses of _chk calls.  This is very similar
01426   // to what InstCombineCalls does, but here we are only lowering calls
01427   // to fortified library functions (e.g. __memcpy_chk) that have the default
01428   // "don't know" as the objectsize.  Anything else should be left alone.
01429   FortifiedLibCallSimplifier Simplifier(TLInfo, true);
01430   if (Value *V = Simplifier.optimizeCall(CI)) {
01431     CI->replaceAllUsesWith(V);
01432     CI->eraseFromParent();
01433     return true;
01434   }
01435   return false;
01436 }
01437 
01438 /// DupRetToEnableTailCallOpts - Look for opportunities to duplicate return
01439 /// instructions to the predecessor to enable tail call optimizations. The
01440 /// case it is currently looking for is:
01441 /// @code
01442 /// bb0:
01443 ///   %tmp0 = tail call i32 @f0()
01444 ///   br label %return
01445 /// bb1:
01446 ///   %tmp1 = tail call i32 @f1()
01447 ///   br label %return
01448 /// bb2:
01449 ///   %tmp2 = tail call i32 @f2()
01450 ///   br label %return
01451 /// return:
01452 ///   %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ]
01453 ///   ret i32 %retval
01454 /// @endcode
01455 ///
01456 /// =>
01457 ///
01458 /// @code
01459 /// bb0:
01460 ///   %tmp0 = tail call i32 @f0()
01461 ///   ret i32 %tmp0
01462 /// bb1:
01463 ///   %tmp1 = tail call i32 @f1()
01464 ///   ret i32 %tmp1
01465 /// bb2:
01466 ///   %tmp2 = tail call i32 @f2()
01467 ///   ret i32 %tmp2
01468 /// @endcode
01469 bool CodeGenPrepare::DupRetToEnableTailCallOpts(BasicBlock *BB) {
01470   if (!TLI)
01471     return false;
01472 
01473   ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator());
01474   if (!RI)
01475     return false;
01476 
01477   PHINode *PN = nullptr;
01478   BitCastInst *BCI = nullptr;
01479   Value *V = RI->getReturnValue();
01480   if (V) {
01481     BCI = dyn_cast<BitCastInst>(V);
01482     if (BCI)
01483       V = BCI->getOperand(0);
01484 
01485     PN = dyn_cast<PHINode>(V);
01486     if (!PN)
01487       return false;
01488   }
01489 
01490   if (PN && PN->getParent() != BB)
01491     return false;
01492 
01493   // It's not safe to eliminate the sign / zero extension of the return value.
01494   // See llvm::isInTailCallPosition().
01495   const Function *F = BB->getParent();
01496   AttributeSet CallerAttrs = F->getAttributes();
01497   if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) ||
01498       CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt))
01499     return false;
01500 
01501   // Make sure there are no instructions between the PHI and return, or that the
01502   // return is the first instruction in the block.
01503   if (PN) {
01504     BasicBlock::iterator BI = BB->begin();
01505     do { ++BI; } while (isa<DbgInfoIntrinsic>(BI));
01506     if (&*BI == BCI)
01507       // Also skip over the bitcast.
01508       ++BI;
01509     if (&*BI != RI)
01510       return false;
01511   } else {
01512     BasicBlock::iterator BI = BB->begin();
01513     while (isa<DbgInfoIntrinsic>(BI)) ++BI;
01514     if (&*BI != RI)
01515       return false;
01516   }
01517 
01518   /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail
01519   /// call.
01520   SmallVector<CallInst*, 4> TailCalls;
01521   if (PN) {
01522     for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
01523       CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I));
01524       // Make sure the phi value is indeed produced by the tail call.
01525       if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) &&
01526           TLI->mayBeEmittedAsTailCall(CI))
01527         TailCalls.push_back(CI);
01528     }
01529   } else {
01530     SmallPtrSet<BasicBlock*, 4> VisitedBBs;
01531     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
01532       if (!VisitedBBs.insert(*PI).second)
01533         continue;
01534 
01535       BasicBlock::InstListType &InstList = (*PI)->getInstList();
01536       BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin();
01537       BasicBlock::InstListType::reverse_iterator RE = InstList.rend();
01538       do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI));
01539       if (RI == RE)
01540         continue;
01541 
01542       CallInst *CI = dyn_cast<CallInst>(&*RI);
01543       if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI))
01544         TailCalls.push_back(CI);
01545     }
01546   }
01547 
01548   bool Changed = false;
01549   for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) {
01550     CallInst *CI = TailCalls[i];
01551     CallSite CS(CI);
01552 
01553     // Conservatively require the attributes of the call to match those of the
01554     // return. Ignore noalias because it doesn't affect the call sequence.
01555     AttributeSet CalleeAttrs = CS.getAttributes();
01556     if (AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
01557           removeAttribute(Attribute::NoAlias) !=
01558         AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
01559           removeAttribute(Attribute::NoAlias))
01560       continue;
01561 
01562     // Make sure the call instruction is followed by an unconditional branch to
01563     // the return block.
01564     BasicBlock *CallBB = CI->getParent();
01565     BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator());
01566     if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
01567       continue;
01568 
01569     // Duplicate the return into CallBB.
01570     (void)FoldReturnIntoUncondBranch(RI, BB, CallBB);
01571     ModifiedDT = Changed = true;
01572     ++NumRetsDup;
01573   }
01574 
01575   // If we eliminated all predecessors of the block, delete the block now.
01576   if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
01577     BB->eraseFromParent();
01578 
01579   return Changed;
01580 }
01581 
01582 //===----------------------------------------------------------------------===//
01583 // Memory Optimization
01584 //===----------------------------------------------------------------------===//
01585 
01586 namespace {
01587 
01588 /// ExtAddrMode - This is an extended version of TargetLowering::AddrMode
01589 /// which holds actual Value*'s for register values.
01590 struct ExtAddrMode : public TargetLowering::AddrMode {
01591   Value *BaseReg;
01592   Value *ScaledReg;
01593   ExtAddrMode() : BaseReg(nullptr), ScaledReg(nullptr) {}
01594   void print(raw_ostream &OS) const;
01595   void dump() const;
01596 
01597   bool operator==(const ExtAddrMode& O) const {
01598     return (BaseReg == O.BaseReg) && (ScaledReg == O.ScaledReg) &&
01599            (BaseGV == O.BaseGV) && (BaseOffs == O.BaseOffs) &&
01600            (HasBaseReg == O.HasBaseReg) && (Scale == O.Scale);
01601   }
01602 };
01603 
01604 #ifndef NDEBUG
01605 static inline raw_ostream &operator<<(raw_ostream &OS, const ExtAddrMode &AM) {
01606   AM.print(OS);
01607   return OS;
01608 }
01609 #endif
01610 
01611 void ExtAddrMode::print(raw_ostream &OS) const {
01612   bool NeedPlus = false;
01613   OS << "[";
01614   if (BaseGV) {
01615     OS << (NeedPlus ? " + " : "")
01616        << "GV:";
01617     BaseGV->printAsOperand(OS, /*PrintType=*/false);
01618     NeedPlus = true;
01619   }
01620 
01621   if (BaseOffs) {
01622     OS << (NeedPlus ? " + " : "")
01623        << BaseOffs;
01624     NeedPlus = true;
01625   }
01626 
01627   if (BaseReg) {
01628     OS << (NeedPlus ? " + " : "")
01629        << "Base:";
01630     BaseReg->printAsOperand(OS, /*PrintType=*/false);
01631     NeedPlus = true;
01632   }
01633   if (Scale) {
01634     OS << (NeedPlus ? " + " : "")
01635        << Scale << "*";
01636     ScaledReg->printAsOperand(OS, /*PrintType=*/false);
01637   }
01638 
01639   OS << ']';
01640 }
01641 
01642 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
01643 void ExtAddrMode::dump() const {
01644   print(dbgs());
01645   dbgs() << '\n';
01646 }
01647 #endif
01648 
01649 /// \brief This class provides transaction based operation on the IR.
01650 /// Every change made through this class is recorded in the internal state and
01651 /// can be undone (rollback) until commit is called.
01652 class TypePromotionTransaction {
01653 
01654   /// \brief This represents the common interface of the individual transaction.
01655   /// Each class implements the logic for doing one specific modification on
01656   /// the IR via the TypePromotionTransaction.
01657   class TypePromotionAction {
01658   protected:
01659     /// The Instruction modified.
01660     Instruction *Inst;
01661 
01662   public:
01663     /// \brief Constructor of the action.
01664     /// The constructor performs the related action on the IR.
01665     TypePromotionAction(Instruction *Inst) : Inst(Inst) {}
01666 
01667     virtual ~TypePromotionAction() {}
01668 
01669     /// \brief Undo the modification done by this action.
01670     /// When this method is called, the IR must be in the same state as it was
01671     /// before this action was applied.
01672     /// \pre Undoing the action works if and only if the IR is in the exact same
01673     /// state as it was directly after this action was applied.
01674     virtual void undo() = 0;
01675 
01676     /// \brief Advocate every change made by this action.
01677     /// When the results on the IR of the action are to be kept, it is important
01678     /// to call this function, otherwise hidden information may be kept forever.
01679     virtual void commit() {
01680       // Nothing to be done, this action is not doing anything.
01681     }
01682   };
01683 
01684   /// \brief Utility to remember the position of an instruction.
01685   class InsertionHandler {
01686     /// Position of an instruction.
01687     /// Either an instruction:
01688     /// - Is the first in a basic block: BB is used.
01689     /// - Has a previous instructon: PrevInst is used.
01690     union {
01691       Instruction *PrevInst;
01692       BasicBlock *BB;
01693     } Point;
01694     /// Remember whether or not the instruction had a previous instruction.
01695     bool HasPrevInstruction;
01696 
01697   public:
01698     /// \brief Record the position of \p Inst.
01699     InsertionHandler(Instruction *Inst) {
01700       BasicBlock::iterator It = Inst;
01701       HasPrevInstruction = (It != (Inst->getParent()->begin()));
01702       if (HasPrevInstruction)
01703         Point.PrevInst = --It;
01704       else
01705         Point.BB = Inst->getParent();
01706     }
01707 
01708     /// \brief Insert \p Inst at the recorded position.
01709     void insert(Instruction *Inst) {
01710       if (HasPrevInstruction) {
01711         if (Inst->getParent())
01712           Inst->removeFromParent();
01713         Inst->insertAfter(Point.PrevInst);
01714       } else {
01715         Instruction *Position = Point.BB->getFirstInsertionPt();
01716         if (Inst->getParent())
01717           Inst->moveBefore(Position);
01718         else
01719           Inst->insertBefore(Position);
01720       }
01721     }
01722   };
01723 
01724   /// \brief Move an instruction before another.
01725   class InstructionMoveBefore : public TypePromotionAction {
01726     /// Original position of the instruction.
01727     InsertionHandler Position;
01728 
01729   public:
01730     /// \brief Move \p Inst before \p Before.
01731     InstructionMoveBefore(Instruction *Inst, Instruction *Before)
01732         : TypePromotionAction(Inst), Position(Inst) {
01733       DEBUG(dbgs() << "Do: move: " << *Inst << "\nbefore: " << *Before << "\n");
01734       Inst->moveBefore(Before);
01735     }
01736 
01737     /// \brief Move the instruction back to its original position.
01738     void undo() override {
01739       DEBUG(dbgs() << "Undo: moveBefore: " << *Inst << "\n");
01740       Position.insert(Inst);
01741     }
01742   };
01743 
01744   /// \brief Set the operand of an instruction with a new value.
01745   class OperandSetter : public TypePromotionAction {
01746     /// Original operand of the instruction.
01747     Value *Origin;
01748     /// Index of the modified instruction.
01749     unsigned Idx;
01750 
01751   public:
01752     /// \brief Set \p Idx operand of \p Inst with \p NewVal.
01753     OperandSetter(Instruction *Inst, unsigned Idx, Value *NewVal)
01754         : TypePromotionAction(Inst), Idx(Idx) {
01755       DEBUG(dbgs() << "Do: setOperand: " << Idx << "\n"
01756                    << "for:" << *Inst << "\n"
01757                    << "with:" << *NewVal << "\n");
01758       Origin = Inst->getOperand(Idx);
01759       Inst->setOperand(Idx, NewVal);
01760     }
01761 
01762     /// \brief Restore the original value of the instruction.
01763     void undo() override {
01764       DEBUG(dbgs() << "Undo: setOperand:" << Idx << "\n"
01765                    << "for: " << *Inst << "\n"
01766                    << "with: " << *Origin << "\n");
01767       Inst->setOperand(Idx, Origin);
01768     }
01769   };
01770 
01771   /// \brief Hide the operands of an instruction.
01772   /// Do as if this instruction was not using any of its operands.
01773   class OperandsHider : public TypePromotionAction {
01774     /// The list of original operands.
01775     SmallVector<Value *, 4> OriginalValues;
01776 
01777   public:
01778     /// \brief Remove \p Inst from the uses of the operands of \p Inst.
01779     OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) {
01780       DEBUG(dbgs() << "Do: OperandsHider: " << *Inst << "\n");
01781       unsigned NumOpnds = Inst->getNumOperands();
01782       OriginalValues.reserve(NumOpnds);
01783       for (unsigned It = 0; It < NumOpnds; ++It) {
01784         // Save the current operand.
01785         Value *Val = Inst->getOperand(It);
01786         OriginalValues.push_back(Val);
01787         // Set a dummy one.
01788         // We could use OperandSetter here, but that would implied an overhead
01789         // that we are not willing to pay.
01790         Inst->setOperand(It, UndefValue::get(Val->getType()));
01791       }
01792     }
01793 
01794     /// \brief Restore the original list of uses.
01795     void undo() override {
01796       DEBUG(dbgs() << "Undo: OperandsHider: " << *Inst << "\n");
01797       for (unsigned It = 0, EndIt = OriginalValues.size(); It != EndIt; ++It)
01798         Inst->setOperand(It, OriginalValues[It]);
01799     }
01800   };
01801 
01802   /// \brief Build a truncate instruction.
01803   class TruncBuilder : public TypePromotionAction {
01804     Value *Val;
01805   public:
01806     /// \brief Build a truncate instruction of \p Opnd producing a \p Ty
01807     /// result.
01808     /// trunc Opnd to Ty.
01809     TruncBuilder(Instruction *Opnd, Type *Ty) : TypePromotionAction(Opnd) {
01810       IRBuilder<> Builder(Opnd);
01811       Val = Builder.CreateTrunc(Opnd, Ty, "promoted");
01812       DEBUG(dbgs() << "Do: TruncBuilder: " << *Val << "\n");
01813     }
01814 
01815     /// \brief Get the built value.
01816     Value *getBuiltValue() { return Val; }
01817 
01818     /// \brief Remove the built instruction.
01819     void undo() override {
01820       DEBUG(dbgs() << "Undo: TruncBuilder: " << *Val << "\n");
01821       if (Instruction *IVal = dyn_cast<Instruction>(Val))
01822         IVal->eraseFromParent();
01823     }
01824   };
01825 
01826   /// \brief Build a sign extension instruction.
01827   class SExtBuilder : public TypePromotionAction {
01828     Value *Val;
01829   public:
01830     /// \brief Build a sign extension instruction of \p Opnd producing a \p Ty
01831     /// result.
01832     /// sext Opnd to Ty.
01833     SExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
01834         : TypePromotionAction(InsertPt) {
01835       IRBuilder<> Builder(InsertPt);
01836       Val = Builder.CreateSExt(Opnd, Ty, "promoted");
01837       DEBUG(dbgs() << "Do: SExtBuilder: " << *Val << "\n");
01838     }
01839 
01840     /// \brief Get the built value.
01841     Value *getBuiltValue() { return Val; }
01842 
01843     /// \brief Remove the built instruction.
01844     void undo() override {
01845       DEBUG(dbgs() << "Undo: SExtBuilder: " << *Val << "\n");
01846       if (Instruction *IVal = dyn_cast<Instruction>(Val))
01847         IVal->eraseFromParent();
01848     }
01849   };
01850 
01851   /// \brief Build a zero extension instruction.
01852   class ZExtBuilder : public TypePromotionAction {
01853     Value *Val;
01854   public:
01855     /// \brief Build a zero extension instruction of \p Opnd producing a \p Ty
01856     /// result.
01857     /// zext Opnd to Ty.
01858     ZExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
01859         : TypePromotionAction(InsertPt) {
01860       IRBuilder<> Builder(InsertPt);
01861       Val = Builder.CreateZExt(Opnd, Ty, "promoted");
01862       DEBUG(dbgs() << "Do: ZExtBuilder: " << *Val << "\n");
01863     }
01864 
01865     /// \brief Get the built value.
01866     Value *getBuiltValue() { return Val; }
01867 
01868     /// \brief Remove the built instruction.
01869     void undo() override {
01870       DEBUG(dbgs() << "Undo: ZExtBuilder: " << *Val << "\n");
01871       if (Instruction *IVal = dyn_cast<Instruction>(Val))
01872         IVal->eraseFromParent();
01873     }
01874   };
01875 
01876   /// \brief Mutate an instruction to another type.
01877   class TypeMutator : public TypePromotionAction {
01878     /// Record the original type.
01879     Type *OrigTy;
01880 
01881   public:
01882     /// \brief Mutate the type of \p Inst into \p NewTy.
01883     TypeMutator(Instruction *Inst, Type *NewTy)
01884         : TypePromotionAction(Inst), OrigTy(Inst->getType()) {
01885       DEBUG(dbgs() << "Do: MutateType: " << *Inst << " with " << *NewTy
01886                    << "\n");
01887       Inst->mutateType(NewTy);
01888     }
01889 
01890     /// \brief Mutate the instruction back to its original type.
01891     void undo() override {
01892       DEBUG(dbgs() << "Undo: MutateType: " << *Inst << " with " << *OrigTy
01893                    << "\n");
01894       Inst->mutateType(OrigTy);
01895     }
01896   };
01897 
01898   /// \brief Replace the uses of an instruction by another instruction.
01899   class UsesReplacer : public TypePromotionAction {
01900     /// Helper structure to keep track of the replaced uses.
01901     struct InstructionAndIdx {
01902       /// The instruction using the instruction.
01903       Instruction *Inst;
01904       /// The index where this instruction is used for Inst.
01905       unsigned Idx;
01906       InstructionAndIdx(Instruction *Inst, unsigned Idx)
01907           : Inst(Inst), Idx(Idx) {}
01908     };
01909 
01910     /// Keep track of the original uses (pair Instruction, Index).
01911     SmallVector<InstructionAndIdx, 4> OriginalUses;
01912     typedef SmallVectorImpl<InstructionAndIdx>::iterator use_iterator;
01913 
01914   public:
01915     /// \brief Replace all the use of \p Inst by \p New.
01916     UsesReplacer(Instruction *Inst, Value *New) : TypePromotionAction(Inst) {
01917       DEBUG(dbgs() << "Do: UsersReplacer: " << *Inst << " with " << *New
01918                    << "\n");
01919       // Record the original uses.
01920       for (Use &U : Inst->uses()) {
01921         Instruction *UserI = cast<Instruction>(U.getUser());
01922         OriginalUses.push_back(InstructionAndIdx(UserI, U.getOperandNo()));
01923       }
01924       // Now, we can replace the uses.
01925       Inst->replaceAllUsesWith(New);
01926     }
01927 
01928     /// \brief Reassign the original uses of Inst to Inst.
01929     void undo() override {
01930       DEBUG(dbgs() << "Undo: UsersReplacer: " << *Inst << "\n");
01931       for (use_iterator UseIt = OriginalUses.begin(),
01932                         EndIt = OriginalUses.end();
01933            UseIt != EndIt; ++UseIt) {
01934         UseIt->Inst->setOperand(UseIt->Idx, Inst);
01935       }
01936     }
01937   };
01938 
01939   /// \brief Remove an instruction from the IR.
01940   class InstructionRemover : public TypePromotionAction {
01941     /// Original position of the instruction.
01942     InsertionHandler Inserter;
01943     /// Helper structure to hide all the link to the instruction. In other
01944     /// words, this helps to do as if the instruction was removed.
01945     OperandsHider Hider;
01946     /// Keep track of the uses replaced, if any.
01947     UsesReplacer *Replacer;
01948 
01949   public:
01950     /// \brief Remove all reference of \p Inst and optinally replace all its
01951     /// uses with New.
01952     /// \pre If !Inst->use_empty(), then New != nullptr
01953     InstructionRemover(Instruction *Inst, Value *New = nullptr)
01954         : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
01955           Replacer(nullptr) {
01956       if (New)
01957         Replacer = new UsesReplacer(Inst, New);
01958       DEBUG(dbgs() << "Do: InstructionRemover: " << *Inst << "\n");
01959       Inst->removeFromParent();
01960     }
01961 
01962     ~InstructionRemover() override { delete Replacer; }
01963 
01964     /// \brief Really remove the instruction.
01965     void commit() override { delete Inst; }
01966 
01967     /// \brief Resurrect the instruction and reassign it to the proper uses if
01968     /// new value was provided when build this action.
01969     void undo() override {
01970       DEBUG(dbgs() << "Undo: InstructionRemover: " << *Inst << "\n");
01971       Inserter.insert(Inst);
01972       if (Replacer)
01973         Replacer->undo();
01974       Hider.undo();
01975     }
01976   };
01977 
01978 public:
01979   /// Restoration point.
01980   /// The restoration point is a pointer to an action instead of an iterator
01981   /// because the iterator may be invalidated but not the pointer.
01982   typedef const TypePromotionAction *ConstRestorationPt;
01983   /// Advocate every changes made in that transaction.
01984   void commit();
01985   /// Undo all the changes made after the given point.
01986   void rollback(ConstRestorationPt Point);
01987   /// Get the current restoration point.
01988   ConstRestorationPt getRestorationPoint() const;
01989 
01990   /// \name API for IR modification with state keeping to support rollback.
01991   /// @{
01992   /// Same as Instruction::setOperand.
01993   void setOperand(Instruction *Inst, unsigned Idx, Value *NewVal);
01994   /// Same as Instruction::eraseFromParent.
01995   void eraseInstruction(Instruction *Inst, Value *NewVal = nullptr);
01996   /// Same as Value::replaceAllUsesWith.
01997   void replaceAllUsesWith(Instruction *Inst, Value *New);
01998   /// Same as Value::mutateType.
01999   void mutateType(Instruction *Inst, Type *NewTy);
02000   /// Same as IRBuilder::createTrunc.
02001   Value *createTrunc(Instruction *Opnd, Type *Ty);
02002   /// Same as IRBuilder::createSExt.
02003   Value *createSExt(Instruction *Inst, Value *Opnd, Type *Ty);
02004   /// Same as IRBuilder::createZExt.
02005   Value *createZExt(Instruction *Inst, Value *Opnd, Type *Ty);
02006   /// Same as Instruction::moveBefore.
02007   void moveBefore(Instruction *Inst, Instruction *Before);
02008   /// @}
02009 
02010 private:
02011   /// The ordered list of actions made so far.
02012   SmallVector<std::unique_ptr<TypePromotionAction>, 16> Actions;
02013   typedef SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator CommitPt;
02014 };
02015 
02016 void TypePromotionTransaction::setOperand(Instruction *Inst, unsigned Idx,
02017                                           Value *NewVal) {
02018   Actions.push_back(
02019       make_unique<TypePromotionTransaction::OperandSetter>(Inst, Idx, NewVal));
02020 }
02021 
02022 void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
02023                                                 Value *NewVal) {
02024   Actions.push_back(
02025       make_unique<TypePromotionTransaction::InstructionRemover>(Inst, NewVal));
02026 }
02027 
02028 void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
02029                                                   Value *New) {
02030   Actions.push_back(make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
02031 }
02032 
02033 void TypePromotionTransaction::mutateType(Instruction *Inst, Type *NewTy) {
02034   Actions.push_back(make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
02035 }
02036 
02037 Value *TypePromotionTransaction::createTrunc(Instruction *Opnd,
02038                                              Type *Ty) {
02039   std::unique_ptr<TruncBuilder> Ptr(new TruncBuilder(Opnd, Ty));
02040   Value *Val = Ptr->getBuiltValue();
02041   Actions.push_back(std::move(Ptr));
02042   return Val;
02043 }
02044 
02045 Value *TypePromotionTransaction::createSExt(Instruction *Inst,
02046                                             Value *Opnd, Type *Ty) {
02047   std::unique_ptr<SExtBuilder> Ptr(new SExtBuilder(Inst, Opnd, Ty));
02048   Value *Val = Ptr->getBuiltValue();
02049   Actions.push_back(std::move(Ptr));
02050   return Val;
02051 }
02052 
02053 Value *TypePromotionTransaction::createZExt(Instruction *Inst,
02054                                             Value *Opnd, Type *Ty) {
02055   std::unique_ptr<ZExtBuilder> Ptr(new ZExtBuilder(Inst, Opnd, Ty));
02056   Value *Val = Ptr->getBuiltValue();
02057   Actions.push_back(std::move(Ptr));
02058   return Val;
02059 }
02060 
02061 void TypePromotionTransaction::moveBefore(Instruction *Inst,
02062                                           Instruction *Before) {
02063   Actions.push_back(
02064       make_unique<TypePromotionTransaction::InstructionMoveBefore>(Inst, Before));
02065 }
02066 
02067 TypePromotionTransaction::ConstRestorationPt
02068 TypePromotionTransaction::getRestorationPoint() const {
02069   return !Actions.empty() ? Actions.back().get() : nullptr;
02070 }
02071 
02072 void TypePromotionTransaction::commit() {
02073   for (CommitPt It = Actions.begin(), EndIt = Actions.end(); It != EndIt;
02074        ++It)
02075     (*It)->commit();
02076   Actions.clear();
02077 }
02078 
02079 void TypePromotionTransaction::rollback(
02080     TypePromotionTransaction::ConstRestorationPt Point) {
02081   while (!Actions.empty() && Point != Actions.back().get()) {
02082     std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
02083     Curr->undo();
02084   }
02085 }
02086 
02087 /// \brief A helper class for matching addressing modes.
02088 ///
02089 /// This encapsulates the logic for matching the target-legal addressing modes.
02090 class AddressingModeMatcher {
02091   SmallVectorImpl<Instruction*> &AddrModeInsts;
02092   const TargetMachine &TM;
02093   const TargetLowering &TLI;
02094 
02095   /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and
02096   /// the memory instruction that we're computing this address for.
02097   Type *AccessTy;
02098   Instruction *MemoryInst;
02099 
02100   /// AddrMode - This is the addressing mode that we're building up.  This is
02101   /// part of the return value of this addressing mode matching stuff.
02102   ExtAddrMode &AddrMode;
02103 
02104   /// The truncate instruction inserted by other CodeGenPrepare optimizations.
02105   const SetOfInstrs &InsertedTruncs;
02106   /// A map from the instructions to their type before promotion.
02107   InstrToOrigTy &PromotedInsts;
02108   /// The ongoing transaction where every action should be registered.
02109   TypePromotionTransaction &TPT;
02110 
02111   /// IgnoreProfitability - This is set to true when we should not do
02112   /// profitability checks.  When true, IsProfitableToFoldIntoAddressingMode
02113   /// always returns true.
02114   bool IgnoreProfitability;
02115 
02116   AddressingModeMatcher(SmallVectorImpl<Instruction *> &AMI,
02117                         const TargetMachine &TM, Type *AT, Instruction *MI,
02118                         ExtAddrMode &AM, const SetOfInstrs &InsertedTruncs,
02119                         InstrToOrigTy &PromotedInsts,
02120                         TypePromotionTransaction &TPT)
02121       : AddrModeInsts(AMI), TM(TM),
02122         TLI(*TM.getSubtargetImpl(*MI->getParent()->getParent())
02123                  ->getTargetLowering()),
02124         AccessTy(AT), MemoryInst(MI), AddrMode(AM),
02125         InsertedTruncs(InsertedTruncs), PromotedInsts(PromotedInsts), TPT(TPT) {
02126     IgnoreProfitability = false;
02127   }
02128 public:
02129 
02130   /// Match - Find the maximal addressing mode that a load/store of V can fold,
02131   /// give an access type of AccessTy.  This returns a list of involved
02132   /// instructions in AddrModeInsts.
02133   /// \p InsertedTruncs The truncate instruction inserted by other
02134   /// CodeGenPrepare
02135   /// optimizations.
02136   /// \p PromotedInsts maps the instructions to their type before promotion.
02137   /// \p The ongoing transaction where every action should be registered.
02138   static ExtAddrMode Match(Value *V, Type *AccessTy,
02139                            Instruction *MemoryInst,
02140                            SmallVectorImpl<Instruction*> &AddrModeInsts,
02141                            const TargetMachine &TM,
02142                            const SetOfInstrs &InsertedTruncs,
02143                            InstrToOrigTy &PromotedInsts,
02144                            TypePromotionTransaction &TPT) {
02145     ExtAddrMode Result;
02146 
02147     bool Success = AddressingModeMatcher(AddrModeInsts, TM, AccessTy,
02148                                          MemoryInst, Result, InsertedTruncs,
02149                                          PromotedInsts, TPT).MatchAddr(V, 0);
02150     (void)Success; assert(Success && "Couldn't select *anything*?");
02151     return Result;
02152   }
02153 private:
02154   bool MatchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth);
02155   bool MatchAddr(Value *V, unsigned Depth);
02156   bool MatchOperationAddr(User *Operation, unsigned Opcode, unsigned Depth,
02157                           bool *MovedAway = nullptr);
02158   bool IsProfitableToFoldIntoAddressingMode(Instruction *I,
02159                                             ExtAddrMode &AMBefore,
02160                                             ExtAddrMode &AMAfter);
02161   bool ValueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
02162   bool IsPromotionProfitable(unsigned NewCost, unsigned OldCost,
02163                              Value *PromotedOperand) const;
02164 };
02165 
02166 /// MatchScaledValue - Try adding ScaleReg*Scale to the current addressing mode.
02167 /// Return true and update AddrMode if this addr mode is legal for the target,
02168 /// false if not.
02169 bool AddressingModeMatcher::MatchScaledValue(Value *ScaleReg, int64_t Scale,
02170                                              unsigned Depth) {
02171   // If Scale is 1, then this is the same as adding ScaleReg to the addressing
02172   // mode.  Just process that directly.
02173   if (Scale == 1)
02174     return MatchAddr(ScaleReg, Depth);
02175 
02176   // If the scale is 0, it takes nothing to add this.
02177   if (Scale == 0)
02178     return true;
02179 
02180   // If we already have a scale of this value, we can add to it, otherwise, we
02181   // need an available scale field.
02182   if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg)
02183     return false;
02184 
02185   ExtAddrMode TestAddrMode = AddrMode;
02186 
02187   // Add scale to turn X*4+X*3 -> X*7.  This could also do things like
02188   // [A+B + A*7] -> [B+A*8].
02189   TestAddrMode.Scale += Scale;
02190   TestAddrMode.ScaledReg = ScaleReg;
02191 
02192   // If the new address isn't legal, bail out.
02193   if (!TLI.isLegalAddressingMode(TestAddrMode, AccessTy))
02194     return false;
02195 
02196   // It was legal, so commit it.
02197   AddrMode = TestAddrMode;
02198 
02199   // Okay, we decided that we can add ScaleReg+Scale to AddrMode.  Check now
02200   // to see if ScaleReg is actually X+C.  If so, we can turn this into adding
02201   // X*Scale + C*Scale to addr mode.
02202   ConstantInt *CI = nullptr; Value *AddLHS = nullptr;
02203   if (isa<Instruction>(ScaleReg) &&  // not a constant expr.
02204       match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) {
02205     TestAddrMode.ScaledReg = AddLHS;
02206     TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale;
02207 
02208     // If this addressing mode is legal, commit it and remember that we folded
02209     // this instruction.
02210     if (TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) {
02211       AddrModeInsts.push_back(cast<Instruction>(ScaleReg));
02212       AddrMode = TestAddrMode;
02213       return true;
02214     }
02215   }
02216 
02217   // Otherwise, not (x+c)*scale, just return what we have.
02218   return true;
02219 }
02220 
02221 /// MightBeFoldableInst - This is a little filter, which returns true if an
02222 /// addressing computation involving I might be folded into a load/store
02223 /// accessing it.  This doesn't need to be perfect, but needs to accept at least
02224 /// the set of instructions that MatchOperationAddr can.
02225 static bool MightBeFoldableInst(Instruction *I) {
02226   switch (I->getOpcode()) {
02227   case Instruction::BitCast:
02228   case Instruction::AddrSpaceCast:
02229     // Don't touch identity bitcasts.
02230     if (I->getType() == I->getOperand(0)->getType())
02231       return false;
02232     return I->getType()->isPointerTy() || I->getType()->isIntegerTy();
02233   case Instruction::PtrToInt:
02234     // PtrToInt is always a noop, as we know that the int type is pointer sized.
02235     return true;
02236   case Instruction::IntToPtr:
02237     // We know the input is intptr_t, so this is foldable.
02238     return true;
02239   case Instruction::Add:
02240     return true;
02241   case Instruction::Mul:
02242   case Instruction::Shl:
02243     // Can only handle X*C and X << C.
02244     return isa<ConstantInt>(I->getOperand(1));
02245   case Instruction::GetElementPtr:
02246     return true;
02247   default:
02248     return false;
02249   }
02250 }
02251 
02252 /// \brief Check whether or not \p Val is a legal instruction for \p TLI.
02253 /// \note \p Val is assumed to be the product of some type promotion.
02254 /// Therefore if \p Val has an undefined state in \p TLI, this is assumed
02255 /// to be legal, as the non-promoted value would have had the same state.
02256 static bool isPromotedInstructionLegal(const TargetLowering &TLI, Value *Val) {
02257   Instruction *PromotedInst = dyn_cast<Instruction>(Val);
02258   if (!PromotedInst)
02259     return false;
02260   int ISDOpcode = TLI.InstructionOpcodeToISD(PromotedInst->getOpcode());
02261   // If the ISDOpcode is undefined, it was undefined before the promotion.
02262   if (!ISDOpcode)
02263     return true;
02264   // Otherwise, check if the promoted instruction is legal or not.
02265   return TLI.isOperationLegalOrCustom(
02266       ISDOpcode, TLI.getValueType(PromotedInst->getType()));
02267 }
02268 
02269 /// \brief Hepler class to perform type promotion.
02270 class TypePromotionHelper {
02271   /// \brief Utility function to check whether or not a sign or zero extension
02272   /// of \p Inst with \p ConsideredExtType can be moved through \p Inst by
02273   /// either using the operands of \p Inst or promoting \p Inst.
02274   /// The type of the extension is defined by \p IsSExt.
02275   /// In other words, check if:
02276   /// ext (Ty Inst opnd1 opnd2 ... opndN) to ConsideredExtType.
02277   /// #1 Promotion applies:
02278   /// ConsideredExtType Inst (ext opnd1 to ConsideredExtType, ...).
02279   /// #2 Operand reuses:
02280   /// ext opnd1 to ConsideredExtType.
02281   /// \p PromotedInsts maps the instructions to their type before promotion.
02282   static bool canGetThrough(const Instruction *Inst, Type *ConsideredExtType,
02283                             const InstrToOrigTy &PromotedInsts, bool IsSExt);
02284 
02285   /// \brief Utility function to determine if \p OpIdx should be promoted when
02286   /// promoting \p Inst.
02287   static bool shouldExtOperand(const Instruction *Inst, int OpIdx) {
02288     if (isa<SelectInst>(Inst) && OpIdx == 0)
02289       return false;
02290     return true;
02291   }
02292 
02293   /// \brief Utility function to promote the operand of \p Ext when this
02294   /// operand is a promotable trunc or sext or zext.
02295   /// \p PromotedInsts maps the instructions to their type before promotion.
02296   /// \p CreatedInstsCost[out] contains the cost of all instructions
02297   /// created to promote the operand of Ext.
02298   /// Newly added extensions are inserted in \p Exts.
02299   /// Newly added truncates are inserted in \p Truncs.
02300   /// Should never be called directly.
02301   /// \return The promoted value which is used instead of Ext.
02302   static Value *promoteOperandForTruncAndAnyExt(
02303       Instruction *Ext, TypePromotionTransaction &TPT,
02304       InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
02305       SmallVectorImpl<Instruction *> *Exts,
02306       SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI);
02307 
02308   /// \brief Utility function to promote the operand of \p Ext when this
02309   /// operand is promotable and is not a supported trunc or sext.
02310   /// \p PromotedInsts maps the instructions to their type before promotion.
02311   /// \p CreatedInstsCost[out] contains the cost of all the instructions
02312   /// created to promote the operand of Ext.
02313   /// Newly added extensions are inserted in \p Exts.
02314   /// Newly added truncates are inserted in \p Truncs.
02315   /// Should never be called directly.
02316   /// \return The promoted value which is used instead of Ext.
02317   static Value *promoteOperandForOther(Instruction *Ext,
02318                                        TypePromotionTransaction &TPT,
02319                                        InstrToOrigTy &PromotedInsts,
02320                                        unsigned &CreatedInstsCost,
02321                                        SmallVectorImpl<Instruction *> *Exts,
02322                                        SmallVectorImpl<Instruction *> *Truncs,
02323                                        const TargetLowering &TLI, bool IsSExt);
02324 
02325   /// \see promoteOperandForOther.
02326   static Value *signExtendOperandForOther(
02327       Instruction *Ext, TypePromotionTransaction &TPT,
02328       InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
02329       SmallVectorImpl<Instruction *> *Exts,
02330       SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
02331     return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
02332                                   Exts, Truncs, TLI, true);
02333   }
02334 
02335   /// \see promoteOperandForOther.
02336   static Value *zeroExtendOperandForOther(
02337       Instruction *Ext, TypePromotionTransaction &TPT,
02338       InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
02339       SmallVectorImpl<Instruction *> *Exts,
02340       SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
02341     return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
02342                                   Exts, Truncs, TLI, false);
02343   }
02344 
02345 public:
02346   /// Type for the utility function that promotes the operand of Ext.
02347   typedef Value *(*Action)(Instruction *Ext, TypePromotionTransaction &TPT,
02348                            InstrToOrigTy &PromotedInsts,
02349                            unsigned &CreatedInstsCost,
02350                            SmallVectorImpl<Instruction *> *Exts,
02351                            SmallVectorImpl<Instruction *> *Truncs,
02352                            const TargetLowering &TLI);
02353   /// \brief Given a sign/zero extend instruction \p Ext, return the approriate
02354   /// action to promote the operand of \p Ext instead of using Ext.
02355   /// \return NULL if no promotable action is possible with the current
02356   /// sign extension.
02357   /// \p InsertedTruncs keeps track of all the truncate instructions inserted by
02358   /// the others CodeGenPrepare optimizations. This information is important
02359   /// because we do not want to promote these instructions as CodeGenPrepare
02360   /// will reinsert them later. Thus creating an infinite loop: create/remove.
02361   /// \p PromotedInsts maps the instructions to their type before promotion.
02362   static Action getAction(Instruction *Ext, const SetOfInstrs &InsertedTruncs,
02363                           const TargetLowering &TLI,
02364                           const InstrToOrigTy &PromotedInsts);
02365 };
02366 
02367 bool TypePromotionHelper::canGetThrough(const Instruction *Inst,
02368                                         Type *ConsideredExtType,
02369                                         const InstrToOrigTy &PromotedInsts,
02370                                         bool IsSExt) {
02371   // The promotion helper does not know how to deal with vector types yet.
02372   // To be able to fix that, we would need to fix the places where we
02373   // statically extend, e.g., constants and such.
02374   if (Inst->getType()->isVectorTy())
02375     return false;
02376 
02377   // We can always get through zext.
02378   if (isa<ZExtInst>(Inst))
02379     return true;
02380 
02381   // sext(sext) is ok too.
02382   if (IsSExt && isa<SExtInst>(Inst))
02383     return true;
02384 
02385   // We can get through binary operator, if it is legal. In other words, the
02386   // binary operator must have a nuw or nsw flag.
02387   const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
02388   if (BinOp && isa<OverflowingBinaryOperator>(BinOp) &&
02389       ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
02390        (IsSExt && BinOp->hasNoSignedWrap())))
02391     return true;
02392 
02393   // Check if we can do the following simplification.
02394   // ext(trunc(opnd)) --> ext(opnd)
02395   if (!isa<TruncInst>(Inst))
02396     return false;
02397 
02398   Value *OpndVal = Inst->getOperand(0);
02399   // Check if we can use this operand in the extension.
02400   // If the type is larger than the result type of the extension,
02401   // we cannot.
02402   if (!OpndVal->getType()->isIntegerTy() ||
02403       OpndVal->getType()->getIntegerBitWidth() >
02404           ConsideredExtType->getIntegerBitWidth())
02405     return false;
02406 
02407   // If the operand of the truncate is not an instruction, we will not have
02408   // any information on the dropped bits.
02409   // (Actually we could for constant but it is not worth the extra logic).
02410   Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
02411   if (!Opnd)
02412     return false;
02413 
02414   // Check if the source of the type is narrow enough.
02415   // I.e., check that trunc just drops extended bits of the same kind of
02416   // the extension.
02417   // #1 get the type of the operand and check the kind of the extended bits.
02418   const Type *OpndType;
02419   InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
02420   if (It != PromotedInsts.end() && It->second.IsSExt == IsSExt)
02421     OpndType = It->second.Ty;
02422   else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
02423     OpndType = Opnd->getOperand(0)->getType();
02424   else
02425     return false;
02426 
02427   // #2 check that the truncate just drop extended bits.
02428   if (Inst->getType()->getIntegerBitWidth() >= OpndType->getIntegerBitWidth())
02429     return true;
02430 
02431   return false;
02432 }
02433 
02434 TypePromotionHelper::Action TypePromotionHelper::getAction(
02435     Instruction *Ext, const SetOfInstrs &InsertedTruncs,
02436     const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts) {
02437   assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
02438          "Unexpected instruction type");
02439   Instruction *ExtOpnd = dyn_cast<Instruction>(Ext->getOperand(0));
02440   Type *ExtTy = Ext->getType();
02441   bool IsSExt = isa<SExtInst>(Ext);
02442   // If the operand of the extension is not an instruction, we cannot
02443   // get through.
02444   // If it, check we can get through.
02445   if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
02446     return nullptr;
02447 
02448   // Do not promote if the operand has been added by codegenprepare.
02449   // Otherwise, it means we are undoing an optimization that is likely to be
02450   // redone, thus causing potential infinite loop.
02451   if (isa<TruncInst>(ExtOpnd) && InsertedTruncs.count(ExtOpnd))
02452     return nullptr;
02453 
02454   // SExt or Trunc instructions.
02455   // Return the related handler.
02456   if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
02457       isa<ZExtInst>(ExtOpnd))
02458     return promoteOperandForTruncAndAnyExt;
02459 
02460   // Regular instruction.
02461   // Abort early if we will have to insert non-free instructions.
02462   if (!ExtOpnd->hasOneUse() && !TLI.isTruncateFree(ExtTy, ExtOpnd->getType()))
02463     return nullptr;
02464   return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
02465 }
02466 
02467 Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
02468     llvm::Instruction *SExt, TypePromotionTransaction &TPT,
02469     InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
02470     SmallVectorImpl<Instruction *> *Exts,
02471     SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
02472   // By construction, the operand of SExt is an instruction. Otherwise we cannot
02473   // get through it and this method should not be called.
02474   Instruction *SExtOpnd = cast<Instruction>(SExt->getOperand(0));
02475   Value *ExtVal = SExt;
02476   bool HasMergedNonFreeExt = false;
02477   if (isa<ZExtInst>(SExtOpnd)) {
02478     // Replace s|zext(zext(opnd))
02479     // => zext(opnd).
02480     HasMergedNonFreeExt = !TLI.isExtFree(SExtOpnd);
02481     Value *ZExt =
02482         TPT.createZExt(SExt, SExtOpnd->getOperand(0), SExt->getType());
02483     TPT.replaceAllUsesWith(SExt, ZExt);
02484     TPT.eraseInstruction(SExt);
02485     ExtVal = ZExt;
02486   } else {
02487     // Replace z|sext(trunc(opnd)) or sext(sext(opnd))
02488     // => z|sext(opnd).
02489     TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0));
02490   }
02491   CreatedInstsCost = 0;
02492 
02493   // Remove dead code.
02494   if (SExtOpnd->use_empty())
02495     TPT.eraseInstruction(SExtOpnd);
02496 
02497   // Check if the extension is still needed.
02498   Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
02499   if (!ExtInst || ExtInst->getType() != ExtInst->getOperand(0)->getType()) {
02500     if (ExtInst) {
02501       if (Exts)
02502         Exts->push_back(ExtInst);
02503       CreatedInstsCost = !TLI.isExtFree(ExtInst) && !HasMergedNonFreeExt;
02504     }
02505     return ExtVal;
02506   }
02507 
02508   // At this point we have: ext ty opnd to ty.
02509   // Reassign the uses of ExtInst to the opnd and remove ExtInst.
02510   Value *NextVal = ExtInst->getOperand(0);
02511   TPT.eraseInstruction(ExtInst, NextVal);
02512   return NextVal;
02513 }
02514 
02515 Value *TypePromotionHelper::promoteOperandForOther(
02516     Instruction *Ext, TypePromotionTransaction &TPT,
02517     InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
02518     SmallVectorImpl<Instruction *> *Exts,
02519     SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI,
02520     bool IsSExt) {
02521   // By construction, the operand of Ext is an instruction. Otherwise we cannot
02522   // get through it and this method should not be called.
02523   Instruction *ExtOpnd = cast<Instruction>(Ext->getOperand(0));
02524   CreatedInstsCost = 0;
02525   if (!ExtOpnd->hasOneUse()) {
02526     // ExtOpnd will be promoted.
02527     // All its uses, but Ext, will need to use a truncated value of the
02528     // promoted version.
02529     // Create the truncate now.
02530     Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->getType());
02531     if (Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
02532       ITrunc->removeFromParent();
02533       // Insert it just after the definition.
02534       ITrunc->insertAfter(ExtOpnd);
02535       if (Truncs)
02536         Truncs->push_back(ITrunc);
02537     }
02538 
02539     TPT.replaceAllUsesWith(ExtOpnd, Trunc);
02540     // Restore the operand of Ext (which has been replace by the previous call
02541     // to replaceAllUsesWith) to avoid creating a cycle trunc <-> sext.
02542     TPT.setOperand(Ext, 0, ExtOpnd);
02543   }
02544 
02545   // Get through the Instruction:
02546   // 1. Update its type.
02547   // 2. Replace the uses of Ext by Inst.
02548   // 3. Extend each operand that needs to be extended.
02549 
02550   // Remember the original type of the instruction before promotion.
02551   // This is useful to know that the high bits are sign extended bits.
02552   PromotedInsts.insert(std::pair<Instruction *, TypeIsSExt>(
02553       ExtOpnd, TypeIsSExt(ExtOpnd->getType(), IsSExt)));
02554   // Step #1.
02555   TPT.mutateType(ExtOpnd, Ext->getType());
02556   // Step #2.
02557   TPT.replaceAllUsesWith(Ext, ExtOpnd);
02558   // Step #3.
02559   Instruction *ExtForOpnd = Ext;
02560 
02561   DEBUG(dbgs() << "Propagate Ext to operands\n");
02562   for (int OpIdx = 0, EndOpIdx = ExtOpnd->getNumOperands(); OpIdx != EndOpIdx;
02563        ++OpIdx) {
02564     DEBUG(dbgs() << "Operand:\n" << *(ExtOpnd->getOperand(OpIdx)) << '\n');
02565     if (ExtOpnd->getOperand(OpIdx)->getType() == Ext->getType() ||
02566         !shouldExtOperand(ExtOpnd, OpIdx)) {
02567       DEBUG(dbgs() << "No need to propagate\n");
02568       continue;
02569     }
02570     // Check if we can statically extend the operand.
02571     Value *Opnd = ExtOpnd->getOperand(OpIdx);
02572     if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
02573       DEBUG(dbgs() << "Statically extend\n");
02574       unsigned BitWidth = Ext->getType()->getIntegerBitWidth();
02575       APInt CstVal = IsSExt ? Cst->getValue().sext(BitWidth)
02576                             : Cst->getValue().zext(BitWidth);
02577       TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(Ext->getType(), CstVal));
02578       continue;
02579     }
02580     // UndefValue are typed, so we have to statically sign extend them.
02581     if (isa<UndefValue>(Opnd)) {
02582       DEBUG(dbgs() << "Statically extend\n");
02583       TPT.setOperand(ExtOpnd, OpIdx, UndefValue::get(Ext->getType()));
02584       continue;
02585     }
02586 
02587     // Otherwise we have to explicity sign extend the operand.
02588     // Check if Ext was reused to extend an operand.
02589     if (!ExtForOpnd) {
02590       // If yes, create a new one.
02591       DEBUG(dbgs() << "More operands to ext\n");
02592       Value *ValForExtOpnd = IsSExt ? TPT.createSExt(Ext, Opnd, Ext->getType())
02593         : TPT.createZExt(Ext, Opnd, Ext->getType());
02594       if (!isa<Instruction>(ValForExtOpnd)) {
02595         TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
02596         continue;
02597       }
02598       ExtForOpnd = cast<Instruction>(ValForExtOpnd);
02599     }
02600     if (Exts)
02601       Exts->push_back(ExtForOpnd);
02602     TPT.setOperand(ExtForOpnd, 0, Opnd);
02603 
02604     // Move the sign extension before the insertion point.
02605     TPT.moveBefore(ExtForOpnd, ExtOpnd);
02606     TPT.setOperand(ExtOpnd, OpIdx, ExtForOpnd);
02607     CreatedInstsCost += !TLI.isExtFree(ExtForOpnd);
02608     // If more sext are required, new instructions will have to be created.
02609     ExtForOpnd = nullptr;
02610   }
02611   if (ExtForOpnd == Ext) {
02612     DEBUG(dbgs() << "Extension is useless now\n");
02613     TPT.eraseInstruction(Ext);
02614   }
02615   return ExtOpnd;
02616 }
02617 
02618 /// IsPromotionProfitable - Check whether or not promoting an instruction
02619 /// to a wider type was profitable.
02620 /// \p NewCost gives the cost of extension instructions created by the
02621 /// promotion.
02622 /// \p OldCost gives the cost of extension instructions before the promotion
02623 /// plus the number of instructions that have been
02624 /// matched in the addressing mode the promotion.
02625 /// \p PromotedOperand is the value that has been promoted.
02626 /// \return True if the promotion is profitable, false otherwise.
02627 bool AddressingModeMatcher::IsPromotionProfitable(
02628     unsigned NewCost, unsigned OldCost, Value *PromotedOperand) const {
02629   DEBUG(dbgs() << "OldCost: " << OldCost << "\tNewCost: " << NewCost << '\n');
02630   // The cost of the new extensions is greater than the cost of the
02631   // old extension plus what we folded.
02632   // This is not profitable.
02633   if (NewCost > OldCost)
02634     return false;
02635   if (NewCost < OldCost)
02636     return true;
02637   // The promotion is neutral but it may help folding the sign extension in
02638   // loads for instance.
02639   // Check that we did not create an illegal instruction.
02640   return isPromotedInstructionLegal(TLI, PromotedOperand);
02641 }
02642 
02643 /// MatchOperationAddr - Given an instruction or constant expr, see if we can
02644 /// fold the operation into the addressing mode.  If so, update the addressing
02645 /// mode and return true, otherwise return false without modifying AddrMode.
02646 /// If \p MovedAway is not NULL, it contains the information of whether or
02647 /// not AddrInst has to be folded into the addressing mode on success.
02648 /// If \p MovedAway == true, \p AddrInst will not be part of the addressing
02649 /// because it has been moved away.
02650 /// Thus AddrInst must not be added in the matched instructions.
02651 /// This state can happen when AddrInst is a sext, since it may be moved away.
02652 /// Therefore, AddrInst may not be valid when MovedAway is true and it must
02653 /// not be referenced anymore.
02654 bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode,
02655                                                unsigned Depth,
02656                                                bool *MovedAway) {
02657   // Avoid exponential behavior on extremely deep expression trees.
02658   if (Depth >= 5) return false;
02659 
02660   // By default, all matched instructions stay in place.
02661   if (MovedAway)
02662     *MovedAway = false;
02663 
02664   switch (Opcode) {
02665   case Instruction::PtrToInt:
02666     // PtrToInt is always a noop, as we know that the int type is pointer sized.
02667     return MatchAddr(AddrInst->getOperand(0), Depth);
02668   case Instruction::IntToPtr:
02669     // This inttoptr is a no-op if the integer type is pointer sized.
02670     if (TLI.getValueType(AddrInst->getOperand(0)->getType()) ==
02671         TLI.getPointerTy(AddrInst->getType()->getPointerAddressSpace()))
02672       return MatchAddr(AddrInst->getOperand(0), Depth);
02673     return false;
02674   case Instruction::BitCast:
02675     // BitCast is always a noop, and we can handle it as long as it is
02676     // int->int or pointer->pointer (we don't want int<->fp or something).
02677     if ((AddrInst->getOperand(0)->getType()->isPointerTy() ||
02678          AddrInst->getOperand(0)->getType()->isIntegerTy()) &&
02679         // Don't touch identity bitcasts.  These were probably put here by LSR,
02680         // and we don't want to mess around with them.  Assume it knows what it
02681         // is doing.
02682         AddrInst->getOperand(0)->getType() != AddrInst->getType())
02683       return MatchAddr(AddrInst->getOperand(0), Depth);
02684     return false;
02685   case Instruction::AddrSpaceCast: {
02686     unsigned SrcAS
02687       = AddrInst->getOperand(0)->getType()->getPointerAddressSpace();
02688     unsigned DestAS = AddrInst->getType()->getPointerAddressSpace();
02689     if (TLI.isNoopAddrSpaceCast(SrcAS, DestAS))
02690       return MatchAddr(AddrInst->getOperand(0), Depth);
02691     return false;
02692   }
02693   case Instruction::Add: {
02694     // Check to see if we can merge in the RHS then the LHS.  If so, we win.
02695     ExtAddrMode BackupAddrMode = AddrMode;
02696     unsigned OldSize = AddrModeInsts.size();
02697     // Start a transaction at this point.
02698     // The LHS may match but not the RHS.
02699     // Therefore, we need a higher level restoration point to undo partially
02700     // matched operation.
02701     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
02702         TPT.getRestorationPoint();
02703 
02704     if (MatchAddr(AddrInst->getOperand(1), Depth+1) &&
02705         MatchAddr(AddrInst->getOperand(0), Depth+1))
02706       return true;
02707 
02708     // Restore the old addr mode info.
02709     AddrMode = BackupAddrMode;
02710     AddrModeInsts.resize(OldSize);
02711     TPT.rollback(LastKnownGood);
02712 
02713     // Otherwise this was over-aggressive.  Try merging in the LHS then the RHS.
02714     if (MatchAddr(AddrInst->getOperand(0), Depth+1) &&
02715         MatchAddr(AddrInst->getOperand(1), Depth+1))
02716       return true;
02717 
02718     // Otherwise we definitely can't merge the ADD in.
02719     AddrMode = BackupAddrMode;
02720     AddrModeInsts.resize(OldSize);
02721     TPT.rollback(LastKnownGood);
02722     break;
02723   }
02724   //case Instruction::Or:
02725   // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD.
02726   //break;
02727   case Instruction::Mul:
02728   case Instruction::Shl: {
02729     // Can only handle X*C and X << C.
02730     ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1));
02731     if (!RHS)
02732       return false;
02733     int64_t Scale = RHS->getSExtValue();
02734     if (Opcode == Instruction::Shl)
02735       Scale = 1LL << Scale;
02736 
02737     return MatchScaledValue(AddrInst->getOperand(0), Scale, Depth);
02738   }
02739   case Instruction::GetElementPtr: {
02740     // Scan the GEP.  We check it if it contains constant offsets and at most
02741     // one variable offset.
02742     int VariableOperand = -1;
02743     unsigned VariableScale = 0;
02744 
02745     int64_t ConstantOffset = 0;
02746     const DataLayout *TD = TLI.getDataLayout();
02747     gep_type_iterator GTI = gep_type_begin(AddrInst);
02748     for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) {
02749       if (StructType *STy = dyn_cast<StructType>(*GTI)) {
02750         const StructLayout *SL = TD->getStructLayout(STy);
02751         unsigned Idx =
02752           cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue();
02753         ConstantOffset += SL->getElementOffset(Idx);
02754       } else {
02755         uint64_t TypeSize = TD->getTypeAllocSize(GTI.getIndexedType());
02756         if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) {
02757           ConstantOffset += CI->getSExtValue()*TypeSize;
02758         } else if (TypeSize) {  // Scales of zero don't do anything.
02759           // We only allow one variable index at the moment.
02760           if (VariableOperand != -1)
02761             return false;
02762 
02763           // Remember the variable index.
02764           VariableOperand = i;
02765           VariableScale = TypeSize;
02766         }
02767       }
02768     }
02769 
02770     // A common case is for the GEP to only do a constant offset.  In this case,
02771     // just add it to the disp field and check validity.
02772     if (VariableOperand == -1) {
02773       AddrMode.BaseOffs += ConstantOffset;
02774       if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){
02775         // Check to see if we can fold the base pointer in too.
02776         if (MatchAddr(AddrInst->getOperand(0), Depth+1))
02777           return true;
02778       }
02779       AddrMode.BaseOffs -= ConstantOffset;
02780       return false;
02781     }
02782 
02783     // Save the valid addressing mode in case we can't match.
02784     ExtAddrMode BackupAddrMode = AddrMode;
02785     unsigned OldSize = AddrModeInsts.size();
02786 
02787     // See if the scale and offset amount is valid for this target.
02788     AddrMode.BaseOffs += ConstantOffset;
02789 
02790     // Match the base operand of the GEP.
02791     if (!MatchAddr(AddrInst->getOperand(0), Depth+1)) {
02792       // If it couldn't be matched, just stuff the value in a register.
02793       if (AddrMode.HasBaseReg) {
02794         AddrMode = BackupAddrMode;
02795         AddrModeInsts.resize(OldSize);
02796         return false;
02797       }
02798       AddrMode.HasBaseReg = true;
02799       AddrMode.BaseReg = AddrInst->getOperand(0);
02800     }
02801 
02802     // Match the remaining variable portion of the GEP.
02803     if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale,
02804                           Depth)) {
02805       // If it couldn't be matched, try stuffing the base into a register
02806       // instead of matching it, and retrying the match of the scale.
02807       AddrMode = BackupAddrMode;
02808       AddrModeInsts.resize(OldSize);
02809       if (AddrMode.HasBaseReg)
02810         return false;
02811       AddrMode.HasBaseReg = true;
02812       AddrMode.BaseReg = AddrInst->getOperand(0);
02813       AddrMode.BaseOffs += ConstantOffset;
02814       if (!MatchScaledValue(AddrInst->getOperand(VariableOperand),
02815                             VariableScale, Depth)) {
02816         // If even that didn't work, bail.
02817         AddrMode = BackupAddrMode;
02818         AddrModeInsts.resize(OldSize);
02819         return false;
02820       }
02821     }
02822 
02823     return true;
02824   }
02825   case Instruction::SExt:
02826   case Instruction::ZExt: {
02827     Instruction *Ext = dyn_cast<Instruction>(AddrInst);
02828     if (!Ext)
02829       return false;
02830 
02831     // Try to move this ext out of the way of the addressing mode.
02832     // Ask for a method for doing so.
02833     TypePromotionHelper::Action TPH =
02834         TypePromotionHelper::getAction(Ext, InsertedTruncs, TLI, PromotedInsts);
02835     if (!TPH)
02836       return false;
02837 
02838     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
02839         TPT.getRestorationPoint();
02840     unsigned CreatedInstsCost = 0;
02841     unsigned ExtCost = !TLI.isExtFree(Ext);
02842     Value *PromotedOperand =
02843         TPH(Ext, TPT, PromotedInsts, CreatedInstsCost, nullptr, nullptr, TLI);
02844     // SExt has been moved away.
02845     // Thus either it will be rematched later in the recursive calls or it is
02846     // gone. Anyway, we must not fold it into the addressing mode at this point.
02847     // E.g.,
02848     // op = add opnd, 1
02849     // idx = ext op
02850     // addr = gep base, idx
02851     // is now:
02852     // promotedOpnd = ext opnd            <- no match here
02853     // op = promoted_add promotedOpnd, 1  <- match (later in recursive calls)
02854     // addr = gep base, op                <- match
02855     if (MovedAway)
02856       *MovedAway = true;
02857 
02858     assert(PromotedOperand &&
02859            "TypePromotionHelper should have filtered out those cases");
02860 
02861     ExtAddrMode BackupAddrMode = AddrMode;
02862     unsigned OldSize = AddrModeInsts.size();
02863 
02864     if (!MatchAddr(PromotedOperand, Depth) ||
02865         // The total of the new cost is equals to the cost of the created
02866         // instructions.
02867         // The total of the old cost is equals to the cost of the extension plus
02868         // what we have saved in the addressing mode.
02869         !IsPromotionProfitable(CreatedInstsCost,
02870                                ExtCost + (AddrModeInsts.size() - OldSize),
02871                                PromotedOperand)) {
02872       AddrMode = BackupAddrMode;
02873       AddrModeInsts.resize(OldSize);
02874       DEBUG(dbgs() << "Sign extension does not pay off: rollback\n");
02875       TPT.rollback(LastKnownGood);
02876       return false;
02877     }
02878     return true;
02879   }
02880   }
02881   return false;
02882 }
02883 
02884 /// MatchAddr - If we can, try to add the value of 'Addr' into the current
02885 /// addressing mode.  If Addr can't be added to AddrMode this returns false and
02886 /// leaves AddrMode unmodified.  This assumes that Addr is either a pointer type
02887 /// or intptr_t for the target.
02888 ///
02889 bool AddressingModeMatcher::MatchAddr(Value *Addr, unsigned Depth) {
02890   // Start a transaction at this point that we will rollback if the matching
02891   // fails.
02892   TypePromotionTransaction::ConstRestorationPt LastKnownGood =
02893       TPT.getRestorationPoint();
02894   if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) {
02895     // Fold in immediates if legal for the target.
02896     AddrMode.BaseOffs += CI->getSExtValue();
02897     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
02898       return true;
02899     AddrMode.BaseOffs -= CI->getSExtValue();
02900   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) {
02901     // If this is a global variable, try to fold it into the addressing mode.
02902     if (!AddrMode.BaseGV) {
02903       AddrMode.BaseGV = GV;
02904       if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
02905         return true;
02906       AddrMode.BaseGV = nullptr;
02907     }
02908   } else if (Instruction *I = dyn_cast<Instruction>(Addr)) {
02909     ExtAddrMode BackupAddrMode = AddrMode;
02910     unsigned OldSize = AddrModeInsts.size();
02911 
02912     // Check to see if it is possible to fold this operation.
02913     bool MovedAway = false;
02914     if (MatchOperationAddr(I, I->getOpcode(), Depth, &MovedAway)) {
02915       // This instruction may have been move away. If so, there is nothing
02916       // to check here.
02917       if (MovedAway)
02918         return true;
02919       // Okay, it's possible to fold this.  Check to see if it is actually
02920       // *profitable* to do so.  We use a simple cost model to avoid increasing
02921       // register pressure too much.
02922       if (I->hasOneUse() ||
02923           IsProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) {
02924         AddrModeInsts.push_back(I);
02925         return true;
02926       }
02927 
02928       // It isn't profitable to do this, roll back.
02929       //cerr << "NOT FOLDING: " << *I;
02930       AddrMode = BackupAddrMode;
02931       AddrModeInsts.resize(OldSize);
02932       TPT.rollback(LastKnownGood);
02933     }
02934   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
02935     if (MatchOperationAddr(CE, CE->getOpcode(), Depth))
02936       return true;
02937     TPT.rollback(LastKnownGood);
02938   } else if (isa<ConstantPointerNull>(Addr)) {
02939     // Null pointer gets folded without affecting the addressing mode.
02940     return true;
02941   }
02942 
02943   // Worse case, the target should support [reg] addressing modes. :)
02944   if (!AddrMode.HasBaseReg) {
02945     AddrMode.HasBaseReg = true;
02946     AddrMode.BaseReg = Addr;
02947     // Still check for legality in case the target supports [imm] but not [i+r].
02948     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
02949       return true;
02950     AddrMode.HasBaseReg = false;
02951     AddrMode.BaseReg = nullptr;
02952   }
02953 
02954   // If the base register is already taken, see if we can do [r+r].
02955   if (AddrMode.Scale == 0) {
02956     AddrMode.Scale = 1;
02957     AddrMode.ScaledReg = Addr;
02958     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
02959       return true;
02960     AddrMode.Scale = 0;
02961     AddrMode.ScaledReg = nullptr;
02962   }
02963   // Couldn't match.
02964   TPT.rollback(LastKnownGood);
02965   return false;
02966 }
02967 
02968 /// IsOperandAMemoryOperand - Check to see if all uses of OpVal by the specified
02969 /// inline asm call are due to memory operands.  If so, return true, otherwise
02970 /// return false.
02971 static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal,
02972                                     const TargetMachine &TM) {
02973   const Function *F = CI->getParent()->getParent();
02974   const TargetLowering *TLI = TM.getSubtargetImpl(*F)->getTargetLowering();
02975   const TargetRegisterInfo *TRI = TM.getSubtargetImpl(*F)->getRegisterInfo();
02976   TargetLowering::AsmOperandInfoVector TargetConstraints =
02977       TLI->ParseConstraints(TRI, ImmutableCallSite(CI));
02978   for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
02979     TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
02980 
02981     // Compute the constraint code and ConstraintType to use.
02982     TLI->ComputeConstraintToUse(OpInfo, SDValue());
02983 
02984     // If this asm operand is our Value*, and if it isn't an indirect memory
02985     // operand, we can't fold it!
02986     if (OpInfo.CallOperandVal == OpVal &&
02987         (OpInfo.ConstraintType != TargetLowering::C_Memory ||
02988          !OpInfo.isIndirect))
02989       return false;
02990   }
02991 
02992   return true;
02993 }
02994 
02995 /// FindAllMemoryUses - Recursively walk all the uses of I until we find a
02996 /// memory use.  If we find an obviously non-foldable instruction, return true.
02997 /// Add the ultimately found memory instructions to MemoryUses.
02998 static bool FindAllMemoryUses(
02999     Instruction *I,
03000     SmallVectorImpl<std::pair<Instruction *, unsigned>> &MemoryUses,
03001     SmallPtrSetImpl<Instruction *> &ConsideredInsts, const TargetMachine &TM) {
03002   // If we already considered this instruction, we're done.
03003   if (!ConsideredInsts.insert(I).second)
03004     return false;
03005 
03006   // If this is an obviously unfoldable instruction, bail out.
03007   if (!MightBeFoldableInst(I))
03008     return true;
03009 
03010   // Loop over all the uses, recursively processing them.
03011   for (Use &U : I->uses()) {
03012     Instruction *UserI = cast<Instruction>(U.getUser());
03013 
03014     if (LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
03015       MemoryUses.push_back(std::make_pair(LI, U.getOperandNo()));
03016       continue;
03017     }
03018 
03019     if (StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
03020       unsigned opNo = U.getOperandNo();
03021       if (opNo == 0) return true; // Storing addr, not into addr.
03022       MemoryUses.push_back(std::make_pair(SI, opNo));
03023       continue;
03024     }
03025 
03026     if (CallInst *CI = dyn_cast<CallInst>(UserI)) {
03027       InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue());
03028       if (!IA) return true;
03029 
03030       // If this is a memory operand, we're cool, otherwise bail out.
03031       if (!IsOperandAMemoryOperand(CI, IA, I, TM))
03032         return true;
03033       continue;
03034     }
03035 
03036     if (FindAllMemoryUses(UserI, MemoryUses, ConsideredInsts, TM))
03037       return true;
03038   }
03039 
03040   return false;
03041 }
03042 
03043 /// ValueAlreadyLiveAtInst - Retrn true if Val is already known to be live at
03044 /// the use site that we're folding it into.  If so, there is no cost to
03045 /// include it in the addressing mode.  KnownLive1 and KnownLive2 are two values
03046 /// that we know are live at the instruction already.
03047 bool AddressingModeMatcher::ValueAlreadyLiveAtInst(Value *Val,Value *KnownLive1,
03048                                                    Value *KnownLive2) {
03049   // If Val is either of the known-live values, we know it is live!
03050   if (Val == nullptr || Val == KnownLive1 || Val == KnownLive2)
03051     return true;
03052 
03053   // All values other than instructions and arguments (e.g. constants) are live.
03054   if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true;
03055 
03056   // If Val is a constant sized alloca in the entry block, it is live, this is
03057   // true because it is just a reference to the stack/frame pointer, which is
03058   // live for the whole function.
03059   if (AllocaInst *AI = dyn_cast<AllocaInst>(Val))
03060     if (AI->isStaticAlloca())
03061       return true;
03062 
03063   // Check to see if this value is already used in the memory instruction's
03064   // block.  If so, it's already live into the block at the very least, so we
03065   // can reasonably fold it.
03066   return Val->isUsedInBasicBlock(MemoryInst->getParent());
03067 }
03068 
03069 /// IsProfitableToFoldIntoAddressingMode - It is possible for the addressing
03070 /// mode of the machine to fold the specified instruction into a load or store
03071 /// that ultimately uses it.  However, the specified instruction has multiple
03072 /// uses.  Given this, it may actually increase register pressure to fold it
03073 /// into the load.  For example, consider this code:
03074 ///
03075 ///     X = ...
03076 ///     Y = X+1
03077 ///     use(Y)   -> nonload/store
03078 ///     Z = Y+1
03079 ///     load Z
03080 ///
03081 /// In this case, Y has multiple uses, and can be folded into the load of Z
03082 /// (yielding load [X+2]).  However, doing this will cause both "X" and "X+1" to
03083 /// be live at the use(Y) line.  If we don't fold Y into load Z, we use one
03084 /// fewer register.  Since Y can't be folded into "use(Y)" we don't increase the
03085 /// number of computations either.
03086 ///
03087 /// Note that this (like most of CodeGenPrepare) is just a rough heuristic.  If
03088 /// X was live across 'load Z' for other reasons, we actually *would* want to
03089 /// fold the addressing mode in the Z case.  This would make Y die earlier.
03090 bool AddressingModeMatcher::
03091 IsProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore,
03092                                      ExtAddrMode &AMAfter) {
03093   if (IgnoreProfitability) return true;
03094 
03095   // AMBefore is the addressing mode before this instruction was folded into it,
03096   // and AMAfter is the addressing mode after the instruction was folded.  Get
03097   // the set of registers referenced by AMAfter and subtract out those
03098   // referenced by AMBefore: this is the set of values which folding in this
03099   // address extends the lifetime of.
03100   //
03101   // Note that there are only two potential values being referenced here,
03102   // BaseReg and ScaleReg (global addresses are always available, as are any
03103   // folded immediates).
03104   Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg;
03105 
03106   // If the BaseReg or ScaledReg was referenced by the previous addrmode, their
03107   // lifetime wasn't extended by adding this instruction.
03108   if (ValueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg))
03109     BaseReg = nullptr;
03110   if (ValueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg))
03111     ScaledReg = nullptr;
03112 
03113   // If folding this instruction (and it's subexprs) didn't extend any live
03114   // ranges, we're ok with it.
03115   if (!BaseReg && !ScaledReg)
03116     return true;
03117 
03118   // If all uses of this instruction are ultimately load/store/inlineasm's,
03119   // check to see if their addressing modes will include this instruction.  If
03120   // so, we can fold it into all uses, so it doesn't matter if it has multiple
03121   // uses.
03122   SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses;
03123   SmallPtrSet<Instruction*, 16> ConsideredInsts;
03124   if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TM))
03125     return false;  // Has a non-memory, non-foldable use!
03126 
03127   // Now that we know that all uses of this instruction are part of a chain of
03128   // computation involving only operations that could theoretically be folded
03129   // into a memory use, loop over each of these uses and see if they could
03130   // *actually* fold the instruction.
03131   SmallVector<Instruction*, 32> MatchedAddrModeInsts;
03132   for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) {
03133     Instruction *User = MemoryUses[i].first;
03134     unsigned OpNo = MemoryUses[i].second;
03135 
03136     // Get the access type of this use.  If the use isn't a pointer, we don't
03137     // know what it accesses.
03138     Value *Address = User->getOperand(OpNo);
03139     if (!Address->getType()->isPointerTy())
03140       return false;
03141     Type *AddressAccessTy = Address->getType()->getPointerElementType();
03142 
03143     // Do a match against the root of this address, ignoring profitability. This
03144     // will tell us if the addressing mode for the memory operation will
03145     // *actually* cover the shared instruction.
03146     ExtAddrMode Result;
03147     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
03148         TPT.getRestorationPoint();
03149     AddressingModeMatcher Matcher(MatchedAddrModeInsts, TM, AddressAccessTy,
03150                                   MemoryInst, Result, InsertedTruncs,
03151                                   PromotedInsts, TPT);
03152     Matcher.IgnoreProfitability = true;
03153     bool Success = Matcher.MatchAddr(Address, 0);
03154     (void)Success; assert(Success && "Couldn't select *anything*?");
03155 
03156     // The match was to check the profitability, the changes made are not
03157     // part of the original matcher. Therefore, they should be dropped
03158     // otherwise the original matcher will not present the right state.
03159     TPT.rollback(LastKnownGood);
03160 
03161     // If the match didn't cover I, then it won't be shared by it.
03162     if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(),
03163                   I) == MatchedAddrModeInsts.end())
03164       return false;
03165 
03166     MatchedAddrModeInsts.clear();
03167   }
03168 
03169   return true;
03170 }
03171 
03172 } // end anonymous namespace
03173 
03174 /// IsNonLocalValue - Return true if the specified values are defined in a
03175 /// different basic block than BB.
03176 static bool IsNonLocalValue(Value *V, BasicBlock *BB) {
03177   if (Instruction *I = dyn_cast<Instruction>(V))
03178     return I->getParent() != BB;
03179   return false;
03180 }
03181 
03182 /// OptimizeMemoryInst - Load and Store Instructions often have
03183 /// addressing modes that can do significant amounts of computation.  As such,
03184 /// instruction selection will try to get the load or store to do as much
03185 /// computation as possible for the program.  The problem is that isel can only
03186 /// see within a single block.  As such, we sink as much legal addressing mode
03187 /// stuff into the block as possible.
03188 ///
03189 /// This method is used to optimize both load/store and inline asms with memory
03190 /// operands.
03191 bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
03192                                         Type *AccessTy) {
03193   Value *Repl = Addr;
03194 
03195   // Try to collapse single-value PHI nodes.  This is necessary to undo
03196   // unprofitable PRE transformations.
03197   SmallVector<Value*, 8> worklist;
03198   SmallPtrSet<Value*, 16> Visited;
03199   worklist.push_back(Addr);
03200 
03201   // Use a worklist to iteratively look through PHI nodes, and ensure that
03202   // the addressing mode obtained from the non-PHI roots of the graph
03203   // are equivalent.
03204   Value *Consensus = nullptr;
03205   unsigned NumUsesConsensus = 0;
03206   bool IsNumUsesConsensusValid = false;
03207   SmallVector<Instruction*, 16> AddrModeInsts;
03208   ExtAddrMode AddrMode;
03209   TypePromotionTransaction TPT;
03210   TypePromotionTransaction::ConstRestorationPt LastKnownGood =
03211       TPT.getRestorationPoint();
03212   while (!worklist.empty()) {
03213     Value *V = worklist.back();
03214     worklist.pop_back();
03215 
03216     // Break use-def graph loops.
03217     if (!Visited.insert(V).second) {
03218       Consensus = nullptr;
03219       break;
03220     }
03221 
03222     // For a PHI node, push all of its incoming values.
03223     if (PHINode *P = dyn_cast<PHINode>(V)) {
03224       for (Value *IncValue : P->incoming_values())
03225         worklist.push_back(IncValue);
03226       continue;
03227     }
03228 
03229     // For non-PHIs, determine the addressing mode being computed.
03230     SmallVector<Instruction*, 16> NewAddrModeInsts;
03231     ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
03232         V, AccessTy, MemoryInst, NewAddrModeInsts, *TM, InsertedTruncsSet,
03233         PromotedInsts, TPT);
03234 
03235     // This check is broken into two cases with very similar code to avoid using
03236     // getNumUses() as much as possible. Some values have a lot of uses, so
03237     // calling getNumUses() unconditionally caused a significant compile-time
03238     // regression.
03239     if (!Consensus) {
03240       Consensus = V;
03241       AddrMode = NewAddrMode;
03242       AddrModeInsts = NewAddrModeInsts;
03243       continue;
03244     } else if (NewAddrMode == AddrMode) {
03245       if (!IsNumUsesConsensusValid) {
03246         NumUsesConsensus = Consensus->getNumUses();
03247         IsNumUsesConsensusValid = true;
03248       }
03249 
03250       // Ensure that the obtained addressing mode is equivalent to that obtained
03251       // for all other roots of the PHI traversal.  Also, when choosing one
03252       // such root as representative, select the one with the most uses in order
03253       // to keep the cost modeling heuristics in AddressingModeMatcher
03254       // applicable.
03255       unsigned NumUses = V->getNumUses();
03256       if (NumUses > NumUsesConsensus) {
03257         Consensus = V;
03258         NumUsesConsensus = NumUses;
03259         AddrModeInsts = NewAddrModeInsts;
03260       }
03261       continue;
03262     }
03263 
03264     Consensus = nullptr;
03265     break;
03266   }
03267 
03268   // If the addressing mode couldn't be determined, or if multiple different
03269   // ones were determined, bail out now.
03270   if (!Consensus) {
03271     TPT.rollback(LastKnownGood);
03272     return false;
03273   }
03274   TPT.commit();
03275 
03276   // Check to see if any of the instructions supersumed by this addr mode are
03277   // non-local to I's BB.
03278   bool AnyNonLocal = false;
03279   for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) {
03280     if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) {
03281       AnyNonLocal = true;
03282       break;
03283     }
03284   }
03285 
03286   // If all the instructions matched are already in this BB, don't do anything.
03287   if (!AnyNonLocal) {
03288     DEBUG(dbgs() << "CGP: Found      local addrmode: " << AddrMode << "\n");
03289     return false;
03290   }
03291 
03292   // Insert this computation right after this user.  Since our caller is
03293   // scanning from the top of the BB to the bottom, reuse of the expr are
03294   // guaranteed to happen later.
03295   IRBuilder<> Builder(MemoryInst);
03296 
03297   // Now that we determined the addressing expression we want to use and know
03298   // that we have to sink it into this block.  Check to see if we have already
03299   // done this for some other load/store instr in this block.  If so, reuse the
03300   // computation.
03301   Value *&SunkAddr = SunkAddrs[Addr];
03302   if (SunkAddr) {
03303     DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for "
03304                  << *MemoryInst << "\n");
03305     if (SunkAddr->getType() != Addr->getType())
03306       SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType());
03307   } else if (AddrSinkUsingGEPs ||
03308              (!AddrSinkUsingGEPs.getNumOccurrences() && TM &&
03309               TM->getSubtargetImpl(*MemoryInst->getParent()->getParent())
03310                   ->useAA())) {
03311     // By default, we use the GEP-based method when AA is used later. This
03312     // prevents new inttoptr/ptrtoint pairs from degrading AA capabilities.
03313     DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
03314                  << *MemoryInst << "\n");
03315     Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(Addr->getType());
03316     Value *ResultPtr = nullptr, *ResultIndex = nullptr;
03317 
03318     // First, find the pointer.
03319     if (AddrMode.BaseReg && AddrMode.BaseReg->getType()->isPointerTy()) {
03320       ResultPtr = AddrMode.BaseReg;
03321       AddrMode.BaseReg = nullptr;
03322     }
03323 
03324     if (AddrMode.Scale && AddrMode.ScaledReg->getType()->isPointerTy()) {
03325       // We can't add more than one pointer together, nor can we scale a
03326       // pointer (both of which seem meaningless).
03327       if (ResultPtr || AddrMode.Scale != 1)
03328         return false;
03329 
03330       ResultPtr = AddrMode.ScaledReg;
03331       AddrMode.Scale = 0;
03332     }
03333 
03334     if (AddrMode.BaseGV) {
03335       if (ResultPtr)
03336         return false;
03337 
03338       ResultPtr = AddrMode.BaseGV;
03339     }
03340 
03341     // If the real base value actually came from an inttoptr, then the matcher
03342     // will look through it and provide only the integer value. In that case,
03343     // use it here.
03344     if (!ResultPtr && AddrMode.BaseReg) {
03345       ResultPtr =
03346         Builder.CreateIntToPtr(AddrMode.BaseReg, Addr->getType(), "sunkaddr");
03347       AddrMode.BaseReg = nullptr;
03348     } else if (!ResultPtr && AddrMode.Scale == 1) {
03349       ResultPtr =
03350         Builder.CreateIntToPtr(AddrMode.ScaledReg, Addr->getType(), "sunkaddr");
03351       AddrMode.Scale = 0;
03352     }
03353 
03354     if (!ResultPtr &&
03355         !AddrMode.BaseReg && !AddrMode.Scale && !AddrMode.BaseOffs) {
03356       SunkAddr = Constant::getNullValue(Addr->getType());
03357     } else if (!ResultPtr) {
03358       return false;
03359     } else {
03360       Type *I8PtrTy =
03361           Builder.getInt8PtrTy(Addr->getType()->getPointerAddressSpace());
03362       Type *I8Ty = Builder.getInt8Ty();
03363 
03364       // Start with the base register. Do this first so that subsequent address
03365       // matching finds it last, which will prevent it from trying to match it
03366       // as the scaled value in case it happens to be a mul. That would be
03367       // problematic if we've sunk a different mul for the scale, because then
03368       // we'd end up sinking both muls.
03369       if (AddrMode.BaseReg) {
03370         Value *V = AddrMode.BaseReg;
03371         if (V->getType() != IntPtrTy)
03372           V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr");
03373 
03374         ResultIndex = V;
03375       }
03376 
03377       // Add the scale value.
03378       if (AddrMode.Scale) {
03379         Value *V = AddrMode.ScaledReg;
03380         if (V->getType() == IntPtrTy) {
03381           // done.
03382         } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() <
03383                    cast<IntegerType>(V->getType())->getBitWidth()) {
03384           V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
03385         } else {
03386           // It is only safe to sign extend the BaseReg if we know that the math
03387           // required to create it did not overflow before we extend it. Since
03388           // the original IR value was tossed in favor of a constant back when
03389           // the AddrMode was created we need to bail out gracefully if widths
03390           // do not match instead of extending it.
03391           Instruction *I = dyn_cast_or_null<Instruction>(ResultIndex);
03392           if (I && (ResultIndex != AddrMode.BaseReg))
03393             I->eraseFromParent();
03394           return false;
03395         }
03396 
03397         if (AddrMode.Scale != 1)
03398           V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
03399                                 "sunkaddr");
03400         if (ResultIndex)
03401           ResultIndex = Builder.CreateAdd(ResultIndex, V, "sunkaddr");
03402         else
03403           ResultIndex = V;
03404       }
03405 
03406       // Add in the Base Offset if present.
03407       if (AddrMode.BaseOffs) {
03408         Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs);
03409         if (ResultIndex) {
03410           // We need to add this separately from the scale above to help with
03411           // SDAG consecutive load/store merging.
03412           if (ResultPtr->getType() != I8PtrTy)
03413             ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy);
03414           ResultPtr = Builder.CreateGEP(I8Ty, ResultPtr, ResultIndex, "sunkaddr");
03415         }
03416 
03417         ResultIndex = V;
03418       }
03419 
03420       if (!ResultIndex) {
03421         SunkAddr = ResultPtr;
03422       } else {
03423         if (ResultPtr->getType() != I8PtrTy)
03424           ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy);
03425         SunkAddr = Builder.CreateGEP(I8Ty, ResultPtr, ResultIndex, "sunkaddr");
03426       }
03427 
03428       if (SunkAddr->getType() != Addr->getType())
03429         SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType());
03430     }
03431   } else {
03432     DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
03433                  << *MemoryInst << "\n");
03434     Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(Addr->getType());
03435     Value *Result = nullptr;
03436 
03437     // Start with the base register. Do this first so that subsequent address
03438     // matching finds it last, which will prevent it from trying to match it
03439     // as the scaled value in case it happens to be a mul. That would be
03440     // problematic if we've sunk a different mul for the scale, because then
03441     // we'd end up sinking both muls.
03442     if (AddrMode.BaseReg) {
03443       Value *V = AddrMode.BaseReg;
03444       if (V->getType()->isPointerTy())
03445         V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
03446       if (V->getType() != IntPtrTy)
03447         V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr");
03448       Result = V;
03449     }
03450 
03451     // Add the scale value.
03452     if (AddrMode.Scale) {
03453       Value *V = AddrMode.ScaledReg;
03454       if (V->getType() == IntPtrTy) {
03455         // done.
03456       } else if (V->getType()->isPointerTy()) {
03457         V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
03458       } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() <
03459                  cast<IntegerType>(V->getType())->getBitWidth()) {
03460         V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
03461       } else {
03462         // It is only safe to sign extend the BaseReg if we know that the math
03463         // required to create it did not overflow before we extend it. Since
03464         // the original IR value was tossed in favor of a constant back when
03465         // the AddrMode was created we need to bail out gracefully if widths
03466         // do not match instead of extending it.
03467         Instruction *I = dyn_cast_or_null<Instruction>(Result);
03468         if (I && (Result != AddrMode.BaseReg))
03469           I->eraseFromParent();
03470         return false;
03471       }
03472       if (AddrMode.Scale != 1)
03473         V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
03474                               "sunkaddr");
03475       if (Result)
03476         Result = Builder.CreateAdd(Result, V, "sunkaddr");
03477       else
03478         Result = V;
03479     }
03480 
03481     // Add in the BaseGV if present.
03482     if (AddrMode.BaseGV) {
03483       Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr");
03484       if (Result)
03485         Result = Builder.CreateAdd(Result, V, "sunkaddr");
03486       else
03487         Result = V;
03488     }
03489 
03490     // Add in the Base Offset if present.
03491     if (AddrMode.BaseOffs) {
03492       Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs);
03493       if (Result)
03494         Result = Builder.CreateAdd(Result, V, "sunkaddr");
03495       else
03496         Result = V;
03497     }
03498 
03499     if (!Result)
03500       SunkAddr = Constant::getNullValue(Addr->getType());
03501     else
03502       SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr");
03503   }
03504 
03505   MemoryInst->replaceUsesOfWith(Repl, SunkAddr);
03506 
03507   // If we have no uses, recursively delete the value and all dead instructions
03508   // using it.
03509   if (Repl->use_empty()) {
03510     // This can cause recursive deletion, which can invalidate our iterator.
03511     // Use a WeakVH to hold onto it in case this happens.
03512     WeakVH IterHandle(CurInstIterator);
03513     BasicBlock *BB = CurInstIterator->getParent();
03514 
03515     RecursivelyDeleteTriviallyDeadInstructions(Repl, TLInfo);
03516 
03517     if (IterHandle != CurInstIterator) {
03518       // If the iterator instruction was recursively deleted, start over at the
03519       // start of the block.
03520       CurInstIterator = BB->begin();
03521       SunkAddrs.clear();
03522     }
03523   }
03524   ++NumMemoryInsts;
03525   return true;
03526 }
03527 
03528 /// OptimizeInlineAsmInst - If there are any memory operands, use
03529 /// OptimizeMemoryInst to sink their address computing into the block when
03530 /// possible / profitable.
03531 bool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) {
03532   bool MadeChange = false;
03533 
03534   const TargetRegisterInfo *TRI =
03535       TM->getSubtargetImpl(*CS->getParent()->getParent())->getRegisterInfo();
03536   TargetLowering::AsmOperandInfoVector
03537     TargetConstraints = TLI->ParseConstraints(TRI, CS);
03538   unsigned ArgNo = 0;
03539   for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
03540     TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
03541 
03542     // Compute the constraint code and ConstraintType to use.
03543     TLI->ComputeConstraintToUse(OpInfo, SDValue());
03544 
03545     if (OpInfo.ConstraintType == TargetLowering::C_Memory &&
03546         OpInfo.isIndirect) {
03547       Value *OpVal = CS->getArgOperand(ArgNo++);
03548       MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType());
03549     } else if (OpInfo.Type == InlineAsm::isInput)
03550       ArgNo++;
03551   }
03552 
03553   return MadeChange;
03554 }
03555 
03556 /// \brief Check if all the uses of \p Inst are equivalent (or free) zero or
03557 /// sign extensions.
03558 static bool hasSameExtUse(Instruction *Inst, const TargetLowering &TLI) {
03559   assert(!Inst->use_empty() && "Input must have at least one use");
03560   const Instruction *FirstUser = cast<Instruction>(*Inst->user_begin());
03561   bool IsSExt = isa<SExtInst>(FirstUser);
03562   Type *ExtTy = FirstUser->getType();
03563   for (const User *U : Inst->users()) {
03564     const Instruction *UI = cast<Instruction>(U);
03565     if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI)))
03566       return false;
03567     Type *CurTy = UI->getType();
03568     // Same input and output types: Same instruction after CSE.
03569     if (CurTy == ExtTy)
03570       continue;
03571 
03572     // If IsSExt is true, we are in this situation:
03573     // a = Inst
03574     // b = sext ty1 a to ty2
03575     // c = sext ty1 a to ty3
03576     // Assuming ty2 is shorter than ty3, this could be turned into:
03577     // a = Inst
03578     // b = sext ty1 a to ty2
03579     // c = sext ty2 b to ty3
03580     // However, the last sext is not free.
03581     if (IsSExt)
03582       return false;
03583 
03584     // This is a ZExt, maybe this is free to extend from one type to another.
03585     // In that case, we would not account for a different use.
03586     Type *NarrowTy;
03587     Type *LargeTy;
03588     if (ExtTy->getScalarType()->getIntegerBitWidth() >
03589         CurTy->getScalarType()->getIntegerBitWidth()) {
03590       NarrowTy = CurTy;
03591       LargeTy = ExtTy;
03592     } else {
03593       NarrowTy = ExtTy;
03594       LargeTy = CurTy;
03595     }
03596 
03597     if (!TLI.isZExtFree(NarrowTy, LargeTy))
03598       return false;
03599   }
03600   // All uses are the same or can be derived from one another for free.
03601   return true;
03602 }
03603 
03604 /// \brief Try to form ExtLd by promoting \p Exts until they reach a
03605 /// load instruction.
03606 /// If an ext(load) can be formed, it is returned via \p LI for the load
03607 /// and \p Inst for the extension.
03608 /// Otherwise LI == nullptr and Inst == nullptr.
03609 /// When some promotion happened, \p TPT contains the proper state to
03610 /// revert them.
03611 ///
03612 /// \return true when promoting was necessary to expose the ext(load)
03613 /// opportunity, false otherwise.
03614 ///
03615 /// Example:
03616 /// \code
03617 /// %ld = load i32* %addr
03618 /// %add = add nuw i32 %ld, 4
03619 /// %zext = zext i32 %add to i64
03620 /// \endcode
03621 /// =>
03622 /// \code
03623 /// %ld = load i32* %addr
03624 /// %zext = zext i32 %ld to i64
03625 /// %add = add nuw i64 %zext, 4
03626 /// \encode
03627 /// Thanks to the promotion, we can match zext(load i32*) to i64.
03628 bool CodeGenPrepare::ExtLdPromotion(TypePromotionTransaction &TPT,
03629                                     LoadInst *&LI, Instruction *&Inst,
03630                                     const SmallVectorImpl<Instruction *> &Exts,
03631                                     unsigned CreatedInstsCost = 0) {
03632   // Iterate over all the extensions to see if one form an ext(load).
03633   for (auto I : Exts) {
03634     // Check if we directly have ext(load).
03635     if ((LI = dyn_cast<LoadInst>(I->getOperand(0)))) {
03636       Inst = I;
03637       // No promotion happened here.
03638       return false;
03639     }
03640     // Check whether or not we want to do any promotion.
03641     if (!TLI || !TLI->enableExtLdPromotion() || DisableExtLdPromotion)
03642       continue;
03643     // Get the action to perform the promotion.
03644     TypePromotionHelper::Action TPH = TypePromotionHelper::getAction(
03645         I, InsertedTruncsSet, *TLI, PromotedInsts);
03646     // Check if we can promote.
03647     if (!TPH)
03648       continue;
03649     // Save the current state.
03650     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
03651         TPT.getRestorationPoint();
03652     SmallVector<Instruction *, 4> NewExts;
03653     unsigned NewCreatedInstsCost = 0;
03654     unsigned ExtCost = !TLI->isExtFree(I);
03655     // Promote.
03656     Value *PromotedVal = TPH(I, TPT, PromotedInsts, NewCreatedInstsCost,
03657                              &NewExts, nullptr, *TLI);
03658     assert(PromotedVal &&
03659            "TypePromotionHelper should have filtered out those cases");
03660 
03661     // We would be able to merge only one extension in a load.
03662     // Therefore, if we have more than 1 new extension we heuristically
03663     // cut this search path, because it means we degrade the code quality.
03664     // With exactly 2, the transformation is neutral, because we will merge
03665     // one extension but leave one. However, we optimistically keep going,
03666     // because the new extension may be removed too.
03667     long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
03668     TotalCreatedInstsCost -= ExtCost;
03669     if (!StressExtLdPromotion &&
03670         (TotalCreatedInstsCost > 1 ||
03671          !isPromotedInstructionLegal(*TLI, PromotedVal))) {
03672       // The promotion is not profitable, rollback to the previous state.
03673       TPT.rollback(LastKnownGood);
03674       continue;
03675     }
03676     // The promotion is profitable.
03677     // Check if it exposes an ext(load).
03678     (void)ExtLdPromotion(TPT, LI, Inst, NewExts, TotalCreatedInstsCost);
03679     if (LI && (StressExtLdPromotion || NewCreatedInstsCost <= ExtCost ||
03680                // If we have created a new extension, i.e., now we have two
03681                // extensions. We must make sure one of them is merged with
03682                // the load, otherwise we may degrade the code quality.
03683                (LI->hasOneUse() || hasSameExtUse(LI, *TLI))))
03684       // Promotion happened.
03685       return true;
03686     // If this does not help to expose an ext(load) then, rollback.
03687     TPT.rollback(LastKnownGood);
03688   }
03689   // None of the extension can form an ext(load).
03690   LI = nullptr;
03691   Inst = nullptr;
03692   return false;
03693 }
03694 
03695 /// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same
03696 /// basic block as the load, unless conditions are unfavorable. This allows
03697 /// SelectionDAG to fold the extend into the load.
03698 /// \p I[in/out] the extension may be modified during the process if some
03699 /// promotions apply.
03700 ///
03701 bool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *&I) {
03702   // Try to promote a chain of computation if it allows to form
03703   // an extended load.
03704   TypePromotionTransaction TPT;
03705   TypePromotionTransaction::ConstRestorationPt LastKnownGood =
03706     TPT.getRestorationPoint();
03707   SmallVector<Instruction *, 1> Exts;
03708   Exts.push_back(I);
03709   // Look for a load being extended.
03710   LoadInst *LI = nullptr;
03711   Instruction *OldExt = I;
03712   bool HasPromoted = ExtLdPromotion(TPT, LI, I, Exts);
03713   if (!LI || !I) {
03714     assert(!HasPromoted && !LI && "If we did not match any load instruction "
03715                                   "the code must remain the same");
03716     I = OldExt;
03717     return false;
03718   }
03719 
03720   // If they're already in the same block, there's nothing to do.
03721   // Make the cheap checks first if we did not promote.
03722   // If we promoted, we need to check if it is indeed profitable.
03723   if (!HasPromoted && LI->getParent() == I->getParent())
03724     return false;
03725 
03726   EVT VT = TLI->getValueType(I->getType());
03727   EVT LoadVT = TLI->getValueType(LI->getType());
03728 
03729   // If the load has other users and the truncate is not free, this probably
03730   // isn't worthwhile.
03731   if (!LI->hasOneUse() && TLI &&
03732       (TLI->isTypeLegal(LoadVT) || !TLI->isTypeLegal(VT)) &&
03733       !TLI->isTruncateFree(I->getType(), LI->getType())) {
03734     I = OldExt;
03735     TPT.rollback(LastKnownGood);
03736     return false;
03737   }
03738 
03739   // Check whether the target supports casts folded into loads.
03740   unsigned LType;
03741   if (isa<ZExtInst>(I))
03742     LType = ISD::ZEXTLOAD;
03743   else {
03744     assert(isa<SExtInst>(I) && "Unexpected ext type!");
03745     LType = ISD::SEXTLOAD;
03746   }
03747   if (TLI && !TLI->isLoadExtLegal(LType, VT, LoadVT)) {
03748     I = OldExt;
03749     TPT.rollback(LastKnownGood);
03750     return false;
03751   }
03752 
03753   // Move the extend into the same block as the load, so that SelectionDAG
03754   // can fold it.
03755   TPT.commit();
03756   I->removeFromParent();
03757   I->insertAfter(LI);
03758   ++NumExtsMoved;
03759   return true;
03760 }
03761 
03762 bool CodeGenPrepare::OptimizeExtUses(Instruction *I) {
03763   BasicBlock *DefBB = I->getParent();
03764 
03765   // If the result of a {s|z}ext and its source are both live out, rewrite all
03766   // other uses of the source with result of extension.
03767   Value *Src = I->getOperand(0);
03768   if (Src->hasOneUse())
03769     return false;
03770 
03771   // Only do this xform if truncating is free.
03772   if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType()))
03773     return false;
03774 
03775   // Only safe to perform the optimization if the source is also defined in
03776   // this block.
03777   if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent())
03778     return false;
03779 
03780   bool DefIsLiveOut = false;
03781   for (User *U : I->users()) {
03782     Instruction *UI = cast<Instruction>(U);
03783 
03784     // Figure out which BB this ext is used in.
03785     BasicBlock *UserBB = UI->getParent();
03786     if (UserBB == DefBB) continue;
03787     DefIsLiveOut = true;
03788     break;
03789   }
03790   if (!DefIsLiveOut)
03791     return false;
03792 
03793   // Make sure none of the uses are PHI nodes.
03794   for (User *U : Src->users()) {
03795     Instruction *UI = cast<Instruction>(U);
03796     BasicBlock *UserBB = UI->getParent();
03797     if (UserBB == DefBB) continue;
03798     // Be conservative. We don't want this xform to end up introducing
03799     // reloads just before load / store instructions.
03800     if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI))
03801       return false;
03802   }
03803 
03804   // InsertedTruncs - Only insert one trunc in each block once.
03805   DenseMap<BasicBlock*, Instruction*> InsertedTruncs;
03806 
03807   bool MadeChange = false;
03808   for (Use &U : Src->uses()) {
03809     Instruction *User = cast<Instruction>(U.getUser());
03810 
03811     // Figure out which BB this ext is used in.
03812     BasicBlock *UserBB = User->getParent();
03813     if (UserBB == DefBB) continue;
03814 
03815     // Both src and def are live in this block. Rewrite the use.
03816     Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
03817 
03818     if (!InsertedTrunc) {
03819       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
03820       InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt);
03821       InsertedTruncsSet.insert(InsertedTrunc);
03822     }
03823 
03824     // Replace a use of the {s|z}ext source with a use of the result.
03825     U = InsertedTrunc;
03826     ++NumExtUses;
03827     MadeChange = true;
03828   }
03829 
03830   return MadeChange;
03831 }
03832 
03833 /// isFormingBranchFromSelectProfitable - Returns true if a SelectInst should be
03834 /// turned into an explicit branch.
03835 static bool isFormingBranchFromSelectProfitable(SelectInst *SI) {
03836   // FIXME: This should use the same heuristics as IfConversion to determine
03837   // whether a select is better represented as a branch.  This requires that
03838   // branch probability metadata is preserved for the select, which is not the
03839   // case currently.
03840 
03841   CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
03842 
03843   // If the branch is predicted right, an out of order CPU can avoid blocking on
03844   // the compare.  Emit cmovs on compares with a memory operand as branches to
03845   // avoid stalls on the load from memory.  If the compare has more than one use
03846   // there's probably another cmov or setcc around so it's not worth emitting a
03847   // branch.
03848   if (!Cmp)
03849     return false;
03850 
03851   Value *CmpOp0 = Cmp->getOperand(0);
03852   Value *CmpOp1 = Cmp->getOperand(1);
03853 
03854   // We check that the memory operand has one use to avoid uses of the loaded
03855   // value directly after the compare, making branches unprofitable.
03856   return Cmp->hasOneUse() &&
03857          ((isa<LoadInst>(CmpOp0) && CmpOp0->hasOneUse()) ||
03858           (isa<LoadInst>(CmpOp1) && CmpOp1->hasOneUse()));
03859 }
03860 
03861 
03862 /// If we have a SelectInst that will likely profit from branch prediction,
03863 /// turn it into a branch.
03864 bool CodeGenPrepare::OptimizeSelectInst(SelectInst *SI) {
03865   bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
03866 
03867   // Can we convert the 'select' to CF ?
03868   if (DisableSelectToBranch || OptSize || !TLI || VectorCond)
03869     return false;
03870 
03871   TargetLowering::SelectSupportKind SelectKind;
03872   if (VectorCond)
03873     SelectKind = TargetLowering::VectorMaskSelect;
03874   else if (SI->getType()->isVectorTy())
03875     SelectKind = TargetLowering::ScalarCondVectorVal;
03876   else
03877     SelectKind = TargetLowering::ScalarValSelect;
03878 
03879   // Do we have efficient codegen support for this kind of 'selects' ?
03880   if (TLI->isSelectSupported(SelectKind)) {
03881     // We have efficient codegen support for the select instruction.
03882     // Check if it is profitable to keep this 'select'.
03883     if (!TLI->isPredictableSelectExpensive() ||
03884         !isFormingBranchFromSelectProfitable(SI))
03885       return false;
03886   }
03887 
03888   ModifiedDT = true;
03889 
03890   // First, we split the block containing the select into 2 blocks.
03891   BasicBlock *StartBlock = SI->getParent();
03892   BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(SI));
03893   BasicBlock *NextBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");
03894 
03895   // Create a new block serving as the landing pad for the branch.
03896   BasicBlock *SmallBlock = BasicBlock::Create(SI->getContext(), "select.mid",
03897                                              NextBlock->getParent(), NextBlock);
03898 
03899   // Move the unconditional branch from the block with the select in it into our
03900   // landing pad block.
03901   StartBlock->getTerminator()->eraseFromParent();
03902   BranchInst::Create(NextBlock, SmallBlock);
03903 
03904   // Insert the real conditional branch based on the original condition.
03905   BranchInst::Create(NextBlock, SmallBlock, SI->getCondition(), SI);
03906 
03907   // The select itself is replaced with a PHI Node.
03908   PHINode *PN = PHINode::Create(SI->getType(), 2, "", NextBlock->begin());
03909   PN->takeName(SI);
03910   PN->addIncoming(SI->getTrueValue(), StartBlock);
03911   PN->addIncoming(SI->getFalseValue(), SmallBlock);
03912   SI->replaceAllUsesWith(PN);
03913   SI->eraseFromParent();
03914 
03915   // Instruct OptimizeBlock to skip to the next block.
03916   CurInstIterator = StartBlock->end();
03917   ++NumSelectsExpanded;
03918   return true;
03919 }
03920 
03921 static bool isBroadcastShuffle(ShuffleVectorInst *SVI) {
03922   SmallVector<int, 16> Mask(SVI->getShuffleMask());
03923   int SplatElem = -1;
03924   for (unsigned i = 0; i < Mask.size(); ++i) {
03925     if (SplatElem != -1 && Mask[i] != -1 && Mask[i] != SplatElem)
03926       return false;
03927     SplatElem = Mask[i];
03928   }
03929 
03930   return true;
03931 }
03932 
03933 /// Some targets have expensive vector shifts if the lanes aren't all the same
03934 /// (e.g. x86 only introduced "vpsllvd" and friends with AVX2). In these cases
03935 /// it's often worth sinking a shufflevector splat down to its use so that
03936 /// codegen can spot all lanes are identical.
03937 bool CodeGenPrepare::OptimizeShuffleVectorInst(ShuffleVectorInst *SVI) {
03938   BasicBlock *DefBB = SVI->getParent();
03939 
03940   // Only do this xform if variable vector shifts are particularly expensive.
03941   if (!TLI || !TLI->isVectorShiftByScalarCheap(SVI->getType()))
03942     return false;
03943 
03944   // We only expect better codegen by sinking a shuffle if we can recognise a
03945   // constant splat.
03946   if (!isBroadcastShuffle(SVI))
03947     return false;
03948 
03949   // InsertedShuffles - Only insert a shuffle in each block once.
03950   DenseMap<BasicBlock*, Instruction*> InsertedShuffles;
03951 
03952   bool MadeChange = false;
03953   for (User *U : SVI->users()) {
03954     Instruction *UI = cast<Instruction>(U);
03955 
03956     // Figure out which BB this ext is used in.
03957     BasicBlock *UserBB = UI->getParent();
03958     if (UserBB == DefBB) continue;
03959 
03960     // For now only apply this when the splat is used by a shift instruction.
03961     if (!UI->isShift()) continue;
03962 
03963     // Everything checks out, sink the shuffle if the user's block doesn't
03964     // already have a copy.
03965     Instruction *&InsertedShuffle = InsertedShuffles[UserBB];
03966 
03967     if (!InsertedShuffle) {
03968       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
03969       InsertedShuffle = new ShuffleVectorInst(SVI->getOperand(0),
03970                                               SVI->getOperand(1),
03971                                               SVI->getOperand(2), "", InsertPt);
03972     }
03973 
03974     UI->replaceUsesOfWith(SVI, InsertedShuffle);
03975     MadeChange = true;
03976   }
03977 
03978   // If we removed all uses, nuke the shuffle.
03979   if (SVI->use_empty()) {
03980     SVI->eraseFromParent();
03981     MadeChange = true;
03982   }
03983 
03984   return MadeChange;
03985 }
03986 
03987 namespace {
03988 /// \brief Helper class to promote a scalar operation to a vector one.
03989 /// This class is used to move downward extractelement transition.
03990 /// E.g.,
03991 /// a = vector_op <2 x i32>
03992 /// b = extractelement <2 x i32> a, i32 0
03993 /// c = scalar_op b
03994 /// store c
03995 ///
03996 /// =>
03997 /// a = vector_op <2 x i32>
03998 /// c = vector_op a (equivalent to scalar_op on the related lane)
03999 /// * d = extractelement <2 x i32> c, i32 0
04000 /// * store d
04001 /// Assuming both extractelement and store can be combine, we get rid of the
04002 /// transition.
04003 class VectorPromoteHelper {
04004   /// Used to perform some checks on the legality of vector operations.
04005   const TargetLowering &TLI;
04006 
04007   /// Used to estimated the cost of the promoted chain.
04008   const TargetTransformInfo &TTI;
04009 
04010   /// The transition being moved downwards.
04011   Instruction *Transition;
04012   /// The sequence of instructions to be promoted.
04013   SmallVector<Instruction *, 4> InstsToBePromoted;
04014   /// Cost of combining a store and an extract.
04015   unsigned StoreExtractCombineCost;
04016   /// Instruction that will be combined with the transition.
04017   Instruction *CombineInst;
04018 
04019   /// \brief The instruction that represents the current end of the transition.
04020   /// Since we are faking the promotion until we reach the end of the chain
04021   /// of computation, we need a way to get the current end of the transition.
04022   Instruction *getEndOfTransition() const {
04023     if (InstsToBePromoted.empty())
04024       return Transition;
04025     return InstsToBePromoted.back();
04026   }
04027 
04028   /// \brief Return the index of the original value in the transition.
04029   /// E.g., for "extractelement <2 x i32> c, i32 1" the original value,
04030   /// c, is at index 0.
04031   unsigned getTransitionOriginalValueIdx() const {
04032     assert(isa<ExtractElementInst>(Transition) &&
04033            "Other kind of transitions are not supported yet");
04034     return 0;
04035   }
04036 
04037   /// \brief Return the index of the index in the transition.
04038   /// E.g., for "extractelement <2 x i32> c, i32 0" the index
04039   /// is at index 1.
04040   unsigned getTransitionIdx() const {
04041     assert(isa<ExtractElementInst>(Transition) &&
04042            "Other kind of transitions are not supported yet");
04043     return 1;
04044   }
04045 
04046   /// \brief Get the type of the transition.
04047   /// This is the type of the original value.
04048   /// E.g., for "extractelement <2 x i32> c, i32 1" the type of the
04049   /// transition is <2 x i32>.
04050   Type *getTransitionType() const {
04051     return Transition->getOperand(getTransitionOriginalValueIdx())->getType();
04052   }
04053 
04054   /// \brief Promote \p ToBePromoted by moving \p Def downward through.
04055   /// I.e., we have the following sequence:
04056   /// Def = Transition <ty1> a to <ty2>
04057   /// b = ToBePromoted <ty2> Def, ...
04058   /// =>
04059   /// b = ToBePromoted <ty1> a, ...
04060   /// Def = Transition <ty1> ToBePromoted to <ty2>
04061   void promoteImpl(Instruction *ToBePromoted);
04062 
04063   /// \brief Check whether or not it is profitable to promote all the
04064   /// instructions enqueued to be promoted.
04065   bool isProfitableToPromote() {
04066     Value *ValIdx = Transition->getOperand(getTransitionOriginalValueIdx());
04067     unsigned Index = isa<ConstantInt>(ValIdx)
04068                          ? cast<ConstantInt>(ValIdx)->getZExtValue()
04069                          : -1;
04070     Type *PromotedType = getTransitionType();
04071 
04072     StoreInst *ST = cast<StoreInst>(CombineInst);
04073     unsigned AS = ST->getPointerAddressSpace();
04074     unsigned Align = ST->getAlignment();
04075     // Check if this store is supported.
04076     if (!TLI.allowsMisalignedMemoryAccesses(
04077             TLI.getValueType(ST->getValueOperand()->getType()), AS, Align)) {
04078       // If this is not supported, there is no way we can combine
04079       // the extract with the store.
04080       return false;
04081     }
04082 
04083     // The scalar chain of computation has to pay for the transition
04084     // scalar to vector.
04085     // The vector chain has to account for the combining cost.
04086     uint64_t ScalarCost =
04087         TTI.getVectorInstrCost(Transition->getOpcode(), PromotedType, Index);
04088     uint64_t VectorCost = StoreExtractCombineCost;
04089     for (const auto &Inst : InstsToBePromoted) {
04090       // Compute the cost.
04091       // By construction, all instructions being promoted are arithmetic ones.
04092       // Moreover, one argument is a constant that can be viewed as a splat
04093       // constant.
04094       Value *Arg0 = Inst->getOperand(0);
04095       bool IsArg0Constant = isa<UndefValue>(Arg0) || isa<ConstantInt>(Arg0) ||
04096                             isa<ConstantFP>(Arg0);
04097       TargetTransformInfo::OperandValueKind Arg0OVK =
04098           IsArg0Constant ? TargetTransformInfo::OK_UniformConstantValue
04099                          : TargetTransformInfo::OK_AnyValue;
04100       TargetTransformInfo::OperandValueKind Arg1OVK =
04101           !IsArg0Constant ? TargetTransformInfo::OK_UniformConstantValue
04102                           : TargetTransformInfo::OK_AnyValue;
04103       ScalarCost += TTI.getArithmeticInstrCost(
04104           Inst->getOpcode(), Inst->getType(), Arg0OVK, Arg1OVK);
04105       VectorCost += TTI.getArithmeticInstrCost(Inst->getOpcode(), PromotedType,
04106                                                Arg0OVK, Arg1OVK);
04107     }
04108     DEBUG(dbgs() << "Estimated cost of computation to be promoted:\nScalar: "
04109                  << ScalarCost << "\nVector: " << VectorCost << '\n');
04110     return ScalarCost > VectorCost;
04111   }
04112 
04113   /// \brief Generate a constant vector with \p Val with the same
04114   /// number of elements as the transition.
04115   /// \p UseSplat defines whether or not \p Val should be replicated
04116   /// accross the whole vector.
04117   /// In other words, if UseSplat == true, we generate <Val, Val, ..., Val>,
04118   /// otherwise we generate a vector with as many undef as possible:
04119   /// <undef, ..., undef, Val, undef, ..., undef> where \p Val is only
04120   /// used at the index of the extract.
04121   Value *getConstantVector(Constant *Val, bool UseSplat) const {
04122     unsigned ExtractIdx = UINT_MAX;
04123     if (!UseSplat) {
04124       // If we cannot determine where the constant must be, we have to
04125       // use a splat constant.
04126       Value *ValExtractIdx = Transition->getOperand(getTransitionIdx());
04127       if (ConstantInt *CstVal = dyn_cast<ConstantInt>(ValExtractIdx))
04128         ExtractIdx = CstVal->getSExtValue();
04129       else
04130         UseSplat = true;
04131     }
04132 
04133     unsigned End = getTransitionType()->getVectorNumElements();
04134     if (UseSplat)
04135       return ConstantVector::getSplat(End, Val);
04136 
04137     SmallVector<Constant *, 4> ConstVec;
04138     UndefValue *UndefVal = UndefValue::get(Val->getType());
04139     for (unsigned Idx = 0; Idx != End; ++Idx) {
04140       if (Idx == ExtractIdx)
04141         ConstVec.push_back(Val);
04142       else
04143         ConstVec.push_back(UndefVal);
04144     }
04145     return ConstantVector::get(ConstVec);
04146   }
04147 
04148   /// \brief Check if promoting to a vector type an operand at \p OperandIdx
04149   /// in \p Use can trigger undefined behavior.
04150   static bool canCauseUndefinedBehavior(const Instruction *Use,
04151                                         unsigned OperandIdx) {
04152     // This is not safe to introduce undef when the operand is on
04153     // the right hand side of a division-like instruction.
04154     if (OperandIdx != 1)
04155       return false;
04156     switch (Use->getOpcode()) {
04157     default:
04158       return false;
04159     case Instruction::SDiv:
04160     case Instruction::UDiv:
04161     case Instruction::SRem:
04162     case Instruction::URem:
04163       return true;
04164     case Instruction::FDiv:
04165     case Instruction::FRem:
04166       return !Use->hasNoNaNs();
04167     }
04168     llvm_unreachable(nullptr);
04169   }
04170 
04171 public:
04172   VectorPromoteHelper(const TargetLowering &TLI, const TargetTransformInfo &TTI,
04173                       Instruction *Transition, unsigned CombineCost)
04174       : TLI(TLI), TTI(TTI), Transition(Transition),
04175         StoreExtractCombineCost(CombineCost), CombineInst(nullptr) {
04176     assert(Transition && "Do not know how to promote null");
04177   }
04178 
04179   /// \brief Check if we can promote \p ToBePromoted to \p Type.
04180   bool canPromote(const Instruction *ToBePromoted) const {
04181     // We could support CastInst too.
04182     return isa<BinaryOperator>(ToBePromoted);
04183   }
04184 
04185   /// \brief Check if it is profitable to promote \p ToBePromoted
04186   /// by moving downward the transition through.
04187   bool shouldPromote(const Instruction *ToBePromoted) const {
04188     // Promote only if all the operands can be statically expanded.
04189     // Indeed, we do not want to introduce any new kind of transitions.
04190     for (const Use &U : ToBePromoted->operands()) {
04191       const Value *Val = U.get();
04192       if (Val == getEndOfTransition()) {
04193         // If the use is a division and the transition is on the rhs,
04194         // we cannot promote the operation, otherwise we may create a
04195         // division by zero.
04196         if (canCauseUndefinedBehavior(ToBePromoted, U.getOperandNo()))
04197           return false;
04198         continue;
04199       }
04200       if (!isa<ConstantInt>(Val) && !isa<UndefValue>(Val) &&
04201           !isa<ConstantFP>(Val))
04202         return false;
04203     }
04204     // Check that the resulting operation is legal.
04205     int ISDOpcode = TLI.InstructionOpcodeToISD(ToBePromoted->getOpcode());
04206     if (!ISDOpcode)
04207       return false;
04208     return StressStoreExtract ||
04209            TLI.isOperationLegalOrCustom(
04210                ISDOpcode, TLI.getValueType(getTransitionType(), true));
04211   }
04212 
04213   /// \brief Check whether or not \p Use can be combined
04214   /// with the transition.
04215   /// I.e., is it possible to do Use(Transition) => AnotherUse?
04216   bool canCombine(const Instruction *Use) { return isa<StoreInst>(Use); }
04217 
04218   /// \brief Record \p ToBePromoted as part of the chain to be promoted.
04219   void enqueueForPromotion(Instruction *ToBePromoted) {
04220     InstsToBePromoted.push_back(ToBePromoted);
04221   }
04222 
04223   /// \brief Set the instruction that will be combined with the transition.
04224   void recordCombineInstruction(Instruction *ToBeCombined) {
04225     assert(canCombine(ToBeCombined) && "Unsupported instruction to combine");
04226     CombineInst = ToBeCombined;
04227   }
04228 
04229   /// \brief Promote all the instructions enqueued for promotion if it is
04230   /// is profitable.
04231   /// \return True if the promotion happened, false otherwise.
04232   bool promote() {
04233     // Check if there is something to promote.
04234     // Right now, if we do not have anything to combine with,
04235     // we assume the promotion is not profitable.
04236     if (InstsToBePromoted.empty() || !CombineInst)
04237       return false;
04238 
04239     // Check cost.
04240     if (!StressStoreExtract && !isProfitableToPromote())
04241       return false;
04242 
04243     // Promote.
04244     for (auto &ToBePromoted : InstsToBePromoted)
04245       promoteImpl(ToBePromoted);
04246     InstsToBePromoted.clear();
04247     return true;
04248   }
04249 };
04250 } // End of anonymous namespace.
04251 
04252 void VectorPromoteHelper::promoteImpl(Instruction *ToBePromoted) {
04253   // At this point, we know that all the operands of ToBePromoted but Def
04254   // can be statically promoted.
04255   // For Def, we need to use its parameter in ToBePromoted:
04256   // b = ToBePromoted ty1 a
04257   // Def = Transition ty1 b to ty2
04258   // Move the transition down.
04259   // 1. Replace all uses of the promoted operation by the transition.
04260   // = ... b => = ... Def.
04261   assert(ToBePromoted->getType() == Transition->getType() &&
04262          "The type of the result of the transition does not match "
04263          "the final type");
04264   ToBePromoted->replaceAllUsesWith(Transition);
04265   // 2. Update the type of the uses.
04266   // b = ToBePromoted ty2 Def => b = ToBePromoted ty1 Def.
04267   Type *TransitionTy = getTransitionType();
04268   ToBePromoted->mutateType(TransitionTy);
04269   // 3. Update all the operands of the promoted operation with promoted
04270   // operands.
04271   // b = ToBePromoted ty1 Def => b = ToBePromoted ty1 a.
04272   for (Use &U : ToBePromoted->operands()) {
04273     Value *Val = U.get();
04274     Value *NewVal = nullptr;
04275     if (Val == Transition)
04276       NewVal = Transition->getOperand(getTransitionOriginalValueIdx());
04277     else if (isa<UndefValue>(Val) || isa<ConstantInt>(Val) ||
04278              isa<ConstantFP>(Val)) {
04279       // Use a splat constant if it is not safe to use undef.
04280       NewVal = getConstantVector(
04281           cast<Constant>(Val),
04282           isa<UndefValue>(Val) ||
04283               canCauseUndefinedBehavior(ToBePromoted, U.getOperandNo()));
04284     } else
04285       llvm_unreachable("Did you modified shouldPromote and forgot to update "
04286                        "this?");
04287     ToBePromoted->setOperand(U.getOperandNo(), NewVal);
04288   }
04289   Transition->removeFromParent();
04290   Transition->insertAfter(ToBePromoted);
04291   Transition->setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
04292 }
04293 
04294 /// Some targets can do store(extractelement) with one instruction.
04295 /// Try to push the extractelement towards the stores when the target
04296 /// has this feature and this is profitable.
04297 bool CodeGenPrepare::OptimizeExtractElementInst(Instruction *Inst) {
04298   unsigned CombineCost = UINT_MAX;
04299   if (DisableStoreExtract || !TLI ||
04300       (!StressStoreExtract &&
04301        !TLI->canCombineStoreAndExtract(Inst->getOperand(0)->getType(),
04302                                        Inst->getOperand(1), CombineCost)))
04303     return false;
04304 
04305   // At this point we know that Inst is a vector to scalar transition.
04306   // Try to move it down the def-use chain, until:
04307   // - We can combine the transition with its single use
04308   //   => we got rid of the transition.
04309   // - We escape the current basic block
04310   //   => we would need to check that we are moving it at a cheaper place and
04311   //      we do not do that for now.
04312   BasicBlock *Parent = Inst->getParent();
04313   DEBUG(dbgs() << "Found an interesting transition: " << *Inst << '\n');
04314   VectorPromoteHelper VPH(*TLI, *TTI, Inst, CombineCost);
04315   // If the transition has more than one use, assume this is not going to be
04316   // beneficial.
04317   while (Inst->hasOneUse()) {
04318     Instruction *ToBePromoted = cast<Instruction>(*Inst->user_begin());
04319     DEBUG(dbgs() << "Use: " << *ToBePromoted << '\n');
04320 
04321     if (ToBePromoted->getParent() != Parent) {
04322       DEBUG(dbgs() << "Instruction to promote is in a different block ("
04323                    << ToBePromoted->getParent()->getName()
04324                    << ") than the transition (" << Parent->getName() << ").\n");
04325       return false;
04326     }
04327 
04328     if (VPH.canCombine(ToBePromoted)) {
04329       DEBUG(dbgs() << "Assume " << *Inst << '\n'
04330                    << "will be combined with: " << *ToBePromoted << '\n');
04331       VPH.recordCombineInstruction(ToBePromoted);
04332       bool Changed = VPH.promote();
04333       NumStoreExtractExposed += Changed;
04334       return Changed;
04335     }
04336 
04337     DEBUG(dbgs() << "Try promoting.\n");
04338     if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
04339       return false;
04340 
04341     DEBUG(dbgs() << "Promoting is possible... Enqueue for promotion!\n");
04342 
04343     VPH.enqueueForPromotion(ToBePromoted);
04344     Inst = ToBePromoted;
04345   }
04346   return false;
04347 }
04348 
04349 bool CodeGenPrepare::OptimizeInst(Instruction *I, bool& ModifiedDT) {
04350   if (PHINode *P = dyn_cast<PHINode>(I)) {
04351     // It is possible for very late stage optimizations (such as SimplifyCFG)
04352     // to introduce PHI nodes too late to be cleaned up.  If we detect such a
04353     // trivial PHI, go ahead and zap it here.
04354     const DataLayout &DL = I->getModule()->getDataLayout();
04355     if (Value *V = SimplifyInstruction(P, DL, TLInfo, nullptr)) {
04356       P->replaceAllUsesWith(V);
04357       P->eraseFromParent();
04358       ++NumPHIsElim;
04359       return true;
04360     }
04361     return false;
04362   }
04363 
04364   if (CastInst *CI = dyn_cast<CastInst>(I)) {
04365     // If the source of the cast is a constant, then this should have
04366     // already been constant folded.  The only reason NOT to constant fold
04367     // it is if something (e.g. LSR) was careful to place the constant
04368     // evaluation in a block other than then one that uses it (e.g. to hoist
04369     // the address of globals out of a loop).  If this is the case, we don't
04370     // want to forward-subst the cast.
04371     if (isa<Constant>(CI->getOperand(0)))
04372       return false;
04373 
04374     if (TLI && OptimizeNoopCopyExpression(CI, *TLI))
04375       return true;
04376 
04377     if (isa<ZExtInst>(I) || isa<SExtInst>(I)) {
04378       /// Sink a zext or sext into its user blocks if the target type doesn't
04379       /// fit in one register
04380       if (TLI && TLI->getTypeAction(CI->getContext(),
04381                                     TLI->getValueType(CI->getType())) ==
04382                      TargetLowering::TypeExpandInteger) {
04383         return SinkCast(CI);
04384       } else {
04385         bool MadeChange = MoveExtToFormExtLoad(I);
04386         return MadeChange | OptimizeExtUses(I);
04387       }
04388     }
04389     return false;
04390   }
04391 
04392   if (CmpInst *CI = dyn_cast<CmpInst>(I))
04393     if (!TLI || !TLI->hasMultipleConditionRegisters())
04394       return OptimizeCmpExpression(CI);
04395 
04396   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
04397     if (TLI)
04398       return OptimizeMemoryInst(I, I->getOperand(0), LI->getType());
04399     return false;
04400   }
04401 
04402   if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
04403     if (TLI)
04404       return OptimizeMemoryInst(I, SI->getOperand(1),
04405                                 SI->getOperand(0)->getType());
04406     return false;
04407   }
04408 
04409   BinaryOperator *BinOp = dyn_cast<BinaryOperator>(I);
04410 
04411   if (BinOp && (BinOp->getOpcode() == Instruction::AShr ||
04412                 BinOp->getOpcode() == Instruction::LShr)) {
04413     ConstantInt *CI = dyn_cast<ConstantInt>(BinOp->getOperand(1));
04414     if (TLI && CI && TLI->hasExtractBitsInsn())
04415       return OptimizeExtractBits(BinOp, CI, *TLI);
04416 
04417     return false;
04418   }
04419 
04420   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
04421     if (GEPI->hasAllZeroIndices()) {
04422       /// The GEP operand must be a pointer, so must its result -> BitCast
04423       Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
04424                                         GEPI->getName(), GEPI);
04425       GEPI->replaceAllUsesWith(NC);
04426       GEPI->eraseFromParent();
04427       ++NumGEPsElim;
04428       OptimizeInst(NC, ModifiedDT);
04429       return true;
04430     }
04431     return false;
04432   }
04433 
04434   if (CallInst *CI = dyn_cast<CallInst>(I))
04435     return OptimizeCallInst(CI, ModifiedDT);
04436 
04437   if (SelectInst *SI = dyn_cast<SelectInst>(I))
04438     return OptimizeSelectInst(SI);
04439 
04440   if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I))
04441     return OptimizeShuffleVectorInst(SVI);
04442 
04443   if (isa<ExtractElementInst>(I))
04444     return OptimizeExtractElementInst(I);
04445 
04446   return false;
04447 }
04448 
04449 // In this pass we look for GEP and cast instructions that are used
04450 // across basic blocks and rewrite them to improve basic-block-at-a-time
04451 // selection.
04452 bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB, bool& ModifiedDT) {
04453   SunkAddrs.clear();
04454   bool MadeChange = false;
04455 
04456   CurInstIterator = BB.begin();
04457   while (CurInstIterator != BB.end()) {
04458     MadeChange |= OptimizeInst(CurInstIterator++, ModifiedDT);
04459     if (ModifiedDT)
04460       return true;
04461   }
04462   MadeChange |= DupRetToEnableTailCallOpts(&BB);
04463 
04464   return MadeChange;
04465 }
04466 
04467 // llvm.dbg.value is far away from the value then iSel may not be able
04468 // handle it properly. iSel will drop llvm.dbg.value if it can not
04469 // find a node corresponding to the value.
04470 bool CodeGenPrepare::PlaceDbgValues(Function &F) {
04471   bool MadeChange = false;
04472   for (BasicBlock &BB : F) {
04473     Instruction *PrevNonDbgInst = nullptr;
04474     for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
04475       Instruction *Insn = BI++;
04476       DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn);
04477       // Leave dbg.values that refer to an alloca alone. These
04478       // instrinsics describe the address of a variable (= the alloca)
04479       // being taken.  They should not be moved next to the alloca
04480       // (and to the beginning of the scope), but rather stay close to
04481       // where said address is used.
04482       if (!DVI || (DVI->getValue() && isa<AllocaInst>(DVI->getValue()))) {
04483         PrevNonDbgInst = Insn;
04484         continue;
04485       }
04486 
04487       Instruction *VI = dyn_cast_or_null<Instruction>(DVI->getValue());
04488       if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) {
04489         DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI);
04490         DVI->removeFromParent();
04491         if (isa<PHINode>(VI))
04492           DVI->insertBefore(VI->getParent()->getFirstInsertionPt());
04493         else
04494           DVI->insertAfter(VI);
04495         MadeChange = true;
04496         ++NumDbgValueMoved;
04497       }
04498     }
04499   }
04500   return MadeChange;
04501 }
04502 
04503 // If there is a sequence that branches based on comparing a single bit
04504 // against zero that can be combined into a single instruction, and the
04505 // target supports folding these into a single instruction, sink the
04506 // mask and compare into the branch uses. Do this before OptimizeBlock ->
04507 // OptimizeInst -> OptimizeCmpExpression, which perturbs the pattern being
04508 // searched for.
04509 bool CodeGenPrepare::sinkAndCmp(Function &F) {
04510   if (!EnableAndCmpSinking)
04511     return false;
04512   if (!TLI || !TLI->isMaskAndBranchFoldingLegal())
04513     return false;
04514   bool MadeChange = false;
04515   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
04516     BasicBlock *BB = I++;
04517 
04518     // Does this BB end with the following?
04519     //   %andVal = and %val, #single-bit-set
04520     //   %icmpVal = icmp %andResult, 0
04521     //   br i1 %cmpVal label %dest1, label %dest2"
04522     BranchInst *Brcc = dyn_cast<BranchInst>(BB->getTerminator());
04523     if (!Brcc || !Brcc->isConditional())
04524       continue;
04525     ICmpInst *Cmp = dyn_cast<ICmpInst>(Brcc->getOperand(0));
04526     if (!Cmp || Cmp->getParent() != BB)
04527       continue;
04528     ConstantInt *Zero = dyn_cast<ConstantInt>(Cmp->getOperand(1));
04529     if (!Zero || !Zero->isZero())
04530       continue;
04531     Instruction *And = dyn_cast<Instruction>(Cmp->getOperand(0));
04532     if (!And || And->getOpcode() != Instruction::And || And->getParent() != BB)
04533       continue;
04534     ConstantInt* Mask = dyn_cast<ConstantInt>(And->getOperand(1));
04535     if (!Mask || !Mask->getUniqueInteger().isPowerOf2())
04536       continue;
04537     DEBUG(dbgs() << "found and; icmp ?,0; brcc\n"); DEBUG(BB->dump());
04538 
04539     // Push the "and; icmp" for any users that are conditional branches.
04540     // Since there can only be one branch use per BB, we don't need to keep
04541     // track of which BBs we insert into.
04542     for (Value::use_iterator UI = Cmp->use_begin(), E = Cmp->use_end();
04543          UI != E; ) {
04544       Use &TheUse = *UI;
04545       // Find brcc use.
04546       BranchInst *BrccUser = dyn_cast<BranchInst>(*UI);
04547       ++UI;
04548       if (!BrccUser || !BrccUser->isConditional())
04549         continue;
04550       BasicBlock *UserBB = BrccUser->getParent();
04551       if (UserBB == BB) continue;
04552       DEBUG(dbgs() << "found Brcc use\n");
04553 
04554       // Sink the "and; icmp" to use.
04555       MadeChange = true;
04556       BinaryOperator *NewAnd =
04557         BinaryOperator::CreateAnd(And->getOperand(0), And->getOperand(1), "",
04558                                   BrccUser);
04559       CmpInst *NewCmp =
04560         CmpInst::Create(Cmp->getOpcode(), Cmp->getPredicate(), NewAnd, Zero,
04561                         "", BrccUser);
04562       TheUse = NewCmp;
04563       ++NumAndCmpsMoved;
04564       DEBUG(BrccUser->getParent()->dump());
04565     }
04566   }
04567   return MadeChange;
04568 }
04569 
04570 /// \brief Retrieve the probabilities of a conditional branch. Returns true on
04571 /// success, or returns false if no or invalid metadata was found.
04572 static bool extractBranchMetadata(BranchInst *BI,
04573                                   uint64_t &ProbTrue, uint64_t &ProbFalse) {
04574   assert(BI->isConditional() &&
04575          "Looking for probabilities on unconditional branch?");
04576   auto *ProfileData = BI->getMetadata(LLVMContext::MD_prof);
04577   if (!ProfileData || ProfileData->getNumOperands() != 3)
04578     return false;
04579 
04580   const auto *CITrue =
04581       mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1));
04582   const auto *CIFalse =
04583       mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2));
04584   if (!CITrue || !CIFalse)
04585     return false;
04586 
04587   ProbTrue = CITrue->getValue().getZExtValue();
04588   ProbFalse = CIFalse->getValue().getZExtValue();
04589 
04590   return true;
04591 }
04592 
04593 /// \brief Scale down both weights to fit into uint32_t.
04594 static void scaleWeights(uint64_t &NewTrue, uint64_t &NewFalse) {
04595   uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
04596   uint32_t Scale = (NewMax / UINT32_MAX) + 1;
04597   NewTrue = NewTrue / Scale;
04598   NewFalse = NewFalse / Scale;
04599 }
04600 
04601 /// \brief Some targets prefer to split a conditional branch like:
04602 /// \code
04603 ///   %0 = icmp ne i32 %a, 0
04604 ///   %1 = icmp ne i32 %b, 0
04605 ///   %or.cond = or i1 %0, %1
04606 ///   br i1 %or.cond, label %TrueBB, label %FalseBB
04607 /// \endcode
04608 /// into multiple branch instructions like:
04609 /// \code
04610 ///   bb1:
04611 ///     %0 = icmp ne i32 %a, 0
04612 ///     br i1 %0, label %TrueBB, label %bb2
04613 ///   bb2:
04614 ///     %1 = icmp ne i32 %b, 0
04615 ///     br i1 %1, label %TrueBB, label %FalseBB
04616 /// \endcode
04617 /// This usually allows instruction selection to do even further optimizations
04618 /// and combine the compare with the branch instruction. Currently this is
04619 /// applied for targets which have "cheap" jump instructions.
04620 ///
04621 /// FIXME: Remove the (equivalent?) implementation in SelectionDAG.
04622 ///
04623 bool CodeGenPrepare::splitBranchCondition(Function &F) {
04624   if (!TM || !TM->Options.EnableFastISel || !TLI || TLI->isJumpExpensive())
04625     return false;
04626 
04627   bool MadeChange = false;
04628   for (auto &BB : F) {
04629     // Does this BB end with the following?
04630     //   %cond1 = icmp|fcmp|binary instruction ...
04631     //   %cond2 = icmp|fcmp|binary instruction ...
04632     //   %cond.or = or|and i1 %cond1, cond2
04633     //   br i1 %cond.or label %dest1, label %dest2"
04634     BinaryOperator *LogicOp;
04635     BasicBlock *TBB, *FBB;
04636     if (!match(BB.getTerminator(), m_Br(m_OneUse(m_BinOp(LogicOp)), TBB, FBB)))
04637       continue;
04638 
04639     unsigned Opc;
04640     Value *Cond1, *Cond2;
04641     if (match(LogicOp, m_And(m_OneUse(m_Value(Cond1)),
04642                              m_OneUse(m_Value(Cond2)))))
04643       Opc = Instruction::And;
04644     else if (match(LogicOp, m_Or(m_OneUse(m_Value(Cond1)),
04645                                  m_OneUse(m_Value(Cond2)))))
04646       Opc = Instruction::Or;
04647     else
04648       continue;
04649 
04650     if (!match(Cond1, m_CombineOr(m_Cmp(), m_BinOp())) ||
04651         !match(Cond2, m_CombineOr(m_Cmp(), m_BinOp()))   )
04652       continue;
04653 
04654     DEBUG(dbgs() << "Before branch condition splitting\n"; BB.dump());
04655 
04656     // Create a new BB.
04657     auto *InsertBefore = std::next(Function::iterator(BB))
04658         .getNodePtrUnchecked();
04659     auto TmpBB = BasicBlock::Create(BB.getContext(),
04660                                     BB.getName() + ".cond.split",
04661                                     BB.getParent(), InsertBefore);
04662 
04663     // Update original basic block by using the first condition directly by the
04664     // branch instruction and removing the no longer needed and/or instruction.
04665     auto *Br1 = cast<BranchInst>(BB.getTerminator());
04666     Br1->setCondition(Cond1);
04667     LogicOp->eraseFromParent();
04668 
04669     // Depending on the conditon we have to either replace the true or the false
04670     // successor of the original branch instruction.
04671     if (Opc == Instruction::And)
04672       Br1->setSuccessor(0, TmpBB);
04673     else
04674       Br1->setSuccessor(1, TmpBB);
04675 
04676     // Fill in the new basic block.
04677     auto *Br2 = IRBuilder<>(TmpBB).CreateCondBr(Cond2, TBB, FBB);
04678     if (auto *I = dyn_cast<Instruction>(Cond2)) {
04679       I->removeFromParent();
04680       I->insertBefore(Br2);
04681     }
04682 
04683     // Update PHI nodes in both successors. The original BB needs to be
04684     // replaced in one succesor's PHI nodes, because the branch comes now from
04685     // the newly generated BB (NewBB). In the other successor we need to add one
04686     // incoming edge to the PHI nodes, because both branch instructions target
04687     // now the same successor. Depending on the original branch condition
04688     // (and/or) we have to swap the successors (TrueDest, FalseDest), so that
04689     // we perfrom the correct update for the PHI nodes.
04690     // This doesn't change the successor order of the just created branch
04691     // instruction (or any other instruction).
04692     if (Opc == Instruction::Or)
04693       std::swap(TBB, FBB);
04694 
04695     // Replace the old BB with the new BB.
04696     for (auto &I : *TBB) {
04697       PHINode *PN = dyn_cast<PHINode>(&I);
04698       if (!PN)
04699         break;
04700       int i;
04701       while ((i = PN->getBasicBlockIndex(&BB)) >= 0)
04702         PN->setIncomingBlock(i, TmpBB);
04703     }
04704 
04705     // Add another incoming edge form the new BB.
04706     for (auto &I : *FBB) {
04707       PHINode *PN = dyn_cast<PHINode>(&I);
04708       if (!PN)
04709         break;
04710       auto *Val = PN->getIncomingValueForBlock(&BB);
04711       PN->addIncoming(Val, TmpBB);
04712     }
04713 
04714     // Update the branch weights (from SelectionDAGBuilder::
04715     // FindMergedConditions).
04716     if (Opc == Instruction::Or) {
04717       // Codegen X | Y as:
04718       // BB1:
04719       //   jmp_if_X TBB
04720       //   jmp TmpBB
04721       // TmpBB:
04722       //   jmp_if_Y TBB
04723       //   jmp FBB
04724       //
04725 
04726       // We have flexibility in setting Prob for BB1 and Prob for NewBB.
04727       // The requirement is that
04728       //   TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB)
04729       //     = TrueProb for orignal BB.
04730       // Assuming the orignal weights are A and B, one choice is to set BB1's
04731       // weights to A and A+2B, and set TmpBB's weights to A and 2B. This choice
04732       // assumes that
04733       //   TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB.
04734       // Another choice is to assume TrueProb for BB1 equals to TrueProb for
04735       // TmpBB, but the math is more complicated.
04736       uint64_t TrueWeight, FalseWeight;
04737       if (extractBranchMetadata(Br1, TrueWeight, FalseWeight)) {
04738         uint64_t NewTrueWeight = TrueWeight;
04739         uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
04740         scaleWeights(NewTrueWeight, NewFalseWeight);
04741         Br1->setMetadata(LLVMContext::MD_prof, MDBuilder(Br1->getContext())
04742                          .createBranchWeights(TrueWeight, FalseWeight));
04743 
04744         NewTrueWeight = TrueWeight;
04745         NewFalseWeight = 2 * FalseWeight;
04746         scaleWeights(NewTrueWeight, NewFalseWeight);
04747         Br2->setMetadata(LLVMContext::MD_prof, MDBuilder(Br2->getContext())
04748                          .createBranchWeights(TrueWeight, FalseWeight));
04749       }
04750     } else {
04751       // Codegen X & Y as:
04752       // BB1:
04753       //   jmp_if_X TmpBB
04754       //   jmp FBB
04755       // TmpBB:
04756       //   jmp_if_Y TBB
04757       //   jmp FBB
04758       //
04759       //  This requires creation of TmpBB after CurBB.
04760 
04761       // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
04762       // The requirement is that
04763       //   FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB)
04764       //     = FalseProb for orignal BB.
04765       // Assuming the orignal weights are A and B, one choice is to set BB1's
04766       // weights to 2A+B and B, and set TmpBB's weights to 2A and B. This choice
04767       // assumes that
04768       //   FalseProb for BB1 == TrueProb for BB1 * FalseProb for TmpBB.
04769       uint64_t TrueWeight, FalseWeight;
04770       if (extractBranchMetadata(Br1, TrueWeight, FalseWeight)) {
04771         uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
04772         uint64_t NewFalseWeight = FalseWeight;
04773         scaleWeights(NewTrueWeight, NewFalseWeight);
04774         Br1->setMetadata(LLVMContext::MD_prof, MDBuilder(Br1->getContext())
04775                          .createBranchWeights(TrueWeight, FalseWeight));
04776 
04777         NewTrueWeight = 2 * TrueWeight;
04778         NewFalseWeight = FalseWeight;
04779         scaleWeights(NewTrueWeight, NewFalseWeight);
04780         Br2->setMetadata(LLVMContext::MD_prof, MDBuilder(Br2->getContext())
04781                          .createBranchWeights(TrueWeight, FalseWeight));
04782       }
04783     }
04784 
04785     // Note: No point in getting fancy here, since the DT info is never
04786     // available to CodeGenPrepare.
04787     ModifiedDT = true;
04788 
04789     MadeChange = true;
04790 
04791     DEBUG(dbgs() << "After branch condition splitting\n"; BB.dump();
04792           TmpBB->dump());
04793   }
04794   return MadeChange;
04795 }