Add a Pass to X86 that builds a Condensed CFG for Load Value Injection (LVI) Gadgets [4/6]

[sconstab]

Summary

Adds a new data structure, ImmutableGraph, and uses RDF to find LVI gadgets and add them to a MachineGadgetGraph.

More specifically, a new X86 machine pass finds Load Value Injection (LVI) gadgets consisting of a load from memory (i.e., SOURCE), and any operation that may transmit the value loaded from memory over a covert channel, or use the value loaded from memory to determine a branch/call target (i.e., SINK).

Also adds a new target feature to X86: +lvi-load-hardening

The feature can be added via the clang CLI using -mlvi-hardening.

[sconstab]

Added help text for the CLI options

[zbrid]

Thanks for putting this up! Here are a few comments.

llvm/lib/Target/X86/ImmutableGraph.h

1

Might be useful if you add a comment about what makes this a fast DAG impl in case someone may want to use it later.

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

254

I think this should go at the top of the function.

271

Am I misunderstanding this comment? It sounds like if FixedLoads is true then BOTH fixed loads and non-fixed loads will be mitigated. Since runOnMachineFunction would call hardenLoads twice for non-fixed loads, would that result in double mitigation for non-fixed loads in the case where we also harden fixed loads? Unfortunately I'm having trouble reasoning through this myself, so I'd appreciate some clarification.

llvm/test/CodeGen/X86/O0-pipeline.ll

61

Remove pass from name since that's typically the convention.

[sconstab]

Addressed Zola's comments.

[sconstab]

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

271

The comment was incorrect.

[zbrid]

LGTM. I would prefer if an actual LLVM maintainer also gave LGTM. @jyknight, @george.burgess.iv, @craig.topper?

[chandlerc]

llvm/lib/Target/X86/ImmutableGraph.h

47–57

Folks, this isn't even close to following LLVM's coding conventions or naming conventions.

These violate the C++ standard.

This shouldn't have been landed as-is. Can you all back this out and actually dig into the review and get this to match LLVM's actual coding style and standards?

[mattdr]

Adding a few early style notes for the next round, but overall echo @chandlerc that this seems significantly outside of normal LLVM code.

llvm/lib/Target/X86/ImmutableGraph.h

27

It's sort of surprising that the LLVM style guide doesn't call this out explicitly, but #include guards are supposed to include the full file path. If they just used the filename, like, this, files with the same name in different paths would collide.

For an example of the expected style, see an adjacent header in this directory: https://github.com/llvm/llvm-project/blob/ba8b3052b59ebee4311d10bee5209dac8747acea/llvm/lib/Target/X86/X86AsmPrinter.h#L10

319

As a general rule new is a code-smell in modern C++. This should be a vector.

336

this should return a unique_ptr to signal ownership transfer

[craig.topper]

llvm/lib/Target/X86/ImmutableGraph.h

47–57

Reverted at 1d42c0db9a2b27c149c5bac373caa5a6d38d1f74

[craig.topper]

Fix include guard on ImmutableGraph.h

[craig.topper]

Remove underscores from names.

[sconstab]

llvm/lib/Target/X86/ImmutableGraph.h

319

@mattdr I do agree with the general rule. I also think that in this case where the structure is immutable, std::vector is wasteful because it needs to keep separate values for the current number of elements and the current capacity. At local scope within a function the unneeded value would likely be optimized away, but then there would be an awkward handoff to transfer the data from the vector to the array members.

I would not want to see the array members changed to vectors, unless LLVM provides an encapsulated array structure that does not need to grow and shrink.

336

Yes, agree.

[craig.topper]

Use std::unique_ptr for arrays in the graph. I started trying to use std::vector, but it kept crashing. Which initially I thought was some issue with the fact that we store pointers into the vectors in other places and that somehow std::move of the vector was breaking that. I think I now realize its because the array is 1 larger than the real number of nodes and my std::vector version didn't take that into account. But thinking about it more, since we are storing pointers into the array, it probably makes more sense for it to just be a plain array than a vector since resizing a vector would invalidate those pointers. Using an array makes it more clear than we don't resize.

[craig.topper]

Use unique_ptr::operator[] in a few places.

[mattdr]

llvm/lib/Target/X86/ImmutableGraph.h

14

erm, "terrific"? If there's a substantive argument w.r.t. cache locality etc., please make it explicit.

17

"extraordinarily" is, again, not a useful engineering categorization. Please restrict comments to describing quantifiable claims of complexity.

41

Every template argument for a class represents combinatorial addition of complexity for the resulting code. Why do each of these template arguments need to exist? in particular, why does SizeT need to exist?

319

So, first: I'm glad you removed the unnecessary use of new[] here and the corresponding (and error-prone!) use of delete[] later. That removes a memory leak LLVM won't have to debug.

You suggest here that something other than std::vector would be more efficient. If so, would std::array suffice? If not, can you explain why static allocation is impossible but dynamic allocation would be too expensive?

[craig.topper]

-Add edge_begin()/edge_end()/edges() to Node class. Hides the N+1 trick used to find the end of a Node's edges.
-Add nodes()/edges() and use range-based for loops.
-Stop using things in the traits class since it doesn't have range-based for loops.
-Const-correct as required since nodes()/edges() return an ArrayRef that ends up making the range for loops const.
-Use llvm::for_each instead of std::for_each.
-Rename Node::value()/Edge::value() to getValue() to align with llvm naming convention.

[sconstab]

llvm/lib/Target/X86/ImmutableGraph.h

14

This is valid. I will reword.

17

AFAIK there is not a precise engineering term for "tiny O(1)." Nonetheless I will reword.

41

I suspect that there may be more uses for this data structure and that eventually it may migrate to ADT. I have SizeT as a template argument because I found it plenty sufficient to have int as the size parameter for the array bounds, but I suspect other uses may require size_t.

319

A statically sized array (e.g., std::array) is insufficient because the size in this case is not compiler determinable; a dynamically sized and dynamically resizable array (e.g., std::vector) is sufficient but overly costly; a dynamically sized and dynamically unresizable array is sufficient and has minimal cost.

[sconstab]

llvm/lib/Target/X86/ImmutableGraph.h

286

@craig.topper It now occurs to me that these fields should probably be reordered to:

std::unique_ptr<Node[]> Nodes;
std::unique_ptr<Edge[]> Edges;
size_type NodesSize;
size_type EdgesSize;

The current ordering will cause internal fragmentation.

Old ordering:

static_assert(sizeof(ImmutableGraph<T, V>) == 32);

New ordering:

static_assert(sizeof(ImmutableGraph<T, V>) == 24);

With vectors instead of arrays:

static_assert(sizeof(ImmutableGraph<T, V>) == 48);

[sconstab]

Overall, the restyling by @craig.topper looks much better than what I had committed before. I agree that std::unique_ptr<T *> is the right "container" in this circumstance. And the addition of ArrayRef<> accessors is also a nice touch. A few extra inline comments.

llvm/lib/Target/X86/ImmutableGraph.h

14

"Iteration and traversal operations benefit from cache locality."

17

"Operations on sets of nodes/edges are efficient, and representations of those sets in memory are compact. For instance..."

85

After the members are reordered, this list must also be reordered.

104

This had not occurred to me until now, but a lot of code is shared between NodeSet and EdgeSet. Maybe a template could reduce the redundancy?

[sconstab]

llvm/lib/Target/X86/ImmutableGraph.h

308

Just noticed that ImmutableGraphBuilder and ImmutableGraph have non-identical types called NodeRef. Suggest renaming this one to BuilderNodeRef.

[craig.topper]

llvm/lib/Target/X86/ImmutableGraph.h

286

I noticed that too. I just didn't focus on it since we only ever one in memory at a time. I'll change in my next update.

308

NodeRef is in the Traits class not the ImmutableGraph, but I will rename the builder one.

[craig.topper]

llvm/lib/Target/X86/ImmutableGraph.h

330

Can this be changed to VI < VertexSize?

370

I think I'll change this to llvm::count_if. Also there was previously a conditional here that made sure the distance between edges was >0, but it didn't seem necessary. Please let me know if there's a reason I should put that back

[craig.topper]

-Apply updates to comments.
-Use nodes()/edges() to implement nodes_begin/end and edges_begin/end to simplify the code a little
-Reorder fields in the Graph class.

[craig.topper]

-Add methods to get the index of a Node or Edge to remove calls to std::distance in various places

[mattdr]

llvm/lib/Target/X86/ImmutableGraph.h

18

"spatial"

42

I think this self-reference to ImmutableGraph dropped the SizeT parameter.

74

Seems like you also want to add a comment here that we know we will never be asked for edges_end for the last stored node -- that is, we know that this + 1 always refers to a valid Node (which is presumably a dummy/sentinel)

80

Why "protected" rather than "private"? Usually seeing "protected" makes me think subclassing is expected, but that doesn't seem to be the case here.

118

How do we know that a value of size_type (aka SizeT) can be cast to unsigned without truncation?

299

this will also break if a non-default SizeT is provided. Maybe a good argument to just leave out SizeT for now, and it can be added in the future as needed?

319

I'm not sure we allocate enough of these in the course of a compilation for the one extra word in a std::vector to matter, but I won't press the point.

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

114

Cleaner how?

234

If the user requests hardening and we can't do it, it seems better to fail loudly so they don't accidentally deploy an unmitigated binary.

[sconstab]

Summary points for @craig.topper who has commandeered this diff:

• fix the typo that Matt pointed out
• SizeT should not be a template parameter, and size_type should be fixed to int.
• Maybe have a member reference in MachineGadgetGraph to the associated MachineFunction.
• Determine how this pass (and other X86 machine passes) should fail on unsupported X86 subtargets.

llvm/lib/Target/X86/ImmutableGraph.h

42

Yup. Good catch.

74

Not sure I agree. I cannot think of a conventional use of this interface that would perform an operation on the sentinel.

G->nodes_end().edges_end(); // invalid use of any end iterator
SomeNode.edges_end(); // invalid if SomeNode == G->nodes_end()

That is, the way that we "know" that we will never be asked for edges_end() for the last stored node is that the ask itself would already violate C++ conventions.

80

The MachineGadgetGraph class actually does subclass ImmutableGraph to add some contextual information. I did not want the constructors for ImmutableGraph to be public, because the intent is to use the builder. So protected seemed like the best option.

118

Ah. We do not know that. We could have a static assert here, but maybe the best thing to do would be to follow Matt's earlier advice and fix size_type to int, rather than have it as a template parameter. Anything larger would break the BitVectors and/or waste space.

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

114

Maybe by keeping a member reference to the associated MachineFunction?

234

@craig.topper I think this is related to the discussion we were having about what would happen for SLH on unsupported subtargets. I'm not sure what the most appropriate solution would be.

[mattdr]

Some more comments. FWIW, I'm doing rounds of review as I can in some evening quiet or during my son's nap. This is a huge change and it's really hard to get any part of it into my head at once in a reasonable amount of time.

llvm/lib/Target/X86/ImmutableGraph.h

74

I believe any operation on the last Node in the array will end up accessing the sentinel:

Node* LastNode = G->nodes_begin() + (G->nodes_size() - 1);  // valid reference to the last node
LastNode->edges_end();  // uses `this+1`, accessing the sentinel value in the Nodes array

80

Ah, I missed that. I searched through the file for public ImmutableGraph and didn't find it because MachineGadgetGraph uses the default inheritance specifier.

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

84–86

Please replace these with constants or functions.

114

Let's put that in the comment instead.

[mattdr]

I'll wait for current comments to be addressed before doing my next round here.

[sconstab]

llvm/lib/Target/X86/ImmutableGraph.h

74

G->nodes_size() will return the size without the sentinel node, so your example should actually operate on the last data node. Right?

[craig.topper]

Address review comments

[craig.topper]

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

84–86

Oops forgot to do this one.

[craig.topper]

llvm/lib/Target/X86/ImmutableGraph.h

42

Removed the template argument

74

Comment added to clarify the extra node was allocated.

118

Removed the template argument

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

114

I found a way to remove the getMF method entirely.

234

Added a fatal error. Which isn't great as it will generate a crash report in clang. But it will tell the user to file a compiler bug so I guess that's something.

[craig.topper]

-Replace ARG_NODE and GADGET_EDGE defines with static constexpr members

[craig.topper]

-Put llvm:: on the for_each calls in this patch instead of D75937

[sconstab]

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

234

Would it be better to have

report_fatal_error("LVI load hardening is only supported on 64-bit "
                   "targets.", false);

So that the crash diagnostic is not generated?

[mattdr]

@craig.topper can you please update/rebase this stack to remove the early LVI CFI work that ended up landed in https://reviews.llvm.org/D76812 instead?

[mattdr]

Accepting modulo some comments to be addressed. Most of my review effort was spent on the data structure and algorithm employed as well as code style and readability.

I am least confident about my understanding of instrAccessesStackSlot and the other functions that make up instrIsFixedAccess, since each function seems to be pattern-matching on something very specific without a reference to why. I also don't know if this diff provides an exhaustive list of fixed loads, or indeed if it was intended to.

llvm/lib/Target/X86/ImmutableGraph.h

103

Worth adding a comment for this (and getEdgeIndex) that this will crash if the Node (Edge) provided is not a reference into this specific instance of ImmutableGraph.

104

Ideally I agree we'd find a way to collapse these -- but for this diff, let's content ourselves with a FIXME comment to that effect.

341

This if is unnecessary

349

Technically a "generic" graph, so we should leave out "Gadget" here

367

Two comments here would make the code significantly easier to understand:

1. Note that we're using .size() here rather than .count(), so we're actually iterating over *all* Node indices, not just the ones to be trimmed
2. The TrimmedNodes vector maps indices in the original NodeSet to the number of Nodes before that index that have been trimmed by that index, to allow later code to map elements to their new position in a dense array with the trimmed items removed

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

57

This is another case where references to good documentation will go a long way. Without details about what the tradeoff is and how to reason about it, it doesn't seem like anyone should use this flag.

237

Each call to hardenLoads leads to a call to buildGadgetGraph. A *lot* of the work that getGadgetGraph does seems to be common between mitigating fixed and non-fixed loads -- for example, computing register dataflow and liveness over the entire function.

And calling hardenLoads twice looks to be the common case, since NoFixedLoads is false by default.

Could we make this pass about half as expensive by default by combining these two calls to hardenLoads into one? It would do the expensive work once, then either harden _all_ loads or _only_ non-fixed loads.

323

Please add a comment explaining the semantics of the boolean return here. I think it's: true if we need to consider defs of this instruction tainted by this use (and therefore add them for analysis); false if this instruction consumes its use

330

Why is it okay to assume that a call doesn't propagate its uses to defs? Is it because we can assume the CFI transform is already inserting an LFENCE? Whatever the reason, let's state it explicitly here

342

Some more detail would be useful here: precise about what? What are the likely errors?

410

We analyze every def from every instruction in the function, but then also in AnalyzeDefUseChain analyze every def of every instruction with an interesting use. Are we doing a lot of extra work?

494

Worth a comment here that we don't need to worry about indirect branches (jmp to register) because elsewhere we prevent them from being generated

507

It seems very weird to make this a template argument rather than just, like, a regular argument.

[craig.topper]

Address some of the review comments. Primarily the ones in ImmutableGraph. I did de-templatize the method in X86LoadValueInjectionLoadHardening.cpp

[craig.topper]

llvm/lib/Target/X86/ImmutableGraph.h

367

I've stopped using TrimmedNodes.size() and TrimEdges.size() in favor of the size methods from the graph which should make things more obvious.

I renamed TrimmedNodes to RemappedNodeIndex and stored the new index rather than the adjustment needed. I'm also changed it to walk nodes instead of indices so we don't have to translate to Node to make the contains call.

I also removed the NewNumEdges count_if and the if statement around the edge loop from the loop below. I don't think that provided any value and just complicated the code.

llvm/lib/Target/X86/X86ISelLowering.cpp

8626 ↗

(On Diff #257465)

Oops this snuck in from something else I was experimenting with in my repo earlier. I'll remove.

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

507

Agreed. I've remove the template argument and made it a static function instead of a method since it doesn't use anything from the class.

[craig.topper]

Fix some mistakes I made in the previous upload where I accidentally deleted the pipeline tests instead of updating them.

[craig.topper]

Merge in test case from D77431 since it logically belongs with these changes.

[mattdr]

llvm/lib/Target/X86/ImmutableGraph.h

367

Many thanks! These changes make the code much more accessible.

[sconstab]

Removed the -x86-lvi-no-fixed CLI flag. This change simplifies the code flow quite a bit.

[craig.topper]

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

323

Was this comment addressed?

342

Was this answered somewhere?

410

Was this answered somewhere?

[sconstab]

Addressed the previously unaddressed comments, as pointed out by @craig.topper.

[sconstab]

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

323

It had not been addressed, so thank you for pointing this out. That lambda was doing too many things at once, which made it more confusing than it needed to be. So I just inlined it in the

for (auto N : Uses) {
…
}

loop, and I added some additional clarifying comments.

342

This was referring to the use of mayLoad(). At the time I wrote that comment, I wasn't sure that mayLoad() was exactly what was needed there, but I now think that it does suffice (SLH also uses MachineInstr::mayLoad()).

410

Wow, big oversight on my part. @mattdr was correct that this was doing a LOT of extra work. I added a memoization scheme that remembers the instructions that may transmit for each def. The getGadgetGraph() routine now runs about 75% faster.

[mattdr]

Calling special attention to the comment at line 341, since I think it affects the correctness of the pass.

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

288

This comment doesn't seem to match how the map is used -- it looks like the loop assumes a def has been analyzed iff it is present in the map. This matches my expectation that, if a def is present and maps to an empty list, it would meant the def had been analyzed and found not to transmit.

296

fwiw, this code would be easier to understand if we didn't shadow Def with another variable named Def.

322–323

"current def" is a bit ambiguous here. I _believe_ it means AnalyzeDef's Def argument? At least, that's the interpretation that makes the comment make sense since UsesVisited is in AnalyzeDef's scope.

332

Copying a comment from a previous iteration:

Why is it okay to assume that a call doesn't propagate its uses to defs? Is it because we can assume the CFI transform is already inserting an LFENCE? Whatever the reason, let's state it explicitly here

342

The comment doesn't match the loop, which is traversing over Uses. More importantly, though: why are we allowed to stop traversing through Uses here? This Def won't be analyzed again, so this is our only chance to enumerate all transmitters to make sure we have all the necessary source -> sink edges in the gadget graph.

365–366

This is also the place we populate Transmitters (with a default-constructed vector) for the current def if we haven't otherwise found any transmits. That's good, and necessary for Transmitters to remember we've analyzed the current def. But we should leave a comment about this subtle load-bearing side-effect.

367–370

Should Transmitters map to an llvm::SmallSet?

[sconstab]

Addressed comments by @mattdr.

Several comments in the code have been updated, but the code has not changed.

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

296

Changed the outer def to SourceDef, which also seems to make the code after the lambda a lot clearer.

322–323

I am now trying to be clearer by using capital-d "Def" to refer specifically to the def that is being analyzed, and lower-case-d "def" to refer to any other defs. Do you think this is better? Good enough?

332

Added clarification to the comment.

342

@mattdr I think that the code is correct, and I added more to the comment in an attempt to clarify. Let me know if you still think that this is an issue.

367–370

In my testing, std::vector seems a bit faster than llvm::SmallSet. I also suspect that llvm::SmallSet may waste more space because many defs will have no transmitters.

[mattdr]

The extra comments and the new variable name are all helpful. Thanks again.

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

322–323

Much better. Thank you for the change!

342

I definitely misread continue as break here. Thanks for the extra clarity and sorry for the noise.

[nikic]

This change causes a 0.8% compile-time regression for unoptimized builds. Based on the pipeline test diffs, I expect this is because the new pass requests a bunch of analyses, which it most likely (LVI load hardening disabled) will not need. Would it be possible to compute the analyses only if LVI load hardening is actually enabled?

[sconstab]

In D75936#2032027, @nikic wrote:

This change causes a 0.8% compile-time regression for unoptimized builds. Based on the pipeline test diffs, I expect this is because the new pass requests a bunch of analyses, which it most likely (LVI load hardening disabled) will not need. Would it be possible to compute the analyses only if LVI load hardening is actually enabled?

@craig.topper Do you have any ideas on how this could be done?

[craig.topper]

In D75936#2032078, @sconstab wrote:

In D75936#2032027, @nikic wrote:

This change causes a 0.8% compile-time regression for unoptimized builds. Based on the pipeline test diffs, I expect this is because the new pass requests a bunch of analyses, which it most likely (LVI load hardening disabled) will not need. Would it be possible to compute the analyses only if LVI load hardening is actually enabled?

@craig.topper Do you have any ideas on how this could be done?

Unfortunately due to LTO the need for LVI hardening is carried as a function attribute. The pass manager system doesn't allow for running different passes per function. So I don't have any good ideas of how to do that.

[craig.topper]

llvm/test/CodeGen/X86/O3-pipeline.ll

140–144

I'm curious what happens if we add AU.setPreservesCFG() to getAnalysisUsage in FixupStatepointCallerSaved.cpp From a quick look through that pass it doesn't look like it changes the Machine CFG.

PostRA Machine Sink already preserves CFG. So I think that should remove the dominator tree construction after PostRA machine sink.

[mattdr]

I'm no expert in the pass manager, but given the very targeted applicability of LVI it definitely seems like our goal should be 0% impact for the vast majority of compilations that don't concern themselves with it.

Is there a way to require the pass be enabled for the compiler invocation as well as for the subtarget? If there's a mismatch (where LVI is desired but the required analyses weren't done) we can fail the compile.

[nikic]

In D75936#2032090, @craig.topper wrote:

In D75936#2032078, @sconstab wrote:

In D75936#2032027, @nikic wrote:

This change causes a 0.8% compile-time regression for unoptimized builds. Based on the pipeline test diffs, I expect this is because the new pass requests a bunch of analyses, which it most likely (LVI load hardening disabled) will not need. Would it be possible to compute the analyses only if LVI load hardening is actually enabled?

@craig.topper Do you have any ideas on how this could be done?

Unfortunately due to LTO the need for LVI hardening is carried as a function attribute. The pass manager system doesn't allow for running different passes per function. So I don't have any good ideas of how to do that.

Hm, I see. One possibility would be to make those analyses lazy, but that's a larger change.

Possibly a pragmatic choice would be to not support this feature at O0? It does not seem relevant for non-production binaries. The relative impact of a couple unnecessary analysis passes is much higher at O0 than it is at O3.

clang/include/clang/Driver/Options.td

 def mno_stackrealign : Flag<["-"], "mno-stackrealign">, Group<m_Group>;
 
 def mretpoline : Flag<["-"], "mretpoline">, Group<m_Group>, Flags<[CoreOption,DriverOption]>;
 def mno_retpoline : Flag<["-"], "mno-retpoline">, Group<m_Group>, Flags<[CoreOption,DriverOption]>;
 def mspeculative_load_hardening : Flag<["-"], "mspeculative-load-hardening">,
   Group<m_Group>, Flags<[CoreOption,CC1Option]>;
 def mno_speculative_load_hardening : Flag<["-"], "mno-speculative-load-hardening">,
   Group<m_Group>, Flags<[CoreOption]>;
+def mlvi_hardening : Flag<["-"], "mlvi-hardening">, Group<m_Group>, Flags<[CoreOption,DriverOption]>,
+  HelpText<"Enable all mitigations for Load Value Injection (LVI)">;
+def mno_lvi_hardening : Flag<["-"], "mno-lvi-hardening">, Group<m_Group>, Flags<[CoreOption,DriverOption]>,
+  HelpText<"Disable mitigations for Load Value Injection (LVI)">;
 def mlvi_cfi : Flag<["-"], "mlvi-cfi">, Group<m_Group>, Flags<[CoreOption,DriverOption]>,
   HelpText<"Enable only control-flow mitigations for Load Value Injection (LVI)">;
 def mno_lvi_cfi : Flag<["-"], "mno-lvi-cfi">, Group<m_Group>, Flags<[CoreOption,DriverOption]>,
   HelpText<"Disable control-flow mitigations for Load Value Injection (LVI)">;
 
 def mrelax : Flag<["-"], "mrelax">, Group<m_riscv_Features_Group>,
   HelpText<"Enable linker relaxation">;
 def mno_relax : Flag<["-"], "mno-relax">, Group<m_riscv_Features_Group>,

clang/lib/Driver/ToolChains/Arch/X86.cpp

if (Args.hasArgNoClaim(options::OPT_mretpoline, options::OPT_mno_retpoline,
     // FIXME: Add a warning about failing to specify `-mretpoline` and
     // eventually switch to an error here.
     Features.push_back("+retpoline-indirect-calls");
     Features.push_back("+retpoline-indirect-branches");
     SpectreOpt = options::OPT_mretpoline_external_thunk;
   }
 
   auto LVIOpt = clang::driver::options::ID::OPT_INVALID;
-  if (Args.hasFlag(options::OPT_mlvi_cfi, options::OPT_mno_lvi_cfi, false)) {
+  if (Args.hasFlag(options::OPT_mlvi_hardening, options::OPT_mno_lvi_hardening,
+                   false)) {
+    Features.push_back("+lvi-load-hardening");
+    Features.push_back("+lvi-cfi"); // load hardening implies CFI protection
+    LVIOpt = options::OPT_mlvi_hardening;
+  } else if (Args.hasFlag(options::OPT_mlvi_cfi, options::OPT_mno_lvi_cfi,
+                          false)) {
     Features.push_back("+lvi-cfi");
     LVIOpt = options::OPT_mlvi_cfi;
   }
 
   if (SpectreOpt != clang::driver::options::ID::OPT_INVALID &&
       LVIOpt != clang::driver::options::ID::OPT_INVALID) {
     D.Diag(diag::err_drv_argument_not_allowed_with)
         << D.getOpts().getOptionName(SpectreOpt)
         << D.getOpts().getOptionName(LVIOpt);
   }
 
   // Now add any that the user explicitly requested on the command line,
   // which may override the defaults.
   handleTargetFeaturesGroup(Args, Features, options::OPT_m_x86_Features_Group);
 }

llvm/lib/Target/X86/CMakeLists.txt

set(sources
   X86InterleavedAccess.cpp
   X86InsertPrefetch.cpp
   X86InstrFMA3Info.cpp
   X86InstrFoldTables.cpp
   X86InstrInfo.cpp
   X86EvexToVex.cpp
   X86LegalizerInfo.cpp
   X86LoadValueInjectionIndirectThunks.cpp
+  X86LoadValueInjectionLoadHardening.cpp
   X86LoadValueInjectionRetHardening.cpp
   X86MCInstLower.cpp
   X86MachineFunctionInfo.cpp
   X86MacroFusion.cpp
   X86OptimizeLEAs.cpp
   X86PadShortFunction.cpp
   X86RegisterBankInfo.cpp
   X86RegisterInfo.cpp

llvm/lib/Target/X86/ImmutableGraph.h

+//==========-- ImmutableGraph.h - A fast DAG implementation ---------=========//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef IMMUTABLEGRAPH_H
+#define IMMUTABLEGRAPH_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <iterator>
+#include <utility>
+#include <vector>
+
+namespace llvm {
+
+template <typename _NodeValueT, typename _EdgeValueT, typename _SizeT = int>
+class ImmutableGraph {
+  using Traits = GraphTraits<ImmutableGraph<_NodeValueT, _EdgeValueT> *>;
+  template <typename> friend class ImmutableGraphBuilder;
+
+public:
+  using NodeValueT = _NodeValueT;
+  using EdgeValueT = _EdgeValueT;
+  using size_type = _SizeT;
+  class Node;
+  class Edge {
+    friend class ImmutableGraph;
+    template <typename> friend class ImmutableGraphBuilder;
+    friend Traits;
+
+    Node *__dest;
+    EdgeValueT __value;
+
+  public:
+    EdgeValueT &value() { return __value; }
+  };
+  class Node {
+    friend class ImmutableGraph;
+    template <typename> friend class ImmutableGraphBuilder;
+    friend Traits;
+
+    Edge *__edges;
+    NodeValueT __value;
+
+  public:
+    NodeValueT &value() { return __value; }
+  };
+
+protected:
+  ImmutableGraph(Node *Nodes, size_type NodesSize, Edge *Edges,
+                 size_type EdgesSize)
+      : __nodes{Nodes}, __nodes_size{NodesSize}, __edges{Edges},
+        __edges_size{EdgesSize} {}
+  ImmutableGraph(const ImmutableGraph &) = delete;
+  ImmutableGraph(ImmutableGraph &&) = delete;
+  ImmutableGraph &operator=(const ImmutableGraph &) = delete;
+  ImmutableGraph &operator=(ImmutableGraph &&) = delete;
+
+public:
+  ~ImmutableGraph() {
+    delete[] __edges;
+    delete[] __nodes;
+  }
+
+  Node *nodes_begin() const { return __nodes; }
+  Node *nodes_end() const { return __nodes + __nodes_size; }
+  Edge *edges_begin() const { return __edges; }
+  Edge *edges_end() const { return __edges + __edges_size; }
+  size_type nodes_size() const { return __nodes_size; }
+  size_type edges_size() const { return __edges_size; }
+  bool empty() const { return __nodes_size == 0; }
+
+  class NodeSet {
+    friend class iterator;
+
+    const ImmutableGraph &__g;
+    BitVector __v;
+
+  public:
+    NodeSet(const ImmutableGraph &G, bool ContainsAll = false)
+        : __g{G}, __v{static_cast<unsigned>(__g.nodes_size()), ContainsAll} {}
+    bool insert(Node *N) {
+      size_type Idx = std::distance(__g.nodes_begin(), N);
+      bool AlreadyExists = __v.test(Idx);
+      __v.set(Idx);
+      return !AlreadyExists;
+    }
+    void erase(Node *N) {
+      size_type Idx = std::distance(__g.nodes_begin(), N);
+      __v.reset(Idx);
+    }
+    bool contains(Node *N) const {
+      size_type Idx = std::distance(__g.nodes_begin(), N);
+      return __v.test(Idx);
+    }
+    void clear() { __v.reset(); }
+    size_type empty() const { return __v.none(); }
+    /// Return the number of elements in the set
+    size_type count() const { return __v.count(); }
+    /// Return the size of the set's domain
+    size_type size() const { return __v.size(); }
+    /// Set union
+    NodeSet &operator|=(const NodeSet &RHS) {
+      assert(&this->__g == &RHS.__g);
+      __v |= RHS.__v;
+      return *this;
+    }
+    /// Set intersection
+    NodeSet &operator&=(const NodeSet &RHS) {
+      assert(&this->__g == &RHS.__g);
+      __v &= RHS.__v;
+      return *this;
+    }
+    /// Set disjoint union
+    NodeSet &operator^=(const NodeSet &RHS) {
+      assert(&this->__g == &RHS.__g);
+      __v ^= RHS.__v;
+      return *this;
+    }
+
+    using index_iterator = typename BitVector::const_set_bits_iterator;
+    index_iterator index_begin() const { return __v.set_bits_begin(); }
+    index_iterator index_end() const { return __v.set_bits_end(); }
+    void set(size_type Idx) { __v.set(Idx); }
+    void reset(size_type Idx) { __v.reset(Idx); }
+
+    class iterator {
+      const NodeSet &__set;
+      size_type __current;
+
+      void advance() {
+        assert(__current != -1);
+        __current = __set.__v.find_next(__current);
+      }
+
+    public:
+      iterator(const NodeSet &Set, size_type Begin)
+          : __set{Set}, __current{Begin} {}
+      iterator operator++(int) {
+        iterator Tmp = *this;
+        advance();
+        return Tmp;
+      }
+      iterator &operator++() {
+        advance();
+        return *this;
+      }
+      Node *operator*() const {
+        assert(__current != -1);
+        return __set.__g.nodes_begin() + __current;
+      }
+      bool operator==(const iterator &other) const {
+        assert(&this->__set == &other.__set);
+        return this->__current == other.__current;
+      }
+      bool operator!=(const iterator &other) const { return !(*this == other); }
+    };
+
+    iterator begin() const { return iterator{*this, __v.find_first()}; }
+    iterator end() const { return iterator{*this, -1}; }
+  };
+
+  class EdgeSet {
+    const ImmutableGraph &__g;
+    BitVector __v;
+
+  public:
+    EdgeSet(const ImmutableGraph &G, bool ContainsAll = false)
+        : __g{G}, __v{static_cast<unsigned>(__g.edges_size()), ContainsAll} {}
+    bool insert(Edge *E) {
+      size_type Idx = std::distance(__g.edges_begin(), E);
+      bool AlreadyExists = __v.test(Idx);
+      __v.set(Idx);
+      return !AlreadyExists;
+    }
+    void erase(Edge *E) {
+      size_type Idx = std::distance(__g.edges_begin(), E);
+      __v.reset(Idx);
+    }
+    bool contains(Edge *E) const {
+      size_type Idx = std::distance(__g.edges_begin(), E);
+      return __v.test(Idx);
+    }
+    void clear() { __v.reset(); }
+    bool empty() const { return __v.none(); }
+    /// Return the number of elements in the set
+    size_type count() const { return __v.count(); }
+    /// Return the size of the set's domain
+    size_type size() const { return __v.size(); }
+    /// Set union
+    EdgeSet &operator|=(const EdgeSet &RHS) {
+      assert(&this->__g == &RHS.__g);
+      __v |= RHS.__v;
+      return *this;
+    }
+    /// Set intersection
+    EdgeSet &operator&=(const EdgeSet &RHS) {
+      assert(&this->__g == &RHS.__g);
+      __v &= RHS.__v;
+      return *this;
+    }
+    /// Set disjoint union
+    EdgeSet &operator^=(const EdgeSet &RHS) {
+      assert(&this->__g == &RHS.__g);
+      __v ^= RHS.__v;
+      return *this;
+    }
+
+    using index_iterator = typename BitVector::const_set_bits_iterator;
+    index_iterator index_begin() const { return __v.set_bits_begin(); }
+    index_iterator index_end() const { return __v.set_bits_end(); }
+    void set(size_type Idx) { __v.set(Idx); }
+    void reset(size_type Idx) { __v.reset(Idx); }
+
+    class iterator {
+      const EdgeSet &__set;
+      size_type __current;
+
+      void advance() {
+        assert(__current != -1);
+        __current = __set.__v.find_next(__current);
+      }
+
+    public:
+      iterator(const EdgeSet &Set, size_type Begin)
+          : __set{Set}, __current{Begin} {}
+      iterator operator++(int) {
+        iterator Tmp = *this;
+        advance();
+        return Tmp;
+      }
+      iterator &operator++() {
+        advance();
+        return *this;
+      }
+      Edge *operator*() const {
+        assert(__current != -1);
+        return __set.__g.edges_begin() + __current;
+      }
+      bool operator==(const iterator &other) const {
+        assert(&this->__set == &other.__set);
+        return this->__current == other.__current;
+      }
+      bool operator!=(const iterator &other) const { return !(*this == other); }
+    };
+
+    iterator begin() const { return iterator{*this, __v.find_first()}; }
+    iterator end() const { return iterator{*this, -1}; }
+  };
+
+private:
+  Node *__nodes;
+  size_type __nodes_size;
+  Edge *__edges;
+  size_type __edges_size;
+};
+
+template <typename GraphT> class ImmutableGraphBuilder {
+  using NodeValueT = typename GraphT::NodeValueT;
+  using EdgeValueT = typename GraphT::EdgeValueT;
+  static_assert(
+      std::is_base_of<ImmutableGraph<NodeValueT, EdgeValueT>, GraphT>::value,
+      "Template argument to ImmutableGraphBuilder must derive from "
+      "ImmutableGraph<>");
+  using size_type = typename GraphT::size_type;
+  using NodeSet = typename GraphT::NodeSet;
+  using Node = typename GraphT::Node;
+  using EdgeSet = typename GraphT::EdgeSet;
+  using Edge = typename GraphT::Edge;
+  using BuilderEdge = std::pair<EdgeValueT, size_type>;
+  using EdgeList = std::vector<BuilderEdge>;
+  using BuilderVertex = std::pair<NodeValueT, EdgeList>;
+  using VertexVec = std::vector<BuilderVertex>;
+
+public:
+  using NodeRef = size_type;
+
+  NodeRef addVertex(const NodeValueT &V) {
+    auto I = __adj_list.emplace(__adj_list.end(), V, EdgeList{});
+    return std::distance(__adj_list.begin(), I);
+  }
+
+  void addEdge(const EdgeValueT &E, NodeRef From, NodeRef To) {
+    __adj_list[From].second.emplace_back(E, To);
+  }
+
+  bool empty() const { return __adj_list.empty(); }
+
+  template <typename... ArgT> GraphT *get(ArgT &&... Args) {
+    size_type VertexSize = __adj_list.size(), EdgeSize = 0;
+    for (const auto &V : __adj_list) {
+      EdgeSize += V.second.size();
+    }
+    auto *VertexArray = new Node[VertexSize + 1 /* terminator node */];
+    auto *EdgeArray = new Edge[EdgeSize];
+    size_type VI = 0, EI = 0;
+    for (; VI < static_cast<size_type>(__adj_list.size()); ++VI) {
+      VertexArray[VI].__value = std::move(__adj_list[VI].first);
+      VertexArray[VI].__edges = &EdgeArray[EI];
+      auto NumEdges = static_cast<size_type>(__adj_list[VI].second.size());
+      if (NumEdges > 0) {
+        for (size_type VEI = 0; VEI < NumEdges; ++VEI, ++EI) {
+          auto &E = __adj_list[VI].second[VEI];
+          EdgeArray[EI].__value = std::move(E.first);
+          EdgeArray[EI].__dest = VertexArray + E.second;
+        }
+      }
+    }
+    assert(VI == VertexSize && EI == EdgeSize && "Gadget graph malformed");
+    VertexArray[VI].__edges = EdgeArray + EdgeSize; // terminator node
+    return new GraphT{VertexArray, VertexSize, EdgeArray, EdgeSize,
+                      std::forward<ArgT>(Args)...};
+  }
+
+  template <typename... ArgT>
+  static GraphT *trim(const GraphT &G, const NodeSet &TrimNodes,
+                      const EdgeSet &TrimEdges, ArgT &&... Args) {
+    size_type NewVertexSize = TrimNodes.size() - TrimNodes.count();
+    size_type NewEdgeSize = TrimEdges.size() - TrimEdges.count();
+    auto *NewVertexArray = new Node[NewVertexSize + 1 /* terminator node */];
+    auto *NewEdgeArray = new Edge[NewEdgeSize];
+    size_type TrimmedNodesSoFar = 0,
+              *TrimmedNodes = new size_type[TrimNodes.size()];
+    for (size_type I = 0; I < TrimNodes.size(); ++I) {
+      TrimmedNodes[I] = TrimmedNodesSoFar;
+      if (TrimNodes.contains(G.nodes_begin() + I))
+        ++TrimmedNodesSoFar;
+    }
+    size_type VertexI = 0, EdgeI = 0;
+    for (Node *NI = G.nodes_begin(), *NE = G.nodes_end(); NI != NE; ++NI) {
+      if (TrimNodes.contains(NI))
+        continue;
+      size_type NewNumEdges =
+          static_cast<int>((NI + 1)->__edges - NI->__edges) > 0
+              ? std::count_if(
+                    NI->__edges, (NI + 1)->__edges,
+                    [&TrimEdges](Edge &E) { return !TrimEdges.contains(&E); })
+              : 0;
+      NewVertexArray[VertexI].__value = NI->__value;
+      NewVertexArray[VertexI].__edges = &NewEdgeArray[EdgeI];
+      if (NewNumEdges > 0) {
+        for (Edge *EI = NI->__edges, *EE = (NI + 1)->__edges; EI != EE; ++EI) {
+          if (TrimEdges.contains(EI))
+            continue;
+          NewEdgeArray[EdgeI].__value = EI->__value;
+          size_type DestIdx = std::distance(G.nodes_begin(), EI->__dest);
+          size_type NewIdx = DestIdx - TrimmedNodes[DestIdx];
+          assert(NewIdx < NewVertexSize);
+          NewEdgeArray[EdgeI].__dest = NewVertexArray + NewIdx;
+          ++EdgeI;
+        }
+      }
+      ++VertexI;
+    }
+    delete[] TrimmedNodes;
+    assert(VertexI == NewVertexSize && EdgeI == NewEdgeSize &&
+           "Gadget graph malformed");
+    NewVertexArray[VertexI].__edges = NewEdgeArray + NewEdgeSize;
+    return new GraphT{NewVertexArray, NewVertexSize, NewEdgeArray, NewEdgeSize,
+                      std::forward<ArgT>(Args)...};
+  }
+
+private:
+  VertexVec __adj_list;
+};
+
+template <typename NodeValueT, typename EdgeValueT>
+struct GraphTraits<ImmutableGraph<NodeValueT, EdgeValueT> *> {
+  using GraphT = ImmutableGraph<NodeValueT, EdgeValueT>;
+  using NodeRef = typename GraphT::Node *;
+  using EdgeRef = typename GraphT::Edge &;
+
+  static NodeRef edge_dest(EdgeRef E) { return E.__dest; }
+  using ChildIteratorType =
+      mapped_iterator<typename GraphT::Edge *, decltype(&edge_dest)>;
+
+  static NodeRef getEntryNode(GraphT *G) { return G->nodes_begin(); }
+  static ChildIteratorType child_begin(NodeRef N) {
+    return {N->__edges, &edge_dest};
+  }
+  static ChildIteratorType child_end(NodeRef N) {
+    return {(N + 1)->__edges, &edge_dest};
+  }
+
+  static NodeRef getNode(typename GraphT::Node &N) { return NodeRef{&N}; }
+  using nodes_iterator =
+      mapped_iterator<typename GraphT::Node *, decltype(&getNode)>;
+  static nodes_iterator nodes_begin(GraphT *G) {
+    return {G->nodes_begin(), &getNode};
+  }
+  static nodes_iterator nodes_end(GraphT *G) {
+    return {G->nodes_end(), &getNode};
+  }
+
+  using ChildEdgeIteratorType = typename GraphT::Edge *;
+
+  static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
+    return N->__edges;
+  }
+  static ChildEdgeIteratorType child_edge_end(NodeRef N) {
+    return (N + 1)->__edges;
+  }
+  static typename GraphT::size_type size(GraphT *G) { return G->nodes_size(); }
+};
+
+} // end namespace llvm
+
+#endif // IMMUTABLEGRAPH_H

llvm/lib/Target/X86/X86.h

 /// fp exceptions when strict-fp enabled.
 FunctionPass *createX86InsertX87waitPass();
 
 InstructionSelector *createX86InstructionSelector(const X86TargetMachine &TM,
                                                   X86Subtarget &,
                                                   X86RegisterBankInfo &);
 
 FunctionPass *createX86LoadValueInjectionIndirectThunksPass();
+FunctionPass *createX86LoadValueInjectionLoadHardeningPass();
 FunctionPass *createX86LoadValueInjectionRetHardeningPass();
 FunctionPass *createX86SpeculativeLoadHardeningPass();
 
 void initializeEvexToVexInstPassPass(PassRegistry &);
 void initializeFixupBWInstPassPass(PassRegistry &);
 void initializeFixupLEAPassPass(PassRegistry &);
 void initializeFPSPass(PassRegistry &);
 void initializeWinEHStatePassPass(PassRegistry &);
 void initializeX86AvoidSFBPassPass(PassRegistry &);
 void initializeX86CallFrameOptimizationPass(PassRegistry &);
 void initializeX86CmovConverterPassPass(PassRegistry &);
 void initializeX86CondBrFoldingPassPass(PassRegistry &);
 void initializeX86DomainReassignmentPass(PassRegistry &);
 void initializeX86ExecutionDomainFixPass(PassRegistry &);
 void initializeX86ExpandPseudoPass(PassRegistry &);
 void initializeX86FlagsCopyLoweringPassPass(PassRegistry &);
 void initializeX86LoadValueInjectionIndirectThunksPassPass(PassRegistry &);
+void initializeX86LoadValueInjectionLoadHardeningPassPass(PassRegistry &);
 void initializeX86LoadValueInjectionRetHardeningPassPass(PassRegistry &);
 void initializeX86OptimizeLEAPassPass(PassRegistry &);
 void initializeX86SpeculativeLoadHardeningPassPass(PassRegistry &);
 
 namespace X86AS {
 enum : unsigned {
   GS = 256,
   FS = 257,

llvm/lib/Target/X86/X86.td

 def FeatureLVIControlFlowIntegrity
     : SubtargetFeature<
           "lvi-cfi", "UseLVIControlFlowIntegrity", "true",
           "Prevent indirect calls/branches from using a memory operand, and "
           "precede all indirect calls/branches from a register with an "
           "LFENCE instruction to serialize control flow. Also decompose RET "
           "instructions into a POP+LFENCE+JMP sequence.">;
 
+// Mitigate LVI attacks against data loads
+def FeatureLVILoadHardening
+    : SubtargetFeature<
+          "lvi-load-hardening", "UseLVILoadHardening", "true",
+          "Insert LFENCE instructions to prevent data speculatively injected "
+          "into loads from being used maliciously.">;
+
 // Direct Move instructions.
 def FeatureMOVDIRI  : SubtargetFeature<"movdiri", "HasMOVDIRI", "true",
                                        "Support movdiri instruction">;
 def FeatureMOVDIR64B : SubtargetFeature<"movdir64b", "HasMOVDIR64B", "true",
                                         "Support movdir64b instruction">;
 
 def FeatureFastBEXTR : SubtargetFeature<"fast-bextr", "HasFastBEXTR", "true",
           "Indicates that the BEXTR instruction is implemented as a single uop "

llvm/lib/Target/X86/X86LoadValueInjectionLoadHardening.cpp

+//==-- X86LoadValueInjectionLoadHardening.cpp - LVI load hardening for x86 --=//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// Description: This pass finds Load Value Injection (LVI) gadgets consisting
+/// of a load from memory (i.e., SOURCE), and any operation that may transmit
+/// the value loaded from memory over a covert channel, or use the value loaded
+/// from memory to determine a branch/call target (i.e., SINK).
+///
+/// For performance purposes, this pass uses a custom data structure to
+/// implement the GadgetGraph: ImmutableGraph. As the name suggests, an
+/// ImmutableGraph cannot be modified, except by creating a new ImmutableGraph.
+/// ImmutableGraph is implemented as two arrays: one containing nodes, and one
+/// containing edges. The advantages to this implementation are two-fold:
+/// 1. Iteration and traversal operations should experience terrific caching
+///    performance.
+/// 2. Set representations and operations on nodes and edges become
+///    extraordinarily efficient. For instance, a set of edges is implemented as
+///    an llvm::BitVector, wherein each bit corresponds to one edge in the edge
+///    array. This implies a lower bound of 64x spacial improvement over, e.g.,
+///    an llvm::DenseSet or llvm::SmallSet. It also means that
+///    insert/erase/contains operations complete in negligible constant time:
+///    insert and erase require one load and one store, and contains requires
+///    just one load.
+///
+//===----------------------------------------------------------------------===//
+
+#include "ImmutableGraph.h"
+#include "X86.h"
+#include "X86Subtarget.h"
+#include "X86TargetMachine.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineDominanceFrontier.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/RDFGraph.h"
+#include "llvm/CodeGen/RDFLiveness.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/DOTGraphTraits.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/GraphWriter.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+#define PASS_KEY "x86-lvi-load"
+#define DEBUG_TYPE PASS_KEY
+
+STATISTIC(NumFunctionsConsidered, "Number of functions analyzed");
+STATISTIC(NumFunctionsMitigated, "Number of functions for which mitigations "
+                                 "were deployed");
+STATISTIC(NumGadgets, "Number of LVI gadgets detected during analysis");
+
+static cl::opt<bool> NoConditionalBranches(
+    PASS_KEY "-no-cbranch",
+    cl::desc("Don't treat conditional branches as disclosure gadgets. This "
+             "may improve performance, at the cost of security."),
+    cl::init(false), cl::Hidden);
+
+static cl::opt<bool> EmitDot(
+    PASS_KEY "-dot",
+    cl::desc(
+        "For each function, emit a dot graph depicting potential LVI gadgets"),
+    cl::init(false), cl::Hidden);
+
+static cl::opt<bool> EmitDotOnly(
+    PASS_KEY "-dot-only",
+    cl::desc("For each function, emit a dot graph depicting potential LVI "
+             "gadgets, and do not insert any fences"),
+    cl::init(false), cl::Hidden);
+
+static cl::opt<bool> EmitDotVerify(
+    PASS_KEY "-dot-verify",
+    cl::desc("For each function, emit a dot graph to stdout depicting "
+             "potential LVI gadgets, used for testing purposes only"),
+    cl::init(false), cl::Hidden);
+
+static cl::opt<bool> NoFixedLoads(
+    PASS_KEY "-no-fixed",
+    cl::desc("Don't mitigate RIP-relative or RSP-relative loads. This "
+             "may improve performance, at the cost of security."),
+    cl::init(false), cl::Hidden);
+
+#define ARG_NODE nullptr
+#define GADGET_EDGE ((int)(-1))
+#define WEIGHT(EdgeValue) ((double)(2 * (EdgeValue) + 1))
+
+namespace {
+
+class X86LoadValueInjectionLoadHardeningPass : public MachineFunctionPass {
+public:
+  X86LoadValueInjectionLoadHardeningPass() : MachineFunctionPass(ID) {}
+
+  StringRef getPassName() const override {
+    return "X86 Load Value Injection (LVI) Load Hardening Pass";
+  }
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  static char ID;
+
+private:
+  struct MachineGadgetGraph : ImmutableGraph<MachineInstr *, int> {
+    using GraphT = ImmutableGraph<MachineInstr *, int>;
+    using Node = typename GraphT::Node;
+    using Edge = typename GraphT::Edge;
+    using size_type = typename GraphT::size_type;
+    MachineGadgetGraph(Node *Nodes, size_type NodesSize, Edge *Edges,
+                       size_type EdgesSize, int NumFences = 0,
+                       int NumGadgets = 0)
+        : GraphT{Nodes, NodesSize, Edges, EdgesSize}, NumFences{NumFences},
+          NumGadgets{NumGadgets} {}
+    MachineFunction &getMF() { // FIXME: This function should be cleaner
+      for (Node *NI = nodes_begin(), *const NE = nodes_end(); NI != NE; ++NI) {
+        if (NI->value()) {
+          return *NI->value()->getMF();
+        }
+      }
+      llvm_unreachable("Could not find a valid node");
+    }
+    static inline bool isCFGEdge(Edge &E) { return E.value() != GADGET_EDGE; }
+    static inline bool isGadgetEdge(Edge &E) {
+      return E.value() == GADGET_EDGE;
+    }
+    int NumFences;
+    int NumGadgets;
+  };
+  friend struct llvm::DOTGraphTraits<MachineGadgetGraph *>;
+  using GTraits = llvm::GraphTraits<MachineGadgetGraph *>;
+  using GraphBuilder = ImmutableGraphBuilder<MachineGadgetGraph>;
+  using EdgeSet = MachineGadgetGraph::EdgeSet;
+  using Gadget = std::pair<MachineInstr *, MachineInstr *>;
+
+  const X86Subtarget *STI;
+  const TargetInstrInfo *TII;
+  const TargetRegisterInfo *TRI;
+
+  int hardenLoads(MachineFunction &MF, bool Fixed) const;
+  std::unique_ptr<MachineGadgetGraph>
+  getGadgetGraph(MachineFunction &MF, const MachineLoopInfo &MLI,
+                 const MachineDominatorTree &MDT,
+                 const MachineDominanceFrontier &MDF, bool FixedLoads) const;
+
+  bool instrUsesRegToAccessMemory(const MachineInstr &I, unsigned Reg) const;
+  bool instrUsesRegToBranch(const MachineInstr &I, unsigned Reg) const;
+  template <unsigned K> bool hasLoadFrom(const MachineInstr &MI) const;
+  bool instrAccessesStackSlot(const MachineInstr &MI) const;
+  bool instrAccessesConstantPool(const MachineInstr &MI) const;
+  bool instrAccessesGOT(const MachineInstr &MI) const;
+  inline bool instrIsFixedAccess(const MachineInstr &MI) const {
+    return instrAccessesConstantPool(MI) || instrAccessesStackSlot(MI) ||
+           instrAccessesGOT(MI);
+  }
+  inline bool isFence(const MachineInstr *MI) const {
+    return MI && (MI->getOpcode() == X86::LFENCE ||
+                  (STI->useLVIControlFlowIntegrity() && MI->isCall()));
+  }
+};
+
+} // end anonymous namespace
+
+namespace llvm {
+
+template <>
+struct GraphTraits<X86LoadValueInjectionLoadHardeningPass::MachineGadgetGraph *>
+    : GraphTraits<ImmutableGraph<MachineInstr *, int> *> {};
+
+template <>
+struct DOTGraphTraits<
+    X86LoadValueInjectionLoadHardeningPass::MachineGadgetGraph *>
+    : DefaultDOTGraphTraits {
+  using GraphType = X86LoadValueInjectionLoadHardeningPass::MachineGadgetGraph;
+  using Traits = X86LoadValueInjectionLoadHardeningPass::GTraits;
+  using NodeRef = typename Traits::NodeRef;
+  using EdgeRef = typename Traits::EdgeRef;
+  using ChildIteratorType = typename Traits::ChildIteratorType;
+  using ChildEdgeIteratorType = typename Traits::ChildEdgeIteratorType;
+
+  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
+
+  static std::string getGraphName(GraphType *G) {
+    std::string GraphName{"Speculative gadgets for \""};
+    GraphName += G->getMF().getName();
+    GraphName += "\" function";
+    return GraphName;
+  }
+
+  std::string getNodeLabel(NodeRef Node, GraphType *) {
+    std::string str;
+    raw_string_ostream str_stream{str};
+    if (Node->value() == ARG_NODE)
+      return "ARGS";
+    str_stream << *Node->value();
+    return str_stream.str();
+  }
+
+  static std::string getNodeAttributes(NodeRef Node, GraphType *) {
+    MachineInstr *MI = Node->value();
+    if (MI == ARG_NODE)
+      return "color = blue";
+    else if (MI->getOpcode() == X86::LFENCE)
+      return "color = green";
+    else
+      return "";
+  }
+
+  static std::string getEdgeAttributes(NodeRef, ChildIteratorType E,
+                                       GraphType *) {
+    int EdgeVal = (*E.getCurrent()).value();
+    return EdgeVal >= 0 ? "label = " + std::to_string(EdgeVal)
+                        : "color = red, style = \"dashed\"";
+  }
+};
+
+} // end namespace llvm
+
+char X86LoadValueInjectionLoadHardeningPass::ID = 0;
+
+void X86LoadValueInjectionLoadHardeningPass::getAnalysisUsage(
+    AnalysisUsage &AU) const {
+  MachineFunctionPass::getAnalysisUsage(AU);
+  AU.addRequired<MachineLoopInfo>();
+  AU.addRequired<MachineDominatorTree>();
+  AU.addRequired<MachineDominanceFrontier>();
+  AU.setPreservesCFG();
+}
+
+bool X86LoadValueInjectionLoadHardeningPass::runOnMachineFunction(
+    MachineFunction &MF) {
+  STI = &MF.getSubtarget<X86Subtarget>();
+  if (!STI->useLVILoadHardening() || !(STI->hasSSE2() || STI->is64Bit()))
+    return false; // FIXME: support 32-bit
+
+  // Don't skip functions with the "optnone" attr but participate in opt-bisect.
+  const Function &F = MF.getFunction();
+  if (!F.hasOptNone() && skipFunction(F))
+    return false;
+
+  LLVM_DEBUG(dbgs() << "***** " << getPassName() << " : " << MF.getName()
+                    << " *****\n");
+  ++NumFunctionsConsidered;
+  TII = STI->getInstrInfo();
+  TRI = STI->getRegisterInfo();
+  LLVM_DEBUG(dbgs() << "Hardening data-dependent loads...\n");
+  hardenLoads(MF, false);
+  LLVM_DEBUG(dbgs() << "Hardening data-dependent loads... Done\n");
+  if (!NoFixedLoads) {
+    LLVM_DEBUG(dbgs() << "Hardening fixed loads...\n");
+    hardenLoads(MF, true);
+    LLVM_DEBUG(dbgs() << "Hardening fixed loads... Done\n");
+  }
+  return false;
+}
+
+// Apply the mitigation to `MF`, return the number of fences inserted.
+// If `FixedLoads` is `true`, then the mitigation will be applied to both fixed
+// and non-fixed loads; otherwise, only non-fixed loads.
+int X86LoadValueInjectionLoadHardeningPass::hardenLoads(MachineFunction &MF,
+                                                        bool FixedLoads) const {
+  LLVM_DEBUG(dbgs() << "Building gadget graph...\n");
+  const auto &MLI = getAnalysis<MachineLoopInfo>();
+  const auto &MDT = getAnalysis<MachineDominatorTree>();
+  const auto &MDF = getAnalysis<MachineDominanceFrontier>();
+  std::unique_ptr<MachineGadgetGraph> Graph =
+      getGadgetGraph(MF, MLI, MDT, MDF, FixedLoads);
+  LLVM_DEBUG(dbgs() << "Building gadget graph... Done\n");
+  if (Graph == nullptr)
+    return 0; // didn't find any gadgets
+
+  if (EmitDotVerify) {
+    WriteGraph(outs(), Graph.get());
+    return 0;
+  }
+
+  if (EmitDot || EmitDotOnly) {
+    LLVM_DEBUG(dbgs() << "Emitting gadget graph...\n");
+    std::error_code FileError;
+    std::string FileName = "lvi.";
+    if (FixedLoads)
+      FileName += "fixed.";
+    FileName += Graph->getMF().getName();
+    FileName += ".dot";
+    raw_fd_ostream FileOut(FileName, FileError);
+    if (FileError)
+      errs() << FileError.message();
+    WriteGraph(FileOut, Graph.get());
+    FileOut.close();
+    LLVM_DEBUG(dbgs() << "Emitting gadget graph... Done\n");
+    if (EmitDotOnly)
+      return 0;
+  }
+
+  return 0;
+}
+
+std::unique_ptr<X86LoadValueInjectionLoadHardeningPass::MachineGadgetGraph>
+X86LoadValueInjectionLoadHardeningPass::getGadgetGraph(
+    MachineFunction &MF, const MachineLoopInfo &MLI,
+    const MachineDominatorTree &MDT, const MachineDominanceFrontier &MDF,
+    bool FixedLoads) const {
+  using namespace rdf;
+
+  // Build the Register Dataflow Graph using the RDF framework
+  TargetOperandInfo TOI{*TII};
+  DataFlowGraph DFG{MF, *TII, *TRI, MDT, MDF, TOI};
+  DFG.build();
+  Liveness L{MF.getRegInfo(), DFG};
+  L.computePhiInfo();
+
+  GraphBuilder Builder;
+  using GraphIter = typename GraphBuilder::NodeRef;
+  DenseMap<MachineInstr *, GraphIter> NodeMap;
+  int FenceCount = 0;
+  auto MaybeAddNode = [&NodeMap, &Builder](MachineInstr *MI) {
+    auto Ref = NodeMap.find(MI);
+    if (Ref == NodeMap.end()) {
+      auto I = Builder.addVertex(MI);
+      NodeMap[MI] = I;
+      return std::pair<GraphIter, bool>{I, true};
+    } else {
+      return std::pair<GraphIter, bool>{Ref->getSecond(), false};
+    }
+  };
+
+  // Analyze all machine instructions to find gadgets and LFENCEs, adding
+  // each interesting value to `Nodes`
+  DenseSet<std::pair<GraphIter, GraphIter>> GadgetEdgeSet;
+  auto AnalyzeDef = [&](NodeAddr<DefNode *> Def) {
+    MachineInstr *MI = Def.Addr->getFlags() & NodeAttrs::PhiRef
+                           ? ARG_NODE
+                           : Def.Addr->getOp().getParent();
+    auto AnalyzeUse = [&](NodeAddr<UseNode *> Use) {
+      assert(!(Use.Addr->getFlags() & NodeAttrs::PhiRef));
+      MachineOperand &UseMO = Use.Addr->getOp();
+      MachineInstr &UseMI = *UseMO.getParent();
+      assert(UseMO.isReg());
+      // We naively assume that an instruction propagates any loaded Uses
+      // to all Defs, unless the instruction is a call
+      if (UseMI.isCall())
+        return false;
+      if (instrUsesRegToAccessMemory(UseMI, UseMO.getReg()) ||
+          (!NoConditionalBranches &&
+           instrUsesRegToBranch(UseMI, UseMO.getReg()))) { // found a gadget!
+        // add the root of this chain
+        auto GadgetBegin = MaybeAddNode(MI);
+        // and the instruction that (transitively) discloses the root
+        auto GadgetEnd = MaybeAddNode(&UseMI);
+        if (GadgetEdgeSet.insert({GadgetBegin.first, GadgetEnd.first}).second)
+          Builder.addEdge(GADGET_EDGE, GadgetBegin.first, GadgetEnd.first);
+        if (UseMI.mayLoad()) // FIXME: This should be more precise
+          return false;      // stop traversing further uses of `Reg`
+      }
+      return true;
+    };
+    SmallSet<NodeId, 8> NodesVisited;
+    std::function<void(NodeAddr<DefNode *>)> AnalyzeDefUseChain =
+        [&](NodeAddr<DefNode *> Def) {
+          if (Def.Addr->getAttrs() & NodeAttrs::Dead)
+            return;
+          RegisterRef DefReg = DFG.getPRI().normalize(Def.Addr->getRegRef(DFG));
+          NodeList Uses;
+          for (auto UseID : L.getAllReachedUses(DefReg, Def)) {
+            auto Use = DFG.addr<UseNode *>(UseID);
+            if (Use.Addr->getFlags() & NodeAttrs::PhiRef) { // phi node
+              NodeAddr<PhiNode *> Phi = Use.Addr->getOwner(DFG);
+              for (auto I : L.getRealUses(Phi.Id)) {
+                if (DFG.getPRI().alias(RegisterRef(I.first), DefReg)) {
+                  for (auto UA : I.second) {
+                    auto PhiUse = DFG.addr<UseNode *>(UA.first);
+                    Uses.push_back(PhiUse);
+                  }
+                }
+              }
+            } else { // not a phi node
+              Uses.push_back(Use);
+            }
+          }
+          for (auto N : Uses) {
+            NodeAddr<UseNode *> Use{N};
+            if (NodesVisited.insert(Use.Id).second && AnalyzeUse(Use)) {
+              NodeAddr<InstrNode *> Owner{Use.Addr->getOwner(DFG)};
+              NodeList Defs = Owner.Addr->members_if(DataFlowGraph::IsDef, DFG);
+              std::for_each(Defs.begin(), Defs.end(), AnalyzeDefUseChain);
+            }
+          }
+        };
+    AnalyzeDefUseChain(Def);
+  };
+
+  LLVM_DEBUG(dbgs() << "Analyzing def-use chains to find gadgets\n");
+  // Analyze function arguments
+  if (!FixedLoads) { // only need to analyze function args once
+    NodeAddr<BlockNode *> EntryBlock = DFG.getFunc().Addr->getEntryBlock(DFG);
+    for (NodeAddr<PhiNode *> ArgPhi :
+         EntryBlock.Addr->members_if(DataFlowGraph::IsPhi, DFG)) {
+      NodeList Defs = ArgPhi.Addr->members_if(DataFlowGraph::IsDef, DFG);
+      std::for_each(Defs.begin(), Defs.end(), AnalyzeDef);
+    }
+  }
+  // Analyze every instruction in MF
+  for (NodeAddr<BlockNode *> BA : DFG.getFunc().Addr->members(DFG)) {
+    for (NodeAddr<StmtNode *> SA :
+         BA.Addr->members_if(DataFlowGraph::IsCode<NodeAttrs::Stmt>, DFG)) {
+      MachineInstr *MI = SA.Addr->getCode();
+      if (isFence(MI)) {
+        MaybeAddNode(MI);
+        ++FenceCount;
+      } else if (MI->mayLoad() && ((FixedLoads && instrIsFixedAccess(*MI)) ||
+                                   (!FixedLoads && !instrIsFixedAccess(*MI)))) {
+        NodeList Defs = SA.Addr->members_if(DataFlowGraph::IsDef, DFG);
+        std::for_each(Defs.begin(), Defs.end(), AnalyzeDef);
+      }
+    }
+  }
+  int GadgetCount = static_cast<int>(GadgetEdgeSet.size());
+  LLVM_DEBUG(dbgs() << "Found " << FenceCount << " fences\n");
+  LLVM_DEBUG(dbgs() << "Found " << GadgetCount << " gadgets\n");
+  if (GadgetCount == 0)
+    return nullptr;
+  NumGadgets += GadgetCount;
+
+  // Traverse CFG to build the rest of the graph
+  SmallSet<MachineBasicBlock *, 8> BlocksVisited;
+  std::function<void(MachineBasicBlock *, GraphIter, unsigned)> TraverseCFG =
+      [&](MachineBasicBlock *MBB, GraphIter GI, unsigned ParentDepth) {
+        unsigned LoopDepth = MLI.getLoopDepth(MBB);
+        if (!MBB->empty()) {
+          // Always add the first instruction in each block
+          auto NI = MBB->begin();
+          auto BeginBB = MaybeAddNode(&*NI);
+          Builder.addEdge(ParentDepth, GI, BeginBB.first);
+          if (!BlocksVisited.insert(MBB).second)
+            return;
+
+          // Add any instructions within the block that are gadget components
+          GI = BeginBB.first;
+          while (++NI != MBB->end()) {
+            auto Ref = NodeMap.find(&*NI);
+            if (Ref != NodeMap.end()) {
+              Builder.addEdge(LoopDepth, GI, Ref->getSecond());
+              GI = Ref->getSecond();
+            }
+          }
+
+          // Always add the terminator instruction, if one exists
+          auto T = MBB->getFirstTerminator();
+          if (T != MBB->end()) {
+            auto EndBB = MaybeAddNode(&*T);
+            if (EndBB.second)
+              Builder.addEdge(LoopDepth, GI, EndBB.first);
+            GI = EndBB.first;
+          }
+        }
+        for (MachineBasicBlock *Succ : MBB->successors())
+          TraverseCFG(Succ, GI, LoopDepth);
+      };
+  // ARG_NODE is a pseudo-instruction that represents MF args in the GadgetGraph
+  GraphIter ArgNode = MaybeAddNode(ARG_NODE).first;
+  TraverseCFG(&MF.front(), ArgNode, 0);
+  std::unique_ptr<MachineGadgetGraph> G{Builder.get(FenceCount, GadgetCount)};
+  LLVM_DEBUG(dbgs() << "Found " << GTraits::size(G.get()) << " nodes\n");
+  return G;
+}
+
+bool X86LoadValueInjectionLoadHardeningPass::instrUsesRegToAccessMemory(
+    const MachineInstr &MI, unsigned Reg) const {
+  if (!MI.mayLoadOrStore() || MI.getOpcode() == X86::MFENCE ||
+      MI.getOpcode() == X86::SFENCE || MI.getOpcode() == X86::LFENCE)
+    return false;
+
+  // FIXME: This does not handle pseudo loading instruction like TCRETURN*
+  const MCInstrDesc &Desc = MI.getDesc();
+  int MemRefBeginIdx = X86II::getMemoryOperandNo(Desc.TSFlags);
+  if (MemRefBeginIdx < 0) {
+    LLVM_DEBUG(dbgs() << "Warning: unable to obtain memory operand for loading "
+                         "instruction:\n";
+               MI.print(dbgs()); dbgs() << '\n';);
+    return false;
+  }
+  MemRefBeginIdx += X86II::getOperandBias(Desc);
+
+  const MachineOperand &BaseMO =
+      MI.getOperand(MemRefBeginIdx + X86::AddrBaseReg);
+  const MachineOperand &IndexMO =
+      MI.getOperand(MemRefBeginIdx + X86::AddrIndexReg);
+  return (BaseMO.isReg() && BaseMO.getReg() != X86::NoRegister &&
+          TRI->regsOverlap(BaseMO.getReg(), Reg)) ||
+         (IndexMO.isReg() && IndexMO.getReg() != X86::NoRegister &&
+          TRI->regsOverlap(IndexMO.getReg(), Reg));
+}
+
+bool X86LoadValueInjectionLoadHardeningPass::instrUsesRegToBranch(
+    const MachineInstr &MI, unsigned Reg) const {
+  if (!MI.isConditionalBranch())
+    return false;
+  for (const MachineOperand &Use : MI.uses())
+    if (Use.isReg() && Use.getReg() == Reg)
+      return true;
+  return false;
+}
+
+template <unsigned K>
+bool X86LoadValueInjectionLoadHardeningPass::hasLoadFrom(
+    const MachineInstr &MI) const {
+  for (auto &MMO : MI.memoperands()) {
+    const PseudoSourceValue *PSV = MMO->getPseudoValue();
+    if (PSV && PSV->kind() == K && MMO->isLoad())
+      return true;
+  }
+  return false;
+}
+
+bool X86LoadValueInjectionLoadHardeningPass::instrAccessesStackSlot(
+    const MachineInstr &MI) const {
+  // Check the PSV first
+  if (hasLoadFrom<PseudoSourceValue::PSVKind::FixedStack>(MI))
+    return true;
+  // Some loads are not marked with a PSV, so we always need to double check
+  const MCInstrDesc &Desc = MI.getDesc();
+  int MemRefBeginIdx = X86II::getMemoryOperandNo(Desc.TSFlags);
+  if (MemRefBeginIdx < 0)
+    return false;
+  MemRefBeginIdx += X86II::getOperandBias(Desc);
+  return MI.getOperand(MemRefBeginIdx + X86::AddrBaseReg).isFI() &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrScaleAmt).isImm() &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrIndexReg).isReg() &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrDisp).isImm() &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrScaleAmt).getImm() == 1 &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrIndexReg).getReg() ==
+             X86::NoRegister &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrDisp).getImm() == 0;
+}
+
+bool X86LoadValueInjectionLoadHardeningPass::instrAccessesConstantPool(
+    const MachineInstr &MI) const {
+  if (hasLoadFrom<PseudoSourceValue::PSVKind::ConstantPool>(MI))
+    return true;
+  const MCInstrDesc &Desc = MI.getDesc();
+  int MemRefBeginIdx = X86II::getMemoryOperandNo(Desc.TSFlags);
+  if (MemRefBeginIdx < 0)
+    return false;
+  MemRefBeginIdx += X86II::getOperandBias(Desc);
+  return MI.getOperand(MemRefBeginIdx + X86::AddrBaseReg).isReg() &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrScaleAmt).isImm() &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrIndexReg).isReg() &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrDisp).isCPI() &&
+         (MI.getOperand(MemRefBeginIdx + X86::AddrBaseReg).getReg() ==
+              X86::RIP ||
+          MI.getOperand(MemRefBeginIdx + X86::AddrBaseReg).getReg() ==
+              X86::NoRegister) &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrScaleAmt).getImm() == 1 &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrIndexReg).getReg() ==
+             X86::NoRegister;
+}
+
+bool X86LoadValueInjectionLoadHardeningPass::instrAccessesGOT(
+    const MachineInstr &MI) const {
+  if (hasLoadFrom<PseudoSourceValue::PSVKind::GOT>(MI))
+    return true;
+  const MCInstrDesc &Desc = MI.getDesc();
+  int MemRefBeginIdx = X86II::getMemoryOperandNo(Desc.TSFlags);
+  if (MemRefBeginIdx < 0)
+    return false;
+  MemRefBeginIdx += X86II::getOperandBias(Desc);
+  return MI.getOperand(MemRefBeginIdx + X86::AddrBaseReg).isReg() &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrScaleAmt).isImm() &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrIndexReg).isReg() &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrDisp).getTargetFlags() ==
+             X86II::MO_GOTPCREL &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrBaseReg).getReg() ==
+             X86::RIP &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrScaleAmt).getImm() == 1 &&
+         MI.getOperand(MemRefBeginIdx + X86::AddrIndexReg).getReg() ==
+             X86::NoRegister;
+}
+
+INITIALIZE_PASS_BEGIN(X86LoadValueInjectionLoadHardeningPass, PASS_KEY,
+                      "X86 LVI load hardening", false, false)
+INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
+INITIALIZE_PASS_END(X86LoadValueInjectionLoadHardeningPass, PASS_KEY,
+                    "X86 LVI load hardening", false, false)
+
+FunctionPass *llvm::createX86LoadValueInjectionLoadHardeningPass() {
+  return new X86LoadValueInjectionLoadHardeningPass();
+}

llvm/lib/Target/X86/X86Subtarget.h

protected:
   bool UseRetpolineExternalThunk = false;
 
   /// Prevent generation of indirect call/branch instructions from memory,
   /// and force all indirect call/branch instructions from a register to be
   /// preceded by an LFENCE. Also decompose RET instructions into a
   /// POP+LFENCE+JMP sequence.
   bool UseLVIControlFlowIntegrity = false;
 
+  /// Insert LFENCE instructions to prevent data speculatively injected into
+  /// loads from being used maliciously.
+  bool UseLVILoadHardening = false;
+
   /// Use software floating point for code generation.
   bool UseSoftFloat = false;
 
   /// Use alias analysis during code generation.
   bool UseAA = false;
 
   /// The minimum alignment known to hold of the stack frame on
   /// entry to the function and which must be maintained by every function.
public:
   bool useRetpolineIndirectCalls() const { return UseRetpolineIndirectCalls; }
   bool useRetpolineIndirectBranches() const {
     return UseRetpolineIndirectBranches;
   }
   bool useRetpolineExternalThunk() const { return UseRetpolineExternalThunk; }
   bool preferMaskRegisters() const { return PreferMaskRegisters; }
   bool useGLMDivSqrtCosts() const { return UseGLMDivSqrtCosts; }
   bool useLVIControlFlowIntegrity() const { return UseLVIControlFlowIntegrity; }
+  bool useLVILoadHardening() const { return UseLVILoadHardening; }
 
   unsigned getPreferVectorWidth() const { return PreferVectorWidth; }
   unsigned getRequiredVectorWidth() const { return RequiredVectorWidth; }
 
   // Helper functions to determine when we should allow widening to 512-bit
   // during codegen.
   // TODO: Currently we're always allowing widening on CPUs without VLX,
   // because for many cases we don't have a better option.

llvm/lib/Target/X86/X86TargetMachine.cpp

extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeX86Target() {
   initializeX86ExpandPseudoPass(PR);
   initializeX86ExecutionDomainFixPass(PR);
   initializeX86DomainReassignmentPass(PR);
   initializeX86AvoidSFBPassPass(PR);
   initializeX86SpeculativeLoadHardeningPassPass(PR);
   initializeX86FlagsCopyLoweringPassPass(PR);
   initializeX86CondBrFoldingPassPass(PR);
   initializeX86LoadValueInjectionIndirectThunksPassPass(PR);
+  initializeX86LoadValueInjectionLoadHardeningPassPass(PR);
   initializeX86LoadValueInjectionRetHardeningPassPass(PR);
   initializeX86OptimizeLEAPassPass(PR);
 }
 
 static std::unique_ptr<TargetLoweringObjectFile> createTLOF(const Triple &TT) {
   if (TT.isOSBinFormatMachO()) {
     if (TT.getArch() == Triple::x86_64)
       return std::make_unique<X86_64MachoTargetObjectFile>();

 }
 void X86PassConfig::addMachineSSAOptimization() {
   addPass(createX86DomainReassignmentPass());
   TargetPassConfig::addMachineSSAOptimization();
 }
 
 void X86PassConfig::addPostRegAlloc() {
   addPass(createX86FloatingPointStackifierPass());
+  addPass(createX86LoadValueInjectionLoadHardeningPass());
 }
 
 void X86PassConfig::addPreSched2() { addPass(createX86ExpandPseudoPass()); }
 
 void X86PassConfig::addPreEmitPass() {
   if (getOptLevel() != CodeGenOpt::None) {
     addPass(new X86ExecutionDomainFix());
     addPass(createBreakFalseDeps());

llvm/test/CodeGen/X86/O0-pipeline.ll

 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       X86 EFLAGS copy lowering
 ; CHECK-NEXT:       X86 WinAlloca Expander
 ; CHECK-NEXT:       Eliminate PHI nodes for register allocation
 ; CHECK-NEXT:       Two-Address instruction pass
 ; CHECK-NEXT:       Fast Register Allocator
 ; CHECK-NEXT:       Bundle Machine CFG Edges
 ; CHECK-NEXT:       X86 FP Stackifier
+; CHECK-NEXT:       MachineDominator Tree Construction
+; CHECK-NEXT:       Machine Natural Loop Construction
+; CHECK-NEXT:       Machine Dominance Frontier Construction
+; CHECK-NEXT:       X86 Load Value Injection (LVI) Load Hardening Pass
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Prologue/Epilogue Insertion & Frame Finalization
 ; CHECK-NEXT:       Post-RA pseudo instruction expansion pass
 ; CHECK-NEXT:       X86 pseudo instruction expansion pass
 ; CHECK-NEXT:       Analyze Machine Code For Garbage Collection
 ; CHECK-NEXT:       Insert fentry calls
 ; CHECK-NEXT:       Insert XRay ops

llvm/test/CodeGen/X86/O3-pipeline.ll

 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Greedy Register Allocator
 ; CHECK-NEXT:       Virtual Register Rewriter
 ; CHECK-NEXT:       Stack Slot Coloring
 ; CHECK-NEXT:       Machine Copy Propagation Pass
 ; CHECK-NEXT:       Machine Loop Invariant Code Motion
 ; CHECK-NEXT:       Bundle Machine CFG Edges
 ; CHECK-NEXT:       X86 FP Stackifier
+; CHECK-NEXT:       MachineDominator Tree Construction
+; CHECK-NEXT:       Machine Dominance Frontier Construction
+; CHECK-NEXT:       X86 Load Value Injection (LVI) Load Hardening Pass
 ; CHECK-NEXT:       PostRA Machine Sink
 ; CHECK-NEXT:       Machine Block Frequency Analysis
-; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       MachinePostDominator Tree Construction
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Machine Optimization Remark Emitter
 ; CHECK-NEXT:       Shrink Wrapping analysis
 ; CHECK-NEXT:       Prologue/Epilogue Insertion & Frame Finalization
 ; CHECK-NEXT:       Control Flow Optimizer
 ; CHECK-NEXT:       Lazy Machine Block Frequency Analysis
 ; CHECK-NEXT:       Tail Duplication

llvm/test/CodeGen/X86/lvi-hardening-gadget-graph.ll

+; RUN: llc -verify-machineinstrs -mtriple=x86_64-unknown -x86-lvi-load-dot-verify -o %t < %s | FileCheck %s
+
+; Function Attrs: noinline nounwind optnone uwtable
+define dso_local i32 @test(i32* %untrusted_user_ptr, i32* %secret, i32 %secret_size) #0 {
+entry:
+  %untrusted_user_ptr.addr = alloca i32*, align 8
+  %secret.addr = alloca i32*, align 8
+  %secret_size.addr = alloca i32, align 4
+  %ret_val = alloca i32, align 4
+  %i = alloca i32, align 4
+  store i32* %untrusted_user_ptr, i32** %untrusted_user_ptr.addr, align 8
+  store i32* %secret, i32** %secret.addr, align 8
+  store i32 %secret_size, i32* %secret_size.addr, align 4
+  store i32 0, i32* %ret_val, align 4
+  call void @llvm.x86.sse2.lfence()
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %i, align 4
+  %1 = load i32, i32* %secret_size.addr, align 4
+  %cmp = icmp slt i32 %0, %1
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %2 = load i32, i32* %i, align 4
+  %rem = srem i32 %2, 2
+  %cmp1 = icmp eq i32 %rem, 0
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  %3 = load i32*, i32** %secret.addr, align 8
+  %4 = load i32, i32* %ret_val, align 4
+  %idxprom = sext i32 %4 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %3, i64 %idxprom
+  %5 = load i32, i32* %arrayidx, align 4
+  %6 = load i32*, i32** %untrusted_user_ptr.addr, align 8
+  store i32 %5, i32* %6, align 4
+  br label %if.end
+
+if.else:                                          ; preds = %for.body
+  %7 = load i32*, i32** %secret.addr, align 8
+  %8 = load i32, i32* %ret_val, align 4
+  %idxprom2 = sext i32 %8 to i64
+  %arrayidx3 = getelementptr inbounds i32, i32* %7, i64 %idxprom2
+  store i32 42, i32* %arrayidx3, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %9 = load i32*, i32** %untrusted_user_ptr.addr, align 8
+  %10 = load i32, i32* %9, align 4
+  store i32 %10, i32* %ret_val, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end
+  %11 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %11, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %12 = load i32, i32* %ret_val, align 4
+  ret i32 %12
+}
+
+; CHECK:      digraph "Speculative gadgets for \"test\" function" {
+; CHECK-NEXT: label="Speculative gadgets for \"test\" function";
+; CHECK:      Node0x{{[0-9a-f]+}} [shape=record,color = green,label="{LFENCE\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 0];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $eax = MOV32rm %stack.4.i, 1, $noreg, 0, $noreg :: (dereferenceable load 4 from %ir.i)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[color = red, style = "dashed"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{JCC_1 %bb.6, 13, implicit killed $eflags\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{CMP32rm killed renamable $eax, %stack.2.secret_size.addr, 1, $noreg, 0, $noreg, implicit-def $eflags :: (dereferenceable load 4 from %ir.secret_size.addr)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[color = red, style = "dashed"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $eax = MOV32rm %stack.4.i, 1, $noreg, 0, $noreg :: (dereferenceable load 4 from %ir.i)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[color = red, style = "dashed"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{JCC_1 %bb.4, 5, implicit killed $eflags\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $rax = MOV64rm %stack.1.secret.addr, 1, $noreg, 0, $noreg :: (dereferenceable load 8 from %ir.secret.addr)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[color = red, style = "dashed"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $eax = MOV32rm killed renamable $rax, 4, killed renamable $rcx, 0, $noreg :: (load 4 from %ir.arrayidx)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $rcx = MOVSX64rm32 %stack.3.ret_val, 1, $noreg, 0, $noreg :: (dereferenceable load 4 from %ir.ret_val)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[color = red, style = "dashed"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $rcx = MOV64rm %stack.0.untrusted_user_ptr.addr, 1, $noreg, 0, $noreg :: (dereferenceable load 8 from %ir.untrusted_user_ptr.addr)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[color = red, style = "dashed"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{MOV32mr killed renamable $rcx, 1, $noreg, 0, $noreg, killed renamable $eax :: (store 4 into %ir.6)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $rax = MOV64rm %stack.1.secret.addr, 1, $noreg, 0, $noreg :: (dereferenceable load 8 from %ir.secret.addr)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[color = red, style = "dashed"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{MOV32mi killed renamable $rax, 4, killed renamable $rcx, 0, $noreg, 42 :: (store 4 into %ir.arrayidx3)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $rcx = MOVSX64rm32 %stack.3.ret_val, 1, $noreg, 0, $noreg :: (dereferenceable load 4 from %ir.ret_val)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[color = red, style = "dashed"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $rax = MOV64rm %stack.0.untrusted_user_ptr.addr, 1, $noreg, 0, $noreg :: (dereferenceable load 8 from %ir.untrusted_user_ptr.addr)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[color = red, style = "dashed"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $eax = MOV32rm killed renamable $rax, 1, $noreg, 0, $noreg :: (load 4 from %ir.9)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,color = blue,label="{ARGS}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 0];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{MOV64mr %stack.0.untrusted_user_ptr.addr, 1, $noreg, 0, $noreg, killed renamable $rdi :: (store 8 into %ir.untrusted_user_ptr.addr)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 0];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{JMP_1 %bb.5\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{JMP_1 %bb.1\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 1];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{renamable $eax = MOV32rm %stack.3.ret_val, 1, $noreg, 0, $noreg :: (dereferenceable load 4 from %ir.ret_val)\n}"];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} -> Node0x{{[0-9a-f]+}}[label = 0];
+; CHECK-NEXT: Node0x{{[0-9a-f]+}} [shape=record,label="{RET 0, $eax\n}"];
+; CHECK-NEXT: }
+
+; Function Attrs: nounwind
+declare void @llvm.x86.sse2.lfence() #1
+
+attributes #0 = { "target-features"="+lvi-cfi"
+                  "target-features"="+lvi-load-hardening" }
+attributes #1 = { nounwind }