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
47using namespace llvm;
48
49#define DEBUG_TYPE "x86-fence-nontemporal-stores"
50
51static 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.
62static 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.
78static bool isSyncOrReturnPoint(const Instruction &I) {
79 return isa<ReturnInst, InvokeInst, CleanupReturnInst>(Val: &I) ||
80 I.maySynchronize() || I.mayThrow();
81}
82
83static 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
93static 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
192namespace {
193
194class X86FenceNonTemporalStoresLegacy : public FunctionPass {
195public:
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
219char X86FenceNonTemporalStoresLegacy::ID = 0;
220
221INITIALIZE_PASS(X86FenceNonTemporalStoresLegacy, DEBUG_TYPE,
222 "X86 Fence Non-Temporal Stores", false, false)
223
224FunctionPass *llvm::createX86FenceNonTemporalStoresLegacyPass() {
225 return new X86FenceNonTemporalStoresLegacy();
226}
227
228PreservedAnalyses
229X86FenceNonTemporalStoresPass::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