LLVM API Documentation

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/IR/CallSite.h"
00022 #include "llvm/IR/Constants.h"
00023 #include "llvm/IR/DataLayout.h"
00024 #include "llvm/IR/DerivedTypes.h"
00025 #include "llvm/IR/Dominators.h"
00026 #include "llvm/IR/Function.h"
00027 #include "llvm/IR/GetElementPtrTypeIterator.h"
00028 #include "llvm/IR/IRBuilder.h"
00029 #include "llvm/IR/InlineAsm.h"
00030 #include "llvm/IR/Instructions.h"
00031 #include "llvm/IR/IntrinsicInst.h"
00032 #include "llvm/IR/PatternMatch.h"
00033 #include "llvm/IR/ValueHandle.h"
00034 #include "llvm/IR/ValueMap.h"
00035 #include "llvm/Pass.h"
00036 #include "llvm/Support/CommandLine.h"
00037 #include "llvm/Support/Debug.h"
00038 #include "llvm/Support/raw_ostream.h"
00039 #include "llvm/Target/TargetLibraryInfo.h"
00040 #include "llvm/Target/TargetLowering.h"
00041 #include "llvm/Target/TargetSubtargetInfo.h"
00042 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00043 #include "llvm/Transforms/Utils/BuildLibCalls.h"
00044 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
00045 #include "llvm/Transforms/Utils/Local.h"
00046 using namespace llvm;
00047 using namespace llvm::PatternMatch;
00048 
00049 #define DEBUG_TYPE "codegenprepare"
00050 
00051 STATISTIC(NumBlocksElim, "Number of blocks eliminated");
00052 STATISTIC(NumPHIsElim,   "Number of trivial PHIs eliminated");
00053 STATISTIC(NumGEPsElim,   "Number of GEPs converted to casts");
00054 STATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of "
00055                       "sunken Cmps");
00056 STATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses "
00057                        "of sunken Casts");
00058 STATISTIC(NumMemoryInsts, "Number of memory instructions whose address "
00059                           "computations were sunk");
00060 STATISTIC(NumExtsMoved,  "Number of [s|z]ext instructions combined with loads");
00061 STATISTIC(NumExtUses,    "Number of uses of [s|z]ext instructions optimized");
00062 STATISTIC(NumRetsDup,    "Number of return instructions duplicated");
00063 STATISTIC(NumDbgValueMoved, "Number of debug value instructions moved");
00064 STATISTIC(NumSelectsExpanded, "Number of selects turned into branches");
00065 STATISTIC(NumAndCmpsMoved, "Number of and/cmp's pushed into branches");
00066 
00067 static cl::opt<bool> DisableBranchOpts(
00068   "disable-cgp-branch-opts", cl::Hidden, cl::init(false),
00069   cl::desc("Disable branch optimizations in CodeGenPrepare"));
00070 
00071 static cl::opt<bool> DisableSelectToBranch(
00072   "disable-cgp-select2branch", cl::Hidden, cl::init(false),
00073   cl::desc("Disable select to branch conversion."));
00074 
00075 static cl::opt<bool> AddrSinkUsingGEPs(
00076   "addr-sink-using-gep", cl::Hidden, cl::init(false),
00077   cl::desc("Address sinking in CGP using GEPs."));
00078 
00079 static cl::opt<bool> EnableAndCmpSinking(
00080    "enable-andcmp-sinking", cl::Hidden, cl::init(true),
00081    cl::desc("Enable sinkinig and/cmp into branches."));
00082 
00083 namespace {
00084 typedef SmallPtrSet<Instruction *, 16> SetOfInstrs;
00085 typedef DenseMap<Instruction *, Type *> InstrToOrigTy;
00086 
00087   class CodeGenPrepare : public FunctionPass {
00088     /// TLI - Keep a pointer of a TargetLowering to consult for determining
00089     /// transformation profitability.
00090     const TargetMachine *TM;
00091     const TargetLowering *TLI;
00092     const TargetLibraryInfo *TLInfo;
00093     DominatorTree *DT;
00094 
00095     /// CurInstIterator - As we scan instructions optimizing them, this is the
00096     /// next instruction to optimize.  Xforms that can invalidate this should
00097     /// update it.
00098     BasicBlock::iterator CurInstIterator;
00099 
00100     /// Keeps track of non-local addresses that have been sunk into a block.
00101     /// This allows us to avoid inserting duplicate code for blocks with
00102     /// multiple load/stores of the same address.
00103     ValueMap<Value*, Value*> SunkAddrs;
00104 
00105     /// Keeps track of all truncates inserted for the current function.
00106     SetOfInstrs InsertedTruncsSet;
00107     /// Keeps track of the type of the related instruction before their
00108     /// promotion for the current function.
00109     InstrToOrigTy PromotedInsts;
00110 
00111     /// ModifiedDT - If CFG is modified in anyway, dominator tree may need to
00112     /// be updated.
00113     bool ModifiedDT;
00114 
00115     /// OptSize - True if optimizing for size.
00116     bool OptSize;
00117 
00118   public:
00119     static char ID; // Pass identification, replacement for typeid
00120     explicit CodeGenPrepare(const TargetMachine *TM = nullptr)
00121       : FunctionPass(ID), TM(TM), TLI(nullptr) {
00122         initializeCodeGenPreparePass(*PassRegistry::getPassRegistry());
00123       }
00124     bool runOnFunction(Function &F) override;
00125 
00126     const char *getPassName() const override { return "CodeGen Prepare"; }
00127 
00128     void getAnalysisUsage(AnalysisUsage &AU) const override {
00129       AU.addPreserved<DominatorTreeWrapperPass>();
00130       AU.addRequired<TargetLibraryInfo>();
00131     }
00132 
00133   private:
00134     bool EliminateFallThrough(Function &F);
00135     bool EliminateMostlyEmptyBlocks(Function &F);
00136     bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
00137     void EliminateMostlyEmptyBlock(BasicBlock *BB);
00138     bool OptimizeBlock(BasicBlock &BB);
00139     bool OptimizeInst(Instruction *I);
00140     bool OptimizeMemoryInst(Instruction *I, Value *Addr, Type *AccessTy);
00141     bool OptimizeInlineAsmInst(CallInst *CS);
00142     bool OptimizeCallInst(CallInst *CI);
00143     bool MoveExtToFormExtLoad(Instruction *I);
00144     bool OptimizeExtUses(Instruction *I);
00145     bool OptimizeSelectInst(SelectInst *SI);
00146     bool OptimizeShuffleVectorInst(ShuffleVectorInst *SI);
00147     bool DupRetToEnableTailCallOpts(BasicBlock *BB);
00148     bool PlaceDbgValues(Function &F);
00149     bool sinkAndCmp(Function &F);
00150   };
00151 }
00152 
00153 char CodeGenPrepare::ID = 0;
00154 INITIALIZE_TM_PASS(CodeGenPrepare, "codegenprepare",
00155                    "Optimize for code generation", false, false)
00156 
00157 FunctionPass *llvm::createCodeGenPreparePass(const TargetMachine *TM) {
00158   return new CodeGenPrepare(TM);
00159 }
00160 
00161 bool CodeGenPrepare::runOnFunction(Function &F) {
00162   if (skipOptnoneFunction(F))
00163     return false;
00164 
00165   bool EverMadeChange = false;
00166   // Clear per function information.
00167   InsertedTruncsSet.clear();
00168   PromotedInsts.clear();
00169 
00170   ModifiedDT = false;
00171   if (TM)
00172     TLI = TM->getSubtargetImpl()->getTargetLowering();
00173   TLInfo = &getAnalysis<TargetLibraryInfo>();
00174   DominatorTreeWrapperPass *DTWP =
00175       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
00176   DT = DTWP ? &DTWP->getDomTree() : nullptr;
00177   OptSize = F.getAttributes().hasAttribute(AttributeSet::FunctionIndex,
00178                                            Attribute::OptimizeForSize);
00179 
00180   /// This optimization identifies DIV instructions that can be
00181   /// profitably bypassed and carried out with a shorter, faster divide.
00182   if (!OptSize && TLI && TLI->isSlowDivBypassed()) {
00183     const DenseMap<unsigned int, unsigned int> &BypassWidths =
00184        TLI->getBypassSlowDivWidths();
00185     for (Function::iterator I = F.begin(); I != F.end(); I++)
00186       EverMadeChange |= bypassSlowDivision(F, I, BypassWidths);
00187   }
00188 
00189   // Eliminate blocks that contain only PHI nodes and an
00190   // unconditional branch.
00191   EverMadeChange |= EliminateMostlyEmptyBlocks(F);
00192 
00193   // llvm.dbg.value is far away from the value then iSel may not be able
00194   // handle it properly. iSel will drop llvm.dbg.value if it can not
00195   // find a node corresponding to the value.
00196   EverMadeChange |= PlaceDbgValues(F);
00197 
00198   // If there is a mask, compare against zero, and branch that can be combined
00199   // into a single target instruction, push the mask and compare into branch
00200   // users. Do this before OptimizeBlock -> OptimizeInst ->
00201   // OptimizeCmpExpression, which perturbs the pattern being searched for.
00202   if (!DisableBranchOpts)
00203     EverMadeChange |= sinkAndCmp(F);
00204 
00205   bool MadeChange = true;
00206   while (MadeChange) {
00207     MadeChange = false;
00208     for (Function::iterator I = F.begin(); I != F.end(); ) {
00209       BasicBlock *BB = I++;
00210       MadeChange |= OptimizeBlock(*BB);
00211     }
00212     EverMadeChange |= MadeChange;
00213   }
00214 
00215   SunkAddrs.clear();
00216 
00217   if (!DisableBranchOpts) {
00218     MadeChange = false;
00219     SmallPtrSet<BasicBlock*, 8> WorkList;
00220     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
00221       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
00222       MadeChange |= ConstantFoldTerminator(BB, true);
00223       if (!MadeChange) continue;
00224 
00225       for (SmallVectorImpl<BasicBlock*>::iterator
00226              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
00227         if (pred_begin(*II) == pred_end(*II))
00228           WorkList.insert(*II);
00229     }
00230 
00231     // Delete the dead blocks and any of their dead successors.
00232     MadeChange |= !WorkList.empty();
00233     while (!WorkList.empty()) {
00234       BasicBlock *BB = *WorkList.begin();
00235       WorkList.erase(BB);
00236       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
00237 
00238       DeleteDeadBlock(BB);
00239 
00240       for (SmallVectorImpl<BasicBlock*>::iterator
00241              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
00242         if (pred_begin(*II) == pred_end(*II))
00243           WorkList.insert(*II);
00244     }
00245 
00246     // Merge pairs of basic blocks with unconditional branches, connected by
00247     // a single edge.
00248     if (EverMadeChange || MadeChange)
00249       MadeChange |= EliminateFallThrough(F);
00250 
00251     if (MadeChange)
00252       ModifiedDT = true;
00253     EverMadeChange |= MadeChange;
00254   }
00255 
00256   if (ModifiedDT && DT)
00257     DT->recalculate(F);
00258 
00259   return EverMadeChange;
00260 }
00261 
00262 /// EliminateFallThrough - Merge basic blocks which are connected
00263 /// by a single edge, where one of the basic blocks has a single successor
00264 /// pointing to the other basic block, which has a single predecessor.
00265 bool CodeGenPrepare::EliminateFallThrough(Function &F) {
00266   bool Changed = false;
00267   // Scan all of the blocks in the function, except for the entry block.
00268   for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
00269     BasicBlock *BB = I++;
00270     // If the destination block has a single pred, then this is a trivial
00271     // edge, just collapse it.
00272     BasicBlock *SinglePred = BB->getSinglePredecessor();
00273 
00274     // Don't merge if BB's address is taken.
00275     if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
00276 
00277     BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
00278     if (Term && !Term->isConditional()) {
00279       Changed = true;
00280       DEBUG(dbgs() << "To merge:\n"<< *SinglePred << "\n\n\n");
00281       // Remember if SinglePred was the entry block of the function.
00282       // If so, we will need to move BB back to the entry position.
00283       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
00284       MergeBasicBlockIntoOnlyPred(BB, this);
00285 
00286       if (isEntry && BB != &BB->getParent()->getEntryBlock())
00287         BB->moveBefore(&BB->getParent()->getEntryBlock());
00288 
00289       // We have erased a block. Update the iterator.
00290       I = BB;
00291     }
00292   }
00293   return Changed;
00294 }
00295 
00296 /// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes,
00297 /// debug info directives, and an unconditional branch.  Passes before isel
00298 /// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for
00299 /// isel.  Start by eliminating these blocks so we can split them the way we
00300 /// want them.
00301 bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) {
00302   bool MadeChange = false;
00303   // Note that this intentionally skips the entry block.
00304   for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
00305     BasicBlock *BB = I++;
00306 
00307     // If this block doesn't end with an uncond branch, ignore it.
00308     BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
00309     if (!BI || !BI->isUnconditional())
00310       continue;
00311 
00312     // If the instruction before the branch (skipping debug info) isn't a phi
00313     // node, then other stuff is happening here.
00314     BasicBlock::iterator BBI = BI;
00315     if (BBI != BB->begin()) {
00316       --BBI;
00317       while (isa<DbgInfoIntrinsic>(BBI)) {
00318         if (BBI == BB->begin())
00319           break;
00320         --BBI;
00321       }
00322       if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
00323         continue;
00324     }
00325 
00326     // Do not break infinite loops.
00327     BasicBlock *DestBB = BI->getSuccessor(0);
00328     if (DestBB == BB)
00329       continue;
00330 
00331     if (!CanMergeBlocks(BB, DestBB))
00332       continue;
00333 
00334     EliminateMostlyEmptyBlock(BB);
00335     MadeChange = true;
00336   }
00337   return MadeChange;
00338 }
00339 
00340 /// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a
00341 /// single uncond branch between them, and BB contains no other non-phi
00342 /// instructions.
00343 bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB,
00344                                     const BasicBlock *DestBB) const {
00345   // We only want to eliminate blocks whose phi nodes are used by phi nodes in
00346   // the successor.  If there are more complex condition (e.g. preheaders),
00347   // don't mess around with them.
00348   BasicBlock::const_iterator BBI = BB->begin();
00349   while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
00350     for (const User *U : PN->users()) {
00351       const Instruction *UI = cast<Instruction>(U);
00352       if (UI->getParent() != DestBB || !isa<PHINode>(UI))
00353         return false;
00354       // If User is inside DestBB block and it is a PHINode then check
00355       // incoming value. If incoming value is not from BB then this is
00356       // a complex condition (e.g. preheaders) we want to avoid here.
00357       if (UI->getParent() == DestBB) {
00358         if (const PHINode *UPN = dyn_cast<PHINode>(UI))
00359           for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) {
00360             Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I));
00361             if (Insn && Insn->getParent() == BB &&
00362                 Insn->getParent() != UPN->getIncomingBlock(I))
00363               return false;
00364           }
00365       }
00366     }
00367   }
00368 
00369   // If BB and DestBB contain any common predecessors, then the phi nodes in BB
00370   // and DestBB may have conflicting incoming values for the block.  If so, we
00371   // can't merge the block.
00372   const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin());
00373   if (!DestBBPN) return true;  // no conflict.
00374 
00375   // Collect the preds of BB.
00376   SmallPtrSet<const BasicBlock*, 16> BBPreds;
00377   if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
00378     // It is faster to get preds from a PHI than with pred_iterator.
00379     for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
00380       BBPreds.insert(BBPN->getIncomingBlock(i));
00381   } else {
00382     BBPreds.insert(pred_begin(BB), pred_end(BB));
00383   }
00384 
00385   // Walk the preds of DestBB.
00386   for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) {
00387     BasicBlock *Pred = DestBBPN->getIncomingBlock(i);
00388     if (BBPreds.count(Pred)) {   // Common predecessor?
00389       BBI = DestBB->begin();
00390       while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
00391         const Value *V1 = PN->getIncomingValueForBlock(Pred);
00392         const Value *V2 = PN->getIncomingValueForBlock(BB);
00393 
00394         // If V2 is a phi node in BB, look up what the mapped value will be.
00395         if (const PHINode *V2PN = dyn_cast<PHINode>(V2))
00396           if (V2PN->getParent() == BB)
00397             V2 = V2PN->getIncomingValueForBlock(Pred);
00398 
00399         // If there is a conflict, bail out.
00400         if (V1 != V2) return false;
00401       }
00402     }
00403   }
00404 
00405   return true;
00406 }
00407 
00408 
00409 /// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and
00410 /// an unconditional branch in it.
00411 void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) {
00412   BranchInst *BI = cast<BranchInst>(BB->getTerminator());
00413   BasicBlock *DestBB = BI->getSuccessor(0);
00414 
00415   DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB);
00416 
00417   // If the destination block has a single pred, then this is a trivial edge,
00418   // just collapse it.
00419   if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
00420     if (SinglePred != DestBB) {
00421       // Remember if SinglePred was the entry block of the function.  If so, we
00422       // will need to move BB back to the entry position.
00423       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
00424       MergeBasicBlockIntoOnlyPred(DestBB, this);
00425 
00426       if (isEntry && BB != &BB->getParent()->getEntryBlock())
00427         BB->moveBefore(&BB->getParent()->getEntryBlock());
00428 
00429       DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
00430       return;
00431     }
00432   }
00433 
00434   // Otherwise, we have multiple predecessors of BB.  Update the PHIs in DestBB
00435   // to handle the new incoming edges it is about to have.
00436   PHINode *PN;
00437   for (BasicBlock::iterator BBI = DestBB->begin();
00438        (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
00439     // Remove the incoming value for BB, and remember it.
00440     Value *InVal = PN->removeIncomingValue(BB, false);
00441 
00442     // Two options: either the InVal is a phi node defined in BB or it is some
00443     // value that dominates BB.
00444     PHINode *InValPhi = dyn_cast<PHINode>(InVal);
00445     if (InValPhi && InValPhi->getParent() == BB) {
00446       // Add all of the input values of the input PHI as inputs of this phi.
00447       for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i)
00448         PN->addIncoming(InValPhi->getIncomingValue(i),
00449                         InValPhi->getIncomingBlock(i));
00450     } else {
00451       // Otherwise, add one instance of the dominating value for each edge that
00452       // we will be adding.
00453       if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
00454         for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
00455           PN->addIncoming(InVal, BBPN->getIncomingBlock(i));
00456       } else {
00457         for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
00458           PN->addIncoming(InVal, *PI);
00459       }
00460     }
00461   }
00462 
00463   // The PHIs are now updated, change everything that refers to BB to use
00464   // DestBB and remove BB.
00465   BB->replaceAllUsesWith(DestBB);
00466   if (DT && !ModifiedDT) {
00467     BasicBlock *BBIDom  = DT->getNode(BB)->getIDom()->getBlock();
00468     BasicBlock *DestBBIDom = DT->getNode(DestBB)->getIDom()->getBlock();
00469     BasicBlock *NewIDom = DT->findNearestCommonDominator(BBIDom, DestBBIDom);
00470     DT->changeImmediateDominator(DestBB, NewIDom);
00471     DT->eraseNode(BB);
00472   }
00473   BB->eraseFromParent();
00474   ++NumBlocksElim;
00475 
00476   DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
00477 }
00478 
00479 /// SinkCast - Sink the specified cast instruction into its user blocks
00480 static bool SinkCast(CastInst *CI) {
00481   BasicBlock *DefBB = CI->getParent();
00482 
00483   /// InsertedCasts - Only insert a cast in each block once.
00484   DenseMap<BasicBlock*, CastInst*> InsertedCasts;
00485 
00486   bool MadeChange = false;
00487   for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
00488        UI != E; ) {
00489     Use &TheUse = UI.getUse();
00490     Instruction *User = cast<Instruction>(*UI);
00491 
00492     // Figure out which BB this cast is used in.  For PHI's this is the
00493     // appropriate predecessor block.
00494     BasicBlock *UserBB = User->getParent();
00495     if (PHINode *PN = dyn_cast<PHINode>(User)) {
00496       UserBB = PN->getIncomingBlock(TheUse);
00497     }
00498 
00499     // Preincrement use iterator so we don't invalidate it.
00500     ++UI;
00501 
00502     // If this user is in the same block as the cast, don't change the cast.
00503     if (UserBB == DefBB) continue;
00504 
00505     // If we have already inserted a cast into this block, use it.
00506     CastInst *&InsertedCast = InsertedCasts[UserBB];
00507 
00508     if (!InsertedCast) {
00509       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
00510       InsertedCast =
00511         CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "",
00512                          InsertPt);
00513       MadeChange = true;
00514     }
00515 
00516     // Replace a use of the cast with a use of the new cast.
00517     TheUse = InsertedCast;
00518     ++NumCastUses;
00519   }
00520 
00521   // If we removed all uses, nuke the cast.
00522   if (CI->use_empty()) {
00523     CI->eraseFromParent();
00524     MadeChange = true;
00525   }
00526 
00527   return MadeChange;
00528 }
00529 
00530 /// OptimizeNoopCopyExpression - If the specified cast instruction is a noop
00531 /// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC),
00532 /// sink it into user blocks to reduce the number of virtual
00533 /// registers that must be created and coalesced.
00534 ///
00535 /// Return true if any changes are made.
00536 ///
00537 static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){
00538   // If this is a noop copy,
00539   EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType());
00540   EVT DstVT = TLI.getValueType(CI->getType());
00541 
00542   // This is an fp<->int conversion?
00543   if (SrcVT.isInteger() != DstVT.isInteger())
00544     return false;
00545 
00546   // If this is an extension, it will be a zero or sign extension, which
00547   // isn't a noop.
00548   if (SrcVT.bitsLT(DstVT)) return false;
00549 
00550   // If these values will be promoted, find out what they will be promoted
00551   // to.  This helps us consider truncates on PPC as noop copies when they
00552   // are.
00553   if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
00554       TargetLowering::TypePromoteInteger)
00555     SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
00556   if (TLI.getTypeAction(CI->getContext(), DstVT) ==
00557       TargetLowering::TypePromoteInteger)
00558     DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
00559 
00560   // If, after promotion, these are the same types, this is a noop copy.
00561   if (SrcVT != DstVT)
00562     return false;
00563 
00564   return SinkCast(CI);
00565 }
00566 
00567 /// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce
00568 /// the number of virtual registers that must be created and coalesced.  This is
00569 /// a clear win except on targets with multiple condition code registers
00570 ///  (PowerPC), where it might lose; some adjustment may be wanted there.
00571 ///
00572 /// Return true if any changes are made.
00573 static bool OptimizeCmpExpression(CmpInst *CI) {
00574   BasicBlock *DefBB = CI->getParent();
00575 
00576   /// InsertedCmp - Only insert a cmp in each block once.
00577   DenseMap<BasicBlock*, CmpInst*> InsertedCmps;
00578 
00579   bool MadeChange = false;
00580   for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
00581        UI != E; ) {
00582     Use &TheUse = UI.getUse();
00583     Instruction *User = cast<Instruction>(*UI);
00584 
00585     // Preincrement use iterator so we don't invalidate it.
00586     ++UI;
00587 
00588     // Don't bother for PHI nodes.
00589     if (isa<PHINode>(User))
00590       continue;
00591 
00592     // Figure out which BB this cmp is used in.
00593     BasicBlock *UserBB = User->getParent();
00594 
00595     // If this user is in the same block as the cmp, don't change the cmp.
00596     if (UserBB == DefBB) continue;
00597 
00598     // If we have already inserted a cmp into this block, use it.
00599     CmpInst *&InsertedCmp = InsertedCmps[UserBB];
00600 
00601     if (!InsertedCmp) {
00602       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
00603       InsertedCmp =
00604         CmpInst::Create(CI->getOpcode(),
00605                         CI->getPredicate(),  CI->getOperand(0),
00606                         CI->getOperand(1), "", InsertPt);
00607       MadeChange = true;
00608     }
00609 
00610     // Replace a use of the cmp with a use of the new cmp.
00611     TheUse = InsertedCmp;
00612     ++NumCmpUses;
00613   }
00614 
00615   // If we removed all uses, nuke the cmp.
00616   if (CI->use_empty())
00617     CI->eraseFromParent();
00618 
00619   return MadeChange;
00620 }
00621 
00622 /// isExtractBitsCandidateUse - Check if the candidates could
00623 /// be combined with shift instruction, which includes:
00624 /// 1. Truncate instruction
00625 /// 2. And instruction and the imm is a mask of the low bits:
00626 /// imm & (imm+1) == 0
00627 static bool isExtractBitsCandidateUse(Instruction *User) {
00628   if (!isa<TruncInst>(User)) {
00629     if (User->getOpcode() != Instruction::And ||
00630         !isa<ConstantInt>(User->getOperand(1)))
00631       return false;
00632 
00633     const APInt &Cimm = cast<ConstantInt>(User->getOperand(1))->getValue();
00634 
00635     if ((Cimm & (Cimm + 1)).getBoolValue())
00636       return false;
00637   }
00638   return true;
00639 }
00640 
00641 /// SinkShiftAndTruncate - sink both shift and truncate instruction
00642 /// to the use of truncate's BB.
00643 static bool
00644 SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI,
00645                      DenseMap<BasicBlock *, BinaryOperator *> &InsertedShifts,
00646                      const TargetLowering &TLI) {
00647   BasicBlock *UserBB = User->getParent();
00648   DenseMap<BasicBlock *, CastInst *> InsertedTruncs;
00649   TruncInst *TruncI = dyn_cast<TruncInst>(User);
00650   bool MadeChange = false;
00651 
00652   for (Value::user_iterator TruncUI = TruncI->user_begin(),
00653                             TruncE = TruncI->user_end();
00654        TruncUI != TruncE;) {
00655 
00656     Use &TruncTheUse = TruncUI.getUse();
00657     Instruction *TruncUser = cast<Instruction>(*TruncUI);
00658     // Preincrement use iterator so we don't invalidate it.
00659 
00660     ++TruncUI;
00661 
00662     int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode());
00663     if (!ISDOpcode)
00664       continue;
00665 
00666     // If the use is actually a legal node, there will not be an
00667     // implicit truncate.
00668     // FIXME: always querying the result type is just an
00669     // approximation; some nodes' legality is determined by the
00670     // operand or other means. There's no good way to find out though.
00671     if (TLI.isOperationLegalOrCustom(ISDOpcode,
00672                                      EVT::getEVT(TruncUser->getType(), true)))
00673       continue;
00674 
00675     // Don't bother for PHI nodes.
00676     if (isa<PHINode>(TruncUser))
00677       continue;
00678 
00679     BasicBlock *TruncUserBB = TruncUser->getParent();
00680 
00681     if (UserBB == TruncUserBB)
00682       continue;
00683 
00684     BinaryOperator *&InsertedShift = InsertedShifts[TruncUserBB];
00685     CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
00686 
00687     if (!InsertedShift && !InsertedTrunc) {
00688       BasicBlock::iterator InsertPt = TruncUserBB->getFirstInsertionPt();
00689       // Sink the shift
00690       if (ShiftI->getOpcode() == Instruction::AShr)
00691         InsertedShift =
00692             BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, "", InsertPt);
00693       else
00694         InsertedShift =
00695             BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "", InsertPt);
00696 
00697       // Sink the trunc
00698       BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt();
00699       TruncInsertPt++;
00700 
00701       InsertedTrunc = CastInst::Create(TruncI->getOpcode(), InsertedShift,
00702                                        TruncI->getType(), "", TruncInsertPt);
00703 
00704       MadeChange = true;
00705 
00706       TruncTheUse = InsertedTrunc;
00707     }
00708   }
00709   return MadeChange;
00710 }
00711 
00712 /// OptimizeExtractBits - sink the shift *right* instruction into user blocks if
00713 /// the uses could potentially be combined with this shift instruction and
00714 /// generate BitExtract instruction. It will only be applied if the architecture
00715 /// supports BitExtract instruction. Here is an example:
00716 /// BB1:
00717 ///   %x.extract.shift = lshr i64 %arg1, 32
00718 /// BB2:
00719 ///   %x.extract.trunc = trunc i64 %x.extract.shift to i16
00720 /// ==>
00721 ///
00722 /// BB2:
00723 ///   %x.extract.shift.1 = lshr i64 %arg1, 32
00724 ///   %x.extract.trunc = trunc i64 %x.extract.shift.1 to i16
00725 ///
00726 /// CodeGen will recoginze the pattern in BB2 and generate BitExtract
00727 /// instruction.
00728 /// Return true if any changes are made.
00729 static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI,
00730                                 const TargetLowering &TLI) {
00731   BasicBlock *DefBB = ShiftI->getParent();
00732 
00733   /// Only insert instructions in each block once.
00734   DenseMap<BasicBlock *, BinaryOperator *> InsertedShifts;
00735 
00736   bool shiftIsLegal = TLI.isTypeLegal(TLI.getValueType(ShiftI->getType()));
00737 
00738   bool MadeChange = false;
00739   for (Value::user_iterator UI = ShiftI->user_begin(), E = ShiftI->user_end();
00740        UI != E;) {
00741     Use &TheUse = UI.getUse();
00742     Instruction *User = cast<Instruction>(*UI);
00743     // Preincrement use iterator so we don't invalidate it.
00744     ++UI;
00745 
00746     // Don't bother for PHI nodes.
00747     if (isa<PHINode>(User))
00748       continue;
00749 
00750     if (!isExtractBitsCandidateUse(User))
00751       continue;
00752 
00753     BasicBlock *UserBB = User->getParent();
00754 
00755     if (UserBB == DefBB) {
00756       // If the shift and truncate instruction are in the same BB. The use of
00757       // the truncate(TruncUse) may still introduce another truncate if not
00758       // legal. In this case, we would like to sink both shift and truncate
00759       // instruction to the BB of TruncUse.
00760       // for example:
00761       // BB1:
00762       // i64 shift.result = lshr i64 opnd, imm
00763       // trunc.result = trunc shift.result to i16
00764       //
00765       // BB2:
00766       //   ----> We will have an implicit truncate here if the architecture does
00767       //   not have i16 compare.
00768       // cmp i16 trunc.result, opnd2
00769       //
00770       if (isa<TruncInst>(User) && shiftIsLegal
00771           // If the type of the truncate is legal, no trucate will be
00772           // introduced in other basic blocks.
00773           && (!TLI.isTypeLegal(TLI.getValueType(User->getType()))))
00774         MadeChange =
00775             SinkShiftAndTruncate(ShiftI, User, CI, InsertedShifts, TLI);
00776 
00777       continue;
00778     }
00779     // If we have already inserted a shift into this block, use it.
00780     BinaryOperator *&InsertedShift = InsertedShifts[UserBB];
00781 
00782     if (!InsertedShift) {
00783       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
00784 
00785       if (ShiftI->getOpcode() == Instruction::AShr)
00786         InsertedShift =
00787             BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, "", InsertPt);
00788       else
00789         InsertedShift =
00790             BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, "", InsertPt);
00791 
00792       MadeChange = true;
00793     }
00794 
00795     // Replace a use of the shift with a use of the new shift.
00796     TheUse = InsertedShift;
00797   }
00798 
00799   // If we removed all uses, nuke the shift.
00800   if (ShiftI->use_empty())
00801     ShiftI->eraseFromParent();
00802 
00803   return MadeChange;
00804 }
00805 
00806 namespace {
00807 class CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls {
00808 protected:
00809   void replaceCall(Value *With) override {
00810     CI->replaceAllUsesWith(With);
00811     CI->eraseFromParent();
00812   }
00813   bool isFoldable(unsigned SizeCIOp, unsigned, bool) const override {
00814       if (ConstantInt *SizeCI =
00815                              dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp)))
00816         return SizeCI->isAllOnesValue();
00817     return false;
00818   }
00819 };
00820 } // end anonymous namespace
00821 
00822 bool CodeGenPrepare::OptimizeCallInst(CallInst *CI) {
00823   BasicBlock *BB = CI->getParent();
00824 
00825   // Lower inline assembly if we can.
00826   // If we found an inline asm expession, and if the target knows how to
00827   // lower it to normal LLVM code, do so now.
00828   if (TLI && isa<InlineAsm>(CI->getCalledValue())) {
00829     if (TLI->ExpandInlineAsm(CI)) {
00830       // Avoid invalidating the iterator.
00831       CurInstIterator = BB->begin();
00832       // Avoid processing instructions out of order, which could cause
00833       // reuse before a value is defined.
00834       SunkAddrs.clear();
00835       return true;
00836     }
00837     // Sink address computing for memory operands into the block.
00838     if (OptimizeInlineAsmInst(CI))
00839       return true;
00840   }
00841 
00842   // Lower all uses of llvm.objectsize.*
00843   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
00844   if (II && II->getIntrinsicID() == Intrinsic::objectsize) {
00845     bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1);
00846     Type *ReturnTy = CI->getType();
00847     Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL);
00848 
00849     // Substituting this can cause recursive simplifications, which can
00850     // invalidate our iterator.  Use a WeakVH to hold onto it in case this
00851     // happens.
00852     WeakVH IterHandle(CurInstIterator);
00853 
00854     replaceAndRecursivelySimplify(CI, RetVal,
00855                                   TLI ? TLI->getDataLayout() : nullptr,
00856                                   TLInfo, ModifiedDT ? nullptr : DT);
00857 
00858     // If the iterator instruction was recursively deleted, start over at the
00859     // start of the block.
00860     if (IterHandle != CurInstIterator) {
00861       CurInstIterator = BB->begin();
00862       SunkAddrs.clear();
00863     }
00864     return true;
00865   }
00866 
00867   if (II && TLI) {
00868     SmallVector<Value*, 2> PtrOps;
00869     Type *AccessTy;
00870     if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy))
00871       while (!PtrOps.empty())
00872         if (OptimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy))
00873           return true;
00874   }
00875 
00876   // From here on out we're working with named functions.
00877   if (!CI->getCalledFunction()) return false;
00878 
00879   // We'll need DataLayout from here on out.
00880   const DataLayout *TD = TLI ? TLI->getDataLayout() : nullptr;
00881   if (!TD) return false;
00882 
00883   // Lower all default uses of _chk calls.  This is very similar
00884   // to what InstCombineCalls does, but here we are only lowering calls
00885   // that have the default "don't know" as the objectsize.  Anything else
00886   // should be left alone.
00887   CodeGenPrepareFortifiedLibCalls Simplifier;
00888   return Simplifier.fold(CI, TD, TLInfo);
00889 }
00890 
00891 /// DupRetToEnableTailCallOpts - Look for opportunities to duplicate return
00892 /// instructions to the predecessor to enable tail call optimizations. The
00893 /// case it is currently looking for is:
00894 /// @code
00895 /// bb0:
00896 ///   %tmp0 = tail call i32 @f0()
00897 ///   br label %return
00898 /// bb1:
00899 ///   %tmp1 = tail call i32 @f1()
00900 ///   br label %return
00901 /// bb2:
00902 ///   %tmp2 = tail call i32 @f2()
00903 ///   br label %return
00904 /// return:
00905 ///   %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ]
00906 ///   ret i32 %retval
00907 /// @endcode
00908 ///
00909 /// =>
00910 ///
00911 /// @code
00912 /// bb0:
00913 ///   %tmp0 = tail call i32 @f0()
00914 ///   ret i32 %tmp0
00915 /// bb1:
00916 ///   %tmp1 = tail call i32 @f1()
00917 ///   ret i32 %tmp1
00918 /// bb2:
00919 ///   %tmp2 = tail call i32 @f2()
00920 ///   ret i32 %tmp2
00921 /// @endcode
00922 bool CodeGenPrepare::DupRetToEnableTailCallOpts(BasicBlock *BB) {
00923   if (!TLI)
00924     return false;
00925 
00926   ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator());
00927   if (!RI)
00928     return false;
00929 
00930   PHINode *PN = nullptr;
00931   BitCastInst *BCI = nullptr;
00932   Value *V = RI->getReturnValue();
00933   if (V) {
00934     BCI = dyn_cast<BitCastInst>(V);
00935     if (BCI)
00936       V = BCI->getOperand(0);
00937 
00938     PN = dyn_cast<PHINode>(V);
00939     if (!PN)
00940       return false;
00941   }
00942 
00943   if (PN && PN->getParent() != BB)
00944     return false;
00945 
00946   // It's not safe to eliminate the sign / zero extension of the return value.
00947   // See llvm::isInTailCallPosition().
00948   const Function *F = BB->getParent();
00949   AttributeSet CallerAttrs = F->getAttributes();
00950   if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) ||
00951       CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt))
00952     return false;
00953 
00954   // Make sure there are no instructions between the PHI and return, or that the
00955   // return is the first instruction in the block.
00956   if (PN) {
00957     BasicBlock::iterator BI = BB->begin();
00958     do { ++BI; } while (isa<DbgInfoIntrinsic>(BI));
00959     if (&*BI == BCI)
00960       // Also skip over the bitcast.
00961       ++BI;
00962     if (&*BI != RI)
00963       return false;
00964   } else {
00965     BasicBlock::iterator BI = BB->begin();
00966     while (isa<DbgInfoIntrinsic>(BI)) ++BI;
00967     if (&*BI != RI)
00968       return false;
00969   }
00970 
00971   /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail
00972   /// call.
00973   SmallVector<CallInst*, 4> TailCalls;
00974   if (PN) {
00975     for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
00976       CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I));
00977       // Make sure the phi value is indeed produced by the tail call.
00978       if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) &&
00979           TLI->mayBeEmittedAsTailCall(CI))
00980         TailCalls.push_back(CI);
00981     }
00982   } else {
00983     SmallPtrSet<BasicBlock*, 4> VisitedBBs;
00984     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
00985       if (!VisitedBBs.insert(*PI))
00986         continue;
00987 
00988       BasicBlock::InstListType &InstList = (*PI)->getInstList();
00989       BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin();
00990       BasicBlock::InstListType::reverse_iterator RE = InstList.rend();
00991       do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI));
00992       if (RI == RE)
00993         continue;
00994 
00995       CallInst *CI = dyn_cast<CallInst>(&*RI);
00996       if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI))
00997         TailCalls.push_back(CI);
00998     }
00999   }
01000 
01001   bool Changed = false;
01002   for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) {
01003     CallInst *CI = TailCalls[i];
01004     CallSite CS(CI);
01005 
01006     // Conservatively require the attributes of the call to match those of the
01007     // return. Ignore noalias because it doesn't affect the call sequence.
01008     AttributeSet CalleeAttrs = CS.getAttributes();
01009     if (AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
01010           removeAttribute(Attribute::NoAlias) !=
01011         AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
01012           removeAttribute(Attribute::NoAlias))
01013       continue;
01014 
01015     // Make sure the call instruction is followed by an unconditional branch to
01016     // the return block.
01017     BasicBlock *CallBB = CI->getParent();
01018     BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator());
01019     if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
01020       continue;
01021 
01022     // Duplicate the return into CallBB.
01023     (void)FoldReturnIntoUncondBranch(RI, BB, CallBB);
01024     ModifiedDT = Changed = true;
01025     ++NumRetsDup;
01026   }
01027 
01028   // If we eliminated all predecessors of the block, delete the block now.
01029   if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
01030     BB->eraseFromParent();
01031 
01032   return Changed;
01033 }
01034 
01035 //===----------------------------------------------------------------------===//
01036 // Memory Optimization
01037 //===----------------------------------------------------------------------===//
01038 
01039 namespace {
01040 
01041 /// ExtAddrMode - This is an extended version of TargetLowering::AddrMode
01042 /// which holds actual Value*'s for register values.
01043 struct ExtAddrMode : public TargetLowering::AddrMode {
01044   Value *BaseReg;
01045   Value *ScaledReg;
01046   ExtAddrMode() : BaseReg(nullptr), ScaledReg(nullptr) {}
01047   void print(raw_ostream &OS) const;
01048   void dump() const;
01049 
01050   bool operator==(const ExtAddrMode& O) const {
01051     return (BaseReg == O.BaseReg) && (ScaledReg == O.ScaledReg) &&
01052            (BaseGV == O.BaseGV) && (BaseOffs == O.BaseOffs) &&
01053            (HasBaseReg == O.HasBaseReg) && (Scale == O.Scale);
01054   }
01055 };
01056 
01057 #ifndef NDEBUG
01058 static inline raw_ostream &operator<<(raw_ostream &OS, const ExtAddrMode &AM) {
01059   AM.print(OS);
01060   return OS;
01061 }
01062 #endif
01063 
01064 void ExtAddrMode::print(raw_ostream &OS) const {
01065   bool NeedPlus = false;
01066   OS << "[";
01067   if (BaseGV) {
01068     OS << (NeedPlus ? " + " : "")
01069        << "GV:";
01070     BaseGV->printAsOperand(OS, /*PrintType=*/false);
01071     NeedPlus = true;
01072   }
01073 
01074   if (BaseOffs) {
01075     OS << (NeedPlus ? " + " : "")
01076        << BaseOffs;
01077     NeedPlus = true;
01078   }
01079 
01080   if (BaseReg) {
01081     OS << (NeedPlus ? " + " : "")
01082        << "Base:";
01083     BaseReg->printAsOperand(OS, /*PrintType=*/false);
01084     NeedPlus = true;
01085   }
01086   if (Scale) {
01087     OS << (NeedPlus ? " + " : "")
01088        << Scale << "*";
01089     ScaledReg->printAsOperand(OS, /*PrintType=*/false);
01090   }
01091 
01092   OS << ']';
01093 }
01094 
01095 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
01096 void ExtAddrMode::dump() const {
01097   print(dbgs());
01098   dbgs() << '\n';
01099 }
01100 #endif
01101 
01102 /// \brief This class provides transaction based operation on the IR.
01103 /// Every change made through this class is recorded in the internal state and
01104 /// can be undone (rollback) until commit is called.
01105 class TypePromotionTransaction {
01106 
01107   /// \brief This represents the common interface of the individual transaction.
01108   /// Each class implements the logic for doing one specific modification on
01109   /// the IR via the TypePromotionTransaction.
01110   class TypePromotionAction {
01111   protected:
01112     /// The Instruction modified.
01113     Instruction *Inst;
01114 
01115   public:
01116     /// \brief Constructor of the action.
01117     /// The constructor performs the related action on the IR.
01118     TypePromotionAction(Instruction *Inst) : Inst(Inst) {}
01119 
01120     virtual ~TypePromotionAction() {}
01121 
01122     /// \brief Undo the modification done by this action.
01123     /// When this method is called, the IR must be in the same state as it was
01124     /// before this action was applied.
01125     /// \pre Undoing the action works if and only if the IR is in the exact same
01126     /// state as it was directly after this action was applied.
01127     virtual void undo() = 0;
01128 
01129     /// \brief Advocate every change made by this action.
01130     /// When the results on the IR of the action are to be kept, it is important
01131     /// to call this function, otherwise hidden information may be kept forever.
01132     virtual void commit() {
01133       // Nothing to be done, this action is not doing anything.
01134     }
01135   };
01136 
01137   /// \brief Utility to remember the position of an instruction.
01138   class InsertionHandler {
01139     /// Position of an instruction.
01140     /// Either an instruction:
01141     /// - Is the first in a basic block: BB is used.
01142     /// - Has a previous instructon: PrevInst is used.
01143     union {
01144       Instruction *PrevInst;
01145       BasicBlock *BB;
01146     } Point;
01147     /// Remember whether or not the instruction had a previous instruction.
01148     bool HasPrevInstruction;
01149 
01150   public:
01151     /// \brief Record the position of \p Inst.
01152     InsertionHandler(Instruction *Inst) {
01153       BasicBlock::iterator It = Inst;
01154       HasPrevInstruction = (It != (Inst->getParent()->begin()));
01155       if (HasPrevInstruction)
01156         Point.PrevInst = --It;
01157       else
01158         Point.BB = Inst->getParent();
01159     }
01160 
01161     /// \brief Insert \p Inst at the recorded position.
01162     void insert(Instruction *Inst) {
01163       if (HasPrevInstruction) {
01164         if (Inst->getParent())
01165           Inst->removeFromParent();
01166         Inst->insertAfter(Point.PrevInst);
01167       } else {
01168         Instruction *Position = Point.BB->getFirstInsertionPt();
01169         if (Inst->getParent())
01170           Inst->moveBefore(Position);
01171         else
01172           Inst->insertBefore(Position);
01173       }
01174     }
01175   };
01176 
01177   /// \brief Move an instruction before another.
01178   class InstructionMoveBefore : public TypePromotionAction {
01179     /// Original position of the instruction.
01180     InsertionHandler Position;
01181 
01182   public:
01183     /// \brief Move \p Inst before \p Before.
01184     InstructionMoveBefore(Instruction *Inst, Instruction *Before)
01185         : TypePromotionAction(Inst), Position(Inst) {
01186       DEBUG(dbgs() << "Do: move: " << *Inst << "\nbefore: " << *Before << "\n");
01187       Inst->moveBefore(Before);
01188     }
01189 
01190     /// \brief Move the instruction back to its original position.
01191     void undo() override {
01192       DEBUG(dbgs() << "Undo: moveBefore: " << *Inst << "\n");
01193       Position.insert(Inst);
01194     }
01195   };
01196 
01197   /// \brief Set the operand of an instruction with a new value.
01198   class OperandSetter : public TypePromotionAction {
01199     /// Original operand of the instruction.
01200     Value *Origin;
01201     /// Index of the modified instruction.
01202     unsigned Idx;
01203 
01204   public:
01205     /// \brief Set \p Idx operand of \p Inst with \p NewVal.
01206     OperandSetter(Instruction *Inst, unsigned Idx, Value *NewVal)
01207         : TypePromotionAction(Inst), Idx(Idx) {
01208       DEBUG(dbgs() << "Do: setOperand: " << Idx << "\n"
01209                    << "for:" << *Inst << "\n"
01210                    << "with:" << *NewVal << "\n");
01211       Origin = Inst->getOperand(Idx);
01212       Inst->setOperand(Idx, NewVal);
01213     }
01214 
01215     /// \brief Restore the original value of the instruction.
01216     void undo() override {
01217       DEBUG(dbgs() << "Undo: setOperand:" << Idx << "\n"
01218                    << "for: " << *Inst << "\n"
01219                    << "with: " << *Origin << "\n");
01220       Inst->setOperand(Idx, Origin);
01221     }
01222   };
01223 
01224   /// \brief Hide the operands of an instruction.
01225   /// Do as if this instruction was not using any of its operands.
01226   class OperandsHider : public TypePromotionAction {
01227     /// The list of original operands.
01228     SmallVector<Value *, 4> OriginalValues;
01229 
01230   public:
01231     /// \brief Remove \p Inst from the uses of the operands of \p Inst.
01232     OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) {
01233       DEBUG(dbgs() << "Do: OperandsHider: " << *Inst << "\n");
01234       unsigned NumOpnds = Inst->getNumOperands();
01235       OriginalValues.reserve(NumOpnds);
01236       for (unsigned It = 0; It < NumOpnds; ++It) {
01237         // Save the current operand.
01238         Value *Val = Inst->getOperand(It);
01239         OriginalValues.push_back(Val);
01240         // Set a dummy one.
01241         // We could use OperandSetter here, but that would implied an overhead
01242         // that we are not willing to pay.
01243         Inst->setOperand(It, UndefValue::get(Val->getType()));
01244       }
01245     }
01246 
01247     /// \brief Restore the original list of uses.
01248     void undo() override {
01249       DEBUG(dbgs() << "Undo: OperandsHider: " << *Inst << "\n");
01250       for (unsigned It = 0, EndIt = OriginalValues.size(); It != EndIt; ++It)
01251         Inst->setOperand(It, OriginalValues[It]);
01252     }
01253   };
01254 
01255   /// \brief Build a truncate instruction.
01256   class TruncBuilder : public TypePromotionAction {
01257   public:
01258     /// \brief Build a truncate instruction of \p Opnd producing a \p Ty
01259     /// result.
01260     /// trunc Opnd to Ty.
01261     TruncBuilder(Instruction *Opnd, Type *Ty) : TypePromotionAction(Opnd) {
01262       IRBuilder<> Builder(Opnd);
01263       Inst = cast<Instruction>(Builder.CreateTrunc(Opnd, Ty, "promoted"));
01264       DEBUG(dbgs() << "Do: TruncBuilder: " << *Inst << "\n");
01265     }
01266 
01267     /// \brief Get the built instruction.
01268     Instruction *getBuiltInstruction() { return Inst; }
01269 
01270     /// \brief Remove the built instruction.
01271     void undo() override {
01272       DEBUG(dbgs() << "Undo: TruncBuilder: " << *Inst << "\n");
01273       Inst->eraseFromParent();
01274     }
01275   };
01276 
01277   /// \brief Build a sign extension instruction.
01278   class SExtBuilder : public TypePromotionAction {
01279   public:
01280     /// \brief Build a sign extension instruction of \p Opnd producing a \p Ty
01281     /// result.
01282     /// sext Opnd to Ty.
01283     SExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
01284         : TypePromotionAction(Inst) {
01285       IRBuilder<> Builder(InsertPt);
01286       Inst = cast<Instruction>(Builder.CreateSExt(Opnd, Ty, "promoted"));
01287       DEBUG(dbgs() << "Do: SExtBuilder: " << *Inst << "\n");
01288     }
01289 
01290     /// \brief Get the built instruction.
01291     Instruction *getBuiltInstruction() { return Inst; }
01292 
01293     /// \brief Remove the built instruction.
01294     void undo() override {
01295       DEBUG(dbgs() << "Undo: SExtBuilder: " << *Inst << "\n");
01296       Inst->eraseFromParent();
01297     }
01298   };
01299 
01300   /// \brief Mutate an instruction to another type.
01301   class TypeMutator : public TypePromotionAction {
01302     /// Record the original type.
01303     Type *OrigTy;
01304 
01305   public:
01306     /// \brief Mutate the type of \p Inst into \p NewTy.
01307     TypeMutator(Instruction *Inst, Type *NewTy)
01308         : TypePromotionAction(Inst), OrigTy(Inst->getType()) {
01309       DEBUG(dbgs() << "Do: MutateType: " << *Inst << " with " << *NewTy
01310                    << "\n");
01311       Inst->mutateType(NewTy);
01312     }
01313 
01314     /// \brief Mutate the instruction back to its original type.
01315     void undo() override {
01316       DEBUG(dbgs() << "Undo: MutateType: " << *Inst << " with " << *OrigTy
01317                    << "\n");
01318       Inst->mutateType(OrigTy);
01319     }
01320   };
01321 
01322   /// \brief Replace the uses of an instruction by another instruction.
01323   class UsesReplacer : public TypePromotionAction {
01324     /// Helper structure to keep track of the replaced uses.
01325     struct InstructionAndIdx {
01326       /// The instruction using the instruction.
01327       Instruction *Inst;
01328       /// The index where this instruction is used for Inst.
01329       unsigned Idx;
01330       InstructionAndIdx(Instruction *Inst, unsigned Idx)
01331           : Inst(Inst), Idx(Idx) {}
01332     };
01333 
01334     /// Keep track of the original uses (pair Instruction, Index).
01335     SmallVector<InstructionAndIdx, 4> OriginalUses;
01336     typedef SmallVectorImpl<InstructionAndIdx>::iterator use_iterator;
01337 
01338   public:
01339     /// \brief Replace all the use of \p Inst by \p New.
01340     UsesReplacer(Instruction *Inst, Value *New) : TypePromotionAction(Inst) {
01341       DEBUG(dbgs() << "Do: UsersReplacer: " << *Inst << " with " << *New
01342                    << "\n");
01343       // Record the original uses.
01344       for (Use &U : Inst->uses()) {
01345         Instruction *UserI = cast<Instruction>(U.getUser());
01346         OriginalUses.push_back(InstructionAndIdx(UserI, U.getOperandNo()));
01347       }
01348       // Now, we can replace the uses.
01349       Inst->replaceAllUsesWith(New);
01350     }
01351 
01352     /// \brief Reassign the original uses of Inst to Inst.
01353     void undo() override {
01354       DEBUG(dbgs() << "Undo: UsersReplacer: " << *Inst << "\n");
01355       for (use_iterator UseIt = OriginalUses.begin(),
01356                         EndIt = OriginalUses.end();
01357            UseIt != EndIt; ++UseIt) {
01358         UseIt->Inst->setOperand(UseIt->Idx, Inst);
01359       }
01360     }
01361   };
01362 
01363   /// \brief Remove an instruction from the IR.
01364   class InstructionRemover : public TypePromotionAction {
01365     /// Original position of the instruction.
01366     InsertionHandler Inserter;
01367     /// Helper structure to hide all the link to the instruction. In other
01368     /// words, this helps to do as if the instruction was removed.
01369     OperandsHider Hider;
01370     /// Keep track of the uses replaced, if any.
01371     UsesReplacer *Replacer;
01372 
01373   public:
01374     /// \brief Remove all reference of \p Inst and optinally replace all its
01375     /// uses with New.
01376     /// \pre If !Inst->use_empty(), then New != nullptr
01377     InstructionRemover(Instruction *Inst, Value *New = nullptr)
01378         : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
01379           Replacer(nullptr) {
01380       if (New)
01381         Replacer = new UsesReplacer(Inst, New);
01382       DEBUG(dbgs() << "Do: InstructionRemover: " << *Inst << "\n");
01383       Inst->removeFromParent();
01384     }
01385 
01386     ~InstructionRemover() { delete Replacer; }
01387 
01388     /// \brief Really remove the instruction.
01389     void commit() override { delete Inst; }
01390 
01391     /// \brief Resurrect the instruction and reassign it to the proper uses if
01392     /// new value was provided when build this action.
01393     void undo() override {
01394       DEBUG(dbgs() << "Undo: InstructionRemover: " << *Inst << "\n");
01395       Inserter.insert(Inst);
01396       if (Replacer)
01397         Replacer->undo();
01398       Hider.undo();
01399     }
01400   };
01401 
01402 public:
01403   /// Restoration point.
01404   /// The restoration point is a pointer to an action instead of an iterator
01405   /// because the iterator may be invalidated but not the pointer.
01406   typedef const TypePromotionAction *ConstRestorationPt;
01407   /// Advocate every changes made in that transaction.
01408   void commit();
01409   /// Undo all the changes made after the given point.
01410   void rollback(ConstRestorationPt Point);
01411   /// Get the current restoration point.
01412   ConstRestorationPt getRestorationPoint() const;
01413 
01414   /// \name API for IR modification with state keeping to support rollback.
01415   /// @{
01416   /// Same as Instruction::setOperand.
01417   void setOperand(Instruction *Inst, unsigned Idx, Value *NewVal);
01418   /// Same as Instruction::eraseFromParent.
01419   void eraseInstruction(Instruction *Inst, Value *NewVal = nullptr);
01420   /// Same as Value::replaceAllUsesWith.
01421   void replaceAllUsesWith(Instruction *Inst, Value *New);
01422   /// Same as Value::mutateType.
01423   void mutateType(Instruction *Inst, Type *NewTy);
01424   /// Same as IRBuilder::createTrunc.
01425   Instruction *createTrunc(Instruction *Opnd, Type *Ty);
01426   /// Same as IRBuilder::createSExt.
01427   Instruction *createSExt(Instruction *Inst, Value *Opnd, Type *Ty);
01428   /// Same as Instruction::moveBefore.
01429   void moveBefore(Instruction *Inst, Instruction *Before);
01430   /// @}
01431 
01432 private:
01433   /// The ordered list of actions made so far.
01434   SmallVector<std::unique_ptr<TypePromotionAction>, 16> Actions;
01435   typedef SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator CommitPt;
01436 };
01437 
01438 void TypePromotionTransaction::setOperand(Instruction *Inst, unsigned Idx,
01439                                           Value *NewVal) {
01440   Actions.push_back(
01441       make_unique<TypePromotionTransaction::OperandSetter>(Inst, Idx, NewVal));
01442 }
01443 
01444 void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
01445                                                 Value *NewVal) {
01446   Actions.push_back(
01447       make_unique<TypePromotionTransaction::InstructionRemover>(Inst, NewVal));
01448 }
01449 
01450 void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
01451                                                   Value *New) {
01452   Actions.push_back(make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
01453 }
01454 
01455 void TypePromotionTransaction::mutateType(Instruction *Inst, Type *NewTy) {
01456   Actions.push_back(make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
01457 }
01458 
01459 Instruction *TypePromotionTransaction::createTrunc(Instruction *Opnd,
01460                                                    Type *Ty) {
01461   std::unique_ptr<TruncBuilder> Ptr(new TruncBuilder(Opnd, Ty));
01462   Instruction *I = Ptr->getBuiltInstruction();
01463   Actions.push_back(std::move(Ptr));
01464   return I;
01465 }
01466 
01467 Instruction *TypePromotionTransaction::createSExt(Instruction *Inst,
01468                                                   Value *Opnd, Type *Ty) {
01469   std::unique_ptr<SExtBuilder> Ptr(new SExtBuilder(Inst, Opnd, Ty));
01470   Instruction *I = Ptr->getBuiltInstruction();
01471   Actions.push_back(std::move(Ptr));
01472   return I;
01473 }
01474 
01475 void TypePromotionTransaction::moveBefore(Instruction *Inst,
01476                                           Instruction *Before) {
01477   Actions.push_back(
01478       make_unique<TypePromotionTransaction::InstructionMoveBefore>(Inst, Before));
01479 }
01480 
01481 TypePromotionTransaction::ConstRestorationPt
01482 TypePromotionTransaction::getRestorationPoint() const {
01483   return !Actions.empty() ? Actions.back().get() : nullptr;
01484 }
01485 
01486 void TypePromotionTransaction::commit() {
01487   for (CommitPt It = Actions.begin(), EndIt = Actions.end(); It != EndIt;
01488        ++It)
01489     (*It)->commit();
01490   Actions.clear();
01491 }
01492 
01493 void TypePromotionTransaction::rollback(
01494     TypePromotionTransaction::ConstRestorationPt Point) {
01495   while (!Actions.empty() && Point != Actions.back().get()) {
01496     std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
01497     Curr->undo();
01498   }
01499 }
01500 
01501 /// \brief A helper class for matching addressing modes.
01502 ///
01503 /// This encapsulates the logic for matching the target-legal addressing modes.
01504 class AddressingModeMatcher {
01505   SmallVectorImpl<Instruction*> &AddrModeInsts;
01506   const TargetLowering &TLI;
01507 
01508   /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and
01509   /// the memory instruction that we're computing this address for.
01510   Type *AccessTy;
01511   Instruction *MemoryInst;
01512 
01513   /// AddrMode - This is the addressing mode that we're building up.  This is
01514   /// part of the return value of this addressing mode matching stuff.
01515   ExtAddrMode &AddrMode;
01516 
01517   /// The truncate instruction inserted by other CodeGenPrepare optimizations.
01518   const SetOfInstrs &InsertedTruncs;
01519   /// A map from the instructions to their type before promotion.
01520   InstrToOrigTy &PromotedInsts;
01521   /// The ongoing transaction where every action should be registered.
01522   TypePromotionTransaction &TPT;
01523 
01524   /// IgnoreProfitability - This is set to true when we should not do
01525   /// profitability checks.  When true, IsProfitableToFoldIntoAddressingMode
01526   /// always returns true.
01527   bool IgnoreProfitability;
01528 
01529   AddressingModeMatcher(SmallVectorImpl<Instruction*> &AMI,
01530                         const TargetLowering &T, Type *AT,
01531                         Instruction *MI, ExtAddrMode &AM,
01532                         const SetOfInstrs &InsertedTruncs,
01533                         InstrToOrigTy &PromotedInsts,
01534                         TypePromotionTransaction &TPT)
01535       : AddrModeInsts(AMI), TLI(T), AccessTy(AT), MemoryInst(MI), AddrMode(AM),
01536         InsertedTruncs(InsertedTruncs), PromotedInsts(PromotedInsts), TPT(TPT) {
01537     IgnoreProfitability = false;
01538   }
01539 public:
01540 
01541   /// Match - Find the maximal addressing mode that a load/store of V can fold,
01542   /// give an access type of AccessTy.  This returns a list of involved
01543   /// instructions in AddrModeInsts.
01544   /// \p InsertedTruncs The truncate instruction inserted by other
01545   /// CodeGenPrepare
01546   /// optimizations.
01547   /// \p PromotedInsts maps the instructions to their type before promotion.
01548   /// \p The ongoing transaction where every action should be registered.
01549   static ExtAddrMode Match(Value *V, Type *AccessTy,
01550                            Instruction *MemoryInst,
01551                            SmallVectorImpl<Instruction*> &AddrModeInsts,
01552                            const TargetLowering &TLI,
01553                            const SetOfInstrs &InsertedTruncs,
01554                            InstrToOrigTy &PromotedInsts,
01555                            TypePromotionTransaction &TPT) {
01556     ExtAddrMode Result;
01557 
01558     bool Success = AddressingModeMatcher(AddrModeInsts, TLI, AccessTy,
01559                                          MemoryInst, Result, InsertedTruncs,
01560                                          PromotedInsts, TPT).MatchAddr(V, 0);
01561     (void)Success; assert(Success && "Couldn't select *anything*?");
01562     return Result;
01563   }
01564 private:
01565   bool MatchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth);
01566   bool MatchAddr(Value *V, unsigned Depth);
01567   bool MatchOperationAddr(User *Operation, unsigned Opcode, unsigned Depth,
01568                           bool *MovedAway = nullptr);
01569   bool IsProfitableToFoldIntoAddressingMode(Instruction *I,
01570                                             ExtAddrMode &AMBefore,
01571                                             ExtAddrMode &AMAfter);
01572   bool ValueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
01573   bool IsPromotionProfitable(unsigned MatchedSize, unsigned SizeWithPromotion,
01574                              Value *PromotedOperand) const;
01575 };
01576 
01577 /// MatchScaledValue - Try adding ScaleReg*Scale to the current addressing mode.
01578 /// Return true and update AddrMode if this addr mode is legal for the target,
01579 /// false if not.
01580 bool AddressingModeMatcher::MatchScaledValue(Value *ScaleReg, int64_t Scale,
01581                                              unsigned Depth) {
01582   // If Scale is 1, then this is the same as adding ScaleReg to the addressing
01583   // mode.  Just process that directly.
01584   if (Scale == 1)
01585     return MatchAddr(ScaleReg, Depth);
01586 
01587   // If the scale is 0, it takes nothing to add this.
01588   if (Scale == 0)
01589     return true;
01590 
01591   // If we already have a scale of this value, we can add to it, otherwise, we
01592   // need an available scale field.
01593   if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg)
01594     return false;
01595 
01596   ExtAddrMode TestAddrMode = AddrMode;
01597 
01598   // Add scale to turn X*4+X*3 -> X*7.  This could also do things like
01599   // [A+B + A*7] -> [B+A*8].
01600   TestAddrMode.Scale += Scale;
01601   TestAddrMode.ScaledReg = ScaleReg;
01602 
01603   // If the new address isn't legal, bail out.
01604   if (!TLI.isLegalAddressingMode(TestAddrMode, AccessTy))
01605     return false;
01606 
01607   // It was legal, so commit it.
01608   AddrMode = TestAddrMode;
01609 
01610   // Okay, we decided that we can add ScaleReg+Scale to AddrMode.  Check now
01611   // to see if ScaleReg is actually X+C.  If so, we can turn this into adding
01612   // X*Scale + C*Scale to addr mode.
01613   ConstantInt *CI = nullptr; Value *AddLHS = nullptr;
01614   if (isa<Instruction>(ScaleReg) &&  // not a constant expr.
01615       match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) {
01616     TestAddrMode.ScaledReg = AddLHS;
01617     TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale;
01618 
01619     // If this addressing mode is legal, commit it and remember that we folded
01620     // this instruction.
01621     if (TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) {
01622       AddrModeInsts.push_back(cast<Instruction>(ScaleReg));
01623       AddrMode = TestAddrMode;
01624       return true;
01625     }
01626   }
01627 
01628   // Otherwise, not (x+c)*scale, just return what we have.
01629   return true;
01630 }
01631 
01632 /// MightBeFoldableInst - This is a little filter, which returns true if an
01633 /// addressing computation involving I might be folded into a load/store
01634 /// accessing it.  This doesn't need to be perfect, but needs to accept at least
01635 /// the set of instructions that MatchOperationAddr can.
01636 static bool MightBeFoldableInst(Instruction *I) {
01637   switch (I->getOpcode()) {
01638   case Instruction::BitCast:
01639   case Instruction::AddrSpaceCast:
01640     // Don't touch identity bitcasts.
01641     if (I->getType() == I->getOperand(0)->getType())
01642       return false;
01643     return I->getType()->isPointerTy() || I->getType()->isIntegerTy();
01644   case Instruction::PtrToInt:
01645     // PtrToInt is always a noop, as we know that the int type is pointer sized.
01646     return true;
01647   case Instruction::IntToPtr:
01648     // We know the input is intptr_t, so this is foldable.
01649     return true;
01650   case Instruction::Add:
01651     return true;
01652   case Instruction::Mul:
01653   case Instruction::Shl:
01654     // Can only handle X*C and X << C.
01655     return isa<ConstantInt>(I->getOperand(1));
01656   case Instruction::GetElementPtr:
01657     return true;
01658   default:
01659     return false;
01660   }
01661 }
01662 
01663 /// \brief Hepler class to perform type promotion.
01664 class TypePromotionHelper {
01665   /// \brief Utility function to check whether or not a sign extension of
01666   /// \p Inst with \p ConsideredSExtType can be moved through \p Inst by either
01667   /// using the operands of \p Inst or promoting \p Inst.
01668   /// In other words, check if:
01669   /// sext (Ty Inst opnd1 opnd2 ... opndN) to ConsideredSExtType.
01670   /// #1 Promotion applies:
01671   /// ConsideredSExtType Inst (sext opnd1 to ConsideredSExtType, ...).
01672   /// #2 Operand reuses:
01673   /// sext opnd1 to ConsideredSExtType.
01674   /// \p PromotedInsts maps the instructions to their type before promotion.
01675   static bool canGetThrough(const Instruction *Inst, Type *ConsideredSExtType,
01676                             const InstrToOrigTy &PromotedInsts);
01677 
01678   /// \brief Utility function to determine if \p OpIdx should be promoted when
01679   /// promoting \p Inst.
01680   static bool shouldSExtOperand(const Instruction *Inst, int OpIdx) {
01681     if (isa<SelectInst>(Inst) && OpIdx == 0)
01682       return false;
01683     return true;
01684   }
01685 
01686   /// \brief Utility function to promote the operand of \p SExt when this
01687   /// operand is a promotable trunc or sext.
01688   /// \p PromotedInsts maps the instructions to their type before promotion.
01689   /// \p CreatedInsts[out] contains how many non-free instructions have been
01690   /// created to promote the operand of SExt.
01691   /// Should never be called directly.
01692   /// \return The promoted value which is used instead of SExt.
01693   static Value *promoteOperandForTruncAndSExt(Instruction *SExt,
01694                                               TypePromotionTransaction &TPT,
01695                                               InstrToOrigTy &PromotedInsts,
01696                                               unsigned &CreatedInsts);
01697 
01698   /// \brief Utility function to promote the operand of \p SExt when this
01699   /// operand is promotable and is not a supported trunc or sext.
01700   /// \p PromotedInsts maps the instructions to their type before promotion.
01701   /// \p CreatedInsts[out] contains how many non-free instructions have been
01702   /// created to promote the operand of SExt.
01703   /// Should never be called directly.
01704   /// \return The promoted value which is used instead of SExt.
01705   static Value *promoteOperandForOther(Instruction *SExt,
01706                                        TypePromotionTransaction &TPT,
01707                                        InstrToOrigTy &PromotedInsts,
01708                                        unsigned &CreatedInsts);
01709 
01710 public:
01711   /// Type for the utility function that promotes the operand of SExt.
01712   typedef Value *(*Action)(Instruction *SExt, TypePromotionTransaction &TPT,
01713                            InstrToOrigTy &PromotedInsts,
01714                            unsigned &CreatedInsts);
01715   /// \brief Given a sign extend instruction \p SExt, return the approriate
01716   /// action to promote the operand of \p SExt instead of using SExt.
01717   /// \return NULL if no promotable action is possible with the current
01718   /// sign extension.
01719   /// \p InsertedTruncs keeps track of all the truncate instructions inserted by
01720   /// the others CodeGenPrepare optimizations. This information is important
01721   /// because we do not want to promote these instructions as CodeGenPrepare
01722   /// will reinsert them later. Thus creating an infinite loop: create/remove.
01723   /// \p PromotedInsts maps the instructions to their type before promotion.
01724   static Action getAction(Instruction *SExt, const SetOfInstrs &InsertedTruncs,
01725                           const TargetLowering &TLI,
01726                           const InstrToOrigTy &PromotedInsts);
01727 };
01728 
01729 bool TypePromotionHelper::canGetThrough(const Instruction *Inst,
01730                                         Type *ConsideredSExtType,
01731                                         const InstrToOrigTy &PromotedInsts) {
01732   // We can always get through sext.
01733   if (isa<SExtInst>(Inst))
01734     return true;
01735 
01736   // We can get through binary operator, if it is legal. In other words, the
01737   // binary operator must have a nuw or nsw flag.
01738   const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
01739   if (BinOp && isa<OverflowingBinaryOperator>(BinOp) &&
01740       (BinOp->hasNoUnsignedWrap() || BinOp->hasNoSignedWrap()))
01741     return true;
01742 
01743   // Check if we can do the following simplification.
01744   // sext(trunc(sext)) --> sext
01745   if (!isa<TruncInst>(Inst))
01746     return false;
01747 
01748   Value *OpndVal = Inst->getOperand(0);
01749   // Check if we can use this operand in the sext.
01750   // If the type is larger than the result type of the sign extension,
01751   // we cannot.
01752   if (OpndVal->getType()->getIntegerBitWidth() >
01753       ConsideredSExtType->getIntegerBitWidth())
01754     return false;
01755 
01756   // If the operand of the truncate is not an instruction, we will not have
01757   // any information on the dropped bits.
01758   // (Actually we could for constant but it is not worth the extra logic).
01759   Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
01760   if (!Opnd)
01761     return false;
01762 
01763   // Check if the source of the type is narrow enough.
01764   // I.e., check that trunc just drops sign extended bits.
01765   // #1 get the type of the operand.
01766   const Type *OpndType;
01767   InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
01768   if (It != PromotedInsts.end())
01769     OpndType = It->second;
01770   else if (isa<SExtInst>(Opnd))
01771     OpndType = cast<Instruction>(Opnd)->getOperand(0)->getType();
01772   else
01773     return false;
01774 
01775   // #2 check that the truncate just drop sign extended bits.
01776   if (Inst->getType()->getIntegerBitWidth() >= OpndType->getIntegerBitWidth())
01777     return true;
01778 
01779   return false;
01780 }
01781 
01782 TypePromotionHelper::Action TypePromotionHelper::getAction(
01783     Instruction *SExt, const SetOfInstrs &InsertedTruncs,
01784     const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts) {
01785   Instruction *SExtOpnd = dyn_cast<Instruction>(SExt->getOperand(0));
01786   Type *SExtTy = SExt->getType();
01787   // If the operand of the sign extension is not an instruction, we cannot
01788   // get through.
01789   // If it, check we can get through.
01790   if (!SExtOpnd || !canGetThrough(SExtOpnd, SExtTy, PromotedInsts))
01791     return nullptr;
01792 
01793   // Do not promote if the operand has been added by codegenprepare.
01794   // Otherwise, it means we are undoing an optimization that is likely to be
01795   // redone, thus causing potential infinite loop.
01796   if (isa<TruncInst>(SExtOpnd) && InsertedTruncs.count(SExtOpnd))
01797     return nullptr;
01798 
01799   // SExt or Trunc instructions.
01800   // Return the related handler.
01801   if (isa<SExtInst>(SExtOpnd) || isa<TruncInst>(SExtOpnd))
01802     return promoteOperandForTruncAndSExt;
01803 
01804   // Regular instruction.
01805   // Abort early if we will have to insert non-free instructions.
01806   if (!SExtOpnd->hasOneUse() &&
01807       !TLI.isTruncateFree(SExtTy, SExtOpnd->getType()))
01808     return nullptr;
01809   return promoteOperandForOther;
01810 }
01811 
01812 Value *TypePromotionHelper::promoteOperandForTruncAndSExt(
01813     llvm::Instruction *SExt, TypePromotionTransaction &TPT,
01814     InstrToOrigTy &PromotedInsts, unsigned &CreatedInsts) {
01815   // By construction, the operand of SExt is an instruction. Otherwise we cannot
01816   // get through it and this method should not be called.
01817   Instruction *SExtOpnd = cast<Instruction>(SExt->getOperand(0));
01818   // Replace sext(trunc(opnd)) or sext(sext(opnd))
01819   // => sext(opnd).
01820   TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0));
01821   CreatedInsts = 0;
01822 
01823   // Remove dead code.
01824   if (SExtOpnd->use_empty())
01825     TPT.eraseInstruction(SExtOpnd);
01826 
01827   // Check if the sext is still needed.
01828   if (SExt->getType() != SExt->getOperand(0)->getType())
01829     return SExt;
01830 
01831   // At this point we have: sext ty opnd to ty.
01832   // Reassign the uses of SExt to the opnd and remove SExt.
01833   Value *NextVal = SExt->getOperand(0);
01834   TPT.eraseInstruction(SExt, NextVal);
01835   return NextVal;
01836 }
01837 
01838 Value *
01839 TypePromotionHelper::promoteOperandForOther(Instruction *SExt,
01840                                             TypePromotionTransaction &TPT,
01841                                             InstrToOrigTy &PromotedInsts,
01842                                             unsigned &CreatedInsts) {
01843   // By construction, the operand of SExt is an instruction. Otherwise we cannot
01844   // get through it and this method should not be called.
01845   Instruction *SExtOpnd = cast<Instruction>(SExt->getOperand(0));
01846   CreatedInsts = 0;
01847   if (!SExtOpnd->hasOneUse()) {
01848     // SExtOpnd will be promoted.
01849     // All its uses, but SExt, will need to use a truncated value of the
01850     // promoted version.
01851     // Create the truncate now.
01852     Instruction *Trunc = TPT.createTrunc(SExt, SExtOpnd->getType());
01853     Trunc->removeFromParent();
01854     // Insert it just after the definition.
01855     Trunc->insertAfter(SExtOpnd);
01856 
01857     TPT.replaceAllUsesWith(SExtOpnd, Trunc);
01858     // Restore the operand of SExt (which has been replace by the previous call
01859     // to replaceAllUsesWith) to avoid creating a cycle trunc <-> sext.
01860     TPT.setOperand(SExt, 0, SExtOpnd);
01861   }
01862 
01863   // Get through the Instruction:
01864   // 1. Update its type.
01865   // 2. Replace the uses of SExt by Inst.
01866   // 3. Sign extend each operand that needs to be sign extended.
01867 
01868   // Remember the original type of the instruction before promotion.
01869   // This is useful to know that the high bits are sign extended bits.
01870   PromotedInsts.insert(
01871       std::pair<Instruction *, Type *>(SExtOpnd, SExtOpnd->getType()));
01872   // Step #1.
01873   TPT.mutateType(SExtOpnd, SExt->getType());
01874   // Step #2.
01875   TPT.replaceAllUsesWith(SExt, SExtOpnd);
01876   // Step #3.
01877   Instruction *SExtForOpnd = SExt;
01878 
01879   DEBUG(dbgs() << "Propagate SExt to operands\n");
01880   for (int OpIdx = 0, EndOpIdx = SExtOpnd->getNumOperands(); OpIdx != EndOpIdx;
01881        ++OpIdx) {
01882     DEBUG(dbgs() << "Operand:\n" << *(SExtOpnd->getOperand(OpIdx)) << '\n');
01883     if (SExtOpnd->getOperand(OpIdx)->getType() == SExt->getType() ||
01884         !shouldSExtOperand(SExtOpnd, OpIdx)) {
01885       DEBUG(dbgs() << "No need to propagate\n");
01886       continue;
01887     }
01888     // Check if we can statically sign extend the operand.
01889     Value *Opnd = SExtOpnd->getOperand(OpIdx);
01890     if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
01891       DEBUG(dbgs() << "Statically sign extend\n");
01892       TPT.setOperand(
01893           SExtOpnd, OpIdx,
01894           ConstantInt::getSigned(SExt->getType(), Cst->getSExtValue()));
01895       continue;
01896     }
01897     // UndefValue are typed, so we have to statically sign extend them.
01898     if (isa<UndefValue>(Opnd)) {
01899       DEBUG(dbgs() << "Statically sign extend\n");
01900       TPT.setOperand(SExtOpnd, OpIdx, UndefValue::get(SExt->getType()));
01901       continue;
01902     }
01903 
01904     // Otherwise we have to explicity sign extend the operand.
01905     // Check if SExt was reused to sign extend an operand.
01906     if (!SExtForOpnd) {
01907       // If yes, create a new one.
01908       DEBUG(dbgs() << "More operands to sext\n");
01909       SExtForOpnd = TPT.createSExt(SExt, Opnd, SExt->getType());
01910       ++CreatedInsts;
01911     }
01912 
01913     TPT.setOperand(SExtForOpnd, 0, Opnd);
01914 
01915     // Move the sign extension before the insertion point.
01916     TPT.moveBefore(SExtForOpnd, SExtOpnd);
01917     TPT.setOperand(SExtOpnd, OpIdx, SExtForOpnd);
01918     // If more sext are required, new instructions will have to be created.
01919     SExtForOpnd = nullptr;
01920   }
01921   if (SExtForOpnd == SExt) {
01922     DEBUG(dbgs() << "Sign extension is useless now\n");
01923     TPT.eraseInstruction(SExt);
01924   }
01925   return SExtOpnd;
01926 }
01927 
01928 /// IsPromotionProfitable - Check whether or not promoting an instruction
01929 /// to a wider type was profitable.
01930 /// \p MatchedSize gives the number of instructions that have been matched
01931 /// in the addressing mode after the promotion was applied.
01932 /// \p SizeWithPromotion gives the number of created instructions for
01933 /// the promotion plus the number of instructions that have been
01934 /// matched in the addressing mode before the promotion.
01935 /// \p PromotedOperand is the value that has been promoted.
01936 /// \return True if the promotion is profitable, false otherwise.
01937 bool
01938 AddressingModeMatcher::IsPromotionProfitable(unsigned MatchedSize,
01939                                              unsigned SizeWithPromotion,
01940                                              Value *PromotedOperand) const {
01941   // We folded less instructions than what we created to promote the operand.
01942   // This is not profitable.
01943   if (MatchedSize < SizeWithPromotion)
01944     return false;
01945   if (MatchedSize > SizeWithPromotion)
01946     return true;
01947   // The promotion is neutral but it may help folding the sign extension in
01948   // loads for instance.
01949   // Check that we did not create an illegal instruction.
01950   Instruction *PromotedInst = dyn_cast<Instruction>(PromotedOperand);
01951   if (!PromotedInst)
01952     return false;
01953   int ISDOpcode = TLI.InstructionOpcodeToISD(PromotedInst->getOpcode());
01954   // If the ISDOpcode is undefined, it was undefined before the promotion.
01955   if (!ISDOpcode)
01956     return true;
01957   // Otherwise, check if the promoted instruction is legal or not.
01958   return TLI.isOperationLegalOrCustom(ISDOpcode,
01959                                       EVT::getEVT(PromotedInst->getType()));
01960 }
01961 
01962 /// MatchOperationAddr - Given an instruction or constant expr, see if we can
01963 /// fold the operation into the addressing mode.  If so, update the addressing
01964 /// mode and return true, otherwise return false without modifying AddrMode.
01965 /// If \p MovedAway is not NULL, it contains the information of whether or
01966 /// not AddrInst has to be folded into the addressing mode on success.
01967 /// If \p MovedAway == true, \p AddrInst will not be part of the addressing
01968 /// because it has been moved away.
01969 /// Thus AddrInst must not be added in the matched instructions.
01970 /// This state can happen when AddrInst is a sext, since it may be moved away.
01971 /// Therefore, AddrInst may not be valid when MovedAway is true and it must
01972 /// not be referenced anymore.
01973 bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode,
01974                                                unsigned Depth,
01975                                                bool *MovedAway) {
01976   // Avoid exponential behavior on extremely deep expression trees.
01977   if (Depth >= 5) return false;
01978 
01979   // By default, all matched instructions stay in place.
01980   if (MovedAway)
01981     *MovedAway = false;
01982 
01983   switch (Opcode) {
01984   case Instruction::PtrToInt:
01985     // PtrToInt is always a noop, as we know that the int type is pointer sized.
01986     return MatchAddr(AddrInst->getOperand(0), Depth);
01987   case Instruction::IntToPtr:
01988     // This inttoptr is a no-op if the integer type is pointer sized.
01989     if (TLI.getValueType(AddrInst->getOperand(0)->getType()) ==
01990         TLI.getPointerTy(AddrInst->getType()->getPointerAddressSpace()))
01991       return MatchAddr(AddrInst->getOperand(0), Depth);
01992     return false;
01993   case Instruction::BitCast:
01994   case Instruction::AddrSpaceCast:
01995     // BitCast is always a noop, and we can handle it as long as it is
01996     // int->int or pointer->pointer (we don't want int<->fp or something).
01997     if ((AddrInst->getOperand(0)->getType()->isPointerTy() ||
01998          AddrInst->getOperand(0)->getType()->isIntegerTy()) &&
01999         // Don't touch identity bitcasts.  These were probably put here by LSR,
02000         // and we don't want to mess around with them.  Assume it knows what it
02001         // is doing.
02002         AddrInst->getOperand(0)->getType() != AddrInst->getType())
02003       return MatchAddr(AddrInst->getOperand(0), Depth);
02004     return false;
02005   case Instruction::Add: {
02006     // Check to see if we can merge in the RHS then the LHS.  If so, we win.
02007     ExtAddrMode BackupAddrMode = AddrMode;
02008     unsigned OldSize = AddrModeInsts.size();
02009     // Start a transaction at this point.
02010     // The LHS may match but not the RHS.
02011     // Therefore, we need a higher level restoration point to undo partially
02012     // matched operation.
02013     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
02014         TPT.getRestorationPoint();
02015 
02016     if (MatchAddr(AddrInst->getOperand(1), Depth+1) &&
02017         MatchAddr(AddrInst->getOperand(0), Depth+1))
02018       return true;
02019 
02020     // Restore the old addr mode info.
02021     AddrMode = BackupAddrMode;
02022     AddrModeInsts.resize(OldSize);
02023     TPT.rollback(LastKnownGood);
02024 
02025     // Otherwise this was over-aggressive.  Try merging in the LHS then the RHS.
02026     if (MatchAddr(AddrInst->getOperand(0), Depth+1) &&
02027         MatchAddr(AddrInst->getOperand(1), Depth+1))
02028       return true;
02029 
02030     // Otherwise we definitely can't merge the ADD in.
02031     AddrMode = BackupAddrMode;
02032     AddrModeInsts.resize(OldSize);
02033     TPT.rollback(LastKnownGood);
02034     break;
02035   }
02036   //case Instruction::Or:
02037   // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD.
02038   //break;
02039   case Instruction::Mul:
02040   case Instruction::Shl: {
02041     // Can only handle X*C and X << C.
02042     ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1));
02043     if (!RHS)
02044       return false;
02045     int64_t Scale = RHS->getSExtValue();
02046     if (Opcode == Instruction::Shl)
02047       Scale = 1LL << Scale;
02048 
02049     return MatchScaledValue(AddrInst->getOperand(0), Scale, Depth);
02050   }
02051   case Instruction::GetElementPtr: {
02052     // Scan the GEP.  We check it if it contains constant offsets and at most
02053     // one variable offset.
02054     int VariableOperand = -1;
02055     unsigned VariableScale = 0;
02056 
02057     int64_t ConstantOffset = 0;
02058     const DataLayout *TD = TLI.getDataLayout();
02059     gep_type_iterator GTI = gep_type_begin(AddrInst);
02060     for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) {
02061       if (StructType *STy = dyn_cast<StructType>(*GTI)) {
02062         const StructLayout *SL = TD->getStructLayout(STy);
02063         unsigned Idx =
02064           cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue();
02065         ConstantOffset += SL->getElementOffset(Idx);
02066       } else {
02067         uint64_t TypeSize = TD->getTypeAllocSize(GTI.getIndexedType());
02068         if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) {
02069           ConstantOffset += CI->getSExtValue()*TypeSize;
02070         } else if (TypeSize) {  // Scales of zero don't do anything.
02071           // We only allow one variable index at the moment.
02072           if (VariableOperand != -1)
02073             return false;
02074 
02075           // Remember the variable index.
02076           VariableOperand = i;
02077           VariableScale = TypeSize;
02078         }
02079       }
02080     }
02081 
02082     // A common case is for the GEP to only do a constant offset.  In this case,
02083     // just add it to the disp field and check validity.
02084     if (VariableOperand == -1) {
02085       AddrMode.BaseOffs += ConstantOffset;
02086       if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){
02087         // Check to see if we can fold the base pointer in too.
02088         if (MatchAddr(AddrInst->getOperand(0), Depth+1))
02089           return true;
02090       }
02091       AddrMode.BaseOffs -= ConstantOffset;
02092       return false;
02093     }
02094 
02095     // Save the valid addressing mode in case we can't match.
02096     ExtAddrMode BackupAddrMode = AddrMode;
02097     unsigned OldSize = AddrModeInsts.size();
02098 
02099     // See if the scale and offset amount is valid for this target.
02100     AddrMode.BaseOffs += ConstantOffset;
02101 
02102     // Match the base operand of the GEP.
02103     if (!MatchAddr(AddrInst->getOperand(0), Depth+1)) {
02104       // If it couldn't be matched, just stuff the value in a register.
02105       if (AddrMode.HasBaseReg) {
02106         AddrMode = BackupAddrMode;
02107         AddrModeInsts.resize(OldSize);
02108         return false;
02109       }
02110       AddrMode.HasBaseReg = true;
02111       AddrMode.BaseReg = AddrInst->getOperand(0);
02112     }
02113 
02114     // Match the remaining variable portion of the GEP.
02115     if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale,
02116                           Depth)) {
02117       // If it couldn't be matched, try stuffing the base into a register
02118       // instead of matching it, and retrying the match of the scale.
02119       AddrMode = BackupAddrMode;
02120       AddrModeInsts.resize(OldSize);
02121       if (AddrMode.HasBaseReg)
02122         return false;
02123       AddrMode.HasBaseReg = true;
02124       AddrMode.BaseReg = AddrInst->getOperand(0);
02125       AddrMode.BaseOffs += ConstantOffset;
02126       if (!MatchScaledValue(AddrInst->getOperand(VariableOperand),
02127                             VariableScale, Depth)) {
02128         // If even that didn't work, bail.
02129         AddrMode = BackupAddrMode;
02130         AddrModeInsts.resize(OldSize);
02131         return false;
02132       }
02133     }
02134 
02135     return true;
02136   }
02137   case Instruction::SExt: {
02138     Instruction *SExt = dyn_cast<Instruction>(AddrInst);
02139     if (!SExt)
02140       return false;
02141 
02142     // Try to move this sext out of the way of the addressing mode.
02143     // Ask for a method for doing so.
02144     TypePromotionHelper::Action TPH = TypePromotionHelper::getAction(
02145         SExt, InsertedTruncs, TLI, PromotedInsts);
02146     if (!TPH)
02147       return false;
02148 
02149     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
02150         TPT.getRestorationPoint();
02151     unsigned CreatedInsts = 0;
02152     Value *PromotedOperand = TPH(SExt, TPT, PromotedInsts, CreatedInsts);
02153     // SExt has been moved away.
02154     // Thus either it will be rematched later in the recursive calls or it is
02155     // gone. Anyway, we must not fold it into the addressing mode at this point.
02156     // E.g.,
02157     // op = add opnd, 1
02158     // idx = sext op
02159     // addr = gep base, idx
02160     // is now:
02161     // promotedOpnd = sext opnd           <- no match here
02162     // op = promoted_add promotedOpnd, 1  <- match (later in recursive calls)
02163     // addr = gep base, op                <- match
02164     if (MovedAway)
02165       *MovedAway = true;
02166 
02167     assert(PromotedOperand &&
02168            "TypePromotionHelper should have filtered out those cases");
02169 
02170     ExtAddrMode BackupAddrMode = AddrMode;
02171     unsigned OldSize = AddrModeInsts.size();
02172 
02173     if (!MatchAddr(PromotedOperand, Depth) ||
02174         !IsPromotionProfitable(AddrModeInsts.size(), OldSize + CreatedInsts,
02175                                PromotedOperand)) {
02176       AddrMode = BackupAddrMode;
02177       AddrModeInsts.resize(OldSize);
02178       DEBUG(dbgs() << "Sign extension does not pay off: rollback\n");
02179       TPT.rollback(LastKnownGood);
02180       return false;
02181     }
02182     return true;
02183   }
02184   }
02185   return false;
02186 }
02187 
02188 /// MatchAddr - If we can, try to add the value of 'Addr' into the current
02189 /// addressing mode.  If Addr can't be added to AddrMode this returns false and
02190 /// leaves AddrMode unmodified.  This assumes that Addr is either a pointer type
02191 /// or intptr_t for the target.
02192 ///
02193 bool AddressingModeMatcher::MatchAddr(Value *Addr, unsigned Depth) {
02194   // Start a transaction at this point that we will rollback if the matching
02195   // fails.
02196   TypePromotionTransaction::ConstRestorationPt LastKnownGood =
02197       TPT.getRestorationPoint();
02198   if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) {
02199     // Fold in immediates if legal for the target.
02200     AddrMode.BaseOffs += CI->getSExtValue();
02201     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
02202       return true;
02203     AddrMode.BaseOffs -= CI->getSExtValue();
02204   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) {
02205     // If this is a global variable, try to fold it into the addressing mode.
02206     if (!AddrMode.BaseGV) {
02207       AddrMode.BaseGV = GV;
02208       if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
02209         return true;
02210       AddrMode.BaseGV = nullptr;
02211     }
02212   } else if (Instruction *I = dyn_cast<Instruction>(Addr)) {
02213     ExtAddrMode BackupAddrMode = AddrMode;
02214     unsigned OldSize = AddrModeInsts.size();
02215 
02216     // Check to see if it is possible to fold this operation.
02217     bool MovedAway = false;
02218     if (MatchOperationAddr(I, I->getOpcode(), Depth, &MovedAway)) {
02219       // This instruction may have been move away. If so, there is nothing
02220       // to check here.
02221       if (MovedAway)
02222         return true;
02223       // Okay, it's possible to fold this.  Check to see if it is actually
02224       // *profitable* to do so.  We use a simple cost model to avoid increasing
02225       // register pressure too much.
02226       if (I->hasOneUse() ||
02227           IsProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) {
02228         AddrModeInsts.push_back(I);
02229         return true;
02230       }
02231 
02232       // It isn't profitable to do this, roll back.
02233       //cerr << "NOT FOLDING: " << *I;
02234       AddrMode = BackupAddrMode;
02235       AddrModeInsts.resize(OldSize);
02236       TPT.rollback(LastKnownGood);
02237     }
02238   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
02239     if (MatchOperationAddr(CE, CE->getOpcode(), Depth))
02240       return true;
02241     TPT.rollback(LastKnownGood);
02242   } else if (isa<ConstantPointerNull>(Addr)) {
02243     // Null pointer gets folded without affecting the addressing mode.
02244     return true;
02245   }
02246 
02247   // Worse case, the target should support [reg] addressing modes. :)
02248   if (!AddrMode.HasBaseReg) {
02249     AddrMode.HasBaseReg = true;
02250     AddrMode.BaseReg = Addr;
02251     // Still check for legality in case the target supports [imm] but not [i+r].
02252     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
02253       return true;
02254     AddrMode.HasBaseReg = false;
02255     AddrMode.BaseReg = nullptr;
02256   }
02257 
02258   // If the base register is already taken, see if we can do [r+r].
02259   if (AddrMode.Scale == 0) {
02260     AddrMode.Scale = 1;
02261     AddrMode.ScaledReg = Addr;
02262     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
02263       return true;
02264     AddrMode.Scale = 0;
02265     AddrMode.ScaledReg = nullptr;
02266   }
02267   // Couldn't match.
02268   TPT.rollback(LastKnownGood);
02269   return false;
02270 }
02271 
02272 /// IsOperandAMemoryOperand - Check to see if all uses of OpVal by the specified
02273 /// inline asm call are due to memory operands.  If so, return true, otherwise
02274 /// return false.
02275 static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal,
02276                                     const TargetLowering &TLI) {
02277   TargetLowering::AsmOperandInfoVector TargetConstraints = TLI.ParseConstraints(ImmutableCallSite(CI));
02278   for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
02279     TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
02280 
02281     // Compute the constraint code and ConstraintType to use.
02282     TLI.ComputeConstraintToUse(OpInfo, SDValue());
02283 
02284     // If this asm operand is our Value*, and if it isn't an indirect memory
02285     // operand, we can't fold it!
02286     if (OpInfo.CallOperandVal == OpVal &&
02287         (OpInfo.ConstraintType != TargetLowering::C_Memory ||
02288          !OpInfo.isIndirect))
02289       return false;
02290   }
02291 
02292   return true;
02293 }
02294 
02295 /// FindAllMemoryUses - Recursively walk all the uses of I until we find a
02296 /// memory use.  If we find an obviously non-foldable instruction, return true.
02297 /// Add the ultimately found memory instructions to MemoryUses.
02298 static bool FindAllMemoryUses(Instruction *I,
02299                 SmallVectorImpl<std::pair<Instruction*,unsigned> > &MemoryUses,
02300                               SmallPtrSetImpl<Instruction*> &ConsideredInsts,
02301                               const TargetLowering &TLI) {
02302   // If we already considered this instruction, we're done.
02303   if (!ConsideredInsts.insert(I))
02304     return false;
02305 
02306   // If this is an obviously unfoldable instruction, bail out.
02307   if (!MightBeFoldableInst(I))
02308     return true;
02309 
02310   // Loop over all the uses, recursively processing them.
02311   for (Use &U : I->uses()) {
02312     Instruction *UserI = cast<Instruction>(U.getUser());
02313 
02314     if (LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
02315       MemoryUses.push_back(std::make_pair(LI, U.getOperandNo()));
02316       continue;
02317     }
02318 
02319     if (StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
02320       unsigned opNo = U.getOperandNo();
02321       if (opNo == 0) return true; // Storing addr, not into addr.
02322       MemoryUses.push_back(std::make_pair(SI, opNo));
02323       continue;
02324     }
02325 
02326     if (CallInst *CI = dyn_cast<CallInst>(UserI)) {
02327       InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue());
02328       if (!IA) return true;
02329 
02330       // If this is a memory operand, we're cool, otherwise bail out.
02331       if (!IsOperandAMemoryOperand(CI, IA, I, TLI))
02332         return true;
02333       continue;
02334     }
02335 
02336     if (FindAllMemoryUses(UserI, MemoryUses, ConsideredInsts, TLI))
02337       return true;
02338   }
02339 
02340   return false;
02341 }
02342 
02343 /// ValueAlreadyLiveAtInst - Retrn true if Val is already known to be live at
02344 /// the use site that we're folding it into.  If so, there is no cost to
02345 /// include it in the addressing mode.  KnownLive1 and KnownLive2 are two values
02346 /// that we know are live at the instruction already.
02347 bool AddressingModeMatcher::ValueAlreadyLiveAtInst(Value *Val,Value *KnownLive1,
02348                                                    Value *KnownLive2) {
02349   // If Val is either of the known-live values, we know it is live!
02350   if (Val == nullptr || Val == KnownLive1 || Val == KnownLive2)
02351     return true;
02352 
02353   // All values other than instructions and arguments (e.g. constants) are live.
02354   if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true;
02355 
02356   // If Val is a constant sized alloca in the entry block, it is live, this is
02357   // true because it is just a reference to the stack/frame pointer, which is
02358   // live for the whole function.
02359   if (AllocaInst *AI = dyn_cast<AllocaInst>(Val))
02360     if (AI->isStaticAlloca())
02361       return true;
02362 
02363   // Check to see if this value is already used in the memory instruction's
02364   // block.  If so, it's already live into the block at the very least, so we
02365   // can reasonably fold it.
02366   return Val->isUsedInBasicBlock(MemoryInst->getParent());
02367 }
02368 
02369 /// IsProfitableToFoldIntoAddressingMode - It is possible for the addressing
02370 /// mode of the machine to fold the specified instruction into a load or store
02371 /// that ultimately uses it.  However, the specified instruction has multiple
02372 /// uses.  Given this, it may actually increase register pressure to fold it
02373 /// into the load.  For example, consider this code:
02374 ///
02375 ///     X = ...
02376 ///     Y = X+1
02377 ///     use(Y)   -> nonload/store
02378 ///     Z = Y+1
02379 ///     load Z
02380 ///
02381 /// In this case, Y has multiple uses, and can be folded into the load of Z
02382 /// (yielding load [X+2]).  However, doing this will cause both "X" and "X+1" to
02383 /// be live at the use(Y) line.  If we don't fold Y into load Z, we use one
02384 /// fewer register.  Since Y can't be folded into "use(Y)" we don't increase the
02385 /// number of computations either.
02386 ///
02387 /// Note that this (like most of CodeGenPrepare) is just a rough heuristic.  If
02388 /// X was live across 'load Z' for other reasons, we actually *would* want to
02389 /// fold the addressing mode in the Z case.  This would make Y die earlier.
02390 bool AddressingModeMatcher::
02391 IsProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore,
02392                                      ExtAddrMode &AMAfter) {
02393   if (IgnoreProfitability) return true;
02394 
02395   // AMBefore is the addressing mode before this instruction was folded into it,
02396   // and AMAfter is the addressing mode after the instruction was folded.  Get
02397   // the set of registers referenced by AMAfter and subtract out those
02398   // referenced by AMBefore: this is the set of values which folding in this
02399   // address extends the lifetime of.
02400   //
02401   // Note that there are only two potential values being referenced here,
02402   // BaseReg and ScaleReg (global addresses are always available, as are any
02403   // folded immediates).
02404   Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg;
02405 
02406   // If the BaseReg or ScaledReg was referenced by the previous addrmode, their
02407   // lifetime wasn't extended by adding this instruction.
02408   if (ValueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg))
02409     BaseReg = nullptr;
02410   if (ValueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg))
02411     ScaledReg = nullptr;
02412 
02413   // If folding this instruction (and it's subexprs) didn't extend any live
02414   // ranges, we're ok with it.
02415   if (!BaseReg && !ScaledReg)
02416     return true;
02417 
02418   // If all uses of this instruction are ultimately load/store/inlineasm's,
02419   // check to see if their addressing modes will include this instruction.  If
02420   // so, we can fold it into all uses, so it doesn't matter if it has multiple
02421   // uses.
02422   SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses;
02423   SmallPtrSet<Instruction*, 16> ConsideredInsts;
02424   if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI))
02425     return false;  // Has a non-memory, non-foldable use!
02426 
02427   // Now that we know that all uses of this instruction are part of a chain of
02428   // computation involving only operations that could theoretically be folded
02429   // into a memory use, loop over each of these uses and see if they could
02430   // *actually* fold the instruction.
02431   SmallVector<Instruction*, 32> MatchedAddrModeInsts;
02432   for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) {
02433     Instruction *User = MemoryUses[i].first;
02434     unsigned OpNo = MemoryUses[i].second;
02435 
02436     // Get the access type of this use.  If the use isn't a pointer, we don't
02437     // know what it accesses.
02438     Value *Address = User->getOperand(OpNo);
02439     if (!Address->getType()->isPointerTy())
02440       return false;
02441     Type *AddressAccessTy = Address->getType()->getPointerElementType();
02442 
02443     // Do a match against the root of this address, ignoring profitability. This
02444     // will tell us if the addressing mode for the memory operation will
02445     // *actually* cover the shared instruction.
02446     ExtAddrMode Result;
02447     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
02448         TPT.getRestorationPoint();
02449     AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, AddressAccessTy,
02450                                   MemoryInst, Result, InsertedTruncs,
02451                                   PromotedInsts, TPT);
02452     Matcher.IgnoreProfitability = true;
02453     bool Success = Matcher.MatchAddr(Address, 0);
02454     (void)Success; assert(Success && "Couldn't select *anything*?");
02455 
02456     // The match was to check the profitability, the changes made are not
02457     // part of the original matcher. Therefore, they should be dropped
02458     // otherwise the original matcher will not present the right state.
02459     TPT.rollback(LastKnownGood);
02460 
02461     // If the match didn't cover I, then it won't be shared by it.
02462     if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(),
02463                   I) == MatchedAddrModeInsts.end())
02464       return false;
02465 
02466     MatchedAddrModeInsts.clear();
02467   }
02468 
02469   return true;
02470 }
02471 
02472 } // end anonymous namespace
02473 
02474 /// IsNonLocalValue - Return true if the specified values are defined in a
02475 /// different basic block than BB.
02476 static bool IsNonLocalValue(Value *V, BasicBlock *BB) {
02477   if (Instruction *I = dyn_cast<Instruction>(V))
02478     return I->getParent() != BB;
02479   return false;
02480 }
02481 
02482 /// OptimizeMemoryInst - Load and Store Instructions often have
02483 /// addressing modes that can do significant amounts of computation.  As such,
02484 /// instruction selection will try to get the load or store to do as much
02485 /// computation as possible for the program.  The problem is that isel can only
02486 /// see within a single block.  As such, we sink as much legal addressing mode
02487 /// stuff into the block as possible.
02488 ///
02489 /// This method is used to optimize both load/store and inline asms with memory
02490 /// operands.
02491 bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
02492                                         Type *AccessTy) {
02493   Value *Repl = Addr;
02494 
02495   // Try to collapse single-value PHI nodes.  This is necessary to undo
02496   // unprofitable PRE transformations.
02497   SmallVector<Value*, 8> worklist;
02498   SmallPtrSet<Value*, 16> Visited;
02499   worklist.push_back(Addr);
02500 
02501   // Use a worklist to iteratively look through PHI nodes, and ensure that
02502   // the addressing mode obtained from the non-PHI roots of the graph
02503   // are equivalent.
02504   Value *Consensus = nullptr;
02505   unsigned NumUsesConsensus = 0;
02506   bool IsNumUsesConsensusValid = false;
02507   SmallVector<Instruction*, 16> AddrModeInsts;
02508   ExtAddrMode AddrMode;
02509   TypePromotionTransaction TPT;
02510   TypePromotionTransaction::ConstRestorationPt LastKnownGood =
02511       TPT.getRestorationPoint();
02512   while (!worklist.empty()) {
02513     Value *V = worklist.back();
02514     worklist.pop_back();
02515 
02516     // Break use-def graph loops.
02517     if (!Visited.insert(V)) {
02518       Consensus = nullptr;
02519       break;
02520     }
02521 
02522     // For a PHI node, push all of its incoming values.
02523     if (PHINode *P = dyn_cast<PHINode>(V)) {
02524       for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i)
02525         worklist.push_back(P->getIncomingValue(i));
02526       continue;
02527     }
02528 
02529     // For non-PHIs, determine the addressing mode being computed.
02530     SmallVector<Instruction*, 16> NewAddrModeInsts;
02531     ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
02532         V, AccessTy, MemoryInst, NewAddrModeInsts, *TLI, InsertedTruncsSet,
02533         PromotedInsts, TPT);
02534 
02535     // This check is broken into two cases with very similar code to avoid using
02536     // getNumUses() as much as possible. Some values have a lot of uses, so
02537     // calling getNumUses() unconditionally caused a significant compile-time
02538     // regression.
02539     if (!Consensus) {
02540       Consensus = V;
02541       AddrMode = NewAddrMode;
02542       AddrModeInsts = NewAddrModeInsts;
02543       continue;
02544     } else if (NewAddrMode == AddrMode) {
02545       if (!IsNumUsesConsensusValid) {
02546         NumUsesConsensus = Consensus->getNumUses();
02547         IsNumUsesConsensusValid = true;
02548       }
02549 
02550       // Ensure that the obtained addressing mode is equivalent to that obtained
02551       // for all other roots of the PHI traversal.  Also, when choosing one
02552       // such root as representative, select the one with the most uses in order
02553       // to keep the cost modeling heuristics in AddressingModeMatcher
02554       // applicable.
02555       unsigned NumUses = V->getNumUses();
02556       if (NumUses > NumUsesConsensus) {
02557         Consensus = V;
02558         NumUsesConsensus = NumUses;
02559         AddrModeInsts = NewAddrModeInsts;
02560       }
02561       continue;
02562     }
02563 
02564     Consensus = nullptr;
02565     break;
02566   }
02567 
02568   // If the addressing mode couldn't be determined, or if multiple different
02569   // ones were determined, bail out now.
02570   if (!Consensus) {
02571     TPT.rollback(LastKnownGood);
02572     return false;
02573   }
02574   TPT.commit();
02575 
02576   // Check to see if any of the instructions supersumed by this addr mode are
02577   // non-local to I's BB.
02578   bool AnyNonLocal = false;
02579   for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) {
02580     if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) {
02581       AnyNonLocal = true;
02582       break;
02583     }
02584   }
02585 
02586   // If all the instructions matched are already in this BB, don't do anything.
02587   if (!AnyNonLocal) {
02588     DEBUG(dbgs() << "CGP: Found      local addrmode: " << AddrMode << "\n");
02589     return false;
02590   }
02591 
02592   // Insert this computation right after this user.  Since our caller is
02593   // scanning from the top of the BB to the bottom, reuse of the expr are
02594   // guaranteed to happen later.
02595   IRBuilder<> Builder(MemoryInst);
02596 
02597   // Now that we determined the addressing expression we want to use and know
02598   // that we have to sink it into this block.  Check to see if we have already
02599   // done this for some other load/store instr in this block.  If so, reuse the
02600   // computation.
02601   Value *&SunkAddr = SunkAddrs[Addr];
02602   if (SunkAddr) {
02603     DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for "
02604                  << *MemoryInst << "\n");
02605     if (SunkAddr->getType() != Addr->getType())
02606       SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType());
02607   } else if (AddrSinkUsingGEPs || (!AddrSinkUsingGEPs.getNumOccurrences() &&
02608                TM && TM->getSubtarget<TargetSubtargetInfo>().useAA())) {
02609     // By default, we use the GEP-based method when AA is used later. This
02610     // prevents new inttoptr/ptrtoint pairs from degrading AA capabilities.
02611     DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
02612                  << *MemoryInst << "\n");
02613     Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(Addr->getType());
02614     Value *ResultPtr = nullptr, *ResultIndex = nullptr;
02615 
02616     // First, find the pointer.
02617     if (AddrMode.BaseReg && AddrMode.BaseReg->getType()->isPointerTy()) {
02618       ResultPtr = AddrMode.BaseReg;
02619       AddrMode.BaseReg = nullptr;
02620     }
02621 
02622     if (AddrMode.Scale && AddrMode.ScaledReg->getType()->isPointerTy()) {
02623       // We can't add more than one pointer together, nor can we scale a
02624       // pointer (both of which seem meaningless).
02625       if (ResultPtr || AddrMode.Scale != 1)
02626         return false;
02627 
02628       ResultPtr = AddrMode.ScaledReg;
02629       AddrMode.Scale = 0;
02630     }
02631 
02632     if (AddrMode.BaseGV) {
02633       if (ResultPtr)
02634         return false;
02635 
02636       ResultPtr = AddrMode.BaseGV;
02637     }
02638 
02639     // If the real base value actually came from an inttoptr, then the matcher
02640     // will look through it and provide only the integer value. In that case,
02641     // use it here.
02642     if (!ResultPtr && AddrMode.BaseReg) {
02643       ResultPtr =
02644         Builder.CreateIntToPtr(AddrMode.BaseReg, Addr->getType(), "sunkaddr");
02645       AddrMode.BaseReg = nullptr;
02646     } else if (!ResultPtr && AddrMode.Scale == 1) {
02647       ResultPtr =
02648         Builder.CreateIntToPtr(AddrMode.ScaledReg, Addr->getType(), "sunkaddr");
02649       AddrMode.Scale = 0;
02650     }
02651 
02652     if (!ResultPtr &&
02653         !AddrMode.BaseReg && !AddrMode.Scale && !AddrMode.BaseOffs) {
02654       SunkAddr = Constant::getNullValue(Addr->getType());
02655     } else if (!ResultPtr) {
02656       return false;
02657     } else {
02658       Type *I8PtrTy =
02659         Builder.getInt8PtrTy(Addr->getType()->getPointerAddressSpace());
02660 
02661       // Start with the base register. Do this first so that subsequent address
02662       // matching finds it last, which will prevent it from trying to match it
02663       // as the scaled value in case it happens to be a mul. That would be
02664       // problematic if we've sunk a different mul for the scale, because then
02665       // we'd end up sinking both muls.
02666       if (AddrMode.BaseReg) {
02667         Value *V = AddrMode.BaseReg;
02668         if (V->getType() != IntPtrTy)
02669           V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr");
02670 
02671         ResultIndex = V;
02672       }
02673 
02674       // Add the scale value.
02675       if (AddrMode.Scale) {
02676         Value *V = AddrMode.ScaledReg;
02677         if (V->getType() == IntPtrTy) {
02678           // done.
02679         } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() <
02680                    cast<IntegerType>(V->getType())->getBitWidth()) {
02681           V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
02682         } else {
02683           // It is only safe to sign extend the BaseReg if we know that the math
02684           // required to create it did not overflow before we extend it. Since
02685           // the original IR value was tossed in favor of a constant back when
02686           // the AddrMode was created we need to bail out gracefully if widths
02687           // do not match instead of extending it.
02688           Instruction *I = dyn_cast_or_null<Instruction>(ResultIndex);
02689           if (I && (ResultIndex != AddrMode.BaseReg))
02690             I->eraseFromParent();
02691           return false;
02692         }
02693 
02694         if (AddrMode.Scale != 1)
02695           V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
02696                                 "sunkaddr");
02697         if (ResultIndex)
02698           ResultIndex = Builder.CreateAdd(ResultIndex, V, "sunkaddr");
02699         else
02700           ResultIndex = V;
02701       }
02702 
02703       // Add in the Base Offset if present.
02704       if (AddrMode.BaseOffs) {
02705         Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs);
02706         if (ResultIndex) {
02707     // We need to add this separately from the scale above to help with
02708     // SDAG consecutive load/store merging.
02709           if (ResultPtr->getType() != I8PtrTy)
02710             ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy);
02711           ResultPtr = Builder.CreateGEP(ResultPtr, ResultIndex, "sunkaddr");
02712         }
02713 
02714         ResultIndex = V;
02715       }
02716 
02717       if (!ResultIndex) {
02718         SunkAddr = ResultPtr;
02719       } else {
02720         if (ResultPtr->getType() != I8PtrTy)
02721           ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy);
02722         SunkAddr = Builder.CreateGEP(ResultPtr, ResultIndex, "sunkaddr");
02723       }
02724 
02725       if (SunkAddr->getType() != Addr->getType())
02726         SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType());
02727     }
02728   } else {
02729     DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
02730                  << *MemoryInst << "\n");
02731     Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(Addr->getType());
02732     Value *Result = nullptr;
02733 
02734     // Start with the base register. Do this first so that subsequent address
02735     // matching finds it last, which will prevent it from trying to match it
02736     // as the scaled value in case it happens to be a mul. That would be
02737     // problematic if we've sunk a different mul for the scale, because then
02738     // we'd end up sinking both muls.
02739     if (AddrMode.BaseReg) {
02740       Value *V = AddrMode.BaseReg;
02741       if (V->getType()->isPointerTy())
02742         V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
02743       if (V->getType() != IntPtrTy)
02744         V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr");
02745       Result = V;
02746     }
02747 
02748     // Add the scale value.
02749     if (AddrMode.Scale) {
02750       Value *V = AddrMode.ScaledReg;
02751       if (V->getType() == IntPtrTy) {
02752         // done.
02753       } else if (V->getType()->isPointerTy()) {
02754         V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
02755       } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() <
02756                  cast<IntegerType>(V->getType())->getBitWidth()) {
02757         V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
02758       } else {
02759         // It is only safe to sign extend the BaseReg if we know that the math
02760         // required to create it did not overflow before we extend it. Since
02761         // the original IR value was tossed in favor of a constant back when
02762         // the AddrMode was created we need to bail out gracefully if widths
02763         // do not match instead of extending it.
02764         Instruction *I = dyn_cast_or_null<Instruction>(Result);
02765         if (I && (Result != AddrMode.BaseReg))
02766           I->eraseFromParent();
02767         return false;
02768       }
02769       if (AddrMode.Scale != 1)
02770         V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
02771                               "sunkaddr");
02772       if (Result)
02773         Result = Builder.CreateAdd(Result, V, "sunkaddr");
02774       else
02775         Result = V;
02776     }
02777 
02778     // Add in the BaseGV if present.
02779     if (AddrMode.BaseGV) {
02780       Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr");
02781       if (Result)
02782         Result = Builder.CreateAdd(Result, V, "sunkaddr");
02783       else
02784         Result = V;
02785     }
02786 
02787     // Add in the Base Offset if present.
02788     if (AddrMode.BaseOffs) {
02789       Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs);
02790       if (Result)
02791         Result = Builder.CreateAdd(Result, V, "sunkaddr");
02792       else
02793         Result = V;
02794     }
02795 
02796     if (!Result)
02797       SunkAddr = Constant::getNullValue(Addr->getType());
02798     else
02799       SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr");
02800   }
02801 
02802   MemoryInst->replaceUsesOfWith(Repl, SunkAddr);
02803 
02804   // If we have no uses, recursively delete the value and all dead instructions
02805   // using it.
02806   if (Repl->use_empty()) {
02807     // This can cause recursive deletion, which can invalidate our iterator.
02808     // Use a WeakVH to hold onto it in case this happens.
02809     WeakVH IterHandle(CurInstIterator);
02810     BasicBlock *BB = CurInstIterator->getParent();
02811 
02812     RecursivelyDeleteTriviallyDeadInstructions(Repl, TLInfo);
02813 
02814     if (IterHandle != CurInstIterator) {
02815       // If the iterator instruction was recursively deleted, start over at the
02816       // start of the block.
02817       CurInstIterator = BB->begin();
02818       SunkAddrs.clear();
02819     }
02820   }
02821   ++NumMemoryInsts;
02822   return true;
02823 }
02824 
02825 /// OptimizeInlineAsmInst - If there are any memory operands, use
02826 /// OptimizeMemoryInst to sink their address computing into the block when
02827 /// possible / profitable.
02828 bool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) {
02829   bool MadeChange = false;
02830 
02831   TargetLowering::AsmOperandInfoVector
02832     TargetConstraints = TLI->ParseConstraints(CS);
02833   unsigned ArgNo = 0;
02834   for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
02835     TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
02836 
02837     // Compute the constraint code and ConstraintType to use.
02838     TLI->ComputeConstraintToUse(OpInfo, SDValue());
02839 
02840     if (OpInfo.ConstraintType == TargetLowering::C_Memory &&
02841         OpInfo.isIndirect) {
02842       Value *OpVal = CS->getArgOperand(ArgNo++);
02843       MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType());
02844     } else if (OpInfo.Type == InlineAsm::isInput)
02845       ArgNo++;
02846   }
02847 
02848   return MadeChange;
02849 }
02850 
02851 /// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same
02852 /// basic block as the load, unless conditions are unfavorable. This allows
02853 /// SelectionDAG to fold the extend into the load.
02854 ///
02855 bool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) {
02856   // Look for a load being extended.
02857   LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0));
02858   if (!LI) return false;
02859 
02860   // If they're already in the same block, there's nothing to do.
02861   if (LI->getParent() == I->getParent())
02862     return false;
02863 
02864   // If the load has other users and the truncate is not free, this probably
02865   // isn't worthwhile.
02866   if (!LI->hasOneUse() &&
02867       TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) ||
02868               !TLI->isTypeLegal(TLI->getValueType(I->getType()))) &&
02869       !TLI->isTruncateFree(I->getType(), LI->getType()))
02870     return false;
02871 
02872   // Check whether the target supports casts folded into loads.
02873   unsigned LType;
02874   if (isa<ZExtInst>(I))
02875     LType = ISD::ZEXTLOAD;
02876   else {
02877     assert(isa<SExtInst>(I) && "Unexpected ext type!");
02878     LType = ISD::SEXTLOAD;
02879   }
02880   if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType())))
02881     return false;
02882 
02883   // Move the extend into the same block as the load, so that SelectionDAG
02884   // can fold it.
02885   I->removeFromParent();
02886   I->insertAfter(LI);
02887   ++NumExtsMoved;
02888   return true;
02889 }
02890 
02891 bool CodeGenPrepare::OptimizeExtUses(Instruction *I) {
02892   BasicBlock *DefBB = I->getParent();
02893 
02894   // If the result of a {s|z}ext and its source are both live out, rewrite all
02895   // other uses of the source with result of extension.
02896   Value *Src = I->getOperand(0);
02897   if (Src->hasOneUse())
02898     return false;
02899 
02900   // Only do this xform if truncating is free.
02901   if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType()))
02902     return false;
02903 
02904   // Only safe to perform the optimization if the source is also defined in
02905   // this block.
02906   if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent())
02907     return false;
02908 
02909   bool DefIsLiveOut = false;
02910   for (User *U : I->users()) {
02911     Instruction *UI = cast<Instruction>(U);
02912 
02913     // Figure out which BB this ext is used in.
02914     BasicBlock *UserBB = UI->getParent();
02915     if (UserBB == DefBB) continue;
02916     DefIsLiveOut = true;
02917     break;
02918   }
02919   if (!DefIsLiveOut)
02920     return false;
02921 
02922   // Make sure none of the uses are PHI nodes.
02923   for (User *U : Src->users()) {
02924     Instruction *UI = cast<Instruction>(U);
02925     BasicBlock *UserBB = UI->getParent();
02926     if (UserBB == DefBB) continue;
02927     // Be conservative. We don't want this xform to end up introducing
02928     // reloads just before load / store instructions.
02929     if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI))
02930       return false;
02931   }
02932 
02933   // InsertedTruncs - Only insert one trunc in each block once.
02934   DenseMap<BasicBlock*, Instruction*> InsertedTruncs;
02935 
02936   bool MadeChange = false;
02937   for (Use &U : Src->uses()) {
02938     Instruction *User = cast<Instruction>(U.getUser());
02939 
02940     // Figure out which BB this ext is used in.
02941     BasicBlock *UserBB = User->getParent();
02942     if (UserBB == DefBB) continue;
02943 
02944     // Both src and def are live in this block. Rewrite the use.
02945     Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
02946 
02947     if (!InsertedTrunc) {
02948       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
02949       InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt);
02950       InsertedTruncsSet.insert(InsertedTrunc);
02951     }
02952 
02953     // Replace a use of the {s|z}ext source with a use of the result.
02954     U = InsertedTrunc;
02955     ++NumExtUses;
02956     MadeChange = true;
02957   }
02958 
02959   return MadeChange;
02960 }
02961 
02962 /// isFormingBranchFromSelectProfitable - Returns true if a SelectInst should be
02963 /// turned into an explicit branch.
02964 static bool isFormingBranchFromSelectProfitable(SelectInst *SI) {
02965   // FIXME: This should use the same heuristics as IfConversion to determine
02966   // whether a select is better represented as a branch.  This requires that
02967   // branch probability metadata is preserved for the select, which is not the
02968   // case currently.
02969 
02970   CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
02971 
02972   // If the branch is predicted right, an out of order CPU can avoid blocking on
02973   // the compare.  Emit cmovs on compares with a memory operand as branches to
02974   // avoid stalls on the load from memory.  If the compare has more than one use
02975   // there's probably another cmov or setcc around so it's not worth emitting a
02976   // branch.
02977   if (!Cmp)
02978     return false;
02979 
02980   Value *CmpOp0 = Cmp->getOperand(0);
02981   Value *CmpOp1 = Cmp->getOperand(1);
02982 
02983   // We check that the memory operand has one use to avoid uses of the loaded
02984   // value directly after the compare, making branches unprofitable.
02985   return Cmp->hasOneUse() &&
02986          ((isa<LoadInst>(CmpOp0) && CmpOp0->hasOneUse()) ||
02987           (isa<LoadInst>(CmpOp1) && CmpOp1->hasOneUse()));
02988 }
02989 
02990 
02991 /// If we have a SelectInst that will likely profit from branch prediction,
02992 /// turn it into a branch.
02993 bool CodeGenPrepare::OptimizeSelectInst(SelectInst *SI) {
02994   bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
02995 
02996   // Can we convert the 'select' to CF ?
02997   if (DisableSelectToBranch || OptSize || !TLI || VectorCond)
02998     return false;
02999 
03000   TargetLowering::SelectSupportKind SelectKind;
03001   if (VectorCond)
03002     SelectKind = TargetLowering::VectorMaskSelect;
03003   else if (SI->getType()->isVectorTy())
03004     SelectKind = TargetLowering::ScalarCondVectorVal;
03005   else
03006     SelectKind = TargetLowering::ScalarValSelect;
03007 
03008   // Do we have efficient codegen support for this kind of 'selects' ?
03009   if (TLI->isSelectSupported(SelectKind)) {
03010     // We have efficient codegen support for the select instruction.
03011     // Check if it is profitable to keep this 'select'.
03012     if (!TLI->isPredictableSelectExpensive() ||
03013         !isFormingBranchFromSelectProfitable(SI))
03014       return false;
03015   }
03016 
03017   ModifiedDT = true;
03018 
03019   // First, we split the block containing the select into 2 blocks.
03020   BasicBlock *StartBlock = SI->getParent();
03021   BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(SI));
03022   BasicBlock *NextBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");
03023 
03024   // Create a new block serving as the landing pad for the branch.
03025   BasicBlock *SmallBlock = BasicBlock::Create(SI->getContext(), "select.mid",
03026                                              NextBlock->getParent(), NextBlock);
03027 
03028   // Move the unconditional branch from the block with the select in it into our
03029   // landing pad block.
03030   StartBlock->getTerminator()->eraseFromParent();
03031   BranchInst::Create(NextBlock, SmallBlock);
03032 
03033   // Insert the real conditional branch based on the original condition.
03034   BranchInst::Create(NextBlock, SmallBlock, SI->getCondition(), SI);
03035 
03036   // The select itself is replaced with a PHI Node.
03037   PHINode *PN = PHINode::Create(SI->getType(), 2, "", NextBlock->begin());
03038   PN->takeName(SI);
03039   PN->addIncoming(SI->getTrueValue(), StartBlock);
03040   PN->addIncoming(SI->getFalseValue(), SmallBlock);
03041   SI->replaceAllUsesWith(PN);
03042   SI->eraseFromParent();
03043 
03044   // Instruct OptimizeBlock to skip to the next block.
03045   CurInstIterator = StartBlock->end();
03046   ++NumSelectsExpanded;
03047   return true;
03048 }
03049 
03050 static bool isBroadcastShuffle(ShuffleVectorInst *SVI) {
03051   SmallVector<int, 16> Mask(SVI->getShuffleMask());
03052   int SplatElem = -1;
03053   for (unsigned i = 0; i < Mask.size(); ++i) {
03054     if (SplatElem != -1 && Mask[i] != -1 && Mask[i] != SplatElem)
03055       return false;
03056     SplatElem = Mask[i];
03057   }
03058 
03059   return true;
03060 }
03061 
03062 /// Some targets have expensive vector shifts if the lanes aren't all the same
03063 /// (e.g. x86 only introduced "vpsllvd" and friends with AVX2). In these cases
03064 /// it's often worth sinking a shufflevector splat down to its use so that
03065 /// codegen can spot all lanes are identical.
03066 bool CodeGenPrepare::OptimizeShuffleVectorInst(ShuffleVectorInst *SVI) {
03067   BasicBlock *DefBB = SVI->getParent();
03068 
03069   // Only do this xform if variable vector shifts are particularly expensive.
03070   if (!TLI || !TLI->isVectorShiftByScalarCheap(SVI->getType()))
03071     return false;
03072 
03073   // We only expect better codegen by sinking a shuffle if we can recognise a
03074   // constant splat.
03075   if (!isBroadcastShuffle(SVI))
03076     return false;
03077 
03078   // InsertedShuffles - Only insert a shuffle in each block once.
03079   DenseMap<BasicBlock*, Instruction*> InsertedShuffles;
03080 
03081   bool MadeChange = false;
03082   for (User *U : SVI->users()) {
03083     Instruction *UI = cast<Instruction>(U);
03084 
03085     // Figure out which BB this ext is used in.
03086     BasicBlock *UserBB = UI->getParent();
03087     if (UserBB == DefBB) continue;
03088 
03089     // For now only apply this when the splat is used by a shift instruction.
03090     if (!UI->isShift()) continue;
03091 
03092     // Everything checks out, sink the shuffle if the user's block doesn't
03093     // already have a copy.
03094     Instruction *&InsertedShuffle = InsertedShuffles[UserBB];
03095 
03096     if (!InsertedShuffle) {
03097       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
03098       InsertedShuffle = new ShuffleVectorInst(SVI->getOperand(0),
03099                                               SVI->getOperand(1),
03100                                               SVI->getOperand(2), "", InsertPt);
03101     }
03102 
03103     UI->replaceUsesOfWith(SVI, InsertedShuffle);
03104     MadeChange = true;
03105   }
03106 
03107   // If we removed all uses, nuke the shuffle.
03108   if (SVI->use_empty()) {
03109     SVI->eraseFromParent();
03110     MadeChange = true;
03111   }
03112 
03113   return MadeChange;
03114 }
03115 
03116 bool CodeGenPrepare::OptimizeInst(Instruction *I) {
03117   if (PHINode *P = dyn_cast<PHINode>(I)) {
03118     // It is possible for very late stage optimizations (such as SimplifyCFG)
03119     // to introduce PHI nodes too late to be cleaned up.  If we detect such a
03120     // trivial PHI, go ahead and zap it here.
03121     if (Value *V = SimplifyInstruction(P, TLI ? TLI->getDataLayout() : nullptr,
03122                                        TLInfo, DT)) {
03123       P->replaceAllUsesWith(V);
03124       P->eraseFromParent();
03125       ++NumPHIsElim;
03126       return true;
03127     }
03128     return false;
03129   }
03130 
03131   if (CastInst *CI = dyn_cast<CastInst>(I)) {
03132     // If the source of the cast is a constant, then this should have
03133     // already been constant folded.  The only reason NOT to constant fold
03134     // it is if something (e.g. LSR) was careful to place the constant
03135     // evaluation in a block other than then one that uses it (e.g. to hoist
03136     // the address of globals out of a loop).  If this is the case, we don't
03137     // want to forward-subst the cast.
03138     if (isa<Constant>(CI->getOperand(0)))
03139       return false;
03140 
03141     if (TLI && OptimizeNoopCopyExpression(CI, *TLI))
03142       return true;
03143 
03144     if (isa<ZExtInst>(I) || isa<SExtInst>(I)) {
03145       /// Sink a zext or sext into its user blocks if the target type doesn't
03146       /// fit in one register
03147       if (TLI && TLI->getTypeAction(CI->getContext(),
03148                                     TLI->getValueType(CI->getType())) ==
03149                      TargetLowering::TypeExpandInteger) {
03150         return SinkCast(CI);
03151       } else {
03152         bool MadeChange = MoveExtToFormExtLoad(I);
03153         return MadeChange | OptimizeExtUses(I);
03154       }
03155     }
03156     return false;
03157   }
03158 
03159   if (CmpInst *CI = dyn_cast<CmpInst>(I))
03160     if (!TLI || !TLI->hasMultipleConditionRegisters())
03161       return OptimizeCmpExpression(CI);
03162 
03163   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
03164     if (TLI)
03165       return OptimizeMemoryInst(I, I->getOperand(0), LI->getType());
03166     return false;
03167   }
03168 
03169   if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
03170     if (TLI)
03171       return OptimizeMemoryInst(I, SI->getOperand(1),
03172                                 SI->getOperand(0)->getType());
03173     return false;
03174   }
03175 
03176   BinaryOperator *BinOp = dyn_cast<BinaryOperator>(I);
03177 
03178   if (BinOp && (BinOp->getOpcode() == Instruction::AShr ||
03179                 BinOp->getOpcode() == Instruction::LShr)) {
03180     ConstantInt *CI = dyn_cast<ConstantInt>(BinOp->getOperand(1));
03181     if (TLI && CI && TLI->hasExtractBitsInsn())
03182       return OptimizeExtractBits(BinOp, CI, *TLI);
03183 
03184     return false;
03185   }
03186 
03187   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
03188     if (GEPI->hasAllZeroIndices()) {
03189       /// The GEP operand must be a pointer, so must its result -> BitCast
03190       Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
03191                                         GEPI->getName(), GEPI);
03192       GEPI->replaceAllUsesWith(NC);
03193       GEPI->eraseFromParent();
03194       ++NumGEPsElim;
03195       OptimizeInst(NC);
03196       return true;
03197     }
03198     return false;
03199   }
03200 
03201   if (CallInst *CI = dyn_cast<CallInst>(I))
03202     return OptimizeCallInst(CI);
03203 
03204   if (SelectInst *SI = dyn_cast<SelectInst>(I))
03205     return OptimizeSelectInst(SI);
03206 
03207   if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I))
03208     return OptimizeShuffleVectorInst(SVI);
03209 
03210   return false;
03211 }
03212 
03213 // In this pass we look for GEP and cast instructions that are used
03214 // across basic blocks and rewrite them to improve basic-block-at-a-time
03215 // selection.
03216 bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) {
03217   SunkAddrs.clear();
03218   bool MadeChange = false;
03219 
03220   CurInstIterator = BB.begin();
03221   while (CurInstIterator != BB.end())
03222     MadeChange |= OptimizeInst(CurInstIterator++);
03223 
03224   MadeChange |= DupRetToEnableTailCallOpts(&BB);
03225 
03226   return MadeChange;
03227 }
03228 
03229 // llvm.dbg.value is far away from the value then iSel may not be able
03230 // handle it properly. iSel will drop llvm.dbg.value if it can not
03231 // find a node corresponding to the value.
03232 bool CodeGenPrepare::PlaceDbgValues(Function &F) {
03233   bool MadeChange = false;
03234   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
03235     Instruction *PrevNonDbgInst = nullptr;
03236     for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE;) {
03237       Instruction *Insn = BI; ++BI;
03238       DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn);
03239       // Leave dbg.values that refer to an alloca alone. These
03240       // instrinsics describe the address of a variable (= the alloca)
03241       // being taken.  They should not be moved next to the alloca
03242       // (and to the beginning of the scope), but rather stay close to
03243       // where said address is used.
03244       if (!DVI || (DVI->getValue() && isa<AllocaInst>(DVI->getValue()))) {
03245         PrevNonDbgInst = Insn;
03246         continue;
03247       }
03248 
03249       Instruction *VI = dyn_cast_or_null<Instruction>(DVI->getValue());
03250       if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) {
03251         DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI);
03252         DVI->removeFromParent();
03253         if (isa<PHINode>(VI))
03254           DVI->insertBefore(VI->getParent()->getFirstInsertionPt());
03255         else
03256           DVI->insertAfter(VI);
03257         MadeChange = true;
03258         ++NumDbgValueMoved;
03259       }
03260     }
03261   }
03262   return MadeChange;
03263 }
03264 
03265 // If there is a sequence that branches based on comparing a single bit
03266 // against zero that can be combined into a single instruction, and the
03267 // target supports folding these into a single instruction, sink the
03268 // mask and compare into the branch uses. Do this before OptimizeBlock ->
03269 // OptimizeInst -> OptimizeCmpExpression, which perturbs the pattern being
03270 // searched for.
03271 bool CodeGenPrepare::sinkAndCmp(Function &F) {
03272   if (!EnableAndCmpSinking)
03273     return false;
03274   if (!TLI || !TLI->isMaskAndBranchFoldingLegal())
03275     return false;
03276   bool MadeChange = false;
03277   for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
03278     BasicBlock *BB = I++;
03279 
03280     // Does this BB end with the following?
03281     //   %andVal = and %val, #single-bit-set
03282     //   %icmpVal = icmp %andResult, 0
03283     //   br i1 %cmpVal label %dest1, label %dest2"
03284     BranchInst *Brcc = dyn_cast<BranchInst>(BB->getTerminator());
03285     if (!Brcc || !Brcc->isConditional())
03286       continue;
03287     ICmpInst *Cmp = dyn_cast<ICmpInst>(Brcc->getOperand(0));
03288     if (!Cmp || Cmp->getParent() != BB)
03289       continue;
03290     ConstantInt *Zero = dyn_cast<ConstantInt>(Cmp->getOperand(1));
03291     if (!Zero || !Zero->isZero())
03292       continue;
03293     Instruction *And = dyn_cast<Instruction>(Cmp->getOperand(0));
03294     if (!And || And->getOpcode() != Instruction::And || And->getParent() != BB)
03295       continue;
03296     ConstantInt* Mask = dyn_cast<ConstantInt>(And->getOperand(1));
03297     if (!Mask || !Mask->getUniqueInteger().isPowerOf2())
03298       continue;
03299     DEBUG(dbgs() << "found and; icmp ?,0; brcc\n"); DEBUG(BB->dump());
03300 
03301     // Push the "and; icmp" for any users that are conditional branches.
03302     // Since there can only be one branch use per BB, we don't need to keep
03303     // track of which BBs we insert into.
03304     for (Value::use_iterator UI = Cmp->use_begin(), E = Cmp->use_end();
03305          UI != E; ) {
03306       Use &TheUse = *UI;
03307       // Find brcc use.
03308       BranchInst *BrccUser = dyn_cast<BranchInst>(*UI);
03309       ++UI;
03310       if (!BrccUser || !BrccUser->isConditional())
03311         continue;
03312       BasicBlock *UserBB = BrccUser->getParent();
03313       if (UserBB == BB) continue;
03314       DEBUG(dbgs() << "found Brcc use\n");
03315 
03316       // Sink the "and; icmp" to use.
03317       MadeChange = true;
03318       BinaryOperator *NewAnd =
03319         BinaryOperator::CreateAnd(And->getOperand(0), And->getOperand(1), "",
03320                                   BrccUser);
03321       CmpInst *NewCmp =
03322         CmpInst::Create(Cmp->getOpcode(), Cmp->getPredicate(), NewAnd, Zero,
03323                         "", BrccUser);
03324       TheUse = NewCmp;
03325       ++NumAndCmpsMoved;
03326       DEBUG(BrccUser->getParent()->dump());
03327     }
03328   }
03329   return MadeChange;
03330 }