9ada111eaa92e683b1b40db7883fc116115880b2
[oota-llvm.git] / lib / CodeGen / 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 #include "llvm/CodeGen/Passes.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/Analysis/InstructionSimplify.h"
24 #include "llvm/Analysis/MemoryLocation.h"
25 #include "llvm/Analysis/TargetLibraryInfo.h"
26 #include "llvm/Analysis/TargetTransformInfo.h"
27 #include "llvm/Analysis/ValueTracking.h"
28 #include "llvm/IR/CallSite.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DataLayout.h"
31 #include "llvm/IR/DerivedTypes.h"
32 #include "llvm/IR/Dominators.h"
33 #include "llvm/IR/Function.h"
34 #include "llvm/IR/GetElementPtrTypeIterator.h"
35 #include "llvm/IR/IRBuilder.h"
36 #include "llvm/IR/InlineAsm.h"
37 #include "llvm/IR/InstIterator.h"
38 #include "llvm/IR/InstrTypes.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/IntrinsicInst.h"
41 #include "llvm/IR/MDBuilder.h"
42 #include "llvm/IR/NoFolder.h"
43 #include "llvm/IR/PatternMatch.h"
44 #include "llvm/IR/Statepoint.h"
45 #include "llvm/IR/ValueHandle.h"
46 #include "llvm/IR/ValueMap.h"
47 #include "llvm/Pass.h"
48 #include "llvm/Support/CommandLine.h"
49 #include "llvm/Support/Debug.h"
50 #include "llvm/Support/raw_ostream.h"
51 #include "llvm/Target/TargetLowering.h"
52 #include "llvm/Target/TargetSubtargetInfo.h"
53 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
54 #include "llvm/Transforms/Utils/BuildLibCalls.h"
55 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
56 #include "llvm/Transforms/Utils/Local.h"
57 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
58 using namespace llvm;
59 using namespace llvm::PatternMatch;
60
61 #define DEBUG_TYPE "codegenprepare"
62
63 STATISTIC(NumBlocksElim, "Number of blocks eliminated");
64 STATISTIC(NumPHIsElim,   "Number of trivial PHIs eliminated");
65 STATISTIC(NumGEPsElim,   "Number of GEPs converted to casts");
66 STATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of "
67                       "sunken Cmps");
68 STATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses "
69                        "of sunken Casts");
70 STATISTIC(NumMemoryInsts, "Number of memory instructions whose address "
71                           "computations were sunk");
72 STATISTIC(NumExtsMoved,  "Number of [s|z]ext instructions combined with loads");
73 STATISTIC(NumExtUses,    "Number of uses of [s|z]ext instructions optimized");
74 STATISTIC(NumAndsAdded,
75           "Number of and mask instructions added to form ext loads");
76 STATISTIC(NumAndUses, "Number of uses of and mask instructions optimized");
77 STATISTIC(NumRetsDup,    "Number of return instructions duplicated");
78 STATISTIC(NumDbgValueMoved, "Number of debug value instructions moved");
79 STATISTIC(NumSelectsExpanded, "Number of selects turned into branches");
80 STATISTIC(NumAndCmpsMoved, "Number of and/cmp's pushed into branches");
81 STATISTIC(NumStoreExtractExposed, "Number of store(extractelement) exposed");
82
83 static cl::opt<bool> DisableBranchOpts(
84   "disable-cgp-branch-opts", cl::Hidden, cl::init(false),
85   cl::desc("Disable branch optimizations in CodeGenPrepare"));
86
87 static cl::opt<bool>
88     DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false),
89                   cl::desc("Disable GC optimizations in CodeGenPrepare"));
90
91 static cl::opt<bool> DisableSelectToBranch(
92   "disable-cgp-select2branch", cl::Hidden, cl::init(false),
93   cl::desc("Disable select to branch conversion."));
94
95 static cl::opt<bool> AddrSinkUsingGEPs(
96   "addr-sink-using-gep", cl::Hidden, cl::init(false),
97   cl::desc("Address sinking in CGP using GEPs."));
98
99 static cl::opt<bool> EnableAndCmpSinking(
100    "enable-andcmp-sinking", cl::Hidden, cl::init(true),
101    cl::desc("Enable sinkinig and/cmp into branches."));
102
103 static cl::opt<bool> DisableStoreExtract(
104     "disable-cgp-store-extract", cl::Hidden, cl::init(false),
105     cl::desc("Disable store(extract) optimizations in CodeGenPrepare"));
106
107 static cl::opt<bool> StressStoreExtract(
108     "stress-cgp-store-extract", cl::Hidden, cl::init(false),
109     cl::desc("Stress test store(extract) optimizations in CodeGenPrepare"));
110
111 static cl::opt<bool> DisableExtLdPromotion(
112     "disable-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
113     cl::desc("Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
114              "CodeGenPrepare"));
115
116 static cl::opt<bool> StressExtLdPromotion(
117     "stress-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
118     cl::desc("Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
119              "optimization in CodeGenPrepare"));
120
121 namespace {
122 typedef SmallPtrSet<Instruction *, 16> SetOfInstrs;
123 typedef PointerIntPair<Type *, 1, bool> TypeIsSExt;
124 typedef DenseMap<Instruction *, TypeIsSExt> InstrToOrigTy;
125 class TypePromotionTransaction;
126
127   class CodeGenPrepare : public FunctionPass {
128     const TargetMachine *TM;
129     const TargetLowering *TLI;
130     const TargetTransformInfo *TTI;
131     const TargetLibraryInfo *TLInfo;
132
133     /// As we scan instructions optimizing them, this is the next instruction
134     /// to optimize. Transforms that can invalidate this should update it.
135     BasicBlock::iterator CurInstIterator;
136
137     /// Keeps track of non-local addresses that have been sunk into a block.
138     /// This allows us to avoid inserting duplicate code for blocks with
139     /// multiple load/stores of the same address.
140     ValueMap<Value*, Value*> SunkAddrs;
141
142     /// Keeps track of all instructions inserted for the current function.
143     SetOfInstrs InsertedInsts;
144     /// Keeps track of the type of the related instruction before their
145     /// promotion for the current function.
146     InstrToOrigTy PromotedInsts;
147
148     /// True if CFG is modified in any way.
149     bool ModifiedDT;
150
151     /// True if optimizing for size.
152     bool OptSize;
153
154     /// DataLayout for the Function being processed.
155     const DataLayout *DL;
156
157   public:
158     static char ID; // Pass identification, replacement for typeid
159     explicit CodeGenPrepare(const TargetMachine *TM = nullptr)
160         : FunctionPass(ID), TM(TM), TLI(nullptr), TTI(nullptr), DL(nullptr) {
161         initializeCodeGenPreparePass(*PassRegistry::getPassRegistry());
162       }
163     bool runOnFunction(Function &F) override;
164
165     const char *getPassName() const override { return "CodeGen Prepare"; }
166
167     void getAnalysisUsage(AnalysisUsage &AU) const override {
168       AU.addPreserved<DominatorTreeWrapperPass>();
169       AU.addRequired<TargetLibraryInfoWrapperPass>();
170       AU.addRequired<TargetTransformInfoWrapperPass>();
171     }
172
173   private:
174     bool eliminateFallThrough(Function &F);
175     bool eliminateMostlyEmptyBlocks(Function &F);
176     bool canMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
177     void eliminateMostlyEmptyBlock(BasicBlock *BB);
178     bool optimizeBlock(BasicBlock &BB, bool& ModifiedDT);
179     bool optimizeInst(Instruction *I, bool& ModifiedDT);
180     bool optimizeMemoryInst(Instruction *I, Value *Addr,
181                             Type *AccessTy, unsigned AS);
182     bool optimizeInlineAsmInst(CallInst *CS);
183     bool optimizeCallInst(CallInst *CI, bool& ModifiedDT);
184     bool moveExtToFormExtLoad(Instruction *&I);
185     bool optimizeExtUses(Instruction *I);
186     bool optimizeLoadExt(LoadInst *I);
187     bool optimizeSelectInst(SelectInst *SI);
188     bool optimizeShuffleVectorInst(ShuffleVectorInst *SI);
189     bool optimizeSwitchInst(SwitchInst *CI);
190     bool optimizeExtractElementInst(Instruction *Inst);
191     bool dupRetToEnableTailCallOpts(BasicBlock *BB);
192     bool placeDbgValues(Function &F);
193     bool sinkAndCmp(Function &F);
194     bool extLdPromotion(TypePromotionTransaction &TPT, LoadInst *&LI,
195                         Instruction *&Inst,
196                         const SmallVectorImpl<Instruction *> &Exts,
197                         unsigned CreatedInstCost);
198     bool splitBranchCondition(Function &F);
199     bool simplifyOffsetableRelocate(Instruction &I);
200     void stripInvariantGroupMetadata(Instruction &I);
201   };
202 }
203
204 char CodeGenPrepare::ID = 0;
205 INITIALIZE_TM_PASS(CodeGenPrepare, "codegenprepare",
206                    "Optimize for code generation", false, false)
207
208 FunctionPass *llvm::createCodeGenPreparePass(const TargetMachine *TM) {
209   return new CodeGenPrepare(TM);
210 }
211
212 namespace {
213
214 bool StoreAddressDependOnValue(StoreInst* SI, Value* DepVal);
215 Value* GetUntaintedAddress(Value* CurrentAddress);
216
217 // The depth we trace down a variable to look for its dependence set.
218 const unsigned kDependenceDepth = 4;
219
220 // Recursively looks for variables that 'Val' depends on at the given depth
221 // 'Depth', and adds them in 'DepSet'. If 'InsertOnlyLeafNodes' is true, only
222 // inserts the leaf node values; otherwise, all visited nodes are included in
223 // 'DepSet'. Note that constants will be ignored.
224 template <typename SetType>
225 void recursivelyFindDependence(SetType* DepSet, Value* Val,
226                                bool InsertOnlyLeafNodes = false,
227                                unsigned Depth = kDependenceDepth) {
228   if (Val == nullptr) {
229     return;
230   }
231   if (!InsertOnlyLeafNodes && !isa<Constant>(Val)) {
232     DepSet->insert(Val);
233   }
234   if (Depth == 0) {
235     // Cannot go deeper. Insert the leaf nodes.
236     if (InsertOnlyLeafNodes && !isa<Constant>(Val)) {
237       DepSet->insert(Val);
238     }
239     return;
240   }
241
242   // Go one step further to explore the dependence of the operands.
243   Instruction* I = nullptr;
244   if ((I = dyn_cast<Instruction>(Val))) {
245     if (isa<LoadInst>(I)) {
246       // A load is considerd the leaf load of the dependence tree. Done.
247       DepSet->insert(Val);
248       return;
249     } else if (I->isBinaryOp()) {
250       BinaryOperator* I = dyn_cast<BinaryOperator>(Val);
251       Value *Op0 = I->getOperand(0), *Op1 = I->getOperand(1);
252       recursivelyFindDependence(DepSet, Op0, Depth - 1);
253       recursivelyFindDependence(DepSet, Op1, Depth - 1);
254     } else if (I->isCast()) {
255       Value* Op0 = I->getOperand(0);
256       recursivelyFindDependence(DepSet, Op0, Depth - 1);
257     } else if (I->getOpcode() == Instruction::Select) {
258       Value* Op0 = I->getOperand(0);
259       Value* Op1 = I->getOperand(1);
260       Value* Op2 = I->getOperand(2);
261       recursivelyFindDependence(DepSet, Op0, Depth - 1);
262       recursivelyFindDependence(DepSet, Op1, Depth - 1);
263       recursivelyFindDependence(DepSet, Op2, Depth - 1);
264     } else if (I->getOpcode() == Instruction::GetElementPtr) {
265       for (unsigned i = 0; i < I->getNumOperands(); i++) {
266         recursivelyFindDependence(DepSet, I->getOperand(i), Depth - 1);
267       }
268     } else if (I->getOpcode() == Instruction::Store) {
269       auto* SI = dyn_cast<StoreInst>(Val);
270       recursivelyFindDependence(DepSet, SI->getPointerOperand(), Depth - 1);
271       recursivelyFindDependence(DepSet, SI->getValueOperand(), Depth - 1);
272     } else {
273       Value* Op0 = nullptr;
274       Value* Op1 = nullptr;
275       switch (I->getOpcode()) {
276         case Instruction::ICmp:
277         case Instruction::FCmp: {
278           Op0 = I->getOperand(0);
279           Op1 = I->getOperand(1);
280           recursivelyFindDependence(DepSet, Op0, Depth - 1);
281           recursivelyFindDependence(DepSet, Op1, Depth - 1);
282           break;
283         }
284         default: {
285           // Be conservative. Add it and be done with it.
286           DepSet->insert(Val);
287           return;
288         }
289       }
290     }
291   } else if (isa<Constant>(Val)) {
292     // Not interested in constant values. Done.
293     return;
294   } else {
295     // Be conservative. Add it and be done with it.
296     DepSet->insert(Val);
297     return;
298   }
299 }
300
301 // Helper function to create a Cast instruction.
302 Value* createCast(IRBuilder<true, NoFolder>& Builder, Value* DepVal,
303                   Type* TargetIntegerType) {
304   Instruction::CastOps CastOp = Instruction::BitCast;
305   switch (DepVal->getType()->getTypeID()) {
306     case Type::IntegerTyID: {
307       CastOp = Instruction::SExt;
308       break;
309     }
310     case Type::FloatTyID:
311     case Type::DoubleTyID: {
312       CastOp = Instruction::FPToSI;
313       break;
314     }
315     case Type::PointerTyID: {
316       CastOp = Instruction::PtrToInt;
317       break;
318     }
319     default: { break; }
320   }
321
322   return Builder.CreateCast(CastOp, DepVal, TargetIntegerType);
323 }
324
325 // Given a value, if it's a tainted address, this function returns the
326 // instruction that ORs the "dependence value" with the "original address".
327 // Otherwise, returns nullptr.  This instruction is the first OR instruction
328 // where one of its operand is an AND instruction with an operand being 0.
329 //
330 // E.g., it returns '%4 = or i32 %3, %2' given 'CurrentAddress' is '%5'.
331 // %0 = load i32, i32* @y, align 4, !tbaa !1
332 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
333 // %1 = sext i1 %cmp to i32
334 // %2 = ptrtoint i32* @x to i32
335 // %3 = and i32 %1, 0
336 // %4 = or i32 %3, %2
337 // %5 = inttoptr i32 %4 to i32*
338 // store i32 1, i32* %5, align 4
339 Instruction* getOrAddress(Value* CurrentAddress) {
340   // Is it a cast from integer to pointer type.
341   Instruction* OrAddress = nullptr;
342   Instruction* AndDep = nullptr;
343   Instruction* CastToInt = nullptr;
344   Value* ActualAddress = nullptr;
345   Constant* ZeroConst = nullptr;
346
347   const Instruction* CastToPtr = dyn_cast<Instruction>(CurrentAddress);
348   if (CastToPtr && CastToPtr->getOpcode() == Instruction::IntToPtr) {
349     // Is it an OR instruction: %1 = or %and, %actualAddress.
350     if ((OrAddress = dyn_cast<Instruction>(CastToPtr->getOperand(0))) &&
351         OrAddress->getOpcode() == Instruction::Or) {
352       // The first operand should be and AND instruction.
353       AndDep = dyn_cast<Instruction>(OrAddress->getOperand(0));
354       if (AndDep && AndDep->getOpcode() == Instruction::And) {
355         // Also make sure its first operand of the "AND" is 0, or the "AND" is
356         // marked explicitly by "NoInstCombine".
357         if ((ZeroConst = dyn_cast<Constant>(AndDep->getOperand(1))) &&
358             ZeroConst->isNullValue()) {
359           return OrAddress;
360         }
361       }
362     }
363   }
364   // Looks like it's not been tainted.
365   return nullptr;
366 }
367
368 // Given a value, if it's a tainted address, this function returns the
369 // instruction that taints the "dependence value". Otherwise, returns nullptr.
370 // This instruction is the last AND instruction where one of its operand is 0.
371 // E.g., it returns '%3' given 'CurrentAddress' is '%5'.
372 // %0 = load i32, i32* @y, align 4, !tbaa !1
373 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
374 // %1 = sext i1 %cmp to i32
375 // %2 = ptrtoint i32* @x to i32
376 // %3 = and i32 %1, 0
377 // %4 = or i32 %3, %2
378 // %5 = inttoptr i32 %4 to i32*
379 // store i32 1, i32* %5, align 4
380 Instruction* getAndDependence(Value* CurrentAddress) {
381   // If 'CurrentAddress' is tainted, get the OR instruction.
382   auto* OrAddress = getOrAddress(CurrentAddress);
383   if (OrAddress == nullptr) {
384     return nullptr;
385   }
386
387   // No need to check the operands.
388   auto* AndDepInst = dyn_cast<Instruction>(OrAddress->getOperand(0));
389   assert(AndDepInst);
390   return AndDepInst;
391 }
392
393 // Given a value, if it's a tainted address, this function returns
394 // the "dependence value", which is the first operand in the AND instruction.
395 // E.g., it returns '%1' given 'CurrentAddress' is '%5'.
396 // %0 = load i32, i32* @y, align 4, !tbaa !1
397 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
398 // %1 = sext i1 %cmp to i32
399 // %2 = ptrtoint i32* @x to i32
400 // %3 = and i32 %1, 0
401 // %4 = or i32 %3, %2
402 // %5 = inttoptr i32 %4 to i32*
403 // store i32 1, i32* %5, align 4
404 Value* getDependence(Value* CurrentAddress) {
405   auto* AndInst = getAndDependence(CurrentAddress);
406   if (AndInst == nullptr) {
407     return nullptr;
408   }
409   return AndInst->getOperand(0);
410 }
411
412 // Given an address that has been tainted, returns the only condition it depends
413 // on, if any; otherwise, returns nullptr.
414 Value* getConditionDependence(Value* Address) {
415   auto* Dep = getDependence(Address);
416   if (Dep == nullptr) {
417     // 'Address' has not been dependence-tainted.
418     return nullptr;
419   }
420
421   Value* Operand = Dep;
422   while (true) {
423     auto* Inst = dyn_cast<Instruction>(Operand);
424     if (Inst == nullptr) {
425       // Non-instruction type does not have condition dependence.
426       return nullptr;
427     }
428     if (Inst->getOpcode() == Instruction::ICmp) {
429       return Inst;
430     } else {
431       if (Inst->getNumOperands() != 1) {
432         return nullptr;
433       } else {
434         Operand = Inst->getOperand(0);
435       }
436     }
437   }
438 }
439
440 // Conservatively decides whether the dependence set of 'Val1' includes the
441 // dependence set of 'Val2'. If 'ExpandSecondValue' is false, we do not expand
442 // 'Val2' and use that single value as its dependence set.
443 // If it returns true, it means the dependence set of 'Val1' includes that of
444 // 'Val2'; otherwise, it only means we cannot conclusively decide it.
445 bool dependenceSetInclusion(Value* Val1, Value* Val2,
446                             int Val1ExpandLevel = 2 * kDependenceDepth,
447                             int Val2ExpandLevel = kDependenceDepth) {
448   typedef SmallSet<Value*, 8> IncludingSet;
449   typedef SmallSet<Value*, 4> IncludedSet;
450
451   IncludingSet DepSet1;
452   IncludedSet DepSet2;
453   // Look for more depths for the including set.
454   recursivelyFindDependence(&DepSet1, Val1, false /*Insert all visited nodes*/,
455                             Val1ExpandLevel);
456   recursivelyFindDependence(&DepSet2, Val2, true /*Only insert leaf nodes*/,
457                             Val2ExpandLevel);
458
459   auto set_inclusion = [](IncludingSet FullSet, IncludedSet Subset) {
460     for (auto* Dep : Subset) {
461       if (0 == FullSet.count(Dep)) {
462         return false;
463       }
464     }
465     return true;
466   };
467   bool inclusion = set_inclusion(DepSet1, DepSet2);
468   DEBUG(dbgs() << "[dependenceSetInclusion]: " << inclusion << "\n");
469   DEBUG(dbgs() << "Including set for: " << *Val1 << "\n");
470   DEBUG(for (const auto* Dep : DepSet1) { dbgs() << "\t\t" << *Dep << "\n"; });
471   DEBUG(dbgs() << "Included set for: " << *Val2 << "\n");
472   DEBUG(for (const auto* Dep : DepSet2) { dbgs() << "\t\t" << *Dep << "\n"; });
473
474   return inclusion;
475 }
476
477 // Recursively iterates through the operands spawned from 'DepVal'. If there
478 // exists a single value that 'DepVal' only depends on, we call that value the
479 // root dependence of 'DepVal' and return it. Otherwise, return 'DepVal'.
480 Value* getRootDependence(Value* DepVal) {
481   SmallSet<Value*, 8> DepSet;
482   for (unsigned depth = kDependenceDepth; depth > 0; --depth) {
483     recursivelyFindDependence(&DepSet, DepVal, true /*Only insert leaf nodes*/,
484                               depth);
485     if (DepSet.size() == 1) {
486       return *DepSet.begin();
487     }
488     DepSet.clear();
489   }
490   return DepVal;
491 }
492
493 // This function actually taints 'DepVal' to the address to 'SI'. If the
494 // address
495 // of 'SI' already depends on whatever 'DepVal' depends on, this function
496 // doesn't do anything and returns false. Otherwise, returns true.
497 //
498 // This effect forces the store and any stores that comes later to depend on
499 // 'DepVal'. For example, we have a condition "cond", and a store instruction
500 // "s: STORE addr, val". If we want "s" (and any later store) to depend on
501 // "cond", we do the following:
502 // %conv = sext i1 %cond to i32
503 // %addrVal = ptrtoint i32* %addr to i32
504 // %andCond = and i32 conv, 0;
505 // %orAddr = or i32 %andCond, %addrVal;
506 // %NewAddr = inttoptr i32 %orAddr to i32*;
507 //
508 // This is a more concrete example:
509 // ------
510 // %0 = load i32, i32* @y, align 4, !tbaa !1
511 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
512 // %1 = sext i1 %cmp to i32
513 // %2 = ptrtoint i32* @x to i32
514 // %3 = and i32 %1, 0
515 // %4 = or i32 %3, %2
516 // %5 = inttoptr i32 %4 to i32*
517 // store i32 1, i32* %5, align 4
518 bool taintStoreAddress(StoreInst* SI, Value* DepVal,
519                        const char* calling_func = __builtin_FUNCTION()) {
520   DEBUG(dbgs() << "Called from " << calling_func << '\n');
521   IRBuilder<true, NoFolder> Builder(SI);
522   BasicBlock* BB = SI->getParent();
523   Value* Address = SI->getPointerOperand();
524   Type* TargetIntegerType =
525       IntegerType::get(Address->getContext(),
526                        BB->getModule()->getDataLayout().getPointerSizeInBits());
527
528   // Does SI's address already depends on whatever 'DepVal' depends on?
529   if (StoreAddressDependOnValue(SI, DepVal)) {
530     return false;
531   }
532
533   // Figure out if there's a root variable 'DepVal' depends on. For example, we
534   // can extract "getelementptr inbounds %struct, %struct* %0, i64 0, i32 123"
535   // to be "%struct* %0" since all other operands are constant.
536   DepVal = getRootDependence(DepVal);
537
538   // Is this already a dependence-tainted store?
539   Value* OldDep = getDependence(Address);
540   if (OldDep) {
541     // The address of 'SI' has already been tainted.  Just need to absorb the
542     // DepVal to the existing dependence in the address of SI.
543     Instruction* AndDep = getAndDependence(Address);
544     IRBuilder<true, NoFolder> Builder(AndDep);
545     Value* NewDep = nullptr;
546     if (DepVal->getType() == AndDep->getType()) {
547       NewDep = Builder.CreateAnd(OldDep, DepVal);
548     } else {
549       NewDep = Builder.CreateAnd(
550           OldDep, createCast(Builder, DepVal, TargetIntegerType));
551     }
552
553     auto* NewDepInst = dyn_cast<Instruction>(NewDep);
554
555     // Use the new AND instruction as the dependence
556     AndDep->setOperand(0, NewDep);
557     return true;
558   }
559
560   // SI's address has not been tainted. Now taint it with 'DepVal'.
561   Value* CastDepToInt = createCast(Builder, DepVal, TargetIntegerType);
562   Value* PtrToIntCast = Builder.CreatePtrToInt(Address, TargetIntegerType);
563   Value* AndDepVal =
564       Builder.CreateAnd(CastDepToInt, ConstantInt::get(TargetIntegerType, 0));
565   auto AndInst = dyn_cast<Instruction>(AndDepVal);
566   // XXX-comment: The original IR InstCombiner would change our and instruction
567   // to a select and then the back end optimize the condition out.  We attach a
568   // flag to instructions and set it here to inform the InstCombiner to not to
569   // touch this and instruction at all.
570   Value* OrAddr = Builder.CreateOr(AndDepVal, PtrToIntCast);
571   Value* NewAddr = Builder.CreateIntToPtr(OrAddr, Address->getType());
572
573   DEBUG(dbgs() << "[taintStoreAddress]\n"
574                << "Original store: " << *SI << '\n');
575   SI->setOperand(1, NewAddr);
576
577   // Debug output.
578   DEBUG(dbgs() << "\tTargetIntegerType: " << *TargetIntegerType << '\n'
579                << "\tCast dependence value to integer: " << *CastDepToInt
580                << '\n'
581                << "\tCast address to integer: " << *PtrToIntCast << '\n'
582                << "\tAnd dependence value: " << *AndDepVal << '\n'
583                << "\tOr address: " << *OrAddr << '\n'
584                << "\tCast or instruction to address: " << *NewAddr << "\n\n");
585
586   return true;
587 }
588
589 // Looks for the previous store in the if block --- 'BrBB', which makes the
590 // speculative store 'StoreToHoist' safe.
591 Value* getSpeculativeStoreInPrevBB(StoreInst* StoreToHoist, BasicBlock* BrBB) {
592   assert(StoreToHoist && "StoreToHoist must be a real store");
593
594   Value* StorePtr = StoreToHoist->getPointerOperand();
595
596   // Look for a store to the same pointer in BrBB.
597   for (BasicBlock::reverse_iterator RI = BrBB->rbegin(), RE = BrBB->rend();
598        RI != RE; ++RI) {
599     Instruction* CurI = &*RI;
600
601     StoreInst* SI = dyn_cast<StoreInst>(CurI);
602     // Found the previous store make sure it stores to the same location.
603     // XXX-update: If the previous store's original untainted address are the
604     // same as 'StorePtr', we are also good to hoist the store.
605     if (SI && (SI->getPointerOperand() == StorePtr ||
606                GetUntaintedAddress(SI->getPointerOperand()) == StorePtr)) {
607       // Found the previous store, return its value operand.
608       return SI;
609     }
610   }
611
612   assert(false &&
613          "We should not reach here since this store is safe to speculate");
614 }
615
616 // XXX-comment: Returns true if it changes the code, false otherwise (the branch
617 // condition already depends on 'DepVal'.
618 bool taintConditionalBranch(BranchInst* BI, Value* DepVal) {
619   assert(BI->isConditional());
620   auto* Cond = BI->getOperand(0);
621   if (dependenceSetInclusion(Cond, DepVal)) {
622     // The dependence/ordering is self-evident.
623     return false;
624   }
625
626   IRBuilder<true, NoFolder> Builder(BI);
627   auto* AndDep =
628       Builder.CreateAnd(DepVal, ConstantInt::get(DepVal->getType(), 0));
629   auto* TruncAndDep =
630       Builder.CreateTrunc(AndDep, IntegerType::get(DepVal->getContext(), 1));
631   auto* OrCond = Builder.CreateOr(TruncAndDep, Cond);
632   BI->setOperand(0, OrCond);
633
634   // Debug output.
635   DEBUG(dbgs() << "\tTainted branch condition:\n" << *BI->getParent());
636
637   return true;
638 }
639
640 bool ConditionalBranchDependsOnValue(BranchInst* BI, Value* DepVal) {
641   assert(BI->isConditional());
642   auto* Cond = BI->getOperand(0);
643   return dependenceSetInclusion(Cond, DepVal);
644 }
645
646 // XXX-update: For a relaxed load 'LI', find the first immediate atomic store or
647 // the first conditional branch. Returns nullptr if there's no such immediately
648 // following store/branch instructions, which we can only enforce the load with
649 // 'acquire'.
650 Instruction* findFirstStoreCondBranchInst(LoadInst* LI) {
651   // In some situations, relaxed loads can be left as is:
652   // 1. The relaxed load is used to calculate the address of the immediate
653   // following store;
654   // 2. The relaxed load is used as a condition in the immediate following
655   // condition, and there are no stores in between. This is actually quite
656   // common. E.g.,
657   // int r1 = x.load(relaxed);
658   // if (r1 != 0) {
659   //   y.store(1, relaxed);
660   // }
661   // However, in this function, we don't deal with them directly. Instead, we
662   // just find the immediate following store/condition branch and return it.
663
664   auto* BB = LI->getParent();
665   auto BE = BB->end();
666   auto BBI = BasicBlock::iterator(LI);
667   BBI++;
668   while (true) {
669     for (; BBI != BE; BBI++) {
670       auto* Inst = dyn_cast<Instruction>(&*BBI);
671       if (Inst == nullptr) {
672         continue;
673       }
674       if (Inst->getOpcode() == Instruction::Store) {
675         return Inst;
676       } else if (Inst->getOpcode() == Instruction::Br) {
677         auto* BrInst = dyn_cast<BranchInst>(Inst);
678         if (BrInst->isConditional()) {
679           return Inst;
680         } else {
681           // Reinitialize iterators with the destination of the unconditional
682           // branch.
683           BB = BrInst->getSuccessor(0);
684           BBI = BB->begin();
685           BE = BB->end();
686           break;
687         }
688       }
689     }
690     if (BBI == BE) {
691       return nullptr;
692     }
693   }
694 }
695
696 // XXX-comment: Returns whether the code has been changed.
697 bool taintMonotonicLoads(const SmallVector<LoadInst*, 1>& MonotonicLoadInsts) {
698   bool Changed = false;
699   for (auto* LI : MonotonicLoadInsts) {
700     auto* FirstInst = findFirstStoreCondBranchInst(LI);
701     if (FirstInst == nullptr) {
702       // We don't seem to be able to taint a following store/conditional branch
703       // instruction. Simply make it acquire.
704       DEBUG(dbgs() << "[RelaxedLoad]: Transformed to acquire load\n"
705                    << *LI << "\n");
706       LI->setOrdering(Acquire);
707       Changed = true;
708       continue;
709     }
710     // Taint 'FirstInst', which could be a store or a condition branch
711     // instruction.
712     if (FirstInst->getOpcode() == Instruction::Store) {
713       Changed |= taintStoreAddress(dyn_cast<StoreInst>(FirstInst), LI);
714     } else if (FirstInst->getOpcode() == Instruction::Br) {
715       Changed |= taintConditionalBranch(dyn_cast<BranchInst>(FirstInst), LI);
716     } else {
717       assert(false && "findFirstStoreCondBranchInst() should return a "
718                     "store/condition branch instruction");
719     }
720   }
721   return Changed;
722 }
723
724 // Inserts a fake conditional branch right after the instruction 'SplitInst',
725 // and the branch condition is 'Condition'. 'SplitInst' will be placed in the
726 // newly created block.
727 void AddFakeConditionalBranch(Instruction* SplitInst, Value* Condition) {
728   auto* BB = SplitInst->getParent();
729   TerminatorInst* ThenTerm = nullptr;
730   TerminatorInst* ElseTerm = nullptr;
731   SplitBlockAndInsertIfThenElse(Condition, SplitInst, &ThenTerm, &ElseTerm);
732   auto* ThenBB = ThenTerm->getParent();
733   auto* ElseBB = ElseTerm->getParent();
734   ThenBB->disableCanEliminateBlock();
735   ThenBB->disableCanEliminateBlock();
736   ThenBB->setName(BB->getName() + "Then.Fake");
737   ElseBB->setName(BB->getName() + "Else.Fake");
738   DEBUG(dbgs() << "Add fake conditional branch:\n"
739                << "Then Block:\n"
740                << *ThenBB << "Else Block:\n"
741                << *ElseBB << "\n");
742 }
743
744 // Returns true if the code is changed, and false otherwise.
745 void TaintRelaxedLoads(LoadInst* LI) {
746   IRBuilder<true, NoFolder> Builder(LI->getNextNode());
747   auto* FakeCondition = dyn_cast<Instruction>(Builder.CreateICmp(
748       CmpInst::ICMP_EQ, LI, Constant::getNullValue(LI->getType())));
749   AddFakeConditionalBranch(FakeCondition->getNextNode(), FakeCondition);
750 }
751
752 // XXX-comment: Returns whether the code has been changed.
753 bool AddsFakeConditionalBranchAfterMonotonicLoads(
754     const SmallVector<LoadInst*, 1>& MonotonicLoadInsts) {
755   bool Changed = false;
756   for (auto* LI : MonotonicLoadInsts) {
757     auto* FirstInst = findFirstStoreCondBranchInst(LI);
758     if (FirstInst != nullptr) {
759       if (FirstInst->getOpcode() == Instruction::Store) {
760         if (StoreAddressDependOnValue(dyn_cast<StoreInst>(FirstInst), LI)) {
761           continue;
762         }
763       } else if (FirstInst->getOpcode() == Instruction::Br) {
764         if (ConditionalBranchDependsOnValue(dyn_cast<BranchInst>(FirstInst),
765                                             LI)) {
766           continue;
767         }
768       } else {
769         dbgs() << "FirstInst=" << *FirstInst << "\n";
770         assert(false && "findFirstStoreCondBranchInst() should return a "
771                         "store/condition branch instruction");
772       }
773     }
774
775     // We really need to process the relaxed load now.
776     TaintRelaxedLoads(LI);
777     Changed = true;
778   }
779   return Changed;
780 }
781
782 /**** Implementations of public methods for dependence tainting ****/
783 Value* GetUntaintedAddress(Value* CurrentAddress) {
784   auto* OrAddress = getOrAddress(CurrentAddress);
785   if (OrAddress == nullptr) {
786     // Is it tainted by a select instruction?
787     auto* Inst = dyn_cast<Instruction>(CurrentAddress);
788     if (nullptr != Inst && Inst->getOpcode() == Instruction::Select) {
789       // A selection instruction.
790       if (Inst->getOperand(1) == Inst->getOperand(2)) {
791         return Inst->getOperand(1);
792       }
793     }
794
795     return CurrentAddress;
796   }
797   Value* ActualAddress = nullptr;
798
799   auto* CastToInt = dyn_cast<Instruction>(OrAddress->getOperand(1));
800   if (CastToInt && CastToInt->getOpcode() == Instruction::PtrToInt) {
801     return CastToInt->getOperand(0);
802   } else {
803     // This should be a IntToPtr constant expression.
804     ConstantExpr* PtrToIntExpr =
805         dyn_cast<ConstantExpr>(OrAddress->getOperand(1));
806     if (PtrToIntExpr && PtrToIntExpr->getOpcode() == Instruction::PtrToInt) {
807       return PtrToIntExpr->getOperand(0);
808     }
809   }
810
811   // Looks like it's not been dependence-tainted. Returns itself.
812   return CurrentAddress;
813 }
814
815 MemoryLocation GetUntaintedMemoryLocation(StoreInst* SI) {
816   AAMDNodes AATags;
817   SI->getAAMetadata(AATags);
818   const auto& DL = SI->getModule()->getDataLayout();
819   const auto* OriginalAddr = GetUntaintedAddress(SI->getPointerOperand());
820   DEBUG(if (OriginalAddr != SI->getPointerOperand()) {
821     dbgs() << "[GetUntaintedMemoryLocation]\n"
822            << "Storing address: " << *SI->getPointerOperand()
823            << "\nUntainted address: " << *OriginalAddr << "\n";
824   });
825   return MemoryLocation(OriginalAddr,
826                         DL.getTypeStoreSize(SI->getValueOperand()->getType()),
827                         AATags);
828 }
829
830 bool TaintDependenceToStore(StoreInst* SI, Value* DepVal) {
831   if (dependenceSetInclusion(SI, DepVal)) {
832     return false;
833   }
834
835   bool tainted = taintStoreAddress(SI, DepVal);
836   assert(tainted);
837   return tainted;
838 }
839
840 bool TaintDependenceToStoreAddress(StoreInst* SI, Value* DepVal) {
841   if (dependenceSetInclusion(SI->getPointerOperand(), DepVal)) {
842     return false;
843   }
844
845   bool tainted = taintStoreAddress(SI, DepVal);
846   assert(tainted);
847   return tainted;
848 }
849
850 bool CompressTaintedStore(BasicBlock* BB) {
851   // This function looks for windows of adajcent stores in 'BB' that satisfy the
852   // following condition (and then do optimization):
853   // *Addr(d1) = v1, d1 is a condition and is the only dependence the store's
854   //                 address depends on && Dep(v1) includes Dep(d1);
855   // *Addr(d2) = v2, d2 is a condition and is the only dependnece the store's
856   //                 address depends on && Dep(v2) includes Dep(d2) &&
857   //                 Dep(d2) includes Dep(d1);
858   // ...
859   // *Addr(dN) = vN, dN is a condition and is the only dependence the store's
860   //                 address depends on && Dep(dN) includes Dep(d"N-1").
861   //
862   // As a result, Dep(dN) includes [Dep(d1) V ... V Dep(d"N-1")], so we can
863   // safely transform the above to the following. In between these stores, we
864   // can omit untainted stores to the same address 'Addr' since they internally
865   // have dependence on the previous stores on the same address.
866   // =>
867   // *Addr = v1
868   // *Addr = v2
869   // *Addr(d3) = v3
870   for (auto BI = BB->begin(), BE = BB->end(); BI != BE; BI++) {
871     // Look for the first store in such a window of adajacent stores.
872     auto* FirstSI = dyn_cast<StoreInst>(&*BI);
873     if (!FirstSI) {
874       continue;
875     }
876
877     // The first store in the window must be tainted.
878     auto* UntaintedAddress = GetUntaintedAddress(FirstSI->getPointerOperand());
879     if (UntaintedAddress == FirstSI->getPointerOperand()) {
880       continue;
881     }
882
883     // The first store's address must directly depend on and only depend on a
884     // condition.
885     auto* FirstSIDepCond = getConditionDependence(FirstSI->getPointerOperand());
886     if (nullptr == FirstSIDepCond) {
887       continue;
888     }
889
890     // Dep(first store's storing value) includes Dep(tainted dependence).
891     if (!dependenceSetInclusion(FirstSI->getValueOperand(), FirstSIDepCond)) {
892       continue;
893     }
894
895     // Look for subsequent stores to the same address that satisfy the condition
896     // of "compressing the dependence".
897     SmallVector<StoreInst*, 8> AdajacentStores;
898     AdajacentStores.push_back(FirstSI);
899     auto BII = BasicBlock::iterator(FirstSI);
900     for (BII++; BII != BE; BII++) {
901       auto* CurrSI = dyn_cast<StoreInst>(&*BII);
902       if (!CurrSI) {
903         if (BII->mayHaveSideEffects()) {
904           // Be conservative. Instructions with side effects are similar to
905           // stores.
906           break;
907         }
908         continue;
909       }
910
911       auto* OrigAddress = GetUntaintedAddress(CurrSI->getPointerOperand());
912       auto* CurrSIDepCond = getConditionDependence(CurrSI->getPointerOperand());
913       // All other stores must satisfy either:
914       // A. 'CurrSI' is an untainted store to the same address, or
915       // B. the combination of the following 5 subconditions:
916       // 1. Tainted;
917       // 2. Untainted address is the same as the group's address;
918       // 3. The address is tainted with a sole value which is a condition;
919       // 4. The storing value depends on the condition in 3.
920       // 5. The condition in 3 depends on the previous stores dependence
921       // condition.
922
923       // Condition A. Should ignore this store directly.
924       if (OrigAddress == CurrSI->getPointerOperand() &&
925           OrigAddress == UntaintedAddress) {
926         continue;
927       }
928       // Check condition B.
929       Value* Cond = nullptr;
930       if (OrigAddress == CurrSI->getPointerOperand() ||
931           OrigAddress != UntaintedAddress || CurrSIDepCond == nullptr ||
932           !dependenceSetInclusion(CurrSI->getValueOperand(), CurrSIDepCond)) {
933         // Check condition 1, 2, 3 & 4.
934         break;
935       }
936
937       // Check condition 5.
938       StoreInst* PrevSI = AdajacentStores[AdajacentStores.size() - 1];
939       auto* PrevSIDepCond = getConditionDependence(PrevSI->getPointerOperand());
940       assert(PrevSIDepCond &&
941              "Store in the group must already depend on a condtion");
942       if (!dependenceSetInclusion(CurrSIDepCond, PrevSIDepCond)) {
943         break;
944       }
945
946       AdajacentStores.push_back(CurrSI);
947     }
948
949     if (AdajacentStores.size() == 1) {
950       // The outer loop should keep looking from the next store.
951       continue;
952     }
953
954     // Now we have such a group of tainted stores to the same address.
955     DEBUG(dbgs() << "[CompressTaintedStore]\n");
956     DEBUG(dbgs() << "Original BB\n");
957     DEBUG(dbgs() << *BB << '\n');
958     auto* LastSI = AdajacentStores[AdajacentStores.size() - 1];
959     for (unsigned i = 0; i < AdajacentStores.size() - 1; ++i) {
960       auto* SI = AdajacentStores[i];
961
962       // Use the original address for stores before the last one.
963       SI->setOperand(1, UntaintedAddress);
964
965       DEBUG(dbgs() << "Store address has been reversed: " << *SI << '\n';);
966     }
967     // XXX-comment: Try to make the last store use fewer registers.
968     // If LastSI's storing value is a select based on the condition with which
969     // its address is tainted, transform the tainted address to a select
970     // instruction, as follows:
971     // r1 = Select Cond ? A : B
972     // r2 = Cond & 0
973     // r3 = Addr | r2
974     // *r3 = r1
975     // ==>
976     // r1 = Select Cond ? A : B
977     // r2 = Select Cond ? Addr : Addr
978     // *r2 = r1
979     // The idea is that both Select instructions depend on the same condition,
980     // so hopefully the backend can generate two cmov instructions for them (and
981     // this saves the number of registers needed).
982     auto* LastSIDep = getConditionDependence(LastSI->getPointerOperand());
983     auto* LastSIValue = dyn_cast<Instruction>(LastSI->getValueOperand());
984     if (LastSIValue && LastSIValue->getOpcode() == Instruction::Select &&
985         LastSIValue->getOperand(0) == LastSIDep) {
986       // XXX-comment: Maybe it's better for us to just leave it as an and/or
987       // dependence pattern.
988       //      /*
989       IRBuilder<true, NoFolder> Builder(LastSI);
990       auto* Address =
991           Builder.CreateSelect(LastSIDep, UntaintedAddress, UntaintedAddress);
992       LastSI->setOperand(1, Address);
993       DEBUG(dbgs() << "The last store becomes :" << *LastSI << "\n\n";);
994       //      */
995     }
996   }
997
998   return true;
999 }
1000
1001 bool PassDependenceToStore(Value* OldAddress, StoreInst* NewStore) {
1002   Value* OldDep = getDependence(OldAddress);
1003   // Return false when there's no dependence to pass from the OldAddress.
1004   if (!OldDep) {
1005     return false;
1006   }
1007
1008   // No need to pass the dependence to NewStore's address if it already depends
1009   // on whatever 'OldAddress' depends on.
1010   if (StoreAddressDependOnValue(NewStore, OldDep)) {
1011     return false;
1012   }
1013   return taintStoreAddress(NewStore, OldAddress);
1014 }
1015
1016 SmallSet<Value*, 8> FindDependence(Value* Val) {
1017   SmallSet<Value*, 8> DepSet;
1018   recursivelyFindDependence(&DepSet, Val, true /*Only insert leaf nodes*/);
1019   return DepSet;
1020 }
1021
1022 bool StoreAddressDependOnValue(StoreInst* SI, Value* DepVal) {
1023   return dependenceSetInclusion(SI->getPointerOperand(), DepVal);
1024 }
1025
1026 bool StoreDependOnValue(StoreInst* SI, Value* Dep) {
1027   return dependenceSetInclusion(SI, Dep);
1028 }
1029
1030 } // namespace
1031
1032
1033
1034 bool CodeGenPrepare::runOnFunction(Function &F) {
1035   // XXX-comment: Delay dealing with relaxed loads in this function to avoid
1036   // further changes done by other passes (e.g., SimplifyCFG).
1037
1038   // Collect all the relaxed loads.
1039   SmallVector<LoadInst*, 1> MonotonicLoadInsts;
1040   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
1041     if (I->isAtomic()) {
1042       switch (I->getOpcode()) {
1043         case Instruction::Load: {
1044           auto* LI = dyn_cast<LoadInst>(&*I);
1045           if (LI->getOrdering() == Monotonic) {
1046             MonotonicLoadInsts.push_back(LI);
1047           }
1048           break;
1049         }
1050         default: {
1051           break;
1052         }
1053       }
1054     }
1055   }
1056   bool EverMadeChange =
1057       AddsFakeConditionalBranchAfterMonotonicLoads(MonotonicLoadInsts);
1058
1059   if (skipOptnoneFunction(F))
1060     return false;
1061
1062   DL = &F.getParent()->getDataLayout();
1063
1064   // Clear per function information.
1065   InsertedInsts.clear();
1066   PromotedInsts.clear();
1067
1068   ModifiedDT = false;
1069   if (TM)
1070     TLI = TM->getSubtargetImpl(F)->getTargetLowering();
1071   TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1072   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1073   OptSize = F.optForSize();
1074
1075   /// This optimization identifies DIV instructions that can be
1076   /// profitably bypassed and carried out with a shorter, faster divide.
1077   if (!OptSize && TLI && TLI->isSlowDivBypassed()) {
1078     const DenseMap<unsigned int, unsigned int> &BypassWidths =
1079        TLI->getBypassSlowDivWidths();
1080     BasicBlock* BB = &*F.begin();
1081     while (BB != nullptr) {
1082       // bypassSlowDivision may create new BBs, but we don't want to reapply the
1083       // optimization to those blocks.
1084       BasicBlock* Next = BB->getNextNode();
1085       EverMadeChange |= bypassSlowDivision(BB, BypassWidths);
1086       BB = Next;
1087     }
1088   }
1089
1090   // Eliminate blocks that contain only PHI nodes and an
1091   // unconditional branch.
1092   EverMadeChange |= eliminateMostlyEmptyBlocks(F);
1093
1094   // llvm.dbg.value is far away from the value then iSel may not be able
1095   // handle it properly. iSel will drop llvm.dbg.value if it can not
1096   // find a node corresponding to the value.
1097   EverMadeChange |= placeDbgValues(F);
1098
1099   // If there is a mask, compare against zero, and branch that can be combined
1100   // into a single target instruction, push the mask and compare into branch
1101   // users. Do this before OptimizeBlock -> OptimizeInst ->
1102   // OptimizeCmpExpression, which perturbs the pattern being searched for.
1103   if (!DisableBranchOpts) {
1104     EverMadeChange |= sinkAndCmp(F);
1105     EverMadeChange |= splitBranchCondition(F);
1106   }
1107
1108   bool MadeChange = true;
1109   while (MadeChange) {
1110     MadeChange = false;
1111     for (Function::iterator I = F.begin(); I != F.end(); ) {
1112       BasicBlock *BB = &*I++;
1113       bool ModifiedDTOnIteration = false;
1114       MadeChange |= optimizeBlock(*BB, ModifiedDTOnIteration);
1115
1116       // Restart BB iteration if the dominator tree of the Function was changed
1117       if (ModifiedDTOnIteration)
1118         break;
1119     }
1120     EverMadeChange |= MadeChange;
1121   }
1122
1123   SunkAddrs.clear();
1124
1125   if (!DisableBranchOpts) {
1126     MadeChange = false;
1127     SmallPtrSet<BasicBlock*, 8> WorkList;
1128     for (BasicBlock &BB : F) {
1129       SmallVector<BasicBlock *, 2> Successors(succ_begin(&BB), succ_end(&BB));
1130       MadeChange |= ConstantFoldTerminator(&BB, true);
1131       if (!MadeChange) continue;
1132
1133       for (SmallVectorImpl<BasicBlock*>::iterator
1134              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
1135         if (pred_begin(*II) == pred_end(*II))
1136           WorkList.insert(*II);
1137     }
1138
1139     // Delete the dead blocks and any of their dead successors.
1140     MadeChange |= !WorkList.empty();
1141     while (!WorkList.empty()) {
1142       BasicBlock *BB = *WorkList.begin();
1143       WorkList.erase(BB);
1144       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
1145
1146       DeleteDeadBlock(BB);
1147
1148       for (SmallVectorImpl<BasicBlock*>::iterator
1149              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
1150         if (pred_begin(*II) == pred_end(*II))
1151           WorkList.insert(*II);
1152     }
1153
1154     // Merge pairs of basic blocks with unconditional branches, connected by
1155     // a single edge.
1156     if (EverMadeChange || MadeChange)
1157       MadeChange |= eliminateFallThrough(F);
1158
1159     EverMadeChange |= MadeChange;
1160   }
1161
1162   if (!DisableGCOpts) {
1163     SmallVector<Instruction *, 2> Statepoints;
1164     for (BasicBlock &BB : F)
1165       for (Instruction &I : BB)
1166         if (isStatepoint(I))
1167           Statepoints.push_back(&I);
1168     for (auto &I : Statepoints)
1169       EverMadeChange |= simplifyOffsetableRelocate(*I);
1170   }
1171
1172   return EverMadeChange;
1173 }
1174
1175 /// Merge basic blocks which are connected by a single edge, where one of the
1176 /// basic blocks has a single successor pointing to the other basic block,
1177 /// which has a single predecessor.
1178 bool CodeGenPrepare::eliminateFallThrough(Function &F) {
1179   bool Changed = false;
1180   // Scan all of the blocks in the function, except for the entry block.
1181   for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
1182     BasicBlock *BB = &*I++;
1183     // If the destination block has a single pred, then this is a trivial
1184     // edge, just collapse it.
1185     BasicBlock *SinglePred = BB->getSinglePredecessor();
1186
1187     // Don't merge if BB's address is taken.
1188     if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
1189
1190     BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
1191     if (Term && !Term->isConditional()) {
1192       Changed = true;
1193       DEBUG(dbgs() << "To merge:\n"<< *SinglePred << "\n\n\n");
1194       // Remember if SinglePred was the entry block of the function.
1195       // If so, we will need to move BB back to the entry position.
1196       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
1197       MergeBasicBlockIntoOnlyPred(BB, nullptr);
1198
1199       if (isEntry && BB != &BB->getParent()->getEntryBlock())
1200         BB->moveBefore(&BB->getParent()->getEntryBlock());
1201
1202       // We have erased a block. Update the iterator.
1203       I = BB->getIterator();
1204     }
1205   }
1206   return Changed;
1207 }
1208
1209 /// Eliminate blocks that contain only PHI nodes, debug info directives, and an
1210 /// unconditional branch. Passes before isel (e.g. LSR/loopsimplify) often split
1211 /// edges in ways that are non-optimal for isel. Start by eliminating these
1212 /// blocks so we can split them the way we want them.
1213 bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F) {
1214   bool MadeChange = false;
1215   // Note that this intentionally skips the entry block.
1216   for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
1217     BasicBlock *BB = &*I++;
1218     // XXX-disabled: Do not eliminate the added fake basic block.
1219     if (!BB->getCanEliminateBlock()) {
1220       continue;
1221     }
1222
1223     // If this block doesn't end with an uncond branch, ignore it.
1224     BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
1225     if (!BI || !BI->isUnconditional())
1226       continue;
1227
1228     // If the instruction before the branch (skipping debug info) isn't a phi
1229     // node, then other stuff is happening here.
1230     BasicBlock::iterator BBI = BI->getIterator();
1231     if (BBI != BB->begin()) {
1232       --BBI;
1233       while (isa<DbgInfoIntrinsic>(BBI)) {
1234         if (BBI == BB->begin())
1235           break;
1236         --BBI;
1237       }
1238       if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
1239         continue;
1240     }
1241
1242     // Do not break infinite loops.
1243     BasicBlock *DestBB = BI->getSuccessor(0);
1244     if (DestBB == BB)
1245       continue;
1246
1247     if (!canMergeBlocks(BB, DestBB))
1248       continue;
1249
1250     eliminateMostlyEmptyBlock(BB);
1251     MadeChange = true;
1252   }
1253   return MadeChange;
1254 }
1255
1256 /// Return true if we can merge BB into DestBB if there is a single
1257 /// unconditional branch between them, and BB contains no other non-phi
1258 /// instructions.
1259 bool CodeGenPrepare::canMergeBlocks(const BasicBlock *BB,
1260                                     const BasicBlock *DestBB) const {
1261   // We only want to eliminate blocks whose phi nodes are used by phi nodes in
1262   // the successor.  If there are more complex condition (e.g. preheaders),
1263   // don't mess around with them.
1264   BasicBlock::const_iterator BBI = BB->begin();
1265   while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
1266     for (const User *U : PN->users()) {
1267       const Instruction *UI = cast<Instruction>(U);
1268       if (UI->getParent() != DestBB || !isa<PHINode>(UI))
1269         return false;
1270       // If User is inside DestBB block and it is a PHINode then check
1271       // incoming value. If incoming value is not from BB then this is
1272       // a complex condition (e.g. preheaders) we want to avoid here.
1273       if (UI->getParent() == DestBB) {
1274         if (const PHINode *UPN = dyn_cast<PHINode>(UI))
1275           for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) {
1276             Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I));
1277             if (Insn && Insn->getParent() == BB &&
1278                 Insn->getParent() != UPN->getIncomingBlock(I))
1279               return false;
1280           }
1281       }
1282     }
1283   }
1284
1285   // If BB and DestBB contain any common predecessors, then the phi nodes in BB
1286   // and DestBB may have conflicting incoming values for the block.  If so, we
1287   // can't merge the block.
1288   const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin());
1289   if (!DestBBPN) return true;  // no conflict.
1290
1291   // Collect the preds of BB.
1292   SmallPtrSet<const BasicBlock*, 16> BBPreds;
1293   if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
1294     // It is faster to get preds from a PHI than with pred_iterator.
1295     for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1296       BBPreds.insert(BBPN->getIncomingBlock(i));
1297   } else {
1298     BBPreds.insert(pred_begin(BB), pred_end(BB));
1299   }
1300
1301   // Walk the preds of DestBB.
1302   for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) {
1303     BasicBlock *Pred = DestBBPN->getIncomingBlock(i);
1304     if (BBPreds.count(Pred)) {   // Common predecessor?
1305       BBI = DestBB->begin();
1306       while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
1307         const Value *V1 = PN->getIncomingValueForBlock(Pred);
1308         const Value *V2 = PN->getIncomingValueForBlock(BB);
1309
1310         // If V2 is a phi node in BB, look up what the mapped value will be.
1311         if (const PHINode *V2PN = dyn_cast<PHINode>(V2))
1312           if (V2PN->getParent() == BB)
1313             V2 = V2PN->getIncomingValueForBlock(Pred);
1314
1315         // If there is a conflict, bail out.
1316         if (V1 != V2) return false;
1317       }
1318     }
1319   }
1320
1321   return true;
1322 }
1323
1324
1325 /// Eliminate a basic block that has only phi's and an unconditional branch in
1326 /// it.
1327 void CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
1328   BranchInst *BI = cast<BranchInst>(BB->getTerminator());
1329   BasicBlock *DestBB = BI->getSuccessor(0);
1330
1331   DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB);
1332
1333   // If the destination block has a single pred, then this is a trivial edge,
1334   // just collapse it.
1335   if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
1336     if (SinglePred != DestBB) {
1337       // Remember if SinglePred was the entry block of the function.  If so, we
1338       // will need to move BB back to the entry position.
1339       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
1340       MergeBasicBlockIntoOnlyPred(DestBB, nullptr);
1341
1342       if (isEntry && BB != &BB->getParent()->getEntryBlock())
1343         BB->moveBefore(&BB->getParent()->getEntryBlock());
1344
1345       DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
1346       return;
1347     }
1348   }
1349
1350   // Otherwise, we have multiple predecessors of BB.  Update the PHIs in DestBB
1351   // to handle the new incoming edges it is about to have.
1352   PHINode *PN;
1353   for (BasicBlock::iterator BBI = DestBB->begin();
1354        (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
1355     // Remove the incoming value for BB, and remember it.
1356     Value *InVal = PN->removeIncomingValue(BB, false);
1357
1358     // Two options: either the InVal is a phi node defined in BB or it is some
1359     // value that dominates BB.
1360     PHINode *InValPhi = dyn_cast<PHINode>(InVal);
1361     if (InValPhi && InValPhi->getParent() == BB) {
1362       // Add all of the input values of the input PHI as inputs of this phi.
1363       for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i)
1364         PN->addIncoming(InValPhi->getIncomingValue(i),
1365                         InValPhi->getIncomingBlock(i));
1366     } else {
1367       // Otherwise, add one instance of the dominating value for each edge that
1368       // we will be adding.
1369       if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
1370         for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1371           PN->addIncoming(InVal, BBPN->getIncomingBlock(i));
1372       } else {
1373         for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
1374           PN->addIncoming(InVal, *PI);
1375       }
1376     }
1377   }
1378
1379   // The PHIs are now updated, change everything that refers to BB to use
1380   // DestBB and remove BB.
1381   BB->replaceAllUsesWith(DestBB);
1382   BB->eraseFromParent();
1383   ++NumBlocksElim;
1384
1385   DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
1386 }
1387
1388 // Computes a map of base pointer relocation instructions to corresponding
1389 // derived pointer relocation instructions given a vector of all relocate calls
1390 static void computeBaseDerivedRelocateMap(
1391     const SmallVectorImpl<GCRelocateInst *> &AllRelocateCalls,
1392     DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>>
1393         &RelocateInstMap) {
1394   // Collect information in two maps: one primarily for locating the base object
1395   // while filling the second map; the second map is the final structure holding
1396   // a mapping between Base and corresponding Derived relocate calls
1397   DenseMap<std::pair<unsigned, unsigned>, GCRelocateInst *> RelocateIdxMap;
1398   for (auto *ThisRelocate : AllRelocateCalls) {
1399     auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1400                             ThisRelocate->getDerivedPtrIndex());
1401     RelocateIdxMap.insert(std::make_pair(K, ThisRelocate));
1402   }
1403   for (auto &Item : RelocateIdxMap) {
1404     std::pair<unsigned, unsigned> Key = Item.first;
1405     if (Key.first == Key.second)
1406       // Base relocation: nothing to insert
1407       continue;
1408
1409     GCRelocateInst *I = Item.second;
1410     auto BaseKey = std::make_pair(Key.first, Key.first);
1411
1412     // We're iterating over RelocateIdxMap so we cannot modify it.
1413     auto MaybeBase = RelocateIdxMap.find(BaseKey);
1414     if (MaybeBase == RelocateIdxMap.end())
1415       // TODO: We might want to insert a new base object relocate and gep off
1416       // that, if there are enough derived object relocates.
1417       continue;
1418
1419     RelocateInstMap[MaybeBase->second].push_back(I);
1420   }
1421 }
1422
1423 // Accepts a GEP and extracts the operands into a vector provided they're all
1424 // small integer constants
1425 static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP,
1426                                           SmallVectorImpl<Value *> &OffsetV) {
1427   for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
1428     // Only accept small constant integer operands
1429     auto Op = dyn_cast<ConstantInt>(GEP->getOperand(i));
1430     if (!Op || Op->getZExtValue() > 20)
1431       return false;
1432   }
1433
1434   for (unsigned i = 1; i < GEP->getNumOperands(); i++)
1435     OffsetV.push_back(GEP->getOperand(i));
1436   return true;
1437 }
1438
1439 // Takes a RelocatedBase (base pointer relocation instruction) and Targets to
1440 // replace, computes a replacement, and affects it.
1441 static bool
1442 simplifyRelocatesOffABase(GCRelocateInst *RelocatedBase,
1443                           const SmallVectorImpl<GCRelocateInst *> &Targets) {
1444   bool MadeChange = false;
1445   for (GCRelocateInst *ToReplace : Targets) {
1446     assert(ToReplace->getBasePtrIndex() == RelocatedBase->getBasePtrIndex() &&
1447            "Not relocating a derived object of the original base object");
1448     if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1449       // A duplicate relocate call. TODO: coalesce duplicates.
1450       continue;
1451     }
1452
1453     if (RelocatedBase->getParent() != ToReplace->getParent()) {
1454       // Base and derived relocates are in different basic blocks.
1455       // In this case transform is only valid when base dominates derived
1456       // relocate. However it would be too expensive to check dominance
1457       // for each such relocate, so we skip the whole transformation.
1458       continue;
1459     }
1460
1461     Value *Base = ToReplace->getBasePtr();
1462     auto Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr());
1463     if (!Derived || Derived->getPointerOperand() != Base)
1464       continue;
1465
1466     SmallVector<Value *, 2> OffsetV;
1467     if (!getGEPSmallConstantIntOffsetV(Derived, OffsetV))
1468       continue;
1469
1470     // Create a Builder and replace the target callsite with a gep
1471     assert(RelocatedBase->getNextNode() && "Should always have one since it's not a terminator");
1472
1473     // Insert after RelocatedBase
1474     IRBuilder<> Builder(RelocatedBase->getNextNode());
1475     Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
1476
1477     // If gc_relocate does not match the actual type, cast it to the right type.
1478     // In theory, there must be a bitcast after gc_relocate if the type does not
1479     // match, and we should reuse it to get the derived pointer. But it could be
1480     // cases like this:
1481     // bb1:
1482     //  ...
1483     //  %g1 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...)
1484     //  br label %merge
1485     //
1486     // bb2:
1487     //  ...
1488     //  %g2 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...)
1489     //  br label %merge
1490     //
1491     // merge:
1492     //  %p1 = phi i8 addrspace(1)* [ %g1, %bb1 ], [ %g2, %bb2 ]
1493     //  %cast = bitcast i8 addrspace(1)* %p1 in to i32 addrspace(1)*
1494     //
1495     // In this case, we can not find the bitcast any more. So we insert a new bitcast
1496     // no matter there is already one or not. In this way, we can handle all cases, and
1497     // the extra bitcast should be optimized away in later passes.
1498     Value *ActualRelocatedBase = RelocatedBase;
1499     if (RelocatedBase->getType() != Base->getType()) {
1500       ActualRelocatedBase =
1501           Builder.CreateBitCast(RelocatedBase, Base->getType());
1502     }
1503     Value *Replacement = Builder.CreateGEP(
1504         Derived->getSourceElementType(), ActualRelocatedBase, makeArrayRef(OffsetV));
1505     Replacement->takeName(ToReplace);
1506     // If the newly generated derived pointer's type does not match the original derived
1507     // pointer's type, cast the new derived pointer to match it. Same reasoning as above.
1508     Value *ActualReplacement = Replacement;
1509     if (Replacement->getType() != ToReplace->getType()) {
1510       ActualReplacement =
1511           Builder.CreateBitCast(Replacement, ToReplace->getType());
1512     }
1513     ToReplace->replaceAllUsesWith(ActualReplacement);
1514     ToReplace->eraseFromParent();
1515
1516     MadeChange = true;
1517   }
1518   return MadeChange;
1519 }
1520
1521 // Turns this:
1522 //
1523 // %base = ...
1524 // %ptr = gep %base + 15
1525 // %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
1526 // %base' = relocate(%tok, i32 4, i32 4)
1527 // %ptr' = relocate(%tok, i32 4, i32 5)
1528 // %val = load %ptr'
1529 //
1530 // into this:
1531 //
1532 // %base = ...
1533 // %ptr = gep %base + 15
1534 // %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
1535 // %base' = gc.relocate(%tok, i32 4, i32 4)
1536 // %ptr' = gep %base' + 15
1537 // %val = load %ptr'
1538 bool CodeGenPrepare::simplifyOffsetableRelocate(Instruction &I) {
1539   bool MadeChange = false;
1540   SmallVector<GCRelocateInst *, 2> AllRelocateCalls;
1541
1542   for (auto *U : I.users())
1543     if (GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U))
1544       // Collect all the relocate calls associated with a statepoint
1545       AllRelocateCalls.push_back(Relocate);
1546
1547   // We need atleast one base pointer relocation + one derived pointer
1548   // relocation to mangle
1549   if (AllRelocateCalls.size() < 2)
1550     return false;
1551
1552   // RelocateInstMap is a mapping from the base relocate instruction to the
1553   // corresponding derived relocate instructions
1554   DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>> RelocateInstMap;
1555   computeBaseDerivedRelocateMap(AllRelocateCalls, RelocateInstMap);
1556   if (RelocateInstMap.empty())
1557     return false;
1558
1559   for (auto &Item : RelocateInstMap)
1560     // Item.first is the RelocatedBase to offset against
1561     // Item.second is the vector of Targets to replace
1562     MadeChange = simplifyRelocatesOffABase(Item.first, Item.second);
1563   return MadeChange;
1564 }
1565
1566 /// SinkCast - Sink the specified cast instruction into its user blocks
1567 static bool SinkCast(CastInst *CI) {
1568   BasicBlock *DefBB = CI->getParent();
1569
1570   /// InsertedCasts - Only insert a cast in each block once.
1571   DenseMap<BasicBlock*, CastInst*> InsertedCasts;
1572
1573   bool MadeChange = false;
1574   for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
1575        UI != E; ) {
1576     Use &TheUse = UI.getUse();
1577     Instruction *User = cast<Instruction>(*UI);
1578
1579     // Figure out which BB this cast is used in.  For PHI's this is the
1580     // appropriate predecessor block.
1581     BasicBlock *UserBB = User->getParent();
1582     if (PHINode *PN = dyn_cast<PHINode>(User)) {
1583       UserBB = PN->getIncomingBlock(TheUse);
1584     }
1585
1586     // Preincrement use iterator so we don't invalidate it.
1587     ++UI;
1588
1589     // If the block selected to receive the cast is an EH pad that does not
1590     // allow non-PHI instructions before the terminator, we can't sink the
1591     // cast.
1592     if (UserBB->getTerminator()->isEHPad())
1593       continue;
1594
1595     // If this user is in the same block as the cast, don't change the cast.
1596     if (UserBB == DefBB) continue;
1597
1598     // If we have already inserted a cast into this block, use it.
1599     CastInst *&InsertedCast = InsertedCasts[UserBB];
1600
1601     if (!InsertedCast) {
1602       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1603       assert(InsertPt != UserBB->end());
1604       InsertedCast = CastInst::Create(CI->getOpcode(), CI->getOperand(0),
1605                                       CI->getType(), "", &*InsertPt);
1606     }
1607
1608     // Replace a use of the cast with a use of the new cast.
1609     TheUse = InsertedCast;
1610     MadeChange = true;
1611     ++NumCastUses;
1612   }
1613
1614   // If we removed all uses, nuke the cast.
1615   if (CI->use_empty()) {
1616     CI->eraseFromParent();
1617     MadeChange = true;
1618   }
1619
1620   return MadeChange;
1621 }
1622
1623 /// If the specified cast instruction is a noop copy (e.g. it's casting from
1624 /// one pointer type to another, i32->i8 on PPC), sink it into user blocks to
1625 /// reduce the number of virtual registers that must be created and coalesced.
1626 ///
1627 /// Return true if any changes are made.
1628 ///
1629 static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI,
1630                                        const DataLayout &DL) {
1631   // If this is a noop copy,
1632   EVT SrcVT = TLI.getValueType(DL, CI->getOperand(0)->getType());
1633   EVT DstVT = TLI.getValueType(DL, CI->getType());
1634
1635   // This is an fp<->int conversion?
1636   if (SrcVT.isInteger() != DstVT.isInteger())
1637     return false;
1638
1639   // If this is an extension, it will be a zero or sign extension, which
1640   // isn't a noop.
1641   if (SrcVT.bitsLT(DstVT)) return false;
1642
1643   // If these values will be promoted, find out what they will be promoted
1644   // to.  This helps us consider truncates on PPC as noop copies when they
1645   // are.
1646   if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
1647       TargetLowering::TypePromoteInteger)
1648     SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
1649   if (TLI.getTypeAction(CI->getContext(), DstVT) ==
1650       TargetLowering::TypePromoteInteger)
1651     DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
1652
1653   // If, after promotion, these are the same types, this is a noop copy.
1654   if (SrcVT != DstVT)
1655     return false;
1656
1657   return SinkCast(CI);
1658 }
1659
1660 /// Try to combine CI into a call to the llvm.uadd.with.overflow intrinsic if
1661 /// possible.
1662 ///
1663 /// Return true if any changes were made.
1664 static bool CombineUAddWithOverflow(CmpInst *CI) {
1665   Value *A, *B;
1666   Instruction *AddI;
1667   if (!match(CI,
1668              m_UAddWithOverflow(m_Value(A), m_Value(B), m_Instruction(AddI))))
1669     return false;
1670
1671   Type *Ty = AddI->getType();
1672   if (!isa<IntegerType>(Ty))
1673     return false;
1674
1675   // We don't want to move around uses of condition values this late, so we we
1676   // check if it is legal to create the call to the intrinsic in the basic
1677   // block containing the icmp:
1678
1679   if (AddI->getParent() != CI->getParent() && !AddI->hasOneUse())
1680     return false;
1681
1682 #ifndef NDEBUG
1683   // Someday m_UAddWithOverflow may get smarter, but this is a safe assumption
1684   // for now:
1685   if (AddI->hasOneUse())
1686     assert(*AddI->user_begin() == CI && "expected!");
1687 #endif
1688
1689   Module *M = CI->getModule();
1690   Value *F = Intrinsic::getDeclaration(M, Intrinsic::uadd_with_overflow, Ty);
1691
1692   auto *InsertPt = AddI->hasOneUse() ? CI : AddI;
1693
1694   auto *UAddWithOverflow =
1695       CallInst::Create(F, {A, B}, "uadd.overflow", InsertPt);
1696   auto *UAdd = ExtractValueInst::Create(UAddWithOverflow, 0, "uadd", InsertPt);
1697   auto *Overflow =
1698       ExtractValueInst::Create(UAddWithOverflow, 1, "overflow", InsertPt);
1699
1700   CI->replaceAllUsesWith(Overflow);
1701   AddI->replaceAllUsesWith(UAdd);
1702   CI->eraseFromParent();
1703   AddI->eraseFromParent();
1704   return true;
1705 }
1706
1707 /// Sink the given CmpInst into user blocks to reduce the number of virtual
1708 /// registers that must be created and coalesced. This is a clear win except on
1709 /// targets with multiple condition code registers (PowerPC), where it might
1710 /// lose; some adjustment may be wanted there.
1711 ///
1712 /// Return true if any changes are made.
1713 static bool SinkCmpExpression(CmpInst *CI) {
1714   BasicBlock *DefBB = CI->getParent();
1715
1716   /// Only insert a cmp in each block once.
1717   DenseMap<BasicBlock*, CmpInst*> InsertedCmps;
1718
1719   bool MadeChange = false;
1720   for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
1721        UI != E; ) {
1722     Use &TheUse = UI.getUse();
1723     Instruction *User = cast<Instruction>(*UI);
1724
1725     // Preincrement use iterator so we don't invalidate it.
1726     ++UI;
1727
1728     // Don't bother for PHI nodes.
1729     if (isa<PHINode>(User))
1730       continue;
1731
1732     // Figure out which BB this cmp is used in.
1733     BasicBlock *UserBB = User->getParent();
1734
1735     // If this user is in the same block as the cmp, don't change the cmp.
1736     if (UserBB == DefBB) continue;
1737
1738     // If we have already inserted a cmp into this block, use it.
1739     CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1740
1741     if (!InsertedCmp) {
1742       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1743       assert(InsertPt != UserBB->end());
1744       InsertedCmp =
1745           CmpInst::Create(CI->getOpcode(), CI->getPredicate(),
1746                           CI->getOperand(0), CI->getOperand(1), "", &*InsertPt);
1747     }
1748
1749     // Replace a use of the cmp with a use of the new cmp.
1750     TheUse = InsertedCmp;
1751     MadeChange = true;
1752     ++NumCmpUses;
1753   }
1754
1755   // If we removed all uses, nuke the cmp.
1756   if (CI->use_empty()) {
1757     CI->eraseFromParent();
1758     MadeChange = true;
1759   }
1760
1761   return MadeChange;
1762 }
1763
1764 static bool OptimizeCmpExpression(CmpInst *CI) {
1765   if (SinkCmpExpression(CI))
1766     return true;
1767
1768   if (CombineUAddWithOverflow(CI))
1769     return true;
1770
1771   return false;
1772 }
1773
1774 /// Check if the candidates could be combined with a shift instruction, which
1775 /// includes:
1776 /// 1. Truncate instruction
1777 /// 2. And instruction and the imm is a mask of the low bits:
1778 /// imm & (imm+1) == 0
1779 static bool isExtractBitsCandidateUse(Instruction *User) {
1780   if (!isa<TruncInst>(User)) {
1781     if (User->getOpcode() != Instruction::And ||
1782         !isa<ConstantInt>(User->getOperand(1)))
1783       return false;
1784
1785     const APInt &Cimm = cast<ConstantInt>(User->getOperand(1))->getValue();
1786
1787     if ((Cimm & (Cimm + 1)).getBoolValue())
1788       return false;
1789   }
1790   return true;
1791 }
1792
1793 /// Sink both shift and truncate instruction to the use of truncate's BB.
1794 static bool
1795 SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI,
1796                      DenseMap<BasicBlock *, BinaryOperator *> &InsertedShifts,
1797                      const TargetLowering &TLI, const DataLayout &DL) {
1798   BasicBlock *UserBB = User->getParent();
1799   DenseMap<BasicBlock *, CastInst *> InsertedTruncs;
1800   TruncInst *TruncI = dyn_cast<TruncInst>(User);
1801   bool MadeChange = false;
1802
1803   for (Value::user_iterator TruncUI = TruncI->user_begin(),
1804                             TruncE = TruncI->user_end();
1805        TruncUI != TruncE;) {
1806
1807     Use &TruncTheUse = TruncUI.getUse();
1808     Instruction *TruncUser = cast<Instruction>(*TruncUI);
1809     // Preincrement use iterator so we don't invalidate it.
1810
1811     ++TruncUI;
1812
1813     int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode());
1814     if (!ISDOpcode)
1815       continue;
1816
1817     // If the use is actually a legal node, there will not be an
1818     // implicit truncate.
1819     // FIXME: always querying the result type is just an
1820     // approximation; some nodes' legality is determined by the
1821     // operand or other means. There's no good way to find out though.
1822     if (TLI.isOperationLegalOrCustom(
1823             ISDOpcode, TLI.getValueType(DL, TruncUser->getType(), true)))
1824       continue;
1825
1826     // Don't bother for PHI nodes.
1827     if (isa<PHINode>(TruncUser))
1828       continue;
1829
1830     BasicBlock *TruncUserBB = TruncUser->getParent();
1831
1832     if (UserBB == TruncUserBB)
1833       continue;
1834
1835     BinaryOperator *&InsertedShift = InsertedShifts[TruncUserBB];
1836     CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
1837
1838     if (!InsertedShift && !InsertedTrunc) {
1839       BasicBlock::iterator InsertPt = TruncUserBB->getFirstInsertionPt();
1840       assert(InsertPt != TruncUserBB->end());
1841       // Sink the shift
1842       if (ShiftI->getOpcode() == Instruction::AShr)
1843         InsertedShift = BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI,
1844                                                    "", &*InsertPt);
1845       else
1846         InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI,
1847                                                    "", &*InsertPt);
1848
1849       // Sink the trunc
1850       BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt();
1851       TruncInsertPt++;
1852       assert(TruncInsertPt != TruncUserBB->end());
1853
1854       InsertedTrunc = CastInst::Create(TruncI->getOpcode(), InsertedShift,
1855                                        TruncI->getType(), "", &*TruncInsertPt);
1856
1857       MadeChange = true;
1858
1859       TruncTheUse = InsertedTrunc;
1860     }
1861   }
1862   return MadeChange;
1863 }
1864
1865 /// Sink the shift *right* instruction into user blocks if the uses could
1866 /// potentially be combined with this shift instruction and generate BitExtract
1867 /// instruction. It will only be applied if the architecture supports BitExtract
1868 /// instruction. Here is an example:
1869 /// BB1:
1870 ///   %x.extract.shift = lshr i64 %arg1, 32
1871 /// BB2:
1872 ///   %x.extract.trunc = trunc i64 %x.extract.shift to i16
1873 /// ==>
1874 ///
1875 /// BB2:
1876 ///   %x.extract.shift.1 = lshr i64 %arg1, 32
1877 ///   %x.extract.trunc = trunc i64 %x.extract.shift.1 to i16
1878 ///
1879 /// CodeGen will recoginze the pattern in BB2 and generate BitExtract
1880 /// instruction.
1881 /// Return true if any changes are made.
1882 static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI,
1883                                 const TargetLowering &TLI,
1884                                 const DataLayout &DL) {
1885   BasicBlock *DefBB = ShiftI->getParent();
1886
1887   /// Only insert instructions in each block once.
1888   DenseMap<BasicBlock *, BinaryOperator *> InsertedShifts;
1889
1890   bool shiftIsLegal = TLI.isTypeLegal(TLI.getValueType(DL, ShiftI->getType()));
1891
1892   bool MadeChange = false;
1893   for (Value::user_iterator UI = ShiftI->user_begin(), E = ShiftI->user_end();
1894        UI != E;) {
1895     Use &TheUse = UI.getUse();
1896     Instruction *User = cast<Instruction>(*UI);
1897     // Preincrement use iterator so we don't invalidate it.
1898     ++UI;
1899
1900     // Don't bother for PHI nodes.
1901     if (isa<PHINode>(User))
1902       continue;
1903
1904     if (!isExtractBitsCandidateUse(User))
1905       continue;
1906
1907     BasicBlock *UserBB = User->getParent();
1908
1909     if (UserBB == DefBB) {
1910       // If the shift and truncate instruction are in the same BB. The use of
1911       // the truncate(TruncUse) may still introduce another truncate if not
1912       // legal. In this case, we would like to sink both shift and truncate
1913       // instruction to the BB of TruncUse.
1914       // for example:
1915       // BB1:
1916       // i64 shift.result = lshr i64 opnd, imm
1917       // trunc.result = trunc shift.result to i16
1918       //
1919       // BB2:
1920       //   ----> We will have an implicit truncate here if the architecture does
1921       //   not have i16 compare.
1922       // cmp i16 trunc.result, opnd2
1923       //
1924       if (isa<TruncInst>(User) && shiftIsLegal
1925           // If the type of the truncate is legal, no trucate will be
1926           // introduced in other basic blocks.
1927           &&
1928           (!TLI.isTypeLegal(TLI.getValueType(DL, User->getType()))))
1929         MadeChange =
1930             SinkShiftAndTruncate(ShiftI, User, CI, InsertedShifts, TLI, DL);
1931
1932       continue;
1933     }
1934     // If we have already inserted a shift into this block, use it.
1935     BinaryOperator *&InsertedShift = InsertedShifts[UserBB];
1936
1937     if (!InsertedShift) {
1938       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1939       assert(InsertPt != UserBB->end());
1940
1941       if (ShiftI->getOpcode() == Instruction::AShr)
1942         InsertedShift = BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI,
1943                                                    "", &*InsertPt);
1944       else
1945         InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI,
1946                                                    "", &*InsertPt);
1947
1948       MadeChange = true;
1949     }
1950
1951     // Replace a use of the shift with a use of the new shift.
1952     TheUse = InsertedShift;
1953   }
1954
1955   // If we removed all uses, nuke the shift.
1956   if (ShiftI->use_empty())
1957     ShiftI->eraseFromParent();
1958
1959   return MadeChange;
1960 }
1961
1962 // Translate a masked load intrinsic like
1963 // <16 x i32 > @llvm.masked.load( <16 x i32>* %addr, i32 align,
1964 //                               <16 x i1> %mask, <16 x i32> %passthru)
1965 // to a chain of basic blocks, with loading element one-by-one if
1966 // the appropriate mask bit is set
1967 //
1968 //  %1 = bitcast i8* %addr to i32*
1969 //  %2 = extractelement <16 x i1> %mask, i32 0
1970 //  %3 = icmp eq i1 %2, true
1971 //  br i1 %3, label %cond.load, label %else
1972 //
1973 //cond.load:                                        ; preds = %0
1974 //  %4 = getelementptr i32* %1, i32 0
1975 //  %5 = load i32* %4
1976 //  %6 = insertelement <16 x i32> undef, i32 %5, i32 0
1977 //  br label %else
1978 //
1979 //else:                                             ; preds = %0, %cond.load
1980 //  %res.phi.else = phi <16 x i32> [ %6, %cond.load ], [ undef, %0 ]
1981 //  %7 = extractelement <16 x i1> %mask, i32 1
1982 //  %8 = icmp eq i1 %7, true
1983 //  br i1 %8, label %cond.load1, label %else2
1984 //
1985 //cond.load1:                                       ; preds = %else
1986 //  %9 = getelementptr i32* %1, i32 1
1987 //  %10 = load i32* %9
1988 //  %11 = insertelement <16 x i32> %res.phi.else, i32 %10, i32 1
1989 //  br label %else2
1990 //
1991 //else2:                                            ; preds = %else, %cond.load1
1992 //  %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else, %else ]
1993 //  %12 = extractelement <16 x i1> %mask, i32 2
1994 //  %13 = icmp eq i1 %12, true
1995 //  br i1 %13, label %cond.load4, label %else5
1996 //
1997 static void ScalarizeMaskedLoad(CallInst *CI) {
1998   Value *Ptr  = CI->getArgOperand(0);
1999   Value *Alignment = CI->getArgOperand(1);
2000   Value *Mask = CI->getArgOperand(2);
2001   Value *Src0 = CI->getArgOperand(3);
2002
2003   unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
2004   VectorType *VecType = dyn_cast<VectorType>(CI->getType());
2005   assert(VecType && "Unexpected return type of masked load intrinsic");
2006
2007   Type *EltTy = CI->getType()->getVectorElementType();
2008
2009   IRBuilder<> Builder(CI->getContext());
2010   Instruction *InsertPt = CI;
2011   BasicBlock *IfBlock = CI->getParent();
2012   BasicBlock *CondBlock = nullptr;
2013   BasicBlock *PrevIfBlock = CI->getParent();
2014
2015   Builder.SetInsertPoint(InsertPt);
2016   Builder.SetCurrentDebugLocation(CI->getDebugLoc());
2017
2018   // Short-cut if the mask is all-true.
2019   bool IsAllOnesMask = isa<Constant>(Mask) &&
2020     cast<Constant>(Mask)->isAllOnesValue();
2021
2022   if (IsAllOnesMask) {
2023     Value *NewI = Builder.CreateAlignedLoad(Ptr, AlignVal);
2024     CI->replaceAllUsesWith(NewI);
2025     CI->eraseFromParent();
2026     return;
2027   }
2028
2029   // Adjust alignment for the scalar instruction.
2030   AlignVal = std::min(AlignVal, VecType->getScalarSizeInBits()/8);
2031   // Bitcast %addr fron i8* to EltTy*
2032   Type *NewPtrType =
2033     EltTy->getPointerTo(cast<PointerType>(Ptr->getType())->getAddressSpace());
2034   Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType);
2035   unsigned VectorWidth = VecType->getNumElements();
2036
2037   Value *UndefVal = UndefValue::get(VecType);
2038
2039   // The result vector
2040   Value *VResult = UndefVal;
2041
2042   if (isa<ConstantVector>(Mask)) {
2043     for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2044       if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
2045           continue;
2046       Value *Gep =
2047           Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
2048       LoadInst* Load = Builder.CreateAlignedLoad(Gep, AlignVal);
2049       VResult = Builder.CreateInsertElement(VResult, Load,
2050                                             Builder.getInt32(Idx));
2051     }
2052     Value *NewI = Builder.CreateSelect(Mask, VResult, Src0);
2053     CI->replaceAllUsesWith(NewI);
2054     CI->eraseFromParent();
2055     return;
2056   }
2057
2058   PHINode *Phi = nullptr;
2059   Value *PrevPhi = UndefVal;
2060
2061   for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2062
2063     // Fill the "else" block, created in the previous iteration
2064     //
2065     //  %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else, %else ]
2066     //  %mask_1 = extractelement <16 x i1> %mask, i32 Idx
2067     //  %to_load = icmp eq i1 %mask_1, true
2068     //  br i1 %to_load, label %cond.load, label %else
2069     //
2070     if (Idx > 0) {
2071       Phi = Builder.CreatePHI(VecType, 2, "res.phi.else");
2072       Phi->addIncoming(VResult, CondBlock);
2073       Phi->addIncoming(PrevPhi, PrevIfBlock);
2074       PrevPhi = Phi;
2075       VResult = Phi;
2076     }
2077
2078     Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx));
2079     Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
2080                                     ConstantInt::get(Predicate->getType(), 1));
2081
2082     // Create "cond" block
2083     //
2084     //  %EltAddr = getelementptr i32* %1, i32 0
2085     //  %Elt = load i32* %EltAddr
2086     //  VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx
2087     //
2088     CondBlock = IfBlock->splitBasicBlock(InsertPt->getIterator(), "cond.load");
2089     Builder.SetInsertPoint(InsertPt);
2090
2091     Value *Gep =
2092         Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
2093     LoadInst *Load = Builder.CreateAlignedLoad(Gep, AlignVal);
2094     VResult = Builder.CreateInsertElement(VResult, Load, Builder.getInt32(Idx));
2095
2096     // Create "else" block, fill it in the next iteration
2097     BasicBlock *NewIfBlock =
2098         CondBlock->splitBasicBlock(InsertPt->getIterator(), "else");
2099     Builder.SetInsertPoint(InsertPt);
2100     Instruction *OldBr = IfBlock->getTerminator();
2101     BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
2102     OldBr->eraseFromParent();
2103     PrevIfBlock = IfBlock;
2104     IfBlock = NewIfBlock;
2105   }
2106
2107   Phi = Builder.CreatePHI(VecType, 2, "res.phi.select");
2108   Phi->addIncoming(VResult, CondBlock);
2109   Phi->addIncoming(PrevPhi, PrevIfBlock);
2110   Value *NewI = Builder.CreateSelect(Mask, Phi, Src0);
2111   CI->replaceAllUsesWith(NewI);
2112   CI->eraseFromParent();
2113 }
2114
2115 // Translate a masked store intrinsic, like
2116 // void @llvm.masked.store(<16 x i32> %src, <16 x i32>* %addr, i32 align,
2117 //                               <16 x i1> %mask)
2118 // to a chain of basic blocks, that stores element one-by-one if
2119 // the appropriate mask bit is set
2120 //
2121 //   %1 = bitcast i8* %addr to i32*
2122 //   %2 = extractelement <16 x i1> %mask, i32 0
2123 //   %3 = icmp eq i1 %2, true
2124 //   br i1 %3, label %cond.store, label %else
2125 //
2126 // cond.store:                                       ; preds = %0
2127 //   %4 = extractelement <16 x i32> %val, i32 0
2128 //   %5 = getelementptr i32* %1, i32 0
2129 //   store i32 %4, i32* %5
2130 //   br label %else
2131 //
2132 // else:                                             ; preds = %0, %cond.store
2133 //   %6 = extractelement <16 x i1> %mask, i32 1
2134 //   %7 = icmp eq i1 %6, true
2135 //   br i1 %7, label %cond.store1, label %else2
2136 //
2137 // cond.store1:                                      ; preds = %else
2138 //   %8 = extractelement <16 x i32> %val, i32 1
2139 //   %9 = getelementptr i32* %1, i32 1
2140 //   store i32 %8, i32* %9
2141 //   br label %else2
2142 //   . . .
2143 static void ScalarizeMaskedStore(CallInst *CI) {
2144   Value *Src = CI->getArgOperand(0);
2145   Value *Ptr  = CI->getArgOperand(1);
2146   Value *Alignment = CI->getArgOperand(2);
2147   Value *Mask = CI->getArgOperand(3);
2148
2149   unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
2150   VectorType *VecType = dyn_cast<VectorType>(Src->getType());
2151   assert(VecType && "Unexpected data type in masked store intrinsic");
2152
2153   Type *EltTy = VecType->getElementType();
2154
2155   IRBuilder<> Builder(CI->getContext());
2156   Instruction *InsertPt = CI;
2157   BasicBlock *IfBlock = CI->getParent();
2158   Builder.SetInsertPoint(InsertPt);
2159   Builder.SetCurrentDebugLocation(CI->getDebugLoc());
2160
2161   // Short-cut if the mask is all-true.
2162   bool IsAllOnesMask = isa<Constant>(Mask) &&
2163     cast<Constant>(Mask)->isAllOnesValue();
2164
2165   if (IsAllOnesMask) {
2166     Builder.CreateAlignedStore(Src, Ptr, AlignVal);
2167     CI->eraseFromParent();
2168     return;
2169   }
2170
2171   // Adjust alignment for the scalar instruction.
2172   AlignVal = std::max(AlignVal, VecType->getScalarSizeInBits()/8);
2173   // Bitcast %addr fron i8* to EltTy*
2174   Type *NewPtrType =
2175     EltTy->getPointerTo(cast<PointerType>(Ptr->getType())->getAddressSpace());
2176   Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType);
2177   unsigned VectorWidth = VecType->getNumElements();
2178
2179   if (isa<ConstantVector>(Mask)) {
2180     for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2181       if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
2182           continue;
2183       Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx));
2184       Value *Gep =
2185           Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
2186       Builder.CreateAlignedStore(OneElt, Gep, AlignVal);
2187     }
2188     CI->eraseFromParent();
2189     return;
2190   }
2191
2192   for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2193
2194     // Fill the "else" block, created in the previous iteration
2195     //
2196     //  %mask_1 = extractelement <16 x i1> %mask, i32 Idx
2197     //  %to_store = icmp eq i1 %mask_1, true
2198     //  br i1 %to_store, label %cond.store, label %else
2199     //
2200     Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx));
2201     Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
2202                                     ConstantInt::get(Predicate->getType(), 1));
2203
2204     // Create "cond" block
2205     //
2206     //  %OneElt = extractelement <16 x i32> %Src, i32 Idx
2207     //  %EltAddr = getelementptr i32* %1, i32 0
2208     //  %store i32 %OneElt, i32* %EltAddr
2209     //
2210     BasicBlock *CondBlock =
2211         IfBlock->splitBasicBlock(InsertPt->getIterator(), "cond.store");
2212     Builder.SetInsertPoint(InsertPt);
2213
2214     Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx));
2215     Value *Gep =
2216         Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
2217     Builder.CreateAlignedStore(OneElt, Gep, AlignVal);
2218
2219     // Create "else" block, fill it in the next iteration
2220     BasicBlock *NewIfBlock =
2221         CondBlock->splitBasicBlock(InsertPt->getIterator(), "else");
2222     Builder.SetInsertPoint(InsertPt);
2223     Instruction *OldBr = IfBlock->getTerminator();
2224     BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
2225     OldBr->eraseFromParent();
2226     IfBlock = NewIfBlock;
2227   }
2228   CI->eraseFromParent();
2229 }
2230
2231 // Translate a masked gather intrinsic like
2232 // <16 x i32 > @llvm.masked.gather.v16i32( <16 x i32*> %Ptrs, i32 4,
2233 //                               <16 x i1> %Mask, <16 x i32> %Src)
2234 // to a chain of basic blocks, with loading element one-by-one if
2235 // the appropriate mask bit is set
2236 //
2237 // % Ptrs = getelementptr i32, i32* %base, <16 x i64> %ind
2238 // % Mask0 = extractelement <16 x i1> %Mask, i32 0
2239 // % ToLoad0 = icmp eq i1 % Mask0, true
2240 // br i1 % ToLoad0, label %cond.load, label %else
2241 //
2242 // cond.load:
2243 // % Ptr0 = extractelement <16 x i32*> %Ptrs, i32 0
2244 // % Load0 = load i32, i32* % Ptr0, align 4
2245 // % Res0 = insertelement <16 x i32> undef, i32 % Load0, i32 0
2246 // br label %else
2247 //
2248 // else:
2249 // %res.phi.else = phi <16 x i32>[% Res0, %cond.load], [undef, % 0]
2250 // % Mask1 = extractelement <16 x i1> %Mask, i32 1
2251 // % ToLoad1 = icmp eq i1 % Mask1, true
2252 // br i1 % ToLoad1, label %cond.load1, label %else2
2253 //
2254 // cond.load1:
2255 // % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1
2256 // % Load1 = load i32, i32* % Ptr1, align 4
2257 // % Res1 = insertelement <16 x i32> %res.phi.else, i32 % Load1, i32 1
2258 // br label %else2
2259 // . . .
2260 // % Result = select <16 x i1> %Mask, <16 x i32> %res.phi.select, <16 x i32> %Src
2261 // ret <16 x i32> %Result
2262 static void ScalarizeMaskedGather(CallInst *CI) {
2263   Value *Ptrs = CI->getArgOperand(0);
2264   Value *Alignment = CI->getArgOperand(1);
2265   Value *Mask = CI->getArgOperand(2);
2266   Value *Src0 = CI->getArgOperand(3);
2267
2268   VectorType *VecType = dyn_cast<VectorType>(CI->getType());
2269
2270   assert(VecType && "Unexpected return type of masked load intrinsic");
2271
2272   IRBuilder<> Builder(CI->getContext());
2273   Instruction *InsertPt = CI;
2274   BasicBlock *IfBlock = CI->getParent();
2275   BasicBlock *CondBlock = nullptr;
2276   BasicBlock *PrevIfBlock = CI->getParent();
2277   Builder.SetInsertPoint(InsertPt);
2278   unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
2279
2280   Builder.SetCurrentDebugLocation(CI->getDebugLoc());
2281
2282   Value *UndefVal = UndefValue::get(VecType);
2283
2284   // The result vector
2285   Value *VResult = UndefVal;
2286   unsigned VectorWidth = VecType->getNumElements();
2287
2288   // Shorten the way if the mask is a vector of constants.
2289   bool IsConstMask = isa<ConstantVector>(Mask);
2290
2291   if (IsConstMask) {
2292     for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2293       if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
2294         continue;
2295       Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
2296                                                 "Ptr" + Twine(Idx));
2297       LoadInst *Load = Builder.CreateAlignedLoad(Ptr, AlignVal,
2298                                                  "Load" + Twine(Idx));
2299       VResult = Builder.CreateInsertElement(VResult, Load,
2300                                             Builder.getInt32(Idx),
2301                                             "Res" + Twine(Idx));
2302     }
2303     Value *NewI = Builder.CreateSelect(Mask, VResult, Src0);
2304     CI->replaceAllUsesWith(NewI);
2305     CI->eraseFromParent();
2306     return;
2307   }
2308
2309   PHINode *Phi = nullptr;
2310   Value *PrevPhi = UndefVal;
2311
2312   for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2313
2314     // Fill the "else" block, created in the previous iteration
2315     //
2316     //  %Mask1 = extractelement <16 x i1> %Mask, i32 1
2317     //  %ToLoad1 = icmp eq i1 %Mask1, true
2318     //  br i1 %ToLoad1, label %cond.load, label %else
2319     //
2320     if (Idx > 0) {
2321       Phi = Builder.CreatePHI(VecType, 2, "res.phi.else");
2322       Phi->addIncoming(VResult, CondBlock);
2323       Phi->addIncoming(PrevPhi, PrevIfBlock);
2324       PrevPhi = Phi;
2325       VResult = Phi;
2326     }
2327
2328     Value *Predicate = Builder.CreateExtractElement(Mask,
2329                                                     Builder.getInt32(Idx),
2330                                                     "Mask" + Twine(Idx));
2331     Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
2332                                     ConstantInt::get(Predicate->getType(), 1),
2333                                     "ToLoad" + Twine(Idx));
2334
2335     // Create "cond" block
2336     //
2337     //  %EltAddr = getelementptr i32* %1, i32 0
2338     //  %Elt = load i32* %EltAddr
2339     //  VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx
2340     //
2341     CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.load");
2342     Builder.SetInsertPoint(InsertPt);
2343
2344     Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
2345                                               "Ptr" + Twine(Idx));
2346     LoadInst *Load = Builder.CreateAlignedLoad(Ptr, AlignVal,
2347                                                "Load" + Twine(Idx));
2348     VResult = Builder.CreateInsertElement(VResult, Load, Builder.getInt32(Idx),
2349                                           "Res" + Twine(Idx));
2350
2351     // Create "else" block, fill it in the next iteration
2352     BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
2353     Builder.SetInsertPoint(InsertPt);
2354     Instruction *OldBr = IfBlock->getTerminator();
2355     BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
2356     OldBr->eraseFromParent();
2357     PrevIfBlock = IfBlock;
2358     IfBlock = NewIfBlock;
2359   }
2360
2361   Phi = Builder.CreatePHI(VecType, 2, "res.phi.select");
2362   Phi->addIncoming(VResult, CondBlock);
2363   Phi->addIncoming(PrevPhi, PrevIfBlock);
2364   Value *NewI = Builder.CreateSelect(Mask, Phi, Src0);
2365   CI->replaceAllUsesWith(NewI);
2366   CI->eraseFromParent();
2367 }
2368
2369 // Translate a masked scatter intrinsic, like
2370 // void @llvm.masked.scatter.v16i32(<16 x i32> %Src, <16 x i32*>* %Ptrs, i32 4,
2371 //                                  <16 x i1> %Mask)
2372 // to a chain of basic blocks, that stores element one-by-one if
2373 // the appropriate mask bit is set.
2374 //
2375 // % Ptrs = getelementptr i32, i32* %ptr, <16 x i64> %ind
2376 // % Mask0 = extractelement <16 x i1> % Mask, i32 0
2377 // % ToStore0 = icmp eq i1 % Mask0, true
2378 // br i1 %ToStore0, label %cond.store, label %else
2379 //
2380 // cond.store:
2381 // % Elt0 = extractelement <16 x i32> %Src, i32 0
2382 // % Ptr0 = extractelement <16 x i32*> %Ptrs, i32 0
2383 // store i32 %Elt0, i32* % Ptr0, align 4
2384 // br label %else
2385 //
2386 // else:
2387 // % Mask1 = extractelement <16 x i1> % Mask, i32 1
2388 // % ToStore1 = icmp eq i1 % Mask1, true
2389 // br i1 % ToStore1, label %cond.store1, label %else2
2390 //
2391 // cond.store1:
2392 // % Elt1 = extractelement <16 x i32> %Src, i32 1
2393 // % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1
2394 // store i32 % Elt1, i32* % Ptr1, align 4
2395 // br label %else2
2396 //   . . .
2397 static void ScalarizeMaskedScatter(CallInst *CI) {
2398   Value *Src = CI->getArgOperand(0);
2399   Value *Ptrs = CI->getArgOperand(1);
2400   Value *Alignment = CI->getArgOperand(2);
2401   Value *Mask = CI->getArgOperand(3);
2402
2403   assert(isa<VectorType>(Src->getType()) &&
2404          "Unexpected data type in masked scatter intrinsic");
2405   assert(isa<VectorType>(Ptrs->getType()) &&
2406          isa<PointerType>(Ptrs->getType()->getVectorElementType()) &&
2407          "Vector of pointers is expected in masked scatter intrinsic");
2408
2409   IRBuilder<> Builder(CI->getContext());
2410   Instruction *InsertPt = CI;
2411   BasicBlock *IfBlock = CI->getParent();
2412   Builder.SetInsertPoint(InsertPt);
2413   Builder.SetCurrentDebugLocation(CI->getDebugLoc());
2414
2415   unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
2416   unsigned VectorWidth = Src->getType()->getVectorNumElements();
2417
2418   // Shorten the way if the mask is a vector of constants.
2419   bool IsConstMask = isa<ConstantVector>(Mask);
2420
2421   if (IsConstMask) {
2422     for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2423       if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
2424         continue;
2425       Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx),
2426                                                    "Elt" + Twine(Idx));
2427       Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
2428                                                 "Ptr" + Twine(Idx));
2429       Builder.CreateAlignedStore(OneElt, Ptr, AlignVal);
2430     }
2431     CI->eraseFromParent();
2432     return;
2433   }
2434   for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2435     // Fill the "else" block, created in the previous iteration
2436     //
2437     //  % Mask1 = extractelement <16 x i1> % Mask, i32 Idx
2438     //  % ToStore = icmp eq i1 % Mask1, true
2439     //  br i1 % ToStore, label %cond.store, label %else
2440     //
2441     Value *Predicate = Builder.CreateExtractElement(Mask,
2442                                                     Builder.getInt32(Idx),
2443                                                     "Mask" + Twine(Idx));
2444     Value *Cmp =
2445        Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
2446                           ConstantInt::get(Predicate->getType(), 1),
2447                           "ToStore" + Twine(Idx));
2448
2449     // Create "cond" block
2450     //
2451     //  % Elt1 = extractelement <16 x i32> %Src, i32 1
2452     //  % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1
2453     //  %store i32 % Elt1, i32* % Ptr1
2454     //
2455     BasicBlock *CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store");
2456     Builder.SetInsertPoint(InsertPt);
2457
2458     Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx),
2459                                                  "Elt" + Twine(Idx));
2460     Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
2461                                               "Ptr" + Twine(Idx));
2462     Builder.CreateAlignedStore(OneElt, Ptr, AlignVal);
2463
2464     // Create "else" block, fill it in the next iteration
2465     BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
2466     Builder.SetInsertPoint(InsertPt);
2467     Instruction *OldBr = IfBlock->getTerminator();
2468     BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
2469     OldBr->eraseFromParent();
2470     IfBlock = NewIfBlock;
2471   }
2472   CI->eraseFromParent();
2473 }
2474
2475 /// If counting leading or trailing zeros is an expensive operation and a zero
2476 /// input is defined, add a check for zero to avoid calling the intrinsic.
2477 ///
2478 /// We want to transform:
2479 ///     %z = call i64 @llvm.cttz.i64(i64 %A, i1 false)
2480 ///
2481 /// into:
2482 ///   entry:
2483 ///     %cmpz = icmp eq i64 %A, 0
2484 ///     br i1 %cmpz, label %cond.end, label %cond.false
2485 ///   cond.false:
2486 ///     %z = call i64 @llvm.cttz.i64(i64 %A, i1 true)
2487 ///     br label %cond.end
2488 ///   cond.end:
2489 ///     %ctz = phi i64 [ 64, %entry ], [ %z, %cond.false ]
2490 ///
2491 /// If the transform is performed, return true and set ModifiedDT to true.
2492 static bool despeculateCountZeros(IntrinsicInst *CountZeros,
2493                                   const TargetLowering *TLI,
2494                                   const DataLayout *DL,
2495                                   bool &ModifiedDT) {
2496   if (!TLI || !DL)
2497     return false;
2498
2499   // If a zero input is undefined, it doesn't make sense to despeculate that.
2500   if (match(CountZeros->getOperand(1), m_One()))
2501     return false;
2502
2503   // If it's cheap to speculate, there's nothing to do.
2504   auto IntrinsicID = CountZeros->getIntrinsicID();
2505   if ((IntrinsicID == Intrinsic::cttz && TLI->isCheapToSpeculateCttz()) ||
2506       (IntrinsicID == Intrinsic::ctlz && TLI->isCheapToSpeculateCtlz()))
2507     return false;
2508
2509   // Only handle legal scalar cases. Anything else requires too much work.
2510   Type *Ty = CountZeros->getType();
2511   unsigned SizeInBits = Ty->getPrimitiveSizeInBits();
2512   if (Ty->isVectorTy() || SizeInBits > DL->getLargestLegalIntTypeSize())
2513     return false;
2514
2515   // The intrinsic will be sunk behind a compare against zero and branch.
2516   BasicBlock *StartBlock = CountZeros->getParent();
2517   BasicBlock *CallBlock = StartBlock->splitBasicBlock(CountZeros, "cond.false");
2518
2519   // Create another block after the count zero intrinsic. A PHI will be added
2520   // in this block to select the result of the intrinsic or the bit-width
2521   // constant if the input to the intrinsic is zero.
2522   BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(CountZeros));
2523   BasicBlock *EndBlock = CallBlock->splitBasicBlock(SplitPt, "cond.end");
2524
2525   // Set up a builder to create a compare, conditional branch, and PHI.
2526   IRBuilder<> Builder(CountZeros->getContext());
2527   Builder.SetInsertPoint(StartBlock->getTerminator());
2528   Builder.SetCurrentDebugLocation(CountZeros->getDebugLoc());
2529
2530   // Replace the unconditional branch that was created by the first split with
2531   // a compare against zero and a conditional branch.
2532   Value *Zero = Constant::getNullValue(Ty);
2533   Value *Cmp = Builder.CreateICmpEQ(CountZeros->getOperand(0), Zero, "cmpz");
2534   Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
2535   StartBlock->getTerminator()->eraseFromParent();
2536
2537   // Create a PHI in the end block to select either the output of the intrinsic
2538   // or the bit width of the operand.
2539   Builder.SetInsertPoint(&EndBlock->front());
2540   PHINode *PN = Builder.CreatePHI(Ty, 2, "ctz");
2541   CountZeros->replaceAllUsesWith(PN);
2542   Value *BitWidth = Builder.getInt(APInt(SizeInBits, SizeInBits));
2543   PN->addIncoming(BitWidth, StartBlock);
2544   PN->addIncoming(CountZeros, CallBlock);
2545
2546   // We are explicitly handling the zero case, so we can set the intrinsic's
2547   // undefined zero argument to 'true'. This will also prevent reprocessing the
2548   // intrinsic; we only despeculate when a zero input is defined.
2549   CountZeros->setArgOperand(1, Builder.getTrue());
2550   ModifiedDT = true;
2551   return true;
2552 }
2553
2554 bool CodeGenPrepare::optimizeCallInst(CallInst *CI, bool& ModifiedDT) {
2555   BasicBlock *BB = CI->getParent();
2556
2557   // Lower inline assembly if we can.
2558   // If we found an inline asm expession, and if the target knows how to
2559   // lower it to normal LLVM code, do so now.
2560   if (TLI && isa<InlineAsm>(CI->getCalledValue())) {
2561     if (TLI->ExpandInlineAsm(CI)) {
2562       // Avoid invalidating the iterator.
2563       CurInstIterator = BB->begin();
2564       // Avoid processing instructions out of order, which could cause
2565       // reuse before a value is defined.
2566       SunkAddrs.clear();
2567       return true;
2568     }
2569     // Sink address computing for memory operands into the block.
2570     if (optimizeInlineAsmInst(CI))
2571       return true;
2572   }
2573
2574   // Align the pointer arguments to this call if the target thinks it's a good
2575   // idea
2576   unsigned MinSize, PrefAlign;
2577   if (TLI && TLI->shouldAlignPointerArgs(CI, MinSize, PrefAlign)) {
2578     for (auto &Arg : CI->arg_operands()) {
2579       // We want to align both objects whose address is used directly and
2580       // objects whose address is used in casts and GEPs, though it only makes
2581       // sense for GEPs if the offset is a multiple of the desired alignment and
2582       // if size - offset meets the size threshold.
2583       if (!Arg->getType()->isPointerTy())
2584         continue;
2585       APInt Offset(DL->getPointerSizeInBits(
2586                        cast<PointerType>(Arg->getType())->getAddressSpace()),
2587                    0);
2588       Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*DL, Offset);
2589       uint64_t Offset2 = Offset.getLimitedValue();
2590       if ((Offset2 & (PrefAlign-1)) != 0)
2591         continue;
2592       AllocaInst *AI;
2593       if ((AI = dyn_cast<AllocaInst>(Val)) && AI->getAlignment() < PrefAlign &&
2594           DL->getTypeAllocSize(AI->getAllocatedType()) >= MinSize + Offset2)
2595         AI->setAlignment(PrefAlign);
2596       // Global variables can only be aligned if they are defined in this
2597       // object (i.e. they are uniquely initialized in this object), and
2598       // over-aligning global variables that have an explicit section is
2599       // forbidden.
2600       GlobalVariable *GV;
2601       if ((GV = dyn_cast<GlobalVariable>(Val)) && GV->canIncreaseAlignment() &&
2602           GV->getAlignment() < PrefAlign &&
2603           DL->getTypeAllocSize(GV->getType()->getElementType()) >=
2604               MinSize + Offset2)
2605         GV->setAlignment(PrefAlign);
2606     }
2607     // If this is a memcpy (or similar) then we may be able to improve the
2608     // alignment
2609     if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(CI)) {
2610       unsigned Align = getKnownAlignment(MI->getDest(), *DL);
2611       if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
2612         Align = std::min(Align, getKnownAlignment(MTI->getSource(), *DL));
2613       if (Align > MI->getAlignment())
2614         MI->setAlignment(ConstantInt::get(MI->getAlignmentType(), Align));
2615     }
2616   }
2617
2618   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
2619   if (II) {
2620     switch (II->getIntrinsicID()) {
2621     default: break;
2622     case Intrinsic::objectsize: {
2623       // Lower all uses of llvm.objectsize.*
2624       bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1);
2625       Type *ReturnTy = CI->getType();
2626       Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL);
2627
2628       // Substituting this can cause recursive simplifications, which can
2629       // invalidate our iterator.  Use a WeakVH to hold onto it in case this
2630       // happens.
2631       WeakVH IterHandle(&*CurInstIterator);
2632
2633       replaceAndRecursivelySimplify(CI, RetVal,
2634                                     TLInfo, nullptr);
2635
2636       // If the iterator instruction was recursively deleted, start over at the
2637       // start of the block.
2638       if (IterHandle != CurInstIterator.getNodePtrUnchecked()) {
2639         CurInstIterator = BB->begin();
2640         SunkAddrs.clear();
2641       }
2642       return true;
2643     }
2644     case Intrinsic::masked_load: {
2645       // Scalarize unsupported vector masked load
2646       if (!TTI->isLegalMaskedLoad(CI->getType())) {
2647         ScalarizeMaskedLoad(CI);
2648         ModifiedDT = true;
2649         return true;
2650       }
2651       return false;
2652     }
2653     case Intrinsic::masked_store: {
2654       if (!TTI->isLegalMaskedStore(CI->getArgOperand(0)->getType())) {
2655         ScalarizeMaskedStore(CI);
2656         ModifiedDT = true;
2657         return true;
2658       }
2659       return false;
2660     }
2661     case Intrinsic::masked_gather: {
2662       if (!TTI->isLegalMaskedGather(CI->getType())) {
2663         ScalarizeMaskedGather(CI);
2664         ModifiedDT = true;
2665         return true;
2666       }
2667       return false;
2668     }
2669     case Intrinsic::masked_scatter: {
2670       if (!TTI->isLegalMaskedScatter(CI->getArgOperand(0)->getType())) {
2671         ScalarizeMaskedScatter(CI);
2672         ModifiedDT = true;
2673         return true;
2674       }
2675       return false;
2676     }
2677     case Intrinsic::aarch64_stlxr:
2678     case Intrinsic::aarch64_stxr: {
2679       ZExtInst *ExtVal = dyn_cast<ZExtInst>(CI->getArgOperand(0));
2680       if (!ExtVal || !ExtVal->hasOneUse() ||
2681           ExtVal->getParent() == CI->getParent())
2682         return false;
2683       // Sink a zext feeding stlxr/stxr before it, so it can be folded into it.
2684       ExtVal->moveBefore(CI);
2685       // Mark this instruction as "inserted by CGP", so that other
2686       // optimizations don't touch it.
2687       InsertedInsts.insert(ExtVal);
2688       return true;
2689     }
2690     case Intrinsic::invariant_group_barrier:
2691       II->replaceAllUsesWith(II->getArgOperand(0));
2692       II->eraseFromParent();
2693       return true;
2694
2695     case Intrinsic::cttz:
2696     case Intrinsic::ctlz:
2697       // If counting zeros is expensive, try to avoid it.
2698       return despeculateCountZeros(II, TLI, DL, ModifiedDT);
2699     }
2700
2701     if (TLI) {
2702       // Unknown address space.
2703       // TODO: Target hook to pick which address space the intrinsic cares
2704       // about?
2705       unsigned AddrSpace = ~0u;
2706       SmallVector<Value*, 2> PtrOps;
2707       Type *AccessTy;
2708       if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy, AddrSpace))
2709         while (!PtrOps.empty())
2710           if (optimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy, AddrSpace))
2711             return true;
2712     }
2713   }
2714
2715   // From here on out we're working with named functions.
2716   if (!CI->getCalledFunction()) return false;
2717
2718   // Lower all default uses of _chk calls.  This is very similar
2719   // to what InstCombineCalls does, but here we are only lowering calls
2720   // to fortified library functions (e.g. __memcpy_chk) that have the default
2721   // "don't know" as the objectsize.  Anything else should be left alone.
2722   FortifiedLibCallSimplifier Simplifier(TLInfo, true);
2723   if (Value *V = Simplifier.optimizeCall(CI)) {
2724     CI->replaceAllUsesWith(V);
2725     CI->eraseFromParent();
2726     return true;
2727   }
2728   return false;
2729 }
2730
2731 /// Look for opportunities to duplicate return instructions to the predecessor
2732 /// to enable tail call optimizations. The case it is currently looking for is:
2733 /// @code
2734 /// bb0:
2735 ///   %tmp0 = tail call i32 @f0()
2736 ///   br label %return
2737 /// bb1:
2738 ///   %tmp1 = tail call i32 @f1()
2739 ///   br label %return
2740 /// bb2:
2741 ///   %tmp2 = tail call i32 @f2()
2742 ///   br label %return
2743 /// return:
2744 ///   %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ]
2745 ///   ret i32 %retval
2746 /// @endcode
2747 ///
2748 /// =>
2749 ///
2750 /// @code
2751 /// bb0:
2752 ///   %tmp0 = tail call i32 @f0()
2753 ///   ret i32 %tmp0
2754 /// bb1:
2755 ///   %tmp1 = tail call i32 @f1()
2756 ///   ret i32 %tmp1
2757 /// bb2:
2758 ///   %tmp2 = tail call i32 @f2()
2759 ///   ret i32 %tmp2
2760 /// @endcode
2761 bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB) {
2762   if (!TLI)
2763     return false;
2764
2765   ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator());
2766   if (!RI)
2767     return false;
2768
2769   PHINode *PN = nullptr;
2770   BitCastInst *BCI = nullptr;
2771   Value *V = RI->getReturnValue();
2772   if (V) {
2773     BCI = dyn_cast<BitCastInst>(V);
2774     if (BCI)
2775       V = BCI->getOperand(0);
2776
2777     PN = dyn_cast<PHINode>(V);
2778     if (!PN)
2779       return false;
2780   }
2781
2782   if (PN && PN->getParent() != BB)
2783     return false;
2784
2785   // It's not safe to eliminate the sign / zero extension of the return value.
2786   // See llvm::isInTailCallPosition().
2787   const Function *F = BB->getParent();
2788   AttributeSet CallerAttrs = F->getAttributes();
2789   if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) ||
2790       CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt))
2791     return false;
2792
2793   // Make sure there are no instructions between the PHI and return, or that the
2794   // return is the first instruction in the block.
2795   if (PN) {
2796     BasicBlock::iterator BI = BB->begin();
2797     do { ++BI; } while (isa<DbgInfoIntrinsic>(BI));
2798     if (&*BI == BCI)
2799       // Also skip over the bitcast.
2800       ++BI;
2801     if (&*BI != RI)
2802       return false;
2803   } else {
2804     BasicBlock::iterator BI = BB->begin();
2805     while (isa<DbgInfoIntrinsic>(BI)) ++BI;
2806     if (&*BI != RI)
2807       return false;
2808   }
2809
2810   /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail
2811   /// call.
2812   SmallVector<CallInst*, 4> TailCalls;
2813   if (PN) {
2814     for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
2815       CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I));
2816       // Make sure the phi value is indeed produced by the tail call.
2817       if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) &&
2818           TLI->mayBeEmittedAsTailCall(CI))
2819         TailCalls.push_back(CI);
2820     }
2821   } else {
2822     SmallPtrSet<BasicBlock*, 4> VisitedBBs;
2823     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
2824       if (!VisitedBBs.insert(*PI).second)
2825         continue;
2826
2827       BasicBlock::InstListType &InstList = (*PI)->getInstList();
2828       BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin();
2829       BasicBlock::InstListType::reverse_iterator RE = InstList.rend();
2830       do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI));
2831       if (RI == RE)
2832         continue;
2833
2834       CallInst *CI = dyn_cast<CallInst>(&*RI);
2835       if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI))
2836         TailCalls.push_back(CI);
2837     }
2838   }
2839
2840   bool Changed = false;
2841   for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) {
2842     CallInst *CI = TailCalls[i];
2843     CallSite CS(CI);
2844
2845     // Conservatively require the attributes of the call to match those of the
2846     // return. Ignore noalias because it doesn't affect the call sequence.
2847     AttributeSet CalleeAttrs = CS.getAttributes();
2848     if (AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
2849           removeAttribute(Attribute::NoAlias) !=
2850         AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
2851           removeAttribute(Attribute::NoAlias))
2852       continue;
2853
2854     // Make sure the call instruction is followed by an unconditional branch to
2855     // the return block.
2856     BasicBlock *CallBB = CI->getParent();
2857     BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator());
2858     if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
2859       continue;
2860
2861     // Duplicate the return into CallBB.
2862     (void)FoldReturnIntoUncondBranch(RI, BB, CallBB);
2863     ModifiedDT = Changed = true;
2864     ++NumRetsDup;
2865   }
2866
2867   // If we eliminated all predecessors of the block, delete the block now.
2868   if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
2869     BB->eraseFromParent();
2870
2871   return Changed;
2872 }
2873
2874 //===----------------------------------------------------------------------===//
2875 // Memory Optimization
2876 //===----------------------------------------------------------------------===//
2877
2878 namespace {
2879
2880 /// This is an extended version of TargetLowering::AddrMode
2881 /// which holds actual Value*'s for register values.
2882 struct ExtAddrMode : public TargetLowering::AddrMode {
2883   Value *BaseReg;
2884   Value *ScaledReg;
2885   ExtAddrMode() : BaseReg(nullptr), ScaledReg(nullptr) {}
2886   void print(raw_ostream &OS) const;
2887   void dump() const;
2888
2889   bool operator==(const ExtAddrMode& O) const {
2890     return (BaseReg == O.BaseReg) && (ScaledReg == O.ScaledReg) &&
2891            (BaseGV == O.BaseGV) && (BaseOffs == O.BaseOffs) &&
2892            (HasBaseReg == O.HasBaseReg) && (Scale == O.Scale);
2893   }
2894 };
2895
2896 #ifndef NDEBUG
2897 static inline raw_ostream &operator<<(raw_ostream &OS, const ExtAddrMode &AM) {
2898   AM.print(OS);
2899   return OS;
2900 }
2901 #endif
2902
2903 void ExtAddrMode::print(raw_ostream &OS) const {
2904   bool NeedPlus = false;
2905   OS << "[";
2906   if (BaseGV) {
2907     OS << (NeedPlus ? " + " : "")
2908        << "GV:";
2909     BaseGV->printAsOperand(OS, /*PrintType=*/false);
2910     NeedPlus = true;
2911   }
2912
2913   if (BaseOffs) {
2914     OS << (NeedPlus ? " + " : "")
2915        << BaseOffs;
2916     NeedPlus = true;
2917   }
2918
2919   if (BaseReg) {
2920     OS << (NeedPlus ? " + " : "")
2921        << "Base:";
2922     BaseReg->printAsOperand(OS, /*PrintType=*/false);
2923     NeedPlus = true;
2924   }
2925   if (Scale) {
2926     OS << (NeedPlus ? " + " : "")
2927        << Scale << "*";
2928     ScaledReg->printAsOperand(OS, /*PrintType=*/false);
2929   }
2930
2931   OS << ']';
2932 }
2933
2934 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2935 void ExtAddrMode::dump() const {
2936   print(dbgs());
2937   dbgs() << '\n';
2938 }
2939 #endif
2940
2941 /// \brief This class provides transaction based operation on the IR.
2942 /// Every change made through this class is recorded in the internal state and
2943 /// can be undone (rollback) until commit is called.
2944 class TypePromotionTransaction {
2945
2946   /// \brief This represents the common interface of the individual transaction.
2947   /// Each class implements the logic for doing one specific modification on
2948   /// the IR via the TypePromotionTransaction.
2949   class TypePromotionAction {
2950   protected:
2951     /// The Instruction modified.
2952     Instruction *Inst;
2953
2954   public:
2955     /// \brief Constructor of the action.
2956     /// The constructor performs the related action on the IR.
2957     TypePromotionAction(Instruction *Inst) : Inst(Inst) {}
2958
2959     virtual ~TypePromotionAction() {}
2960
2961     /// \brief Undo the modification done by this action.
2962     /// When this method is called, the IR must be in the same state as it was
2963     /// before this action was applied.
2964     /// \pre Undoing the action works if and only if the IR is in the exact same
2965     /// state as it was directly after this action was applied.
2966     virtual void undo() = 0;
2967
2968     /// \brief Advocate every change made by this action.
2969     /// When the results on the IR of the action are to be kept, it is important
2970     /// to call this function, otherwise hidden information may be kept forever.
2971     virtual void commit() {
2972       // Nothing to be done, this action is not doing anything.
2973     }
2974   };
2975
2976   /// \brief Utility to remember the position of an instruction.
2977   class InsertionHandler {
2978     /// Position of an instruction.
2979     /// Either an instruction:
2980     /// - Is the first in a basic block: BB is used.
2981     /// - Has a previous instructon: PrevInst is used.
2982     union {
2983       Instruction *PrevInst;
2984       BasicBlock *BB;
2985     } Point;
2986     /// Remember whether or not the instruction had a previous instruction.
2987     bool HasPrevInstruction;
2988
2989   public:
2990     /// \brief Record the position of \p Inst.
2991     InsertionHandler(Instruction *Inst) {
2992       BasicBlock::iterator It = Inst->getIterator();
2993       HasPrevInstruction = (It != (Inst->getParent()->begin()));
2994       if (HasPrevInstruction)
2995         Point.PrevInst = &*--It;
2996       else
2997         Point.BB = Inst->getParent();
2998     }
2999
3000     /// \brief Insert \p Inst at the recorded position.
3001     void insert(Instruction *Inst) {
3002       if (HasPrevInstruction) {
3003         if (Inst->getParent())
3004           Inst->removeFromParent();
3005         Inst->insertAfter(Point.PrevInst);
3006       } else {
3007         Instruction *Position = &*Point.BB->getFirstInsertionPt();
3008         if (Inst->getParent())
3009           Inst->moveBefore(Position);
3010         else
3011           Inst->insertBefore(Position);
3012       }
3013     }
3014   };
3015
3016   /// \brief Move an instruction before another.
3017   class InstructionMoveBefore : public TypePromotionAction {
3018     /// Original position of the instruction.
3019     InsertionHandler Position;
3020
3021   public:
3022     /// \brief Move \p Inst before \p Before.
3023     InstructionMoveBefore(Instruction *Inst, Instruction *Before)
3024         : TypePromotionAction(Inst), Position(Inst) {
3025       DEBUG(dbgs() << "Do: move: " << *Inst << "\nbefore: " << *Before << "\n");
3026       Inst->moveBefore(Before);
3027     }
3028
3029     /// \brief Move the instruction back to its original position.
3030     void undo() override {
3031       DEBUG(dbgs() << "Undo: moveBefore: " << *Inst << "\n");
3032       Position.insert(Inst);
3033     }
3034   };
3035
3036   /// \brief Set the operand of an instruction with a new value.
3037   class OperandSetter : public TypePromotionAction {
3038     /// Original operand of the instruction.
3039     Value *Origin;
3040     /// Index of the modified instruction.
3041     unsigned Idx;
3042
3043   public:
3044     /// \brief Set \p Idx operand of \p Inst with \p NewVal.
3045     OperandSetter(Instruction *Inst, unsigned Idx, Value *NewVal)
3046         : TypePromotionAction(Inst), Idx(Idx) {
3047       DEBUG(dbgs() << "Do: setOperand: " << Idx << "\n"
3048                    << "for:" << *Inst << "\n"
3049                    << "with:" << *NewVal << "\n");
3050       Origin = Inst->getOperand(Idx);
3051       Inst->setOperand(Idx, NewVal);
3052     }
3053
3054     /// \brief Restore the original value of the instruction.
3055     void undo() override {
3056       DEBUG(dbgs() << "Undo: setOperand:" << Idx << "\n"
3057                    << "for: " << *Inst << "\n"
3058                    << "with: " << *Origin << "\n");
3059       Inst->setOperand(Idx, Origin);
3060     }
3061   };
3062
3063   /// \brief Hide the operands of an instruction.
3064   /// Do as if this instruction was not using any of its operands.
3065   class OperandsHider : public TypePromotionAction {
3066     /// The list of original operands.
3067     SmallVector<Value *, 4> OriginalValues;
3068
3069   public:
3070     /// \brief Remove \p Inst from the uses of the operands of \p Inst.
3071     OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) {
3072       DEBUG(dbgs() << "Do: OperandsHider: " << *Inst << "\n");
3073       unsigned NumOpnds = Inst->getNumOperands();
3074       OriginalValues.reserve(NumOpnds);
3075       for (unsigned It = 0; It < NumOpnds; ++It) {
3076         // Save the current operand.
3077         Value *Val = Inst->getOperand(It);
3078         OriginalValues.push_back(Val);
3079         // Set a dummy one.
3080         // We could use OperandSetter here, but that would imply an overhead
3081         // that we are not willing to pay.
3082         Inst->setOperand(It, UndefValue::get(Val->getType()));
3083       }
3084     }
3085
3086     /// \brief Restore the original list of uses.
3087     void undo() override {
3088       DEBUG(dbgs() << "Undo: OperandsHider: " << *Inst << "\n");
3089       for (unsigned It = 0, EndIt = OriginalValues.size(); It != EndIt; ++It)
3090         Inst->setOperand(It, OriginalValues[It]);
3091     }
3092   };
3093
3094   /// \brief Build a truncate instruction.
3095   class TruncBuilder : public TypePromotionAction {
3096     Value *Val;
3097   public:
3098     /// \brief Build a truncate instruction of \p Opnd producing a \p Ty
3099     /// result.
3100     /// trunc Opnd to Ty.
3101     TruncBuilder(Instruction *Opnd, Type *Ty) : TypePromotionAction(Opnd) {
3102       IRBuilder<> Builder(Opnd);
3103       Val = Builder.CreateTrunc(Opnd, Ty, "promoted");
3104       DEBUG(dbgs() << "Do: TruncBuilder: " << *Val << "\n");
3105     }
3106
3107     /// \brief Get the built value.
3108     Value *getBuiltValue() { return Val; }
3109
3110     /// \brief Remove the built instruction.
3111     void undo() override {
3112       DEBUG(dbgs() << "Undo: TruncBuilder: " << *Val << "\n");
3113       if (Instruction *IVal = dyn_cast<Instruction>(Val))
3114         IVal->eraseFromParent();
3115     }
3116   };
3117
3118   /// \brief Build a sign extension instruction.
3119   class SExtBuilder : public TypePromotionAction {
3120     Value *Val;
3121   public:
3122     /// \brief Build a sign extension instruction of \p Opnd producing a \p Ty
3123     /// result.
3124     /// sext Opnd to Ty.
3125     SExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
3126         : TypePromotionAction(InsertPt) {
3127       IRBuilder<> Builder(InsertPt);
3128       Val = Builder.CreateSExt(Opnd, Ty, "promoted");
3129       DEBUG(dbgs() << "Do: SExtBuilder: " << *Val << "\n");
3130     }
3131
3132     /// \brief Get the built value.
3133     Value *getBuiltValue() { return Val; }
3134
3135     /// \brief Remove the built instruction.
3136     void undo() override {
3137       DEBUG(dbgs() << "Undo: SExtBuilder: " << *Val << "\n");
3138       if (Instruction *IVal = dyn_cast<Instruction>(Val))
3139         IVal->eraseFromParent();
3140     }
3141   };
3142
3143   /// \brief Build a zero extension instruction.
3144   class ZExtBuilder : public TypePromotionAction {
3145     Value *Val;
3146   public:
3147     /// \brief Build a zero extension instruction of \p Opnd producing a \p Ty
3148     /// result.
3149     /// zext Opnd to Ty.
3150     ZExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
3151         : TypePromotionAction(InsertPt) {
3152       IRBuilder<> Builder(InsertPt);
3153       Val = Builder.CreateZExt(Opnd, Ty, "promoted");
3154       DEBUG(dbgs() << "Do: ZExtBuilder: " << *Val << "\n");
3155     }
3156
3157     /// \brief Get the built value.
3158     Value *getBuiltValue() { return Val; }
3159
3160     /// \brief Remove the built instruction.
3161     void undo() override {
3162       DEBUG(dbgs() << "Undo: ZExtBuilder: " << *Val << "\n");
3163       if (Instruction *IVal = dyn_cast<Instruction>(Val))
3164         IVal->eraseFromParent();
3165     }
3166   };
3167
3168   /// \brief Mutate an instruction to another type.
3169   class TypeMutator : public TypePromotionAction {
3170     /// Record the original type.
3171     Type *OrigTy;
3172
3173   public:
3174     /// \brief Mutate the type of \p Inst into \p NewTy.
3175     TypeMutator(Instruction *Inst, Type *NewTy)
3176         : TypePromotionAction(Inst), OrigTy(Inst->getType()) {
3177       DEBUG(dbgs() << "Do: MutateType: " << *Inst << " with " << *NewTy
3178                    << "\n");
3179       Inst->mutateType(NewTy);
3180     }
3181
3182     /// \brief Mutate the instruction back to its original type.
3183     void undo() override {
3184       DEBUG(dbgs() << "Undo: MutateType: " << *Inst << " with " << *OrigTy
3185                    << "\n");
3186       Inst->mutateType(OrigTy);
3187     }
3188   };
3189
3190   /// \brief Replace the uses of an instruction by another instruction.
3191   class UsesReplacer : public TypePromotionAction {
3192     /// Helper structure to keep track of the replaced uses.
3193     struct InstructionAndIdx {
3194       /// The instruction using the instruction.
3195       Instruction *Inst;
3196       /// The index where this instruction is used for Inst.
3197       unsigned Idx;
3198       InstructionAndIdx(Instruction *Inst, unsigned Idx)
3199           : Inst(Inst), Idx(Idx) {}
3200     };
3201
3202     /// Keep track of the original uses (pair Instruction, Index).
3203     SmallVector<InstructionAndIdx, 4> OriginalUses;
3204     typedef SmallVectorImpl<InstructionAndIdx>::iterator use_iterator;
3205
3206   public:
3207     /// \brief Replace all the use of \p Inst by \p New.
3208     UsesReplacer(Instruction *Inst, Value *New) : TypePromotionAction(Inst) {
3209       DEBUG(dbgs() << "Do: UsersReplacer: " << *Inst << " with " << *New
3210                    << "\n");
3211       // Record the original uses.
3212       for (Use &U : Inst->uses()) {
3213         Instruction *UserI = cast<Instruction>(U.getUser());
3214         OriginalUses.push_back(InstructionAndIdx(UserI, U.getOperandNo()));
3215       }
3216       // Now, we can replace the uses.
3217       Inst->replaceAllUsesWith(New);
3218     }
3219
3220     /// \brief Reassign the original uses of Inst to Inst.
3221     void undo() override {
3222       DEBUG(dbgs() << "Undo: UsersReplacer: " << *Inst << "\n");
3223       for (use_iterator UseIt = OriginalUses.begin(),
3224                         EndIt = OriginalUses.end();
3225            UseIt != EndIt; ++UseIt) {
3226         UseIt->Inst->setOperand(UseIt->Idx, Inst);
3227       }
3228     }
3229   };
3230
3231   /// \brief Remove an instruction from the IR.
3232   class InstructionRemover : public TypePromotionAction {
3233     /// Original position of the instruction.
3234     InsertionHandler Inserter;
3235     /// Helper structure to hide all the link to the instruction. In other
3236     /// words, this helps to do as if the instruction was removed.
3237     OperandsHider Hider;
3238     /// Keep track of the uses replaced, if any.
3239     UsesReplacer *Replacer;
3240
3241   public:
3242     /// \brief Remove all reference of \p Inst and optinally replace all its
3243     /// uses with New.
3244     /// \pre If !Inst->use_empty(), then New != nullptr
3245     InstructionRemover(Instruction *Inst, Value *New = nullptr)
3246         : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3247           Replacer(nullptr) {
3248       if (New)
3249         Replacer = new UsesReplacer(Inst, New);
3250       DEBUG(dbgs() << "Do: InstructionRemover: " << *Inst << "\n");
3251       Inst->removeFromParent();
3252     }
3253
3254     ~InstructionRemover() override { delete Replacer; }
3255
3256     /// \brief Really remove the instruction.
3257     void commit() override { delete Inst; }
3258
3259     /// \brief Resurrect the instruction and reassign it to the proper uses if
3260     /// new value was provided when build this action.
3261     void undo() override {
3262       DEBUG(dbgs() << "Undo: InstructionRemover: " << *Inst << "\n");
3263       Inserter.insert(Inst);
3264       if (Replacer)
3265         Replacer->undo();
3266       Hider.undo();
3267     }
3268   };
3269
3270 public:
3271   /// Restoration point.
3272   /// The restoration point is a pointer to an action instead of an iterator
3273   /// because the iterator may be invalidated but not the pointer.
3274   typedef const TypePromotionAction *ConstRestorationPt;
3275   /// Advocate every changes made in that transaction.
3276   void commit();
3277   /// Undo all the changes made after the given point.
3278   void rollback(ConstRestorationPt Point);
3279   /// Get the current restoration point.
3280   ConstRestorationPt getRestorationPoint() const;
3281
3282   /// \name API for IR modification with state keeping to support rollback.
3283   /// @{
3284   /// Same as Instruction::setOperand.
3285   void setOperand(Instruction *Inst, unsigned Idx, Value *NewVal);
3286   /// Same as Instruction::eraseFromParent.
3287   void eraseInstruction(Instruction *Inst, Value *NewVal = nullptr);
3288   /// Same as Value::replaceAllUsesWith.
3289   void replaceAllUsesWith(Instruction *Inst, Value *New);
3290   /// Same as Value::mutateType.
3291   void mutateType(Instruction *Inst, Type *NewTy);
3292   /// Same as IRBuilder::createTrunc.
3293   Value *createTrunc(Instruction *Opnd, Type *Ty);
3294   /// Same as IRBuilder::createSExt.
3295   Value *createSExt(Instruction *Inst, Value *Opnd, Type *Ty);
3296   /// Same as IRBuilder::createZExt.
3297   Value *createZExt(Instruction *Inst, Value *Opnd, Type *Ty);
3298   /// Same as Instruction::moveBefore.
3299   void moveBefore(Instruction *Inst, Instruction *Before);
3300   /// @}
3301
3302 private:
3303   /// The ordered list of actions made so far.
3304   SmallVector<std::unique_ptr<TypePromotionAction>, 16> Actions;
3305   typedef SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator CommitPt;
3306 };
3307
3308 void TypePromotionTransaction::setOperand(Instruction *Inst, unsigned Idx,
3309                                           Value *NewVal) {
3310   Actions.push_back(
3311       make_unique<TypePromotionTransaction::OperandSetter>(Inst, Idx, NewVal));
3312 }
3313
3314 void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
3315                                                 Value *NewVal) {
3316   Actions.push_back(
3317       make_unique<TypePromotionTransaction::InstructionRemover>(Inst, NewVal));
3318 }
3319
3320 void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
3321                                                   Value *New) {
3322   Actions.push_back(make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3323 }
3324
3325 void TypePromotionTransaction::mutateType(Instruction *Inst, Type *NewTy) {
3326   Actions.push_back(make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3327 }
3328
3329 Value *TypePromotionTransaction::createTrunc(Instruction *Opnd,
3330                                              Type *Ty) {
3331   std::unique_ptr<TruncBuilder> Ptr(new TruncBuilder(Opnd, Ty));
3332   Value *Val = Ptr->getBuiltValue();
3333   Actions.push_back(std::move(Ptr));
3334   return Val;
3335 }
3336
3337 Value *TypePromotionTransaction::createSExt(Instruction *Inst,
3338                                             Value *Opnd, Type *Ty) {
3339   std::unique_ptr<SExtBuilder> Ptr(new SExtBuilder(Inst, Opnd, Ty));
3340   Value *Val = Ptr->getBuiltValue();
3341   Actions.push_back(std::move(Ptr));
3342   return Val;
3343 }
3344
3345 Value *TypePromotionTransaction::createZExt(Instruction *Inst,
3346                                             Value *Opnd, Type *Ty) {
3347   std::unique_ptr<ZExtBuilder> Ptr(new ZExtBuilder(Inst, Opnd, Ty));
3348   Value *Val = Ptr->getBuiltValue();
3349   Actions.push_back(std::move(Ptr));
3350   return Val;
3351 }
3352
3353 void TypePromotionTransaction::moveBefore(Instruction *Inst,
3354                                           Instruction *Before) {
3355   Actions.push_back(
3356       make_unique<TypePromotionTransaction::InstructionMoveBefore>(Inst, Before));
3357 }
3358
3359 TypePromotionTransaction::ConstRestorationPt
3360 TypePromotionTransaction::getRestorationPoint() const {
3361   return !Actions.empty() ? Actions.back().get() : nullptr;
3362 }
3363
3364 void TypePromotionTransaction::commit() {
3365   for (CommitPt It = Actions.begin(), EndIt = Actions.end(); It != EndIt;
3366        ++It)
3367     (*It)->commit();
3368   Actions.clear();
3369 }
3370
3371 void TypePromotionTransaction::rollback(
3372     TypePromotionTransaction::ConstRestorationPt Point) {
3373   while (!Actions.empty() && Point != Actions.back().get()) {
3374     std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3375     Curr->undo();
3376   }
3377 }
3378
3379 /// \brief A helper class for matching addressing modes.
3380 ///
3381 /// This encapsulates the logic for matching the target-legal addressing modes.
3382 class AddressingModeMatcher {
3383   SmallVectorImpl<Instruction*> &AddrModeInsts;
3384   const TargetMachine &TM;
3385   const TargetLowering &TLI;
3386   const DataLayout &DL;
3387
3388   /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and
3389   /// the memory instruction that we're computing this address for.
3390   Type *AccessTy;
3391   unsigned AddrSpace;
3392   Instruction *MemoryInst;
3393
3394   /// This is the addressing mode that we're building up. This is
3395   /// part of the return value of this addressing mode matching stuff.
3396   ExtAddrMode &AddrMode;
3397
3398   /// The instructions inserted by other CodeGenPrepare optimizations.
3399   const SetOfInstrs &InsertedInsts;
3400   /// A map from the instructions to their type before promotion.
3401   InstrToOrigTy &PromotedInsts;
3402   /// The ongoing transaction where every action should be registered.
3403   TypePromotionTransaction &TPT;
3404
3405   /// This is set to true when we should not do profitability checks.
3406   /// When true, IsProfitableToFoldIntoAddressingMode always returns true.
3407   bool IgnoreProfitability;
3408
3409   AddressingModeMatcher(SmallVectorImpl<Instruction *> &AMI,
3410                         const TargetMachine &TM, Type *AT, unsigned AS,
3411                         Instruction *MI, ExtAddrMode &AM,
3412                         const SetOfInstrs &InsertedInsts,
3413                         InstrToOrigTy &PromotedInsts,
3414                         TypePromotionTransaction &TPT)
3415       : AddrModeInsts(AMI), TM(TM),
3416         TLI(*TM.getSubtargetImpl(*MI->getParent()->getParent())
3417                  ->getTargetLowering()),
3418         DL(MI->getModule()->getDataLayout()), AccessTy(AT), AddrSpace(AS),
3419         MemoryInst(MI), AddrMode(AM), InsertedInsts(InsertedInsts),
3420         PromotedInsts(PromotedInsts), TPT(TPT) {
3421     IgnoreProfitability = false;
3422   }
3423 public:
3424
3425   /// Find the maximal addressing mode that a load/store of V can fold,
3426   /// give an access type of AccessTy.  This returns a list of involved
3427   /// instructions in AddrModeInsts.
3428   /// \p InsertedInsts The instructions inserted by other CodeGenPrepare
3429   /// optimizations.
3430   /// \p PromotedInsts maps the instructions to their type before promotion.
3431   /// \p The ongoing transaction where every action should be registered.
3432   static ExtAddrMode Match(Value *V, Type *AccessTy, unsigned AS,
3433                            Instruction *MemoryInst,
3434                            SmallVectorImpl<Instruction*> &AddrModeInsts,
3435                            const TargetMachine &TM,
3436                            const SetOfInstrs &InsertedInsts,
3437                            InstrToOrigTy &PromotedInsts,
3438                            TypePromotionTransaction &TPT) {
3439     ExtAddrMode Result;
3440
3441     bool Success = AddressingModeMatcher(AddrModeInsts, TM, AccessTy, AS,
3442                                          MemoryInst, Result, InsertedInsts,
3443                                          PromotedInsts, TPT).matchAddr(V, 0);
3444     (void)Success; assert(Success && "Couldn't select *anything*?");
3445     return Result;
3446   }
3447 private:
3448   bool matchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth);
3449   bool matchAddr(Value *V, unsigned Depth);
3450   bool matchOperationAddr(User *Operation, unsigned Opcode, unsigned Depth,
3451                           bool *MovedAway = nullptr);
3452   bool isProfitableToFoldIntoAddressingMode(Instruction *I,
3453                                             ExtAddrMode &AMBefore,
3454                                             ExtAddrMode &AMAfter);
3455   bool valueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
3456   bool isPromotionProfitable(unsigned NewCost, unsigned OldCost,
3457                              Value *PromotedOperand) const;
3458 };
3459
3460 /// Try adding ScaleReg*Scale to the current addressing mode.
3461 /// Return true and update AddrMode if this addr mode is legal for the target,
3462 /// false if not.
3463 bool AddressingModeMatcher::matchScaledValue(Value *ScaleReg, int64_t Scale,
3464                                              unsigned Depth) {
3465   // If Scale is 1, then this is the same as adding ScaleReg to the addressing
3466   // mode.  Just process that directly.
3467   if (Scale == 1)
3468     return matchAddr(ScaleReg, Depth);
3469
3470   // If the scale is 0, it takes nothing to add this.
3471   if (Scale == 0)
3472     return true;
3473
3474   // If we already have a scale of this value, we can add to it, otherwise, we
3475   // need an available scale field.
3476   if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg)
3477     return false;
3478
3479   ExtAddrMode TestAddrMode = AddrMode;
3480
3481   // Add scale to turn X*4+X*3 -> X*7.  This could also do things like
3482   // [A+B + A*7] -> [B+A*8].
3483   TestAddrMode.Scale += Scale;
3484   TestAddrMode.ScaledReg = ScaleReg;
3485
3486   // If the new address isn't legal, bail out.
3487   if (!TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace))
3488     return false;
3489
3490   // It was legal, so commit it.
3491   AddrMode = TestAddrMode;
3492
3493   // Okay, we decided that we can add ScaleReg+Scale to AddrMode.  Check now
3494   // to see if ScaleReg is actually X+C.  If so, we can turn this into adding
3495   // X*Scale + C*Scale to addr mode.
3496   ConstantInt *CI = nullptr; Value *AddLHS = nullptr;
3497   if (isa<Instruction>(ScaleReg) &&  // not a constant expr.
3498       match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) {
3499     TestAddrMode.ScaledReg = AddLHS;
3500     TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale;
3501
3502     // If this addressing mode is legal, commit it and remember that we folded
3503     // this instruction.
3504     if (TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace)) {
3505       AddrModeInsts.push_back(cast<Instruction>(ScaleReg));
3506       AddrMode = TestAddrMode;
3507       return true;
3508     }
3509   }
3510
3511   // Otherwise, not (x+c)*scale, just return what we have.
3512   return true;
3513 }
3514
3515 /// This is a little filter, which returns true if an addressing computation
3516 /// involving I might be folded into a load/store accessing it.
3517 /// This doesn't need to be perfect, but needs to accept at least
3518 /// the set of instructions that MatchOperationAddr can.
3519 static bool MightBeFoldableInst(Instruction *I) {
3520   switch (I->getOpcode()) {
3521   case Instruction::BitCast:
3522   case Instruction::AddrSpaceCast:
3523     // Don't touch identity bitcasts.
3524     if (I->getType() == I->getOperand(0)->getType())
3525       return false;
3526     return I->getType()->isPointerTy() || I->getType()->isIntegerTy();
3527   case Instruction::PtrToInt:
3528     // PtrToInt is always a noop, as we know that the int type is pointer sized.
3529     return true;
3530   case Instruction::IntToPtr:
3531     // We know the input is intptr_t, so this is foldable.
3532     return true;
3533   case Instruction::Add:
3534     return true;
3535   case Instruction::Mul:
3536   case Instruction::Shl:
3537     // Can only handle X*C and X << C.
3538     return isa<ConstantInt>(I->getOperand(1));
3539   case Instruction::GetElementPtr:
3540     return true;
3541   default:
3542     return false;
3543   }
3544 }
3545
3546 /// \brief Check whether or not \p Val is a legal instruction for \p TLI.
3547 /// \note \p Val is assumed to be the product of some type promotion.
3548 /// Therefore if \p Val has an undefined state in \p TLI, this is assumed
3549 /// to be legal, as the non-promoted value would have had the same state.
3550 static bool isPromotedInstructionLegal(const TargetLowering &TLI,
3551                                        const DataLayout &DL, Value *Val) {
3552   Instruction *PromotedInst = dyn_cast<Instruction>(Val);
3553   if (!PromotedInst)
3554     return false;
3555   int ISDOpcode = TLI.InstructionOpcodeToISD(PromotedInst->getOpcode());
3556   // If the ISDOpcode is undefined, it was undefined before the promotion.
3557   if (!ISDOpcode)
3558     return true;
3559   // Otherwise, check if the promoted instruction is legal or not.
3560   return TLI.isOperationLegalOrCustom(
3561       ISDOpcode, TLI.getValueType(DL, PromotedInst->getType()));
3562 }
3563
3564 /// \brief Hepler class to perform type promotion.
3565 class TypePromotionHelper {
3566   /// \brief Utility function to check whether or not a sign or zero extension
3567   /// of \p Inst with \p ConsideredExtType can be moved through \p Inst by
3568   /// either using the operands of \p Inst or promoting \p Inst.
3569   /// The type of the extension is defined by \p IsSExt.
3570   /// In other words, check if:
3571   /// ext (Ty Inst opnd1 opnd2 ... opndN) to ConsideredExtType.
3572   /// #1 Promotion applies:
3573   /// ConsideredExtType Inst (ext opnd1 to ConsideredExtType, ...).
3574   /// #2 Operand reuses:
3575   /// ext opnd1 to ConsideredExtType.
3576   /// \p PromotedInsts maps the instructions to their type before promotion.
3577   static bool canGetThrough(const Instruction *Inst, Type *ConsideredExtType,
3578                             const InstrToOrigTy &PromotedInsts, bool IsSExt);
3579
3580   /// \brief Utility function to determine if \p OpIdx should be promoted when
3581   /// promoting \p Inst.
3582   static bool shouldExtOperand(const Instruction *Inst, int OpIdx) {
3583     return !(isa<SelectInst>(Inst) && OpIdx == 0);
3584   }
3585
3586   /// \brief Utility function to promote the operand of \p Ext when this
3587   /// operand is a promotable trunc or sext or zext.
3588   /// \p PromotedInsts maps the instructions to their type before promotion.
3589   /// \p CreatedInstsCost[out] contains the cost of all instructions
3590   /// created to promote the operand of Ext.
3591   /// Newly added extensions are inserted in \p Exts.
3592   /// Newly added truncates are inserted in \p Truncs.
3593   /// Should never be called directly.
3594   /// \return The promoted value which is used instead of Ext.
3595   static Value *promoteOperandForTruncAndAnyExt(
3596       Instruction *Ext, TypePromotionTransaction &TPT,
3597       InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
3598       SmallVectorImpl<Instruction *> *Exts,
3599       SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI);
3600
3601   /// \brief Utility function to promote the operand of \p Ext when this
3602   /// operand is promotable and is not a supported trunc or sext.
3603   /// \p PromotedInsts maps the instructions to their type before promotion.
3604   /// \p CreatedInstsCost[out] contains the cost of all the instructions
3605   /// created to promote the operand of Ext.
3606   /// Newly added extensions are inserted in \p Exts.
3607   /// Newly added truncates are inserted in \p Truncs.
3608   /// Should never be called directly.
3609   /// \return The promoted value which is used instead of Ext.
3610   static Value *promoteOperandForOther(Instruction *Ext,
3611                                        TypePromotionTransaction &TPT,
3612                                        InstrToOrigTy &PromotedInsts,
3613                                        unsigned &CreatedInstsCost,
3614                                        SmallVectorImpl<Instruction *> *Exts,
3615                                        SmallVectorImpl<Instruction *> *Truncs,
3616                                        const TargetLowering &TLI, bool IsSExt);
3617
3618   /// \see promoteOperandForOther.
3619   static Value *signExtendOperandForOther(
3620       Instruction *Ext, TypePromotionTransaction &TPT,
3621       InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
3622       SmallVectorImpl<Instruction *> *Exts,
3623       SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
3624     return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
3625                                   Exts, Truncs, TLI, true);
3626   }
3627
3628   /// \see promoteOperandForOther.
3629   static Value *zeroExtendOperandForOther(
3630       Instruction *Ext, TypePromotionTransaction &TPT,
3631       InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
3632       SmallVectorImpl<Instruction *> *Exts,
3633       SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
3634     return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
3635                                   Exts, Truncs, TLI, false);
3636   }
3637
3638 public:
3639   /// Type for the utility function that promotes the operand of Ext.
3640   typedef Value *(*Action)(Instruction *Ext, TypePromotionTransaction &TPT,
3641                            InstrToOrigTy &PromotedInsts,
3642                            unsigned &CreatedInstsCost,
3643                            SmallVectorImpl<Instruction *> *Exts,
3644                            SmallVectorImpl<Instruction *> *Truncs,
3645                            const TargetLowering &TLI);
3646   /// \brief Given a sign/zero extend instruction \p Ext, return the approriate
3647   /// action to promote the operand of \p Ext instead of using Ext.
3648   /// \return NULL if no promotable action is possible with the current
3649   /// sign extension.
3650   /// \p InsertedInsts keeps track of all the instructions inserted by the
3651   /// other CodeGenPrepare optimizations. This information is important
3652   /// because we do not want to promote these instructions as CodeGenPrepare
3653   /// will reinsert them later. Thus creating an infinite loop: create/remove.
3654   /// \p PromotedInsts maps the instructions to their type before promotion.
3655   static Action getAction(Instruction *Ext, const SetOfInstrs &InsertedInsts,
3656                           const TargetLowering &TLI,
3657                           const InstrToOrigTy &PromotedInsts);
3658 };
3659
3660 bool TypePromotionHelper::canGetThrough(const Instruction *Inst,
3661                                         Type *ConsideredExtType,
3662                                         const InstrToOrigTy &PromotedInsts,
3663                                         bool IsSExt) {
3664   // The promotion helper does not know how to deal with vector types yet.
3665   // To be able to fix that, we would need to fix the places where we
3666   // statically extend, e.g., constants and such.
3667   if (Inst->getType()->isVectorTy())
3668     return false;
3669
3670   // We can always get through zext.
3671   if (isa<ZExtInst>(Inst))
3672     return true;
3673
3674   // sext(sext) is ok too.
3675   if (IsSExt && isa<SExtInst>(Inst))
3676     return true;
3677
3678   // We can get through binary operator, if it is legal. In other words, the
3679   // binary operator must have a nuw or nsw flag.
3680   const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
3681   if (BinOp && isa<OverflowingBinaryOperator>(BinOp) &&
3682       ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
3683        (IsSExt && BinOp->hasNoSignedWrap())))
3684     return true;
3685
3686   // Check if we can do the following simplification.
3687   // ext(trunc(opnd)) --> ext(opnd)
3688   if (!isa<TruncInst>(Inst))
3689     return false;
3690
3691   Value *OpndVal = Inst->getOperand(0);
3692   // Check if we can use this operand in the extension.
3693   // If the type is larger than the result type of the extension, we cannot.
3694   if (!OpndVal->getType()->isIntegerTy() ||
3695       OpndVal->getType()->getIntegerBitWidth() >
3696           ConsideredExtType->getIntegerBitWidth())
3697     return false;
3698
3699   // If the operand of the truncate is not an instruction, we will not have
3700   // any information on the dropped bits.
3701   // (Actually we could for constant but it is not worth the extra logic).
3702   Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
3703   if (!Opnd)
3704     return false;
3705
3706   // Check if the source of the type is narrow enough.
3707   // I.e., check that trunc just drops extended bits of the same kind of
3708   // the extension.
3709   // #1 get the type of the operand and check the kind of the extended bits.
3710   const Type *OpndType;
3711   InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
3712   if (It != PromotedInsts.end() && It->second.getInt() == IsSExt)
3713     OpndType = It->second.getPointer();
3714   else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
3715     OpndType = Opnd->getOperand(0)->getType();
3716   else
3717     return false;
3718
3719   // #2 check that the truncate just drops extended bits.
3720   return Inst->getType()->getIntegerBitWidth() >=
3721          OpndType->getIntegerBitWidth();
3722 }
3723
3724 TypePromotionHelper::Action TypePromotionHelper::getAction(
3725     Instruction *Ext, const SetOfInstrs &InsertedInsts,
3726     const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts) {
3727   assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
3728          "Unexpected instruction type");
3729   Instruction *ExtOpnd = dyn_cast<Instruction>(Ext->getOperand(0));
3730   Type *ExtTy = Ext->getType();
3731   bool IsSExt = isa<SExtInst>(Ext);
3732   // If the operand of the extension is not an instruction, we cannot
3733   // get through.
3734   // If it, check we can get through.
3735   if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
3736     return nullptr;
3737
3738   // Do not promote if the operand has been added by codegenprepare.
3739   // Otherwise, it means we are undoing an optimization that is likely to be
3740   // redone, thus causing potential infinite loop.
3741   if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd))
3742     return nullptr;
3743
3744   // SExt or Trunc instructions.
3745   // Return the related handler.
3746   if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
3747       isa<ZExtInst>(ExtOpnd))
3748     return promoteOperandForTruncAndAnyExt;
3749
3750   // Regular instruction.
3751   // Abort early if we will have to insert non-free instructions.
3752   if (!ExtOpnd->hasOneUse() && !TLI.isTruncateFree(ExtTy, ExtOpnd->getType()))
3753     return nullptr;
3754   return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
3755 }
3756
3757 Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
3758     llvm::Instruction *SExt, TypePromotionTransaction &TPT,
3759     InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
3760     SmallVectorImpl<Instruction *> *Exts,
3761     SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) {
3762   // By construction, the operand of SExt is an instruction. Otherwise we cannot
3763   // get through it and this method should not be called.
3764   Instruction *SExtOpnd = cast<Instruction>(SExt->getOperand(0));
3765   Value *ExtVal = SExt;
3766   bool HasMergedNonFreeExt = false;
3767   if (isa<ZExtInst>(SExtOpnd)) {
3768     // Replace s|zext(zext(opnd))
3769     // => zext(opnd).
3770     HasMergedNonFreeExt = !TLI.isExtFree(SExtOpnd);
3771     Value *ZExt =
3772         TPT.createZExt(SExt, SExtOpnd->getOperand(0), SExt->getType());
3773     TPT.replaceAllUsesWith(SExt, ZExt);
3774     TPT.eraseInstruction(SExt);
3775     ExtVal = ZExt;
3776   } else {
3777     // Replace z|sext(trunc(opnd)) or sext(sext(opnd))
3778     // => z|sext(opnd).
3779     TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0));
3780   }
3781   CreatedInstsCost = 0;
3782
3783   // Remove dead code.
3784   if (SExtOpnd->use_empty())
3785     TPT.eraseInstruction(SExtOpnd);
3786
3787   // Check if the extension is still needed.
3788   Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
3789   if (!ExtInst || ExtInst->getType() != ExtInst->getOperand(0)->getType()) {
3790     if (ExtInst) {
3791       if (Exts)
3792         Exts->push_back(ExtInst);
3793       CreatedInstsCost = !TLI.isExtFree(ExtInst) && !HasMergedNonFreeExt;
3794     }
3795     return ExtVal;
3796   }
3797
3798   // At this point we have: ext ty opnd to ty.
3799   // Reassign the uses of ExtInst to the opnd and remove ExtInst.
3800   Value *NextVal = ExtInst->getOperand(0);
3801   TPT.eraseInstruction(ExtInst, NextVal);
3802   return NextVal;
3803 }
3804
3805 Value *TypePromotionHelper::promoteOperandForOther(
3806     Instruction *Ext, TypePromotionTransaction &TPT,
3807     InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost,
3808     SmallVectorImpl<Instruction *> *Exts,
3809     SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI,
3810     bool IsSExt) {
3811   // By construction, the operand of Ext is an instruction. Otherwise we cannot
3812   // get through it and this method should not be called.
3813   Instruction *ExtOpnd = cast<Instruction>(Ext->getOperand(0));
3814   CreatedInstsCost = 0;
3815   if (!ExtOpnd->hasOneUse()) {
3816     // ExtOpnd will be promoted.
3817     // All its uses, but Ext, will need to use a truncated value of the
3818     // promoted version.
3819     // Create the truncate now.
3820     Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->getType());
3821     if (Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
3822       ITrunc->removeFromParent();
3823       // Insert it just after the definition.
3824       ITrunc->insertAfter(ExtOpnd);
3825       if (Truncs)
3826         Truncs->push_back(ITrunc);
3827     }
3828
3829     TPT.replaceAllUsesWith(ExtOpnd, Trunc);
3830     // Restore the operand of Ext (which has been replaced by the previous call
3831     // to replaceAllUsesWith) to avoid creating a cycle trunc <-> sext.
3832     TPT.setOperand(Ext, 0, ExtOpnd);
3833   }
3834
3835   // Get through the Instruction:
3836   // 1. Update its type.
3837   // 2. Replace the uses of Ext by Inst.
3838   // 3. Extend each operand that needs to be extended.
3839
3840   // Remember the original type of the instruction before promotion.
3841   // This is useful to know that the high bits are sign extended bits.
3842   PromotedInsts.insert(std::pair<Instruction *, TypeIsSExt>(
3843       ExtOpnd, TypeIsSExt(ExtOpnd->getType(), IsSExt)));
3844   // Step #1.
3845   TPT.mutateType(ExtOpnd, Ext->getType());
3846   // Step #2.
3847   TPT.replaceAllUsesWith(Ext, ExtOpnd);
3848   // Step #3.
3849   Instruction *ExtForOpnd = Ext;
3850
3851   DEBUG(dbgs() << "Propagate Ext to operands\n");
3852   for (int OpIdx = 0, EndOpIdx = ExtOpnd->getNumOperands(); OpIdx != EndOpIdx;
3853        ++OpIdx) {
3854     DEBUG(dbgs() << "Operand:\n" << *(ExtOpnd->getOperand(OpIdx)) << '\n');
3855     if (ExtOpnd->getOperand(OpIdx)->getType() == Ext->getType() ||
3856         !shouldExtOperand(ExtOpnd, OpIdx)) {
3857       DEBUG(dbgs() << "No need to propagate\n");
3858       continue;
3859     }
3860     // Check if we can statically extend the operand.
3861     Value *Opnd = ExtOpnd->getOperand(OpIdx);
3862     if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
3863       DEBUG(dbgs() << "Statically extend\n");
3864       unsigned BitWidth = Ext->getType()->getIntegerBitWidth();
3865       APInt CstVal = IsSExt ? Cst->getValue().sext(BitWidth)
3866                             : Cst->getValue().zext(BitWidth);
3867       TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(Ext->getType(), CstVal));
3868       continue;
3869     }
3870     // UndefValue are typed, so we have to statically sign extend them.
3871     if (isa<UndefValue>(Opnd)) {
3872       DEBUG(dbgs() << "Statically extend\n");
3873       TPT.setOperand(ExtOpnd, OpIdx, UndefValue::get(Ext->getType()));
3874       continue;
3875     }
3876
3877     // Otherwise we have to explicity sign extend the operand.
3878     // Check if Ext was reused to extend an operand.
3879     if (!ExtForOpnd) {
3880       // If yes, create a new one.
3881       DEBUG(dbgs() << "More operands to ext\n");
3882       Value *ValForExtOpnd = IsSExt ? TPT.createSExt(Ext, Opnd, Ext->getType())
3883         : TPT.createZExt(Ext, Opnd, Ext->getType());
3884       if (!isa<Instruction>(ValForExtOpnd)) {
3885         TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
3886         continue;
3887       }
3888       ExtForOpnd = cast<Instruction>(ValForExtOpnd);
3889     }
3890     if (Exts)
3891       Exts->push_back(ExtForOpnd);
3892     TPT.setOperand(ExtForOpnd, 0, Opnd);
3893
3894     // Move the sign extension before the insertion point.
3895     TPT.moveBefore(ExtForOpnd, ExtOpnd);
3896     TPT.setOperand(ExtOpnd, OpIdx, ExtForOpnd);
3897     CreatedInstsCost += !TLI.isExtFree(ExtForOpnd);
3898     // If more sext are required, new instructions will have to be created.
3899     ExtForOpnd = nullptr;
3900   }
3901   if (ExtForOpnd == Ext) {
3902     DEBUG(dbgs() << "Extension is useless now\n");
3903     TPT.eraseInstruction(Ext);
3904   }
3905   return ExtOpnd;
3906 }
3907
3908 /// Check whether or not promoting an instruction to a wider type is profitable.
3909 /// \p NewCost gives the cost of extension instructions created by the
3910 /// promotion.
3911 /// \p OldCost gives the cost of extension instructions before the promotion
3912 /// plus the number of instructions that have been
3913 /// matched in the addressing mode the promotion.
3914 /// \p PromotedOperand is the value that has been promoted.
3915 /// \return True if the promotion is profitable, false otherwise.
3916 bool AddressingModeMatcher::isPromotionProfitable(
3917     unsigned NewCost, unsigned OldCost, Value *PromotedOperand) const {
3918   DEBUG(dbgs() << "OldCost: " << OldCost << "\tNewCost: " << NewCost << '\n');
3919   // The cost of the new extensions is greater than the cost of the
3920   // old extension plus what we folded.
3921   // This is not profitable.
3922   if (NewCost > OldCost)
3923     return false;
3924   if (NewCost < OldCost)
3925     return true;
3926   // The promotion is neutral but it may help folding the sign extension in
3927   // loads for instance.
3928   // Check that we did not create an illegal instruction.
3929   return isPromotedInstructionLegal(TLI, DL, PromotedOperand);
3930 }
3931
3932 /// Given an instruction or constant expr, see if we can fold the operation
3933 /// into the addressing mode. If so, update the addressing mode and return
3934 /// true, otherwise return false without modifying AddrMode.
3935 /// If \p MovedAway is not NULL, it contains the information of whether or
3936 /// not AddrInst has to be folded into the addressing mode on success.
3937 /// If \p MovedAway == true, \p AddrInst will not be part of the addressing
3938 /// because it has been moved away.
3939 /// Thus AddrInst must not be added in the matched instructions.
3940 /// This state can happen when AddrInst is a sext, since it may be moved away.
3941 /// Therefore, AddrInst may not be valid when MovedAway is true and it must
3942 /// not be referenced anymore.
3943 bool AddressingModeMatcher::matchOperationAddr(User *AddrInst, unsigned Opcode,
3944                                                unsigned Depth,
3945                                                bool *MovedAway) {
3946   // Avoid exponential behavior on extremely deep expression trees.
3947   if (Depth >= 5) return false;
3948
3949   // By default, all matched instructions stay in place.
3950   if (MovedAway)
3951     *MovedAway = false;
3952
3953   switch (Opcode) {
3954   case Instruction::PtrToInt:
3955     // PtrToInt is always a noop, as we know that the int type is pointer sized.
3956     return matchAddr(AddrInst->getOperand(0), Depth);
3957   case Instruction::IntToPtr: {
3958     auto AS = AddrInst->getType()->getPointerAddressSpace();
3959     auto PtrTy = MVT::getIntegerVT(DL.getPointerSizeInBits(AS));
3960     // This inttoptr is a no-op if the integer type is pointer sized.
3961     if (TLI.getValueType(DL, AddrInst->getOperand(0)->getType()) == PtrTy)
3962       return matchAddr(AddrInst->getOperand(0), Depth);
3963     return false;
3964   }
3965   case Instruction::BitCast:
3966     // BitCast is always a noop, and we can handle it as long as it is
3967     // int->int or pointer->pointer (we don't want int<->fp or something).
3968     if ((AddrInst->getOperand(0)->getType()->isPointerTy() ||
3969          AddrInst->getOperand(0)->getType()->isIntegerTy()) &&
3970         // Don't touch identity bitcasts.  These were probably put here by LSR,
3971         // and we don't want to mess around with them.  Assume it knows what it
3972         // is doing.
3973         AddrInst->getOperand(0)->getType() != AddrInst->getType())
3974       return matchAddr(AddrInst->getOperand(0), Depth);
3975     return false;
3976   case Instruction::AddrSpaceCast: {
3977     unsigned SrcAS
3978       = AddrInst->getOperand(0)->getType()->getPointerAddressSpace();
3979     unsigned DestAS = AddrInst->getType()->getPointerAddressSpace();
3980     if (TLI.isNoopAddrSpaceCast(SrcAS, DestAS))
3981       return matchAddr(AddrInst->getOperand(0), Depth);
3982     return false;
3983   }
3984   case Instruction::Add: {
3985     // Check to see if we can merge in the RHS then the LHS.  If so, we win.
3986     ExtAddrMode BackupAddrMode = AddrMode;
3987     unsigned OldSize = AddrModeInsts.size();
3988     // Start a transaction at this point.
3989     // The LHS may match but not the RHS.
3990     // Therefore, we need a higher level restoration point to undo partially
3991     // matched operation.
3992     TypePromotionTransaction::ConstRestorationPt LastKnownGood =
3993         TPT.getRestorationPoint();
3994
3995     if (matchAddr(AddrInst->getOperand(1), Depth+1) &&
3996         matchAddr(AddrInst->getOperand(0), Depth+1))
3997       return true;
3998
3999     // Restore the old addr mode info.
4000     AddrMode = BackupAddrMode;
4001     AddrModeInsts.resize(OldSize);
4002     TPT.rollback(LastKnownGood);
4003
4004     // Otherwise this was over-aggressive.  Try merging in the LHS then the RHS.
4005     if (matchAddr(AddrInst->getOperand(0), Depth+1) &&
4006         matchAddr(AddrInst->getOperand(1), Depth+1))
4007       return true;
4008
4009     // Otherwise we definitely can't merge the ADD in.
4010     AddrMode = BackupAddrMode;
4011     AddrModeInsts.resize(OldSize);
4012     TPT.rollback(LastKnownGood);
4013     break;
4014   }
4015   //case Instruction::Or:
4016   // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD.
4017   //break;
4018   case Instruction::Mul:
4019   case Instruction::Shl: {
4020     // Can only handle X*C and X << C.
4021     ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1));
4022     if (!RHS)
4023       return false;
4024     int64_t Scale = RHS->getSExtValue();
4025     if (Opcode == Instruction::Shl)
4026       Scale = 1LL << Scale;
4027
4028     return matchScaledValue(AddrInst->getOperand(0), Scale, Depth);
4029   }
4030   case Instruction::GetElementPtr: {
4031     // Scan the GEP.  We check it if it contains constant offsets and at most
4032     // one variable offset.
4033     int VariableOperand = -1;
4034     unsigned VariableScale = 0;
4035
4036     int64_t ConstantOffset = 0;
4037     gep_type_iterator GTI = gep_type_begin(AddrInst);
4038     for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) {
4039       if (StructType *STy = dyn_cast<StructType>(*GTI)) {
4040         const StructLayout *SL = DL.getStructLayout(STy);
4041         unsigned Idx =
4042           cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue();
4043         ConstantOffset += SL->getElementOffset(Idx);
4044       } else {
4045         uint64_t TypeSize = DL.getTypeAllocSize(GTI.getIndexedType());
4046         if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) {
4047           ConstantOffset += CI->getSExtValue()*TypeSize;
4048         } else if (TypeSize) {  // Scales of zero don't do anything.
4049           // We only allow one variable index at the moment.
4050           if (VariableOperand != -1)
4051             return false;
4052
4053           // Remember the variable index.
4054           VariableOperand = i;
4055           VariableScale = TypeSize;
4056         }
4057       }
4058     }
4059
4060     // A common case is for the GEP to only do a constant offset.  In this case,
4061     // just add it to the disp field and check validity.
4062     if (VariableOperand == -1) {
4063       AddrMode.BaseOffs += ConstantOffset;
4064       if (ConstantOffset == 0 ||
4065           TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) {
4066         // Check to see if we can fold the base pointer in too.
4067         if (matchAddr(AddrInst->getOperand(0), Depth+1))
4068           return true;
4069       }
4070       AddrMode.BaseOffs -= ConstantOffset;
4071       return false;
4072     }
4073