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