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