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