lib/CodeGen/TaintRelaxedAtomicsUtils.h

   1 //===- TaintRelaxedAtomicsUtils.h - Utils for Tainting Relaxed Atomics --------===//
   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 util functions for taiting relaxed atomics to enforce
  11 // strong ordering.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef _TAINTRELAXEDATOMICSUTILS_H
  16 #define _TAINTRELAXEDATOMICSUTILS_H
  17
  18 #include "llvm/CodeGen/Passes.h"
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/SetVector.h"
  21 #include "llvm/ADT/SmallPtrSet.h"
  22 #include "llvm/ADT/SmallSet.h"
  23 #include "llvm/ADT/SmallVector.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/Analysis/InstructionSimplify.h"
  26 #include "llvm/Analysis/MemoryLocation.h"
  27 #include "llvm/Analysis/TargetLibraryInfo.h"
  28 #include "llvm/Analysis/TargetTransformInfo.h"
  29 #include "llvm/Analysis/ValueTracking.h"
  30 #include "llvm/IR/CallSite.h"
  31 #include "llvm/IR/Constants.h"
  32 #include "llvm/IR/DataLayout.h"
  33 #include "llvm/IR/DerivedTypes.h"
  34 #include "llvm/IR/Dominators.h"
  35 #include "llvm/IR/Function.h"
  36 #include "llvm/IR/GetElementPtrTypeIterator.h"
  37 #include "llvm/IR/IRBuilder.h"
  38 #include "llvm/IR/InlineAsm.h"
  39 #include "llvm/IR/InstIterator.h"
  40 #include "llvm/IR/InstrTypes.h"
  41 #include "llvm/IR/Instructions.h"
  42 #include "llvm/IR/IntrinsicInst.h"
  43 #include "llvm/IR/MDBuilder.h"
  44 #include "llvm/IR/NoFolder.h"
  45 #include "llvm/IR/PatternMatch.h"
  46 #include "llvm/IR/Statepoint.h"
  47 #include "llvm/IR/ValueHandle.h"
  48 #include "llvm/IR/ValueMap.h"
  49 #include "llvm/Pass.h"
  50 #include "llvm/Support/CommandLine.h"
  51 #include "llvm/Support/Debug.h"
  52 #include "llvm/Support/raw_ostream.h"
  53 #include "llvm/Target/TargetLowering.h"
  54 #include "llvm/Target/TargetSubtargetInfo.h"
  55 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  56 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  57 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
  58 #include "llvm/Transforms/Utils/Local.h"
  59 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
  60 using namespace llvm;
  61
  62 namespace llvm {
  63
  64 bool StoreAddressDependOnValue(StoreInst* SI, Value* DepVal);
  65
  66 bool LoadAddressDependOnValue(LoadInst* LI, Value* DepVal);
  67
  68 Value* GetUntaintedAddress(Value* CurrentAddress);
  69
  70 // Helper function to create a Cast instruction.
  71 template <typename BuilderTy>
  72 Value* createCast(BuilderTy& Builder, Value* DepVal, Type* TargetIntegerType);
  73
  74 // Given a value, if it's a tainted address, this function returns the
  75 // instruction that ORs the "dependence value" with the "original address".
  76 // Otherwise, returns nullptr.  This instruction is the first OR instruction
  77 // where one of its operand is an AND instruction with an operand being 0.
  78 //
  79 // E.g., it returns '%4 = or i32 %3, %2' given 'CurrentAddress' is '%5'.
  80 // %0 = load i32, i32* @y, align 4, !tbaa !1
  81 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
  82 // %1 = sext i1 %cmp to i32
  83 // %2 = ptrtoint i32* @x to i32
  84 // %3 = and i32 %1, 0
  85 // %4 = or i32 %3, %2
  86 // %5 = inttoptr i32 %4 to i32*
  87 // store i32 1, i32* %5, align 4
  88 Instruction* getOrAddress(Value* CurrentAddress);
  89
  90 // Given a value, if it's a tainted address, this function returns the
  91 // instruction that taints the "dependence value". Otherwise, returns nullptr.
  92 // This instruction is the last AND instruction where one of its operand is 0.
  93 // E.g., it returns '%3' given 'CurrentAddress' is '%5'.
  94 // %0 = load i32, i32* @y, align 4, !tbaa !1
  95 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
  96 // %1 = sext i1 %cmp to i32
  97 // %2 = ptrtoint i32* @x to i32
  98 // %3 = and i32 %1, 0
  99 // %4 = or i32 %3, %2
 100 // %5 = inttoptr i32 %4 to i32*
 101 // store i32 1, i32* %5, align 4
 102 Instruction* getAndDependence(Value* CurrentAddress);
 103
 104 // Given a value, if it's a tainted address, this function returns
 105 // the "dependence value", which is the first operand in the AND instruction.
 106 // E.g., it returns '%1' given 'CurrentAddress' is '%5'.
 107 // %0 = load i32, i32* @y, align 4, !tbaa !1
 108 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
 109 // %1 = sext i1 %cmp to i32
 110 // %2 = ptrtoint i32* @x to i32
 111 // %3 = and i32 %1, 0
 112 // %4 = or i32 %3, %2
 113 // %5 = inttoptr i32 %4 to i32*
 114 // store i32 1, i32* %5, align 4
 115 Value* getDependence(Value* CurrentAddress);
 116
 117 // Given an address that has been tainted, returns the only condition it depends
 118 // on, if any; otherwise, returns nullptr.
 119 Value* getConditionDependence(Value* Address);
 120
 121 // Conservatively decides whether the dependence set of 'Val1' includes the
 122 // dependence set of 'Val2'. If 'ExpandSecondValue' is false, we do not expand
 123 // 'Val2' and use that single value as its dependence set.
 124 // If it returns true, it means the dependence set of 'Val1' includes that of
 125 // 'Val2'; otherwise, it only means we cannot conclusively decide it.
 126 bool dependenceSetInclusion(Value* Val1, Value* Val2,
 127                             int Val1ExpandLevel,
 128                             int Val2ExpandLevel);
 129
 130 // Recursively iterates through the operands spawned from 'DepVal'. If there
 131 // exists a single value that 'DepVal' only depends on, we call that value the
 132 // root dependence of 'DepVal' and return it. Otherwise, return 'DepVal'.
 133 Value* getRootDependence(Value* DepVal);
 134
 135 // This function actually taints 'DepVal' to the address to 'SI'. If the
 136 // address
 137 // of 'SI' already depends on whatever 'DepVal' depends on, this function
 138 // doesn't do anything and returns false. Otherwise, returns true.
 139 //
 140 // This effect forces the store and any stores that comes later to depend on
 141 // 'DepVal'. For example, we have a condition "cond", and a store instruction
 142 // "s: STORE addr, val". If we want "s" (and any later store) to depend on
 143 // "cond", we do the following:
 144 // %conv = sext i1 %cond to i32
 145 // %addrVal = ptrtoint i32* %addr to i32
 146 // %andCond = and i32 conv, 0;
 147 // %orAddr = or i32 %andCond, %addrVal;
 148 // %NewAddr = inttoptr i32 %orAddr to i32*;
 149 //
 150 // This is a more concrete example:
 151 // ------
 152 // %0 = load i32, i32* @y, align 4, !tbaa !1
 153 // %cmp = icmp ne i32 %0, 42  // <== this is like the condition
 154 // %1 = sext i1 %cmp to i32
 155 // %2 = ptrtoint i32* @x to i32
 156 // %3 = and i32 %1, 0
 157 // %4 = or i32 %3, %2
 158 // %5 = inttoptr i32 %4 to i32*
 159 // store i32 1, i32* %5, align 4
 160 bool taintStoreAddress(StoreInst* SI, Value* DepVal);
 161
 162 // Given the load part result of a RMW 'LoadPart', taints the address of the
 163 // store exclusive 'Addr' and returns it.
 164 Value* taintRMWStoreAddressWithLoadPart(IRBuilder<>& Builder, Value* Address,
 165                                         Instruction* LoadPart);
 166
 167 // XXX-comment: Returns true if it changes the code, false otherwise (the
 168 // branch
 169 // condition already depends on 'DepVal'.
 170 bool taintConditionalBranch(BranchInst* BI, Value* DepVal);
 171
 172 bool ConditionalBranchDependsOnValue(BranchInst* BI, Value* DepVal);
 173
 174 // XXX-update: For an instruction (e.g., a relaxed load) 'Inst', find the first
 175 // immediate atomic store or the first conditional branch. Returns nullptr if
 176 // there's no such immediately following store/branch instructions, which we can
 177 // only enforce the load with 'acquire'. 'ChainedBB' contains all the blocks
 178 // chained together with unconditional branches from 'BB' to the block with the
 179 // first store/cond branch.
 180 template <typename Vector>
 181 Instruction* findFirstStoreCondBranchInst(Instruction* Inst, Vector* ChainedBB);
 182
 183 // XXX-update: Find the next node of the last relaxed load from 'FromInst' to
 184 // 'ToInst'. If none, return 'ToInst'.
 185 Instruction* findLastLoadNext(Instruction* FromInst, Instruction* ToInst);
 186
 187 // Inserts a fake conditional branch right after the instruction 'SplitInst',
 188 // and the branch condition is 'Condition'. 'SplitInst' will be placed in the
 189 // newly created block.
 190 void AddFakeConditionalBranch(Instruction* SplitInst, Value* Condition);
 191
 192 // Returns true if the code is changed, and false otherwise.
 193 void TaintRelaxedLoads(Instruction* UsageInst, Instruction* InsertPoint);
 194
 195 // Taints the 'Inst' (i.e., adds a fake conditional block that uses the 'Inst')
 196 // at the beginning of basic block 'BB'. Note that we need to add an appropriate
 197 // PHI node and taint the PHI node. Returns true if the code is changed, and
 198 // false otherwise.
 199 void TaintAtBlockBeginning(Instruction* Inst, BasicBlock* BB);
 200
 201 // XXX-comment: Finds the appropriate Value derived from an atomic load.
 202 // 'ChainedBB' contains all the blocks chained together with unconditional
 203 // branches from LI's parent BB to the block with the first store/cond branch.
 204 // If we don't find any, it means 'LI' is not used at all (which should not
 205 // happen in practice). We can simply set 'LI' to be acquire just to be safe.
 206 template <typename Vector>
 207 Instruction* findMostRecentDependenceUsage(LoadInst* LI, Instruction* LaterInst,
 208                                            Vector* ChainedBB,
 209                                            DominatorTree* DT);
 210
 211 // XXX-comment: For an instruction (e.g., a load) 'Inst', and the first upcoming
 212 // store/conditional branch instruction 'FirstInst', returns whether there are
 213 // any intermediate instructions I (including 'FirstInst') that satisfy:
 214 // 1. I is a load/store, and its address depends on 'Inst'.
 215 // 2. I is a conditional branch whose condition depends on 'Inst'.
 216 // Note that 'Inst' and 'FirstInst' can be in different basic blocks, but Inst's
 217 // basic block can unconditionally jumps (by steps) to FirstInst's block.
 218 bool NeedExtraConstraints(Instruction* Inst, Instruction* FirstInst);
 219
 220 // XXX-comment: For an instruction (e.g., a load) 'Inst', returns whether there
 221 // are any intermediate instructions I (including 'FirstInst') that satisfy:
 222 // 1. There are no reachable store/conditional branch before 'I'.
 223 // 2. I is a load/store, and its address depends on 'Inst'.
 224 // 3. I is a conditional branch whose condition depends on 'Inst'.
 225 // Note that 'Inst' and 'FirstInst' can be in different basic blocks, but Inst's
 226 // basic block can unconditionally jumps (by steps) to FirstInst's block.
 227 bool NeedExtraConstraints(Instruction* Inst);
 228
 229 // XXX-comment: Returns whether the code has been changed.
 230 bool AddFakeConditionalBranchAfterMonotonicLoads(
 231     SmallSet<LoadInst*, 1>& MonotonicLoadInsts, DominatorTree* DT);
 232
 233 /**** Public methods for dependence tainting ****/
 234 Value* GetUntaintedAddress(Value* CurrentAddress);
 235
 236 MemoryLocation GetUntaintedMemoryLocation(StoreInst* SI);
 237
 238 bool TaintDependenceToStore(StoreInst* SI, Value* DepVal);
 239
 240 bool TaintDependenceToStoreAddress(StoreInst* SI, Value* DepVal);
 241
 242 bool CompressTaintedStore(BasicBlock* BB);
 243
 244 bool PassDependenceToStore(Value* OldAddress, StoreInst* NewStore);
 245
 246 SmallSet<Value*, 8> FindDependence(Value* Val);
 247
 248 bool StoreDependOnValue(StoreInst* SI, Value* Dep);
 249
 250 bool ValueDependOnValue(Value * Inst, Value* Dep);
 251
 252 // XXX-update: Checks whether the relaxed load 'LI' has subsequent instructions
 253 // that naturally prevents it from being reordered across later stores.
 254 bool HasSubsequentOrderingProtection(LoadInst* LI);
 255
 256
 257 // XXX-update: Checks whether the tainting to instruction 'I' can be delayed
 258 // with respects to the relaxed load 'LI'. This usually means 'I' itself already
 259 // depends on the 'LI' or 'I' is a store/store-like atomic operation that has
 260 // release semantics.
 261 bool CanDelayTainting(LoadInst* LI, Instruction* I);
 262
 263 } // namespace llvm
 264
 265 #endif