Generates conditional branch instead of fake ones for Select instruction in some...
[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   // Set the insertion point right after the 'DepVal'.
522   Instruction* Inst = nullptr;
523   IRBuilder<true, NoFolder> Builder(SI);
524   BasicBlock* BB = SI->getParent();
525   Value* Address = SI->getPointerOperand();
526   Type* TargetIntegerType =
527       IntegerType::get(Address->getContext(),
528                        BB->getModule()->getDataLayout().getPointerSizeInBits());
529
530   // Does SI's address already depends on whatever 'DepVal' depends on?
531   if (StoreAddressDependOnValue(SI, DepVal)) {
532     return false;
533   }
534
535   // Figure out if there's a root variable 'DepVal' depends on. For example, we
536   // can extract "getelementptr inbounds %struct, %struct* %0, i64 0, i32 123"
537   // to be "%struct* %0" since all other operands are constant.
538   DepVal = getRootDependence(DepVal);
539
540   // Is this already a dependence-tainted store?
541   Value* OldDep = getDependence(Address);
542   if (OldDep) {
543     // The address of 'SI' has already been tainted.  Just need to absorb the
544     // DepVal to the existing dependence in the address of SI.
545     Instruction* AndDep = getAndDependence(Address);
546     IRBuilder<true, NoFolder> Builder(AndDep);
547     Value* NewDep = nullptr;
548     if (DepVal->getType() == AndDep->getType()) {
549       NewDep = Builder.CreateAnd(OldDep, DepVal);
550     } else {
551       NewDep = Builder.CreateAnd(
552           OldDep, createCast(Builder, DepVal, TargetIntegerType));
553     }
554
555     auto* NewDepInst = dyn_cast<Instruction>(NewDep);
556
557     // Use the new AND instruction as the dependence
558     AndDep->setOperand(0, NewDep);
559     return true;
560   }
561
562   // SI's address has not been tainted. Now taint it with 'DepVal'.
563   Value* CastDepToInt = createCast(Builder, DepVal, TargetIntegerType);
564   Value* PtrToIntCast = Builder.CreatePtrToInt(Address, TargetIntegerType);
565   Value* AndDepVal =
566       Builder.CreateAnd(CastDepToInt, ConstantInt::get(TargetIntegerType, 0));
567   auto AndInst = dyn_cast<Instruction>(AndDepVal);
568   // XXX-comment: The original IR InstCombiner would change our and instruction
569   // to a select and then the back end optimize the condition out.  We attach a
570   // flag to instructions and set it here to inform the InstCombiner to not to
571   // touch this and instruction at all.
572   Value* OrAddr = Builder.CreateOr(AndDepVal, PtrToIntCast);
573   Value* NewAddr = Builder.CreateIntToPtr(OrAddr, Address->getType());
574
575   DEBUG(dbgs() << "[taintStoreAddress]\n"
576                << "Original store: " << *SI << '\n');
577   SI->setOperand(1, NewAddr);
578
579   // Debug output.
580   DEBUG(dbgs() << "\tTargetIntegerType: " << *TargetIntegerType << '\n'
581                << "\tCast dependence value to integer: " << *CastDepToInt
582                << '\n'
583                << "\tCast address to integer: " << *PtrToIntCast << '\n'
584                << "\tAnd dependence value: " << *AndDepVal << '\n'
585                << "\tOr address: " << *OrAddr << '\n'
586                << "\tCast or instruction to address: " << *NewAddr << "\n\n");
587
588   return true;
589 }
590
591 // Looks for the previous store in the if block --- 'BrBB', which makes the
592 // speculative store 'StoreToHoist' safe.
593 Value* getSpeculativeStoreInPrevBB(StoreInst* StoreToHoist, BasicBlock* BrBB) {
594   assert(StoreToHoist && "StoreToHoist must be a real store");
595
596   Value* StorePtr = StoreToHoist->getPointerOperand();
597
598   // Look for a store to the same pointer in BrBB.
599   for (BasicBlock::reverse_iterator RI = BrBB->rbegin(), RE = BrBB->rend();
600        RI != RE; ++RI) {
601     Instruction* CurI = &*RI;
602
603     StoreInst* SI = dyn_cast<StoreInst>(CurI);
604     // Found the previous store make sure it stores to the same location.
605     // XXX-update: If the previous store's original untainted address are the
606     // same as 'StorePtr', we are also good to hoist the store.
607     if (SI && (SI->getPointerOperand() == StorePtr ||
608                GetUntaintedAddress(SI->getPointerOperand()) == StorePtr)) {
609       // Found the previous store, return its value operand.
610       return SI;
611     }
612   }
613
614   assert(false &&
615          "We should not reach here since this store is safe to speculate");
616 }
617
618 // XXX-comment: Returns true if it changes the code, false otherwise (the branch
619 // condition already depends on 'DepVal'.
620 bool taintConditionalBranch(BranchInst* BI, Value* DepVal) {
621   assert(BI->isConditional());
622   auto* Cond = BI->getOperand(0);
623   if (dependenceSetInclusion(Cond, DepVal)) {
624     // The dependence/ordering is self-evident.
625     return false;
626   }
627
628   IRBuilder<true, NoFolder> Builder(BI);
629   auto* AndDep =
630       Builder.CreateAnd(DepVal, ConstantInt::get(DepVal->getType(), 0));
631   auto* TruncAndDep =
632       Builder.CreateTrunc(AndDep, IntegerType::get(DepVal->getContext(), 1));
633   auto* OrCond = Builder.CreateOr(TruncAndDep, Cond);
634   BI->setOperand(0, OrCond);
635
636   // Debug output.
637   DEBUG(dbgs() << "\tTainted branch condition:\n" << *BI->getParent());
638
639   return true;
640 }
641
642 bool ConditionalBranchDependsOnValue(BranchInst* BI, Value* DepVal) {
643   assert(BI->isConditional());
644   auto* Cond = BI->getOperand(0);
645   return dependenceSetInclusion(Cond, DepVal);
646 }
647
648 // XXX-update: For a relaxed load 'LI', find the first immediate atomic store or
649 // the first conditional branch. Returns nullptr if there's no such immediately
650 // following store/branch instructions, which we can only enforce the load with
651 // 'acquire'.
652 Instruction* findFirstStoreCondBranchInst(LoadInst* LI) {
653   // In some situations, relaxed loads can be left as is:
654   // 1. The relaxed load is used to calculate the address of the immediate
655   // following store;
656   // 2. The relaxed load is used as a condition in the immediate following
657   // condition, and there are no stores in between. This is actually quite
658   // common. E.g.,
659   // int r1 = x.load(relaxed);
660   // if (r1 != 0) {
661   //   y.store(1, relaxed);
662   // }
663   // However, in this function, we don't deal with them directly. Instead, we
664   // just find the immediate following store/condition branch and return it.
665
666   auto* BB = LI->getParent();
667   auto BE = BB->end();
668   auto BBI = BasicBlock::iterator(LI);
669   BBI++;
670   while (true) {
671     for (; BBI != BE; BBI++) {
672       auto* Inst = dyn_cast<Instruction>(&*BBI);
673       if (Inst == nullptr) {
674         continue;
675       }
676       if (Inst->getOpcode() == Instruction::Store) {
677         return Inst;
678       } else if (Inst->getOpcode() == Instruction::Br) {
679         auto* BrInst = dyn_cast<BranchInst>(Inst);
680         if (BrInst->isConditional()) {
681           return Inst;
682         } else {
683           // Reinitialize iterators with the destination of the unconditional
684           // branch.
685           BB = BrInst->getSuccessor(0);
686           BBI = BB->begin();
687           BE = BB->end();
688           break;
689         }
690       }
691     }
692     if (BBI == BE) {
693       return nullptr;
694     }
695   }
696 }
697
698 // XXX-comment: Returns whether the code has been changed.
699 bool taintMonotonicLoads(const SmallVector<LoadInst*, 1>& MonotonicLoadInsts) {
700   bool Changed = false;
701   for (auto* LI : MonotonicLoadInsts) {
702     auto* FirstInst = findFirstStoreCondBranchInst(LI);
703     if (FirstInst == nullptr) {
704       // We don't seem to be able to taint a following store/conditional branch
705       // instruction. Simply make it acquire.
706       DEBUG(dbgs() << "[RelaxedLoad]: Transformed to acquire load\n"
707                    << *LI << "\n");
708       LI->setOrdering(Acquire);
709       Changed = true;
710       continue;
711     }
712     // Taint 'FirstInst', which could be a store or a condition branch
713     // instruction.
714     if (FirstInst->getOpcode() == Instruction::Store) {
715       Changed |= taintStoreAddress(dyn_cast<StoreInst>(FirstInst), LI);
716     } else if (FirstInst->getOpcode() == Instruction::Br) {
717       Changed |= taintConditionalBranch(dyn_cast<BranchInst>(FirstInst), LI);
718     } else {
719       assert(false && "findFirstStoreCondBranchInst() should return a "
720                     "store/condition branch instruction");
721     }
722   }
723   return Changed;
724 }
725
726 // Inserts a fake conditional branch right after the instruction 'SplitInst',
727 // and the branch condition is 'Condition'. 'SplitInst' will be placed in the
728 // newly created block.
729 void AddFakeConditionalBranch(Instruction* SplitInst, Value* Condition) {
730   auto* BB = SplitInst->getParent();
731   TerminatorInst* ThenTerm = nullptr;
732   TerminatorInst* ElseTerm = nullptr;
733   SplitBlockAndInsertIfThenElse(Condition, SplitInst, &ThenTerm, &ElseTerm);
734   assert(ThenTerm && ElseTerm &&
735          "Then/Else terminators cannot be empty after basic block spliting");
736   auto* ThenBB = ThenTerm->getParent();
737   auto* ElseBB = ElseTerm->getParent();
738   auto* TailBB = ThenBB->getSingleSuccessor();
739   assert(TailBB && "Tail block cannot be empty after basic block spliting");
740
741   ThenBB->disableCanEliminateBlock();
742   ThenBB->disableCanEliminateBlock();
743   TailBB->disableCanEliminateBlock();
744   ThenBB->setName(BB->getName() + "Then.Fake");
745   ElseBB->setName(BB->getName() + "Else.Fake");
746   DEBUG(dbgs() << "Add fake conditional branch:\n"
747                << "Then Block:\n"
748                << *ThenBB << "Else Block:\n"
749                << *ElseBB << "\n");
750 }
751
752 // Returns true if the code is changed, and false otherwise.
753 void TaintRelaxedLoads(LoadInst* LI) {
754   // For better performance, we can add a "AND X 0" instruction before the
755   // condition.
756   auto* FirstInst = findFirstStoreCondBranchInst(LI);
757   Instruction* InsertPoint = nullptr;
758   if (FirstInst == nullptr) {
759     InsertPoint = LI->getParent()->getTerminator();
760     InsertPoint = LI->getNextNode();
761   } else {
762     InsertPoint = LI->getNextNode();
763   }
764   IRBuilder<true, NoFolder> Builder(InsertPoint);
765   auto* AndZero = dyn_cast<Instruction>(
766       Builder.CreateAnd(LI, Constant::getNullValue(LI->getType())));
767   auto* FakeCondition = dyn_cast<Instruction>(Builder.CreateICmp(
768       CmpInst::ICMP_NE, AndZero, Constant::getNullValue(LI->getType())));
769   AddFakeConditionalBranch(FakeCondition->getNextNode(), FakeCondition);
770 }
771
772 // XXX-comment: Returns whether the code has been changed.
773 bool AddFakeConditionalBranchAfterMonotonicLoads(
774     const SmallVector<LoadInst*, 1>& MonotonicLoadInsts) {
775   bool Changed = false;
776   for (auto* LI : MonotonicLoadInsts) {
777     auto* FirstInst = findFirstStoreCondBranchInst(LI);
778     if (FirstInst != nullptr) {
779       if (FirstInst->getOpcode() == Instruction::Store) {
780         if (StoreAddressDependOnValue(dyn_cast<StoreInst>(FirstInst), LI)) {
781           continue;
782         }
783       } else if (FirstInst->getOpcode() == Instruction::Br) {
784         if (ConditionalBranchDependsOnValue(dyn_cast<BranchInst>(FirstInst),
785                                             LI)) {
786           continue;
787         }
788       } else {
789         dbgs() << "FirstInst=" << *FirstInst << "\n";
790         assert(false && "findFirstStoreCondBranchInst() should return a "
791                         "store/condition branch instruction");
792       }
793     }
794
795     // We really need to process the relaxed load now.
796     StoreInst* SI = nullptr;;
797     if (FirstInst && (SI = dyn_cast<StoreInst>(FirstInst))) {
798       // For immediately coming stores, taint the address of the store.
799       taintStoreAddress(SI, LI);
800     } else {
801       // For immediately coming branch, directly add a fake branch.
802       TaintRelaxedLoads(LI);
803       Changed = true;
804     }
805   }
806   return Changed;
807 }
808
809 /**** Implementations of public methods for dependence tainting ****/
810 Value* GetUntaintedAddress(Value* CurrentAddress) {
811   auto* OrAddress = getOrAddress(CurrentAddress);
812   if (OrAddress == nullptr) {
813     // Is it tainted by a select instruction?
814     auto* Inst = dyn_cast<Instruction>(CurrentAddress);
815     if (nullptr != Inst && Inst->getOpcode() == Instruction::Select) {
816       // A selection instruction.
817       if (Inst->getOperand(1) == Inst->getOperand(2)) {
818         return Inst->getOperand(1);
819       }
820     }
821
822     return CurrentAddress;
823   }
824   Value* ActualAddress = nullptr;
825
826   auto* CastToInt = dyn_cast<Instruction>(OrAddress->getOperand(1));
827   if (CastToInt && CastToInt->getOpcode() == Instruction::PtrToInt) {
828     return CastToInt->getOperand(0);
829   } else {
830     // This should be a IntToPtr constant expression.
831     ConstantExpr* PtrToIntExpr =
832         dyn_cast<ConstantExpr>(OrAddress->getOperand(1));
833     if (PtrToIntExpr && PtrToIntExpr->getOpcode() == Instruction::PtrToInt) {
834       return PtrToIntExpr->getOperand(0);
835     }
836   }
837
838   // Looks like it's not been dependence-tainted. Returns itself.
839   return CurrentAddress;
840 }
841
842 MemoryLocation GetUntaintedMemoryLocation(StoreInst* SI) {
843   AAMDNodes AATags;
844   SI->getAAMetadata(AATags);
845   const auto& DL = SI->getModule()->getDataLayout();
846   const auto* OriginalAddr = GetUntaintedAddress(SI->getPointerOperand());
847   DEBUG(if (OriginalAddr != SI->getPointerOperand()) {
848     dbgs() << "[GetUntaintedMemoryLocation]\n"
849            << "Storing address: " << *SI->getPointerOperand()
850            << "\nUntainted address: " << *OriginalAddr << "\n";
851   });
852   return MemoryLocation(OriginalAddr,
853                         DL.getTypeStoreSize(SI->getValueOperand()->getType()),
854                         AATags);
855 }
856
857 bool TaintDependenceToStore(StoreInst* SI, Value* DepVal) {
858   if (dependenceSetInclusion(SI, DepVal)) {
859     return false;
860   }
861
862   bool tainted = taintStoreAddress(SI, DepVal);
863   assert(tainted);
864   return tainted;
865 }
866
867 bool TaintDependenceToStoreAddress(StoreInst* SI, Value* DepVal) {
868   if (dependenceSetInclusion(SI->getPointerOperand(), DepVal)) {
869     return false;
870   }
871
872   bool tainted = taintStoreAddress(SI, DepVal);
873   assert(tainted);
874   return tainted;
875 }
876
877 bool CompressTaintedStore(BasicBlock* BB) {
878   // This function looks for windows of adajcent stores in 'BB' that satisfy the
879   // following condition (and then do optimization):
880   // *Addr(d1) = v1, d1 is a condition and is the only dependence the store's
881   //                 address depends on && Dep(v1) includes Dep(d1);
882   // *Addr(d2) = v2, d2 is a condition and is the only dependnece the store's
883   //                 address depends on && Dep(v2) includes Dep(d2) &&
884   //                 Dep(d2) includes Dep(d1);
885   // ...
886   // *Addr(dN) = vN, dN is a condition and is the only dependence the store's
887   //                 address depends on && Dep(dN) includes Dep(d"N-1").
888   //
889   // As a result, Dep(dN) includes [Dep(d1) V ... V Dep(d"N-1")], so we can
890   // safely transform the above to the following. In between these stores, we
891   // can omit untainted stores to the same address 'Addr' since they internally
892   // have dependence on the previous stores on the same address.
893   // =>
894   // *Addr = v1
895   // *Addr = v2
896   // *Addr(d3) = v3
897   for (auto BI = BB->begin(), BE = BB->end(); BI != BE; BI++) {
898     // Look for the first store in such a window of adajacent stores.
899     auto* FirstSI = dyn_cast<StoreInst>(&*BI);
900     if (!FirstSI) {
901       continue;
902     }
903
904     // The first store in the window must be tainted.
905     auto* UntaintedAddress = GetUntaintedAddress(FirstSI->getPointerOperand());
906     if (UntaintedAddress == FirstSI->getPointerOperand()) {
907       continue;
908     }
909
910     // The first store's address must directly depend on and only depend on a
911     // condition.
912     auto* FirstSIDepCond = getConditionDependence(FirstSI->getPointerOperand());
913     if (nullptr == FirstSIDepCond) {
914       continue;
915     }
916
917     // Dep(first store's storing value) includes Dep(tainted dependence).
918     if (!dependenceSetInclusion(FirstSI->getValueOperand(), FirstSIDepCond)) {
919       continue;
920     }
921
922     // Look for subsequent stores to the same address that satisfy the condition
923     // of "compressing the dependence".
924     SmallVector<StoreInst*, 8> AdajacentStores;
925     AdajacentStores.push_back(FirstSI);
926     auto BII = BasicBlock::iterator(FirstSI);
927     for (BII++; BII != BE; BII++) {
928       auto* CurrSI = dyn_cast<StoreInst>(&*BII);
929       if (!CurrSI) {
930         if (BII->mayHaveSideEffects()) {
931           // Be conservative. Instructions with side effects are similar to
932           // stores.
933           break;
934         }
935         continue;
936       }
937
938       auto* OrigAddress = GetUntaintedAddress(CurrSI->getPointerOperand());
939       auto* CurrSIDepCond = getConditionDependence(CurrSI->getPointerOperand());
940       // All other stores must satisfy either:
941       // A. 'CurrSI' is an untainted store to the same address, or
942       // B. the combination of the following 5 subconditions:
943       // 1. Tainted;
944       // 2. Untainted address is the same as the group's address;
945       // 3. The address is tainted with a sole value which is a condition;
946       // 4. The storing value depends on the condition in 3.
947       // 5. The condition in 3 depends on the previous stores dependence
948       // condition.
949
950       // Condition A. Should ignore this store directly.
951       if (OrigAddress == CurrSI->getPointerOperand() &&
952           OrigAddress == UntaintedAddress) {
953         continue;
954       }
955       // Check condition B.
956       Value* Cond = nullptr;
957       if (OrigAddress == CurrSI->getPointerOperand() ||
958           OrigAddress != UntaintedAddress || CurrSIDepCond == nullptr ||
959           !dependenceSetInclusion(CurrSI->getValueOperand(), CurrSIDepCond)) {
960         // Check condition 1, 2, 3 & 4.
961         break;
962       }
963
964       // Check condition 5.
965       StoreInst* PrevSI = AdajacentStores[AdajacentStores.size() - 1];
966       auto* PrevSIDepCond = getConditionDependence(PrevSI->getPointerOperand());
967       assert(PrevSIDepCond &&
968              "Store in the group must already depend on a condtion");
969       if (!dependenceSetInclusion(CurrSIDepCond, PrevSIDepCond)) {
970         break;
971       }
972
973       AdajacentStores.push_back(CurrSI);
974     }
975
976     if (AdajacentStores.size() == 1) {
977       // The outer loop should keep looking from the next store.
978       continue;
979     }
980
981     // Now we have such a group of tainted stores to the same address.
982     DEBUG(dbgs() << "[CompressTaintedStore]\n");
983     DEBUG(dbgs() << "Original BB\n");
984     DEBUG(dbgs() << *BB << '\n');
985     auto* LastSI = AdajacentStores[AdajacentStores.size() - 1];
986     for (unsigned i = 0; i < AdajacentStores.size() - 1; ++i) {
987       auto* SI = AdajacentStores[i];
988
989       // Use the original address for stores before the last one.
990       SI->setOperand(1, UntaintedAddress);
991
992       DEBUG(dbgs() << "Store address has been reversed: " << *SI << '\n';);
993     }
994     // XXX-comment: Try to make the last store use fewer registers.
995     // If LastSI's storing value is a select based on the condition with which
996     // its address is tainted, transform the tainted address to a select
997     // instruction, as follows:
998     // r1 = Select Cond ? A : B
999     // r2 = Cond & 0
1000     // r3 = Addr | r2
1001     // *r3 = r1
1002     // ==>
1003     // r1 = Select Cond ? A : B
1004     // r2 = Select Cond ? Addr : Addr
1005     // *r2 = r1
1006     // The idea is that both Select instructions depend on the same condition,
1007     // so hopefully the backend can generate two cmov instructions for them (and
1008     // this saves the number of registers needed).
1009     auto* LastSIDep = getConditionDependence(LastSI->getPointerOperand());
1010     auto* LastSIValue = dyn_cast<Instruction>(LastSI->getValueOperand());
1011     if (LastSIValue && LastSIValue->getOpcode() == Instruction::Select &&
1012         LastSIValue->getOperand(0) == LastSIDep) {
1013       // XXX-comment: Maybe it's better for us to just leave it as an and/or
1014       // dependence pattern.
1015       //      /*
1016       IRBuilder<true, NoFolder> Builder(LastSI);
1017       auto* Address =
1018           Builder.CreateSelect(LastSIDep, UntaintedAddress, UntaintedAddress);
1019       LastSI->setOperand(1, Address);
1020       DEBUG(dbgs() << "The last store becomes :" << *LastSI << "\n\n";);
1021       //      */
1022     }
1023   }
1024
1025   return true;
1026 }
1027
1028 bool PassDependenceToStore(Value* OldAddress, StoreInst* NewStore) {
1029   Value* OldDep = getDependence(OldAddress);
1030   // Return false when there's no dependence to pass from the OldAddress.
1031   if (!OldDep) {
1032     return false;
1033   }
1034
1035   // No need to pass the dependence to NewStore's address if it already depends
1036   // on whatever 'OldAddress' depends on.
1037   if (StoreAddressDependOnValue(NewStore, OldDep)) {
1038     return false;
1039   }
1040   return taintStoreAddress(NewStore, OldAddress);
1041 }
1042
1043 SmallSet<Value*, 8> FindDependence(Value* Val) {
1044   SmallSet<Value*, 8> DepSet;
1045   recursivelyFindDependence(&DepSet, Val, true /*Only insert leaf nodes*/);
1046   return DepSet;
1047 }
1048
1049 bool StoreAddressDependOnValue(StoreInst* SI, Value* DepVal) {
1050   return dependenceSetInclusion(SI->getPointerOperand(), DepVal);
1051 }
1052
1053 bool StoreDependOnValue(StoreInst* SI, Value* Dep) {
1054   return dependenceSetInclusion(SI, Dep);
1055 }
1056
1057 } // namespace
1058
1059
1060
1061 bool CodeGenPrepare::runOnFunction(Function &F) {
1062   bool EverMadeChange = false;
1063
1064   if (skipOptnoneFunction(F))
1065     return false;
1066
1067   DL = &F.getParent()->getDataLayout();
1068
1069   // Clear per function information.
1070   InsertedInsts.clear();
1071   PromotedInsts.clear();
1072
1073   ModifiedDT = false;
1074   if (TM)
1075     TLI = TM->getSubtargetImpl(F)->getTargetLowering();
1076   TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1077   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1078   OptSize = F.optForSize();
1079
1080   /// This optimization identifies DIV instructions that can be
1081   /// profitably bypassed and carried out with a shorter, faster divide.
1082   if (!OptSize && TLI && TLI->isSlowDivBypassed()) {
1083     const DenseMap<unsigned int, unsigned int> &BypassWidths =
1084        TLI->getBypassSlowDivWidths();
1085     BasicBlock* BB = &*F.begin();
1086     while (BB != nullptr) {
1087       // bypassSlowDivision may create new BBs, but we don't want to reapply the
1088       // optimization to those blocks.
1089       BasicBlock* Next = BB->getNextNode();
1090       EverMadeChange |= bypassSlowDivision(BB, BypassWidths);
1091       BB = Next;
1092     }
1093   }
1094
1095   // Eliminate blocks that contain only PHI nodes and an
1096   // unconditional branch.
1097   EverMadeChange |= eliminateMostlyEmptyBlocks(F);
1098
1099   // llvm.dbg.value is far away from the value then iSel may not be able
1100   // handle it properly. iSel will drop llvm.dbg.value if it can not
1101   // find a node corresponding to the value.
1102   EverMadeChange |= placeDbgValues(F);
1103
1104   // If there is a mask, compare against zero, and branch that can be combined
1105   // into a single target instruction, push the mask and compare into branch
1106   // users. Do this before OptimizeBlock -> OptimizeInst ->
1107   // OptimizeCmpExpression, which perturbs the pattern being searched for.
1108   if (!DisableBranchOpts) {
1109     EverMadeChange |= sinkAndCmp(F);
1110     EverMadeChange |= splitBranchCondition(F);
1111   }
1112
1113   bool MadeChange = true;
1114   while (MadeChange) {
1115     MadeChange = false;
1116     for (Function::iterator I = F.begin(); I != F.end(); ) {
1117       BasicBlock *BB = &*I++;
1118       bool ModifiedDTOnIteration = false;
1119       MadeChange |= optimizeBlock(*BB, ModifiedDTOnIteration);
1120
1121       // Restart BB iteration if the dominator tree of the Function was changed
1122       if (ModifiedDTOnIteration)
1123         break;
1124     }
1125     EverMadeChange |= MadeChange;
1126   }
1127
1128   SunkAddrs.clear();
1129
1130   if (!DisableBranchOpts) {
1131     MadeChange = false;
1132     SmallPtrSet<BasicBlock*, 8> WorkList;
1133     for (BasicBlock &BB : F) {
1134       SmallVector<BasicBlock *, 2> Successors(succ_begin(&BB), succ_end(&BB));
1135       MadeChange |= ConstantFoldTerminator(&BB, true);
1136       if (!MadeChange) continue;
1137
1138       for (SmallVectorImpl<BasicBlock*>::iterator
1139              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
1140         if (pred_begin(*II) == pred_end(*II))
1141           WorkList.insert(*II);
1142     }
1143
1144     // Delete the dead blocks and any of their dead successors.
1145     MadeChange |= !WorkList.empty();
1146     while (!WorkList.empty()) {
1147       BasicBlock *BB = *WorkList.begin();
1148       WorkList.erase(BB);
1149       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
1150
1151       DeleteDeadBlock(BB);
1152
1153       for (SmallVectorImpl<BasicBlock*>::iterator
1154              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
1155         if (pred_begin(*II) == pred_end(*II))
1156           WorkList.insert(*II);
1157     }
1158
1159     // Merge pairs of basic blocks with unconditional branches, connected by
1160     // a single edge.
1161     if (EverMadeChange || MadeChange)
1162       MadeChange |= eliminateFallThrough(F);
1163
1164     EverMadeChange |= MadeChange;
1165   }
1166
1167   if (!DisableGCOpts) {
1168     SmallVector<Instruction *, 2> Statepoints;
1169     for (BasicBlock &BB : F)
1170       for (Instruction &I : BB)
1171         if (isStatepoint(I))
1172           Statepoints.push_back(&I);
1173     for (auto &I : Statepoints)
1174       EverMadeChange |= simplifyOffsetableRelocate(*I);
1175   }
1176
1177   // XXX-comment: Delay dealing with relaxed loads in this function to avoid
1178   // further changes done by other passes (e.g., SimplifyCFG).
1179   // Collect all the relaxed loads.
1180   SmallVector<LoadInst*, 1> MonotonicLoadInsts;
1181   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
1182     if (I->isAtomic()) {
1183       switch (I->getOpcode()) {
1184         case Instruction::Load: {
1185           auto* LI = dyn_cast<LoadInst>(&*I);
1186           if (LI->getOrdering() == Monotonic) {
1187             MonotonicLoadInsts.push_back(LI);
1188           }
1189           break;
1190         }
1191         default: {
1192           break;
1193         }
1194       }
1195     }
1196   }
1197   EverMadeChange |=
1198       AddFakeConditionalBranchAfterMonotonicLoads(MonotonicLoadInsts);
1199
1200   return EverMadeChange;
1201 }
1202
1203 /// Merge basic blocks which are connected by a single edge, where one of the
1204 /// basic blocks has a single successor pointing to the other basic block,
1205 /// which has a single predecessor.
1206 bool CodeGenPrepare::eliminateFallThrough(Function &F) {
1207   bool Changed = false;
1208   // Scan all of the blocks in the function, except for the entry block.
1209   for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
1210     BasicBlock *BB = &*I++;
1211     // If the destination block has a single pred, then this is a trivial
1212     // edge, just collapse it.
1213     BasicBlock *SinglePred = BB->getSinglePredecessor();
1214
1215     // Don't merge if BB's address is taken.
1216     if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
1217
1218     BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
1219     if (Term && !Term->isConditional()) {
1220       Changed = true;
1221       DEBUG(dbgs() << "To merge:\n"<< *SinglePred << "\n\n\n");
1222       // Remember if SinglePred was the entry block of the function.
1223       // If so, we will need to move BB back to the entry position.
1224       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
1225       MergeBasicBlockIntoOnlyPred(BB, nullptr);
1226
1227       if (isEntry && BB != &BB->getParent()->getEntryBlock())
1228         BB->moveBefore(&BB->getParent()->getEntryBlock());
1229
1230       // We have erased a block. Update the iterator.
1231       I = BB->getIterator();
1232     }
1233   }
1234   return Changed;
1235 }
1236
1237 /// Eliminate blocks that contain only PHI nodes, debug info directives, and an
1238 /// unconditional branch. Passes before isel (e.g. LSR/loopsimplify) often split
1239 /// edges in ways that are non-optimal for isel. Start by eliminating these
1240 /// blocks so we can split them the way we want them.
1241 bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F) {
1242   bool MadeChange = false;
1243   // Note that this intentionally skips the entry block.
1244   for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
1245     BasicBlock *BB = &*I++;
1246     // If this block doesn't end with an uncond branch, ignore it.
1247     BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
1248     if (!BI || !BI->isUnconditional())
1249       continue;
1250
1251     // If the instruction before the branch (skipping debug info) isn't a phi
1252     // node, then other stuff is happening here.
1253     BasicBlock::iterator BBI = BI->getIterator();
1254     if (BBI != BB->begin()) {
1255       --BBI;
1256       while (isa<DbgInfoIntrinsic>(BBI)) {
1257         if (BBI == BB->begin())
1258           break;
1259         --BBI;
1260       }
1261       if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
1262         continue;
1263     }
1264
1265     // Do not break infinite loops.
1266     BasicBlock *DestBB = BI->getSuccessor(0);
1267     if (DestBB == BB)
1268       continue;
1269
1270     if (!canMergeBlocks(BB, DestBB))
1271       continue;
1272
1273     eliminateMostlyEmptyBlock(BB);
1274     MadeChange = true;
1275   }
1276   return MadeChange;
1277 }
1278
1279 /// Return true if we can merge BB into DestBB if there is a single
1280 /// unconditional branch between them, and BB contains no other non-phi
1281 /// instructions.
1282 bool CodeGenPrepare::canMergeBlocks(const BasicBlock *BB,
1283                                     const BasicBlock *DestBB) const {
1284   // We only want to eliminate blocks whose phi nodes are used by phi nodes in
1285   // the successor.  If there are more complex condition (e.g. preheaders),
1286   // don't mess around with them.
1287   BasicBlock::const_iterator BBI = BB->begin();
1288   while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
1289     for (const User *U : PN->users()) {
1290       const Instruction *UI = cast<Instruction>(U);
1291       if (UI->getParent() != DestBB || !isa<PHINode>(UI))
1292         return false;
1293       // If User is inside DestBB block and it is a PHINode then check
1294       // incoming value. If incoming value is not from BB then this is
1295       // a complex condition (e.g. preheaders) we want to avoid here.
1296       if (UI->getParent() == DestBB) {
1297         if (const PHINode *UPN = dyn_cast<PHINode>(UI))
1298           for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) {
1299             Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I));
1300             if (Insn && Insn->getParent() == BB &&
1301                 Insn->getParent() != UPN->getIncomingBlock(I))
1302               return false;
1303           }
1304       }
1305     }
1306   }
1307
1308   // If BB and DestBB contain any common predecessors, then the phi nodes in BB
1309   // and DestBB may have conflicting incoming values for the block.  If so, we
1310   // can't merge the block.
1311   const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin());
1312   if (!DestBBPN) return true;  // no conflict.
1313
1314   // Collect the preds of BB.
1315   SmallPtrSet<const BasicBlock*, 16> BBPreds;
1316   if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
1317     // It is faster to get preds from a PHI than with pred_iterator.
1318     for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1319       BBPreds.insert(BBPN->getIncomingBlock(i));
1320   } else {
1321     BBPreds.insert(pred_begin(BB), pred_end(BB));
1322   }
1323
1324   // Walk the preds of DestBB.
1325   for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) {
1326     BasicBlock *Pred = DestBBPN->getIncomingBlock(i);
1327     if (BBPreds.count(Pred)) {   // Common predecessor?
1328       BBI = DestBB->begin();
1329       while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) {
1330         const Value *V1 = PN->getIncomingValueForBlock(Pred);
1331         const Value *V2 = PN->getIncomingValueForBlock(BB);
1332
1333         // If V2 is a phi node in BB, look up what the mapped value will be.
1334         if (const PHINode *V2PN = dyn_cast<PHINode>(V2))
1335           if (V2PN->getParent() == BB)
1336             V2 = V2PN->getIncomingValueForBlock(Pred);
1337
1338         // If there is a conflict, bail out.
1339         if (V1 != V2) return false;
1340       }
1341     }
1342   }
1343
1344   return true;
1345 }
1346
1347
1348 /// Eliminate a basic block that has only phi's and an unconditional branch in
1349 /// it.
1350 void CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
1351   BranchInst *BI = cast<BranchInst>(BB->getTerminator());
1352   BasicBlock *DestBB = BI->getSuccessor(0);
1353
1354   DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB);
1355
1356   // If the destination block has a single pred, then this is a trivial edge,
1357   // just collapse it.
1358   if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
1359     if (SinglePred != DestBB) {
1360       // Remember if SinglePred was the entry block of the function.  If so, we
1361       // will need to move BB back to the entry position.
1362       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
1363       MergeBasicBlockIntoOnlyPred(DestBB, nullptr);
1364
1365       if (isEntry && BB != &BB->getParent()->getEntryBlock())
1366         BB->moveBefore(&BB->getParent()->getEntryBlock());
1367
1368       DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
1369       return;
1370     }
1371   }
1372
1373   // Otherwise, we have multiple predecessors of BB.  Update the PHIs in DestBB
1374   // to handle the new incoming edges it is about to have.
1375   PHINode *PN;
1376   for (BasicBlock::iterator BBI = DestBB->begin();
1377        (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
1378     // Remove the incoming value for BB, and remember it.
1379     Value *InVal = PN->removeIncomingValue(BB, false);
1380
1381     // Two options: either the InVal is a phi node defined in BB or it is some
1382     // value that dominates BB.
1383     PHINode *InValPhi = dyn_cast<PHINode>(InVal);
1384     if (InValPhi && InValPhi->getParent() == BB) {
1385       // Add all of the input values of the input PHI as inputs of this phi.
1386       for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i)
1387         PN->addIncoming(InValPhi->getIncomingValue(i),
1388                         InValPhi->getIncomingBlock(i));
1389     } else {
1390       // Otherwise, add one instance of the dominating value for each edge that
1391       // we will be adding.
1392       if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) {
1393         for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1394           PN->addIncoming(InVal, BBPN->getIncomingBlock(i));
1395       } else {
1396         for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
1397           PN->addIncoming(InVal, *PI);
1398       }
1399     }
1400   }
1401
1402   // The PHIs are now updated, change everything that refers to BB to use
1403   // DestBB and remove BB.
1404   BB->replaceAllUsesWith(DestBB);
1405   BB->eraseFromParent();
1406   ++NumBlocksElim;
1407
1408   DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
1409 }
1410
1411 // Computes a map of base pointer relocation instructions to corresponding
1412 // derived pointer relocation instructions given a vector of all relocate calls
1413 static void computeBaseDerivedRelocateMap(
1414     const SmallVectorImpl<GCRelocateInst *> &AllRelocateCalls,
1415     DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>>
1416         &RelocateInstMap) {
1417   // Collect information in two maps: one primarily for locating the base object
1418   // while filling the second map; the second map is the final structure holding
1419   // a mapping between Base and corresponding Derived relocate calls
1420   DenseMap<std::pair<unsigned, unsigned>, GCRelocateInst *> RelocateIdxMap;
1421   for (auto *ThisRelocate : AllRelocateCalls) {
1422     auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1423                             ThisRelocate->getDerivedPtrIndex());
1424     RelocateIdxMap.insert(std::make_pair(K, ThisRelocate));
1425   }
1426   for (auto &Item : RelocateIdxMap) {
1427     std::pair<unsigned, unsigned> Key = Item.first;
1428     if (Key.first == Key.second)
1429       // Base relocation: nothing to insert
1430       continue;
1431
1432     GCRelocateInst *I = Item.second;
1433     auto BaseKey = std::make_pair(Key.first, Key.first);
1434
1435     // We're iterating over RelocateIdxMap so we cannot modify it.
1436     auto MaybeBase = RelocateIdxMap.find(BaseKey);
1437     if (MaybeBase == RelocateIdxMap.end())
1438       // TODO: We might want to insert a new base object relocate and gep off
1439       // that, if there are enough derived object relocates.
1440       continue;
1441
1442     RelocateInstMap[MaybeBase->second].push_back(I);
1443   }
1444 }
1445
1446 // Accepts a GEP and extracts the operands into a vector provided they're all
1447 // small integer constants
1448 static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP,
1449                                           SmallVectorImpl<Value *> &OffsetV) {
1450   for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
1451     // Only accept small constant integer operands
1452     auto Op = dyn_cast<ConstantInt>(GEP->getOperand(i));
1453     if (!Op || Op->getZExtValue() > 20)
1454       return false;
1455   }
1456
1457   for (unsigned i = 1; i < GEP->getNumOperands(); i++)
1458     OffsetV.push_back(GEP->getOperand(i));
1459   return true;
1460 }
1461
1462 // Takes a RelocatedBase (base pointer relocation instruction) and Targets to
1463 // replace, computes a replacement, and affects it.
1464 static bool
1465 simplifyRelocatesOffABase(GCRelocateInst *RelocatedBase,
1466                           const SmallVectorImpl<GCRelocateInst *> &Targets) {
1467   bool MadeChange = false;
1468   for (GCRelocateInst *ToReplace : Targets) {
1469     assert(ToReplace->getBasePtrIndex() == RelocatedBase->getBasePtrIndex() &&
1470            "Not relocating a derived object of the original base object");
1471     if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1472       // A duplicate relocate call. TODO: coalesce duplicates.
1473       continue;
1474     }
1475
1476     if (RelocatedBase->getParent() != ToReplace->getParent()) {
1477       // Base and derived relocates are in different basic blocks.
1478       // In this case transform is only valid when base dominates derived
1479       // relocate. However it would be too expensive to check dominance
1480       // for each such relocate, so we skip the whole transformation.
1481       continue;
1482     }
1483
1484     Value *Base = ToReplace->getBasePtr();
1485     auto Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr());
1486     if (!Derived || Derived->getPointerOperand() != Base)
1487       continue;
1488
1489     SmallVector<Value *, 2> OffsetV;
1490     if (!getGEPSmallConstantIntOffsetV(Derived, OffsetV))
1491       continue;
1492
1493     // Create a Builder and replace the target callsite with a gep
1494     assert(RelocatedBase->getNextNode() && "Should always have one since it's not a terminator");
1495
1496     // Insert after RelocatedBase
1497     IRBuilder<> Builder(RelocatedBase->getNextNode());
1498     Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
1499
1500     // If gc_relocate does not match the actual type, cast it to the right type.
1501     // In theory, there must be a bitcast after gc_relocate if the type does not
1502     // match, and we should reuse it to get the derived pointer. But it could be
1503     // cases like this:
1504     // bb1:
1505     //  ...
1506     //  %g1 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...)
1507     //  br label %merge
1508     //
1509     // bb2:
1510     //  ...
1511     //  %g2 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...)
1512     //  br label %merge
1513     //
1514     // merge:
1515     //  %p1 = phi i8 addrspace(1)* [ %g1, %bb1 ], [ %g2, %bb2 ]
1516     //  %cast = bitcast i8 addrspace(1)* %p1 in to i32 addrspace(1)*
1517     //
1518     // In this case, we can not find the bitcast any more. So we insert a new bitcast
1519     // no matter there is already one or not. In this way, we can handle all cases, and
1520     // the extra bitcast should be optimized away in later passes.
1521     Value *ActualRelocatedBase = RelocatedBase;
1522     if (RelocatedBase->getType() != Base->getType()) {
1523       ActualRelocatedBase =
1524           Builder.CreateBitCast(RelocatedBase, Base->getType());
1525     }
1526     Value *Replacement = Builder.CreateGEP(
1527         Derived->getSourceElementType(), ActualRelocatedBase, makeArrayRef(OffsetV));
1528     Replacement->takeName(ToReplace);
1529     // If the newly generated derived pointer's type does not match the original derived
1530     // pointer's type, cast the new derived pointer to match it. Same reasoning as above.
1531     Value *ActualReplacement = Replacement;
1532     if (Replacement->getType() != ToReplace->getType()) {
1533       ActualReplacement =
1534           Builder.CreateBitCast(Replacement, ToReplace->getType());
1535     }
1536     ToReplace->replaceAllUsesWith(ActualReplacement);
1537     ToReplace->eraseFromParent();
1538
1539     MadeChange = true;
1540   }
1541   return MadeChange;
1542 }
1543
1544 // Turns this:
1545 //
1546 // %base = ...
1547 // %ptr = gep %base + 15
1548 // %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
1549 // %base' = relocate(%tok, i32 4, i32 4)
1550 // %ptr' = relocate(%tok, i32 4, i32 5)
1551 // %val = load %ptr'
1552 //
1553 // into this:
1554 //
1555 // %base = ...
1556 // %ptr = gep %base + 15
1557 // %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr)
1558 // %base' = gc.relocate(%tok, i32 4, i32 4)
1559 // %ptr' = gep %base' + 15
1560 // %val = load %ptr'
1561 bool CodeGenPrepare::simplifyOffsetableRelocate(Instruction &I) {
1562   bool MadeChange = false;
1563   SmallVector<GCRelocateInst *, 2> AllRelocateCalls;
1564
1565   for (auto *U : I.users())
1566     if (GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U))
1567       // Collect all the relocate calls associated with a statepoint
1568       AllRelocateCalls.push_back(Relocate);
1569
1570   // We need atleast one base pointer relocation + one derived pointer
1571   // relocation to mangle
1572   if (AllRelocateCalls.size() < 2)
1573     return false;
1574
1575   // RelocateInstMap is a mapping from the base relocate instruction to the
1576   // corresponding derived relocate instructions
1577   DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>> RelocateInstMap;
1578   computeBaseDerivedRelocateMap(AllRelocateCalls, RelocateInstMap);
1579   if (RelocateInstMap.empty())
1580     return false;
1581
1582   for (auto &Item : RelocateInstMap)
1583     // Item.first is the RelocatedBase to offset against
1584     // Item.second is the vector of Targets to replace
1585     MadeChange = simplifyRelocatesOffABase(Item.first, Item.second);
1586   return MadeChange;
1587 }
1588
1589 /// SinkCast - Sink the specified cast instruction into its user blocks
1590 static bool SinkCast(CastInst *CI) {
1591   BasicBlock *DefBB = CI->getParent();
1592
1593   /// InsertedCasts - Only insert a cast in each block once.
1594   DenseMap<BasicBlock*, CastInst*> InsertedCasts;
1595
1596   bool MadeChange = false;
1597   for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
1598        UI != E; ) {
1599     Use &TheUse = UI.getUse();
1600     Instruction *User = cast<Instruction>(*UI);
1601
1602     // Figure out which BB this cast is used in.  For PHI's this is the
1603     // appropriate predecessor block.
1604     BasicBlock *UserBB = User->getParent();
1605     if (PHINode *PN = dyn_cast<PHINode>(User)) {
1606       UserBB = PN->getIncomingBlock(TheUse);
1607     }
1608
1609     // Preincrement use iterator so we don't invalidate it.
1610     ++UI;
1611
1612     // If the block selected to receive the cast is an EH pad that does not
1613     // allow non-PHI instructions before the terminator, we can't sink the
1614     // cast.
1615     if (UserBB->getTerminator()->isEHPad())
1616       continue;
1617
1618     // If this user is in the same block as the cast, don't change the cast.
1619     if (UserBB == DefBB) continue;
1620
1621     // If we have already inserted a cast into this block, use it.
1622     CastInst *&InsertedCast = InsertedCasts[UserBB];
1623
1624     if (!InsertedCast) {
1625       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1626       assert(InsertPt != UserBB->end());
1627       InsertedCast = CastInst::Create(CI->getOpcode(), CI->getOperand(0),
1628                                       CI->getType(), "", &*InsertPt);
1629     }
1630
1631     // Replace a use of the cast with a use of the new cast.
1632     TheUse = InsertedCast;
1633     MadeChange = true;
1634     ++NumCastUses;
1635   }
1636
1637   // If we removed all uses, nuke the cast.
1638   if (CI->use_empty()) {
1639     CI->eraseFromParent();
1640     MadeChange = true;
1641   }
1642
1643   return MadeChange;
1644 }
1645
1646 /// If the specified cast instruction is a noop copy (e.g. it's casting from
1647 /// one pointer type to another, i32->i8 on PPC), sink it into user blocks to
1648 /// reduce the number of virtual registers that must be created and coalesced.
1649 ///
1650 /// Return true if any changes are made.
1651 ///
1652 static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI,
1653                                        const DataLayout &DL) {
1654   // If this is a noop copy,
1655   EVT SrcVT = TLI.getValueType(DL, CI->getOperand(0)->getType());
1656   EVT DstVT = TLI.getValueType(DL, CI->getType());
1657
1658   // This is an fp<->int conversion?
1659   if (SrcVT.isInteger() != DstVT.isInteger())
1660     return false;
1661
1662   // If this is an extension, it will be a zero or sign extension, which
1663   // isn't a noop.
1664   if (SrcVT.bitsLT(DstVT)) return false;
1665
1666   // If these values will be promoted, find out what they will be promoted
1667   // to.  This helps us consider truncates on PPC as noop copies when they
1668   // are.
1669   if (TLI.getTypeAction(CI->getContext(), SrcVT) ==
1670       TargetLowering::TypePromoteInteger)
1671     SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT);
1672   if (TLI.getTypeAction(CI->getContext(), DstVT) ==
1673       TargetLowering::TypePromoteInteger)
1674     DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT);
1675
1676   // If, after promotion, these are the same types, this is a noop copy.
1677   if (SrcVT != DstVT)
1678     return false;
1679
1680   return SinkCast(CI);
1681 }
1682
1683 /// Try to combine CI into a call to the llvm.uadd.with.overflow intrinsic if
1684 /// possible.
1685 ///
1686 /// Return true if any changes were made.
1687 static bool CombineUAddWithOverflow(CmpInst *CI) {
1688   Value *A, *B;
1689   Instruction *AddI;
1690   if (!match(CI,
1691              m_UAddWithOverflow(m_Value(A), m_Value(B), m_Instruction(AddI))))
1692     return false;
1693
1694   Type *Ty = AddI->getType();
1695   if (!isa<IntegerType>(Ty))
1696     return false;
1697
1698   // We don't want to move around uses of condition values this late, so we we
1699   // check if it is legal to create the call to the intrinsic in the basic
1700   // block containing the icmp:
1701
1702   if (AddI->getParent() != CI->getParent() && !AddI->hasOneUse())
1703     return false;
1704
1705 #ifndef NDEBUG
1706   // Someday m_UAddWithOverflow may get smarter, but this is a safe assumption
1707   // for now:
1708   if (AddI->hasOneUse())
1709     assert(*AddI->user_begin() == CI && "expected!");
1710 #endif
1711
1712   Module *M = CI->getModule();
1713   Value *F = Intrinsic::getDeclaration(M, Intrinsic::uadd_with_overflow, Ty);
1714
1715   auto *InsertPt = AddI->hasOneUse() ? CI : AddI;
1716
1717   auto *UAddWithOverflow =
1718       CallInst::Create(F, {A, B}, "uadd.overflow", InsertPt);
1719   auto *UAdd = ExtractValueInst::Create(UAddWithOverflow, 0, "uadd", InsertPt);
1720   auto *Overflow =
1721       ExtractValueInst::Create(UAddWithOverflow, 1, "overflow", InsertPt);
1722
1723   CI->replaceAllUsesWith(Overflow);
1724   AddI->replaceAllUsesWith(UAdd);
1725   CI->eraseFromParent();
1726   AddI->eraseFromParent();
1727   return true;
1728 }
1729
1730 /// Sink the given CmpInst into user blocks to reduce the number of virtual
1731 /// registers that must be created and coalesced. This is a clear win except on
1732 /// targets with multiple condition code registers (PowerPC), where it might
1733 /// lose; some adjustment may be wanted there.
1734 ///
1735 /// Return true if any changes are made.
1736 static bool SinkCmpExpression(CmpInst *CI) {
1737   BasicBlock *DefBB = CI->getParent();
1738
1739   /// Only insert a cmp in each block once.
1740   DenseMap<BasicBlock*, CmpInst*> InsertedCmps;
1741
1742   bool MadeChange = false;
1743   for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end();
1744        UI != E; ) {
1745     Use &TheUse = UI.getUse();
1746     Instruction *User = cast<Instruction>(*UI);
1747
1748     // Preincrement use iterator so we don't invalidate it.
1749     ++UI;
1750
1751     // Don't bother for PHI nodes.
1752     if (isa<PHINode>(User))
1753       continue;
1754
1755     // Figure out which BB this cmp is used in.
1756     BasicBlock *UserBB = User->getParent();
1757
1758     // If this user is in the same block as the cmp, don't change the cmp.
1759     if (UserBB == DefBB) continue;
1760
1761     // If we have already inserted a cmp into this block, use it.
1762     CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1763
1764     if (!InsertedCmp) {
1765       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1766       assert(InsertPt != UserBB->end());
1767       InsertedCmp =
1768           CmpInst::Create(CI->getOpcode(), CI->getPredicate(),
1769                           CI->getOperand(0), CI->getOperand(1), "", &*InsertPt);
1770     }
1771
1772     // Replace a use of the cmp with a use of the new cmp.
1773     TheUse = InsertedCmp;
1774     MadeChange = true;
1775     ++NumCmpUses;
1776   }
1777
1778   // If we removed all uses, nuke the cmp.
1779   if (CI->use_empty()) {
1780     CI->eraseFromParent();
1781     MadeChange = true;
1782   }
1783
1784   return MadeChange;
1785 }
1786
1787 static bool OptimizeCmpExpression(CmpInst *CI) {
1788   if (SinkCmpExpression(CI))
1789     return true;
1790
1791   if (CombineUAddWithOverflow(CI))
1792     return true;
1793
1794   return false;
1795 }
1796
1797 /// Check if the candidates could be combined with a shift instruction, which
1798 /// includes:
1799 /// 1. Truncate instruction
1800 /// 2. And instruction and the imm is a mask of the low bits:
1801 /// imm & (imm+1) == 0
1802 static bool isExtractBitsCandidateUse(Instruction *User) {
1803   if (!isa<TruncInst>(User)) {
1804     if (User->getOpcode() != Instruction::And ||
1805         !isa<ConstantInt>(User->getOperand(1)))
1806       return false;
1807
1808     const APInt &Cimm = cast<ConstantInt>(User->getOperand(1))->getValue();
1809
1810     if ((Cimm & (Cimm + 1)).getBoolValue())
1811       return false;
1812   }
1813   return true;
1814 }
1815
1816 /// Sink both shift and truncate instruction to the use of truncate's BB.
1817 static bool
1818 SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI,
1819                      DenseMap<BasicBlock *, BinaryOperator *> &InsertedShifts,
1820                      const TargetLowering &TLI, const DataLayout &DL) {
1821   BasicBlock *UserBB = User->getParent();
1822   DenseMap<BasicBlock *, CastInst *> InsertedTruncs;
1823   TruncInst *TruncI = dyn_cast<TruncInst>(User);
1824   bool MadeChange = false;
1825
1826   for (Value::user_iterator TruncUI = TruncI->user_begin(),
1827                             TruncE = TruncI->user_end();
1828        TruncUI != TruncE;) {
1829
1830     Use &TruncTheUse = TruncUI.getUse();
1831     Instruction *TruncUser = cast<Instruction>(*TruncUI);
1832     // Preincrement use iterator so we don't invalidate it.
1833
1834     ++TruncUI;
1835
1836     int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode());
1837     if (!ISDOpcode)
1838       continue;
1839
1840     // If the use is actually a legal node, there will not be an
1841     // implicit truncate.
1842     // FIXME: always querying the result type is just an
1843     // approximation; some nodes' legality is determined by the
1844     // operand or other means. There's no good way to find out though.
1845     if (TLI.isOperationLegalOrCustom(
1846             ISDOpcode, TLI.getValueType(DL, TruncUser->getType(), true)))
1847       continue;
1848
1849     // Don't bother for PHI nodes.
1850     if (isa<PHINode>(TruncUser))
1851       continue;
1852
1853     BasicBlock *TruncUserBB = TruncUser->getParent();
1854
1855     if (UserBB == TruncUserBB)
1856       continue;
1857
1858     BinaryOperator *&InsertedShift = InsertedShifts[TruncUserBB];
1859     CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
1860
1861     if (!InsertedShift && !InsertedTrunc) {
1862       BasicBlock::iterator InsertPt = TruncUserBB->getFirstInsertionPt();
1863       assert(InsertPt != TruncUserBB->end());
1864       // Sink the shift
1865       if (ShiftI->getOpcode() == Instruction::AShr)
1866         InsertedShift = BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI,
1867                                                    "", &*InsertPt);
1868       else
1869         InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI,
1870                                                    "", &*InsertPt);
1871
1872       // Sink the trunc
1873       BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt();
1874       TruncInsertPt++;
1875       assert(TruncInsertPt != TruncUserBB->end());
1876
1877       InsertedTrunc = CastInst::Create(TruncI->getOpcode(), InsertedShift,
1878                                        TruncI->getType(), "", &*TruncInsertPt);
1879
1880       MadeChange = true;
1881
1882       TruncTheUse = InsertedTrunc;
1883     }
1884   }
1885   return MadeChange;
1886 }
1887
1888 /// Sink the shift *right* instruction into user blocks if the uses could
1889 /// potentially be combined with this shift instruction and generate BitExtract
1890 /// instruction. It will only be applied if the architecture supports BitExtract
1891 /// instruction. Here is an example:
1892 /// BB1:
1893 ///   %x.extract.shift = lshr i64 %arg1, 32
1894 /// BB2:
1895 ///   %x.extract.trunc = trunc i64 %x.extract.shift to i16
1896 /// ==>
1897 ///
1898 /// BB2:
1899 ///   %x.extract.shift.1 = lshr i64 %arg1, 32
1900 ///   %x.extract.trunc = trunc i64 %x.extract.shift.1 to i16
1901 ///
1902 /// CodeGen will recoginze the pattern in BB2 and generate BitExtract
1903 /// instruction.
1904 /// Return true if any changes are made.
1905 static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI,
1906                                 const TargetLowering &TLI,
1907                                 const DataLayout &DL) {
1908   BasicBlock *DefBB = ShiftI->getParent();
1909
1910   /// Only insert instructions in each block once.
1911   DenseMap<BasicBlock *, BinaryOperator *> InsertedShifts;
1912
1913   bool shiftIsLegal = TLI.isTypeLegal(TLI.getValueType(DL, ShiftI->getType()));
1914
1915   bool MadeChange = false;
1916   for (Value::user_iterator UI = ShiftI->user_begin(), E = ShiftI->user_end();
1917        UI != E;) {
1918     Use &TheUse = UI.getUse();
1919     Instruction *User = cast<Instruction>(*UI);
1920     // Preincrement use iterator so we don't invalidate it.
1921     ++UI;
1922
1923     // Don't bother for PHI nodes.
1924     if (isa<PHINode>(User))
1925       continue;
1926
1927     if (!isExtractBitsCandidateUse(User))
1928       continue;
1929
1930     BasicBlock *UserBB = User->getParent();
1931
1932     if (UserBB == DefBB) {
1933       // If the shift and truncate instruction are in the same BB. The use of
1934       // the truncate(TruncUse) may still introduce another truncate if not
1935       // legal. In this case, we would like to sink both shift and truncate
1936       // instruction to the BB of TruncUse.
1937       // for example:
1938       // BB1:
1939       // i64 shift.result = lshr i64 opnd, imm
1940       // trunc.result = trunc shift.result to i16
1941       //
1942       // BB2:
1943       //   ----> We will have an implicit truncate here if the architecture does
1944       //   not have i16 compare.
1945       // cmp i16 trunc.result, opnd2
1946       //
1947       if (isa<TruncInst>(User) && shiftIsLegal
1948           // If the type of the truncate is legal, no trucate will be
1949           // introduced in other basic blocks.
1950           &&
1951           (!TLI.isTypeLegal(TLI.getValueType(DL, User->getType()))))
1952         MadeChange =
1953             SinkShiftAndTruncate(ShiftI, User, CI, InsertedShifts, TLI, DL);
1954
1955       continue;
1956     }
1957     // If we have already inserted a shift into this block, use it.
1958     BinaryOperator *&InsertedShift = InsertedShifts[UserBB];
1959
1960     if (!InsertedShift) {
1961       BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
1962       assert(InsertPt != UserBB->end());
1963
1964       if (ShiftI->getOpcode() == Instruction::AShr)
1965         InsertedShift = BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI,
1966                                                    "", &*InsertPt);
1967       else
1968         InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI,
1969                                                    "", &*InsertPt);
1970
1971       MadeChange = true;
1972     }
1973
1974     // Replace a use of the shift with a use of the new shift.
1975     TheUse = InsertedShift;
1976   }
1977
1978   // If we removed all uses, nuke the shift.
1979   if (ShiftI->use_empty())
1980     ShiftI->eraseFromParent();
1981
1982   return MadeChange;
1983 }
1984
1985 // Translate a masked load intrinsic like
1986 // <16 x i32 > @llvm.masked.load( <16 x i32>* %addr, i32 align,
1987 //                               <16 x i1> %mask, <16 x i32> %passthru)
1988 // to a chain of basic blocks, with loading element one-by-one if
1989 // the appropriate mask bit is set
1990 //
1991 //  %1 = bitcast i8* %addr to i32*
1992 //  %2 = extractelement <16 x i1> %mask, i32 0
1993 //  %3 = icmp eq i1 %2, true
1994 //  br i1 %3, label %cond.load, label %else
1995 //
1996 //cond.load:                                        ; preds = %0
1997 //  %4 = getelementptr i32* %1, i32 0
1998 //  %5 = load i32* %4
1999 //  %6 = insertelement <16 x i32> undef, i32 %5, i32 0
2000 //  br label %else
2001 //
2002 //else:                                             ; preds = %0, %cond.load
2003 //  %res.phi.else = phi <16 x i32> [ %6, %cond.load ], [ undef, %0 ]
2004 //  %7 = extractelement <16 x i1> %mask, i32 1
2005 //  %8 = icmp eq i1 %7, true
2006 //  br i1 %8, label %cond.load1, label %else2
2007 //
2008 //cond.load1:                                       ; preds = %else
2009 //  %9 = getelementptr i32* %1, i32 1
2010 //  %10 = load i32* %9
2011 //  %11 = insertelement <16 x i32> %res.phi.else, i32 %10, i32 1
2012 //  br label %else2
2013 //
2014 //else2:                                            ; preds = %else, %cond.load1
2015 //  %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else, %else ]
2016 //  %12 = extractelement <16 x i1> %mask, i32 2
2017 //  %13 = icmp eq i1 %12, true
2018 //  br i1 %13, label %cond.load4, label %else5
2019 //
2020 static void ScalarizeMaskedLoad(CallInst *CI) {
2021   Value *Ptr  = CI->getArgOperand(0);
2022   Value *Alignment = CI->getArgOperand(1);
2023   Value *Mask = CI->getArgOperand(2);
2024   Value *Src0 = CI->getArgOperand(3);
2025
2026   unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
2027   VectorType *VecType = dyn_cast<VectorType>(CI->getType());
2028   assert(VecType && "Unexpected return type of masked load intrinsic");
2029
2030   Type *EltTy = CI->getType()->getVectorElementType();
2031
2032   IRBuilder<> Builder(CI->getContext());
2033   Instruction *InsertPt = CI;
2034   BasicBlock *IfBlock = CI->getParent();
2035   BasicBlock *CondBlock = nullptr;
2036   BasicBlock *PrevIfBlock = CI->getParent();
2037
2038   Builder.SetInsertPoint(InsertPt);
2039   Builder.SetCurrentDebugLocation(CI->getDebugLoc());
2040
2041   // Short-cut if the mask is all-true.
2042   bool IsAllOnesMask = isa<Constant>(Mask) &&
2043     cast<Constant>(Mask)->isAllOnesValue();
2044
2045   if (IsAllOnesMask) {
2046     Value *NewI = Builder.CreateAlignedLoad(Ptr, AlignVal);
2047     CI->replaceAllUsesWith(NewI);
2048     CI->eraseFromParent();
2049     return;
2050   }
2051
2052   // Adjust alignment for the scalar instruction.
2053   AlignVal = std::min(AlignVal, VecType->getScalarSizeInBits()/8);
2054   // Bitcast %addr fron i8* to EltTy*
2055   Type *NewPtrType =
2056     EltTy->getPointerTo(cast<PointerType>(Ptr->getType())->getAddressSpace());
2057   Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType);
2058   unsigned VectorWidth = VecType->getNumElements();
2059
2060   Value *UndefVal = UndefValue::get(VecType);
2061
2062   // The result vector
2063   Value *VResult = UndefVal;
2064
2065   if (isa<ConstantVector>(Mask)) {
2066     for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2067       if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
2068           continue;
2069       Value *Gep =
2070           Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
2071       LoadInst* Load = Builder.CreateAlignedLoad(Gep, AlignVal);
2072       VResult = Builder.CreateInsertElement(VResult, Load,
2073                                             Builder.getInt32(Idx));
2074     }
2075     Value *NewI = Builder.CreateSelect(Mask, VResult, Src0);
2076     CI->replaceAllUsesWith(NewI);
2077     CI->eraseFromParent();
2078     return;
2079   }
2080
2081   PHINode *Phi = nullptr;
2082   Value *PrevPhi = UndefVal;
2083
2084   for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2085
2086     // Fill the "else" block, created in the previous iteration
2087     //
2088     //  %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else, %else ]
2089     //  %mask_1 = extractelement <16 x i1> %mask, i32 Idx
2090     //  %to_load = icmp eq i1 %mask_1, true
2091     //  br i1 %to_load, label %cond.load, label %else
2092     //
2093     if (Idx > 0) {
2094       Phi = Builder.CreatePHI(VecType, 2, "res.phi.else");
2095       Phi->addIncoming(VResult, CondBlock);
2096       Phi->addIncoming(PrevPhi, PrevIfBlock);
2097       PrevPhi = Phi;
2098       VResult = Phi;
2099     }
2100
2101     Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx));
2102     Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
2103                                     ConstantInt::get(Predicate->getType(), 1));
2104
2105     // Create "cond" block
2106     //
2107     //  %EltAddr = getelementptr i32* %1, i32 0
2108     //  %Elt = load i32* %EltAddr
2109     //  VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx
2110     //
2111     CondBlock = IfBlock->splitBasicBlock(InsertPt->getIterator(), "cond.load");
2112     Builder.SetInsertPoint(InsertPt);
2113
2114     Value *Gep =
2115         Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
2116     LoadInst *Load = Builder.CreateAlignedLoad(Gep, AlignVal);
2117     VResult = Builder.CreateInsertElement(VResult, Load, Builder.getInt32(Idx));
2118
2119     // Create "else" block, fill it in the next iteration
2120     BasicBlock *NewIfBlock =
2121         CondBlock->splitBasicBlock(InsertPt->getIterator(), "else");
2122     Builder.SetInsertPoint(InsertPt);
2123     Instruction *OldBr = IfBlock->getTerminator();
2124     BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
2125     OldBr->eraseFromParent();
2126     PrevIfBlock = IfBlock;
2127     IfBlock = NewIfBlock;
2128   }
2129
2130   Phi = Builder.CreatePHI(VecType, 2, "res.phi.select");
2131   Phi->addIncoming(VResult, CondBlock);
2132   Phi->addIncoming(PrevPhi, PrevIfBlock);
2133   Value *NewI = Builder.CreateSelect(Mask, Phi, Src0);
2134   CI->replaceAllUsesWith(NewI);
2135   CI->eraseFromParent();
2136 }
2137
2138 // Translate a masked store intrinsic, like
2139 // void @llvm.masked.store(<16 x i32> %src, <16 x i32>* %addr, i32 align,
2140 //                               <16 x i1> %mask)
2141 // to a chain of basic blocks, that stores element one-by-one if
2142 // the appropriate mask bit is set
2143 //
2144 //   %1 = bitcast i8* %addr to i32*
2145 //   %2 = extractelement <16 x i1> %mask, i32 0
2146 //   %3 = icmp eq i1 %2, true
2147 //   br i1 %3, label %cond.store, label %else
2148 //
2149 // cond.store:                                       ; preds = %0
2150 //   %4 = extractelement <16 x i32> %val, i32 0
2151 //   %5 = getelementptr i32* %1, i32 0
2152 //   store i32 %4, i32* %5
2153 //   br label %else
2154 //
2155 // else:                                             ; preds = %0, %cond.store
2156 //   %6 = extractelement <16 x i1> %mask, i32 1
2157 //   %7 = icmp eq i1 %6, true
2158 //   br i1 %7, label %cond.store1, label %else2
2159 //
2160 // cond.store1:                                      ; preds = %else
2161 //   %8 = extractelement <16 x i32> %val, i32 1
2162 //   %9 = getelementptr i32* %1, i32 1
2163 //   store i32 %8, i32* %9
2164 //   br label %else2
2165 //   . . .
2166 static void ScalarizeMaskedStore(CallInst *CI) {
2167   Value *Src = CI->getArgOperand(0);
2168   Value *Ptr  = CI->getArgOperand(1);
2169   Value *Alignment = CI->getArgOperand(2);
2170   Value *Mask = CI->getArgOperand(3);
2171
2172   unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
2173   VectorType *VecType = dyn_cast<VectorType>(Src->getType());
2174   assert(VecType && "Unexpected data type in masked store intrinsic");
2175
2176   Type *EltTy = VecType->getElementType();
2177
2178   IRBuilder<> Builder(CI->getContext());
2179   Instruction *InsertPt = CI;
2180   BasicBlock *IfBlock = CI->getParent();
2181   Builder.SetInsertPoint(InsertPt);
2182   Builder.SetCurrentDebugLocation(CI->getDebugLoc());
2183
2184   // Short-cut if the mask is all-true.
2185   bool IsAllOnesMask = isa<Constant>(Mask) &&
2186     cast<Constant>(Mask)->isAllOnesValue();
2187
2188   if (IsAllOnesMask) {
2189     Builder.CreateAlignedStore(Src, Ptr, AlignVal);
2190     CI->eraseFromParent();
2191     return;
2192   }
2193
2194   // Adjust alignment for the scalar instruction.
2195   AlignVal = std::max(AlignVal, VecType->getScalarSizeInBits()/8);
2196   // Bitcast %addr fron i8* to EltTy*
2197   Type *NewPtrType =
2198     EltTy->getPointerTo(cast<PointerType>(Ptr->getType())->getAddressSpace());
2199   Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType);
2200   unsigned VectorWidth = VecType->getNumElements();
2201
2202   if (isa<ConstantVector>(Mask)) {
2203     for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2204       if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
2205           continue;
2206       Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx));
2207       Value *Gep =
2208           Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
2209       Builder.CreateAlignedStore(OneElt, Gep, AlignVal);
2210     }
2211     CI->eraseFromParent();
2212     return;
2213   }
2214
2215   for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2216
2217     // Fill the "else" block, created in the previous iteration
2218     //
2219     //  %mask_1 = extractelement <16 x i1> %mask, i32 Idx
2220     //  %to_store = icmp eq i1 %mask_1, true
2221     //  br i1 %to_store, label %cond.store, label %else
2222     //
2223     Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx));
2224     Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
2225                                     ConstantInt::get(Predicate->getType(), 1));
2226
2227     // Create "cond" block
2228     //
2229     //  %OneElt = extractelement <16 x i32> %Src, i32 Idx
2230     //  %EltAddr = getelementptr i32* %1, i32 0
2231     //  %store i32 %OneElt, i32* %EltAddr
2232     //
2233     BasicBlock *CondBlock =
2234         IfBlock->splitBasicBlock(InsertPt->getIterator(), "cond.store");
2235     Builder.SetInsertPoint(InsertPt);
2236
2237     Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx));
2238     Value *Gep =
2239         Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx));
2240     Builder.CreateAlignedStore(OneElt, Gep, AlignVal);
2241
2242     // Create "else" block, fill it in the next iteration
2243     BasicBlock *NewIfBlock =
2244         CondBlock->splitBasicBlock(InsertPt->getIterator(), "else");
2245     Builder.SetInsertPoint(InsertPt);
2246     Instruction *OldBr = IfBlock->getTerminator();
2247     BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
2248     OldBr->eraseFromParent();
2249     IfBlock = NewIfBlock;
2250   }
2251   CI->eraseFromParent();
2252 }
2253
2254 // Translate a masked gather intrinsic like
2255 // <16 x i32 > @llvm.masked.gather.v16i32( <16 x i32*> %Ptrs, i32 4,
2256 //                               <16 x i1> %Mask, <16 x i32> %Src)
2257 // to a chain of basic blocks, with loading element one-by-one if
2258 // the appropriate mask bit is set
2259 //
2260 // % Ptrs = getelementptr i32, i32* %base, <16 x i64> %ind
2261 // % Mask0 = extractelement <16 x i1> %Mask, i32 0
2262 // % ToLoad0 = icmp eq i1 % Mask0, true
2263 // br i1 % ToLoad0, label %cond.load, label %else
2264 //
2265 // cond.load:
2266 // % Ptr0 = extractelement <16 x i32*> %Ptrs, i32 0
2267 // % Load0 = load i32, i32* % Ptr0, align 4
2268 // % Res0 = insertelement <16 x i32> undef, i32 % Load0, i32 0
2269 // br label %else
2270 //
2271 // else:
2272 // %res.phi.else = phi <16 x i32>[% Res0, %cond.load], [undef, % 0]
2273 // % Mask1 = extractelement <16 x i1> %Mask, i32 1
2274 // % ToLoad1 = icmp eq i1 % Mask1, true
2275 // br i1 % ToLoad1, label %cond.load1, label %else2
2276 //
2277 // cond.load1:
2278 // % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1
2279 // % Load1 = load i32, i32* % Ptr1, align 4
2280 // % Res1 = insertelement <16 x i32> %res.phi.else, i32 % Load1, i32 1
2281 // br label %else2
2282 // . . .
2283 // % Result = select <16 x i1> %Mask, <16 x i32> %res.phi.select, <16 x i32> %Src
2284 // ret <16 x i32> %Result
2285 static void ScalarizeMaskedGather(CallInst *CI) {
2286   Value *Ptrs = CI->getArgOperand(0);
2287   Value *Alignment = CI->getArgOperand(1);
2288   Value *Mask = CI->getArgOperand(2);
2289   Value *Src0 = CI->getArgOperand(3);
2290
2291   VectorType *VecType = dyn_cast<VectorType>(CI->getType());
2292
2293   assert(VecType && "Unexpected return type of masked load intrinsic");
2294
2295   IRBuilder<> Builder(CI->getContext());
2296   Instruction *InsertPt = CI;
2297   BasicBlock *IfBlock = CI->getParent();
2298   BasicBlock *CondBlock = nullptr;
2299   BasicBlock *PrevIfBlock = CI->getParent();
2300   Builder.SetInsertPoint(InsertPt);
2301   unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
2302
2303   Builder.SetCurrentDebugLocation(CI->getDebugLoc());
2304
2305   Value *UndefVal = UndefValue::get(VecType);
2306
2307   // The result vector
2308   Value *VResult = UndefVal;
2309   unsigned VectorWidth = VecType->getNumElements();
2310
2311   // Shorten the way if the mask is a vector of constants.
2312   bool IsConstMask = isa<ConstantVector>(Mask);
2313
2314   if (IsConstMask) {
2315     for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2316       if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
2317         continue;
2318       Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
2319                                                 "Ptr" + Twine(Idx));
2320       LoadInst *Load = Builder.CreateAlignedLoad(Ptr, AlignVal,
2321                                                  "Load" + Twine(Idx));
2322       VResult = Builder.CreateInsertElement(VResult, Load,
2323                                             Builder.getInt32(Idx),
2324                                             "Res" + Twine(Idx));
2325     }
2326     Value *NewI = Builder.CreateSelect(Mask, VResult, Src0);
2327     CI->replaceAllUsesWith(NewI);
2328     CI->eraseFromParent();
2329     return;
2330   }
2331
2332   PHINode *Phi = nullptr;
2333   Value *PrevPhi = UndefVal;
2334
2335   for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2336
2337     // Fill the "else" block, created in the previous iteration
2338     //
2339     //  %Mask1 = extractelement <16 x i1> %Mask, i32 1
2340     //  %ToLoad1 = icmp eq i1 %Mask1, true
2341     //  br i1 %ToLoad1, label %cond.load, label %else
2342     //
2343     if (Idx > 0) {
2344       Phi = Builder.CreatePHI(VecType, 2, "res.phi.else");
2345       Phi->addIncoming(VResult, CondBlock);
2346       Phi->addIncoming(PrevPhi, PrevIfBlock);
2347       PrevPhi = Phi;
2348       VResult = Phi;
2349     }
2350
2351     Value *Predicate = Builder.CreateExtractElement(Mask,
2352                                                     Builder.getInt32(Idx),
2353                                                     "Mask" + Twine(Idx));
2354     Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
2355                                     ConstantInt::get(Predicate->getType(), 1),
2356                                     "ToLoad" + Twine(Idx));
2357
2358     // Create "cond" block
2359     //
2360     //  %EltAddr = getelementptr i32* %1, i32 0
2361     //  %Elt = load i32* %EltAddr
2362     //  VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx
2363     //
2364     CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.load");
2365     Builder.SetInsertPoint(InsertPt);
2366
2367     Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
2368                                               "Ptr" + Twine(Idx));
2369     LoadInst *Load = Builder.CreateAlignedLoad(Ptr, AlignVal,
2370                                                "Load" + Twine(Idx));
2371     VResult = Builder.CreateInsertElement(VResult, Load, Builder.getInt32(Idx),
2372                                           "Res" + Twine(Idx));
2373
2374     // Create "else" block, fill it in the next iteration
2375     BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
2376     Builder.SetInsertPoint(InsertPt);
2377     Instruction *OldBr = IfBlock->getTerminator();
2378     BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
2379     OldBr->eraseFromParent();
2380     PrevIfBlock = IfBlock;
2381     IfBlock = NewIfBlock;
2382   }
2383
2384   Phi = Builder.CreatePHI(VecType, 2, "res.phi.select");
2385   Phi->addIncoming(VResult, CondBlock);
2386   Phi->addIncoming(PrevPhi, PrevIfBlock);
2387   Value *NewI = Builder.CreateSelect(Mask, Phi, Src0);
2388   CI->replaceAllUsesWith(NewI);
2389   CI->eraseFromParent();
2390 }
2391
2392 // Translate a masked scatter intrinsic, like
2393 // void @llvm.masked.scatter.v16i32(<16 x i32> %Src, <16 x i32*>* %Ptrs, i32 4,
2394 //                                  <16 x i1> %Mask)
2395 // to a chain of basic blocks, that stores element one-by-one if
2396 // the appropriate mask bit is set.
2397 //
2398 // % Ptrs = getelementptr i32, i32* %ptr, <16 x i64> %ind
2399 // % Mask0 = extractelement <16 x i1> % Mask, i32 0
2400 // % ToStore0 = icmp eq i1 % Mask0, true
2401 // br i1 %ToStore0, label %cond.store, label %else
2402 //
2403 // cond.store:
2404 // % Elt0 = extractelement <16 x i32> %Src, i32 0
2405 // % Ptr0 = extractelement <16 x i32*> %Ptrs, i32 0
2406 // store i32 %Elt0, i32* % Ptr0, align 4
2407 // br label %else
2408 //
2409 // else:
2410 // % Mask1 = extractelement <16 x i1> % Mask, i32 1
2411 // % ToStore1 = icmp eq i1 % Mask1, true
2412 // br i1 % ToStore1, label %cond.store1, label %else2
2413 //
2414 // cond.store1:
2415 // % Elt1 = extractelement <16 x i32> %Src, i32 1
2416 // % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1
2417 // store i32 % Elt1, i32* % Ptr1, align 4
2418 // br label %else2
2419 //   . . .
2420 static void ScalarizeMaskedScatter(CallInst *CI) {
2421   Value *Src = CI->getArgOperand(0);
2422   Value *Ptrs = CI->getArgOperand(1);
2423   Value *Alignment = CI->getArgOperand(2);
2424   Value *Mask = CI->getArgOperand(3);
2425
2426   assert(isa<VectorType>(Src->getType()) &&
2427          "Unexpected data type in masked scatter intrinsic");
2428   assert(isa<VectorType>(Ptrs->getType()) &&
2429          isa<PointerType>(Ptrs->getType()->getVectorElementType()) &&
2430          "Vector of pointers is expected in masked scatter intrinsic");
2431
2432   IRBuilder<> Builder(CI->getContext());
2433   Instruction *InsertPt = CI;
2434   BasicBlock *IfBlock = CI->getParent();
2435   Builder.SetInsertPoint(InsertPt);
2436   Builder.SetCurrentDebugLocation(CI->getDebugLoc());
2437
2438   unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue();
2439   unsigned VectorWidth = Src->getType()->getVectorNumElements();
2440
2441   // Shorten the way if the mask is a vector of constants.
2442   bool IsConstMask = isa<ConstantVector>(Mask);
2443
2444   if (IsConstMask) {
2445     for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2446       if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue())
2447         continue;
2448       Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx),
2449                                                    "Elt" + Twine(Idx));
2450       Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
2451                                                 "Ptr" + Twine(Idx));
2452       Builder.CreateAlignedStore(OneElt, Ptr, AlignVal);
2453     }
2454     CI->eraseFromParent();
2455     return;
2456   }
2457   for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) {
2458     // Fill the "else" block, created in the previous iteration
2459     //
2460     //  % Mask1 = extractelement <16 x i1> % Mask, i32 Idx
2461     //  % ToStore = icmp eq i1 % Mask1, true
2462     //  br i1 % ToStore, label %cond.store, label %else
2463     //
2464     Value *Predicate = Builder.CreateExtractElement(Mask,
2465                                                     Builder.getInt32(Idx),
2466                                                     "Mask" + Twine(Idx));
2467     Value *Cmp =
2468        Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate,
2469                           ConstantInt::get(Predicate->getType(), 1),
2470                           "ToStore" + Twine(Idx));
2471
2472     // Create "cond" block
2473     //
2474     //  % Elt1 = extractelement <16 x i32> %Src, i32 1
2475     //  % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1
2476     //  %store i32 % Elt1, i32* % Ptr1
2477     //
2478     BasicBlock *CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store");
2479     Builder.SetInsertPoint(InsertPt);
2480
2481     Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx),
2482                                                  "Elt" + Twine(Idx));
2483     Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx),
2484                                               "Ptr" + Twine(Idx));
2485     Builder.CreateAlignedStore(OneElt, Ptr, AlignVal);
2486
2487     // Create "else" block, fill it in the next iteration
2488     BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else");
2489     Builder.SetInsertPoint(InsertPt);
2490     Instruction *OldBr = IfBlock->getTerminator();
2491     BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr);
2492     OldBr->eraseFromParent();
2493     IfBlock = NewIfBlock;
2494   }
2495   CI->eraseFromParent();
2496 }
2497
2498 /// If counting leading or trailing zeros is an expensive operation and a zero
2499 /// input is defined, add a check for zero to avoid calling the intrinsic.
2500 ///
2501 /// We want to transform:
2502 ///     %z = call i64 @llvm.cttz.i64(i64 %A, i1 false)
2503 ///
2504 /// into:
2505 ///   entry:
2506 ///     %cmpz = icmp eq i64 %A, 0
2507 ///     br i1 %cmpz, label %cond.end, label %cond.false
2508 ///   cond.false:
2509 ///     %z = call i64 @llvm.cttz.i64(i64 %A, i1 true)
2510 ///     br label %cond.end
2511 ///   cond.end:
2512 ///     %ctz = phi i64 [ 64, %entry ], [ %z, %cond.false ]
2513 ///
2514 /// If the transform is performed, return true and set ModifiedDT to true.
2515 static bool despeculateCountZeros(IntrinsicInst *CountZeros,
2516                                   const TargetLowering *TLI,
2517                                   const DataLayout *DL,
2518                                   bool &ModifiedDT) {
2519   if (!TLI || !DL)
2520     return false;
2521
2522   // If a zero input is undefined, it doesn't make sense to despeculate that.
2523   if (match(CountZeros->getOperand(1), m_One()))
2524     return false;
2525
2526   // If it's cheap to speculate, there's nothing to do.
2527   auto IntrinsicID = CountZeros->getIntrinsicID();
2528   if ((IntrinsicID == Intrinsic::cttz && TLI->isCheapToSpeculateCttz()) ||
2529       (IntrinsicID == Intrinsic::ctlz && TLI->isCheapToSpeculateCtlz()))
2530     return false;
2531
2532   // Only handle legal scalar cases. Anything else requires too much work.
2533   Type *Ty = CountZeros->getType();
2534   unsigned SizeInBits = Ty->getPrimitiveSizeInBits();
2535   if (Ty->isVectorTy() || SizeInBits > DL->getLargestLegalIntTypeSize())
2536     return false;
2537
2538   // The intrinsic will be sunk behind a compare against zero and branch.
2539   BasicBlock *StartBlock = CountZeros->getParent();
2540   BasicBlock *CallBlock = StartBlock->splitBasicBlock(CountZeros, "cond.false");
2541
2542   // Create another block after the count zero intrinsic. A PHI will be added
2543   // in this block to select the result of the intrinsic or the bit-width
2544   // constant if the input to the intrinsic is zero.
2545   BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(CountZeros));
2546   BasicBlock *EndBlock = CallBlock->splitBasicBlock(SplitPt, "cond.end");
2547
2548   // Set up a builder to create a compare, conditional branch, and PHI.
2549   IRBuilder<> Builder(CountZeros->getContext());
2550   Builder.SetInsertPoint(StartBlock->getTerminator());
2551   Builder.SetCurrentDebugLocation(CountZeros->getDebugLoc());
2552
2553   // Replace the unconditional branch that was created by the first split with
2554   // a compare against zero and a conditional branch.
2555   Value *Zero = Constant::getNullValue(Ty);
2556   Value *Cmp = Builder.CreateICmpEQ(CountZeros->getOperand(0), Zero, "cmpz");
2557   Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
2558   StartBlock->getTerminator()->eraseFromParent();
2559
2560   // Create a PHI in the end block to select either the output of the intrinsic
2561   // or the bit width of the operand.
2562   Builder.SetInsertPoint(&EndBlock->front());
2563   PHINode *PN = Builder.CreatePHI(Ty, 2, "ctz");
2564   CountZeros->replaceAllUsesWith(PN);
2565   Value *BitWidth = Builder.getInt(APInt(SizeInBits, SizeInBits));
2566   PN->addIncoming(BitWidth, StartBlock);
2567   PN->addIncoming(CountZeros, CallBlock);
2568
2569   // We are explicitly handling the zero case, so we can set the intrinsic's
2570   // undefined zero argument to 'true'. This will also prevent reprocessing the
2571   // intrinsic; we only despeculate when a zero input is defined.
2572   CountZeros->setArgOperand(1, Builder.getTrue());
2573   ModifiedDT = true;
2574   return true;
2575 }
2576
2577 bool CodeGenPrepare::optimizeCallInst(CallInst *CI, bool& ModifiedDT) {
2578   BasicBlock *BB = CI->getParent();
2579
2580   // Lower inline assembly if we can.
2581   // If we found an inline asm expession, and if the target knows how to
2582   // lower it to normal LLVM code, do so now.
2583   if (TLI && isa<InlineAsm>(CI->getCalledValue())) {
2584     if (TLI->ExpandInlineAsm(CI)) {
2585       // Avoid invalidating the iterator.
2586       CurInstIterator = BB->begin();
2587       // Avoid processing instructions out of order, which could cause
2588       // reuse before a value is defined.
2589       SunkAddrs.clear();
2590       return true;
2591     }
2592     // Sink address computing for memory operands into the block.
2593     if (optimizeInlineAsmInst(CI))
2594       return true;
2595   }
2596
2597   // Align the pointer arguments to this call if the target thinks it's a good
2598   // idea
2599   unsigned MinSize, PrefAlign;
2600   if (TLI && TLI->shouldAlignPointerArgs(CI, MinSize, PrefAlign)) {
2601     for (auto &Arg : CI->arg_operands()) {
2602       // We want to align both objects whose address is used directly and
2603       // objects whose address is used in casts and GEPs, though it only makes
2604       // sense for GEPs if the offset is a multiple of the desired alignment and
2605       // if size - offset meets the size threshold.
2606       if (!Arg->getType()->isPointerTy())
2607         continue;
2608       APInt Offset(DL->getPointerSizeInBits(
2609                        cast<PointerType>(Arg->getType())->getAddressSpace()),
2610                    0);
2611       Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*DL, Offset);
2612       uint64_t Offset2 = Offset.getLimitedValue();
2613       if ((Offset2 & (PrefAlign-1)) != 0)
2614         continue;
2615       AllocaInst *AI;
2616       if ((AI = dyn_cast<AllocaInst>(Val)) && AI->getAlignment() < PrefAlign &&
2617           DL->getTypeAllocSize(AI->getAllocatedType()) >= MinSize + Offset2)
2618         AI->setAlignment(PrefAlign);
2619       // Global variables can only be aligned if they are defined in this
2620       // object (i.e. they are uniquely initialized in this object), and
2621       // over-aligning global variables that have an explicit section is
2622       // forbidden.
2623       GlobalVariable *GV;
2624       if ((GV = dyn_cast<GlobalVariable>(Val)) && GV->canIncreaseAlignment() &&
2625           GV->getAlignment() < PrefAlign &&
2626           DL->getTypeAllocSize(GV->getType()->getElementType()) >=
2627               MinSize + Offset2)
2628         GV->setAlignment(PrefAlign);
2629     }
2630     // If this is a memcpy (or similar) then we may be able to improve the
2631     // alignment
2632     if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(CI)) {
2633       unsigned Align = getKnownAlignment(MI->getDest(), *DL);
2634       if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
2635         Align = std::min(Align, getKnownAlignment(MTI->getSource(), *DL));
2636       if (Align > MI->getAlignment())
2637         MI->setAlignment(ConstantInt::get(MI->getAlignmentType(), Align));
2638     }
2639   }
2640
2641   IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI);
2642   if (II) {
2643     switch (II->getIntrinsicID()) {
2644     default: break;
2645     case Intrinsic::objectsize: {
2646       // Lower all uses of llvm.objectsize.*
2647       bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1);
2648       Type *ReturnTy = CI->getType();
2649       Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL);
2650
2651       // Substituting this can cause recursive simplifications, which can
2652       // invalidate our iterator.  Use a WeakVH to hold onto it in case this
2653       // happens.
2654       WeakVH IterHandle(&*CurInstIterator);
2655
2656       replaceAndRecursivelySimplify(CI, RetVal,
2657                                     TLInfo, nullptr);
2658
2659       // If the iterator instruction was recursively deleted, start over at the
2660       // start of the block.
2661       if (IterHandle != CurInstIterator.getNodePtrUnchecked()) {
2662         CurInstIterator = BB->begin();
2663         SunkAddrs.clear();
2664       }
2665       return true;
2666     }
2667     case Intrinsic::masked_load: {
2668       // Scalarize unsupported vector masked load
2669       if (!TTI->isLegalMaskedLoad(CI->getType())) {
2670         ScalarizeMaskedLoad(CI);
2671         ModifiedDT = true;
2672         return true;
2673       }
2674       return false;
2675     }
2676     case Intrinsic::masked_store: {
2677       if (!TTI->isLegalMaskedStore(CI->getArgOperand(0)->getType())) {
2678         ScalarizeMaskedStore(CI);
2679         ModifiedDT = true;
2680         return true;
2681       }
2682       return false;
2683     }
2684     case Intrinsic::masked_gather: {
2685       if (!TTI->isLegalMaskedGather(CI->getType())) {
2686         ScalarizeMaskedGather(CI);
2687         ModifiedDT = true;
2688         return true;
2689       }
2690       return false;
2691     }
2692     case Intrinsic::masked_scatter: {
2693       if (!TTI->isLegalMaskedScatter(CI->getArgOperand(0)->getType())) {
2694         ScalarizeMaskedScatter(CI);
2695         ModifiedDT = true;
2696         return true;
2697       }
2698       return false;
2699     }
2700     case Intrinsic::aarch64_stlxr:
2701     case Intrinsic::aarch64_stxr: {
2702       ZExtInst *ExtVal = dyn_cast<ZExtInst>(CI->getArgOperand(0));
2703       if (!ExtVal || !ExtVal->hasOneUse() ||
2704           ExtVal->getParent() == CI->getParent())
2705         return false;
2706       // Sink a zext feeding stlxr/stxr before it, so it can be folded into it.
2707       ExtVal->moveBefore(CI);
2708       // Mark this instruction as "inserted by CGP", so that other
2709       // optimizations don't touch it.
2710       InsertedInsts.insert(ExtVal);
2711       return true;
2712     }
2713     case Intrinsic::invariant_group_barrier:
2714       II->replaceAllUsesWith(II->getArgOperand(0));
2715       II->eraseFromParent();
2716       return true;
2717
2718     case Intrinsic::cttz:
2719     case Intrinsic::ctlz:
2720       // If counting zeros is expensive, try to avoid it.
2721       return despeculateCountZeros(II, TLI, DL, ModifiedDT);
2722     }
2723
2724     if (TLI) {
2725       // Unknown address space.
2726       // TODO: Target hook to pick which address space the intrinsic cares
2727       // about?
2728       unsigned AddrSpace = ~0u;
2729       SmallVector<Value*, 2> PtrOps;
2730       Type *AccessTy;
2731       if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy, AddrSpace))
2732         while (!PtrOps.empty())
2733           if (optimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy, AddrSpace))
2734             return true;
2735     }
2736   }
2737
2738   // From here on out we're working with named functions.
2739   if (!CI->getCalledFunction()) return false;
2740
2741   // Lower all default uses of _chk calls.  This is very similar
2742   // to what InstCombineCalls does, but here we are only lowering calls
2743   // to fortified library functions (e.g. __memcpy_chk) that have the default
2744   // "don't know" as the objectsize.  Anything else should be left alone.
2745   FortifiedLibCallSimplifier Simplifier(TLInfo, true);
2746   if (Value *V = Simplifier.optimizeCall(CI)) {
2747     CI->replaceAllUsesWith(V);
2748     CI->eraseFromParent();
2749     return true;
2750   }
2751   return false;
2752 }
2753
2754 /// Look for opportunities to duplicate return instructions to the predecessor
2755 /// to enable tail call optimizations. The case it is currently looking for is:
2756 /// @code
2757 /// bb0:
2758 ///   %tmp0 = tail call i32 @f0()
2759 ///   br label %return
2760 /// bb1:
2761 ///   %tmp1 = tail call i32 @f1()
2762 ///   br label %return
2763 /// bb2:
2764 ///   %tmp2 = tail call i32 @f2()
2765 ///   br label %return
2766 /// return:
2767 ///   %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ]
2768 ///   ret i32 %retval
2769 /// @endcode
2770 ///
2771 /// =>
2772 ///
2773 /// @code
2774 /// bb0:
2775 ///   %tmp0 = tail call i32 @f0()
2776 ///   ret i32 %tmp0
2777 /// bb1:
2778 ///   %tmp1 = tail call i32 @f1()
2779 ///   ret i32 %tmp1
2780 /// bb2:
2781 ///   %tmp2 = tail call i32 @f2()
2782 ///   ret i32 %tmp2
2783 /// @endcode
2784 bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB) {
2785   if (!TLI)
2786     return false;
2787
2788   ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator());
2789   if (!RI)
2790     return false;
2791
2792   PHINode *PN = nullptr;
2793   BitCastInst *BCI = nullptr;
2794   Value *V = RI->getReturnValue();
2795   if (V) {
2796     BCI = dyn_cast<BitCastInst>(V);
2797     if (BCI)
2798       V = BCI->getOperand(0);
2799
2800     PN = dyn_cast<PHINode>(V);
2801     if (!PN)
2802       return false;
2803   }
2804
2805   if (PN && PN->getParent() != BB)
2806     return false;
2807
2808   // It's not safe to eliminate the sign / zero extension of the return value.
2809   // See llvm::isInTailCallPosition().
2810   const Function *F = BB->getParent();
2811   AttributeSet CallerAttrs = F->getAttributes();
2812   if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) ||
2813       CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt))
2814     return false;
2815
2816   // Make sure there are no instructions between the PHI and return, or that the
2817   // return is the first instruction in the block.
2818   if (PN) {
2819     BasicBlock::iterator BI = BB->begin();
2820     do { ++BI; } while (isa<DbgInfoIntrinsic>(BI));
2821     if (&*BI == BCI)
2822       // Also skip over the bitcast.
2823       ++BI;
2824     if (&*BI != RI)
2825       return false;
2826   } else {
2827     BasicBlock::iterator BI = BB->begin();
2828     while (isa<DbgInfoIntrinsic>(BI)) ++BI;
2829     if (&*BI != RI)
2830       return false;
2831   }
2832
2833   /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail
2834   /// call.
2835   SmallVector<CallInst*, 4> TailCalls;
2836   if (PN) {
2837     for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
2838       CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I));
2839       // Make sure the phi value is indeed produced by the tail call.
2840       if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) &&
2841           TLI->mayBeEmittedAsTailCall(CI))
2842         TailCalls.push_back(CI);
2843     }
2844   } else {
2845     SmallPtrSet<BasicBlock*, 4> VisitedBBs;
2846     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
2847       if (!VisitedBBs.insert(*PI).second)
2848         continue;
2849
2850       BasicBlock::InstListType &InstList = (*PI)->getInstList();
2851       BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin();
2852       BasicBlock::InstListType::reverse_iterator RE = InstList.rend();
2853       do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI));
2854       if (RI == RE)
2855         continue;
2856
2857       CallInst *CI = dyn_cast<CallInst>(&*RI);
2858       if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI))
2859         TailCalls.push_back(CI);
2860     }
2861   }
2862
2863   bool Changed = false;
2864   for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) {
2865     CallInst *CI = TailCalls[i];
2866     CallSite CS(CI);
2867
2868     // Conservatively require the attributes of the call to match those of the
2869     // return. Ignore noalias because it doesn't affect the call sequence.
2870     AttributeSet CalleeAttrs = CS.getAttributes();
2871     if (AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
2872           removeAttribute(Attribute::NoAlias) !=
2873         AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex).
2874           removeAttribute(Attribute::NoAlias))
2875       continue;
2876
2877     // Make sure the call instruction is followed by an unconditional branch to
2878     // the return block.
2879     BasicBlock *CallBB = CI->getParent();
2880     BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator());
2881     if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
2882       continue;
2883
2884     // Duplicate the return into CallBB.
2885     (void)FoldReturnIntoUncondBranch(RI, BB, CallBB);
2886     ModifiedDT = Changed = true;
2887     ++NumRetsDup;
2888   }
2889
2890   // If we eliminated all predecessors of the block, delete the block now.
2891   if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
2892     BB->eraseFromParent();
2893
2894   return Changed;
2895 }
2896
2897 //===----------------------------------------------------------------------===//
2898 // Memory Optimization
2899 //===----------------------------------------------------------------------===//
2900
2901 namespace {
2902
2903 /// This is an extended version of TargetLowering::AddrMode
2904 /// which holds actual Value*'s for register values.
2905 struct ExtAddrMode : public TargetLowering::AddrMode {
2906   Value *BaseReg;
2907   Value *ScaledReg;
2908   ExtAddrMode() : BaseReg(nullptr), ScaledReg(nullptr) {}
2909   void print(raw_ostream &OS) const;
2910   void dump() const;
2911
2912   bool operator==(const ExtAddrMode& O) const {
2913     return (BaseReg == O.BaseReg) && (ScaledReg == O.ScaledReg) &&
2914            (BaseGV == O.BaseGV) && (BaseOffs == O.BaseOffs) &&
2915            (HasBaseReg == O.HasBaseReg) && (Scale == O.Scale);
2916   }
2917 };
2918
2919 #ifndef NDEBUG
2920 static inline raw_ostream &operator<<(raw_ostream &OS, const ExtAddrMode &AM) {
2921   AM.print(OS);
2922   return OS;
2923 }
2924 #endif
2925
2926 void ExtAddrMode::print(raw_ostream &OS) const {
2927   bool NeedPlus = false;
2928   OS << "[";
2929   if (BaseGV) {
2930     OS << (NeedPlus ? " + " : "")
2931        << "GV:";
2932     BaseGV->printAsOperand(OS, /*PrintType=*/false);
2933     NeedPlus = true;
2934   }
2935
2936   if (BaseOffs) {
2937     OS << (NeedPlus ? " + " : "")
2938        << BaseOffs;
2939     NeedPlus = true;
2940   }
2941
2942   if (BaseReg) {
2943     OS << (NeedPlus ? " + " : "")
2944        << "Base:";
2945     BaseReg->printAsOperand(OS, /*PrintType=*/false);
2946     NeedPlus = true;
2947   }
2948   if (Scale) {
2949     OS << (NeedPlus ? " + " : "")
2950        << Scale << "*";
2951     ScaledReg->printAsOperand(OS, /*PrintType=*/false);
2952   }
2953
2954   OS << ']';
2955 }
2956
2957 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2958 void ExtAddrMode::dump() const {
2959   print(dbgs());
2960   dbgs() << '\n';
2961 }
2962 #endif
2963
2964 /// \brief This class provides transaction based operation on the IR.
2965 /// Every change made through this class is recorded in the internal state and
2966 /// can be undone (rollback) until commit is called.
2967 class TypePromotionTransaction {
2968
2969   /// \brief This represents the common interface of the individual transaction.
2970   /// Each class implements the logic for doing one specific modification on
2971   /// the IR via the TypePromotionTransaction.
2972   class TypePromotionAction {
2973   protected:
2974     /// The Instruction modified.
2975     Instruction *Inst;
2976
2977   public:
2978     /// \brief Constructor of the action.
2979     /// The constructor performs the related action on the IR.
2980     TypePromotionAction(Instruction *Inst) : Inst(Inst) {}
2981
2982     virtual ~TypePromotionAction() {}
2983
2984     /// \brief Undo the modification done by this action.
2985     /// When this method is called, the IR must be in the same state as it was
2986     /// before this action was applied.
2987     /// \pre Undoing the action works if and only if the IR is in the exact same
2988     /// state as it was directly after this action was applied.
2989     virtual void undo() = 0;
2990
2991     /// \brief Advocate every change made by this action.
2992     /// When the results on the IR of the action are to be kept, it is important
2993     /// to call this function, otherwise hidden information may be kept forever.
2994     virtual void commit() {
2995       // Nothing to be done, this action is not doing anything.
2996     }
2997   };
2998
2999   /// \brief Utility to remember the position of an instruction.
3000   class InsertionHandler {
3001     /// Position of an instruction.
3002     /// Either an instruction:
3003     /// - Is the first in a basic block: BB is used.
3004     /// - Has a previous instructon: PrevInst is used.
3005     union {
3006       Instruction *PrevInst;
3007       BasicBlock *BB;
3008     } Point;
3009     /// Remember whether or not the instruction had a previous instruction.
3010     bool HasPrevInstruction;
3011
3012   public:
3013     /// \brief Record the position of \p Inst.
3014     InsertionHandler(Instruction *Inst) {
3015       BasicBlock::iterator It = Inst->getIterator();
3016       HasPrevInstruction = (It != (Inst->getParent()->begin()));
3017       if (HasPrevInstruction)
3018         Point.PrevInst = &*--It;
3019       else
3020         Point.BB = Inst->getParent();
3021     }
3022
3023     /// \brief Insert \p Inst at the recorded position.
3024     void insert(Instruction *Inst) {
3025       if (HasPrevInstruction) {
3026         if (Inst->getParent())
3027           Inst->removeFromParent();
3028         Inst->insertAfter(Point.PrevInst);
3029       } else {
3030         Instruction *Position = &*Point.BB->getFirstInsertionPt();
3031         if (Inst->getParent())
3032           Inst->moveBefore(Position);
3033         else
3034           Inst->insertBefore(Position);
3035       }
3036     }
3037   };
3038
3039   /// \brief Move an instruction before another.
3040   class InstructionMoveBefore : public TypePromotionAction {
3041     /// Original position of the instruction.
3042     InsertionHandler Position;
3043
3044   public:
3045     /// \brief Move \p Inst before \p Before.
3046     InstructionMoveBefore(Instruction *Inst, Instruction *Before)
3047         : TypePromotionAction(Inst), Position(Inst) {
3048       DEBUG(dbgs() << "Do: move: " << *Inst << "\nbefore: " << *Before << "\n");
3049       Inst->moveBefore(Before);
3050     }
3051
3052     /// \brief Move the instruction back to its original position.
3053     void undo() override {
3054       DEBUG(dbgs() << "Undo: moveBefore: " << *Inst << "\n");
3055       Position.insert(Inst);
3056     }
3057   };
3058
3059   /// \brief Set the operand of an instruction with a new value.
3060   class OperandSetter : public TypePromotionAction {
3061     /// Original operand of the instruction.
3062     Value *Origin;
3063     /// Index of the modified instruction.
3064     unsigned Idx;
3065
3066   public:
3067     /// \brief Set \p Idx operand of \p Inst with \p NewVal.
3068     OperandSetter(Instruction *Inst, unsigned Idx, Value *NewVal)
3069         : TypePromotionAction(Inst), Idx(Idx) {
3070       DEBUG(dbgs() << "Do: setOperand: " << Idx << "\n"
3071                    << "for:" << *Inst << "\n"
3072                    << "with:" << *NewVal << "\n");
3073       Origin = Inst->getOperand(Idx);
3074       Inst->setOperand(Idx, NewVal);
3075     }
3076
3077     /// \brief Restore the original value of the instruction.
3078     void undo() override {
3079       DEBUG(dbgs() << "Undo: setOperand:" << Idx << "\n"
3080                    << "for: " << *Inst << "\n"
3081                    << "with: " << *Origin << "\n");
3082       Inst->setOperand(Idx, Origin);
3083     }
3084   };
3085
3086   /// \brief Hide the operands of an instruction.
3087   /// Do as if this instruction was not using any of its operands.
3088   class OperandsHider : public TypePromotionAction {
3089     /// The list of original operands.
3090     SmallVector<Value *, 4> OriginalValues;
3091
3092   public:
3093     /// \brief Remove \p Inst from the uses of the operands of \p Inst.
3094     OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) {
3095       DEBUG(dbgs() << "Do: OperandsHider: " << *Inst << "\n");
3096       unsigned NumOpnds = Inst->getNumOperands();
3097       OriginalValues.reserve(NumOpnds);
3098       for (unsigned It = 0; It < NumOpnds; ++It) {
3099         // Save the current operand.
3100         Value *Val = Inst->getOperand(It);
3101         OriginalValues.push_back(Val);
3102         // Set a dummy one.
3103         // We could use OperandSetter here, but that would imply an overhead
3104         // that we are not willing to pay.
3105         Inst->setOperand(It, UndefValue::get(Val->getType()));
3106       }
3107     }
3108
3109     /// \brief Restore the original list of uses.
3110     void undo() override {
3111       DEBUG(dbgs() << "Undo: OperandsHider: " << *Inst << "\n");
3112       for (unsigned It = 0, EndIt = OriginalValues.size(); It != EndIt; ++It)
3113         Inst->setOperand(It, OriginalValues[It]);
3114     }
3115   };
3116
3117   /// \brief Build a truncate instruction.
3118   class TruncBuilder : public TypePromotionAction {
3119     Value *Val;
3120   public:
3121     /// \brief Build a truncate instruction of \p Opnd producing a \p Ty
3122     /// result.
3123     /// trunc Opnd to Ty.
3124     TruncBuilder(Instruction *Opnd, Type *Ty) : TypePromotionAction(Opnd) {
3125       IRBuilder<> Builder(Opnd);
3126       Val = Builder.CreateTrunc(Opnd, Ty, "promoted");
3127       DEBUG(dbgs() << "Do: TruncBuilder: " << *Val << "\n");
3128     }
3129
3130     /// \brief Get the built value.
3131     Value *getBuiltValue() { return Val; }
3132
3133     /// \brief Remove the built instruction.
3134     void undo() override {
3135       DEBUG(dbgs() << "Undo: TruncBuilder: " << *Val << "\n");
3136       if (Instruction *IVal = dyn_cast<Instruction>(Val))
3137         IVal->eraseFromParent();
3138     }
3139   };
3140
3141   /// \brief Build a sign extension instruction.
3142   class SExtBuilder : public TypePromotionAction {
3143     Value *Val;
3144   public:
3145     /// \brief Build a sign extension instruction of \p Opnd producing a \p Ty
3146     /// result.
3147     /// sext Opnd to Ty.
3148     SExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
3149         : TypePromotionAction(InsertPt) {
3150       IRBuilder<> Builder(InsertPt);
3151       Val = Builder.CreateSExt(Opnd, Ty, "promoted");
3152       DEBUG(dbgs() << "Do: SExtBuilder: " << *Val << "\n");
3153     }
3154
3155     /// \brief Get the built value.
3156     Value *getBuiltValue() { return Val; }
3157
3158     /// \brief Remove the built instruction.
3159     void undo() override {
3160       DEBUG(dbgs() << "Undo: SExtBuilder: " << *Val << "\n");
3161       if (Instruction *IVal = dyn_cast<Instruction>(Val))
3162         IVal->eraseFromParent();
3163     }
3164   };
3165
3166   /// \brief Build a zero extension instruction.
3167   class ZExtBuilder : public TypePromotionAction {
3168     Value *Val;
3169   public:
3170     /// \brief Build a zero extension instruction of \p Opnd producing a \p Ty
3171     /// result.
3172     /// zext Opnd to Ty.
3173     ZExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty)
3174         : TypePromotionAction(InsertPt) {
3175       IRBuilder<> Builder(InsertPt);
3176       Val = Builder.CreateZExt(Opnd, Ty, "promoted");
3177       DEBUG(dbgs() << "Do: ZExtBuilder: " << *Val << "\n");
3178     }
3179
3180     /// \brief Get the built value.
3181     Value *getBuiltValue() { return Val; }
3182
3183     /// \brief Remove the built instruction.
3184     void undo() override {
3185       DEBUG(dbgs() << "Undo: ZExtBuilder: " << *Val << "\n");
3186       if (Instruction *IVal = dyn_cast<Instruction>(Val))
3187         IVal->eraseFromParent();
3188     }
3189   };
3190
3191   /// \brief Mutate an instruction to another type.
3192   class TypeMutator : public TypePromotionAction {
3193     /// Record the original type.
3194     Type *OrigTy;
3195
3196   public:
3197     /// \brief Mutate the type of \p Inst into \p NewTy.
3198     TypeMutator(Instruction *Inst, Type *NewTy)
3199         : TypePromotionAction(Inst), OrigTy(Inst->getType()) {
3200       DEBUG(dbgs() << "Do: MutateType: " << *Inst << " with " << *NewTy
3201                    << "\n");
3202       Inst->mutateType(NewTy);
3203     }
3204
3205     /// \brief Mutate the instruction back to its original type.
3206     void undo() override {
3207       DEBUG(dbgs() << "Undo: MutateType: " << *Inst << " with " << *OrigTy
3208                    << "\n");
3209       Inst->mutateType(OrigTy);
3210     }
3211   };
3212
3213   /// \brief Replace the uses of an instruction by another instruction.
3214   class UsesReplacer : public TypePromotionAction {
3215     /// Helper structure to keep track of the replaced uses.
3216     struct InstructionAndIdx {
3217       /// The instruction using the instruction.
3218       Instruction *Inst;
3219       /// The index where this instruction is used for Inst.
3220       unsigned Idx;
3221       InstructionAndIdx(Instruction *Inst, unsigned Idx)
3222           : Inst(Inst), Idx(Idx) {}
3223     };
3224
3225     /// Keep track of the original uses (pair Instruction, Index).
3226     SmallVector<InstructionAndIdx, 4> OriginalUses;
3227     typedef SmallVectorImpl<InstructionAndIdx>::iterator use_iterator;
3228
3229   public:
3230     /// \brief Replace all the use of \p Inst by \p New.
3231     UsesReplacer(Instruction *Inst, Value *New) : TypePromotionAction(Inst) {
3232       DEBUG(dbgs() << "Do: UsersReplacer: " << *Inst << " with " << *New
3233                    << "\n");
3234       // Record the original uses.
3235       for (Use &U : Inst->uses()) {
3236         Instruction *UserI = cast<Instruction>(U.getUser());
3237         OriginalUses.push_back(InstructionAndIdx(UserI, U.getOperandNo()));
3238       }
3239       // Now, we can replace the uses.
3240       Inst->replaceAllUsesWith(New);
3241     }
3242
3243     /// \brief Reassign the original uses of Inst to Inst.
3244     void undo() override {
3245       DEBUG(dbgs() << "Undo: UsersReplacer: " << *Inst << "\n");
3246       for (use_iterator UseIt = OriginalUses.begin(),
3247                         EndIt = OriginalUses.end();
3248            UseIt != EndIt; ++UseIt) {
3249         UseIt->Inst->setOperand(UseIt->Idx, Inst);
3250       }
3251     }
3252   };
3253
3254   /// \brief Remove an instruction from the IR.
3255   class InstructionRemover : public TypePromotionAction {
3256     /// Original position of the instruction.
3257     InsertionHandler Inserter;
3258     /// Helper structure to hide all the link to the instruction. In other
3259     /// words, this helps to do as if the instruction was removed.
3260     OperandsHider Hider;
3261     /// Keep track of the uses replaced, if any.
3262     UsesReplacer *Replacer;
3263
3264   public:
3265     /// \brief Remove all reference of \p Inst and optinally replace all its
3266     /// uses with New.
3267     /// \pre If !Inst->use_empty(), then New != nullptr
3268     InstructionRemover(Instruction *Inst, Value *New = nullptr)
3269         : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3270           Replacer(nullptr) {
3271       if (New)
3272         Replacer = new UsesReplacer(Inst, New);
3273       DEBUG(dbgs() << "Do: InstructionRemover: " << *Inst << "\n");
3274       Inst->removeFromParent();
3275     }
3276
3277     ~InstructionRemover() override { delete Replacer; }
3278
3279     /// \brief Really remove the instruction.
3280     void commit() override { delete Inst; }
3281
3282     /// \brief Resurrect the instruction and reassign it to the proper uses if
3283     /// new value was provided when build this action.
3284     void undo() override {
3285       DEBUG(dbgs() << "Undo: InstructionRemover: " << *Inst << "\n");
3286       Inserter.insert(Inst);
3287       if (Replacer)
3288         Replacer->undo();
3289       Hider.undo();
3290     }
3291   };
3292
3293 public:
3294   /// Restoration point.
3295   /// The restoration point is a pointer to an action instead of an iterator
3296   /// because the iterator may be invalidated but not the pointer.
3297   typedef const TypePromotionAction *ConstRestorationPt;
3298   /// Advocate every changes made in that transaction.
3299   void commit();
3300   /// Undo all the changes made after the given point.
3301   void rollback(ConstRestorationPt Point);
3302   /// Get the current restoration point.
3303   ConstRestorationPt getRestorationPoint() const;
3304
3305   /// \name API for IR modification with state keeping to support rollback.
3306   /// @{
3307   /// Same as Instruction::setOperand.
3308   void setOperand(Instruction *Inst, unsigned Idx, Value *NewVal);
3309   /// Same as Instruction::eraseFromParent.
3310   void eraseInstruction(Instruction *Inst, Value *NewVal = nullptr);
3311   /// Same as Value::replaceAllUsesWith.
3312   void replaceAllUsesWith(Instruction *Inst, Value *New);
3313   /// Same as Value::mutateType.
3314   void mutateType(Instruction *Inst, Type *NewTy);
3315   /// Same as IRBuilder::createTrunc.
3316   Value *createTrunc(Instruction *Opnd, Type *Ty);
3317   /// Same as IRBuilder::createSExt.
3318   Value *createSExt(Instruction *Inst, Value *Opnd, Type *Ty);
3319   /// Same as IRBuilder::createZExt.
3320   Value *createZExt(Instruction *Inst, Value *Opnd, Type *Ty);
3321   /// Same as Instruction::moveBefore.
3322   void moveBefore(Instruction *Inst, Instruction *Before);
3323   /// @}
3324
3325 private:
3326   /// The ordered list of actions made so far.
3327   SmallVector<std::unique_ptr<TypePromotionAction>, 16> Actions;
3328   typedef SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator CommitPt;
3329 };
3330
3331 void TypePromotionTransaction::setOperand(Instruction *Inst, unsigned Idx,
3332                                           Value *NewVal) {
3333   Actions.push_back(
3334       make_unique<TypePromotionTransaction::OperandSetter>(Inst, Idx, NewVal));
3335 }
3336
3337 void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
3338                                                 Value *NewVal) {
3339   Actions.push_back(
3340       make_unique<TypePromotionTransaction::InstructionRemover>(Inst, NewVal));
3341 }
3342
3343 void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
3344                                                   Value *New) {
3345   Actions.push_back(make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3346 }
3347
3348 void TypePromotionTransaction::mutateType(Instruction *Inst, Type *NewTy) {
3349   Actions.push_back(make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3350 }
3351
3352 Value *TypePromotionTransaction::createTrunc(Instruction *Opnd,
3353                                              Type *Ty) {
3354   std::unique_ptr<TruncBuilder> Ptr(new TruncBuilder(Opnd, Ty));
3355   Value *Val = Ptr->getBuiltValue();
3356   Actions.push_back(std::move(Ptr));
3357   return Val;
3358 }
3359
3360 Value *TypePromotionTransaction::createSExt(Instruction *Inst,
3361                                             Value *Opnd, Type *Ty) {
3362   std::unique_ptr<SExtBuilder> Ptr(new SExtBuilder(Inst, Opnd, Ty));
3363   Value *Val = Ptr->getBuiltValue();
3364   Actions.push_back(std::move(Ptr));
3365   return Val;
3366 }
3367
3368 Value *TypePromotionTransaction::createZExt(Instruction *Inst,
3369                                             Value *Opnd, Type *Ty) {
3370   std::unique_ptr<ZExtBuilder> Ptr(new ZExtBuilder(Inst, Opnd, Ty));
3371   Value *Val = Ptr->getBuiltValue();
3372   Actions.push_back(std::move(Ptr));
3373   return Val;
3374 }
3375
3376 void TypePromotionTransaction::moveBefore(Instruction *Inst,
3377                                           Instruction *Before) {
3378   Actions.push_back(
3379       make_unique<TypePromotionTransaction::InstructionMoveBefore>(Inst, Before));
3380 }
3381
3382 TypePromotionTransaction::ConstRestorationPt
3383 TypePromotionTransaction::getRestorationPoint() const {
3384   return !Actions.empty() ? Actions.back().get() : nullptr;
3385 }
3386
3387 void TypePromotionTransaction::commit() {
3388   for (CommitPt It = Actions.begin(), EndIt = Actions.end(); It != EndIt;
3389        ++It)
3390     (*It)->commit();
3391   Actions.clear();
3392 }
3393
3394 void TypePromotionTransaction::rollback(
3395     TypePromotionTransaction::ConstRestorationPt Point) {
3396   while (!Actions.empty() && Point != Actions.back().get()) {
3397     std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3398     Curr->undo();
3399   }
3400 }
3401
3402 /// \brief A helper class for matching addressing modes.
3403 ///
3404 /// This encapsulates the logic for matching the target-legal addressing modes.
3405 class AddressingModeMatcher {
3406   SmallVectorImpl<Instruction*> &AddrModeInsts;
3407   const TargetMachine &TM;
3408   const TargetLowering &TLI;
3409   const DataLayout &DL;
3410
3411   /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and
3412   /// the memory instruction that we're computing this address for.
3413   Type *AccessTy;
3414   unsigned AddrSpace;
3415   Instruction *MemoryInst;
3416
3417   /// This is the addressing mode that we're building up. This is
3418   /// part of the return value of this addressing mode matching stuff.
3419   ExtAddrMode &AddrMode;
3420
3421   /// The instructions inserted by other CodeGenPrepare optimizations.
3422   const SetOfInstrs &InsertedInsts;
3423   /// A map from the instructions to their type before promotion.
3424   InstrToOrigTy &PromotedInsts;
3425   /// The ongoing transaction where every action should be registered.
3426   TypePromotionTransaction &TPT;
3427
3428   /// This is set to true when we should not do profitability checks.
3429   /// When true, IsProfitableToFoldIntoAddressingMode always returns true.
3430   bool IgnoreProfitability;
3431
3432   AddressingModeMatcher(SmallVectorImpl<Instruction *> &AMI,
3433                         const TargetMachine &TM, Type *AT, unsigned AS,
3434                         Instruction *MI, ExtAddrMode &AM,
3435                         const SetOfInstrs &InsertedInsts,
3436                         InstrToOrigTy &PromotedInsts,
3437                         TypePromotionTransaction &TPT)
3438       : AddrModeInsts(AMI), TM(TM),
3439         TLI(*TM.getSubtargetImpl(*MI->getParent()->getParent())
3440                  ->getTargetLowering()),
3441         DL(MI->getModule()->getDataLayout()), AccessTy(AT), AddrSpace(AS),
3442         MemoryInst(MI), AddrMode(AM), InsertedInsts(InsertedInsts),
3443         PromotedInsts(PromotedInsts), TPT(TPT) {
3444     IgnoreProfitability = false;
3445   }
3446 public:
3447
3448   /// Find the maximal addressing mode that a load/store of V can fold,
3449   /// give an access type of AccessTy.  This returns a list of involved
3450   /// instructions in AddrModeInsts.
3451   /// \p InsertedInsts The instructions inserted by other CodeGenPrepare
3452   /// optimizations.
3453   /// \p PromotedInsts maps the instructions to their type before promotion.
3454   /// \p The ongoing transaction where every action should be registered.
3455   static ExtAddrMode Match(Value *V, Type *AccessTy, unsigned AS,
3456                            Instruction *MemoryInst,
3457                            SmallVectorImpl<Instruction*> &AddrModeInsts,
3458                            const TargetMachine &TM,
3459                            const SetOfInstrs &InsertedInsts,
3460                            InstrToOrigTy &PromotedInsts,
3461                            TypePromotionTransaction &TPT) {
3462     ExtAddrMode Result;
3463
3464     bool Success = AddressingModeMatcher(AddrModeInsts, TM, AccessTy, AS,
3465                                          MemoryInst, Result, InsertedInsts,
3466                                          PromotedInsts, TPT).matchAddr(V, 0);
3467     (void)Success; assert(Success && "Couldn't select *anything*?");
3468     return Result;
3469   }
3470 private:
3471   bool matchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth);
3472   bool matchAddr(Value *V, unsigned Depth);
3473   bool matchOperationAddr(User *Operation, unsigned Opcode, unsigned Depth,
3474                           bool *MovedAway = nullptr);
3475   bool isProfitableToFoldIntoAddressingMode(Instruction *I,
3476                                             ExtAddrMode &AMBefore,
3477                                             ExtAddrMode &AMAfter);
3478   bool valueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
3479   bool isPromotionProfitable(unsigned NewCost, unsigned OldCost,
3480                              Value *PromotedOperand) const;
3481 };
3482
3483 /// Try adding ScaleReg*Scale to the current addressing mode.
3484 /// Return true and update AddrMode if this addr mode is legal for the target,
3485 /// false if not.
3486 bool AddressingModeMatcher::matchScaledValue(Value *ScaleReg, int64_t Scale,
3487                                              unsigned Depth) {
3488   // If Scale is 1, then this is the same as adding ScaleReg to the addressing