| 1 | //===----------------------------------------------------------------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | /// \file |
| 10 | /// |
| 11 | /// This pass performs forward dataflow analysis to insert `llvm.x86.sse.sfence` |
| 12 | /// intrinsics between non-temporal stores and subsequent potential |
| 13 | /// synchronization points (such as atomic operations, function calls, exception |
| 14 | /// unwinding, and function returns), guaranteeing that weakly-ordered |
| 15 | /// non-temporal stores are serialized before synchronization, while still |
| 16 | /// allowing the performance benefits of non-temporal stores in a loop. |
| 17 | /// |
| 18 | /// Non-temporal store instructions in LLVM IR (!nontemporal metadata) are |
| 19 | /// documented as optimization hints. However, on X86, regular stores follow the |
| 20 | /// TSO (Total Store Order) memory model, whereas non-temporal stores (MOVNT*) |
| 21 | /// write to weakly-ordered write-combining (WC) memory buffers that bypass |
| 22 | /// cache hierarchies. |
| 23 | /// |
| 24 | /// Without explicit memory fences, write-combining stores are not ordered with |
| 25 | /// respect to other WC stores or normal WB stores. As a result, cross-thread |
| 26 | /// synchronization that follows a non-temporal store may allow other threads to |
| 27 | /// observe out-of-order writes, unless an SFENCE is executed. |
| 28 | /// |
| 29 | //===----------------------------------------------------------------------===// |
| 30 | |
| 31 | #include "X86.h" |
| 32 | #include "X86Subtarget.h" |
| 33 | #include "X86TargetMachine.h" |
| 34 | #include "llvm/ADT/DenseMap.h" |
| 35 | #include "llvm/ADT/STLExtras.h" |
| 36 | #include "llvm/ADT/SmallVector.h" |
| 37 | #include "llvm/CodeGen/TargetPassConfig.h" |
| 38 | #include "llvm/IR/BasicBlock.h" |
| 39 | #include "llvm/IR/CFG.h" |
| 40 | #include "llvm/IR/Function.h" |
| 41 | #include "llvm/IR/IRBuilder.h" |
| 42 | #include "llvm/IR/Instructions.h" |
| 43 | #include "llvm/IR/IntrinsicsX86.h" |
| 44 | #include "llvm/IR/PassManager.h" |
| 45 | #include "llvm/Pass.h" |
| 46 | |
| 47 | using namespace llvm; |
| 48 | |
| 49 | #define DEBUG_TYPE "x86-fence-nontemporal-stores" |
| 50 | |
| 51 | static bool isNonTemporalStore(const Instruction &I) { |
| 52 | return I.hasMetadata(KindID: LLVMContext::MD_nontemporal) && I.mayWriteToMemory(); |
| 53 | } |
| 54 | |
| 55 | /// Returns true if I is a hardware fence that serializes write-combining |
| 56 | /// stores: |
| 57 | /// - SFENCE (llvm.x86.sse.sfence) flushes and serializes WC stores. |
| 58 | /// - MFENCE (llvm.x86.sse2.mfence) serializes all memory operations. |
| 59 | /// |
| 60 | /// Note: Atomic fences (such as `fence seq_cst` or `fence release`) do NOT |
| 61 | /// necessarily serialize write-combining stores. |
| 62 | static bool isNonTemporalFence(const Instruction &I) { |
| 63 | if (const auto *CB = dyn_cast<CallBase>(Val: &I)) { |
| 64 | if (auto Intrin = CB->getIntrinsicID()) { |
| 65 | return Intrin == Intrinsic::x86_sse_sfence || |
| 66 | Intrin == Intrinsic::x86_sse2_mfence; |
| 67 | } |
| 68 | } |
| 69 | return false; |
| 70 | } |
| 71 | |
| 72 | /// Returns true if I is a potential cross-thread synchronization point, or |
| 73 | /// which might return to a caller (either via return or throwing). |
| 74 | /// |
| 75 | /// InvokeInst and CleanupRetInst are handled as a special case, because |
| 76 | /// I.mayThrow() may return false, yet return true for their CatchSwitchInst |
| 77 | /// unwind destination, which cannot have non-PHI instructions preceeding it. |
| 78 | static bool isSyncOrReturnPoint(const Instruction &I) { |
| 79 | return isa<ReturnInst, InvokeInst, CleanupReturnInst>(Val: &I) || |
| 80 | I.maySynchronize() || I.mayThrow(); |
| 81 | } |
| 82 | |
| 83 | static bool containsNonTemporalStores(Function &F) { |
| 84 | for (const BasicBlock &BB : F) { |
| 85 | for (const Instruction &I : BB) { |
| 86 | if (isNonTemporalStore(I)) |
| 87 | return true; |
| 88 | } |
| 89 | } |
| 90 | return false; |
| 91 | } |
| 92 | |
| 93 | static bool runImpl(Function &F, const X86Subtarget *ST) { |
| 94 | // If the target lacks SSE1, non-temporal stores cannot use MOVNT instructions |
| 95 | // (they lower to regular TSO stores), and SFENCE is not supported by |
| 96 | // hardware. |
| 97 | if (ST && !ST->hasSSE1()) |
| 98 | return false; |
| 99 | |
| 100 | // Fast path: if the function contains no non-temporal stores, do nothing. |
| 101 | if (!containsNonTemporalStores(F)) |
| 102 | return false; |
| 103 | |
| 104 | // Compute the "dirty" (currently outstanding unfenced non-temporal stores) |
| 105 | // state at entry of each basic block. Note that this is conservative: if a |
| 106 | // block has multiple predecessors, we will insert a sfence if _any_ of the |
| 107 | // predecessors had a nontemporal store, instead of splitting the critical |
| 108 | // edge. |
| 109 | // |
| 110 | // The Flags bitfield keeps track of the state: |
| 111 | // - If the block contains no state-altering instructions, Passthrough = true, |
| 112 | // and we'll then propagate DirtyOut based on DirtyIn |
| 113 | // - If the last state-altering instruction is an NT store, DirtyOut = true |
| 114 | // - If the last state-altering instruction is a fence or sync point (before |
| 115 | // which a fence would be added), DirtyOut = false. |
| 116 | enum BlockFlags { |
| 117 | Passthrough = 1, |
| 118 | DirtyIn = 2, |
| 119 | DirtyOut = 4, |
| 120 | }; |
| 121 | DenseMap<const BasicBlock *, int> Flags; |
| 122 | // Forward dataflow analysis to compute DirtyIn for all basic blocks. |
| 123 | SmallSetVector<const BasicBlock *, 16> Worklist; |
| 124 | |
| 125 | for (const BasicBlock &BB : F) { |
| 126 | int Flag = Passthrough; |
| 127 | for (const Instruction &I : BB) { |
| 128 | if (isNonTemporalStore(I)) { |
| 129 | Flag = DirtyOut; |
| 130 | } else if (isNonTemporalFence(I) || isSyncOrReturnPoint(I)) { |
| 131 | Flag = 0; |
| 132 | } |
| 133 | } |
| 134 | Flags[&BB] = Flag; |
| 135 | |
| 136 | if ((Flag & DirtyOut)) { |
| 137 | for (const BasicBlock *Succ : successors(BB: &BB)) { |
| 138 | Worklist.insert(X: Succ); |
| 139 | } |
| 140 | } |
| 141 | } |
| 142 | |
| 143 | // Iterate the worklist and update DirtyIn/DirtyOut as required, adding |
| 144 | // successors to worklist whenever DirtyOut is modified. |
| 145 | while (!Worklist.empty()) { |
| 146 | const BasicBlock *BB = Worklist.pop_back_val(); |
| 147 | |
| 148 | bool NewDirtyIn = false; |
| 149 | for (const BasicBlock *Pred : predecessors(BB)) { |
| 150 | if (Flags[Pred] & DirtyOut) { |
| 151 | NewDirtyIn = true; |
| 152 | break; |
| 153 | } |
| 154 | } |
| 155 | if (NewDirtyIn && !(Flags[BB] & DirtyIn)) { |
| 156 | Flags[BB] |= DirtyIn; |
| 157 | if (Flags[BB] & Passthrough) { |
| 158 | Flags[BB] |= DirtyOut; |
| 159 | for (const BasicBlock *Succ : successors(BB)) |
| 160 | Worklist.insert(X: Succ); |
| 161 | } |
| 162 | } |
| 163 | } |
| 164 | |
| 165 | // Finally, walk each block and insert sfence before any sync point reached in |
| 166 | // a dirty state. |
| 167 | bool Changed = false; |
| 168 | IRBuilder<> Builder(*F.getParent()); |
| 169 | |
| 170 | for (BasicBlock &BB : F) { |
| 171 | bool CurrentDirty = Flags[&BB] & DirtyIn; |
| 172 | for (Instruction &I : llvm::make_early_inc_range(Range&: BB)) { |
| 173 | if (isNonTemporalStore(I)) { |
| 174 | CurrentDirty = true; |
| 175 | } else if (isNonTemporalFence(I)) { |
| 176 | CurrentDirty = false; |
| 177 | } else if (isSyncOrReturnPoint(I)) { |
| 178 | if (CurrentDirty) { |
| 179 | Builder.SetInsertPoint(&I); |
| 180 | Builder.SetCurrentDebugLocation(I.getDebugLoc()); |
| 181 | Builder.CreateIntrinsic(ID: Intrinsic::x86_sse_sfence, Args: {}); |
| 182 | CurrentDirty = false; |
| 183 | Changed = true; |
| 184 | } |
| 185 | } |
| 186 | } |
| 187 | } |
| 188 | |
| 189 | return Changed; |
| 190 | } |
| 191 | |
| 192 | namespace { |
| 193 | |
| 194 | class X86FenceNonTemporalStoresLegacy : public FunctionPass { |
| 195 | public: |
| 196 | static char ID; |
| 197 | |
| 198 | X86FenceNonTemporalStoresLegacy() : FunctionPass(ID) {} |
| 199 | |
| 200 | bool runOnFunction(Function &F) override { |
| 201 | auto *TPC = getAnalysisIfAvailable<TargetPassConfig>(); |
| 202 | const X86Subtarget *ST = |
| 203 | TPC ? &TPC->getTM<X86TargetMachine>().getSubtarget<X86Subtarget>(F) |
| 204 | : nullptr; |
| 205 | return runImpl(F, ST); |
| 206 | } |
| 207 | |
| 208 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
| 209 | AU.setPreservesCFG(); |
| 210 | } |
| 211 | |
| 212 | StringRef getPassName() const override { |
| 213 | return "X86 Fence Non-Temporal Stores" ; |
| 214 | } |
| 215 | }; |
| 216 | |
| 217 | } // end anonymous namespace |
| 218 | |
| 219 | char X86FenceNonTemporalStoresLegacy::ID = 0; |
| 220 | |
| 221 | INITIALIZE_PASS(X86FenceNonTemporalStoresLegacy, DEBUG_TYPE, |
| 222 | "X86 Fence Non-Temporal Stores" , false, false) |
| 223 | |
| 224 | FunctionPass *llvm::createX86FenceNonTemporalStoresLegacyPass() { |
| 225 | return new X86FenceNonTemporalStoresLegacy(); |
| 226 | } |
| 227 | |
| 228 | PreservedAnalyses |
| 229 | X86FenceNonTemporalStoresPass::run(Function &F, FunctionAnalysisManager &FAM) { |
| 230 | const X86Subtarget *ST = TM ? TM->getSubtargetImpl(F) : nullptr; |
| 231 | if (!runImpl(F, ST)) |
| 232 | return PreservedAnalyses::all(); |
| 233 | |
| 234 | PreservedAnalyses PA; |
| 235 | PA.preserveSet<CFGAnalyses>(); |
| 236 | return PA; |
| 237 | } |
| 238 | |