lib/Transforms/Scalar/CodeGenPrepare.cpp

   1 //===- CodeGenPrepare.cpp - Prepare a function for code generation --------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass munges the code in the input function to better prepare it for
  11 // SelectionDAG-based code generation. This works around limitations in it's
  12 // basic-block-at-a-time approach. It should eventually be removed.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "codegenprepare"
  17 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/SmallSet.h"
  20 #include "llvm/ADT/Statistic.h"
  21 #include "llvm/Analysis/DominatorInternals.h"
  22 #include "llvm/Analysis/Dominators.h"
  23 #include "llvm/Analysis/InstructionSimplify.h"
  24 #include "llvm/Analysis/ProfileInfo.h"
  25 #include "llvm/Assembly/Writer.h"
  26 #include "llvm/IR/Constants.h"
  27 #include "llvm/IR/DataLayout.h"
  28 #include "llvm/IR/DerivedTypes.h"
  29 #include "llvm/IR/Function.h"
  30 #include "llvm/IR/IRBuilder.h"
  31 #include "llvm/IR/InlineAsm.h"
  32 #include "llvm/IR/Instructions.h"
  33 #include "llvm/IR/IntrinsicInst.h"
  34 #include "llvm/Pass.h"
  35 #include "llvm/Support/CallSite.h"
  36 #include "llvm/Support/CommandLine.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Support/GetElementPtrTypeIterator.h"
  39 #include "llvm/Support/PatternMatch.h"
  40 #include "llvm/Support/ValueHandle.h"
  41 #include "llvm/Support/raw_ostream.h"
  42 #include "llvm/Target/TargetLibraryInfo.h"
  43 #include "llvm/Target/TargetLowering.h"
  44 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  45 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  46 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
  47 #include "llvm/Transforms/Utils/Local.h"
  48 using namespace llvm;
  49 using namespace llvm::PatternMatch;
  50
  51 STATISTIC(NumBlocksElim, "Number of blocks eliminated");
  52 STATISTIC(NumPHIsElim,   "Number of trivial PHIs eliminated");
  53 STATISTIC(NumGEPsElim,   "Number of GEPs converted to casts");
  54 STATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of "
  55                       "sunken Cmps");
  56 STATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses "
  57                        "of sunken Casts");
  58 STATISTIC(NumMemoryInsts, "Number of memory instructions whose address "
  59                           "computations were sunk");
  60 STATISTIC(NumExtsMoved,  "Number of [s|z]ext instructions combined with loads");
  61 STATISTIC(NumExtUses,    "Number of uses of [s|z]ext instructions optimized");
  62 STATISTIC(NumRetsDup,    "Number of return instructions duplicated");
  63 STATISTIC(NumDbgValueMoved, "Number of debug value instructions moved");
  64 STATISTIC(NumSelectsExpanded, "Number of selects turned into branches");
  65
  66 static cl::opt<bool> DisableBranchOpts(
  67   "disable-cgp-branch-opts", cl::Hidden, cl::init(false),
  68   cl::desc("Disable branch optimizations in CodeGenPrepare"));
  69
  70 static cl::opt<bool> DisableSelectToBranch(
  71   "disable-cgp-select2branch", cl::Hidden, cl::init(false),
  72   cl::desc("Disable select to branch conversion."));
  73
  74 namespace {
  75   class CodeGenPrepare : public FunctionPass {
  76     /// TLI - Keep a pointer of a TargetLowering to consult for determining
  77     /// transformation profitability.
  78     const TargetLowering *TLI;
  79     const TargetLibraryInfo *TLInfo;
  80     DominatorTree *DT;
  81     ProfileInfo *PFI;
  82
  83     /// CurInstIterator - As we scan instructions optimizing them, this is the
  84     /// next instruction to optimize.  Xforms that can invalidate this should
  85     /// update it.
  86     BasicBlock::iterator CurInstIterator;
  87
  88     /// Keeps track of non-local addresses that have been sunk into a block.
  89     /// This allows us to avoid inserting duplicate code for blocks with
  90     /// multiple load/stores of the same address.
  91     DenseMap<Value*, Value*> SunkAddrs;
  92
  93     /// ModifiedDT - If CFG is modified in anyway, dominator tree may need to
  94     /// be updated.
  95     bool ModifiedDT;
  96
  97     /// OptSize - True if optimizing for size.
  98     bool OptSize;
  99
 100   public:
 101     static char ID; // Pass identification, replacement for typeid
 102     explicit CodeGenPrepare(const TargetLowering *tli = 0)
 103       : FunctionPass(ID), TLI(tli) {
 104         initializeCodeGenPreparePass(*PassRegistry::getPassRegistry());
 105       }
 106     bool runOnFunction(Function &F);
 107
 108     const char *getPassName() const { return "CodeGen Prepare"; }
 109
 110     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 111       AU.addPreserved<DominatorTree>();
 112       AU.addPreserved<ProfileInfo>();
 113       AU.addRequired<TargetLibraryInfo>();
 114     }
 115
 116   private:
 117     bool EliminateFallThrough(Function &F);
 118     bool EliminateMostlyEmptyBlocks(Function &F);
 119     bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
 120     void EliminateMostlyEmptyBlock(BasicBlock *BB);
 121     bool OptimizeBlock(BasicBlock &BB);
 122     bool OptimizeInst(Instruction *I);
 123     bool OptimizeMemoryInst(Instruction *I, Value *Addr, Type *AccessTy);
 124     bool OptimizeInlineAsmInst(CallInst *CS);
 125     bool OptimizeCallInst(CallInst *CI);
 126     bool MoveExtToFormExtLoad(Instruction *I);
 127     bool OptimizeExtUses(Instruction *I);
 128     bool OptimizeSelectInst(SelectInst *SI);
 129     bool DupRetToEnableTailCallOpts(BasicBlock *BB);
 130     bool PlaceDbgValues(Function &F);
 131   };
 132 }
 133
 134 char CodeGenPrepare::ID = 0;
 135 INITIALIZE_PASS_BEGIN(CodeGenPrepare, "codegenprepare",
 136                 "Optimize for code generation", false, false)
 137 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 138 INITIALIZE_PASS_END(CodeGenPrepare, "codegenprepare",
 139                 "Optimize for code generation", false, false)
 140
 141 FunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) {
 142   return new CodeGenPrepare(TLI);
 143 }
 144
 145 bool CodeGenPrepare::runOnFunction(Function &F) {
 146   bool EverMadeChange = false;
 147
 148   ModifiedDT = false;
 149   TLInfo = &getAnalysis<TargetLibraryInfo>();
 150   DT = getAnalysisIfAvailable<DominatorTree>();
 151   PFI = getAnalysisIfAvailable<ProfileInfo>();
 152   OptSize = F.getAttributes().hasAttribute(AttributeSet::FunctionIndex,
 153                                            Attribute::OptimizeForSize);
 154
 155   /// This optimization identifies DIV instructions that can be
 156   /// profitably bypassed and carried out with a shorter, faster divide.
 157   if (!OptSize && TLI && TLI->isSlowDivBypassed()) {
 158     const DenseMap<unsigned int, unsigned int> &BypassWidths =
 159        TLI->getBypassSlowDivWidths();
 160     for (Function::iterator I = F.begin(); I != F.end(); I++)
 161       EverMadeChange |= bypassSlowDivision(F, I, BypassWidths);
 162   }
 163
 164   // Eliminate blocks that contain only PHI nodes and an
 165   // unconditional branch.
 166   EverMadeChange |= EliminateMostlyEmptyBlocks(F);
 167
 168   // llvm.dbg.value is far away from the value then iSel may not be able
 169   // handle it properly. iSel will drop llvm.dbg.value if it can not
 170   // find a node corresponding to the value.
 171   EverMadeChange |= PlaceDbgValues(F);
 172
 173   bool MadeChange = true;
 174   while (MadeChange) {
 175     MadeChange = false;
 176     for (Function::iterator I = F.begin(); I != F.end(); ) {
 177       BasicBlock *BB = I++;
 178       MadeChange |= OptimizeBlock(*BB);
 179     }
 180     EverMadeChange |= MadeChange;
 181   }
 182
 183   SunkAddrs.clear();
 184
 185   if (!DisableBranchOpts) {
 186     MadeChange = false;
 187     SmallPtrSet<BasicBlock*, 8> WorkList;
 188     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
 189       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
 190       MadeChange |= ConstantFoldTerminator(BB, true);
 191       if (!MadeChange) continue;
 192
 193       for (SmallVectorImpl<BasicBlock*>::iterator
 194              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
 195         if (pred_begin(*II) == pred_end(*II))
 196           WorkList.insert(*II);
 197     }
 198
 199     // Delete the dead blocks and any of their dead successors.
 200     MadeChange |= !WorkList.empty();
 201     while (!WorkList.empty()) {
 202       BasicBlock *BB = *WorkList.begin();
 203       WorkList.erase(BB);
 204       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
 205
 206       DeleteDeadBlock(BB);
 207
 208       for (SmallVectorImpl<BasicBlock*>::iterator
 209              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
 210         if (pred_begin(*II) == pred_end(*II))
 211           WorkList.insert(*II);
 212     }
 213
 214     // Merge pairs of basic blocks with unconditional branches, connected by
 215     // a single edge.
 216     if (EverMadeChange || MadeChange)
 217       MadeChange |= EliminateFallThrough(F);
 218
 219     if (MadeChange)
 220       ModifiedDT = true;
 221     EverMadeChange |= MadeChange;
 222   }
 223
 224   if (ModifiedDT && DT)
 225     DT->DT->recalculate(F);
 226
 227   return EverMadeChange;
 228 }
 229
 230 /// EliminateFallThrough - Merge basic blocks which are connected
 231 /// by a single edge, where one of the basic blocks has a single successor
 232 /// pointing to the other basic block, which has a single predecessor.
 233 bool CodeGenPrepare::EliminateFallThrough(Function &F) {
 234   bool Changed = false;
 235   // Scan all of the blocks in the function, except for the entry block.
 236   for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) {
 237     BasicBlock *BB = I++;
 238     // If the destination block has a single pred, then this is a trivial
 239     // edge, just collapse it.
 240     BasicBlock *SinglePred = BB->getSinglePredecessor();
 241
 242     // Don't merge if BB's address is taken.
 243     if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
 244
 245     BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
 246     if (Term && !Term->isConditional()) {
 247       Changed = true;
 248       DEBUG(dbgs() << "To merge:\n"<< *SinglePred << "\n\n\n");
 249       // Remember if SinglePred was the entry block of the function.
 250       // If so, we will need to move BB back to the entry position.
 251       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
 252       MergeBasicBlockIntoOnlyPred(BB, this);
 253
 254       if (isEntry && BB != &BB->getParent()->getEntryBlock())
 255         BB->moveBefore(&BB->getParent()->getEntryBlock());
 256
 257       // We have erased a block. Update the iterator.
 258       I = BB;
 259     }
 260   }
 261   return Changed;
 262 }
 263
 264 /// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes,
 265 /// debug info directives, and an unconditional branch.  Passes before isel
 266 /// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for
 267 /// isel.  Start by eliminating these blocks so we can split them the way we
 268 /// want them.
 269 bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) {
 270   bool MadeChange = false;
 271   // Note that this intentionally skips the entry block.
 272   for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) {
 273     BasicBlock *BB = I++;
 274
 275     // If this block doesn't end with an uncond branch, ignore it.
 276     BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 277     if (!BI || !BI->isUnconditional())
 278       continue;
 279
 280     // If the instruction before the branch (skipping debug info) isn't a phi
 281     // node, then other stuff is happening here.
 282     BasicBlock::iterator BBI = BI;
 283     if (BBI != BB->begin()) {
 284       --BBI;
 285       while (isa<DbgInfoIntrinsic>(BBI)) {
 286         if (BBI == BB->begin())
 287           break;
 288         --BBI;
 289       }
 290       if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
 291         continue;
 292     }
 293
 294     // Do not break infinite loops.
 295     BasicBlock *DestBB = BI->getSuccessor(0);
 296     if (DestBB == BB)
 297       continue;
 298
 299     if (!CanMergeBlocks(BB, DestBB))
 300       continue;
 301
 302     EliminateMostlyEmptyBlock(BB);
 303     MadeChange = true;
 304   }
 305   return MadeChange;
 306 }
 307
 308 /// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a
 309 /// single uncond branch between them, and BB contains no other non-phi
 310 /// instructions.
 311 bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB,
 312                                     const BasicBlock *DestBB) const {
 313   // We only want to eliminate blocks whose phi nodes are used by phi nodes in
 314   // the successor.  If there are more complex condition (e.g. preheaders),
 315   // don't mess around with them.
 316   BasicBlock::const_iterator BBI = BB->begin();
 317   while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
 318     for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end();
 319          UI != E; ++UI) {
 320       const Instruction *User = cast<Instruction>(*UI);
 321       if (User->getParent() != DestBB || !isa<PHINode>(User))
 322         return false;
 323       // If User is inside DestBB block and it is a PHINode then check
 324       // incoming value. If incoming value is not from BB then this is
 325       // a complex condition (e.g. preheaders) we want to avoid here.
 326       if (User->getParent() == DestBB) {
 327         if (const PHINode *UPN = dyn_cast<PHINode>(User))
 328           for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) {
 329             Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I));
 330             if (Insn && Insn->getParent() == BB &&
 331                 Insn->getParent() != UPN->getIncomingBlock(I))
 332               return false;
 333           }
 334       }
 335     }
 336   }
 337
 338   // If BB and DestBB contain any common predecessors, then the phi nodes in BB
 339   // and DestBB may have conflicting incoming values for the block.  If so, we
 340   // can't merge the block.
 341   const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin());
 342   if (!DestBBPN) return true;  // no conflict.
 343
 344   // Collect the preds of BB.
 345   SmallPtrSet<const BasicBlock*, 16> BBPreds;
 346   if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
 347     // It is faster to get preds from a PHI than with pred_iterator.
 348     for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
 349       BBPreds.insert(BBPN->getIncomingBlock(i));
 350   } else {
 351     BBPreds.insert(pred_begin(BB), pred_end(BB));
 352   }
 353
 354   // Walk the preds of DestBB.
 355   for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) {
 356     BasicBlock *Pred = DestBBPN->getIncomingBlock(i);
 357     if (BBPreds.count(Pred)) {   // Common predecessor?
 358       BBI = DestBB->begin();
 359       while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
 360         const Value *V1 = PN->getIncomingValueForBlock(Pred);
 361         const Value *V2 = PN->getIncomingValueForBlock(BB);
 362
 363         // If V2 is a phi node in BB, look up what the mapped value will be.
 364         if (const PHINode *V2PN = dyn_cast<PHINode>(V2))
 365           if (V2PN->getParent() == BB)
 366             V2 = V2PN->getIncomingValueForBlock(Pred);
 367
 368         // If there is a conflict, bail out.
 369         if (V1 != V2) return false;
 370       }
 371     }
 372   }
 373
 374   return true;
 375 }
 376
 377
 378 /// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and
 379 /// an unconditional branch in it.
 380 void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) {
 381   BranchInst *BI = cast<BranchInst>(BB->getTerminator());
 382   BasicBlock *DestBB = BI->getSuccessor(0);
 383
 384   DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB);
 385
 386   // If the destination block has a single pred, then this is a trivial edge,
 387   // just collapse it.
 388   if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
 389     if (SinglePred != DestBB) {
 390       // Remember if SinglePred was the entry block of the function.  If so, we
 391       // will need to move BB back to the entry position.
 392       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
 393       MergeBasicBlockIntoOnlyPred(DestBB, this);
 394
 395       if (isEntry && BB != &BB->getParent()->getEntryBlock())
 396         BB->moveBefore(&BB->getParent()->getEntryBlock());
 397
 398       DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
 399       return;
 400     }
 401   }
 402
 403   // Otherwise, we have multiple predecessors of BB.  Update the PHIs in DestBB
 404   // to handle the new incoming edges it is about to have.
 405   PHINode *PN;
 406   for (BasicBlock::iterator BBI = DestBB->begin();
 407        (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
 408     // Remove the incoming value for BB, and remember it.
 409     Value *InVal = PN->removeIncomingValue(BB, false);
 410
 411     // Two options: either the InVal is a phi node defined in BB or it is some
 412     // value that dominates BB.
 413     PHINode *InValPhi = dyn_cast<PHINode>(InVal);
 414     if (InValPhi && InValPhi->getParent() == BB) {
 415       // Add all of the input values of the input PHI as inputs of this phi.
 416       for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i)
 417         PN->addIncoming(InValPhi->getIncomingValue(i),
 418                         InValPhi->getIncomingBlock(i));
 419     } else {
 420       // Otherwise, add one instance of the dominating value for each edge that
 421       // we will be adding.
 422       if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
 423         for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
 424           PN->addIncoming(InVal, BBPN->getIncomingBlock(i));
 425       } else {
 426         for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
 427           PN->addIncoming(InVal, *PI);
 428       }
 429     }
 430   }
 431
 432   // The PHIs are now updated, change everything that refers to BB to use
 433   // DestBB and remove BB.
 434   BB->replaceAllUsesWith(DestBB);
 435   if (DT && !ModifiedDT) {
 436     BasicBlock *BBIDom  = DT->getNode(BB)->getIDom()->getBlock();
 437     BasicBlock *DestBBIDom = DT->getNode(DestBB)->getIDom()->getBlock();
 438     BasicBlock *NewIDom = DT->findNearestCommonDominator(BBIDom, DestBBIDom);
 439     DT->changeImmediateDominator(DestBB, NewIDom);
 440     DT->eraseNode(BB);
 441   }
 442   if (PFI) {
 443     PFI->replaceAllUses(BB, DestBB);
 444     PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB));
 445   }
 446   BB->eraseFromParent();
 447   ++NumBlocksElim;
 448
 449   DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
 450 }
 451
 452 /// OptimizeNoopCopyExpression - If the specified cast instruction is a noop
 453 /// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC),
 454 /// sink it into user blocks to reduce the number of virtual
 455 /// registers that must be created and coalesced.
 456 ///
 457 /// Return true if any changes are made.
 458 ///
 459 static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){
 460   // If this is a noop copy,
 461   EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType());
 462   EVT DstVT = TLI.getValueType(CI->getType());
 463
 464   // This is an fp<->int conversion?
 465   if (SrcVT.isInteger() != DstVT.isInteger())
 466     return false;
 467
 468   // If this is an extension, it will be a zero or sign extension, which
 469   // isn't a noop.
 470   if (SrcVT.bitsLT(DstVT)) return false;
 471
 472   // If these values will be promoted, find out what they will be promoted
 473   // to.  This helps us consider truncates on PPC as noop copies when they
 474   // are.
 475   if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
 476       TargetLowering::TypePromoteInteger)
 477     SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
 478   if (TLI.getTypeAction(CI->getContext(), DstVT) ==
 479       TargetLowering::TypePromoteInteger)
 480     DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
 481
 482   // If, after promotion, these are the same types, this is a noop copy.
 483   if (SrcVT != DstVT)
 484     return false;
 485
 486   BasicBlock *DefBB = CI->getParent();
 487
 488   /// InsertedCasts - Only insert a cast in each block once.
 489   DenseMap<BasicBlock*, CastInst*> InsertedCasts;
 490
 491   bool MadeChange = false;
 492   for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
 493        UI != E; ) {
 494     Use &TheUse = UI.getUse();
 495     Instruction *User = cast<Instruction>(*UI);
 496
 497     // Figure out which BB this cast is used in.  For PHI's this is the
 498     // appropriate predecessor block.
 499     BasicBlock *UserBB = User->getParent();
 500     if (PHINode *PN = dyn_cast<PHINode>(User)) {
 501       UserBB = PN->getIncomingBlock(UI);
 502     }
 503
 504     // Preincrement use iterator so we don't invalidate it.
 505     ++UI;
 506
 507     // If this user is in the same block as the cast, don't change the cast.
 508     if (UserBB == DefBB) continue;
 509
 510     // If we have already inserted a cast into this block, use it.
 511     CastInst *&InsertedCast = InsertedCasts[UserBB];
 512
 513     if (!InsertedCast) {
 514       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
 515       InsertedCast =
 516         CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "",
 517                          InsertPt);
 518       MadeChange = true;
 519     }
 520
 521     // Replace a use of the cast with a use of the new cast.
 522     TheUse = InsertedCast;
 523     ++NumCastUses;
 524   }
 525
 526   // If we removed all uses, nuke the cast.
 527   if (CI->use_empty()) {
 528     CI->eraseFromParent();
 529     MadeChange = true;
 530   }
 531
 532   return MadeChange;
 533 }
 534
 535 /// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce
 536 /// the number of virtual registers that must be created and coalesced.  This is
 537 /// a clear win except on targets with multiple condition code registers
 538 ///  (PowerPC), where it might lose; some adjustment may be wanted there.
 539 ///
 540 /// Return true if any changes are made.
 541 static bool OptimizeCmpExpression(CmpInst *CI) {
 542   BasicBlock *DefBB = CI->getParent();
 543
 544   /// InsertedCmp - Only insert a cmp in each block once.
 545   DenseMap<BasicBlock*, CmpInst*> InsertedCmps;
 546
 547   bool MadeChange = false;
 548   for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
 549        UI != E; ) {
 550     Use &TheUse = UI.getUse();
 551     Instruction *User = cast<Instruction>(*UI);
 552
 553     // Preincrement use iterator so we don't invalidate it.
 554     ++UI;
 555
 556     // Don't bother for PHI nodes.
 557     if (isa<PHINode>(User))
 558       continue;
 559
 560     // Figure out which BB this cmp is used in.
 561     BasicBlock *UserBB = User->getParent();
 562
 563     // If this user is in the same block as the cmp, don't change the cmp.
 564     if (UserBB == DefBB) continue;
 565
 566     // If we have already inserted a cmp into this block, use it.
 567     CmpInst *&InsertedCmp = InsertedCmps[UserBB];
 568
 569     if (!InsertedCmp) {
 570       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
 571       InsertedCmp =
 572         CmpInst::Create(CI->getOpcode(),
 573                         CI->getPredicate(),  CI->getOperand(0),
 574                         CI->getOperand(1), "", InsertPt);
 575       MadeChange = true;
 576     }
 577
 578     // Replace a use of the cmp with a use of the new cmp.
 579     TheUse = InsertedCmp;
 580     ++NumCmpUses;
 581   }
 582
 583   // If we removed all uses, nuke the cmp.
 584   if (CI->use_empty())
 585     CI->eraseFromParent();
 586
 587   return MadeChange;
 588 }
 589
 590 namespace {
 591 class CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls {
 592 protected:
 593   void replaceCall(Value *With) {
 594     CI->replaceAllUsesWith(With);
 595     CI->eraseFromParent();
 596   }
 597   bool isFoldable(unsigned SizeCIOp, unsigned, bool) const {
 598       if (ConstantInt *SizeCI =
 599                              dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp)))
 600         return SizeCI->isAllOnesValue();
 601     return false;
 602   }
 603 };
 604 } // end anonymous namespace
 605
 606 bool CodeGenPrepare::OptimizeCallInst(CallInst *CI) {
 607   BasicBlock *BB = CI->getParent();
 608
 609   // Lower inline assembly if we can.
 610   // If we found an inline asm expession, and if the target knows how to
 611   // lower it to normal LLVM code, do so now.
 612   if (TLI && isa<InlineAsm>(CI->getCalledValue())) {
 613     if (TLI->ExpandInlineAsm(CI)) {
 614       // Avoid invalidating the iterator.
 615       CurInstIterator = BB->begin();
 616       // Avoid processing instructions out of order, which could cause
 617       // reuse before a value is defined.
 618       SunkAddrs.clear();
 619       return true;
 620     }
 621     // Sink address computing for memory operands into the block.
 622     if (OptimizeInlineAsmInst(CI))
 623       return true;
 624   }
 625
 626   // Lower all uses of llvm.objectsize.*
 627   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
 628   if (II && II->getIntrinsicID() == Intrinsic::objectsize) {
 629     bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1);
 630     Type *ReturnTy = CI->getType();
 631     Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL);
 632
 633     // Substituting this can cause recursive simplifications, which can
 634     // invalidate our iterator.  Use a WeakVH to hold onto it in case this
 635     // happens.
 636     WeakVH IterHandle(CurInstIterator);
 637
 638     replaceAndRecursivelySimplify(CI, RetVal, TLI ? TLI->getDataLayout() : 0,
 639                                   TLInfo, ModifiedDT ? 0 : DT);
 640
 641     // If the iterator instruction was recursively deleted, start over at the
 642     // start of the block.
 643     if (IterHandle != CurInstIterator) {
 644       CurInstIterator = BB->begin();
 645       SunkAddrs.clear();
 646     }
 647     return true;
 648   }
 649
 650   if (II && TLI) {
 651     SmallVector<Value*, 2> PtrOps;
 652     Type *AccessTy;
 653     if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy))
 654       while (!PtrOps.empty())
 655         if (OptimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy))
 656           return true;
 657   }
 658
 659   // From here on out we're working with named functions.
 660   if (CI->getCalledFunction() == 0) return false;
 661
 662   // We'll need DataLayout from here on out.
 663   const DataLayout *TD = TLI ? TLI->getDataLayout() : 0;
 664   if (!TD) return false;
 665
 666   // Lower all default uses of _chk calls.  This is very similar
 667   // to what InstCombineCalls does, but here we are only lowering calls
 668   // that have the default "don't know" as the objectsize.  Anything else
 669   // should be left alone.
 670   CodeGenPrepareFortifiedLibCalls Simplifier;
 671   return Simplifier.fold(CI, TD, TLInfo);
 672 }
 673
 674 /// DupRetToEnableTailCallOpts - Look for opportunities to duplicate return
 675 /// instructions to the predecessor to enable tail call optimizations. The
 676 /// case it is currently looking for is:
 677 /// @code
 678 /// bb0:
 679 ///   %tmp0 = tail call i32 @f0()
 680 ///   br label %return
 681 /// bb1:
 682 ///   %tmp1 = tail call i32 @f1()
 683 ///   br label %return
 684 /// bb2:
 685 ///   %tmp2 = tail call i32 @f2()
 686 ///   br label %return
 687 /// return:
 688 ///   %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ]
 689 ///   ret i32 %retval
 690 /// @endcode
 691 ///
 692 /// =>
 693 ///
 694 /// @code
 695 /// bb0:
 696 ///   %tmp0 = tail call i32 @f0()
 697 ///   ret i32 %tmp0
 698 /// bb1:
 699 ///   %tmp1 = tail call i32 @f1()
 700 ///   ret i32 %tmp1
 701 /// bb2:
 702 ///   %tmp2 = tail call i32 @f2()
 703 ///   ret i32 %tmp2
 704 /// @endcode
 705 bool CodeGenPrepare::DupRetToEnableTailCallOpts(BasicBlock *BB) {
 706   if (!TLI)
 707     return false;
 708
 709   ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator());
 710   if (!RI)
 711     return false;
 712
 713   PHINode *PN = 0;
 714   BitCastInst *BCI = 0;
 715   Value *V = RI->getReturnValue();
 716   if (V) {
 717     BCI = dyn_cast<BitCastInst>(V);
 718     if (BCI)
 719       V = BCI->getOperand(0);
 720
 721     PN = dyn_cast<PHINode>(V);
 722     if (!PN)
 723       return false;
 724   }
 725
 726   if (PN && PN->getParent() != BB)
 727     return false;
 728
 729   // It's not safe to eliminate the sign / zero extension of the return value.
 730   // See llvm::isInTailCallPosition().
 731   const Function *F = BB->getParent();
 732   AttributeSet CallerAttrs = F->getAttributes();
 733   if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) ||
 734       CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt))
 735     return false;
 736
 737   // Make sure there are no instructions between the PHI and return, or that the
 738   // return is the first instruction in the block.
 739   if (PN) {
 740     BasicBlock::iterator BI = BB->begin();
 741     do { ++BI; } while (isa<DbgInfoIntrinsic>(BI));
 742     if (&*BI == BCI)
 743       // Also skip over the bitcast.
 744       ++BI;
 745     if (&*BI != RI)
 746       return false;
 747   } else {
 748     BasicBlock::iterator BI = BB->begin();
 749     while (isa<DbgInfoIntrinsic>(BI)) ++BI;
 750     if (&*BI != RI)
 751       return false;
 752   }
 753
 754   /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail
 755   /// call.
 756   SmallVector<CallInst*, 4> TailCalls;
 757   if (PN) {
 758     for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
 759       CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I));
 760       // Make sure the phi value is indeed produced by the tail call.
 761       if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) &&
 762           TLI->mayBeEmittedAsTailCall(CI))
 763         TailCalls.push_back(CI);
 764     }
 765   } else {
 766     SmallPtrSet<BasicBlock*, 4> VisitedBBs;
 767     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
 768       if (!VisitedBBs.insert(*PI))
 769         continue;
 770
 771       BasicBlock::InstListType &InstList = (*PI)->getInstList();
 772       BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin();
 773       BasicBlock::InstListType::reverse_iterator RE = InstList.rend();
 774       do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI));
 775       if (RI == RE)
 776         continue;
 777
 778       CallInst *CI = dyn_cast<CallInst>(&*RI);
 779       if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI))
 780         TailCalls.push_back(CI);
 781     }
 782   }
 783
 784   bool Changed = false;
 785   for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) {
 786     CallInst *CI = TailCalls[i];
 787     CallSite CS(CI);
 788
 789     // Conservatively require the attributes of the call to match those of the
 790     // return. Ignore noalias because it doesn't affect the call sequence.
 791     AttributeSet CalleeAttrs = CS.getAttributes();
 792     if (AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
 793           removeAttribute(Attribute::NoAlias) !=
 794         AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
 795           removeAttribute(Attribute::NoAlias))
 796       continue;
 797
 798     // Make sure the call instruction is followed by an unconditional branch to
 799     // the return block.
 800     BasicBlock *CallBB = CI->getParent();
 801     BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator());
 802     if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
 803       continue;
 804
 805     // Duplicate the return into CallBB.
 806     (void)FoldReturnIntoUncondBranch(RI, BB, CallBB);
 807     ModifiedDT = Changed = true;
 808     ++NumRetsDup;
 809   }
 810
 811   // If we eliminated all predecessors of the block, delete the block now.
 812   if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
 813     BB->eraseFromParent();
 814
 815   return Changed;
 816 }
 817
 818 //===----------------------------------------------------------------------===//
 819 // Memory Optimization
 820 //===----------------------------------------------------------------------===//
 821
 822 namespace {
 823
 824 /// ExtAddrMode - This is an extended version of TargetLowering::AddrMode
 825 /// which holds actual Value*'s for register values.
 826 struct ExtAddrMode : public TargetLowering::AddrMode {
 827   Value *BaseReg;
 828   Value *ScaledReg;
 829   ExtAddrMode() : BaseReg(0), ScaledReg(0) {}
 830   void print(raw_ostream &OS) const;
 831   void dump() const;
 832
 833   bool operator==(const ExtAddrMode& O) const {
 834     return (BaseReg == O.BaseReg) && (ScaledReg == O.ScaledReg) &&
 835            (BaseGV == O.BaseGV) && (BaseOffs == O.BaseOffs) &&
 836            (HasBaseReg == O.HasBaseReg) && (Scale == O.Scale);
 837   }
 838 };
 839
 840 static inline raw_ostream &operator<<(raw_ostream &OS, const ExtAddrMode &AM) {
 841   AM.print(OS);
 842   return OS;
 843 }
 844
 845 void ExtAddrMode::print(raw_ostream &OS) const {
 846   bool NeedPlus = false;
 847   OS << "[";
 848   if (BaseGV) {
 849     OS << (NeedPlus ? " + " : "")
 850        << "GV:";
 851     WriteAsOperand(OS, BaseGV, /*PrintType=*/false);
 852     NeedPlus = true;
 853   }
 854
 855   if (BaseOffs)
 856     OS << (NeedPlus ? " + " : "") << BaseOffs, NeedPlus = true;
 857
 858   if (BaseReg) {
 859     OS << (NeedPlus ? " + " : "")
 860        << "Base:";
 861     WriteAsOperand(OS, BaseReg, /*PrintType=*/false);
 862     NeedPlus = true;
 863   }
 864   if (Scale) {
 865     OS << (NeedPlus ? " + " : "")
 866        << Scale << "*";
 867     WriteAsOperand(OS, ScaledReg, /*PrintType=*/false);
 868     NeedPlus = true;
 869   }
 870
 871   OS << ']';
 872 }
 873
 874 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 875 void ExtAddrMode::dump() const {
 876   print(dbgs());
 877   dbgs() << '\n';
 878 }
 879 #endif
 880
 881
 882 /// \brief A helper class for matching addressing modes.
 883 ///
 884 /// This encapsulates the logic for matching the target-legal addressing modes.
 885 class AddressingModeMatcher {
 886   SmallVectorImpl<Instruction*> &AddrModeInsts;
 887   const TargetLowering &TLI;
 888
 889   /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and
 890   /// the memory instruction that we're computing this address for.
 891   Type *AccessTy;
 892   Instruction *MemoryInst;
 893
 894   /// AddrMode - This is the addressing mode that we're building up.  This is
 895   /// part of the return value of this addressing mode matching stuff.
 896   ExtAddrMode &AddrMode;
 897
 898   /// IgnoreProfitability - This is set to true when we should not do
 899   /// profitability checks.  When true, IsProfitableToFoldIntoAddressingMode
 900   /// always returns true.
 901   bool IgnoreProfitability;
 902
 903   AddressingModeMatcher(SmallVectorImpl<Instruction*> &AMI,
 904                         const TargetLowering &T, Type *AT,
 905                         Instruction *MI, ExtAddrMode &AM)
 906     : AddrModeInsts(AMI), TLI(T), AccessTy(AT), MemoryInst(MI), AddrMode(AM) {
 907     IgnoreProfitability = false;
 908   }
 909 public:
 910
 911   /// Match - Find the maximal addressing mode that a load/store of V can fold,
 912   /// give an access type of AccessTy.  This returns a list of involved
 913   /// instructions in AddrModeInsts.
 914   static ExtAddrMode Match(Value *V, Type *AccessTy,
 915                            Instruction *MemoryInst,
 916                            SmallVectorImpl<Instruction*> &AddrModeInsts,
 917                            const TargetLowering &TLI) {
 918     ExtAddrMode Result;
 919
 920     bool Success =
 921       AddressingModeMatcher(AddrModeInsts, TLI, AccessTy,
 922                             MemoryInst, Result).MatchAddr(V, 0);
 923     (void)Success; assert(Success && "Couldn't select *anything*?");
 924     return Result;
 925   }
 926 private:
 927   bool MatchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth);
 928   bool MatchAddr(Value *V, unsigned Depth);
 929   bool MatchOperationAddr(User *Operation, unsigned Opcode, unsigned Depth);
 930   bool IsProfitableToFoldIntoAddressingMode(Instruction *I,
 931                                             ExtAddrMode &AMBefore,
 932                                             ExtAddrMode &AMAfter);
 933   bool ValueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
 934 };
 935
 936 /// MatchScaledValue - Try adding ScaleReg*Scale to the current addressing mode.
 937 /// Return true and update AddrMode if this addr mode is legal for the target,
 938 /// false if not.
 939 bool AddressingModeMatcher::MatchScaledValue(Value *ScaleReg, int64_t Scale,
 940                                              unsigned Depth) {
 941   // If Scale is 1, then this is the same as adding ScaleReg to the addressing
 942   // mode.  Just process that directly.
 943   if (Scale == 1)
 944     return MatchAddr(ScaleReg, Depth);
 945
 946   // If the scale is 0, it takes nothing to add this.
 947   if (Scale == 0)
 948     return true;
 949
 950   // If we already have a scale of this value, we can add to it, otherwise, we
 951   // need an available scale field.
 952   if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg)
 953     return false;
 954
 955   ExtAddrMode TestAddrMode = AddrMode;
 956
 957   // Add scale to turn X*4+X*3 -> X*7.  This could also do things like
 958   // [A+B + A*7] -> [B+A*8].
 959   TestAddrMode.Scale += Scale;
 960   TestAddrMode.ScaledReg = ScaleReg;
 961
 962   // If the new address isn't legal, bail out.
 963   if (!TLI.isLegalAddressingMode(TestAddrMode, AccessTy))
 964     return false;
 965
 966   // It was legal, so commit it.
 967   AddrMode = TestAddrMode;
 968
 969   // Okay, we decided that we can add ScaleReg+Scale to AddrMode.  Check now
 970   // to see if ScaleReg is actually X+C.  If so, we can turn this into adding
 971   // X*Scale + C*Scale to addr mode.
 972   ConstantInt *CI = 0; Value *AddLHS = 0;
 973   if (isa<Instruction>(ScaleReg) &&  // not a constant expr.
 974       match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) {
 975     TestAddrMode.ScaledReg = AddLHS;
 976     TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale;
 977
 978     // If this addressing mode is legal, commit it and remember that we folded
 979     // this instruction.
 980     if (TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) {
 981       AddrModeInsts.push_back(cast<Instruction>(ScaleReg));
 982       AddrMode = TestAddrMode;
 983       return true;
 984     }
 985   }
 986
 987   // Otherwise, not (x+c)*scale, just return what we have.
 988   return true;
 989 }
 990
 991 /// MightBeFoldableInst - This is a little filter, which returns true if an
 992 /// addressing computation involving I might be folded into a load/store
 993 /// accessing it.  This doesn't need to be perfect, but needs to accept at least
 994 /// the set of instructions that MatchOperationAddr can.
 995 static bool MightBeFoldableInst(Instruction *I) {
 996   switch (I->getOpcode()) {
 997   case Instruction::BitCast:
 998     // Don't touch identity bitcasts.
 999     if (I->getType() == I->getOperand(0)->getType())
1000       return false;
1001     return I->getType()->isPointerTy() || I->getType()->isIntegerTy();
1002   case Instruction::PtrToInt:
1003     // PtrToInt is always a noop, as we know that the int type is pointer sized.
1004     return true;
1005   case Instruction::IntToPtr:
1006     // We know the input is intptr_t, so this is foldable.
1007     return true;
1008   case Instruction::Add:
1009     return true;
1010   case Instruction::Mul:
1011   case Instruction::Shl:
1012     // Can only handle X*C and X << C.
1013     return isa<ConstantInt>(I->getOperand(1));
1014   case Instruction::GetElementPtr:
1015     return true;
1016   default:
1017     return false;
1018   }
1019 }
1020
1021 /// MatchOperationAddr - Given an instruction or constant expr, see if we can
1022 /// fold the operation into the addressing mode.  If so, update the addressing
1023 /// mode and return true, otherwise return false without modifying AddrMode.
1024 bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode,
1025                                                unsigned Depth) {
1026   // Avoid exponential behavior on extremely deep expression trees.
1027   if (Depth >= 5) return false;
1028
1029   switch (Opcode) {
1030   case Instruction::PtrToInt:
1031     // PtrToInt is always a noop, as we know that the int type is pointer sized.
1032     return MatchAddr(AddrInst->getOperand(0), Depth);
1033   case Instruction::IntToPtr:
1034     // This inttoptr is a no-op if the integer type is pointer sized.
1035     if (TLI.getValueType(AddrInst->getOperand(0)->getType()) ==
1036         TLI.getPointerTy())
1037       return MatchAddr(AddrInst->getOperand(0), Depth);
1038     return false;
1039   case Instruction::BitCast:
1040     // BitCast is always a noop, and we can handle it as long as it is
1041     // int->int or pointer->pointer (we don't want int<->fp or something).
1042     if ((AddrInst->getOperand(0)->getType()->isPointerTy() ||
1043          AddrInst->getOperand(0)->getType()->isIntegerTy()) &&
1044         // Don't touch identity bitcasts.  These were probably put here by LSR,
1045         // and we don't want to mess around with them.  Assume it knows what it
1046         // is doing.
1047         AddrInst->getOperand(0)->getType() != AddrInst->getType())
1048       return MatchAddr(AddrInst->getOperand(0), Depth);
1049     return false;
1050   case Instruction::Add: {
1051     // Check to see if we can merge in the RHS then the LHS.  If so, we win.
1052     ExtAddrMode BackupAddrMode = AddrMode;
1053     unsigned OldSize = AddrModeInsts.size();
1054     if (MatchAddr(AddrInst->getOperand(1), Depth+1) &&
1055         MatchAddr(AddrInst->getOperand(0), Depth+1))
1056       return true;
1057
1058     // Restore the old addr mode info.
1059     AddrMode = BackupAddrMode;
1060     AddrModeInsts.resize(OldSize);
1061
1062     // Otherwise this was over-aggressive.  Try merging in the LHS then the RHS.
1063     if (MatchAddr(AddrInst->getOperand(0), Depth+1) &&
1064         MatchAddr(AddrInst->getOperand(1), Depth+1))
1065       return true;
1066
1067     // Otherwise we definitely can't merge the ADD in.
1068     AddrMode = BackupAddrMode;
1069     AddrModeInsts.resize(OldSize);
1070     break;
1071   }
1072   //case Instruction::Or:
1073   // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD.
1074   //break;
1075   case Instruction::Mul:
1076   case Instruction::Shl: {
1077     // Can only handle X*C and X << C.
1078     ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1));
1079     if (!RHS) return false;
1080     int64_t Scale = RHS->getSExtValue();
1081     if (Opcode == Instruction::Shl)
1082       Scale = 1LL << Scale;
1083
1084     return MatchScaledValue(AddrInst->getOperand(0), Scale, Depth);
1085   }
1086   case Instruction::GetElementPtr: {
1087     // Scan the GEP.  We check it if it contains constant offsets and at most
1088     // one variable offset.
1089     int VariableOperand = -1;
1090     unsigned VariableScale = 0;
1091
1092     int64_t ConstantOffset = 0;
1093     const DataLayout *TD = TLI.getDataLayout();
1094     gep_type_iterator GTI = gep_type_begin(AddrInst);
1095     for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) {
1096       if (StructType *STy = dyn_cast<StructType>(*GTI)) {
1097         const StructLayout *SL = TD->getStructLayout(STy);
1098         unsigned Idx =
1099           cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue();
1100         ConstantOffset += SL->getElementOffset(Idx);
1101       } else {
1102         uint64_t TypeSize = TD->getTypeAllocSize(GTI.getIndexedType());
1103         if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) {
1104           ConstantOffset += CI->getSExtValue()*TypeSize;
1105         } else if (TypeSize) {  // Scales of zero don't do anything.
1106           // We only allow one variable index at the moment.
1107           if (VariableOperand != -1)
1108             return false;
1109
1110           // Remember the variable index.
1111           VariableOperand = i;
1112           VariableScale = TypeSize;
1113         }
1114       }
1115     }
1116
1117     // A common case is for the GEP to only do a constant offset.  In this case,
1118     // just add it to the disp field and check validity.
1119     if (VariableOperand == -1) {
1120       AddrMode.BaseOffs += ConstantOffset;
1121       if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){
1122         // Check to see if we can fold the base pointer in too.
1123         if (MatchAddr(AddrInst->getOperand(0), Depth+1))
1124           return true;
1125       }
1126       AddrMode.BaseOffs -= ConstantOffset;
1127       return false;
1128     }
1129
1130     // Save the valid addressing mode in case we can't match.
1131     ExtAddrMode BackupAddrMode = AddrMode;
1132     unsigned OldSize = AddrModeInsts.size();
1133
1134     // See if the scale and offset amount is valid for this target.
1135     AddrMode.BaseOffs += ConstantOffset;
1136
1137     // Match the base operand of the GEP.
1138     if (!MatchAddr(AddrInst->getOperand(0), Depth+1)) {
1139       // If it couldn't be matched, just stuff the value in a register.
1140       if (AddrMode.HasBaseReg) {
1141         AddrMode = BackupAddrMode;
1142         AddrModeInsts.resize(OldSize);
1143         return false;
1144       }
1145       AddrMode.HasBaseReg = true;
1146       AddrMode.BaseReg = AddrInst->getOperand(0);
1147     }
1148
1149     // Match the remaining variable portion of the GEP.
1150     if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale,
1151                           Depth)) {
1152       // If it couldn't be matched, try stuffing the base into a register
1153       // instead of matching it, and retrying the match of the scale.
1154       AddrMode = BackupAddrMode;
1155       AddrModeInsts.resize(OldSize);
1156       if (AddrMode.HasBaseReg)
1157         return false;
1158       AddrMode.HasBaseReg = true;
1159       AddrMode.BaseReg = AddrInst->getOperand(0);
1160       AddrMode.BaseOffs += ConstantOffset;
1161       if (!MatchScaledValue(AddrInst->getOperand(VariableOperand),
1162                             VariableScale, Depth)) {
1163         // If even that didn't work, bail.
1164         AddrMode = BackupAddrMode;
1165         AddrModeInsts.resize(OldSize);
1166         return false;
1167       }
1168     }
1169
1170     return true;
1171   }
1172   }
1173   return false;
1174 }
1175
1176 /// MatchAddr - If we can, try to add the value of 'Addr' into the current
1177 /// addressing mode.  If Addr can't be added to AddrMode this returns false and
1178 /// leaves AddrMode unmodified.  This assumes that Addr is either a pointer type
1179 /// or intptr_t for the target.
1180 ///
1181 bool AddressingModeMatcher::MatchAddr(Value *Addr, unsigned Depth) {
1182   if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) {
1183     // Fold in immediates if legal for the target.
1184     AddrMode.BaseOffs += CI->getSExtValue();
1185     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
1186       return true;
1187     AddrMode.BaseOffs -= CI->getSExtValue();
1188   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) {
1189     // If this is a global variable, try to fold it into the addressing mode.
1190     if (AddrMode.BaseGV == 0) {
1191       AddrMode.BaseGV = GV;
1192       if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
1193         return true;
1194       AddrMode.BaseGV = 0;
1195     }
1196   } else if (Instruction *I = dyn_cast<Instruction>(Addr)) {
1197     ExtAddrMode BackupAddrMode = AddrMode;
1198     unsigned OldSize = AddrModeInsts.size();
1199
1200     // Check to see if it is possible to fold this operation.
1201     if (MatchOperationAddr(I, I->getOpcode(), Depth)) {
1202       // Okay, it's possible to fold this.  Check to see if it is actually
1203       // *profitable* to do so.  We use a simple cost model to avoid increasing
1204       // register pressure too much.
1205       if (I->hasOneUse() ||
1206           IsProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) {
1207         AddrModeInsts.push_back(I);
1208         return true;
1209       }
1210
1211       // It isn't profitable to do this, roll back.
1212       //cerr << "NOT FOLDING: " << *I;
1213       AddrMode = BackupAddrMode;
1214       AddrModeInsts.resize(OldSize);
1215     }
1216   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
1217     if (MatchOperationAddr(CE, CE->getOpcode(), Depth))
1218       return true;
1219   } else if (isa<ConstantPointerNull>(Addr)) {
1220     // Null pointer gets folded without affecting the addressing mode.
1221     return true;
1222   }
1223
1224   // Worse case, the target should support [reg] addressing modes. :)
1225   if (!AddrMode.HasBaseReg) {
1226     AddrMode.HasBaseReg = true;
1227     AddrMode.BaseReg = Addr;
1228     // Still check for legality in case the target supports [imm] but not [i+r].
1229     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
1230       return true;
1231     AddrMode.HasBaseReg = false;
1232     AddrMode.BaseReg = 0;
1233   }
1234
1235   // If the base register is already taken, see if we can do [r+r].
1236   if (AddrMode.Scale == 0) {
1237     AddrMode.Scale = 1;
1238     AddrMode.ScaledReg = Addr;
1239     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
1240       return true;
1241     AddrMode.Scale = 0;
1242     AddrMode.ScaledReg = 0;
1243   }
1244   // Couldn't match.
1245   return false;
1246 }
1247
1248 /// IsOperandAMemoryOperand - Check to see if all uses of OpVal by the specified
1249 /// inline asm call are due to memory operands.  If so, return true, otherwise
1250 /// return false.
1251 static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal,
1252                                     const TargetLowering &TLI) {
1253   TargetLowering::AsmOperandInfoVector TargetConstraints = TLI.ParseConstraints(ImmutableCallSite(CI));
1254   for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
1255     TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
1256
1257     // Compute the constraint code and ConstraintType to use.
1258     TLI.ComputeConstraintToUse(OpInfo, SDValue());
1259
1260     // If this asm operand is our Value*, and if it isn't an indirect memory
1261     // operand, we can't fold it!
1262     if (OpInfo.CallOperandVal == OpVal &&
1263         (OpInfo.ConstraintType != TargetLowering::C_Memory ||
1264          !OpInfo.isIndirect))
1265       return false;
1266   }
1267
1268   return true;
1269 }
1270
1271 /// FindAllMemoryUses - Recursively walk all the uses of I until we find a
1272 /// memory use.  If we find an obviously non-foldable instruction, return true.
1273 /// Add the ultimately found memory instructions to MemoryUses.
1274 static bool FindAllMemoryUses(Instruction *I,
1275                 SmallVectorImpl<std::pair<Instruction*,unsigned> > &MemoryUses,
1276                               SmallPtrSet<Instruction*, 16> &ConsideredInsts,
1277                               const TargetLowering &TLI) {
1278   // If we already considered this instruction, we're done.
1279   if (!ConsideredInsts.insert(I))
1280     return false;
1281
1282   // If this is an obviously unfoldable instruction, bail out.
1283   if (!MightBeFoldableInst(I))
1284     return true;
1285
1286   // Loop over all the uses, recursively processing them.
1287   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
1288        UI != E; ++UI) {
1289     User *U = *UI;
1290
1291     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
1292       MemoryUses.push_back(std::make_pair(LI, UI.getOperandNo()));
1293       continue;
1294     }
1295
1296     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1297       unsigned opNo = UI.getOperandNo();
1298       if (opNo == 0) return true; // Storing addr, not into addr.
1299       MemoryUses.push_back(std::make_pair(SI, opNo));
1300       continue;
1301     }
1302
1303     if (CallInst *CI = dyn_cast<CallInst>(U)) {
1304       InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue());
1305       if (!IA) return true;
1306
1307       // If this is a memory operand, we're cool, otherwise bail out.
1308       if (!IsOperandAMemoryOperand(CI, IA, I, TLI))
1309         return true;
1310       continue;
1311     }
1312
1313     if (FindAllMemoryUses(cast<Instruction>(U), MemoryUses, ConsideredInsts,
1314                           TLI))
1315       return true;
1316   }
1317
1318   return false;
1319 }
1320
1321 /// ValueAlreadyLiveAtInst - Retrn true if Val is already known to be live at
1322 /// the use site that we're folding it into.  If so, there is no cost to
1323 /// include it in the addressing mode.  KnownLive1 and KnownLive2 are two values
1324 /// that we know are live at the instruction already.
1325 bool AddressingModeMatcher::ValueAlreadyLiveAtInst(Value *Val,Value *KnownLive1,
1326                                                    Value *KnownLive2) {
1327   // If Val is either of the known-live values, we know it is live!
1328   if (Val == 0 || Val == KnownLive1 || Val == KnownLive2)
1329     return true;
1330
1331   // All values other than instructions and arguments (e.g. constants) are live.
1332   if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true;
1333
1334   // If Val is a constant sized alloca in the entry block, it is live, this is
1335   // true because it is just a reference to the stack/frame pointer, which is
1336   // live for the whole function.
1337   if (AllocaInst *AI = dyn_cast<AllocaInst>(Val))
1338     if (AI->isStaticAlloca())
1339       return true;
1340
1341   // Check to see if this value is already used in the memory instruction's
1342   // block.  If so, it's already live into the block at the very least, so we
1343   // can reasonably fold it.
1344   return Val->isUsedInBasicBlock(MemoryInst->getParent());
1345 }
1346
1347 /// IsProfitableToFoldIntoAddressingMode - It is possible for the addressing
1348 /// mode of the machine to fold the specified instruction into a load or store
1349 /// that ultimately uses it.  However, the specified instruction has multiple
1350 /// uses.  Given this, it may actually increase register pressure to fold it
1351 /// into the load.  For example, consider this code:
1352 ///
1353 ///     X = ...
1354 ///     Y = X+1
1355 ///     use(Y)   -> nonload/store
1356 ///     Z = Y+1
1357 ///     load Z
1358 ///
1359 /// In this case, Y has multiple uses, and can be folded into the load of Z
1360 /// (yielding load [X+2]).  However, doing this will cause both "X" and "X+1" to
1361 /// be live at the use(Y) line.  If we don't fold Y into load Z, we use one
1362 /// fewer register.  Since Y can't be folded into "use(Y)" we don't increase the
1363 /// number of computations either.
1364 ///
1365 /// Note that this (like most of CodeGenPrepare) is just a rough heuristic.  If
1366 /// X was live across 'load Z' for other reasons, we actually *would* want to
1367 /// fold the addressing mode in the Z case.  This would make Y die earlier.
1368 bool AddressingModeMatcher::
1369 IsProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore,
1370                                      ExtAddrMode &AMAfter) {
1371   if (IgnoreProfitability) return true;
1372
1373   // AMBefore is the addressing mode before this instruction was folded into it,
1374   // and AMAfter is the addressing mode after the instruction was folded.  Get
1375   // the set of registers referenced by AMAfter and subtract out those
1376   // referenced by AMBefore: this is the set of values which folding in this
1377   // address extends the lifetime of.
1378   //
1379   // Note that there are only two potential values being referenced here,
1380   // BaseReg and ScaleReg (global addresses are always available, as are any
1381   // folded immediates).
1382   Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg;
1383
1384   // If the BaseReg or ScaledReg was referenced by the previous addrmode, their
1385   // lifetime wasn't extended by adding this instruction.
1386   if (ValueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg))
1387     BaseReg = 0;
1388   if (ValueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg))
1389     ScaledReg = 0;
1390
1391   // If folding this instruction (and it's subexprs) didn't extend any live
1392   // ranges, we're ok with it.
1393   if (BaseReg == 0 && ScaledReg == 0)
1394     return true;
1395
1396   // If all uses of this instruction are ultimately load/store/inlineasm's,
1397   // check to see if their addressing modes will include this instruction.  If
1398   // so, we can fold it into all uses, so it doesn't matter if it has multiple
1399   // uses.
1400   SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses;
1401   SmallPtrSet<Instruction*, 16> ConsideredInsts;
1402   if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI))
1403     return false;  // Has a non-memory, non-foldable use!
1404
1405   // Now that we know that all uses of this instruction are part of a chain of
1406   // computation involving only operations that could theoretically be folded
1407   // into a memory use, loop over each of these uses and see if they could
1408   // *actually* fold the instruction.
1409   SmallVector<Instruction*, 32> MatchedAddrModeInsts;
1410   for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) {
1411     Instruction *User = MemoryUses[i].first;
1412     unsigned OpNo = MemoryUses[i].second;
1413
1414     // Get the access type of this use.  If the use isn't a pointer, we don't
1415     // know what it accesses.
1416     Value *Address = User->getOperand(OpNo);
1417     if (!Address->getType()->isPointerTy())
1418       return false;
1419     Type *AddressAccessTy =
1420       cast<PointerType>(Address->getType())->getElementType();
1421
1422     // Do a match against the root of this address, ignoring profitability. This
1423     // will tell us if the addressing mode for the memory operation will
1424     // *actually* cover the shared instruction.
1425     ExtAddrMode Result;
1426     AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, AddressAccessTy,
1427                                   MemoryInst, Result);
1428     Matcher.IgnoreProfitability = true;
1429     bool Success = Matcher.MatchAddr(Address, 0);
1430     (void)Success; assert(Success && "Couldn't select *anything*?");
1431
1432     // If the match didn't cover I, then it won't be shared by it.
1433     if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(),
1434                   I) == MatchedAddrModeInsts.end())
1435       return false;
1436
1437     MatchedAddrModeInsts.clear();
1438   }
1439
1440   return true;
1441 }
1442
1443 } // end anonymous namespace
1444
1445 /// IsNonLocalValue - Return true if the specified values are defined in a
1446 /// different basic block than BB.
1447 static bool IsNonLocalValue(Value *V, BasicBlock *BB) {
1448   if (Instruction *I = dyn_cast<Instruction>(V))
1449     return I->getParent() != BB;
1450   return false;
1451 }
1452
1453 /// OptimizeMemoryInst - Load and Store Instructions often have
1454 /// addressing modes that can do significant amounts of computation.  As such,
1455 /// instruction selection will try to get the load or store to do as much
1456 /// computation as possible for the program.  The problem is that isel can only
1457 /// see within a single block.  As such, we sink as much legal addressing mode
1458 /// stuff into the block as possible.
1459 ///
1460 /// This method is used to optimize both load/store and inline asms with memory
1461 /// operands.
1462 bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
1463                                         Type *AccessTy) {
1464   Value *Repl = Addr;
1465
1466   // Try to collapse single-value PHI nodes.  This is necessary to undo
1467   // unprofitable PRE transformations.
1468   SmallVector<Value*, 8> worklist;
1469   SmallPtrSet<Value*, 16> Visited;
1470   worklist.push_back(Addr);
1471
1472   // Use a worklist to iteratively look through PHI nodes, and ensure that
1473   // the addressing mode obtained from the non-PHI roots of the graph
1474   // are equivalent.
1475   Value *Consensus = 0;
1476   unsigned NumUsesConsensus = 0;
1477   bool IsNumUsesConsensusValid = false;
1478   SmallVector<Instruction*, 16> AddrModeInsts;
1479   ExtAddrMode AddrMode;
1480   while (!worklist.empty()) {
1481     Value *V = worklist.back();
1482     worklist.pop_back();
1483
1484     // Break use-def graph loops.
1485     if (!Visited.insert(V)) {
1486       Consensus = 0;
1487       break;
1488     }
1489
1490     // For a PHI node, push all of its incoming values.
1491     if (PHINode *P = dyn_cast<PHINode>(V)) {
1492       for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i)
1493         worklist.push_back(P->getIncomingValue(i));
1494       continue;
1495     }
1496
1497     // For non-PHIs, determine the addressing mode being computed.
1498     SmallVector<Instruction*, 16> NewAddrModeInsts;
1499     ExtAddrMode NewAddrMode =
1500       AddressingModeMatcher::Match(V, AccessTy, MemoryInst,
1501                                    NewAddrModeInsts, *TLI);
1502
1503     // This check is broken into two cases with very similar code to avoid using
1504     // getNumUses() as much as possible. Some values have a lot of uses, so
1505     // calling getNumUses() unconditionally caused a significant compile-time
1506     // regression.
1507     if (!Consensus) {
1508       Consensus = V;
1509       AddrMode = NewAddrMode;
1510       AddrModeInsts = NewAddrModeInsts;
1511       continue;
1512     } else if (NewAddrMode == AddrMode) {
1513       if (!IsNumUsesConsensusValid) {
1514         NumUsesConsensus = Consensus->getNumUses();
1515         IsNumUsesConsensusValid = true;
1516       }
1517
1518       // Ensure that the obtained addressing mode is equivalent to that obtained
1519       // for all other roots of the PHI traversal.  Also, when choosing one
1520       // such root as representative, select the one with the most uses in order
1521       // to keep the cost modeling heuristics in AddressingModeMatcher
1522       // applicable.
1523       unsigned NumUses = V->getNumUses();
1524       if (NumUses > NumUsesConsensus) {
1525         Consensus = V;
1526         NumUsesConsensus = NumUses;
1527         AddrModeInsts = NewAddrModeInsts;
1528       }
1529       continue;
1530     }
1531
1532     Consensus = 0;
1533     break;
1534   }
1535
1536   // If the addressing mode couldn't be determined, or if multiple different
1537   // ones were determined, bail out now.
1538   if (!Consensus) return false;
1539
1540   // Check to see if any of the instructions supersumed by this addr mode are
1541   // non-local to I's BB.
1542   bool AnyNonLocal = false;
1543   for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) {
1544     if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) {
1545       AnyNonLocal = true;
1546       break;
1547     }
1548   }
1549
1550   // If all the instructions matched are already in this BB, don't do anything.
1551   if (!AnyNonLocal) {
1552     DEBUG(dbgs() << "CGP: Found      local addrmode: " << AddrMode << "\n");
1553     return false;
1554   }
1555
1556   // Insert this computation right after this user.  Since our caller is
1557   // scanning from the top of the BB to the bottom, reuse of the expr are
1558   // guaranteed to happen later.
1559   IRBuilder<> Builder(MemoryInst);
1560
1561   // Now that we determined the addressing expression we want to use and know
1562   // that we have to sink it into this block.  Check to see if we have already
1563   // done this for some other load/store instr in this block.  If so, reuse the
1564   // computation.
1565   Value *&SunkAddr = SunkAddrs[Addr];
1566   if (SunkAddr) {
1567     DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for "
1568                  << *MemoryInst);
1569     if (SunkAddr->getType() != Addr->getType())
1570       SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType());
1571   } else {
1572     DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
1573                  << *MemoryInst);
1574     Type *IntPtrTy =
1575           TLI->getDataLayout()->getIntPtrType(AccessTy->getContext());
1576
1577     Value *Result = 0;
1578
1579     // Start with the base register. Do this first so that subsequent address
1580     // matching finds it last, which will prevent it from trying to match it
1581     // as the scaled value in case it happens to be a mul. That would be
1582     // problematic if we've sunk a different mul for the scale, because then
1583     // we'd end up sinking both muls.
1584     if (AddrMode.BaseReg) {
1585       Value *V = AddrMode.BaseReg;
1586       if (V->getType()->isPointerTy())
1587         V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
1588       if (V->getType() != IntPtrTy)
1589         V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr");
1590       Result = V;
1591     }
1592
1593     // Add the scale value.
1594     if (AddrMode.Scale) {
1595       Value *V = AddrMode.ScaledReg;
1596       if (V->getType() == IntPtrTy) {
1597         // done.
1598       } else if (V->getType()->isPointerTy()) {
1599         V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
1600       } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() <
1601                  cast<IntegerType>(V->getType())->getBitWidth()) {
1602         V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
1603       } else {
1604         V = Builder.CreateSExt(V, IntPtrTy, "sunkaddr");
1605       }
1606       if (AddrMode.Scale != 1)
1607         V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
1608                               "sunkaddr");
1609       if (Result)
1610         Result = Builder.CreateAdd(Result, V, "sunkaddr");
1611       else
1612         Result = V;
1613     }
1614
1615     // Add in the BaseGV if present.
1616     if (AddrMode.BaseGV) {
1617       Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr");
1618       if (Result)
1619         Result = Builder.CreateAdd(Result, V, "sunkaddr");
1620       else
1621         Result = V;
1622     }
1623
1624     // Add in the Base Offset if present.
1625     if (AddrMode.BaseOffs) {
1626       Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs);
1627       if (Result)
1628         Result = Builder.CreateAdd(Result, V, "sunkaddr");
1629       else
1630         Result = V;
1631     }
1632
1633     if (Result == 0)
1634       SunkAddr = Constant::getNullValue(Addr->getType());
1635     else
1636       SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr");
1637   }
1638
1639   MemoryInst->replaceUsesOfWith(Repl, SunkAddr);
1640
1641   // If we have no uses, recursively delete the value and all dead instructions
1642   // using it.
1643   if (Repl->use_empty()) {
1644     // This can cause recursive deletion, which can invalidate our iterator.
1645     // Use a WeakVH to hold onto it in case this happens.
1646     WeakVH IterHandle(CurInstIterator);
1647     BasicBlock *BB = CurInstIterator->getParent();
1648
1649     RecursivelyDeleteTriviallyDeadInstructions(Repl, TLInfo);
1650
1651     if (IterHandle != CurInstIterator) {
1652       // If the iterator instruction was recursively deleted, start over at the
1653       // start of the block.
1654       CurInstIterator = BB->begin();
1655       SunkAddrs.clear();
1656     } else {
1657       // This address is now available for reassignment, so erase the table
1658       // entry; we don't want to match some completely different instruction.
1659       SunkAddrs[Addr] = 0;
1660     }
1661   }
1662   ++NumMemoryInsts;
1663   return true;
1664 }
1665
1666 /// OptimizeInlineAsmInst - If there are any memory operands, use
1667 /// OptimizeMemoryInst to sink their address computing into the block when
1668 /// possible / profitable.
1669 bool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) {
1670   bool MadeChange = false;
1671
1672   TargetLowering::AsmOperandInfoVector
1673     TargetConstraints = TLI->ParseConstraints(CS);
1674   unsigned ArgNo = 0;
1675   for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
1676     TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
1677
1678     // Compute the constraint code and ConstraintType to use.
1679     TLI->ComputeConstraintToUse(OpInfo, SDValue());
1680
1681     if (OpInfo.ConstraintType == TargetLowering::C_Memory &&
1682         OpInfo.isIndirect) {
1683       Value *OpVal = CS->getArgOperand(ArgNo++);
1684       MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType());
1685     } else if (OpInfo.Type == InlineAsm::isInput)
1686       ArgNo++;
1687   }
1688
1689   return MadeChange;
1690 }
1691
1692 /// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same
1693 /// basic block as the load, unless conditions are unfavorable. This allows
1694 /// SelectionDAG to fold the extend into the load.
1695 ///
1696 bool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) {
1697   // Look for a load being extended.
1698   LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0));
1699   if (!LI) return false;
1700
1701   // If they're already in the same block, there's nothing to do.
1702   if (LI->getParent() == I->getParent())
1703     return false;
1704
1705   // If the load has other users and the truncate is not free, this probably
1706   // isn't worthwhile.
1707   if (!LI->hasOneUse() &&
1708       TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) ||
1709               !TLI->isTypeLegal(TLI->getValueType(I->getType()))) &&
1710       !TLI->isTruncateFree(I->getType(), LI->getType()))
1711     return false;
1712
1713   // Check whether the target supports casts folded into loads.
1714   unsigned LType;
1715   if (isa<ZExtInst>(I))
1716     LType = ISD::ZEXTLOAD;
1717   else {
1718     assert(isa<SExtInst>(I) && "Unexpected ext type!");
1719     LType = ISD::SEXTLOAD;
1720   }
1721   if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType())))
1722     return false;
1723
1724   // Move the extend into the same block as the load, so that SelectionDAG
1725   // can fold it.
1726   I->removeFromParent();
1727   I->insertAfter(LI);
1728   ++NumExtsMoved;
1729   return true;
1730 }
1731
1732 bool CodeGenPrepare::OptimizeExtUses(Instruction *I) {
1733   BasicBlock *DefBB = I->getParent();
1734
1735   // If the result of a {s|z}ext and its source are both live out, rewrite all
1736   // other uses of the source with result of extension.
1737   Value *Src = I->getOperand(0);
1738   if (Src->hasOneUse())
1739     return false;
1740
1741   // Only do this xform if truncating is free.
1742   if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType()))
1743     return false;
1744
1745   // Only safe to perform the optimization if the source is also defined in
1746   // this block.
1747   if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent())
1748     return false;
1749
1750   bool DefIsLiveOut = false;
1751   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
1752        UI != E; ++UI) {
1753     Instruction *User = cast<Instruction>(*UI);
1754
1755     // Figure out which BB this ext is used in.
1756     BasicBlock *UserBB = User->getParent();
1757     if (UserBB == DefBB) continue;
1758     DefIsLiveOut = true;
1759     break;
1760   }
1761   if (!DefIsLiveOut)
1762     return false;
1763
1764   // Make sure non of the uses are PHI nodes.
1765   for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end();
1766        UI != E; ++UI) {
1767     Instruction *User = cast<Instruction>(*UI);
1768     BasicBlock *UserBB = User->getParent();
1769     if (UserBB == DefBB) continue;
1770     // Be conservative. We don't want this xform to end up introducing
1771     // reloads just before load / store instructions.
1772     if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User))
1773       return false;
1774   }
1775
1776   // InsertedTruncs - Only insert one trunc in each block once.
1777   DenseMap<BasicBlock*, Instruction*> InsertedTruncs;
1778
1779   bool MadeChange = false;
1780   for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end();
1781        UI != E; ++UI) {
1782     Use &TheUse = UI.getUse();
1783     Instruction *User = cast<Instruction>(*UI);
1784
1785     // Figure out which BB this ext is used in.
1786     BasicBlock *UserBB = User->getParent();
1787     if (UserBB == DefBB) continue;
1788
1789     // Both src and def are live in this block. Rewrite the use.
1790     Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
1791
1792     if (!InsertedTrunc) {
1793       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1794       InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt);
1795     }
1796
1797     // Replace a use of the {s|z}ext source with a use of the result.
1798     TheUse = InsertedTrunc;
1799     ++NumExtUses;
1800     MadeChange = true;
1801   }
1802
1803   return MadeChange;
1804 }
1805
1806 /// isFormingBranchFromSelectProfitable - Returns true if a SelectInst should be
1807 /// turned into an explicit branch.
1808 static bool isFormingBranchFromSelectProfitable(SelectInst *SI) {
1809   // FIXME: This should use the same heuristics as IfConversion to determine
1810   // whether a select is better represented as a branch.  This requires that
1811   // branch probability metadata is preserved for the select, which is not the
1812   // case currently.
1813
1814   CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
1815
1816   // If the branch is predicted right, an out of order CPU can avoid blocking on
1817   // the compare.  Emit cmovs on compares with a memory operand as branches to
1818   // avoid stalls on the load from memory.  If the compare has more than one use
1819   // there's probably another cmov or setcc around so it's not worth emitting a
1820   // branch.
1821   if (!Cmp)
1822     return false;
1823
1824   Value *CmpOp0 = Cmp->getOperand(0);
1825   Value *CmpOp1 = Cmp->getOperand(1);
1826
1827   // We check that the memory operand has one use to avoid uses of the loaded
1828   // value directly after the compare, making branches unprofitable.
1829   return Cmp->hasOneUse() &&
1830          ((isa<LoadInst>(CmpOp0) && CmpOp0->hasOneUse()) ||
1831           (isa<LoadInst>(CmpOp1) && CmpOp1->hasOneUse()));
1832 }
1833
1834
1835 /// If we have a SelectInst that will likely profit from branch prediction,
1836 /// turn it into a branch.
1837 bool CodeGenPrepare::OptimizeSelectInst(SelectInst *SI) {
1838   bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
1839
1840   // Can we convert the 'select' to CF ?
1841   if (DisableSelectToBranch || OptSize || !TLI || VectorCond)
1842     return false;
1843
1844   TargetLowering::SelectSupportKind SelectKind;
1845   if (VectorCond)
1846     SelectKind = TargetLowering::VectorMaskSelect;
1847   else if (SI->getType()->isVectorTy())
1848     SelectKind = TargetLowering::ScalarCondVectorVal;
1849   else
1850     SelectKind = TargetLowering::ScalarValSelect;
1851
1852   // Do we have efficient codegen support for this kind of 'selects' ?
1853   if (TLI->isSelectSupported(SelectKind)) {
1854     // We have efficient codegen support for the select instruction.
1855     // Check if it is profitable to keep this 'select'.
1856     if (!TLI->isPredictableSelectExpensive() ||
1857         !isFormingBranchFromSelectProfitable(SI))
1858       return false;
1859   }
1860
1861   ModifiedDT = true;
1862
1863   // First, we split the block containing the select into 2 blocks.
1864   BasicBlock *StartBlock = SI->getParent();
1865   BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(SI));
1866   BasicBlock *NextBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");
1867
1868   // Create a new block serving as the landing pad for the branch.
1869   BasicBlock *SmallBlock = BasicBlock::Create(SI->getContext(), "select.mid",
1870                                              NextBlock->getParent(), NextBlock);
1871
1872   // Move the unconditional branch from the block with the select in it into our
1873   // landing pad block.
1874   StartBlock->getTerminator()->eraseFromParent();
1875   BranchInst::Create(NextBlock, SmallBlock);
1876
1877   // Insert the real conditional branch based on the original condition.
1878   BranchInst::Create(NextBlock, SmallBlock, SI->getCondition(), SI);
1879
1880   // The select itself is replaced with a PHI Node.
1881   PHINode *PN = PHINode::Create(SI->getType(), 2, "", NextBlock->begin());
1882   PN->takeName(SI);
1883   PN->addIncoming(SI->getTrueValue(), StartBlock);
1884   PN->addIncoming(SI->getFalseValue(), SmallBlock);
1885   SI->replaceAllUsesWith(PN);
1886   SI->eraseFromParent();
1887
1888   // Instruct OptimizeBlock to skip to the next block.
1889   CurInstIterator = StartBlock->end();
1890   ++NumSelectsExpanded;
1891   return true;
1892 }
1893
1894 bool CodeGenPrepare::OptimizeInst(Instruction *I) {
1895   if (PHINode *P = dyn_cast<PHINode>(I)) {
1896     // It is possible for very late stage optimizations (such as SimplifyCFG)
1897     // to introduce PHI nodes too late to be cleaned up.  If we detect such a
1898     // trivial PHI, go ahead and zap it here.
1899     if (Value *V = SimplifyInstruction(P)) {
1900       P->replaceAllUsesWith(V);
1901       P->eraseFromParent();
1902       ++NumPHIsElim;
1903       return true;
1904     }
1905     return false;
1906   }
1907
1908   if (CastInst *CI = dyn_cast<CastInst>(I)) {
1909     // If the source of the cast is a constant, then this should have
1910     // already been constant folded.  The only reason NOT to constant fold
1911     // it is if something (e.g. LSR) was careful to place the constant
1912     // evaluation in a block other than then one that uses it (e.g. to hoist
1913     // the address of globals out of a loop).  If this is the case, we don't
1914     // want to forward-subst the cast.
1915     if (isa<Constant>(CI->getOperand(0)))
1916       return false;
1917
1918     if (TLI && OptimizeNoopCopyExpression(CI, *TLI))
1919       return true;
1920
1921     if (isa<ZExtInst>(I) || isa<SExtInst>(I)) {
1922       bool MadeChange = MoveExtToFormExtLoad(I);
1923       return MadeChange | OptimizeExtUses(I);
1924     }
1925     return false;
1926   }
1927
1928   if (CmpInst *CI = dyn_cast<CmpInst>(I))
1929     return OptimizeCmpExpression(CI);
1930
1931   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
1932     if (TLI)
1933       return OptimizeMemoryInst(I, I->getOperand(0), LI->getType());
1934     return false;
1935   }
1936
1937   if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
1938     if (TLI)
1939       return OptimizeMemoryInst(I, SI->getOperand(1),
1940                                 SI->getOperand(0)->getType());
1941     return false;
1942   }
1943
1944   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
1945     if (GEPI->hasAllZeroIndices()) {
1946       /// The GEP operand must be a pointer, so must its result -> BitCast
1947       Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
1948                                         GEPI->getName(), GEPI);
1949       GEPI->replaceAllUsesWith(NC);
1950       GEPI->eraseFromParent();
1951       ++NumGEPsElim;
1952       OptimizeInst(NC);
1953       return true;
1954     }
1955     return false;
1956   }
1957
1958   if (CallInst *CI = dyn_cast<CallInst>(I))
1959     return OptimizeCallInst(CI);
1960
1961   if (SelectInst *SI = dyn_cast<SelectInst>(I))
1962     return OptimizeSelectInst(SI);
1963
1964   return false;
1965 }
1966
1967 // In this pass we look for GEP and cast instructions that are used
1968 // across basic blocks and rewrite them to improve basic-block-at-a-time
1969 // selection.
1970 bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) {
1971   SunkAddrs.clear();
1972   bool MadeChange = false;
1973
1974   CurInstIterator = BB.begin();
1975   while (CurInstIterator != BB.end())
1976     MadeChange |= OptimizeInst(CurInstIterator++);
1977
1978   MadeChange |= DupRetToEnableTailCallOpts(&BB);
1979
1980   return MadeChange;
1981 }
1982
1983 // llvm.dbg.value is far away from the value then iSel may not be able
1984 // handle it properly. iSel will drop llvm.dbg.value if it can not
1985 // find a node corresponding to the value.
1986 bool CodeGenPrepare::PlaceDbgValues(Function &F) {
1987   bool MadeChange = false;
1988   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
1989     Instruction *PrevNonDbgInst = NULL;
1990     for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE;) {
1991       Instruction *Insn = BI; ++BI;
1992       DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn);
1993       if (!DVI) {
1994         PrevNonDbgInst = Insn;
1995         continue;
1996       }
1997
1998       Instruction *VI = dyn_cast_or_null<Instruction>(DVI->getValue());
1999       if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) {
2000         DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI);
2001         DVI->removeFromParent();
2002         if (isa<PHINode>(VI))
2003           DVI->insertBefore(VI->getParent()->getFirstInsertionPt());
2004         else
2005           DVI->insertAfter(VI);
2006         MadeChange = true;
2007         ++NumDbgValueMoved;
2008       }
2009     }
2010   }
2011   return MadeChange;
2012 }