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