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