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