lib/CodeGen/AtomicExpandPass.cpp

   1 //===-- AtomicExpandPass.cpp - Expand atomic instructions -------===//
   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 file contains a pass (at IR level) to replace atomic instructions with
  11 // target specific instruction which implement the same semantics in a way
  12 // which better fits the target backend.  This can include the use of either
  13 // (intrinsic-based) load-linked/store-conditional loops, AtomicCmpXchg, or
  14 // type coercions.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/ADT/SetOperations.h"
  19 #include "llvm/ADT/SetVector.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/Analysis/MemoryLocation.h"
  23 #include "llvm/CodeGen/AtomicExpandUtils.h"
  24 #include "llvm/CodeGen/Passes.h"
  25 #include "llvm/IR/Function.h"
  26 #include "llvm/IR/IRBuilder.h"
  27 #include "llvm/IR/InstIterator.h"
  28 #include "llvm/IR/Instructions.h"
  29 #include "llvm/IR/Intrinsics.h"
  30 #include "llvm/IR/Module.h"
  31 #include "llvm/IR/NoFolder.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/Target/TargetLowering.h"
  35 #include "llvm/Target/TargetMachine.h"
  36 #include "llvm/Target/TargetSubtargetInfo.h"
  37
  38 using namespace llvm;
  39
  40 #define DEBUG_TYPE "atomic-expand"
  41
  42 namespace {
  43   class AtomicExpand: public FunctionPass {
  44     const TargetMachine *TM;
  45     const TargetLowering *TLI;
  46   public:
  47     static char ID; // Pass identification, replacement for typeid
  48     explicit AtomicExpand(const TargetMachine *TM = nullptr)
  49       : FunctionPass(ID), TM(TM), TLI(nullptr) {
  50       initializeAtomicExpandPass(*PassRegistry::getPassRegistry());
  51     }
  52
  53     bool runOnFunction(Function &F) override;
  54
  55   private:
  56     bool bracketInstWithFences(Instruction *I, AtomicOrdering Order,
  57                                bool IsStore, bool IsLoad);
  58     IntegerType *getCorrespondingIntegerType(Type *T, const DataLayout &DL);
  59     LoadInst *convertAtomicLoadToIntegerType(LoadInst *LI);
  60     bool tryExpandAtomicLoad(LoadInst *LI);
  61     bool expandAtomicLoadToLL(LoadInst *LI);
  62     bool expandAtomicLoadToCmpXchg(LoadInst *LI);
  63     StoreInst *convertAtomicStoreToIntegerType(StoreInst *SI);
  64     bool expandAtomicStore(StoreInst *SI);
  65     bool tryExpandAtomicRMW(AtomicRMWInst *AI);
  66     bool expandAtomicOpToLLSC(
  67         Instruction *I, Value *Addr, AtomicOrdering MemOpOrder,
  68         std::function<Value *(IRBuilder<> &, Value *)> PerformOp);
  69     bool expandAtomicCmpXchg(AtomicCmpXchgInst *CI);
  70     bool isIdempotentRMW(AtomicRMWInst *AI);
  71     bool simplifyIdempotentRMW(AtomicRMWInst *AI);
  72   };
  73 }
  74
  75 char AtomicExpand::ID = 0;
  76 char &llvm::AtomicExpandID = AtomicExpand::ID;
  77 INITIALIZE_TM_PASS(AtomicExpand, "atomic-expand",
  78     "Expand Atomic calls in terms of either load-linked & store-conditional or cmpxchg",
  79     false, false)
  80
  81 FunctionPass *llvm::createAtomicExpandPass(const TargetMachine *TM) {
  82   return new AtomicExpand(TM);
  83 }
  84
  85
  86 namespace {
  87
  88 bool StoreAddressDependOnValue(StoreInst* SI, Value* DepVal);
  89 Value* GetUntaintedAddress(Value* CurrentAddress);
  90
  91 // The depth we trace down a variable to look for its dependence set.
  92 const unsigned kDependenceDepth = 4;
  93
  94 // Recursively looks for variables that 'Val' depends on at the given depth
  95 // 'Depth', and adds them in 'DepSet'. If 'InsertOnlyLeafNodes' is true, only
  96 // inserts the leaf node values; otherwise, all visited nodes are included in
  97 // 'DepSet'. Note that constants will be ignored.
  98 template <typename SetType>
  99 void recursivelyFindDependence(SetType* DepSet, Value* Val,
 100                                bool InsertOnlyLeafNodes = false,
 101                                unsigned Depth = kDependenceDepth) {
 102   if (Val == nullptr) {
 103     return;
 104   }
 105   if (!InsertOnlyLeafNodes && !isa<Constant>(Val)) {
 106     DepSet->insert(Val);
 107   }
 108   if (Depth == 0) {
 109     // Cannot go deeper. Insert the leaf nodes.
 110     if (InsertOnlyLeafNodes && !isa<Constant>(Val)) {
 111       DepSet->insert(Val);
 112     }
 113     return;
 114   }
 115
 116   // Go one step further to explore the dependence of the operands.
 117   Instruction* I = nullptr;
 118   if ((I = dyn_cast<Instruction>(Val))) {
 119     if (isa<LoadInst>(I)) {
 120       // A load is considerd the leaf load of the dependence tree. Done.
 121       DepSet->insert(Val);
 122       return;
 123     } else if (I->isBinaryOp()) {
 124       BinaryOperator* I = dyn_cast<BinaryOperator>(Val);
 125       Value *Op0 = I->getOperand(0), *Op1 = I->getOperand(1);
 126       recursivelyFindDependence(DepSet, Op0, Depth - 1);
 127       recursivelyFindDependence(DepSet, Op1, Depth - 1);
 128     } else if (I->isCast()) {
 129       Value* Op0 = I->getOperand(0);
 130       recursivelyFindDependence(DepSet, Op0, Depth - 1);
 131     } else if (I->getOpcode() == Instruction::Select) {
 132       Value* Op0 = I->getOperand(0);
 133       Value* Op1 = I->getOperand(1);
 134       Value* Op2 = I->getOperand(2);
 135       recursivelyFindDependence(DepSet, Op0, Depth - 1);
 136       recursivelyFindDependence(DepSet, Op1, Depth - 1);
 137       recursivelyFindDependence(DepSet, Op2, Depth - 1);
 138     } else if (I->getOpcode() == Instruction::GetElementPtr) {
 139       for (unsigned i = 0; i < I->getNumOperands(); i++) {
 140         recursivelyFindDependence(DepSet, I->getOperand(i), Depth - 1);
 141       }
 142     } else if (I->getOpcode() == Instruction::Store) {
 143       auto* SI = dyn_cast<StoreInst>(Val);
 144       recursivelyFindDependence(DepSet, SI->getPointerOperand(), Depth - 1);
 145       recursivelyFindDependence(DepSet, SI->getValueOperand(), Depth - 1);
 146     } else {
 147       Value* Op0 = nullptr;
 148       Value* Op1 = nullptr;
 149       switch (I->getOpcode()) {
 150         case Instruction::ICmp:
 151         case Instruction::FCmp: {
 152           Op0 = I->getOperand(0);
 153           Op1 = I->getOperand(1);
 154           recursivelyFindDependence(DepSet, Op0, Depth - 1);
 155           recursivelyFindDependence(DepSet, Op1, Depth - 1);
 156           break;
 157         }
 158         default: {
 159           // Be conservative. Add it and be done with it.
 160           DepSet->insert(Val);
 161           return;
 162         }
 163       }
 164     }
 165   } else if (isa<Constant>(Val)) {
 166     // Not interested in constant values. Done.
 167     return;
 168   } else {
 169     // Be conservative. Add it and be done with it.
 170     DepSet->insert(Val);
 171     return;
 172   }
 173 }
 174
 175 // Helper function to create a Cast instruction.
 176 Value* createCast(IRBuilder<true, NoFolder>& Builder, Value* DepVal,
 177                   Type* TargetIntegerType) {
 178   Instruction::CastOps CastOp = Instruction::BitCast;
 179   switch (DepVal->getType()->getTypeID()) {
 180     case Type::IntegerTyID: {
 181       CastOp = Instruction::SExt;
 182       break;
 183     }
 184     case Type::FloatTyID:
 185     case Type::DoubleTyID: {
 186       CastOp = Instruction::FPToSI;
 187       break;
 188     }
 189     case Type::PointerTyID: {
 190       CastOp = Instruction::PtrToInt;
 191       break;
 192     }
 193     default: { break; }
 194   }
 195
 196   return Builder.CreateCast(CastOp, DepVal, TargetIntegerType);
 197 }
 198
 199 // Given a value, if it's a tainted address, this function returns the
 200 // instruction that ORs the "dependence value" with the "original address".
 201 // Otherwise, returns nullptr.  This instruction is the first OR instruction
 202 // where one of its operand is an AND instruction with an operand being 0.
 203 //
 204 // E.g., it returns '%4 = or i32 %3, %2' given 'CurrentAddress' is '%5'.
 205 // %0 = load i32, i32* @y, align 4, !tbaa !1
 206 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
 207 // %1 = sext i1 %cmp to i32
 208 // %2 = ptrtoint i32* @x to i32
 209 // %3 = and i32 %1, 0
 210 // %4 = or i32 %3, %2
 211 // %5 = inttoptr i32 %4 to i32*
 212 // store i32 1, i32* %5, align 4
 213 Instruction* getOrAddress(Value* CurrentAddress) {
 214   // Is it a cast from integer to pointer type.
 215   Instruction* OrAddress = nullptr;
 216   Instruction* AndDep = nullptr;
 217   Instruction* CastToInt = nullptr;
 218   Value* ActualAddress = nullptr;
 219   Constant* ZeroConst = nullptr;
 220
 221   const Instruction* CastToPtr = dyn_cast<Instruction>(CurrentAddress);
 222   if (CastToPtr && CastToPtr->getOpcode() == Instruction::IntToPtr) {
 223     // Is it an OR instruction: %1 = or %and, %actualAddress.
 224     if ((OrAddress = dyn_cast<Instruction>(CastToPtr->getOperand(0))) &&
 225         OrAddress->getOpcode() == Instruction::Or) {
 226       // The first operand should be and AND instruction.
 227       AndDep = dyn_cast<Instruction>(OrAddress->getOperand(0));
 228       if (AndDep && AndDep->getOpcode() == Instruction::And) {
 229         // Also make sure its first operand of the "AND" is 0, or the "AND" is
 230         // marked explicitly by "NoInstCombine".
 231         if ((ZeroConst = dyn_cast<Constant>(AndDep->getOperand(1))) &&
 232             ZeroConst->isNullValue()) {
 233           return OrAddress;
 234         }
 235       }
 236     }
 237   }
 238   // Looks like it's not been tainted.
 239   return nullptr;
 240 }
 241
 242 // Given a value, if it's a tainted address, this function returns the
 243 // instruction that taints the "dependence value". Otherwise, returns nullptr.
 244 // This instruction is the last AND instruction where one of its operand is 0.
 245 // E.g., it returns '%3' given 'CurrentAddress' is '%5'.
 246 // %0 = load i32, i32* @y, align 4, !tbaa !1
 247 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
 248 // %1 = sext i1 %cmp to i32
 249 // %2 = ptrtoint i32* @x to i32
 250 // %3 = and i32 %1, 0
 251 // %4 = or i32 %3, %2
 252 // %5 = inttoptr i32 %4 to i32*
 253 // store i32 1, i32* %5, align 4
 254 Instruction* getAndDependence(Value* CurrentAddress) {
 255   // If 'CurrentAddress' is tainted, get the OR instruction.
 256   auto* OrAddress = getOrAddress(CurrentAddress);
 257   if (OrAddress == nullptr) {
 258     return nullptr;
 259   }
 260
 261   // No need to check the operands.
 262   auto* AndDepInst = dyn_cast<Instruction>(OrAddress->getOperand(0));
 263   assert(AndDepInst);
 264   return AndDepInst;
 265 }
 266
 267 // Given a value, if it's a tainted address, this function returns
 268 // the "dependence value", which is the first operand in the AND instruction.
 269 // E.g., it returns '%1' given 'CurrentAddress' is '%5'.
 270 // %0 = load i32, i32* @y, align 4, !tbaa !1
 271 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
 272 // %1 = sext i1 %cmp to i32
 273 // %2 = ptrtoint i32* @x to i32
 274 // %3 = and i32 %1, 0
 275 // %4 = or i32 %3, %2
 276 // %5 = inttoptr i32 %4 to i32*
 277 // store i32 1, i32* %5, align 4
 278 Value* getDependence(Value* CurrentAddress) {
 279   auto* AndInst = getAndDependence(CurrentAddress);
 280   if (AndInst == nullptr) {
 281     return nullptr;
 282   }
 283   return AndInst->getOperand(0);
 284 }
 285
 286 // Given an address that has been tainted, returns the only condition it depends
 287 // on, if any; otherwise, returns nullptr.
 288 Value* getConditionDependence(Value* Address) {
 289   auto* Dep = getDependence(Address);
 290   if (Dep == nullptr) {
 291     // 'Address' has not been dependence-tainted.
 292     return nullptr;
 293   }
 294
 295   Value* Operand = Dep;
 296   while (true) {
 297     auto* Inst = dyn_cast<Instruction>(Operand);
 298     if (Inst == nullptr) {
 299       // Non-instruction type does not have condition dependence.
 300       return nullptr;
 301     }
 302     if (Inst->getOpcode() == Instruction::ICmp) {
 303       return Inst;
 304     } else {
 305       if (Inst->getNumOperands() != 1) {
 306         return nullptr;
 307       } else {
 308         Operand = Inst->getOperand(0);
 309       }
 310     }
 311   }
 312 }
 313
 314 // Conservatively decides whether the dependence set of 'Val1' includes the
 315 // dependence set of 'Val2'. If 'ExpandSecondValue' is false, we do not expand
 316 // 'Val2' and use that single value as its dependence set.
 317 // If it returns true, it means the dependence set of 'Val1' includes that of
 318 // 'Val2'; otherwise, it only means we cannot conclusively decide it.
 319 bool dependenceSetInclusion(Value* Val1, Value* Val2,
 320                             int Val1ExpandLevel = 2 * kDependenceDepth,
 321                             int Val2ExpandLevel = kDependenceDepth) {
 322   typedef SmallSet<Value*, 8> IncludingSet;
 323   typedef SmallSet<Value*, 4> IncludedSet;
 324
 325   IncludingSet DepSet1;
 326   IncludedSet DepSet2;
 327   // Look for more depths for the including set.
 328   recursivelyFindDependence(&DepSet1, Val1, false /*Insert all visited nodes*/,
 329                             Val1ExpandLevel);
 330   recursivelyFindDependence(&DepSet2, Val2, true /*Only insert leaf nodes*/,
 331                             Val2ExpandLevel);
 332
 333   auto set_inclusion = [](IncludingSet FullSet, IncludedSet Subset) {
 334     for (auto* Dep : Subset) {
 335       if (0 == FullSet.count(Dep)) {
 336         return false;
 337       }
 338     }
 339     return true;
 340   };
 341   bool inclusion = set_inclusion(DepSet1, DepSet2);
 342   DEBUG(dbgs() << "[dependenceSetInclusion]: " << inclusion << "\n");
 343   DEBUG(dbgs() << "Including set for: " << *Val1 << "\n");
 344   DEBUG(for (const auto* Dep : DepSet1) { dbgs() << "\t\t" << *Dep << "\n"; });
 345   DEBUG(dbgs() << "Included set for: " << *Val2 << "\n");
 346   DEBUG(for (const auto* Dep : DepSet2) { dbgs() << "\t\t" << *Dep << "\n"; });
 347
 348   return inclusion;
 349 }
 350
 351 // Recursively iterates through the operands spawned from 'DepVal'. If there
 352 // exists a single value that 'DepVal' only depends on, we call that value the
 353 // root dependence of 'DepVal' and return it. Otherwise, return 'DepVal'.
 354 Value* getRootDependence(Value* DepVal) {
 355   SmallSet<Value*, 8> DepSet;
 356   for (unsigned depth = kDependenceDepth; depth > 0; --depth) {
 357     recursivelyFindDependence(&DepSet, DepVal, true /*Only insert leaf nodes*/,
 358                               depth);
 359     if (DepSet.size() == 1) {
 360       return *DepSet.begin();
 361     }
 362     DepSet.clear();
 363   }
 364   return DepVal;
 365 }
 366
 367 // This function actually taints 'DepVal' to the address to 'SI'. If the
 368 // address
 369 // of 'SI' already depends on whatever 'DepVal' depends on, this function
 370 // doesn't do anything and returns false. Otherwise, returns true.
 371 //
 372 // This effect forces the store and any stores that comes later to depend on
 373 // 'DepVal'. For example, we have a condition "cond", and a store instruction
 374 // "s: STORE addr, val". If we want "s" (and any later store) to depend on
 375 // "cond", we do the following:
 376 // %conv = sext i1 %cond to i32
 377 // %addrVal = ptrtoint i32* %addr to i32
 378 // %andCond = and i32 conv, 0;
 379 // %orAddr = or i32 %andCond, %addrVal;
 380 // %NewAddr = inttoptr i32 %orAddr to i32*;
 381 //
 382 // This is a more concrete example:
 383 // ------
 384 // %0 = load i32, i32* @y, align 4, !tbaa !1
 385 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
 386 // %1 = sext i1 %cmp to i32
 387 // %2 = ptrtoint i32* @x to i32
 388 // %3 = and i32 %1, 0
 389 // %4 = or i32 %3, %2
 390 // %5 = inttoptr i32 %4 to i32*
 391 // store i32 1, i32* %5, align 4
 392 bool taintStoreAddress(StoreInst* SI, Value* DepVal,
 393                        const char* calling_func = __builtin_FUNCTION()) {
 394   DEBUG(dbgs() << "Called from " << calling_func << '\n');
 395   IRBuilder<true, NoFolder> Builder(SI);
 396   BasicBlock* BB = SI->getParent();
 397   Value* Address = SI->getPointerOperand();
 398   Type* TargetIntegerType =
 399       IntegerType::get(Address->getContext(),
 400                        BB->getModule()->getDataLayout().getPointerSizeInBits());
 401
 402   // Does SI's address already depends on whatever 'DepVal' depends on?
 403   if (StoreAddressDependOnValue(SI, DepVal)) {
 404     return false;
 405   }
 406
 407   // Figure out if there's a root variable 'DepVal' depends on. For example, we
 408   // can extract "getelementptr inbounds %struct, %struct* %0, i64 0, i32 123"
 409   // to be "%struct* %0" since all other operands are constant.
 410   DepVal = getRootDependence(DepVal);
 411
 412   // Is this already a dependence-tainted store?
 413   Value* OldDep = getDependence(Address);
 414   if (OldDep) {
 415     // The address of 'SI' has already been tainted.  Just need to absorb the
 416     // DepVal to the existing dependence in the address of SI.
 417     Instruction* AndDep = getAndDependence(Address);
 418     IRBuilder<true, NoFolder> Builder(AndDep);
 419     Value* NewDep = nullptr;
 420     if (DepVal->getType() == AndDep->getType()) {
 421       NewDep = Builder.CreateAnd(OldDep, DepVal);
 422     } else {
 423       NewDep = Builder.CreateAnd(
 424           OldDep, createCast(Builder, DepVal, TargetIntegerType));
 425     }
 426
 427     auto* NewDepInst = dyn_cast<Instruction>(NewDep);
 428
 429     // Use the new AND instruction as the dependence
 430     AndDep->setOperand(0, NewDep);
 431     return true;
 432   }
 433
 434   // SI's address has not been tainted. Now taint it with 'DepVal'.
 435   Value* CastDepToInt = createCast(Builder, DepVal, TargetIntegerType);
 436   Value* PtrToIntCast = Builder.CreatePtrToInt(Address, TargetIntegerType);
 437   Value* AndDepVal =
 438       Builder.CreateAnd(CastDepToInt, ConstantInt::get(TargetIntegerType, 0));
 439   auto AndInst = dyn_cast<Instruction>(AndDepVal);
 440   // XXX-comment: The original IR InstCombiner would change our and instruction
 441   // to a select and then the back end optimize the condition out.  We attach a
 442   // flag to instructions and set it here to inform the InstCombiner to not to
 443   // touch this and instruction at all.
 444   Value* OrAddr = Builder.CreateOr(AndDepVal, PtrToIntCast);
 445   Value* NewAddr = Builder.CreateIntToPtr(OrAddr, Address->getType());
 446
 447   DEBUG(dbgs() << "[taintStoreAddress]\n"
 448                << "Original store: " << *SI << '\n');
 449   SI->setOperand(1, NewAddr);
 450
 451   // Debug output.
 452   DEBUG(dbgs() << "\tTargetIntegerType: " << *TargetIntegerType << '\n'
 453                << "\tCast dependence value to integer: " << *CastDepToInt
 454                << '\n'
 455                << "\tCast address to integer: " << *PtrToIntCast << '\n'
 456                << "\tAnd dependence value: " << *AndDepVal << '\n'
 457                << "\tOr address: " << *OrAddr << '\n'
 458                << "\tCast or instruction to address: " << *NewAddr << "\n\n");
 459
 460   return true;
 461 }
 462
 463 // Looks for the previous store in the if block --- 'BrBB', which makes the
 464 // speculative store 'StoreToHoist' safe.
 465 Value* getSpeculativeStoreInPrevBB(StoreInst* StoreToHoist, BasicBlock* BrBB) {
 466   assert(StoreToHoist && "StoreToHoist must be a real store");
 467
 468   Value* StorePtr = StoreToHoist->getPointerOperand();
 469
 470   // Look for a store to the same pointer in BrBB.
 471   for (BasicBlock::reverse_iterator RI = BrBB->rbegin(), RE = BrBB->rend();
 472        RI != RE; ++RI) {
 473     Instruction* CurI = &*RI;
 474
 475     StoreInst* SI = dyn_cast<StoreInst>(CurI);
 476     // Found the previous store make sure it stores to the same location.
 477     // XXX-update: If the previous store's original untainted address are the
 478     // same as 'StorePtr', we are also good to hoist the store.
 479     if (SI && (SI->getPointerOperand() == StorePtr ||
 480                GetUntaintedAddress(SI->getPointerOperand()) == StorePtr)) {
 481       // Found the previous store, return its value operand.
 482       return SI;
 483     }
 484   }
 485
 486   assert(false &&
 487          "We should not reach here since this store is safe to speculate");
 488 }
 489
 490 // XXX-comment: Returns true if it changes the code, false otherwise (the branch
 491 // condition already depends on 'DepVal'.
 492 bool taintConditionalBranch(BranchInst* BI, Value* DepVal) {
 493   assert(BI->isConditional());
 494   auto* Cond = BI->getOperand(0);
 495   if (dependenceSetInclusion(Cond, DepVal)) {
 496     // The dependence/ordering is self-evident.
 497     return false;
 498   }
 499
 500   IRBuilder<true, NoFolder> Builder(BI);
 501   auto* AndDep =
 502       Builder.CreateAnd(DepVal, ConstantInt::get(DepVal->getType(), 0));
 503   auto* TruncAndDep =
 504       Builder.CreateTrunc(AndDep, IntegerType::get(DepVal->getContext(), 1));
 505   auto* OrCond = Builder.CreateOr(TruncAndDep, Cond);
 506   BI->setOperand(0, OrCond);
 507
 508   // Debug output.
 509   DEBUG(dbgs() << "\tTainted branch condition:\n" << *BI->getParent());
 510
 511   return true;
 512 }
 513
 514 // XXX-update: For a relaxed load 'LI', find the first immediate atomic store or
 515 // the first conditional branch. Returns nullptr if there's no such immediately
 516 // following store/branch instructions, which we can only enforce the load with
 517 // 'acquire'.
 518 Instruction* findFirstStoreCondBranchInst(LoadInst* LI) {
 519   // In some situations, relaxed loads can be left as is:
 520   // 1. The relaxed load is used to calculate the address of the immediate
 521   // following store;
 522   // 2. The relaxed load is used as a condition in the immediate following
 523   // condition, and there are no stores in between. This is actually quite
 524   // common. E.g.,
 525   // int r1 = x.load(relaxed);
 526   // if (r1 != 0) {
 527   //   y.store(1, relaxed);
 528   // }
 529   // However, in this function, we don't deal with them directly. Instead, we
 530   // just find the immediate following store/condition branch and return it.
 531
 532   auto* BB = LI->getParent();
 533   auto BE = BB->end();
 534   auto BBI = BasicBlock::iterator(LI);
 535   BBI++;
 536   while (true) {
 537     for (; BBI != BE; BBI++) {
 538       auto* Inst = dyn_cast<Instruction>(&*BBI);
 539       if (Inst == nullptr) {
 540         continue;
 541       }
 542       if (Inst->getOpcode() == Instruction::Store) {
 543         return Inst;
 544       } else if (Inst->getOpcode() == Instruction::Br) {
 545         auto* BrInst = dyn_cast<BranchInst>(Inst);
 546         if (BrInst->isConditional()) {
 547           return Inst;
 548         } else {
 549           // Reinitialize iterators with the destination of the unconditional
 550           // branch.
 551           BB = BrInst->getSuccessor(0);
 552           BBI = BB->begin();
 553           BE = BB->end();
 554           break;
 555         }
 556       }
 557     }
 558     if (BBI == BE) {
 559       return nullptr;
 560     }
 561   }
 562 }
 563
 564 // XXX-comment: Returns whether the code has been changed.
 565 bool taintMonotonicLoads(const SmallVector<LoadInst*, 1>& MonotonicLoadInsts) {
 566   bool Changed = false;
 567   for (auto* LI : MonotonicLoadInsts) {
 568     auto* FirstInst = findFirstStoreCondBranchInst(LI);
 569     if (FirstInst == nullptr) {
 570       // We don't seem to be able to taint a following store/conditional branch
 571       // instruction. Simply make it acquire.
 572       DEBUG(dbgs() << "[RelaxedLoad]: Transformed to acquire load\n"
 573                    << *LI << "\n");
 574       LI->setOrdering(Acquire);
 575       Changed = true;
 576       continue;
 577     }
 578     // Taint 'FirstInst', which could be a store or a condition branch
 579     // instruction.
 580     if (FirstInst->getOpcode() == Instruction::Store) {
 581       Changed |= taintStoreAddress(dyn_cast<StoreInst>(FirstInst), LI);
 582     } else if (FirstInst->getOpcode() == Instruction::Br) {
 583       Changed |= taintConditionalBranch(dyn_cast<BranchInst>(FirstInst), LI);
 584     } else {
 585       assert(false && "findFirstStoreCondBranchInst() should return a "
 586                     "store/condition branch instruction");
 587     }
 588   }
 589   return Changed;
 590 }
 591
 592 /**** Implementations of public methods for dependence tainting ****/
 593 Value* GetUntaintedAddress(Value* CurrentAddress) {
 594   auto* OrAddress = getOrAddress(CurrentAddress);
 595   if (OrAddress == nullptr) {
 596     // Is it tainted by a select instruction?
 597     auto* Inst = dyn_cast<Instruction>(CurrentAddress);
 598     if (nullptr != Inst && Inst->getOpcode() == Instruction::Select) {
 599       // A selection instruction.
 600       if (Inst->getOperand(1) == Inst->getOperand(2)) {
 601         return Inst->getOperand(1);
 602       }
 603     }
 604
 605     return CurrentAddress;
 606   }
 607   Value* ActualAddress = nullptr;
 608
 609   auto* CastToInt = dyn_cast<Instruction>(OrAddress->getOperand(1));
 610   if (CastToInt && CastToInt->getOpcode() == Instruction::PtrToInt) {
 611     return CastToInt->getOperand(0);
 612   } else {
 613     // This should be a IntToPtr constant expression.
 614     ConstantExpr* PtrToIntExpr =
 615         dyn_cast<ConstantExpr>(OrAddress->getOperand(1));
 616     if (PtrToIntExpr && PtrToIntExpr->getOpcode() == Instruction::PtrToInt) {
 617       return PtrToIntExpr->getOperand(0);
 618     }
 619   }
 620
 621   // Looks like it's not been dependence-tainted. Returns itself.
 622   return CurrentAddress;
 623 }
 624
 625 MemoryLocation GetUntaintedMemoryLocation(StoreInst* SI) {
 626   AAMDNodes AATags;
 627   SI->getAAMetadata(AATags);
 628   const auto& DL = SI->getModule()->getDataLayout();
 629   const auto* OriginalAddr = GetUntaintedAddress(SI->getPointerOperand());
 630   DEBUG(if (OriginalAddr != SI->getPointerOperand()) {
 631     dbgs() << "[GetUntaintedMemoryLocation]\n"
 632            << "Storing address: " << *SI->getPointerOperand()
 633            << "\nUntainted address: " << *OriginalAddr << "\n";
 634   });
 635   return MemoryLocation(OriginalAddr,
 636                         DL.getTypeStoreSize(SI->getValueOperand()->getType()),
 637                         AATags);
 638 }
 639
 640 bool TaintDependenceToStore(StoreInst* SI, Value* DepVal) {
 641   if (dependenceSetInclusion(SI, DepVal)) {
 642     return false;
 643   }
 644
 645   bool tainted = taintStoreAddress(SI, DepVal);
 646   assert(tainted);
 647   return tainted;
 648 }
 649
 650 bool TaintDependenceToStoreAddress(StoreInst* SI, Value* DepVal) {
 651   if (dependenceSetInclusion(SI->getPointerOperand(), DepVal)) {
 652     return false;
 653   }
 654
 655   bool tainted = taintStoreAddress(SI, DepVal);
 656   assert(tainted);
 657   return tainted;
 658 }
 659
 660 bool CompressTaintedStore(BasicBlock* BB) {
 661   // This function looks for windows of adajcent stores in 'BB' that satisfy the
 662   // following condition (and then do optimization):
 663   // *Addr(d1) = v1, d1 is a condition and is the only dependence the store's
 664   //                 address depends on && Dep(v1) includes Dep(d1);
 665   // *Addr(d2) = v2, d2 is a condition and is the only dependnece the store's
 666   //                 address depends on && Dep(v2) includes Dep(d2) &&
 667   //                 Dep(d2) includes Dep(d1);
 668   // ...
 669   // *Addr(dN) = vN, dN is a condition and is the only dependence the store's
 670   //                 address depends on && Dep(dN) includes Dep(d"N-1").
 671   //
 672   // As a result, Dep(dN) includes [Dep(d1) V ... V Dep(d"N-1")], so we can
 673   // safely transform the above to the following. In between these stores, we
 674   // can omit untainted stores to the same address 'Addr' since they internally
 675   // have dependence on the previous stores on the same address.
 676   // =>
 677   // *Addr = v1
 678   // *Addr = v2
 679   // *Addr(d3) = v3
 680   for (auto BI = BB->begin(), BE = BB->end(); BI != BE; BI++) {
 681     // Look for the first store in such a window of adajacent stores.
 682     auto* FirstSI = dyn_cast<StoreInst>(&*BI);
 683     if (!FirstSI) {
 684       continue;
 685     }
 686
 687     // The first store in the window must be tainted.
 688     auto* UntaintedAddress = GetUntaintedAddress(FirstSI->getPointerOperand());
 689     if (UntaintedAddress == FirstSI->getPointerOperand()) {
 690       continue;
 691     }
 692
 693     // The first store's address must directly depend on and only depend on a
 694     // condition.
 695     auto* FirstSIDepCond = getConditionDependence(FirstSI->getPointerOperand());
 696     if (nullptr == FirstSIDepCond) {
 697       continue;
 698     }
 699
 700     // Dep(first store's storing value) includes Dep(tainted dependence).
 701     if (!dependenceSetInclusion(FirstSI->getValueOperand(), FirstSIDepCond)) {
 702       continue;
 703     }
 704
 705     // Look for subsequent stores to the same address that satisfy the condition
 706     // of "compressing the dependence".
 707     SmallVector<StoreInst*, 8> AdajacentStores;
 708     AdajacentStores.push_back(FirstSI);
 709     auto BII = BasicBlock::iterator(FirstSI);
 710     for (BII++; BII != BE; BII++) {
 711       auto* CurrSI = dyn_cast<StoreInst>(&*BII);
 712       if (!CurrSI) {
 713         if (BII->mayHaveSideEffects()) {
 714           // Be conservative. Instructions with side effects are similar to
 715           // stores.
 716           break;
 717         }
 718         continue;
 719       }
 720
 721       auto* OrigAddress = GetUntaintedAddress(CurrSI->getPointerOperand());
 722       auto* CurrSIDepCond = getConditionDependence(CurrSI->getPointerOperand());
 723       // All other stores must satisfy either:
 724       // A. 'CurrSI' is an untainted store to the same address, or
 725       // B. the combination of the following 5 subconditions:
 726       // 1. Tainted;
 727       // 2. Untainted address is the same as the group's address;
 728       // 3. The address is tainted with a sole value which is a condition;
 729       // 4. The storing value depends on the condition in 3.
 730       // 5. The condition in 3 depends on the previous stores dependence
 731       // condition.
 732
 733       // Condition A. Should ignore this store directly.
 734       if (OrigAddress == CurrSI->getPointerOperand() &&
 735           OrigAddress == UntaintedAddress) {
 736         continue;
 737       }
 738       // Check condition B.
 739       Value* Cond = nullptr;
 740       if (OrigAddress == CurrSI->getPointerOperand() ||
 741           OrigAddress != UntaintedAddress || CurrSIDepCond == nullptr ||
 742           !dependenceSetInclusion(CurrSI->getValueOperand(), CurrSIDepCond)) {
 743         // Check condition 1, 2, 3 & 4.
 744         break;
 745       }
 746
 747       // Check condition 5.
 748       StoreInst* PrevSI = AdajacentStores[AdajacentStores.size() - 1];
 749       auto* PrevSIDepCond = getConditionDependence(PrevSI->getPointerOperand());
 750       assert(PrevSIDepCond &&
 751              "Store in the group must already depend on a condtion");
 752       if (!dependenceSetInclusion(CurrSIDepCond, PrevSIDepCond)) {
 753         break;
 754       }
 755
 756       AdajacentStores.push_back(CurrSI);
 757     }
 758
 759     if (AdajacentStores.size() == 1) {
 760       // The outer loop should keep looking from the next store.
 761       continue;
 762     }
 763
 764     // Now we have such a group of tainted stores to the same address.
 765     DEBUG(dbgs() << "[CompressTaintedStore]\n");
 766     DEBUG(dbgs() << "Original BB\n");
 767     DEBUG(dbgs() << *BB << '\n');
 768     auto* LastSI = AdajacentStores[AdajacentStores.size() - 1];
 769     for (int i = 0; i < AdajacentStores.size() - 1; ++i) {
 770       auto* SI = AdajacentStores[i];
 771
 772       // Use the original address for stores before the last one.
 773       SI->setOperand(1, UntaintedAddress);
 774
 775       DEBUG(dbgs() << "Store address has been reversed: " << *SI << '\n';);
 776     }
 777     // XXX-comment: Try to make the last store use fewer registers.
 778     // If LastSI's storing value is a select based on the condition with which
 779     // its address is tainted, transform the tainted address to a select
 780     // instruction, as follows:
 781     // r1 = Select Cond ? A : B
 782     // r2 = Cond & 0
 783     // r3 = Addr | r2
 784     // *r3 = r1
 785     // ==>
 786     // r1 = Select Cond ? A : B
 787     // r2 = Select Cond ? Addr : Addr
 788     // *r2 = r1
 789     // The idea is that both Select instructions depend on the same condition,
 790     // so hopefully the backend can generate two cmov instructions for them (and
 791     // this saves the number of registers needed).
 792     auto* LastSIDep = getConditionDependence(LastSI->getPointerOperand());
 793     auto* LastSIValue = dyn_cast<Instruction>(LastSI->getValueOperand());
 794     if (LastSIValue && LastSIValue->getOpcode() == Instruction::Select &&
 795         LastSIValue->getOperand(0) == LastSIDep) {
 796       // XXX-comment: Maybe it's better for us to just leave it as an and/or
 797       // dependence pattern.
 798       //      /*
 799       IRBuilder<true, NoFolder> Builder(LastSI);
 800       auto* Address =
 801           Builder.CreateSelect(LastSIDep, UntaintedAddress, UntaintedAddress);
 802       LastSI->setOperand(1, Address);
 803       DEBUG(dbgs() << "The last store becomes :" << *LastSI << "\n\n";);
 804       //      */
 805     }
 806   }
 807
 808   return true;
 809 }
 810
 811 bool PassDependenceToStore(Value* OldAddress, StoreInst* NewStore) {
 812   Value* OldDep = getDependence(OldAddress);
 813   // Return false when there's no dependence to pass from the OldAddress.
 814   if (!OldDep) {
 815     return false;
 816   }
 817
 818   // No need to pass the dependence to NewStore's address if it already depends
 819   // on whatever 'OldAddress' depends on.
 820   if (StoreAddressDependOnValue(NewStore, OldDep)) {
 821     return false;
 822   }
 823   return taintStoreAddress(NewStore, OldAddress);
 824 }
 825
 826 SmallSet<Value*, 8> FindDependence(Value* Val) {
 827   SmallSet<Value*, 8> DepSet;
 828   recursivelyFindDependence(&DepSet, Val, true /*Only insert leaf nodes*/);
 829   return DepSet;
 830 }
 831
 832 bool StoreAddressDependOnValue(StoreInst* SI, Value* DepVal) {
 833   return dependenceSetInclusion(SI->getPointerOperand(), DepVal);
 834 }
 835
 836 bool StoreDependOnValue(StoreInst* SI, Value* Dep) {
 837   return dependenceSetInclusion(SI, Dep);
 838 }
 839
 840 } // namespace
 841
 842
 843 bool AtomicExpand::runOnFunction(Function &F) {
 844   if (!TM || !TM->getSubtargetImpl(F)->enableAtomicExpand())
 845     return false;
 846   TLI = TM->getSubtargetImpl(F)->getTargetLowering();
 847
 848   SmallVector<Instruction *, 1> AtomicInsts;
 849   SmallVector<LoadInst*, 1> MonotonicLoadInsts;
 850
 851   // Changing control-flow while iterating through it is a bad idea, so gather a
 852   // list of all atomic instructions before we start.
 853   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
 854     // XXX-update: For relaxed loads, change them to acquire. This includes
 855     // relaxed loads, relaxed atomic RMW & relaxed atomic compare exchange.
 856     if (I->isAtomic()) {
 857       switch (I->getOpcode()) {
 858         case Instruction::AtomicCmpXchg: {
 859           // XXX-comment: AtomicCmpXchg in AArch64 will be translated to a
 860           // conditional branch that contains the value of the load anyway, so
 861           // we don't need to do anything.
 862           /*
 863           auto* CmpXchg = dyn_cast<AtomicCmpXchgInst>(&*I);
 864           auto SuccOrdering = CmpXchg->getSuccessOrdering();
 865           if (SuccOrdering == Monotonic) {
 866             CmpXchg->setSuccessOrdering(Acquire);
 867           } else if (SuccOrdering == Release) {
 868             CmpXchg->setSuccessOrdering(AcquireRelease);
 869           }
 870           */
 871           break;
 872         }
 873         case Instruction::AtomicRMW: {
 874           // XXX-comment: Similar to AtomicCmpXchg. These instructions in
 875           // AArch64 will be translated to a loop whose condition depends on the
 876           // store status, which further depends on the load value.
 877           /*
 878           auto* RMW = dyn_cast<AtomicRMWInst>(&*I);
 879           if (RMW->getOrdering() == Monotonic) {
 880             RMW->setOrdering(Acquire);
 881           }
 882           */
 883           break;
 884         }
 885         case Instruction::Load: {
 886           auto* LI = dyn_cast<LoadInst>(&*I);
 887           if (LI->getOrdering() == Monotonic) {
 888             /*
 889             DEBUG(dbgs() << "Transforming relaxed loads to acquire loads: "
 890                          << *LI << '\n');
 891             LI->setOrdering(Acquire);
 892             */
 893             MonotonicLoadInsts.push_back(LI);
 894           }
 895           break;
 896         }
 897         default: {
 898           break;
 899         }
 900       }
 901       AtomicInsts.push_back(&*I);
 902     }
 903   }
 904
 905   bool MadeChange = false;
 906   for (auto I : AtomicInsts) {
 907     auto LI = dyn_cast<LoadInst>(I);
 908     auto SI = dyn_cast<StoreInst>(I);
 909     auto RMWI = dyn_cast<AtomicRMWInst>(I);
 910     auto CASI = dyn_cast<AtomicCmpXchgInst>(I);
 911     assert((LI || SI || RMWI || CASI || isa<FenceInst>(I)) &&
 912            "Unknown atomic instruction");
 913
 914     auto FenceOrdering = Monotonic;
 915     bool IsStore, IsLoad;
 916     if (TLI->getInsertFencesForAtomic()) {
 917       if (LI && isAtLeastAcquire(LI->getOrdering())) {
 918         FenceOrdering = LI->getOrdering();
 919         LI->setOrdering(Monotonic);
 920         IsStore = false;
 921         IsLoad = true;
 922       } else if (SI && isAtLeastRelease(SI->getOrdering())) {
 923         FenceOrdering = SI->getOrdering();
 924         SI->setOrdering(Monotonic);
 925         IsStore = true;
 926         IsLoad = false;
 927       } else if (RMWI && (isAtLeastRelease(RMWI->getOrdering()) ||
 928                           isAtLeastAcquire(RMWI->getOrdering()))) {
 929         FenceOrdering = RMWI->getOrdering();
 930         RMWI->setOrdering(Monotonic);
 931         IsStore = IsLoad = true;
 932       } else if (CASI && !TLI->shouldExpandAtomicCmpXchgInIR(CASI) &&
 933                  (isAtLeastRelease(CASI->getSuccessOrdering()) ||
 934                   isAtLeastAcquire(CASI->getSuccessOrdering()))) {
 935         // If a compare and swap is lowered to LL/SC, we can do smarter fence
 936         // insertion, with a stronger one on the success path than on the
 937         // failure path. As a result, fence insertion is directly done by
 938         // expandAtomicCmpXchg in that case.
 939         FenceOrdering = CASI->getSuccessOrdering();
 940         CASI->setSuccessOrdering(Monotonic);
 941         CASI->setFailureOrdering(Monotonic);
 942         IsStore = IsLoad = true;
 943       }
 944
 945       if (FenceOrdering != Monotonic) {
 946         MadeChange |= bracketInstWithFences(I, FenceOrdering, IsStore, IsLoad);
 947       }
 948     }
 949
 950     if (LI) {
 951       if (LI->getType()->isFloatingPointTy()) {
 952         // TODO: add a TLI hook to control this so that each target can
 953         // convert to lowering the original type one at a time.
 954         LI = convertAtomicLoadToIntegerType(LI);
 955         assert(LI->getType()->isIntegerTy() && "invariant broken");
 956         MadeChange = true;
 957       }
 958
 959       MadeChange |= tryExpandAtomicLoad(LI);
 960     } else if (SI) {
 961       if (SI->getValueOperand()->getType()->isFloatingPointTy()) {
 962         // TODO: add a TLI hook to control this so that each target can
 963         // convert to lowering the original type one at a time.
 964         SI = convertAtomicStoreToIntegerType(SI);
 965         assert(SI->getValueOperand()->getType()->isIntegerTy() &&
 966                "invariant broken");
 967         MadeChange = true;
 968       }
 969
 970       if (TLI->shouldExpandAtomicStoreInIR(SI))
 971         MadeChange |= expandAtomicStore(SI);
 972     } else if (RMWI) {
 973       // There are two different ways of expanding RMW instructions:
 974       // - into a load if it is idempotent
 975       // - into a Cmpxchg/LL-SC loop otherwise
 976       // we try them in that order.
 977
 978       if (isIdempotentRMW(RMWI) && simplifyIdempotentRMW(RMWI)) {
 979         MadeChange = true;
 980       } else {
 981         MadeChange |= tryExpandAtomicRMW(RMWI);
 982       }
 983     } else if (CASI && TLI->shouldExpandAtomicCmpXchgInIR(CASI)) {
 984       MadeChange |= expandAtomicCmpXchg(CASI);
 985     }
 986   }
 987
 988   MadeChange |= taintMonotonicLoads(MonotonicLoadInsts);
 989
 990   return MadeChange;
 991 }
 992
 993 bool AtomicExpand::bracketInstWithFences(Instruction *I, AtomicOrdering Order,
 994                                          bool IsStore, bool IsLoad) {
 995   IRBuilder<> Builder(I);
 996
 997   auto LeadingFence = TLI->emitLeadingFence(Builder, Order, IsStore, IsLoad);
 998
 999   auto TrailingFence = TLI->emitTrailingFence(Builder, Order, IsStore, IsLoad);
1000   // The trailing fence is emitted before the instruction instead of after
1001   // because there is no easy way of setting Builder insertion point after
1002   // an instruction. So we must erase it from the BB, and insert it back
1003   // in the right place.
1004   // We have a guard here because not every atomic operation generates a
1005   // trailing fence.
1006   if (TrailingFence) {
1007     TrailingFence->removeFromParent();
1008     TrailingFence->insertAfter(I);
1009   }
1010
1011   return (LeadingFence || TrailingFence);
1012 }
1013
1014 /// Get the iX type with the same bitwidth as T.
1015 IntegerType *AtomicExpand::getCorrespondingIntegerType(Type *T,
1016                                                        const DataLayout &DL) {
1017   EVT VT = TLI->getValueType(DL, T);
1018   unsigned BitWidth = VT.getStoreSizeInBits();
1019   assert(BitWidth == VT.getSizeInBits() && "must be a power of two");
1020   return IntegerType::get(T->getContext(), BitWidth);
1021 }
1022
1023 /// Convert an atomic load of a non-integral type to an integer load of the
1024 /// equivelent bitwidth.  See the function comment on
1025 /// convertAtomicStoreToIntegerType for background.
1026 LoadInst *AtomicExpand::convertAtomicLoadToIntegerType(LoadInst *LI) {
1027   auto *M = LI->getModule();
1028   Type *NewTy = getCorrespondingIntegerType(LI->getType(),
1029                                             M->getDataLayout());
1030
1031   IRBuilder<> Builder(LI);
1032
1033   Value *Addr = LI->getPointerOperand();
1034   Type *PT = PointerType::get(NewTy,
1035                               Addr->getType()->getPointerAddressSpace());
1036   Value *NewAddr = Builder.CreateBitCast(Addr, PT);
1037
1038   auto *NewLI = Builder.CreateLoad(NewAddr);
1039   NewLI->setAlignment(LI->getAlignment());
1040   NewLI->setVolatile(LI->isVolatile());
1041   NewLI->setAtomic(LI->getOrdering(), LI->getSynchScope());
1042   DEBUG(dbgs() << "Replaced " << *LI << " with " << *NewLI << "\n");
1043
1044   Value *NewVal = Builder.CreateBitCast(NewLI, LI->getType());
1045   LI->replaceAllUsesWith(NewVal);
1046   LI->eraseFromParent();
1047   return NewLI;
1048 }
1049
1050 bool AtomicExpand::tryExpandAtomicLoad(LoadInst *LI) {
1051   switch (TLI->shouldExpandAtomicLoadInIR(LI)) {
1052   case TargetLoweringBase::AtomicExpansionKind::None:
1053     return false;
1054   case TargetLoweringBase::AtomicExpansionKind::LLSC:
1055     return expandAtomicOpToLLSC(
1056         LI, LI->getPointerOperand(), LI->getOrdering(),
1057         [](IRBuilder<> &Builder, Value *Loaded) { return Loaded; });
1058   case TargetLoweringBase::AtomicExpansionKind::LLOnly:
1059     return expandAtomicLoadToLL(LI);
1060   case TargetLoweringBase::AtomicExpansionKind::CmpXChg:
1061     return expandAtomicLoadToCmpXchg(LI);
1062   }
1063   llvm_unreachable("Unhandled case in tryExpandAtomicLoad");
1064 }
1065
1066 bool AtomicExpand::expandAtomicLoadToLL(LoadInst *LI) {
1067   IRBuilder<> Builder(LI);
1068
1069   // On some architectures, load-linked instructions are atomic for larger
1070   // sizes than normal loads. For example, the only 64-bit load guaranteed
1071   // to be single-copy atomic by ARM is an ldrexd (A3.5.3).
1072   Value *Val =
1073       TLI->emitLoadLinked(Builder, LI->getPointerOperand(), LI->getOrdering());
1074   TLI->emitAtomicCmpXchgNoStoreLLBalance(Builder);
1075
1076   LI->replaceAllUsesWith(Val);
1077   LI->eraseFromParent();
1078
1079   return true;
1080 }
1081
1082 bool AtomicExpand::expandAtomicLoadToCmpXchg(LoadInst *LI) {
1083   IRBuilder<> Builder(LI);
1084   AtomicOrdering Order = LI->getOrdering();
1085   Value *Addr = LI->getPointerOperand();
1086   Type *Ty = cast<PointerType>(Addr->getType())->getElementType();
1087   Constant *DummyVal = Constant::getNullValue(Ty);
1088
1089   Value *Pair = Builder.CreateAtomicCmpXchg(
1090       Addr, DummyVal, DummyVal, Order,
1091       AtomicCmpXchgInst::getStrongestFailureOrdering(Order));
1092   Value *Loaded = Builder.CreateExtractValue(Pair, 0, "loaded");
1093
1094   LI->replaceAllUsesWith(Loaded);
1095   LI->eraseFromParent();
1096
1097   return true;
1098 }
1099
1100 /// Convert an atomic store of a non-integral type to an integer store of the
1101 /// equivelent bitwidth.  We used to not support floating point or vector
1102 /// atomics in the IR at all.  The backends learned to deal with the bitcast
1103 /// idiom because that was the only way of expressing the notion of a atomic
1104 /// float or vector store.  The long term plan is to teach each backend to
1105 /// instruction select from the original atomic store, but as a migration
1106 /// mechanism, we convert back to the old format which the backends understand.
1107 /// Each backend will need individual work to recognize the new format.
1108 StoreInst *AtomicExpand::convertAtomicStoreToIntegerType(StoreInst *SI) {
1109   IRBuilder<> Builder(SI);
1110   auto *M = SI->getModule();
1111   Type *NewTy = getCorrespondingIntegerType(SI->getValueOperand()->getType(),
1112                                             M->getDataLayout());
1113   Value *NewVal = Builder.CreateBitCast(SI->getValueOperand(), NewTy);
1114
1115   Value *Addr = SI->getPointerOperand();
1116   Type *PT = PointerType::get(NewTy,
1117                               Addr->getType()->getPointerAddressSpace());
1118   Value *NewAddr = Builder.CreateBitCast(Addr, PT);
1119
1120   StoreInst *NewSI = Builder.CreateStore(NewVal, NewAddr);
1121   NewSI->setAlignment(SI->getAlignment());
1122   NewSI->setVolatile(SI->isVolatile());
1123   NewSI->setAtomic(SI->getOrdering(), SI->getSynchScope());
1124   DEBUG(dbgs() << "Replaced " << *SI << " with " << *NewSI << "\n");
1125   SI->eraseFromParent();
1126   return NewSI;
1127 }
1128
1129 bool AtomicExpand::expandAtomicStore(StoreInst *SI) {
1130   // This function is only called on atomic stores that are too large to be
1131   // atomic if implemented as a native store. So we replace them by an
1132   // atomic swap, that can be implemented for example as a ldrex/strex on ARM
1133   // or lock cmpxchg8/16b on X86, as these are atomic for larger sizes.
1134   // It is the responsibility of the target to only signal expansion via
1135   // shouldExpandAtomicRMW in cases where this is required and possible.
1136   IRBuilder<> Builder(SI);
1137   AtomicRMWInst *AI =
1138       Builder.CreateAtomicRMW(AtomicRMWInst::Xchg, SI->getPointerOperand(),
1139                               SI->getValueOperand(), SI->getOrdering());
1140   SI->eraseFromParent();
1141
1142   // Now we have an appropriate swap instruction, lower it as usual.
1143   return tryExpandAtomicRMW(AI);
1144 }
1145
1146 static void createCmpXchgInstFun(IRBuilder<> &Builder, Value *Addr,
1147                                  Value *Loaded, Value *NewVal,
1148                                  AtomicOrdering MemOpOrder,
1149                                  Value *&Success, Value *&NewLoaded) {
1150   Value* Pair = Builder.CreateAtomicCmpXchg(
1151       Addr, Loaded, NewVal, MemOpOrder,
1152       AtomicCmpXchgInst::getStrongestFailureOrdering(MemOpOrder));
1153   Success = Builder.CreateExtractValue(Pair, 1, "success");
1154   NewLoaded = Builder.CreateExtractValue(Pair, 0, "newloaded");
1155 }
1156
1157 /// Emit IR to implement the given atomicrmw operation on values in registers,
1158 /// returning the new value.
1159 static Value *performAtomicOp(AtomicRMWInst::BinOp Op, IRBuilder<> &Builder,
1160                               Value *Loaded, Value *Inc) {
1161   Value *NewVal;
1162   switch (Op) {
1163   case AtomicRMWInst::Xchg:
1164     return Inc;
1165   case AtomicRMWInst::Add:
1166     return Builder.CreateAdd(Loaded, Inc, "new");
1167   case AtomicRMWInst::Sub:
1168     return Builder.CreateSub(Loaded, Inc, "new");
1169   case AtomicRMWInst::And:
1170     return Builder.CreateAnd(Loaded, Inc, "new");
1171   case AtomicRMWInst::Nand:
1172     return Builder.CreateNot(Builder.CreateAnd(Loaded, Inc), "new");
1173   case AtomicRMWInst::Or:
1174     return Builder.CreateOr(Loaded, Inc, "new");
1175   case AtomicRMWInst::Xor:
1176     return Builder.CreateXor(Loaded, Inc, "new");
1177   case AtomicRMWInst::Max:
1178     NewVal = Builder.CreateICmpSGT(Loaded, Inc);
1179     return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
1180   case AtomicRMWInst::Min:
1181     NewVal = Builder.CreateICmpSLE(Loaded, Inc);
1182     return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
1183   case AtomicRMWInst::UMax:
1184     NewVal = Builder.CreateICmpUGT(Loaded, Inc);
1185     return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
1186   case AtomicRMWInst::UMin:
1187     NewVal = Builder.CreateICmpULE(Loaded, Inc);
1188     return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
1189   default:
1190     llvm_unreachable("Unknown atomic op");
1191   }
1192 }
1193
1194 bool AtomicExpand::tryExpandAtomicRMW(AtomicRMWInst *AI) {
1195   switch (TLI->shouldExpandAtomicRMWInIR(AI)) {
1196   case TargetLoweringBase::AtomicExpansionKind::None:
1197     return false;
1198   case TargetLoweringBase::AtomicExpansionKind::LLSC:
1199     return expandAtomicOpToLLSC(AI, AI->getPointerOperand(), AI->getOrdering(),
1200                                 [&](IRBuilder<> &Builder, Value *Loaded) {
1201                                   return performAtomicOp(AI->getOperation(),
1202                                                          Builder, Loaded,
1203                                                          AI->getValOperand());
1204                                 });
1205   case TargetLoweringBase::AtomicExpansionKind::CmpXChg:
1206     return expandAtomicRMWToCmpXchg(AI, createCmpXchgInstFun);
1207   default:
1208     llvm_unreachable("Unhandled case in tryExpandAtomicRMW");
1209   }
1210 }
1211
1212 bool AtomicExpand::expandAtomicOpToLLSC(
1213     Instruction *I, Value *Addr, AtomicOrdering MemOpOrder,
1214     std::function<Value *(IRBuilder<> &, Value *)> PerformOp) {
1215   BasicBlock *BB = I->getParent();
1216   Function *F = BB->getParent();
1217   LLVMContext &Ctx = F->getContext();
1218
1219   // Given: atomicrmw some_op iN* %addr, iN %incr ordering
1220   //
1221   // The standard expansion we produce is:
1222   //     [...]
1223   //     fence?
1224   // atomicrmw.start:
1225   //     %loaded = @load.linked(%addr)
1226   //     %new = some_op iN %loaded, %incr
1227   //     %stored = @store_conditional(%new, %addr)
1228   //     %try_again = icmp i32 ne %stored, 0
1229   //     br i1 %try_again, label %loop, label %atomicrmw.end
1230   // atomicrmw.end:
1231   //     fence?
1232   //     [...]
1233   BasicBlock *ExitBB = BB->splitBasicBlock(I->getIterator(), "atomicrmw.end");
1234   BasicBlock *LoopBB =  BasicBlock::Create(Ctx, "atomicrmw.start", F, ExitBB);
1235
1236   // This grabs the DebugLoc from I.
1237   IRBuilder<> Builder(I);
1238
1239   // The split call above "helpfully" added a branch at the end of BB (to the
1240   // wrong place), but we might want a fence too. It's easiest to just remove
1241   // the branch entirely.
1242   std::prev(BB->end())->eraseFromParent();
1243   Builder.SetInsertPoint(BB);
1244   Builder.CreateBr(LoopBB);
1245
1246   // Start the main loop block now that we've taken care of the preliminaries.
1247   Builder.SetInsertPoint(LoopBB);
1248   Value *Loaded = TLI->emitLoadLinked(Builder, Addr, MemOpOrder);
1249
1250   Value *NewVal = PerformOp(Builder, Loaded);
1251
1252   Value *StoreSuccess =
1253       TLI->emitStoreConditional(Builder, NewVal, Addr, MemOpOrder);
1254   Value *TryAgain = Builder.CreateICmpNE(
1255       StoreSuccess, ConstantInt::get(IntegerType::get(Ctx, 32), 0), "tryagain");
1256   Builder.CreateCondBr(TryAgain, LoopBB, ExitBB);
1257
1258   Builder.SetInsertPoint(ExitBB, ExitBB->begin());
1259
1260   I->replaceAllUsesWith(Loaded);
1261   I->eraseFromParent();
1262
1263   return true;
1264 }
1265
1266 bool AtomicExpand::expandAtomicCmpXchg(AtomicCmpXchgInst *CI) {
1267   AtomicOrdering SuccessOrder = CI->getSuccessOrdering();
1268   AtomicOrdering FailureOrder = CI->getFailureOrdering();
1269   Value *Addr = CI->getPointerOperand();
1270   BasicBlock *BB = CI->getParent();
1271   Function *F = BB->getParent();
1272   LLVMContext &Ctx = F->getContext();
1273   // If getInsertFencesForAtomic() returns true, then the target does not want
1274   // to deal with memory orders, and emitLeading/TrailingFence should take care
1275   // of everything. Otherwise, emitLeading/TrailingFence are no-op and we
1276   // should preserve the ordering.
1277   AtomicOrdering MemOpOrder =
1278       TLI->getInsertFencesForAtomic() ? Monotonic : SuccessOrder;
1279
1280   // Given: cmpxchg some_op iN* %addr, iN %desired, iN %new success_ord fail_ord
1281   //
1282   // The full expansion we produce is:
1283   //     [...]
1284   //     fence?
1285   // cmpxchg.start:
1286   //     %loaded = @load.linked(%addr)
1287   //     %should_store = icmp eq %loaded, %desired
1288   //     br i1 %should_store, label %cmpxchg.trystore,
1289   //                          label %cmpxchg.nostore
1290   // cmpxchg.trystore:
1291   //     %stored = @store_conditional(%new, %addr)
1292   //     %success = icmp eq i32 %stored, 0
1293   //     br i1 %success, label %cmpxchg.success, label %loop/%cmpxchg.failure
1294   // cmpxchg.success:
1295   //     fence?
1296   //     br label %cmpxchg.end
1297   // cmpxchg.nostore:
1298   //     @load_linked_fail_balance()?
1299   //     br label %cmpxchg.failure
1300   // cmpxchg.failure:
1301   //     fence?
1302   //     br label %cmpxchg.end
1303   // cmpxchg.end:
1304   //     %success = phi i1 [true, %cmpxchg.success], [false, %cmpxchg.failure]
1305   //     %restmp = insertvalue { iN, i1 } undef, iN %loaded, 0
1306   //     %res = insertvalue { iN, i1 } %restmp, i1 %success, 1
1307   //     [...]
1308   BasicBlock *ExitBB = BB->splitBasicBlock(CI->getIterator(), "cmpxchg.end");
1309   auto FailureBB = BasicBlock::Create(Ctx, "cmpxchg.failure", F, ExitBB);
1310   auto NoStoreBB = BasicBlock::Create(Ctx, "cmpxchg.nostore", F, FailureBB);
1311   auto SuccessBB = BasicBlock::Create(Ctx, "cmpxchg.success", F, NoStoreBB);
1312   auto TryStoreBB = BasicBlock::Create(Ctx, "cmpxchg.trystore", F, SuccessBB);
1313   auto LoopBB = BasicBlock::Create(Ctx, "cmpxchg.start", F, TryStoreBB);
1314
1315   // This grabs the DebugLoc from CI
1316   IRBuilder<> Builder(CI);
1317
1318   // The split call above "helpfully" added a branch at the end of BB (to the
1319   // wrong place), but we might want a fence too. It's easiest to just remove
1320   // the branch entirely.
1321   std::prev(BB->end())->eraseFromParent();
1322   Builder.SetInsertPoint(BB);
1323   TLI->emitLeadingFence(Builder, SuccessOrder, /*IsStore=*/true,
1324                         /*IsLoad=*/true);
1325   Builder.CreateBr(LoopBB);
1326
1327   // Start the main loop block now that we've taken care of the preliminaries.
1328   Builder.SetInsertPoint(LoopBB);
1329   Value *Loaded = TLI->emitLoadLinked(Builder, Addr, MemOpOrder);
1330   Value *ShouldStore =
1331       Builder.CreateICmpEQ(Loaded, CI->getCompareOperand(), "should_store");
1332
1333   // If the cmpxchg doesn't actually need any ordering when it fails, we can
1334   // jump straight past that fence instruction (if it exists).
1335   Builder.CreateCondBr(ShouldStore, TryStoreBB, NoStoreBB);
1336
1337   Builder.SetInsertPoint(TryStoreBB);
1338   Value *StoreSuccess = TLI->emitStoreConditional(
1339       Builder, CI->getNewValOperand(), Addr, MemOpOrder);
1340   StoreSuccess = Builder.CreateICmpEQ(
1341       StoreSuccess, ConstantInt::get(Type::getInt32Ty(Ctx), 0), "success");
1342   Builder.CreateCondBr(StoreSuccess, SuccessBB,
1343                        CI->isWeak() ? FailureBB : LoopBB);
1344
1345   // Make sure later instructions don't get reordered with a fence if necessary.
1346   Builder.SetInsertPoint(SuccessBB);
1347   TLI->emitTrailingFence(Builder, SuccessOrder, /*IsStore=*/true,
1348                          /*IsLoad=*/true);
1349   Builder.CreateBr(ExitBB);
1350
1351   Builder.SetInsertPoint(NoStoreBB);
1352   // In the failing case, where we don't execute the store-conditional, the
1353   // target might want to balance out the load-linked with a dedicated
1354   // instruction (e.g., on ARM, clearing the exclusive monitor).
1355   TLI->emitAtomicCmpXchgNoStoreLLBalance(Builder);
1356   Builder.CreateBr(FailureBB);
1357
1358   Builder.SetInsertPoint(FailureBB);
1359   TLI->emitTrailingFence(Builder, FailureOrder, /*IsStore=*/true,
1360                          /*IsLoad=*/true);
1361   Builder.CreateBr(ExitBB);
1362
1363   // Finally, we have control-flow based knowledge of whether the cmpxchg
1364   // succeeded or not. We expose this to later passes by converting any
1365   // subsequent "icmp eq/ne %loaded, %oldval" into a use of an appropriate PHI.
1366
1367   // Setup the builder so we can create any PHIs we need.
1368   Builder.SetInsertPoint(ExitBB, ExitBB->begin());
1369   PHINode *Success = Builder.CreatePHI(Type::getInt1Ty(Ctx), 2);
1370   Success->addIncoming(ConstantInt::getTrue(Ctx), SuccessBB);
1371   Success->addIncoming(ConstantInt::getFalse(Ctx), FailureBB);
1372
1373   // Look for any users of the cmpxchg that are just comparing the loaded value
1374   // against the desired one, and replace them with the CFG-derived version.
1375   SmallVector<ExtractValueInst *, 2> PrunedInsts;
1376   for (auto User : CI->users()) {
1377     ExtractValueInst *EV = dyn_cast<ExtractValueInst>(User);
1378     if (!EV)
1379       continue;
1380
1381     assert(EV->getNumIndices() == 1 && EV->getIndices()[0] <= 1 &&
1382            "weird extraction from { iN, i1 }");
1383
1384     if (EV->getIndices()[0] == 0)
1385       EV->replaceAllUsesWith(Loaded);
1386     else
1387       EV->replaceAllUsesWith(Success);
1388
1389     PrunedInsts.push_back(EV);
1390   }
1391
1392   // We can remove the instructions now we're no longer iterating through them.
1393   for (auto EV : PrunedInsts)
1394     EV->eraseFromParent();
1395
1396   if (!CI->use_empty()) {
1397     // Some use of the full struct return that we don't understand has happened,
1398     // so we've got to reconstruct it properly.
1399     Value *Res;
1400     Res = Builder.CreateInsertValue(UndefValue::get(CI->getType()), Loaded, 0);
1401     Res = Builder.CreateInsertValue(Res, Success, 1);
1402
1403     CI->replaceAllUsesWith(Res);
1404   }
1405
1406   CI->eraseFromParent();
1407   return true;
1408 }
1409
1410 bool AtomicExpand::isIdempotentRMW(AtomicRMWInst* RMWI) {
1411   auto C = dyn_cast<ConstantInt>(RMWI->getValOperand());
1412   if(!C)
1413     return false;
1414
1415   AtomicRMWInst::BinOp Op = RMWI->getOperation();
1416   switch(Op) {
1417     case AtomicRMWInst::Add:
1418     case AtomicRMWInst::Sub:
1419     case AtomicRMWInst::Or:
1420     case AtomicRMWInst::Xor:
1421       return C->isZero();
1422     case AtomicRMWInst::And:
1423       return C->isMinusOne();
1424     // FIXME: we could also treat Min/Max/UMin/UMax by the INT_MIN/INT_MAX/...
1425     default:
1426       return false;
1427   }
1428 }
1429
1430 bool AtomicExpand::simplifyIdempotentRMW(AtomicRMWInst* RMWI) {
1431   if (auto ResultingLoad = TLI->lowerIdempotentRMWIntoFencedLoad(RMWI)) {
1432     tryExpandAtomicLoad(ResultingLoad);
1433     return true;
1434   }
1435   return false;
1436 }
1437
1438 bool llvm::expandAtomicRMWToCmpXchg(AtomicRMWInst *AI,
1439                                     CreateCmpXchgInstFun CreateCmpXchg) {
1440   assert(AI);
1441
1442   AtomicOrdering MemOpOrder =
1443       AI->getOrdering() == Unordered ? Monotonic : AI->getOrdering();
1444   Value *Addr = AI->getPointerOperand();
1445   BasicBlock *BB = AI->getParent();
1446   Function *F = BB->getParent();
1447   LLVMContext &Ctx = F->getContext();
1448
1449   // Given: atomicrmw some_op iN* %addr, iN %incr ordering
1450   //
1451   // The standard expansion we produce is:
1452   //     [...]
1453   //     %init_loaded = load atomic iN* %addr
1454   //     br label %loop
1455   // loop:
1456   //     %loaded = phi iN [ %init_loaded, %entry ], [ %new_loaded, %loop ]
1457   //     %new = some_op iN %loaded, %incr
1458   //     %pair = cmpxchg iN* %addr, iN %loaded, iN %new
1459   //     %new_loaded = extractvalue { iN, i1 } %pair, 0
1460   //     %success = extractvalue { iN, i1 } %pair, 1
1461   //     br i1 %success, label %atomicrmw.end, label %loop
1462   // atomicrmw.end:
1463   //     [...]
1464   BasicBlock *ExitBB = BB->splitBasicBlock(AI->getIterator(), "atomicrmw.end");
1465   BasicBlock *LoopBB = BasicBlock::Create(Ctx, "atomicrmw.start", F, ExitBB);
1466
1467   // This grabs the DebugLoc from AI.
1468   IRBuilder<> Builder(AI);
1469
1470   // The split call above "helpfully" added a branch at the end of BB (to the
1471   // wrong place), but we want a load. It's easiest to just remove
1472   // the branch entirely.
1473   std::prev(BB->end())->eraseFromParent();
1474   Builder.SetInsertPoint(BB);
1475   LoadInst *InitLoaded = Builder.CreateLoad(Addr);
1476   // Atomics require at least natural alignment.
1477   InitLoaded->setAlignment(AI->getType()->getPrimitiveSizeInBits() / 8);
1478   Builder.CreateBr(LoopBB);
1479
1480   // Start the main loop block now that we've taken care of the preliminaries.
1481   Builder.SetInsertPoint(LoopBB);
1482   PHINode *Loaded = Builder.CreatePHI(AI->getType(), 2, "loaded");
1483   Loaded->addIncoming(InitLoaded, BB);
1484
1485   Value *NewVal =
1486       performAtomicOp(AI->getOperation(), Builder, Loaded, AI->getValOperand());
1487
1488   Value *NewLoaded = nullptr;
1489   Value *Success = nullptr;
1490
1491   CreateCmpXchg(Builder, Addr, Loaded, NewVal, MemOpOrder,
1492                 Success, NewLoaded);
1493   assert(Success && NewLoaded);
1494
1495   Loaded->addIncoming(NewLoaded, LoopBB);
1496
1497   Builder.CreateCondBr(Success, ExitBB, LoopBB);
1498
1499   Builder.SetInsertPoint(ExitBB, ExitBB->begin());
1500
1501   AI->replaceAllUsesWith(NewLoaded);
1502   AI->eraseFromParent();
1503
1504   return true;
1505 }