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/Constants.h"
  27 #include "llvm/DataLayout.h"
  28 #include "llvm/DerivedTypes.h"
  29 #include "llvm/Function.h"
  30 #include "llvm/IRBuilder.h"
  31 #include "llvm/InlineAsm.h"
  32 #include "llvm/Instructions.h"
  33 #include "llvm/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/AddrModeMatcher.h"
  45 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  46 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  47 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
  48 #include "llvm/Transforms/Utils/Local.h"
  49 using namespace llvm;
  50 using namespace llvm::PatternMatch;
  51
  52 STATISTIC(NumBlocksElim, "Number of blocks eliminated");
  53 STATISTIC(NumPHIsElim,   "Number of trivial PHIs eliminated");
  54 STATISTIC(NumGEPsElim,   "Number of GEPs converted to casts");
  55 STATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of "
  56                       "sunken Cmps");
  57 STATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses "
  58                        "of sunken Casts");
  59 STATISTIC(NumMemoryInsts, "Number of memory instructions whose address "
  60                           "computations were sunk");
  61 STATISTIC(NumExtsMoved,  "Number of [s|z]ext instructions combined with loads");
  62 STATISTIC(NumExtUses,    "Number of uses of [s|z]ext instructions optimized");
  63 STATISTIC(NumRetsDup,    "Number of return instructions duplicated");
  64 STATISTIC(NumDbgValueMoved, "Number of debug value instructions moved");
  65 STATISTIC(NumSelectsExpanded, "Number of selects turned into branches");
  66
  67 static cl::opt<bool> DisableBranchOpts(
  68   "disable-cgp-branch-opts", cl::Hidden, cl::init(false),
  69   cl::desc("Disable branch optimizations in CodeGenPrepare"));
  70
  71 static cl::opt<bool> DisableSelectToBranch(
  72   "disable-cgp-select2branch", cl::Hidden, cl::init(false),
  73   cl::desc("Disable select to branch conversion."));
  74
  75 namespace {
  76   class CodeGenPrepare : public FunctionPass {
  77     /// TLI - Keep a pointer of a TargetLowering to consult for determining
  78     /// transformation profitability.
  79     const TargetLowering *TLI;
  80     const TargetLibraryInfo *TLInfo;
  81     DominatorTree *DT;
  82     ProfileInfo *PFI;
  83
  84     /// CurInstIterator - As we scan instructions optimizing them, this is the
  85     /// next instruction to optimize.  Xforms that can invalidate this should
  86     /// update it.
  87     BasicBlock::iterator CurInstIterator;
  88
  89     /// Keeps track of non-local addresses that have been sunk into a block.
  90     /// This allows us to avoid inserting duplicate code for blocks with
  91     /// multiple load/stores of the same address.
  92     DenseMap<Value*, Value*> SunkAddrs;
  93
  94     /// ModifiedDT - If CFG is modified in anyway, dominator tree may need to
  95     /// be updated.
  96     bool ModifiedDT;
  97
  98     /// OptSize - True if optimizing for size.
  99     bool OptSize;
 100
 101   public:
 102     static char ID; // Pass identification, replacement for typeid
 103     explicit CodeGenPrepare(const TargetLowering *tli = 0)
 104       : FunctionPass(ID), TLI(tli) {
 105         initializeCodeGenPreparePass(*PassRegistry::getPassRegistry());
 106       }
 107     bool runOnFunction(Function &F);
 108
 109     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 110       AU.addPreserved<DominatorTree>();
 111       AU.addPreserved<ProfileInfo>();
 112       AU.addRequired<TargetLibraryInfo>();
 113     }
 114
 115   private:
 116     bool EliminateFallThrough(Function &F);
 117     bool EliminateMostlyEmptyBlocks(Function &F);
 118     bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
 119     void EliminateMostlyEmptyBlock(BasicBlock *BB);
 120     bool OptimizeBlock(BasicBlock &BB);
 121     bool OptimizeInst(Instruction *I);
 122     bool OptimizeMemoryInst(Instruction *I, Value *Addr, Type *AccessTy);
 123     bool OptimizeInlineAsmInst(CallInst *CS);
 124     bool OptimizeCallInst(CallInst *CI);
 125     bool MoveExtToFormExtLoad(Instruction *I);
 126     bool OptimizeExtUses(Instruction *I);
 127     bool OptimizeSelectInst(SelectInst *SI);
 128     bool DupRetToEnableTailCallOpts(BasicBlock *BB);
 129     bool PlaceDbgValues(Function &F);
 130   };
 131 }
 132
 133 char CodeGenPrepare::ID = 0;
 134 INITIALIZE_PASS_BEGIN(CodeGenPrepare, "codegenprepare",
 135                 "Optimize for code generation", false, false)
 136 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 137 INITIALIZE_PASS_END(CodeGenPrepare, "codegenprepare",
 138                 "Optimize for code generation", false, false)
 139
 140 FunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) {
 141   return new CodeGenPrepare(TLI);
 142 }
 143
 144 bool CodeGenPrepare::runOnFunction(Function &F) {
 145   bool EverMadeChange = false;
 146
 147   ModifiedDT = false;
 148   TLInfo = &getAnalysis<TargetLibraryInfo>();
 149   DT = getAnalysisIfAvailable<DominatorTree>();
 150   PFI = getAnalysisIfAvailable<ProfileInfo>();
 151   OptSize = F.getFnAttributes().hasAttribute(Attributes::OptimizeForSize);
 152
 153   /// This optimization identifies DIV instructions that can be
 154   /// profitably bypassed and carried out with a shorter, faster divide.
 155   if (TLI && TLI->isSlowDivBypassed()) {
 156     const DenseMap<unsigned int, unsigned int> &BypassWidths =
 157        TLI->getBypassSlowDivWidths();
 158     for (Function::iterator I = F.begin(); I != F.end(); I++)
 159       EverMadeChange |= bypassSlowDivision(F, I, BypassWidths);
 160   }
 161
 162   // Eliminate blocks that contain only PHI nodes and an
 163   // unconditional branch.
 164   EverMadeChange |= EliminateMostlyEmptyBlocks(F);
 165
 166   // llvm.dbg.value is far away from the value then iSel may not be able
 167   // handle it properly. iSel will drop llvm.dbg.value if it can not
 168   // find a node corresponding to the value.
 169   EverMadeChange |= PlaceDbgValues(F);
 170
 171   bool MadeChange = true;
 172   while (MadeChange) {
 173     MadeChange = false;
 174     for (Function::iterator I = F.begin(); I != F.end(); ) {
 175       BasicBlock *BB = I++;
 176       MadeChange |= OptimizeBlock(*BB);
 177     }
 178     EverMadeChange |= MadeChange;
 179   }
 180
 181   SunkAddrs.clear();
 182
 183   if (!DisableBranchOpts) {
 184     MadeChange = false;
 185     SmallPtrSet<BasicBlock*, 8> WorkList;
 186     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
 187       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
 188       MadeChange |= ConstantFoldTerminator(BB, true);
 189       if (!MadeChange) continue;
 190
 191       for (SmallVectorImpl<BasicBlock*>::iterator
 192              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
 193         if (pred_begin(*II) == pred_end(*II))
 194           WorkList.insert(*II);
 195     }
 196
 197     // Delete the dead blocks and any of their dead successors.
 198     while (!WorkList.empty()) {
 199       BasicBlock *BB = *WorkList.begin();
 200       WorkList.erase(BB);
 201       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
 202
 203       DeleteDeadBlock(BB);
 204
 205       for (SmallVectorImpl<BasicBlock*>::iterator
 206              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
 207         if (pred_begin(*II) == pred_end(*II))
 208           WorkList.insert(*II);
 209     }
 210
 211     // Merge pairs of basic blocks with unconditional branches, connected by
 212     // a single edge.
 213     if (EverMadeChange || MadeChange)
 214       MadeChange |= EliminateFallThrough(F);
 215
 216     if (MadeChange)
 217       ModifiedDT = true;
 218     EverMadeChange |= MadeChange;
 219   }
 220
 221   if (ModifiedDT && DT)
 222     DT->DT->recalculate(F);
 223
 224   return EverMadeChange;
 225 }
 226
 227 /// EliminateFallThrough - Merge basic blocks which are connected
 228 /// by a single edge, where one of the basic blocks has a single successor
 229 /// pointing to the other basic block, which has a single predecessor.
 230 bool CodeGenPrepare::EliminateFallThrough(Function &F) {
 231   bool Changed = false;
 232   // Scan all of the blocks in the function, except for the entry block.
 233   for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) {
 234     BasicBlock *BB = I++;
 235     // If the destination block has a single pred, then this is a trivial
 236     // edge, just collapse it.
 237     BasicBlock *SinglePred = BB->getSinglePredecessor();
 238
 239     // Don't merge if BB's address is taken.
 240     if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
 241
 242     BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
 243     if (Term && !Term->isConditional()) {
 244       Changed = true;
 245       DEBUG(dbgs() << "To merge:\n"<< *SinglePred << "\n\n\n");
 246       // Remember if SinglePred was the entry block of the function.
 247       // If so, we will need to move BB back to the entry position.
 248       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
 249       MergeBasicBlockIntoOnlyPred(BB, this);
 250
 251       if (isEntry && BB != &BB->getParent()->getEntryBlock())
 252         BB->moveBefore(&BB->getParent()->getEntryBlock());
 253
 254       // We have erased a block. Update the iterator.
 255       I = BB;
 256     }
 257   }
 258   return Changed;
 259 }
 260
 261 /// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes,
 262 /// debug info directives, and an unconditional branch.  Passes before isel
 263 /// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for
 264 /// isel.  Start by eliminating these blocks so we can split them the way we
 265 /// want them.
 266 bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) {
 267   bool MadeChange = false;
 268   // Note that this intentionally skips the entry block.
 269   for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) {
 270     BasicBlock *BB = I++;
 271
 272     // If this block doesn't end with an uncond branch, ignore it.
 273     BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
 274     if (!BI || !BI->isUnconditional())
 275       continue;
 276
 277     // If the instruction before the branch (skipping debug info) isn't a phi
 278     // node, then other stuff is happening here.
 279     BasicBlock::iterator BBI = BI;
 280     if (BBI != BB->begin()) {
 281       --BBI;
 282       while (isa<DbgInfoIntrinsic>(BBI)) {
 283         if (BBI == BB->begin())
 284           break;
 285         --BBI;
 286       }
 287       if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
 288         continue;
 289     }
 290
 291     // Do not break infinite loops.
 292     BasicBlock *DestBB = BI->getSuccessor(0);
 293     if (DestBB == BB)
 294       continue;
 295
 296     if (!CanMergeBlocks(BB, DestBB))
 297       continue;
 298
 299     EliminateMostlyEmptyBlock(BB);
 300     MadeChange = true;
 301   }
 302   return MadeChange;
 303 }
 304
 305 /// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a
 306 /// single uncond branch between them, and BB contains no other non-phi
 307 /// instructions.
 308 bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB,
 309                                     const BasicBlock *DestBB) const {
 310   // We only want to eliminate blocks whose phi nodes are used by phi nodes in
 311   // the successor.  If there are more complex condition (e.g. preheaders),
 312   // don't mess around with them.
 313   BasicBlock::const_iterator BBI = BB->begin();
 314   while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
 315     for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end();
 316          UI != E; ++UI) {
 317       const Instruction *User = cast<Instruction>(*UI);
 318       if (User->getParent() != DestBB || !isa<PHINode>(User))
 319         return false;
 320       // If User is inside DestBB block and it is a PHINode then check
 321       // incoming value. If incoming value is not from BB then this is
 322       // a complex condition (e.g. preheaders) we want to avoid here.
 323       if (User->getParent() == DestBB) {
 324         if (const PHINode *UPN = dyn_cast<PHINode>(User))
 325           for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) {
 326             Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I));
 327             if (Insn && Insn->getParent() == BB &&
 328                 Insn->getParent() != UPN->getIncomingBlock(I))
 329               return false;
 330           }
 331       }
 332     }
 333   }
 334
 335   // If BB and DestBB contain any common predecessors, then the phi nodes in BB
 336   // and DestBB may have conflicting incoming values for the block.  If so, we
 337   // can't merge the block.
 338   const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin());
 339   if (!DestBBPN) return true;  // no conflict.
 340
 341   // Collect the preds of BB.
 342   SmallPtrSet<const BasicBlock*, 16> BBPreds;
 343   if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
 344     // It is faster to get preds from a PHI than with pred_iterator.
 345     for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
 346       BBPreds.insert(BBPN->getIncomingBlock(i));
 347   } else {
 348     BBPreds.insert(pred_begin(BB), pred_end(BB));
 349   }
 350
 351   // Walk the preds of DestBB.
 352   for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) {
 353     BasicBlock *Pred = DestBBPN->getIncomingBlock(i);
 354     if (BBPreds.count(Pred)) {   // Common predecessor?
 355       BBI = DestBB->begin();
 356       while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
 357         const Value *V1 = PN->getIncomingValueForBlock(Pred);
 358         const Value *V2 = PN->getIncomingValueForBlock(BB);
 359
 360         // If V2 is a phi node in BB, look up what the mapped value will be.
 361         if (const PHINode *V2PN = dyn_cast<PHINode>(V2))
 362           if (V2PN->getParent() == BB)
 363             V2 = V2PN->getIncomingValueForBlock(Pred);
 364
 365         // If there is a conflict, bail out.
 366         if (V1 != V2) return false;
 367       }
 368     }
 369   }
 370
 371   return true;
 372 }
 373
 374
 375 /// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and
 376 /// an unconditional branch in it.
 377 void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) {
 378   BranchInst *BI = cast<BranchInst>(BB->getTerminator());
 379   BasicBlock *DestBB = BI->getSuccessor(0);
 380
 381   DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB);
 382
 383   // If the destination block has a single pred, then this is a trivial edge,
 384   // just collapse it.
 385   if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
 386     if (SinglePred != DestBB) {
 387       // Remember if SinglePred was the entry block of the function.  If so, we
 388       // will need to move BB back to the entry position.
 389       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
 390       MergeBasicBlockIntoOnlyPred(DestBB, this);
 391
 392       if (isEntry && BB != &BB->getParent()->getEntryBlock())
 393         BB->moveBefore(&BB->getParent()->getEntryBlock());
 394
 395       DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
 396       return;
 397     }
 398   }
 399
 400   // Otherwise, we have multiple predecessors of BB.  Update the PHIs in DestBB
 401   // to handle the new incoming edges it is about to have.
 402   PHINode *PN;
 403   for (BasicBlock::iterator BBI = DestBB->begin();
 404        (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
 405     // Remove the incoming value for BB, and remember it.
 406     Value *InVal = PN->removeIncomingValue(BB, false);
 407
 408     // Two options: either the InVal is a phi node defined in BB or it is some
 409     // value that dominates BB.
 410     PHINode *InValPhi = dyn_cast<PHINode>(InVal);
 411     if (InValPhi && InValPhi->getParent() == BB) {
 412       // Add all of the input values of the input PHI as inputs of this phi.
 413       for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i)
 414         PN->addIncoming(InValPhi->getIncomingValue(i),
 415                         InValPhi->getIncomingBlock(i));
 416     } else {
 417       // Otherwise, add one instance of the dominating value for each edge that
 418       // we will be adding.
 419       if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
 420         for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
 421           PN->addIncoming(InVal, BBPN->getIncomingBlock(i));
 422       } else {
 423         for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
 424           PN->addIncoming(InVal, *PI);
 425       }
 426     }
 427   }
 428
 429   // The PHIs are now updated, change everything that refers to BB to use
 430   // DestBB and remove BB.
 431   BB->replaceAllUsesWith(DestBB);
 432   if (DT && !ModifiedDT) {
 433     BasicBlock *BBIDom  = DT->getNode(BB)->getIDom()->getBlock();
 434     BasicBlock *DestBBIDom = DT->getNode(DestBB)->getIDom()->getBlock();
 435     BasicBlock *NewIDom = DT->findNearestCommonDominator(BBIDom, DestBBIDom);
 436     DT->changeImmediateDominator(DestBB, NewIDom);
 437     DT->eraseNode(BB);
 438   }
 439   if (PFI) {
 440     PFI->replaceAllUses(BB, DestBB);
 441     PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB));
 442   }
 443   BB->eraseFromParent();
 444   ++NumBlocksElim;
 445
 446   DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
 447 }
 448
 449 /// OptimizeNoopCopyExpression - If the specified cast instruction is a noop
 450 /// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC),
 451 /// sink it into user blocks to reduce the number of virtual
 452 /// registers that must be created and coalesced.
 453 ///
 454 /// Return true if any changes are made.
 455 ///
 456 static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){
 457   // If this is a noop copy,
 458   EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType());
 459   EVT DstVT = TLI.getValueType(CI->getType());
 460
 461   // This is an fp<->int conversion?
 462   if (SrcVT.isInteger() != DstVT.isInteger())
 463     return false;
 464
 465   // If this is an extension, it will be a zero or sign extension, which
 466   // isn't a noop.
 467   if (SrcVT.bitsLT(DstVT)) return false;
 468
 469   // If these values will be promoted, find out what they will be promoted
 470   // to.  This helps us consider truncates on PPC as noop copies when they
 471   // are.
 472   if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
 473       TargetLowering::TypePromoteInteger)
 474     SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
 475   if (TLI.getTypeAction(CI->getContext(), DstVT) ==
 476       TargetLowering::TypePromoteInteger)
 477     DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
 478
 479   // If, after promotion, these are the same types, this is a noop copy.
 480   if (SrcVT != DstVT)
 481     return false;
 482
 483   BasicBlock *DefBB = CI->getParent();
 484
 485   /// InsertedCasts - Only insert a cast in each block once.
 486   DenseMap<BasicBlock*, CastInst*> InsertedCasts;
 487
 488   bool MadeChange = false;
 489   for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
 490        UI != E; ) {
 491     Use &TheUse = UI.getUse();
 492     Instruction *User = cast<Instruction>(*UI);
 493
 494     // Figure out which BB this cast is used in.  For PHI's this is the
 495     // appropriate predecessor block.
 496     BasicBlock *UserBB = User->getParent();
 497     if (PHINode *PN = dyn_cast<PHINode>(User)) {
 498       UserBB = PN->getIncomingBlock(UI);
 499     }
 500
 501     // Preincrement use iterator so we don't invalidate it.
 502     ++UI;
 503
 504     // If this user is in the same block as the cast, don't change the cast.
 505     if (UserBB == DefBB) continue;
 506
 507     // If we have already inserted a cast into this block, use it.
 508     CastInst *&InsertedCast = InsertedCasts[UserBB];
 509
 510     if (!InsertedCast) {
 511       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
 512       InsertedCast =
 513         CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "",
 514                          InsertPt);
 515       MadeChange = true;
 516     }
 517
 518     // Replace a use of the cast with a use of the new cast.
 519     TheUse = InsertedCast;
 520     ++NumCastUses;
 521   }
 522
 523   // If we removed all uses, nuke the cast.
 524   if (CI->use_empty()) {
 525     CI->eraseFromParent();
 526     MadeChange = true;
 527   }
 528
 529   return MadeChange;
 530 }
 531
 532 /// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce
 533 /// the number of virtual registers that must be created and coalesced.  This is
 534 /// a clear win except on targets with multiple condition code registers
 535 ///  (PowerPC), where it might lose; some adjustment may be wanted there.
 536 ///
 537 /// Return true if any changes are made.
 538 static bool OptimizeCmpExpression(CmpInst *CI) {
 539   BasicBlock *DefBB = CI->getParent();
 540
 541   /// InsertedCmp - Only insert a cmp in each block once.
 542   DenseMap<BasicBlock*, CmpInst*> InsertedCmps;
 543
 544   bool MadeChange = false;
 545   for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
 546        UI != E; ) {
 547     Use &TheUse = UI.getUse();
 548     Instruction *User = cast<Instruction>(*UI);
 549
 550     // Preincrement use iterator so we don't invalidate it.
 551     ++UI;
 552
 553     // Don't bother for PHI nodes.
 554     if (isa<PHINode>(User))
 555       continue;
 556
 557     // Figure out which BB this cmp is used in.
 558     BasicBlock *UserBB = User->getParent();
 559
 560     // If this user is in the same block as the cmp, don't change the cmp.
 561     if (UserBB == DefBB) continue;
 562
 563     // If we have already inserted a cmp into this block, use it.
 564     CmpInst *&InsertedCmp = InsertedCmps[UserBB];
 565
 566     if (!InsertedCmp) {
 567       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
 568       InsertedCmp =
 569         CmpInst::Create(CI->getOpcode(),
 570                         CI->getPredicate(),  CI->getOperand(0),
 571                         CI->getOperand(1), "", InsertPt);
 572       MadeChange = true;
 573     }
 574
 575     // Replace a use of the cmp with a use of the new cmp.
 576     TheUse = InsertedCmp;
 577     ++NumCmpUses;
 578   }
 579
 580   // If we removed all uses, nuke the cmp.
 581   if (CI->use_empty())
 582     CI->eraseFromParent();
 583
 584   return MadeChange;
 585 }
 586
 587 namespace {
 588 class CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls {
 589 protected:
 590   void replaceCall(Value *With) {
 591     CI->replaceAllUsesWith(With);
 592     CI->eraseFromParent();
 593   }
 594   bool isFoldable(unsigned SizeCIOp, unsigned, bool) const {
 595       if (ConstantInt *SizeCI =
 596                              dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp)))
 597         return SizeCI->isAllOnesValue();
 598     return false;
 599   }
 600 };
 601 } // end anonymous namespace
 602
 603 bool CodeGenPrepare::OptimizeCallInst(CallInst *CI) {
 604   BasicBlock *BB = CI->getParent();
 605
 606   // Lower inline assembly if we can.
 607   // If we found an inline asm expession, and if the target knows how to
 608   // lower it to normal LLVM code, do so now.
 609   if (TLI && isa<InlineAsm>(CI->getCalledValue())) {
 610     if (TLI->ExpandInlineAsm(CI)) {
 611       // Avoid invalidating the iterator.
 612       CurInstIterator = BB->begin();
 613       // Avoid processing instructions out of order, which could cause
 614       // reuse before a value is defined.
 615       SunkAddrs.clear();
 616       return true;
 617     }
 618     // Sink address computing for memory operands into the block.
 619     if (OptimizeInlineAsmInst(CI))
 620       return true;
 621   }
 622
 623   // Lower all uses of llvm.objectsize.*
 624   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
 625   if (II && II->getIntrinsicID() == Intrinsic::objectsize) {
 626     bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1);
 627     Type *ReturnTy = CI->getType();
 628     Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL);
 629
 630     // Substituting this can cause recursive simplifications, which can
 631     // invalidate our iterator.  Use a WeakVH to hold onto it in case this
 632     // happens.
 633     WeakVH IterHandle(CurInstIterator);
 634
 635     replaceAndRecursivelySimplify(CI, RetVal, TLI ? TLI->getDataLayout() : 0,
 636                                   TLInfo, ModifiedDT ? 0 : DT);
 637
 638     // If the iterator instruction was recursively deleted, start over at the
 639     // start of the block.
 640     if (IterHandle != CurInstIterator) {
 641       CurInstIterator = BB->begin();
 642       SunkAddrs.clear();
 643     }
 644     return true;
 645   }
 646
 647   if (II && TLI) {
 648     SmallVector<Value*, 2> PtrOps;
 649     Type *AccessTy;
 650     if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy))
 651       while (!PtrOps.empty())
 652         if (OptimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy))
 653           return true;
 654   }
 655
 656   // From here on out we're working with named functions.
 657   if (CI->getCalledFunction() == 0) return false;
 658
 659   // We'll need DataLayout from here on out.
 660   const DataLayout *TD = TLI ? TLI->getDataLayout() : 0;
 661   if (!TD) return false;
 662
 663   // Lower all default uses of _chk calls.  This is very similar
 664   // to what InstCombineCalls does, but here we are only lowering calls
 665   // that have the default "don't know" as the objectsize.  Anything else
 666   // should be left alone.
 667   CodeGenPrepareFortifiedLibCalls Simplifier;
 668   return Simplifier.fold(CI, TD, TLInfo);
 669 }
 670
 671 /// DupRetToEnableTailCallOpts - Look for opportunities to duplicate return
 672 /// instructions to the predecessor to enable tail call optimizations. The
 673 /// case it is currently looking for is:
 674 /// @code
 675 /// bb0:
 676 ///   %tmp0 = tail call i32 @f0()
 677 ///   br label %return
 678 /// bb1:
 679 ///   %tmp1 = tail call i32 @f1()
 680 ///   br label %return
 681 /// bb2:
 682 ///   %tmp2 = tail call i32 @f2()
 683 ///   br label %return
 684 /// return:
 685 ///   %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ]
 686 ///   ret i32 %retval
 687 /// @endcode
 688 ///
 689 /// =>
 690 ///
 691 /// @code
 692 /// bb0:
 693 ///   %tmp0 = tail call i32 @f0()
 694 ///   ret i32 %tmp0
 695 /// bb1:
 696 ///   %tmp1 = tail call i32 @f1()
 697 ///   ret i32 %tmp1
 698 /// bb2:
 699 ///   %tmp2 = tail call i32 @f2()
 700 ///   ret i32 %tmp2
 701 /// @endcode
 702 bool CodeGenPrepare::DupRetToEnableTailCallOpts(BasicBlock *BB) {
 703   if (!TLI)
 704     return false;
 705
 706   ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator());
 707   if (!RI)
 708     return false;
 709
 710   PHINode *PN = 0;
 711   BitCastInst *BCI = 0;
 712   Value *V = RI->getReturnValue();
 713   if (V) {
 714     BCI = dyn_cast<BitCastInst>(V);
 715     if (BCI)
 716       V = BCI->getOperand(0);
 717
 718     PN = dyn_cast<PHINode>(V);
 719     if (!PN)
 720       return false;
 721   }
 722
 723   if (PN && PN->getParent() != BB)
 724     return false;
 725
 726   // It's not safe to eliminate the sign / zero extension of the return value.
 727   // See llvm::isInTailCallPosition().
 728   const Function *F = BB->getParent();
 729   Attributes CallerRetAttr = F->getAttributes().getRetAttributes();
 730   if (CallerRetAttr.hasAttribute(Attributes::ZExt) ||
 731       CallerRetAttr.hasAttribute(Attributes::SExt))
 732     return false;
 733
 734   // Make sure there are no instructions between the PHI and return, or that the
 735   // return is the first instruction in the block.
 736   if (PN) {
 737     BasicBlock::iterator BI = BB->begin();
 738     do { ++BI; } while (isa<DbgInfoIntrinsic>(BI));
 739     if (&*BI == BCI)
 740       // Also skip over the bitcast.
 741       ++BI;
 742     if (&*BI != RI)
 743       return false;
 744   } else {
 745     BasicBlock::iterator BI = BB->begin();
 746     while (isa<DbgInfoIntrinsic>(BI)) ++BI;
 747     if (&*BI != RI)
 748       return false;
 749   }
 750
 751   /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail
 752   /// call.
 753   SmallVector<CallInst*, 4> TailCalls;
 754   if (PN) {
 755     for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
 756       CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I));
 757       // Make sure the phi value is indeed produced by the tail call.
 758       if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) &&
 759           TLI->mayBeEmittedAsTailCall(CI))
 760         TailCalls.push_back(CI);
 761     }
 762   } else {
 763     SmallPtrSet<BasicBlock*, 4> VisitedBBs;
 764     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
 765       if (!VisitedBBs.insert(*PI))
 766         continue;
 767
 768       BasicBlock::InstListType &InstList = (*PI)->getInstList();
 769       BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin();
 770       BasicBlock::InstListType::reverse_iterator RE = InstList.rend();
 771       do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI));
 772       if (RI == RE)
 773         continue;
 774
 775       CallInst *CI = dyn_cast<CallInst>(&*RI);
 776       if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI))
 777         TailCalls.push_back(CI);
 778     }
 779   }
 780
 781   bool Changed = false;
 782   for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) {
 783     CallInst *CI = TailCalls[i];
 784     CallSite CS(CI);
 785
 786     // Conservatively require the attributes of the call to match those of the
 787     // return. Ignore noalias because it doesn't affect the call sequence.
 788     Attributes CalleeRetAttr = CS.getAttributes().getRetAttributes();
 789     if (AttrBuilder(CalleeRetAttr).
 790           removeAttribute(Attributes::NoAlias) !=
 791         AttrBuilder(CallerRetAttr).
 792           removeAttribute(Attributes::NoAlias))
 793       continue;
 794
 795     // Make sure the call instruction is followed by an unconditional branch to
 796     // the return block.
 797     BasicBlock *CallBB = CI->getParent();
 798     BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator());
 799     if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
 800       continue;
 801
 802     // Duplicate the return into CallBB.
 803     (void)FoldReturnIntoUncondBranch(RI, BB, CallBB);
 804     ModifiedDT = Changed = true;
 805     ++NumRetsDup;
 806   }
 807
 808   // If we eliminated all predecessors of the block, delete the block now.
 809   if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
 810     BB->eraseFromParent();
 811
 812   return Changed;
 813 }
 814
 815 //===----------------------------------------------------------------------===//
 816 // Memory Optimization
 817 //===----------------------------------------------------------------------===//
 818
 819 /// IsNonLocalValue - Return true if the specified values are defined in a
 820 /// different basic block than BB.
 821 static bool IsNonLocalValue(Value *V, BasicBlock *BB) {
 822   if (Instruction *I = dyn_cast<Instruction>(V))
 823     return I->getParent() != BB;
 824   return false;
 825 }
 826
 827 /// OptimizeMemoryInst - Load and Store Instructions often have
 828 /// addressing modes that can do significant amounts of computation.  As such,
 829 /// instruction selection will try to get the load or store to do as much
 830 /// computation as possible for the program.  The problem is that isel can only
 831 /// see within a single block.  As such, we sink as much legal addressing mode
 832 /// stuff into the block as possible.
 833 ///
 834 /// This method is used to optimize both load/store and inline asms with memory
 835 /// operands.
 836 bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
 837                                         Type *AccessTy) {
 838   Value *Repl = Addr;
 839
 840   // Try to collapse single-value PHI nodes.  This is necessary to undo
 841   // unprofitable PRE transformations.
 842   SmallVector<Value*, 8> worklist;
 843   SmallPtrSet<Value*, 16> Visited;
 844   worklist.push_back(Addr);
 845
 846   // Use a worklist to iteratively look through PHI nodes, and ensure that
 847   // the addressing mode obtained from the non-PHI roots of the graph
 848   // are equivalent.
 849   Value *Consensus = 0;
 850   unsigned NumUsesConsensus = 0;
 851   bool IsNumUsesConsensusValid = false;
 852   SmallVector<Instruction*, 16> AddrModeInsts;
 853   ExtAddrMode AddrMode;
 854   while (!worklist.empty()) {
 855     Value *V = worklist.back();
 856     worklist.pop_back();
 857
 858     // Break use-def graph loops.
 859     if (!Visited.insert(V)) {
 860       Consensus = 0;
 861       break;
 862     }
 863
 864     // For a PHI node, push all of its incoming values.
 865     if (PHINode *P = dyn_cast<PHINode>(V)) {
 866       for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i)
 867         worklist.push_back(P->getIncomingValue(i));
 868       continue;
 869     }
 870
 871     // For non-PHIs, determine the addressing mode being computed.
 872     SmallVector<Instruction*, 16> NewAddrModeInsts;
 873     ExtAddrMode NewAddrMode =
 874       AddressingModeMatcher::Match(V, AccessTy, MemoryInst,
 875                                    NewAddrModeInsts, *TLI);
 876
 877     // This check is broken into two cases with very similar code to avoid using
 878     // getNumUses() as much as possible. Some values have a lot of uses, so
 879     // calling getNumUses() unconditionally caused a significant compile-time
 880     // regression.
 881     if (!Consensus) {
 882       Consensus = V;
 883       AddrMode = NewAddrMode;
 884       AddrModeInsts = NewAddrModeInsts;
 885       continue;
 886     } else if (NewAddrMode == AddrMode) {
 887       if (!IsNumUsesConsensusValid) {
 888         NumUsesConsensus = Consensus->getNumUses();
 889         IsNumUsesConsensusValid = true;
 890       }
 891
 892       // Ensure that the obtained addressing mode is equivalent to that obtained
 893       // for all other roots of the PHI traversal.  Also, when choosing one
 894       // such root as representative, select the one with the most uses in order
 895       // to keep the cost modeling heuristics in AddressingModeMatcher
 896       // applicable.
 897       unsigned NumUses = V->getNumUses();
 898       if (NumUses > NumUsesConsensus) {
 899         Consensus = V;
 900         NumUsesConsensus = NumUses;
 901         AddrModeInsts = NewAddrModeInsts;
 902       }
 903       continue;
 904     }
 905
 906     Consensus = 0;
 907     break;
 908   }
 909
 910   // If the addressing mode couldn't be determined, or if multiple different
 911   // ones were determined, bail out now.
 912   if (!Consensus) return false;
 913
 914   // Check to see if any of the instructions supersumed by this addr mode are
 915   // non-local to I's BB.
 916   bool AnyNonLocal = false;
 917   for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) {
 918     if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) {
 919       AnyNonLocal = true;
 920       break;
 921     }
 922   }
 923
 924   // If all the instructions matched are already in this BB, don't do anything.
 925   if (!AnyNonLocal) {
 926     DEBUG(dbgs() << "CGP: Found      local addrmode: " << AddrMode << "\n");
 927     return false;
 928   }
 929
 930   // Insert this computation right after this user.  Since our caller is
 931   // scanning from the top of the BB to the bottom, reuse of the expr are
 932   // guaranteed to happen later.
 933   IRBuilder<> Builder(MemoryInst);
 934
 935   // Now that we determined the addressing expression we want to use and know
 936   // that we have to sink it into this block.  Check to see if we have already
 937   // done this for some other load/store instr in this block.  If so, reuse the
 938   // computation.
 939   Value *&SunkAddr = SunkAddrs[Addr];
 940   if (SunkAddr) {
 941     DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for "
 942                  << *MemoryInst);
 943     if (SunkAddr->getType() != Addr->getType())
 944       SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType());
 945   } else {
 946     DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for "
 947                  << *MemoryInst);
 948     Type *IntPtrTy =
 949           TLI->getDataLayout()->getIntPtrType(AccessTy->getContext());
 950
 951     Value *Result = 0;
 952
 953     // Start with the base register. Do this first so that subsequent address
 954     // matching finds it last, which will prevent it from trying to match it
 955     // as the scaled value in case it happens to be a mul. That would be
 956     // problematic if we've sunk a different mul for the scale, because then
 957     // we'd end up sinking both muls.
 958     if (AddrMode.BaseReg) {
 959       Value *V = AddrMode.BaseReg;
 960       if (V->getType()->isPointerTy())
 961         V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
 962       if (V->getType() != IntPtrTy)
 963         V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr");
 964       Result = V;
 965     }
 966
 967     // Add the scale value.
 968     if (AddrMode.Scale) {
 969       Value *V = AddrMode.ScaledReg;
 970       if (V->getType() == IntPtrTy) {
 971         // done.
 972       } else if (V->getType()->isPointerTy()) {
 973         V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr");
 974       } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() <
 975                  cast<IntegerType>(V->getType())->getBitWidth()) {
 976         V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr");
 977       } else {
 978         V = Builder.CreateSExt(V, IntPtrTy, "sunkaddr");
 979       }
 980       if (AddrMode.Scale != 1)
 981         V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale),
 982                               "sunkaddr");
 983       if (Result)
 984         Result = Builder.CreateAdd(Result, V, "sunkaddr");
 985       else
 986         Result = V;
 987     }
 988
 989     // Add in the BaseGV if present.
 990     if (AddrMode.BaseGV) {
 991       Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr");
 992       if (Result)
 993         Result = Builder.CreateAdd(Result, V, "sunkaddr");
 994       else
 995         Result = V;
 996     }
 997
 998     // Add in the Base Offset if present.
 999     if (AddrMode.BaseOffs) {
1000       Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs);
1001       if (Result)
1002         Result = Builder.CreateAdd(Result, V, "sunkaddr");
1003       else
1004         Result = V;
1005     }
1006
1007     if (Result == 0)
1008       SunkAddr = Constant::getNullValue(Addr->getType());
1009     else
1010       SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr");
1011   }
1012
1013   MemoryInst->replaceUsesOfWith(Repl, SunkAddr);
1014
1015   // If we have no uses, recursively delete the value and all dead instructions
1016   // using it.
1017   if (Repl->use_empty()) {
1018     // This can cause recursive deletion, which can invalidate our iterator.
1019     // Use a WeakVH to hold onto it in case this happens.
1020     WeakVH IterHandle(CurInstIterator);
1021     BasicBlock *BB = CurInstIterator->getParent();
1022
1023     RecursivelyDeleteTriviallyDeadInstructions(Repl, TLInfo);
1024
1025     if (IterHandle != CurInstIterator) {
1026       // If the iterator instruction was recursively deleted, start over at the
1027       // start of the block.
1028       CurInstIterator = BB->begin();
1029       SunkAddrs.clear();
1030     } else {
1031       // This address is now available for reassignment, so erase the table
1032       // entry; we don't want to match some completely different instruction.
1033       SunkAddrs[Addr] = 0;
1034     }
1035   }
1036   ++NumMemoryInsts;
1037   return true;
1038 }
1039
1040 /// OptimizeInlineAsmInst - If there are any memory operands, use
1041 /// OptimizeMemoryInst to sink their address computing into the block when
1042 /// possible / profitable.
1043 bool CodeGenPrepare::OptimizeInlineAsmInst(CallInst *CS) {
1044   bool MadeChange = false;
1045
1046   TargetLowering::AsmOperandInfoVector
1047     TargetConstraints = TLI->ParseConstraints(CS);
1048   unsigned ArgNo = 0;
1049   for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
1050     TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
1051
1052     // Compute the constraint code and ConstraintType to use.
1053     TLI->ComputeConstraintToUse(OpInfo, SDValue());
1054
1055     if (OpInfo.ConstraintType == TargetLowering::C_Memory &&
1056         OpInfo.isIndirect) {
1057       Value *OpVal = CS->getArgOperand(ArgNo++);
1058       MadeChange |= OptimizeMemoryInst(CS, OpVal, OpVal->getType());
1059     } else if (OpInfo.Type == InlineAsm::isInput)
1060       ArgNo++;
1061   }
1062
1063   return MadeChange;
1064 }
1065
1066 /// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same
1067 /// basic block as the load, unless conditions are unfavorable. This allows
1068 /// SelectionDAG to fold the extend into the load.
1069 ///
1070 bool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) {
1071   // Look for a load being extended.
1072   LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0));
1073   if (!LI) return false;
1074
1075   // If they're already in the same block, there's nothing to do.
1076   if (LI->getParent() == I->getParent())
1077     return false;
1078
1079   // If the load has other users and the truncate is not free, this probably
1080   // isn't worthwhile.
1081   if (!LI->hasOneUse() &&
1082       TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) ||
1083               !TLI->isTypeLegal(TLI->getValueType(I->getType()))) &&
1084       !TLI->isTruncateFree(I->getType(), LI->getType()))
1085     return false;
1086
1087   // Check whether the target supports casts folded into loads.
1088   unsigned LType;
1089   if (isa<ZExtInst>(I))
1090     LType = ISD::ZEXTLOAD;
1091   else {
1092     assert(isa<SExtInst>(I) && "Unexpected ext type!");
1093     LType = ISD::SEXTLOAD;
1094   }
1095   if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType())))
1096     return false;
1097
1098   // Move the extend into the same block as the load, so that SelectionDAG
1099   // can fold it.
1100   I->removeFromParent();
1101   I->insertAfter(LI);
1102   ++NumExtsMoved;
1103   return true;
1104 }
1105
1106 bool CodeGenPrepare::OptimizeExtUses(Instruction *I) {
1107   BasicBlock *DefBB = I->getParent();
1108
1109   // If the result of a {s|z}ext and its source are both live out, rewrite all
1110   // other uses of the source with result of extension.
1111   Value *Src = I->getOperand(0);
1112   if (Src->hasOneUse())
1113     return false;
1114
1115   // Only do this xform if truncating is free.
1116   if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType()))
1117     return false;
1118
1119   // Only safe to perform the optimization if the source is also defined in
1120   // this block.
1121   if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent())
1122     return false;
1123
1124   bool DefIsLiveOut = false;
1125   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
1126        UI != E; ++UI) {
1127     Instruction *User = cast<Instruction>(*UI);
1128
1129     // Figure out which BB this ext is used in.
1130     BasicBlock *UserBB = User->getParent();
1131     if (UserBB == DefBB) continue;
1132     DefIsLiveOut = true;
1133     break;
1134   }
1135   if (!DefIsLiveOut)
1136     return false;
1137
1138   // Make sure non of the uses are PHI nodes.
1139   for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end();
1140        UI != E; ++UI) {
1141     Instruction *User = cast<Instruction>(*UI);
1142     BasicBlock *UserBB = User->getParent();
1143     if (UserBB == DefBB) continue;
1144     // Be conservative. We don't want this xform to end up introducing
1145     // reloads just before load / store instructions.
1146     if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User))
1147       return false;
1148   }
1149
1150   // InsertedTruncs - Only insert one trunc in each block once.
1151   DenseMap<BasicBlock*, Instruction*> InsertedTruncs;
1152
1153   bool MadeChange = false;
1154   for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end();
1155        UI != E; ++UI) {
1156     Use &TheUse = UI.getUse();
1157     Instruction *User = cast<Instruction>(*UI);
1158
1159     // Figure out which BB this ext is used in.
1160     BasicBlock *UserBB = User->getParent();
1161     if (UserBB == DefBB) continue;
1162
1163     // Both src and def are live in this block. Rewrite the use.
1164     Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
1165
1166     if (!InsertedTrunc) {
1167       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1168       InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt);
1169     }
1170
1171     // Replace a use of the {s|z}ext source with a use of the result.
1172     TheUse = InsertedTrunc;
1173     ++NumExtUses;
1174     MadeChange = true;
1175   }
1176
1177   return MadeChange;
1178 }
1179
1180 /// isFormingBranchFromSelectProfitable - Returns true if a SelectInst should be
1181 /// turned into an explicit branch.
1182 static bool isFormingBranchFromSelectProfitable(SelectInst *SI) {
1183   // FIXME: This should use the same heuristics as IfConversion to determine
1184   // whether a select is better represented as a branch.  This requires that
1185   // branch probability metadata is preserved for the select, which is not the
1186   // case currently.
1187
1188   CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
1189
1190   // If the branch is predicted right, an out of order CPU can avoid blocking on
1191   // the compare.  Emit cmovs on compares with a memory operand as branches to
1192   // avoid stalls on the load from memory.  If the compare has more than one use
1193   // there's probably another cmov or setcc around so it's not worth emitting a
1194   // branch.
1195   if (!Cmp)
1196     return false;
1197
1198   Value *CmpOp0 = Cmp->getOperand(0);
1199   Value *CmpOp1 = Cmp->getOperand(1);
1200
1201   // We check that the memory operand has one use to avoid uses of the loaded
1202   // value directly after the compare, making branches unprofitable.
1203   return Cmp->hasOneUse() &&
1204          ((isa<LoadInst>(CmpOp0) && CmpOp0->hasOneUse()) ||
1205           (isa<LoadInst>(CmpOp1) && CmpOp1->hasOneUse()));
1206 }
1207
1208
1209 /// If we have a SelectInst that will likely profit from branch prediction,
1210 /// turn it into a branch.
1211 bool CodeGenPrepare::OptimizeSelectInst(SelectInst *SI) {
1212   bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
1213
1214   // Can we convert the 'select' to CF ?
1215   if (DisableSelectToBranch || OptSize || !TLI || VectorCond)
1216     return false;
1217
1218   TargetLowering::SelectSupportKind SelectKind;
1219   if (VectorCond)
1220     SelectKind = TargetLowering::VectorMaskSelect;
1221   else if (SI->getType()->isVectorTy())
1222     SelectKind = TargetLowering::ScalarCondVectorVal;
1223   else
1224     SelectKind = TargetLowering::ScalarValSelect;
1225
1226   // Do we have efficient codegen support for this kind of 'selects' ?
1227   if (TLI->isSelectSupported(SelectKind)) {
1228     // We have efficient codegen support for the select instruction.
1229     // Check if it is profitable to keep this 'select'.
1230     if (!TLI->isPredictableSelectExpensive() ||
1231         !isFormingBranchFromSelectProfitable(SI))
1232       return false;
1233   }
1234
1235   ModifiedDT = true;
1236
1237   // First, we split the block containing the select into 2 blocks.
1238   BasicBlock *StartBlock = SI->getParent();
1239   BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(SI));
1240   BasicBlock *NextBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");
1241
1242   // Create a new block serving as the landing pad for the branch.
1243   BasicBlock *SmallBlock = BasicBlock::Create(SI->getContext(), "select.mid",
1244                                              NextBlock->getParent(), NextBlock);
1245
1246   // Move the unconditional branch from the block with the select in it into our
1247   // landing pad block.
1248   StartBlock->getTerminator()->eraseFromParent();
1249   BranchInst::Create(NextBlock, SmallBlock);
1250
1251   // Insert the real conditional branch based on the original condition.
1252   BranchInst::Create(NextBlock, SmallBlock, SI->getCondition(), SI);
1253
1254   // The select itself is replaced with a PHI Node.
1255   PHINode *PN = PHINode::Create(SI->getType(), 2, "", NextBlock->begin());
1256   PN->takeName(SI);
1257   PN->addIncoming(SI->getTrueValue(), StartBlock);
1258   PN->addIncoming(SI->getFalseValue(), SmallBlock);
1259   SI->replaceAllUsesWith(PN);
1260   SI->eraseFromParent();
1261
1262   // Instruct OptimizeBlock to skip to the next block.
1263   CurInstIterator = StartBlock->end();
1264   ++NumSelectsExpanded;
1265   return true;
1266 }
1267
1268 bool CodeGenPrepare::OptimizeInst(Instruction *I) {
1269   if (PHINode *P = dyn_cast<PHINode>(I)) {
1270     // It is possible for very late stage optimizations (such as SimplifyCFG)
1271     // to introduce PHI nodes too late to be cleaned up.  If we detect such a
1272     // trivial PHI, go ahead and zap it here.
1273     if (Value *V = SimplifyInstruction(P)) {
1274       P->replaceAllUsesWith(V);
1275       P->eraseFromParent();
1276       ++NumPHIsElim;
1277       return true;
1278     }
1279     return false;
1280   }
1281
1282   if (CastInst *CI = dyn_cast<CastInst>(I)) {
1283     // If the source of the cast is a constant, then this should have
1284     // already been constant folded.  The only reason NOT to constant fold
1285     // it is if something (e.g. LSR) was careful to place the constant
1286     // evaluation in a block other than then one that uses it (e.g. to hoist
1287     // the address of globals out of a loop).  If this is the case, we don't
1288     // want to forward-subst the cast.
1289     if (isa<Constant>(CI->getOperand(0)))
1290       return false;
1291
1292     if (TLI && OptimizeNoopCopyExpression(CI, *TLI))
1293       return true;
1294
1295     if (isa<ZExtInst>(I) || isa<SExtInst>(I)) {
1296       bool MadeChange = MoveExtToFormExtLoad(I);
1297       return MadeChange | OptimizeExtUses(I);
1298     }
1299     return false;
1300   }
1301
1302   if (CmpInst *CI = dyn_cast<CmpInst>(I))
1303     return OptimizeCmpExpression(CI);
1304
1305   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
1306     if (TLI)
1307       return OptimizeMemoryInst(I, I->getOperand(0), LI->getType());
1308     return false;
1309   }
1310
1311   if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
1312     if (TLI)
1313       return OptimizeMemoryInst(I, SI->getOperand(1),
1314                                 SI->getOperand(0)->getType());
1315     return false;
1316   }
1317
1318   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
1319     if (GEPI->hasAllZeroIndices()) {
1320       /// The GEP operand must be a pointer, so must its result -> BitCast
1321       Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
1322                                         GEPI->getName(), GEPI);
1323       GEPI->replaceAllUsesWith(NC);
1324       GEPI->eraseFromParent();
1325       ++NumGEPsElim;
1326       OptimizeInst(NC);
1327       return true;
1328     }
1329     return false;
1330   }
1331
1332   if (CallInst *CI = dyn_cast<CallInst>(I))
1333     return OptimizeCallInst(CI);
1334
1335   if (SelectInst *SI = dyn_cast<SelectInst>(I))
1336     return OptimizeSelectInst(SI);
1337
1338   return false;
1339 }
1340
1341 // In this pass we look for GEP and cast instructions that are used
1342 // across basic blocks and rewrite them to improve basic-block-at-a-time
1343 // selection.
1344 bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) {
1345   SunkAddrs.clear();
1346   bool MadeChange = false;
1347
1348   CurInstIterator = BB.begin();
1349   while (CurInstIterator != BB.end())
1350     MadeChange |= OptimizeInst(CurInstIterator++);
1351
1352   MadeChange |= DupRetToEnableTailCallOpts(&BB);
1353
1354   return MadeChange;
1355 }
1356
1357 // llvm.dbg.value is far away from the value then iSel may not be able
1358 // handle it properly. iSel will drop llvm.dbg.value if it can not
1359 // find a node corresponding to the value.
1360 bool CodeGenPrepare::PlaceDbgValues(Function &F) {
1361   bool MadeChange = false;
1362   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
1363     Instruction *PrevNonDbgInst = NULL;
1364     for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE;) {
1365       Instruction *Insn = BI; ++BI;
1366       DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn);
1367       if (!DVI) {
1368         PrevNonDbgInst = Insn;
1369         continue;
1370       }
1371
1372       Instruction *VI = dyn_cast_or_null<Instruction>(DVI->getValue());
1373       if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) {
1374         DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI);
1375         DVI->removeFromParent();
1376         if (isa<PHINode>(VI))
1377           DVI->insertBefore(VI->getParent()->getFirstInsertionPt());
1378         else
1379           DVI->insertAfter(VI);
1380         MadeChange = true;
1381         ++NumDbgValueMoved;
1382       }
1383     }
1384   }
1385   return MadeChange;
1386 }