[mlir] Add a generic mem2reg implementation.

[Moxinilian]

Summary

This patch introduces a generic implementation of mem2reg on
unstructured control-flow, along with a specialization for LLVM IR. This
is achieved by defining three new interfaces, representing 1. allocating
operations, 2. operations doing memory accesses, 3. operations that can
be rewired and/or deleted to stop using a specific use.

The file containing the core implementation of the algorithm
(Mem2Reg.cpp) contains a detailed explanation of how the algorithm
works. The contract for this pass is that given a memory slot with a
single non-aliased pointer, the pass will either remove all the uses of
the pointer or not change anything.

To help review this patch, I recommend starting by looking at the
interfaces defined in Mem2Reg.td, along with their reference
implementation for LLVM IR defined in LLVMMem2Reg.cpp. Then, the core
algorithm is implemented in Mem2Reg.cpp.

If this is all good I also have an implementation of the interfaces for
0-dimensional memref promotion that I can upstream afterwards.

[zero9178]

mlir/include/mlir/Transforms/Mem2Reg.td

1

Is there any precedence for having an interface within Transforms? I think even if the interface is only used by one single transform (at the moment at least), it is more conventional to have them within the Interfaces directory.

In particular, having it within Transforms would create a few layering issues here:
MLIRLLVMDialect dialect would have to depend on the MLIRTransforms library (something this patch currently doesn't do, which would likely cause linking errors in shared library builds).

If it were to instead be within Interfaces and a library on its own there you could have both MLIRLLVMDialect and MLIRTransforms depend on the interface and be properly decoupled.

42

ultra nit: mlir::MemorySlot is currently 24 bytes on 64 bit machines. That'd be worth passing as const mlir::MemorySlot& instead probably.
Ditto below

114

Should this be const ::llvm::SmallPtrSetImpl<::mlir::OpOperand *> &?

Ditto below

126

What is onlyIf here? Is this a stale description?

[zero9178]

mlir/lib/Dialect/LLVMIR/IR/LLVMMem2Reg.cpp

34

This is a mismatch between what LLVM currently does: https://godbolt.org/z/vKTE59v7o
It creates a undef operation instead of poison. That said I think there is a transition away from undef in LLVM IR, although this has seemingly not yet been done to mem2reg. Was the choice of posion here deliberate?

43

I might be misunderstanding the logic here, but shouldn't the logic to replace DbgDeclareOp with DbgValueOp rather be done in the removeBlockingUses implementation of DbgDeclareOp?

167

Doesn't LifetimeStartOp (and end), not have any results, making this a noop?

[Moxinilian]

mlir/lib/Dialect/LLVMIR/IR/LLVMMem2Reg.cpp

34

Yeah this is I think an interesting point. In the LLVM mem2reg, some things have been replaced with poison, but for some reason not the default value for the allocas. We spent a lot of time discussing whether or not we should use undef or poison here. We settled on poison at the time because 1. there is the transition away from undef in LLVM and 2. poison would make sense semantically here, especially considering loading uninitialized variables is undefined behavior in C.

However I just realized that the langref in fact specifies that this should be undef unfortunately. I personally find that poison would be a better fit but if undef is specified I think we should stick to that then.

43

This is an unfortunate tricky point with respect to debug intrinsics. A value debug intrinsic should be generated at each store and at each merge point. If this was added to removeBlockingUses, this would only be called when removing the declare intrinsic, without knowledge of where the merge points are. So instead we have this hook on block arguments to insert it there. This is not super pretty but it is the most generic approach we could find there. If you have other suggestions that would be very welcome, but otherwise I'm not sure if there is much better to do.

[Moxinilian]

Address comments.

[Moxinilian]

Update default for LLVM to undef

[zero9178]

mlir/lib/Dialect/LLVMIR/IR/LLVMMem2Reg.cpp

43

I see, thank you for the explanation! I was initially mostly taken back by it being the allcoas responsibility to do so, but I don't know any better either and think it makes the most sense.

120

I think this pattern of "builder guard" & "set insertion point to *this" should be moved to the caller of removeBlockingUses, not be present in the implementation of interfaces.

Having the transformation pass do it guards against easy misuse of the API (an implementation accidently forgetting to reset the insertion point). I think it is also common expectation in MLIR (due to things like the RewritePatterns) to expect a builder to have an insertion point after the Op it is acting upon. Ops can always change their insertion point if they have different needs, but the vast majority likely needs it after the op itself.

[Moxinilian]

Address builder guard comment.

[Moxinilian]

Remove default implementations for interfaces.

[rriddle]

mlir/lib/Transforms/Mem2Reg.cpp

12

Everything in the Transforms library must be dialect agnostic, is this an accidental include here?

[Moxinilian]

Remove accidental include.

[Moxinilian]

Adjust incorrect comments.

[Moxinilian]

Relaxed interfaces a bit. The promotable op interface was a bit too restrictive for non-mem-op operations. Instead, specialized methods for memory ops where moved to the mem op interface. ALso relaxed the loaded value requirements.

[gysit]

mlir/include/mlir/Dialect/LLVMIR/LLVMOps.td

176

nit: can these be dropped?

mlir/include/mlir/Interfaces/Mem2RegInterfaces.td

1 ↗

(On Diff #515278)

nit: Mem2RegInterfaces.td

Note: the commit message may also need an update after renaming.

193 ↗

(On Diff #515278)

ultra nit: Let's drop one empty line here.

mlir/lib/Dialect/LLVMIR/IR/LLVMMem2Reg.cpp

205–206

nit: Could we use forwardToUsers here?

mlir/lib/Transforms/Mem2Reg.cpp

235

nit: drop llvm::

mlir/test/Transforms/mem2reg-llvmir.mlir

49

nit: maybe add a check promotion happened.

78

nit: I similarly would add a check if promotion happened.

[gysit]

mlir/test/Transforms/mem2reg-llvmir-dbginfo.mlir

100–101

Are these last two check lines needed? I would not expect any code there?

mlir/test/Transforms/mem2reg-llvmir.mlir

83

nit: Can you upper case the test variables like [[bb2]] or [[v3]]. Uppercase makes it easier to distinguish them from the IR.

[Mogball]

mlir/include/mlir/Interfaces/Mem2RegInterfaces.h

26 ↗

(On Diff #515278)

Is this location different than the location of the Value?

mlir/include/mlir/Interfaces/Mem2RegInterfaces.td

27 ↗

(On Diff #515278)

Couldn't you assert that the slot is a result of the operation in question? Then it is impossible for more than one operation to return the same slot.

39 ↗

(On Diff #515278)

can you provide examples of IR and operations and what the before/after of calling this method is? It's not clear what the operation is supposed to do when implementing this hook just from the description of the method

62 ↗

(On Diff #515278)

Why not have the interface provide a hook that lazily creates the default value instead? It's better to materialize IR only when necessary

mlir/lib/Dialect/LLVMIR/IR/LLVMMem2Reg.cpp

63

you could honestly provide default implementations for these methods

mlir/lib/Transforms/Mem2Reg.cpp

254

why 16? The general rule is to use the default value unless you have performance numbers to justify a particular choice.

326

drop llvm::

[Mogball]

mlir/lib/Transforms/Mem2Reg.cpp

172

This seems like something that could be added to DenseMap

[Moxinilian]

mlir/include/mlir/Interfaces/Mem2RegInterfaces.td

27 ↗

(On Diff #515278)

There are legitimate reasons for that to not be the case even though this pass supports it. For example, one could design their allocating operations using regions, if they need interesting lifetime control. Example:

dialect.region_alloca {
   ^bb0(%slot: ptr<i32>):
      // ...
}

In that case, the slot is not a result of the allocator.

62 ↗

(On Diff #515278)

Right. The reason I am doing it right now is because deciding the default value should be used comes in late, and lazily creating it might invalidate ongoing iterators. Let me see if I can still make it happen, the design has changed a bit since I picked this option.

mlir/lib/Transforms/Mem2Reg.cpp

254

Correct me if I am wrong but I believe SmallPtrSet simply does not have a default?

[Moxinilian]

mlir/include/mlir/Interfaces/Mem2RegInterfaces.td

39 ↗

(On Diff #515278)

I have added more details to the documentation, although I think the LLVM IR implementation showcases a good example? This value is basically the reaching definition used if there is no reaching definition at the point of a load.

62 ↗

(On Diff #515278)

Okay so I have made a few changes towards this goal. Now the default value is generated lazily. The only problem is that if it is generated to provide as a reaching definition for a MemOp promotion, but the MemOp does not end up using it, it has been generated for nothing. Right now that means I have left the ability to do clean-up in the completion handler. I can picture a world where the interface method takes a lambda that would generate the default value if need be but it is becoming excessively complicated in my opinion. Tell me if you have a better idea.

mlir/lib/Dialect/LLVMIR/IR/LLVMMem2Reg.cpp

63

So we discussed this a bit internally, and the problem with default implementations here is that it is easy to forget handling a case, and that makes for hard to detect problems. Are you sure this is worth it?

[Moxinilian]

Address comments.

[Moxinilian]

Remove formatting changes in DenseMap.

[gysit]

LGTM modulo the assertion comment.

mlir/lib/Transforms/Mem2Reg.cpp

189

This may trigger a warning if compiled without assertion. The standard way to avoid this is putting

(void)isResultOrNewBlockArgument;

before the assertion. Also consider starting the search from the slot.ptr and then call get defining op / cast it to a block argument, e.g:

auto isResultOrBlockArgument = [&](Value value) {
  if (value.getDefiningOp() == allocator)
    return true;
  if (BlockArgument arg = value.dyn_cast<BlockArgument>())
    if (arg.getOwner()->getParentOp() == allocator)
      return true;
  return false;
}

[kuhar]

mlir/lib/Transforms/Mem2Reg.cpp

189

In this specific case, shouldn't the whole body of this constructor be guarded by #ifndef NDEBUG?

IE this block does not produce any results/side-effects used in non-debug builds.

424–425

nit: for (auto &user: llvm::make_first_range(userToBlockingUses))?

528

nit: public is the default for struct and can be omitted here

[gysit]

mlir/lib/Transforms/Mem2Reg.cpp

189

Yes that sounds right. Without NDEBUG there is probably an unused variable warning as well.

[Moxinilian]

Address comments.

[Moxinilian]

mlir/include/mlir/Interfaces/Mem2RegInterfaces.td

27 ↗

(On Diff #515278)

I now assert that the block is either a result or an argument of one of its regions. Those seems like the only reasonable options anyway (if one needs something else, they should define the interface on the operation that actually generates the slot).

[Moxinilian]

Rebased to latest main.

[Moxinilian]

Fix formatting.

[kuhar]

mlir/lib/Transforms/Mem2Reg.cpp

189

This hasn't been fully addressed

246–247

nit: Use llvm::is_contained

[mehdi_amini]

It's not clear to me

mlir/include/mlir/Transforms/Passes.td

191

Is it conservative with respect to aliasing? How is this handled?

[Moxinilian]

Hopefully this clarifies!

mlir/include/mlir/Transforms/Passes.td

191

Aliasing is structurally not allowed: for promotion to happen, all users of the alloca must implement one of the mem2reg interfaces, and those do not allow aliasing. I agree that this is not very clear here and in the documentation of the interfaces. I will open a subsequent revision to make this obvious.

mlir/include/mlir/Dialect/LLVMIR/LLVMDialect.h

 #include "mlir/IR/OpImplementation.h"
 #include "mlir/IR/TypeSupport.h"
 #include "mlir/IR/Types.h"
 #include "mlir/Interfaces/CallInterfaces.h"
 #include "mlir/Interfaces/ControlFlowInterfaces.h"
 #include "mlir/Interfaces/InferTypeOpInterface.h"
 #include "mlir/Interfaces/SideEffectInterfaces.h"
 #include "mlir/Support/ThreadLocalCache.h"
+#include "mlir/Transforms/Mem2Reg.h"
 #include "llvm/ADT/PointerEmbeddedInt.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 
 namespace llvm {
 class Type;

mlir/include/mlir/Dialect/LLVMIR/LLVMIntrinsicOps.td

 #ifndef LLVM_INTRINSIC_OPS
 #define LLVM_INTRINSIC_OPS
 
 include "mlir/IR/OpBase.td"
 include "mlir/Dialect/LLVMIR/LLVMAttrDefs.td"
 include "mlir/Dialect/LLVMIR/LLVMOpBase.td"
 include "mlir/Interfaces/InferTypeOpInterface.td"
+include "mlir/Transforms/Mem2Reg.td"
 
 // Operations that correspond to LLVM intrinsics. With MLIR operation set being
 // extendable, there is no reason to introduce a hard boundary between "core"
 // operations and intrinsics. However, we systematically prefix them with
 // "intr." to avoid potential name clashes.
 
 class LLVM_UnaryIntrOpBase<string func, Type element,
                            list<Trait> traits = [], bit requiresFastmath = 0> :

 }
 
 //===----------------------------------------------------------------------===//
 // Lifetime Markers
 //===----------------------------------------------------------------------===//
 
 /// Base operation for lifetime markers. The LLVM intrinsics require the size
 /// operand to be an immediate. In MLIR it is encoded as an attribute.
-class LLVM_LifetimeBaseOp<string opName> : LLVM_ZeroResultIntrOp<opName> {
+class LLVM_LifetimeBaseOp<string opName> : LLVM_ZeroResultIntrOp<opName, [],
+    [DeclareOpInterfaceMethods<PromotableOpInterface>]> {
   let arguments = (ins I64Attr:$size, LLVM_AnyPointer:$ptr);
 
   // Custom builder to convert the size attribute to an integer.
   let llvmBuilder = [{
     llvm::Module *module = builder.GetInsertBlock()->getModule();
     llvm::Function *fn = llvm::Intrinsic::getDeclaration(
         module, llvm::Intrinsic::}] # llvmEnumName # [{, {}] #
         !interleave(ListIntSubst<LLVM_IntrPatterns.operand, [0]>.lst, ", ")
def LLVM_CoroResumeOp : LLVM_IntrOp<"coro.resume", [], [], [], 0> {
   let arguments = (ins LLVM_i8Ptr:$handle);
   let assemblyFormat = "$handle attr-dict `:` qualified(type($handle))";
 }
 
 //
 // Debug function intrinsics.
 //
 
-class LLVM_DbgIntrOp<string name, string argName> : LLVM_IntrOp<name, [], [], [], 0> {
+class LLVM_DbgIntrOp<string name, string argName, list<Trait> traits = []>
+    : LLVM_IntrOp<name, [], [], traits, 0> {
   let llvmBuilder = [{
     llvm::Module *module = builder.GetInsertBlock()->getModule();
     llvm::LLVMContext &ctx = module->getContext();
     llvm::Function *fn =
       llvm::Intrinsic::getDeclaration(module, llvm::Intrinsic::}]
        # !subst(".", "_", name) # [{);
     builder.CreateCall(fn, {
         llvm::MetadataAsValue::get(ctx,
$_op = $_builder.create<$_qualCppClassName>($_location,
         *argOperand, $_var_attr($varInfo));
   }];
   let assemblyFormat = [{
     qualified($varInfo) `=` $}] # argName #
       [{ `:` qualified(type($}] # argName # [{)) attr-dict
   }];
 }
 
-def LLVM_DbgDeclareOp : LLVM_DbgIntrOp<"dbg.declare", "addr"> {
+def LLVM_DbgDeclareOp : LLVM_DbgIntrOp< "dbg.declare", "addr",
+    [DeclareOpInterfaceMethods<PromotableOpInterface>]> {
   let summary = "Declare the address of a local debug info variable.";
   let arguments = (ins LLVM_AnyPointer:$addr, LLVM_DILocalVariableAttr:$varInfo);
 }
 
 def LLVM_DbgValueOp : LLVM_DbgIntrOp<"dbg.value", "value"> {
   let summary = "Describe the current value of a local debug info variable.";
   let arguments = (ins LLVM_Type:$value, LLVM_DILocalVariableAttr:$varInfo);
 }

mlir/include/mlir/Dialect/LLVMIR/LLVMOps.td

 include "mlir/Dialect/LLVMIR/LLVMOpBase.td"
 include "mlir/IR/EnumAttr.td"
 include "mlir/IR/FunctionInterfaces.td"
 include "mlir/IR/SymbolInterfaces.td"
 include "mlir/Interfaces/CallInterfaces.td"
 include "mlir/Interfaces/ControlFlowInterfaces.td"
 include "mlir/Interfaces/InferTypeOpInterface.td"
 include "mlir/Interfaces/SideEffectInterfaces.td"
+include "mlir/Transforms/Mem2Reg.td"
 
 class LLVM_Builder<string builder> {
   string llvmBuilder = builder;
 }
 
 // Base class for LLVM terminator operations.  All terminator operations have
 // zero results and an optional list of successors.
 class LLVM_TerminatorOp<string mnemonic, list<Trait> traits = []> :

 def LLVM_FSubOp : LLVM_FloatArithmeticOp<"fsub", "FSub">;
 def LLVM_FMulOp : LLVM_FloatArithmeticOp<"fmul", "FMul">;
 def LLVM_FDivOp : LLVM_FloatArithmeticOp<"fdiv", "FDiv">;
 def LLVM_FRemOp : LLVM_FloatArithmeticOp<"frem", "FRem">;
 def LLVM_FNegOp : LLVM_UnaryFloatArithmeticOp<
   LLVM_ScalarOrVectorOf<LLVM_AnyFloat>, "fneg", "FNeg">;
 
 // Memory-related operations.
-def LLVM_AllocaOp : LLVM_Op<"alloca">, LLVM_MemOpPatterns {
+def LLVM_AllocaOp : LLVM_Op<"alloca", [
+    DeclareOpInterfaceMethods<PromotableAllocationOpInterface,
+    ["handleBlockArgument", "handlePromotionComplete"]>]>,
+  LLVM_MemOpPatterns {
   let arguments = (ins AnyInteger:$arraySize,
                    OptionalAttr<I64Attr>:$alignment,
                    OptionalAttr<TypeAttr>:$elem_type,
                    UnitAttr:$inalloca);
   let results = (outs Res<LLVM_AnyPointer, "",
                           [MemAlloc<AutomaticAllocationScopeResource>]>:$res);
   string llvmInstName = "Alloca";
   string llvmBuilder = [{
[{
             elemTypeAttr, false);
 
     }]>
     ];
   let hasCustomAssemblyFormat = 1;
   let hasVerifier = 1;
 }
 
-def LLVM_GEPOp : LLVM_Op<"getelementptr", [Pure]> {
+def LLVM_GEPOp : LLVM_Op<"getelementptr", [Pure,
+    DeclareOpInterfaceMethods<PromotableOpInterface>]> {
   let arguments = (ins LLVM_ScalarOrVectorOf<LLVM_AnyPointer>:$base,
                    Variadic<LLVM_ScalarOrVectorOf<AnyInteger>>:$dynamicIndices,
                    DenseI32ArrayAttr:$rawConstantIndices,
                    OptionalAttr<TypeAttr>:$elem_type,
                    UnitAttr:$inbounds);
   let results = (outs LLVM_ScalarOrVectorOf<LLVM_AnyPointer>:$res);
   let skipDefaultBuilders = 1;
 
let extraClassDeclaration = [{
     Type getSourceElementType();
 
     GEPIndicesAdaptor<ValueRange> getIndices();
   }];
   let hasFolder = 1;
   let hasVerifier = 1;
 }
 
-def LLVM_LoadOp : LLVM_MemAccessOpBase<"load"> {
+def LLVM_LoadOp : LLVM_MemAccessOpBase<"load", [
+    DeclareOpInterfaceMethods<PromotableOpInterface>,
+    DeclareOpInterfaceMethods<PromotableMemOpInterface>]> {
   dag args = (ins Arg<LLVM_PointerTo<LLVM_LoadableType>, "", [MemRead]>:$addr,
               OptionalAttr<I64Attr>:$alignment,
               UnitAttr:$volatile_,
               UnitAttr:$nontemporal,
               DefaultValuedAttr<
                 AtomicOrdering, "AtomicOrdering::not_atomic">:$ordering,
               OptionalAttr<StrAttr>:$syncscope);
   // Append the aliasing related attributes define in LLVM_MemAccessOpBase.
OpBuilder<(ins "Type":$type, "Value":$addr,
       CArg<"unsigned", "0">:$alignment, CArg<"bool", "false">:$isVolatile,
       CArg<"bool", "false">:$isNonTemporal,
       CArg<"AtomicOrdering", "AtomicOrdering::not_atomic">:$ordering,
       CArg<"StringRef", "StringRef()">:$syncscope)>
   ];
   let hasVerifier = 1;
 }
 
-def LLVM_StoreOp : LLVM_MemAccessOpBase<"store"> {
+def LLVM_StoreOp : LLVM_MemAccessOpBase<"store", [
+    DeclareOpInterfaceMethods<PromotableOpInterface>,
+    DeclareOpInterfaceMethods<PromotableMemOpInterface>]> {
   dag args = (ins LLVM_LoadableType:$value,
               Arg<LLVM_PointerTo<LLVM_LoadableType>,"",[MemWrite]>:$addr,
               OptionalAttr<I64Attr>:$alignment,
               UnitAttr:$volatile_,
               UnitAttr:$nontemporal,
               DefaultValuedAttr<
                 AtomicOrdering, "AtomicOrdering::not_atomic">:$ordering,
               OptionalAttr<StrAttr>:$syncscope);
class LLVM_CastOp<string mnemonic, string instName, Type type,
   let builders = [LLVM_OneResultOpBuilder];
   let assemblyFormat = "$arg attr-dict `:` type($arg) `to` type($res)";
   string llvmInstName = instName;
   string mlirBuilder = [{
     $res = $_builder.create<$_qualCppClassName>(
       $_location, $_resultType, $arg);
   }];
 }
-def LLVM_BitcastOp : LLVM_CastOp<"bitcast", "BitCast",
-                                 LLVM_AnyNonAggregate, LLVM_AnyNonAggregate> {
+def LLVM_BitcastOp : LLVM_CastOp<"bitcast", "BitCast", LLVM_AnyNonAggregate,
+    LLVM_AnyNonAggregate, [DeclareOpInterfaceMethods<PromotableOpInterface>]> {
   let hasFolder = 1;
   let hasVerifier = 1;
 }
 def LLVM_AddrSpaceCastOp : LLVM_CastOp<"addrspacecast", "AddrSpaceCast",
-                                       LLVM_ScalarOrVectorOf<LLVM_AnyPointer>,
-                                       LLVM_ScalarOrVectorOf<LLVM_AnyPointer>> {
+    LLVM_ScalarOrVectorOf<LLVM_AnyPointer>,
+    [DeclareOpInterfaceMethods<PromotableOpInterface>]> {
   let hasFolder = 1;
 }
 def LLVM_IntToPtrOp : LLVM_CastOp<"inttoptr", "IntToPtr",
                                   LLVM_ScalarOrVectorOf<AnyInteger>,
                                   LLVM_ScalarOrVectorOf<LLVM_AnyPointer>>;
 def LLVM_PtrToIntOp : LLVM_CastOp<"ptrtoint", "PtrToInt",
                                   LLVM_ScalarOrVectorOf<LLVM_AnyPointer>,
                                   LLVM_ScalarOrVectorOf<AnyInteger>>;

mlir/include/mlir/Transforms/CMakeLists.txt

 
+set(LLVM_TARGET_DEFINITIONS Mem2Reg.td)
+mlir_tablegen(Mem2Reg.h.inc -gen-op-interface-decls)
+mlir_tablegen(Mem2Reg.cpp.inc -gen-op-interface-defs)
+add_public_tablegen_target(NSTransformMem2RegMem2RegIncGen)
+
 set(LLVM_TARGET_DEFINITIONS Passes.td)
 mlir_tablegen(Passes.h.inc -gen-pass-decls -name Transforms)
 mlir_tablegen(Transforms.capi.h.inc -gen-pass-capi-header --prefix Transforms)
 mlir_tablegen(Transforms.capi.cpp.inc -gen-pass-capi-impl --prefix Transforms)
 add_public_tablegen_target(MLIRTransformsPassIncGen)
 
 add_mlir_doc(Passes GeneralPasses ./ -gen-pass-doc)

mlir/include/mlir/Transforms/Mem2Reg.h

+//===-- Mem2Reg.h - Mem2Reg definitions -------------------------*- C++ -*-===//
+//
+// 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 MLIR_TRANSFORMS_MEM2REG_H
+#define MLIR_TRANSFORMS_MEM2REG_H
+
+#include "mlir/IR/Dominance.h"
+#include "mlir/IR/OpDefinition.h"
+
+namespace mlir {
+
+/// Represents a slot in memory. This is generated by an allocating operation
+/// (for example alloca).
+struct MemorySlot {
+  /// Pointer to the memory slot, used by operations to refer to it.
+  Value ptr;
+  /// Type of the value contained in the slot.
+  Type elemType;
+  /// Location of the slot in the source code. This may for example point to a
+  /// local variable representing a memory slot on the stack.
+  Location location;
+};
+
+/// Returned by operation promotion logic requesting the deletion of an
+/// operation.
+enum class DeletionKind {
+  /// Keep the operation after promotion.
+  Keep,
+  /// Delete the operation after promotion.
+  Delete,
+};
+
+} // namespace mlir
+
+#include "mlir/Transforms/Mem2Reg.h.inc"
+
+namespace mlir {
+
+/// Attempts to promote the memory slots of the provided allocators. Succeeds if
+/// at least one memory slot was promoted.
+LogicalResult
+tryToPromoteMemorySlots(ArrayRef<PromotableAllocationOpInterface> allocators,
+                        OpBuilder &builder, DominanceInfo &dominance);
+
+} // namespace mlir
+
+#endif // MLIR_TRANSFORMS_MEM2REG_H

mlir/include/mlir/Transforms/Mem2Reg.td

+//===-- Mem2Reg.td - Mem2Reg interfaces definitions --------*- tablegen -*-===//
+//
+// 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 MLIR_TRANSFORMS_MEM2REG
+#define MLIR_TRANSFORMS_MEM2REG
+
+include "mlir/IR/OpBase.td"
+
+def PromotableAllocationOpInterface
+    : OpInterface<"PromotableAllocationOpInterface"> {
+  let description = [{
+    Describes an operation allocating a memory slot that can be promoted into
+    SSA values.
+  }];
+  let cppNamespace = "::mlir";
+
+  let methods = [
+    InterfaceMethod<[{
+        Returns a list of memory slots for which promotion should be attempted.
+        This only considers the local semantics of the allocator, ignoring
+        whether the slot pointer is properly used or not. This allocator is the
+        "owner" of the returned slots, meaning no two allocators should return
+        the same slot. The content of the memory slot must only be reachable
+        using loads and stores to the provided slot pointer, no aliasing is
+        allowed.
+
+        Promotion of the slot will lead to the slot pointer no longer being
+        used, leaving the content of the memory slot unreachable.
+      }], "::llvm::SmallVector<::mlir::MemorySlot>", "getPromotableSlots",
+      (ins)
+    >,
+    InterfaceMethod<[{
+        Gets the default value of this memory slot. This value must outlive
+        the promotion and dominate all the uses of this slot's pointer. The
+        provided builder can be used to create the default value on the fly.
+      }], "::mlir::Value", "getDefaultValue",
+      (ins "::mlir::MemorySlot":$slot, "::mlir::OpBuilder &":$builder)
+    >,
+    InterfaceMethod<[{
+        Hook triggered for every new block argument added to a block.
+        This will only be called for slots declared by this operation.
+      }],
+      "void", "handleBlockArgument",
+      (ins
+        "::mlir::MemorySlot":$slot,
+        "::mlir::BlockArgument":$argument,
+        "::mlir::OpBuilder &":$builder
+      ), [{}], [{ return; }]
+    >,
+    InterfaceMethod<[{
+        Hook triggered once the promotion of a slot is complete. This can
+        also clean up the created default value if necessary.
+        This will only be called for slots declared by this operation.
+      }],
+      "void", "handlePromotionComplete",
+      (ins "::mlir::MemorySlot":$slot, "::mlir::Value":$defaultValue),
+      [{}], [{ return; }]
+    >,
+  ];
+}
+
+def PromotableMemOpInterface : OpInterface<"PromotableMemOpInterface"> {
+  let description = [{
+    Describes an operation that can load from memory slots and/or store
+    to memory slots. Loads and stores must be of whole values of the same
+    type as the slot itself.
+
+    If the same operation does both loads and stores on the same slot, the
+    load must semantically happen first.
+  }];
+  let cppNamespace = "::mlir";
+
+  let methods = [
+    InterfaceMethod<[{
+        Gets the value loaded from the provided memory slot, if any.
+        This method is only called on operations that use the slot.
+      }],
+      "::mlir::Value", "getLoaded",
+      (ins "::mlir::MemorySlot":$slot)
+    >,
+    InterfaceMethod<[{
+        Gets the value stored to the provided memory slot, if any.
+        This method is only called on operations that use the slot.
+      }],
+      "::mlir::Value", "getStored",
+      (ins "::mlir::MemorySlot":$slot)
+    >,
+  ];
+}
+
+def PromotableOpInterface : OpInterface<"PromotableOpInterface"> {
+  let description = [{
+    Describes an operation that can be transformed or deleted so it no longer
+    uses a provided value (blocking use), in case this would allow the promotion
+    of a memory slot.
+  }];
+  let cppNamespace = "::mlir";
+
+  let methods = [
+    InterfaceMethod<[{
+        Checks that this operation can be promoted to no longer use the provided
+        blocking uses, in the context of promoting `slot`.
+
+        If the removal procedure of the use will require that other uses get
+        removed, that dependency should be added to the `newBlockingUses`
+        argument. Dependent uses must only be uses of results of this operation.
+      }], "bool", "canUsesBeRemoved",
+      (ins "::mlir::MemorySlot":$slot,
+           "::llvm::SmallPtrSetImpl<::mlir::OpOperand *> &":$blockingUses,
+           "::llvm::SmallVectorImpl<::mlir::OpOperand *> &":$newBlockingUses)
+    >,
+    InterfaceMethod<[{
+        Transforms IR to ensure that the current operation does not use the provided
+        memory slot anymore. `reachingDefinition` contains the value currently
+        stored in the provided memory slot, immediately before the current
+        operation.
+
+        During the transformation, *no operation should be deleted*.
+        The operation can only schedule its own deletion by returning the
+        appropriate `DeletionKind`. The deletion must be legal assuming the
+        blocking uses passed through the `onlyIf` list in `canUseBeRemoved`
+        have been removed.
+
+        After calling this method, the blocking uses should have disappeared
+        or this operation should have scheduled its own deletion.
+
+        This method will only be called after ensuring promotion is allowed via
+        `canUseBeRemoved`. The requested blocking use removal may or may not
+        have been done at the point of calling this method, but it will be done
+        eventually.
+      }],
+      "::mlir::DeletionKind",
+      "removeBlockingUses",
+      (ins "::mlir::MemorySlot":$slot,
+           "::llvm::SmallPtrSetImpl<mlir::OpOperand *> &":$blockingUses,
+           "::mlir::OpBuilder &":$builder,
+           "::mlir::Value":$reachingDefinition)
+    >,
+  ];
+}
+
+
+#endif // MLIR_TRANSFORMS_MEM2REG

mlir/include/mlir/Transforms/Passes.h

 // Passes
 //===----------------------------------------------------------------------===//
 
 #define GEN_PASS_DECL_CANONICALIZER
 #define GEN_PASS_DECL_CONTROLFLOWSINK
 #define GEN_PASS_DECL_CSEPASS
 #define GEN_PASS_DECL_INLINER
 #define GEN_PASS_DECL_LOOPINVARIANTCODEMOTION
+#define GEN_PASS_DECL_MEM2REG
 #define GEN_PASS_DECL_PRINTIRPASS
 #define GEN_PASS_DECL_PRINTOPSTATS
 #define GEN_PASS_DECL_STRIPDEBUGINFO
 #define GEN_PASS_DECL_SCCP
 #define GEN_PASS_DECL_SYMBOLDCE
 #define GEN_PASS_DECL_SYMBOLPRIVATIZE
 #define GEN_PASS_DECL_TOPOLOGICALSORT
 #include "mlir/Transforms/Passes.h.inc"

mlir/include/mlir/Transforms/Passes.td

def LocationSnapshot : Pass<"snapshot-op-locations"> {
   ];
 }
 
 def LoopInvariantCodeMotion : Pass<"loop-invariant-code-motion"> {
   let summary = "Hoist loop invariant instructions outside of the loop";
   let constructor = "mlir::createLoopInvariantCodeMotionPass()";
 }
 
+def Mem2Reg : Pass<"mem2reg"> {
+  let summary = "Promotes memory slots into values.";
+  let description = [{
+    This pass removes loads out of and stores into a memory slot, and turns
+    them into direct uses of SSA values. This is done generically using the
+    `PromoteAllocationOpInterface`, `PromoteOpInterface` and
+    `PromoteMemOpInterface` interfaces.
+
+    This pass will attempt to compute which definitions of the content of
+    the memory slot reach operations that use the memory slot pointer. It
+    will rewire or remove operations that use the slot pointer so they no
+    longer use it. If any of this is not possible, the IR will be left
+    without mutation.
+
+    This pass only supports unstructured control-flow. Promotion of operations
+    within subregions will not happen.
+  }];
+}
+
 def PrintOpStats : Pass<"print-op-stats"> {
   let summary = "Print statistics of operations";
   let constructor = "mlir::createPrintOpStatsPass()";
   let options = [
     Option<"printAsJSON", "json", "bool", /*default=*/"false",
            "print the stats as JSON">
   ];
 }

mlir/lib/Dialect/LLVMIR/CMakeLists.txt

 add_subdirectory(Transforms)
 
 add_mlir_dialect_library(MLIRLLVMDialect
   IR/FunctionCallUtils.cpp
   IR/LLVMAttrs.cpp
   IR/LLVMDialect.cpp
   IR/LLVMInlining.cpp
   IR/LLVMInterfaces.cpp
+  IR/LLVMMem2Reg.cpp
   IR/LLVMTypes.cpp
   IR/LLVMTypeSyntax.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${MLIR_MAIN_INCLUDE_DIR}/mlir/Dialect/LLVMIR
 
   DEPENDS
   MLIRLLVMOpsIncGen

mlir/lib/Dialect/LLVMIR/IR/LLVMMem2Reg.cpp

+//===- LLVMMem2RegInterfaces.cpp - LLVM Interfaces --------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements Mem2Reg-related interfaces for LLVM dialect operations.
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Dialect/LLVMIR/LLVMDialect.h"
+#include "mlir/Transforms/Mem2Reg.h"
+
+using namespace mlir;
+
+//===--
+// Interfaces for AllocaOp
+//===--
+
+llvm::SmallVector<MemorySlot> LLVM::AllocaOp::getPromotableSlots() {
+  if (!getOperation()->getBlock()->isEntryBlock())
+    return {};
+
+  Type elemType =
+      getElemType() ? *getElemType() : getResult().getType().getElementType();
+  return {MemorySlot{getResult(), elemType, getLoc()}};
+}
+
+Value LLVM::AllocaOp::getDefaultValue(MemorySlot slot, OpBuilder &builder) {
+  OpBuilder::InsertionGuard builderGuard(builder);
+  builder.setInsertionPointAfter(*this);
+  return builder.create<LLVM::PoisonOp>(getLoc(), slot.elemType);
+}
+
+void LLVM::AllocaOp::handleBlockArgument(MemorySlot slot,
+                                         BlockArgument argument,
+                                         OpBuilder &builder) {
+  OpBuilder::InsertionGuard builderGuard(builder);
+  builder.setInsertionPointToStart(argument.getOwner());
+  for (Operation *user : getOperation()->getUsers())
+    if (auto declareOp = llvm::dyn_cast<LLVM::DbgDeclareOp>(user))
+      builder.create<LLVM::DbgValueOp>(declareOp.getLoc(), argument,
+                                       declareOp.getVarInfo());
+}
+
+void LLVM::AllocaOp::handlePromotionComplete(MemorySlot slot,
+                                             Value defaultValue) {
+  if (defaultValue.use_empty())
+    defaultValue.getDefiningOp()->erase();
+  erase();
+}
+
+//===--
+// Interfaces for LoadOp/StoreOp
+//===--
+
+Value LLVM::LoadOp::getLoaded(MemorySlot slot) {
+  if (getAddr() != slot.ptr)
+    return {};
+  return getResult();
+}
+
+Value LLVM::LoadOp::getStored(MemorySlot slot) { return {}; }
+
+Value LLVM::StoreOp::getLoaded(MemorySlot slot) { return {}; }
+
+Value LLVM::StoreOp::getStored(MemorySlot slot) {
+  if (getAddr() != slot.ptr)
+    return {};
+  return getValue();
+}
+
+bool LLVM::LoadOp::canUsesBeRemoved(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    SmallVectorImpl<OpOperand *> &newBlockingUses) {
+  if (blockingUses.size() != 1)
+    return false;
+  Value blockingUse = (*blockingUses.begin())->get();
+  // If the blocking use is the slot ptr itself, there will be enough
+  // context to reconstruct the result of the load at removal time, so it can
+  // be removed (provided it loads the exact stored value and is not
+  // volatile).
+  return blockingUse == slot.ptr && getAddr() == slot.ptr &&
+         getResult().getType() == slot.elemType && !getVolatile_();
+}
+
+DeletionKind
+LLVM::LoadOp::removeBlockingUses(MemorySlot slot,
+                                 SmallPtrSetImpl<OpOperand *> &blockingUses,
+                                 OpBuilder &builder, Value reachingDefinition) {
+  // `canUsesBeRemoved` checked this blocking use must be the loaded slot
+  // pointer.
+  getResult().replaceAllUsesWith(reachingDefinition);
+  return DeletionKind::Delete;
+}
+
+bool LLVM::StoreOp::canUsesBeRemoved(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    SmallVectorImpl<OpOperand *> &newBlockingUses) {
+  if (blockingUses.size() != 1)
+    return false;
+  Value blockingUse = (*blockingUses.begin())->get();
+  // If the blocking use is the slot ptr itself, dropping the store is
+  // fine, provided we are currently promoting its target value. Don't allow a
+  // store OF the slot pointer, only INTO the slot pointer.
+  return blockingUse == slot.ptr && getAddr() == slot.ptr &&
+         getValue() != slot.ptr && getValue().getType() == slot.elemType &&
+         !getVolatile_();
+}
+
+DeletionKind LLVM::StoreOp::removeBlockingUses(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    OpBuilder &builder, Value reachingDefinition) {
+  // `canUsesBeRemoved` checked this blocking use must be the stored slot
+  // pointer.
+  OpBuilder::InsertionGuard builderGuard(builder);
+  builder.setInsertionPointAfter(*this);
+  for (Operation *user : slot.ptr.getUsers())
+    if (auto declareOp = llvm::dyn_cast<LLVM::DbgDeclareOp>(user))
+      builder.create<LLVM::DbgValueOp>(declareOp->getLoc(), getValue(),
+                                       declareOp.getVarInfo());
+  return DeletionKind::Delete;
+}
+
+//===--
+// Interfaces for discardable OPs
+//===--
+
+/// Conditions the deletion of the operation to the removal of all its uses.
+static bool forwardToUsers(Operation *op,
+                           SmallVectorImpl<OpOperand *> &newBlockingUses) {
+  for (Value result : op->getResults())
+    for (OpOperand &use : result.getUses())
+      newBlockingUses.push_back(&use);
+  return true;
+}
+
+bool LLVM::BitcastOp::canUsesBeRemoved(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    SmallVectorImpl<OpOperand *> &newBlockingUses) {
+  return forwardToUsers(*this, newBlockingUses);
+}
+
+DeletionKind LLVM::BitcastOp::removeBlockingUses(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    OpBuilder &builder, Value reachingDefinition) {
+  return DeletionKind::Delete;
+}
+
+bool LLVM::AddrSpaceCastOp::canUsesBeRemoved(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    SmallVectorImpl<OpOperand *> &newBlockingUses) {
+  return forwardToUsers(*this, newBlockingUses);
+}
+
+DeletionKind LLVM::AddrSpaceCastOp::removeBlockingUses(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    OpBuilder &builder, Value reachingDefinition) {
+  return DeletionKind::Delete;
+}
+
+bool LLVM::LifetimeStartOp::canUsesBeRemoved(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    SmallVectorImpl<OpOperand *> &newBlockingUses) {
+  return forwardToUsers(*this, newBlockingUses);
+}
+
+DeletionKind LLVM::LifetimeStartOp::removeBlockingUses(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    OpBuilder &builder, Value reachingDefinition) {
+  return DeletionKind::Delete;
+}
+
+bool LLVM::LifetimeEndOp::canUsesBeRemoved(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    SmallVectorImpl<OpOperand *> &newBlockingUses) {
+  return forwardToUsers(*this, newBlockingUses);
+}
+
+DeletionKind LLVM::LifetimeEndOp::removeBlockingUses(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    OpBuilder &builder, Value reachingDefinition) {
+  return DeletionKind::Delete;
+}
+
+bool LLVM::DbgDeclareOp::canUsesBeRemoved(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    SmallVectorImpl<OpOperand *> &newBlockingUses) {
+  return forwardToUsers(*this, newBlockingUses);
+}
+
+DeletionKind LLVM::DbgDeclareOp::removeBlockingUses(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    OpBuilder &builder, Value reachingDefinition) {
+  return DeletionKind::Delete;
+}
+
+static bool hasAllZeroIndices(LLVM::GEPOp gepOp) {
+  return llvm::all_of(gepOp.getIndices(), [](auto index) {
+    auto indexAttr = index.template dyn_cast<IntegerAttr>();
+    return indexAttr && indexAttr.getValue() == 0;
+  });
+}
+
+bool LLVM::GEPOp::canUsesBeRemoved(
+    MemorySlot slot, SmallPtrSetImpl<OpOperand *> &blockingUses,
+    SmallVectorImpl<OpOperand *> &newBlockingUses) {
+  // GEP can be removed as long as it is a no-op and its users can be removed.
+  if (!hasAllZeroIndices(*this))
+    return false;
+
+  for (OpOperand &use : getResult().getUses())
+    newBlockingUses.push_back(&use);
+
+  return true;
+}
+
+DeletionKind
+LLVM::GEPOp::removeBlockingUses(MemorySlot slot,
+                                SmallPtrSetImpl<OpOperand *> &blockingUses,
+                                OpBuilder &builder, Value reachingDefinition) {
+  return DeletionKind::Delete;
+}

mlir/lib/Transforms/CMakeLists.txt

 add_subdirectory(Utils)
 
 add_mlir_library(MLIRTransforms
   Canonicalizer.cpp
   ControlFlowSink.cpp
   CSE.cpp
   GenerateRuntimeVerification.cpp
   Inliner.cpp
   LocationSnapshot.cpp
   LoopInvariantCodeMotion.cpp
+  Mem2Reg.cpp
   OpStats.cpp
   PrintIR.cpp
   SCCP.cpp
   StripDebugInfo.cpp
   SymbolDCE.cpp
   SymbolPrivatize.cpp
   TopologicalSort.cpp
   ViewOpGraph.cpp

mlir/lib/Transforms/Mem2Reg.cpp

+//===- Mem2Reg.cpp - Promotes memory slots into values ----------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Transforms/Mem2Reg.h"
+#include "mlir/Analysis/SliceAnalysis.h"
+#include "mlir/Dialect/LLVMIR/LLVMDialect.h"
+#include "mlir/Transforms/Passes.h"
+#include "llvm/Support/GenericIteratedDominanceFrontier.h"
+
+namespace mlir {
+#define GEN_PASS_DEF_MEM2REG
+#include "mlir/Transforms/Passes.h.inc"
+} // namespace mlir
+
+#include "mlir/Transforms/Mem2Reg.cpp.inc"
+
+using namespace mlir;
+
+/// mem2reg
+///
+/// This pass turns unnecessary uses of automatically allocated memory slots
+/// into direct Value-based operations. For example, it will simplify storing a
+/// constant in a memory slot to immediately load it to a direct use of that
+/// constant. In other words, given a memory slot addressed by a non-aliased
+/// "pointer" Value, mem2reg removes all the uses of that pointer.
+///
+/// Within a block, this is done by following the chain of stores and loads of
+/// the slot and replacing the results of loads with the values previously
+/// stored. If a load happens before any other store, a poison value is used
+/// instead.
+///
+/// Control flow can create situations where a load could be replaced by
+/// multiple possible stores depending on the control flow path taken. As a
+/// result, this pass must introduce new block arguments in some blocks to
+/// accomodate for the multiple possible definitions. Each predecessor will
+/// populate the block argument with the definition reached at its end. With
+/// this, the value stored can be well defined at block boundaries, allowing
+/// the propagation of replacement through blocks.
+///
+/// This pass computes this transformation in four main steps:
+/// - A first step computes the list of operations that transitively use the
+/// memory slot we would like to promote. The purpose of this phase is to
+/// identify which uses must be removed to promote the slot, either by rewiring
+/// the user or deleting it. Naturally, direct uses of the slot must be removed.
+/// Sometimes additional uses must also be removed: this is notably the case
+/// when a direct user of the slot cannot rewire its use and must delete itself,
+/// and thus must make its users no longer use it. If any of those uses cannot
+/// be removed by their users in any way, promotion cannot continue: this is
+/// decided at this step.
+/// - A second step computes the list of blocks where a block argument will be
+/// needed ("merge points") without mutating the IR. These blocks are the blocks
+/// leading to a definition clash between two predecessors. Such blocks happen
+/// to be the Iterated Dominance Frontier (IDF) of the set of blocks containing
+/// a store, as they represent the point where a clear defining dominator stops
+/// existing. Computing this information in advance allows making sure the
+/// terminators that will forward values are capable of doing so (inability to
+/// do so aborts promotion at this step).
+/// - A third step computes the reaching definition of the memory slot at each
+/// blocking user. This is the core of the mem2reg algorithm, also known as
+/// load-store forwarding. This analyses loads and stores and propagates which
+/// value must be stored in the slot at each blocking user.  This is achieved by
+/// doing a depth-first walk of the dominator tree of the function. This is
+/// sufficient because the reaching definition at the beginning of a block is
+/// either its new block argument if it is a merge block, or the definition
+/// reaching the end of its immediate dominator (parent in the dominator tree).
+/// We can therefore propagate this information down the dominator tree to
+/// proceed with renaming within blocks.
+/// - The final fourth step uses the reaching definition to remove blocking uses
+/// in topological order.
+///
+/// The two first steps do not mutate IR because promotion can still be aborted
+/// at this point. Once the two last steps are reached, promotion is guaranteed
+/// to succeed, allowing to start mutating IR.
+///
+/// For further reading, chapter three of SSA-based Compiler Design [1]
+/// showcases SSA construction, where mem2reg is an adaptation of the same
+/// process.
+///
+/// [1]: Rastello F. & Bouchez Tichadou F., SSA-based Compiler Design (2022),
+///      Springer.
+
+namespace {
+
+/// The SlotPromoter handles the state of promoting a memory slot. It wraps a
+/// slot and its associated allocator, along with analysis results related to
+/// the slot.
+class SlotPromoter {
+public:
+  SlotPromoter(MemorySlot slot, PromotableAllocationOpInterface allocator,
+               OpBuilder &builder, DominanceInfo &dominance)
+      : slot(slot), allocator(allocator), builder(builder),
+        dominance(dominance) {}
+
+  /// Prepare data for the promotion of the slot while checking if it can be
+  /// promoted. Succeeds if the slot can be promoted. This method does not
+  /// mutate IR.
+  LogicalResult prepareSlotPromotion();
+
+  /// Actually promotes the slot by mutating IR. This method must only be
+  /// called after a successful call to `SlotPromoter::prepareSlotPromotion`.
+  /// Promoting a slot does not invalidate the preparation of other slots.
+  void promoteSlot();
+
+private:
+  /// This is the first step of the promotion algorithm.
+  /// Computes the transitive uses of the slot that block promotion. This finds
+  /// uses that would block the promotion, checks that the operation has a
+  /// solution to remove the blocking use, and potentially forwards the analysis
+  /// if the operation needs further blocking uses resolved to resolve its own
+  /// uses (typically, removing its users because it will delete itself to
+  /// resolve its own blocking uses). This will fail if one of the transitive
+  /// users cannot remove a requested use, and should prevent promotion.
+  LogicalResult computeBlockingUses();
+
+  /// Computes in which blocks the value stored in the slot is actually used,
+  /// meaning blocks leading to a load. This method uses `definingBlocks`, the
+  /// set of blocks containing a store to the slot (defining the value of the
+  /// slot).
+  SmallPtrSet<Block *, 16>
+  computeSlotLiveIn(SmallPtrSetImpl<Block *> &definingBlocks);
+
+  /// This is the second step of the promotion algorithm.
+  /// Computes the points in which multiple re-definitions of the slot's value
+  /// (stores) may conflict.
+  void computeMergePoints();
+
+  /// Ensures predecessors of merge points can properly provide their current
+  /// definition of the value stored in the slot to the merge point. This can
+  /// notably be an issue if the terminator used does not have the ability to
+  /// forward values through block operands.
+  bool areMergePointsUsable();
+
+  /// Computes the reaching definition for all the operations that require
+  /// promotion. `reachingDef` is the value the slot should contain at the
+  /// beginning of the block. This method returns the reached definition at the
+  /// end of the block.
+  Value computeReachingDefInBlock(Block *block, Value reachingDef);
+
+  /// This is the third step of the promotion algorithm.
+  /// Computes the reaching definition for all the operations that require
+  /// promotion. `reachingDef` corresponds to the initial value the
+  /// slot will contain before any write, typically a poison value.
+  void computeReachingDefInRegion(Region *region, Value reachingDef);
+
+  /// This is the fourth step of the promotion algorithm.
+  /// Removes the blocking uses of the slot, in topological order.
+  void removeBlockingUses(Value defaultValue);
+
+  MemorySlot slot;
+  PromotableAllocationOpInterface allocator;
+  OpBuilder &builder;
+  SmallPtrSet<Block *, 8> mergePoints;
+  /// Contains, for each operation, which uses must be eliminated by promotion.
+  /// This is a DAG structure because an operation that must eliminate some of
+  /// its uses always comes from a request from an operation that must
+  /// eliminate some of its own uses.
+  DenseMap<Operation *, SmallPtrSet<OpOperand *, 4>> userToBlockingUses;
+  /// Contains the reaching definition at this operation. Reaching definitions
+  /// are only computed for operations in the promote DAG.
+  DenseMap<PromotableOpInterface, Value> reachingDefs;
+  DominanceInfo &dominance;
+};
+
+} // namespace
+
+template <typename K, typename V>
+static V &getOrInsertDefault(DenseMap<K, V> &map, K key) {
+  return map.try_emplace(key).first->second;
+}
+
+LogicalResult SlotPromoter::computeBlockingUses() {
+  // The promotion of an operation may require the promotion of further
+  // operations (typically, removing operations that use an operation that must
+  // delete itself). We thus need to start from the use of the slot pointer and
+  // propagate further requests through the forward slice.
+
+  // First insert that all immediate users of the slot pointer must no longer
+  // use it.
+  for (OpOperand &use : slot.ptr.getUses()) {
+    SmallPtrSet<OpOperand *, 4> &blockingUses =
+        getOrInsertDefault(userToBlockingUses, use.getOwner());
+    blockingUses.insert(&use);
+  }
+
+  // Then, propagate the requirements for the removal of uses. The
+  // topologically-sorted forward slice allows for all blocking uses of an
+  // operation to have been computed before we reach it. Operations are
+  // traversed in topological order of their uses, starting from the slot
+  // pointer.
+  SetVector<Operation *> forwardSlice;
+  mlir::getForwardSlice(slot.ptr, &forwardSlice);
+  for (Operation *user : forwardSlice) {
+    // If the next operation has no blocking uses, everything is fine.
+    if (!userToBlockingUses.contains(user))
+      continue;
+
+    SmallPtrSet<OpOperand *, 4> &blockingUses = userToBlockingUses[user];
+    auto promotable = llvm::dyn_cast<PromotableOpInterface>(user);
+
+    // An operation that has blocking uses must be promoted. If it is not
+    // promotable, promotion must fail.
+    if (!promotable)
+      return failure();
+
+    SmallVector<OpOperand *> newBlockingUses;
+    // If the operation decides it cannot deal with removing the blocking uses,
+    // promotion must fail.
+    if (!promotable.canUsesBeRemoved(slot, blockingUses, newBlockingUses))
+      return failure();
+
+    // Then, register any new blocking uses for coming operations.
+    for (OpOperand *blockingUse : newBlockingUses) {
+      assert(llvm::find(promotable->getResults(), blockingUse->get()) !=
+             promotable->result_end());
+
+      SmallPtrSetImpl<OpOperand *> &newUserBlockingUseSet =
+          getOrInsertDefault(userToBlockingUses, blockingUse->getOwner());
+      newUserBlockingUseSet.insert(blockingUse);
+    }
+  }
+
+  // Because this pass currently only supports analysing the parent region of
+  // the slot pointer, if a promotable op that needs promotion is outside of
+  // this region, promotion must fail because it will be impossible to provide a
+  // valid `reachingDef` for it.
+  for (auto &[toPromote, _] : userToBlockingUses)
+    if (toPromote->getParentRegion() != slot.ptr.getParentRegion())
+      return failure();
+
+  return success();
+}
+
+SmallPtrSet<Block *, 16>
+SlotPromoter::computeSlotLiveIn(SmallPtrSetImpl<Block *> &definingBlocks) {
+  SmallPtrSet<Block *, 16> liveIn;
+
+  // The worklist contains blocks in which it is known that the slot value is
+  // live-in. The further blocks where this value is live-in will be inferred
+  // from these.
+  SmallVector<Block *> liveInWorkList;
+
+  // Blocks with a load before any other store to the slot are the starting
+  // points of the analysis. The slot value is definitely live-in in those
+  // blocks.
+  SmallPtrSet<Block *, 16> visited;
+  for (Operation *user : slot.ptr.getUsers()) {
+    if (visited.contains(user->getBlock()))
+      continue;
+    visited.insert(user->getBlock());
+
+    for (Operation &op : user->getBlock()->getOperations()) {
+      if (auto memOp = llvm::dyn_cast<PromotableMemOpInterface>(op)) {
+        // If this operation loads the slot, it is loading from it before
+        // ever writing to it, so the value is live-in in this block.
+        if (memOp.getLoaded(slot)) {
+          liveInWorkList.push_back(user->getBlock());
+          break;
+        }
+
+        // If we store to the slot, further loads will see that value.
+        // Because we did not meet any load before, the value is not live-in.
+        if (memOp.getStored(slot))
+          break;
+      }
+    }
+  }
+
+  // The information is then propagated to the predecessors until a def site
+  // (store) is found.
+  while (!liveInWorkList.empty()) {
+    Block *liveInBlock = liveInWorkList.pop_back_val();
+
+    if (!liveIn.insert(liveInBlock).second)
+      continue;
+
+    // If a predecessor is a defining block, either:
+    // - It has a load before its first store, in which case it is live-in but
+    // has already been processed in the initialisation step.
+    // - It has a store before any load, in which case it is not live-in.
+    // We can thus at this stage insert to the worklist only predecessors that
+    // are not defining blocks.
+    for (Block *pred : liveInBlock->getPredecessors())
+      if (!definingBlocks.contains(pred))
+        liveInWorkList.push_back(pred);
+  }
+
+  return liveIn;
+}
+
+using IDFCalculator = llvm::IDFCalculatorBase<Block, false>;
+void SlotPromoter::computeMergePoints() {
+  if (slot.ptr.getParentRegion()->hasOneBlock())
+    return;
+
+  IDFCalculator idfCalculator(dominance.getDomTree(slot.ptr.getParentRegion()));
+
+  SmallPtrSet<Block *, 16> definingBlocks;
+  for (Operation *user : slot.ptr.getUsers())
+    if (auto storeOp = llvm::dyn_cast<PromotableMemOpInterface>(user))
+      if (storeOp.getStored(slot))
+        definingBlocks.insert(user->getBlock());
+
+  idfCalculator.setDefiningBlocks(definingBlocks);
+
+  SmallPtrSet<Block *, 16> liveIn = computeSlotLiveIn(definingBlocks);
+  idfCalculator.setLiveInBlocks(liveIn);
+
+  SmallVector<Block *> mergePointsVec;
+  idfCalculator.calculate(mergePointsVec);
+
+  mergePoints.insert(mergePointsVec.begin(), mergePointsVec.end());
+}
+
+bool SlotPromoter::areMergePointsUsable() {
+  for (Block *mergePoint : mergePoints)
+    for (Block *pred : mergePoint->getPredecessors())
+      if (!llvm::isa<BranchOpInterface>(pred->getTerminator()))
+        return false;
+
+  return true;
+}
+
+Value SlotPromoter::computeReachingDefInBlock(Block *block, Value reachingDef) {
+  for (Operation &op : block->getOperations()) {
+    if (userToBlockingUses.contains(&op))
+      reachingDefs.insert({&op, reachingDef});
+
+    if (auto memOp = llvm::dyn_cast<PromotableMemOpInterface>(op))
+      if (Value stored = memOp.getStored(slot))
+        reachingDef = stored;
+  }
+
+  return reachingDef;
+}
+
+void SlotPromoter::computeReachingDefInRegion(Region *region,
+                                              Value reachingDef) {
+  if (region->hasOneBlock()) {
+    computeReachingDefInBlock(&region->front(), reachingDef);
+    return;
+  }
+
+  struct DfsJob {
+    llvm::DomTreeNodeBase<Block> *block;
+    Value reachingDef;
+  };
+
+  SmallVector<DfsJob> dfsStack;
+
+  auto &domTree = dominance.getDomTree(slot.ptr.getParentRegion());
+
+  dfsStack.emplace_back<DfsJob>(
+      {domTree.getNode(&region->front()), reachingDef});
+
+  while (!dfsStack.empty()) {
+    DfsJob job = dfsStack.pop_back_val();
+    Block *block = job.block->getBlock();
+
+    if (mergePoints.contains(block)) {
+      BlockArgument blockArgument =
+          block->addArgument(slot.elemType, slot.location);
+      allocator.handleBlockArgument(slot, blockArgument, builder);
+      job.reachingDef = blockArgument;
+    }
+
+    job.reachingDef = computeReachingDefInBlock(block, job.reachingDef);
+
+    if (auto terminator =
+            llvm::dyn_cast<BranchOpInterface>(block->getTerminator())) {
+      for (BlockOperand &blockOperand : terminator->getBlockOperands()) {
+        if (mergePoints.contains(blockOperand.get())) {
+          terminator.getSuccessorOperands(blockOperand.getOperandNumber())
+              .append(job.reachingDef);
+        }
+      }
+    }
+
+    for (auto *child : job.block->children()) {
+      dfsStack.emplace_back<DfsJob>({child, job.reachingDef});
+    }
+  }
+}
+
+void SlotPromoter::removeBlockingUses(Value defaultValue) {
+  llvm::SetVector<Operation *> usersToRemoveUses;
+  for (auto &[user, _] : userToBlockingUses)
+    usersToRemoveUses.insert(user);
+  SetVector<Operation *> sortedUsersToRemoveUses =
+      mlir::topologicalSort(usersToRemoveUses);
+
+  llvm::SmallVector<Operation *> toErase;
+  for (Operation *op : llvm::reverse(sortedUsersToRemoveUses)) {
+    auto toPromote = llvm::cast<PromotableOpInterface>(op);
+    Value reachingDef = reachingDefs.lookup(toPromote);
+
+    // If no reaching definition is known, this use is outside the reach of the
+    // slot. The default value should thus be used.
+    if (!reachingDef)
+      reachingDef = defaultValue;
+
+    if (toPromote.removeBlockingUses(slot, userToBlockingUses[toPromote],
+                                     builder,
+                                     reachingDef) == DeletionKind::Delete)
+      toErase.push_back(op);
+  }
+
+  for (Operation *toEraseOp : toErase)
+    toEraseOp->erase();
+
+  assert(slot.ptr.use_empty() &&
+         "after promotion, the slot pointer should not be used anymore");
+}
+
+void SlotPromoter::promoteSlot() {
+  Value defaultValue = allocator.getDefaultValue(slot, builder);
+
+  computeReachingDefInRegion(slot.ptr.getParentRegion(), defaultValue);
+
+  // Now that reaching definitions are known, remove all users.
+  removeBlockingUses(defaultValue);
+
+  // Update terminators in dead branches to forward default if they are
+  // succeeded by a merge points.
+  for (Block *mergePoint : mergePoints) {
+    for (BlockOperand &use : mergePoint->getUses()) {
+      auto user = llvm::cast<BranchOpInterface>(use.getOwner());
+      SuccessorOperands succOperands =
+          user.getSuccessorOperands(use.getOperandNumber());
+      assert(succOperands.size() == mergePoint->getNumArguments() ||
+             succOperands.size() + 1 == mergePoint->getNumArguments());
+      if (succOperands.size() + 1 == mergePoint->getNumArguments())
+        succOperands.append(defaultValue);
+    }
+  }
+
+  allocator.handlePromotionComplete(slot, defaultValue);
+}
+
+LogicalResult SlotPromoter::prepareSlotPromotion() {
+  // First, find the set of operations that will need to be changed for the
+  // promotion to happen. These operations need to resolve some of their uses,
+  // either by rewiring them or simply deleting themselves. If any of them
+  // cannot find a way to resolve their blocking uses, we abort the promotion.
+  if (failed(computeBlockingUses()))
+    return failure();
+
+  // Then, compute blocks in which two or more definitions of the allocated
+  // variable may conflict. These blocks will need a new block argument to
+  // accomodate this.
+  computeMergePoints();
+
+  // The slot can be promoted if the block arguments to be created can
+  // actually be populated with values, which may not be possible depending
+  // on their predecessors.
+  return success(areMergePointsUsable());
+}
+
+LogicalResult mlir::tryToPromoteMemorySlots(
+    ArrayRef<PromotableAllocationOpInterface> allocators, OpBuilder &builder,
+    DominanceInfo &dominance) {
+  // Actual promotion may invalidate the dominance analysis, so slot promotion
+  // is prepated in batches.
+  SmallVector<SlotPromoter> toPromote;
+  for (PromotableAllocationOpInterface allocator : allocators) {
+    for (MemorySlot slot : allocator.getPromotableSlots()) {
+      if (slot.ptr.use_empty())
+        continue;
+
+      SlotPromoter promoter(slot, allocator, builder, dominance);
+      if (succeeded(promoter.prepareSlotPromotion()))
+        toPromote.emplace_back(std::move(promoter));
+    }
+  }
+
+  for (SlotPromoter &promoter : toPromote)
+    promoter.promoteSlot();
+
+  return success(!toPromote.empty());
+}
+
+namespace {
+
+struct Mem2Reg : public impl::Mem2RegBase<Mem2Reg> {
+  void runOnOperation() override {
+    Operation *scopeOp = getOperation();
+    bool changed = false;
+
+    for (Region &region : scopeOp->getRegions()) {
+      if (region.getBlocks().empty())
+        continue;
+
+      OpBuilder builder(&region.front(), region.front().begin());
+
+      // Promoting a slot can allow for further promotion of other slots,
+      // promotion is tried until no promotion succeeds.
+      while (true) {
+        DominanceInfo &dominance = getAnalysis<DominanceInfo>();
+
+        SmallVector<PromotableAllocationOpInterface> allocators;
+        // Build a list of allocators to attempt to promote the slots of.
+        for (Block &block : region)
+          for (Operation &op : block.getOperations())
+            if (auto allocator =
+                    llvm::dyn_cast<PromotableAllocationOpInterface>(op))
+              allocators.emplace_back(allocator);
+
+        // Attempt promoting until no promotion succeeds.
+        if (failed(tryToPromoteMemorySlots(allocators, builder, dominance)))
+          break;
+
+        changed = true;
+        getAnalysisManager().invalidate({});
+      }
+    }
+
+    if (!changed)
+      markAllAnalysesPreserved();
+  }
+};
+
+} // namespace

mlir/test/Transforms/mem2reg-llvmir-dbginfo.mlir

+// RUN: mlir-opt %s --pass-pipeline='builtin.module(llvm.func(mem2reg))' | FileCheck %s
+
+llvm.func @use(i64)
+llvm.func @use_ptr(!llvm.ptr)
+
+#di_basic_type = #llvm.di_basic_type<tag = DW_TAG_base_type, name = "ptr sized type", sizeInBits = 64>
+#di_file = #llvm.di_file<"test.ll" in "">
+#di_compile_unit = #llvm.di_compile_unit<sourceLanguage = DW_LANG_C_plus_plus_14, file = #di_file, producer = "clang", isOptimized = false, emissionKind = Full>
+#di_subprogram = #llvm.di_subprogram<compileUnit = #di_compile_unit, scope = #di_file, name = "blah", linkageName = "blah", file = #di_file, line = 7, subprogramFlags = Definition>
+// CHECK: #[[$VAR:.*]] = #llvm.di_local_variable<{{.*}}name = "ptr sized var"{{.*}}>
+#di_local_variable = #llvm.di_local_variable<scope = #di_subprogram, name = "ptr sized var", file = #di_file, line = 7, arg = 1, type = #di_basic_type>
+#di_local_variable_2 = #llvm.di_local_variable<scope = #di_subprogram, name = "ptr sized var 2", file = #di_file, line = 7, arg = 1, type = #di_basic_type>
+
+// CHECK-LABEL: llvm.func @basic_store_load
+llvm.func @basic_store_load(%arg0: i64) -> i64 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  // CHECK-NOT: = llvm.alloca
+  %1 = llvm.alloca %0 x i64 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  // CHECK-NOT: llvm.store
+  llvm.store %arg0, %1 {alignment = 4 : i64} : i64, !llvm.ptr
+  // CHECK-NOT: llvm.intr.dbg.declare
+  llvm.intr.dbg.declare #di_local_variable = %1 : !llvm.ptr
+  // CHECK: llvm.intr.dbg.value #[[$VAR]] = %[[LOADED:.*]] : i64
+  // CHECK-NOT: llvm.intr.dbg.value
+  // CHECK-NOT: llvm.intr.dbg.declare
+  // CHECK-NOT: llvm.store
+  %2 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i64
+  // CHECK: llvm.return %[[LOADED]] : i64
+  llvm.return %2 : i64
+}
+
+// CHECK-LABEL: llvm.func @block_argument_value
+// CHECK-SAME: (%[[ARG0:.*]]: i64, {{.*}})
+llvm.func @block_argument_value(%arg0: i64, %arg1: i1) -> i64 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  // CHECK-NOT: = llvm.alloca
+  %1 = llvm.alloca %0 x i64 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  // CHECK-NOT: llvm.intr.dbg.declare
+  llvm.intr.dbg.declare #di_local_variable = %1 : !llvm.ptr
+  llvm.cond_br %arg1, ^bb1, ^bb2
+// CHECK: ^{{.*}}:
+^bb1:
+  // CHECK: llvm.intr.dbg.value #[[$VAR]] = %[[ARG0]]
+  // CHECK-NOT: llvm.intr.dbg.value
+  llvm.store %arg0, %1 {alignment = 4 : i64} : i64, !llvm.ptr
+  llvm.br ^bb2
+// CHECK: ^{{.*}}(%[[BLOCKARG:.*]]: i64):
+^bb2:
+  // CHECK: llvm.intr.dbg.value #[[$VAR]] = %[[BLOCKARG]]
+  %2 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i64
+  llvm.return %2 : i64
+}
+
+// CHECK-LABEL: llvm.func @double_block_argument_value
+// CHECK-SAME: (%[[ARG0:.*]]: i64, {{.*}})
+llvm.func @double_block_argument_value(%arg0: i64, %arg1: i1) -> i64 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  // CHECK-NOT: = llvm.alloca
+  %1 = llvm.alloca %0 x i64 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  // CHECK-NOT: llvm.intr.dbg.declare
+  llvm.intr.dbg.declare #di_local_variable = %1 : !llvm.ptr
+  llvm.cond_br %arg1, ^bb1, ^bb2
+// CHECK: ^{{.*}}(%[[BLOCKARG1:.*]]: i64):
+^bb1:
+  // CHECK: llvm.intr.dbg.value #[[$VAR]] = %[[BLOCKARG1]]
+  %2 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i64
+  llvm.call @use(%2) : (i64) -> ()
+  // CHECK: llvm.intr.dbg.value #[[$VAR]] = %[[ARG0]]
+  llvm.store %arg0, %1 {alignment = 4 : i64} : i64, !llvm.ptr
+  llvm.br ^bb2
+  // CHECK-NOT: llvm.intr.dbg.value
+// CHECK: ^{{.*}}(%[[BLOCKARG2:.*]]: i64):
+^bb2:
+  // CHECK: llvm.intr.dbg.value #[[$VAR]] = %[[BLOCKARG2]]
+  llvm.br ^bb1
+}
+
+// CHECK-LABEL: llvm.func @always_drop_promoted_declare
+// CHECK-NOT: = llvm.alloca
+// CHECK-NOT: llvm.intr.dbg.
+llvm.func @always_drop_promoted_declare() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.alloca %0 x i64 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  llvm.intr.dbg.declare #di_local_variable = %1 : !llvm.ptr
+  llvm.return
+}
+
+// CHECK-LABEL: llvm.func @keep_dbg_if_not_promoted
+llvm.func @keep_dbg_if_not_promoted() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  // CHECK: %[[ALLOCA:.*]] = llvm.alloca
+  %1 = llvm.alloca %0 x i64 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  // CHECK-NOT: = llvm.alloca
+  // CHECK-NOT: llvm.intr.dbg.declare
+  // CHECK: llvm.intr.dbg.declare #[[$VAR]] = %[[ALLOCA]]
+  // CHECK-NOT: = llvm.alloca
+  // CHECK-NOT: llvm.intr.dbg.declare
+  // CHECK: llvm.call @use_ptr(%[[ALLOCA]])
+  // CHECK-NOT: = llvm.alloca
+  // CHECK-NOT: llvm.intr.dbg.declare
+  llvm.intr.dbg.declare #di_local_variable = %1 : !llvm.ptr
+  %2 = llvm.alloca %0 x i64 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  llvm.intr.dbg.declare #di_local_variable_2 = %2 : !llvm.ptr
+  llvm.call @use_ptr(%1) : (!llvm.ptr) -> ()
+  llvm.return
+}

mlir/test/Transforms/mem2reg-llvmir.mlir

+// RUN: mlir-opt %s --pass-pipeline="builtin.module(llvm.func(mem2reg))" --split-input-file | FileCheck %s
+
+// CHECK-LABEL: llvm.func @default_value
+llvm.func @default_value() -> i32 {
+  // CHECK: %[[POISON:.*]] = llvm.mlir.poison : i32
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  %2 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i32
+  // CHECK: llvm.return %[[POISON]] : i32
+  llvm.return %2 : i32
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @store_of_ptr
+llvm.func @store_of_ptr() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(4 : i32) : i32
+  %2 = llvm.mlir.null : !llvm.ptr
+  // CHECK: %[[ALLOCA:.*]] = llvm.alloca
+  %3 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  // CHECK: llvm.store %{{.*}}, %[[ALLOCA]]
+  llvm.store %1, %3 {alignment = 4 : i64} : i32, !llvm.ptr
+  // CHECK: llvm.store %[[ALLOCA]], %{{.*}}
+  llvm.store %3, %2 {alignment = 8 : i64} : !llvm.ptr, !llvm.ptr
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @unreachable
+llvm.func @unreachable() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(0 : i32) : i32
+  // CHECK-NOT: = llvm.alloca
+  %2 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.return
+
+// CHECK: ^{{.*}}:
+// CHECK-NEXT: llvm.return
+^bb1:  // no predecessors
+  llvm.store %1, %2 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @unreachable_in_loop
+llvm.func @unreachable_in_loop() -> i32 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(6 : i32) : i32
+  %2 = llvm.mlir.constant(5 : i32) : i32
+  %3 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.store %1, %3 {alignment = 4 : i64} : i32, !llvm.ptr
+  // CHECK: llvm.br ^[[LOOP:.*]]
+  llvm.br ^bb1
+  
+// CHECK: ^[[LOOP]]:
+^bb1:  // 2 preds: ^bb0, ^bb3
+  // CHECK-NEXT: llvm.br ^[[ENDOFLOOP:.*]]
+  llvm.store %2, %3 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.br ^bb3
+
+// CHECK: ^[[UNREACHABLE:.*]]:
+^bb2:  // no predecessors
+  // CHECK-NEXT: llvm.br ^[[ENDOFLOOP]]
+  llvm.br ^bb3
+  
+// CHECK: ^[[ENDOFLOOP]]:
+^bb3:  // 2 preds: ^bb1, ^bb2
+  // CHECK-NEXT: llvm.br ^[[LOOP]]
+  llvm.br ^bb1
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @branching
+llvm.func @branching(%arg0: i1, %arg1: i1) -> i32 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(2 : i32) : i32
+  %2 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  // CHECK: llvm.cond_br %{{.*}}, ^[[bb2:.*]](%{{.*}} : i32), ^{{.*}}
+  llvm.cond_br %arg0, ^bb2, ^bb1
+^bb1:  // pred: ^bb0
+  llvm.store %1, %2 {alignment = 4 : i64} : i32, !llvm.ptr
+  // CHECK: llvm.cond_br %{{.*}}, ^[[bb2]](%{{.*}} : i32), ^[[bb2]](%{{.*}} : i32)
+  llvm.cond_br %arg1, ^bb2, ^bb2
+// CHECK: ^[[bb2]](%[[v3:.*]]: i32):
+^bb2:  // 3 preds: ^bb0, ^bb1, ^bb1
+  %3 = llvm.load %2 {alignment = 4 : i64} : !llvm.ptr -> i32
+  // CHECK: llvm.return %[[v3]] : i32
+  llvm.return %3 : i32
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @recursive_alloca
+// CHECK-NOT: = llvm.alloca
+llvm.func @recursive_alloca() -> i32 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(0 : i32) : i32
+  %2 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  %3 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  %4 = llvm.alloca %0 x !llvm.ptr {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  llvm.store %1, %3 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.store %3, %4 {alignment = 8 : i64} : !llvm.ptr, !llvm.ptr
+  %5 = llvm.load %4 {alignment = 8 : i64} : !llvm.ptr -> !llvm.ptr
+  %6 = llvm.load %5 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.store %6, %2 {alignment = 4 : i64} : i32, !llvm.ptr
+  %7 = llvm.load %2 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.return %7 : i32
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @reset_in_branch
+// CHECK-NOT: = llvm.alloca
+// CHECK-NOT: ^{{.*}}({{.*}}):
+llvm.func @reset_in_branch(%arg0: i32, %arg1: i1) {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(true) : i1
+  %2 = llvm.mlir.constant(false) : i1
+  %3 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.store %arg0, %3 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.cond_br %arg1, ^bb1, ^bb2
+^bb1:  // pred: ^bb0
+  llvm.store %arg0, %3 {alignment = 4 : i64} : i32, !llvm.ptr
+  %4 = llvm.load %3 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.call @reset_in_branch(%4, %2) : (i32, i1) -> ()
+  llvm.br ^bb3
+^bb2:  // pred: ^bb0
+  %5 = llvm.load %3 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.call @reset_in_branch(%5, %1) : (i32, i1) -> ()
+  llvm.br ^bb3
+^bb3:  // 2 preds: ^bb1, ^bb2
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @intertwined_alloca
+// CHECK-NOT: = llvm.alloca
+llvm.func @intertwined_alloca(%arg0: !llvm.ptr, %arg1: i32) {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(0 : i32) : i32
+  %2 = llvm.alloca %0 x !llvm.ptr {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  %3 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  %4 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  %5 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  %6 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.store %arg0, %2 {alignment = 8 : i64} : !llvm.ptr, !llvm.ptr
+  llvm.store %arg1, %3 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.store %1, %4 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.br ^bb1
+^bb1:  // 2 preds: ^bb0, ^bb4
+  %7 = llvm.load %3 {alignment = 4 : i64} : !llvm.ptr -> i32
+  %8 = llvm.add %7, %0  : i32
+  %9 = llvm.load %4 {alignment = 4 : i64} : !llvm.ptr -> i32
+  %10 = llvm.icmp "sgt" %8, %9 : i32
+  %11 = llvm.zext %10 : i1 to i32
+  llvm.cond_br %10, ^bb2, ^bb5
+^bb2:  // pred: ^bb1
+  %12 = llvm.load %6 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.store %12, %5 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.store %1, %6 {alignment = 4 : i64} : i32, !llvm.ptr
+  %13 = llvm.load %4 {alignment = 4 : i64} : !llvm.ptr -> i32
+  %14 = llvm.icmp "sgt" %13, %1 : i32
+  %15 = llvm.zext %14 : i1 to i32
+  llvm.cond_br %14, ^bb3, ^bb4
+^bb3:  // pred: ^bb2
+  %16 = llvm.load %2 {alignment = 8 : i64} : !llvm.ptr -> !llvm.ptr
+  %17 = llvm.load %4 {alignment = 4 : i64} : !llvm.ptr -> i32
+  %18 = llvm.sub %17, %0  : i32
+  %19 = llvm.getelementptr %16[%18] : (!llvm.ptr, i32) -> !llvm.ptr, i8
+  %20 = llvm.load %5 {alignment = 4 : i64} : !llvm.ptr -> i32
+  %21 = llvm.trunc %20 : i32 to i8
+  llvm.store %21, %19 {alignment = 1 : i64} : i8, !llvm.ptr
+  llvm.br ^bb4
+^bb4:  // 2 preds: ^bb2, ^bb3
+  %22 = llvm.load %4 {alignment = 4 : i64} : !llvm.ptr -> i32
+  %23 = llvm.add %22, %0  : i32
+  llvm.store %23, %4 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.br ^bb1
+^bb5:  // pred: ^bb1
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @complex_cf
+// CHECK-NOT: = llvm.alloca
+llvm.func @complex_cf(%arg0: i32, ...) {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(false) : i1
+  %2 = llvm.mlir.constant(0 : i32) : i32
+  %3 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.cond_br %1, ^bb1, ^bb2
+^bb1:  // pred: ^bb0
+  llvm.br ^bb2
+^bb2:  // 2 preds: ^bb0, ^bb1
+  llvm.store %2, %3 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.br ^bb3
+^bb3:  // 2 preds: ^bb2, ^bb16
+  llvm.cond_br %1, ^bb4, ^bb17
+^bb4:  // pred: ^bb3
+  llvm.cond_br %1, ^bb5, ^bb14
+^bb5:  // pred: ^bb4
+  llvm.cond_br %1, ^bb7, ^bb6
+^bb6:  // pred: ^bb5
+  llvm.br ^bb7
+^bb7:  // 2 preds: ^bb5, ^bb6
+  llvm.cond_br %1, ^bb9, ^bb8
+^bb8:  // pred: ^bb7
+  llvm.br ^bb9
+^bb9:  // 2 preds: ^bb7, ^bb8
+  llvm.cond_br %1, ^bb11, ^bb10
+^bb10:  // pred: ^bb9
+  llvm.br ^bb11
+^bb11:  // 2 preds: ^bb9, ^bb10
+  llvm.cond_br %1, ^bb12, ^bb13
+^bb12:  // pred: ^bb11
+  llvm.br ^bb13
+^bb13:  // 2 preds: ^bb11, ^bb12
+  llvm.br ^bb14
+^bb14:  // 2 preds: ^bb4, ^bb13
+  llvm.cond_br %1, ^bb15, ^bb16
+^bb15:  // pred: ^bb14
+  llvm.br ^bb16
+^bb16:  // 2 preds: ^bb14, ^bb15
+  llvm.br ^bb3
+^bb17:  // pred: ^bb3
+  llvm.br ^bb20
+^bb18:  // no predecessors
+  %4 = llvm.load %3 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.br ^bb24
+^bb19:  // no predecessors
+  llvm.br ^bb20
+^bb20:  // 2 preds: ^bb17, ^bb19
+  llvm.cond_br %1, ^bb21, ^bb22
+^bb21:  // pred: ^bb20
+  llvm.br ^bb23
+^bb22:  // pred: ^bb20
+  llvm.br ^bb23
+^bb23:  // 2 preds: ^bb21, ^bb22
+  llvm.br ^bb24
+^bb24:  // 2 preds: ^bb18, ^bb23
+  llvm.br ^bb26
+^bb25:  // no predecessors
+  llvm.br ^bb26
+^bb26:  // 2 preds: ^bb24, ^bb25
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @llvm_crash
+llvm.func @llvm_crash() -> i32 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(0 : i32) : i32
+  %2 = llvm.mlir.addressof @j : !llvm.ptr
+  %3 = llvm.mlir.constant(0 : i8) : i8
+  // CHECK-NOT: = llvm.alloca
+  // CHECK: %[[VOLATILE_ALLOCA:.*]] = llvm.alloca
+  // CHECK-NOT: = llvm.alloca
+  %4 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  %5 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  %6 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  %7 = llvm.bitcast %1 : i32 to i32
+  // CHECK: llvm.store volatile %{{.*}}, %[[VOLATILE_ALLOCA]]
+  llvm.store volatile %1, %5 {alignment = 4 : i64} : i32, !llvm.ptr
+  %8 = llvm.call @_setjmp(%2) : (!llvm.ptr) -> i32
+  %9 = llvm.icmp "ne" %8, %1 : i32
+  %10 = llvm.zext %9 : i1 to i8
+  %11 = llvm.icmp "ne" %10, %3 : i8
+  llvm.cond_br %11, ^bb1, ^bb2
+^bb1:  // pred: ^bb0
+  // CHECK: = llvm.load volatile %[[VOLATILE_ALLOCA]]
+  %12 = llvm.load volatile %5 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.store %12, %6 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.br ^bb3
+^bb2:  // pred: ^bb0
+  // CHECK: llvm.store volatile %{{.*}}, %[[VOLATILE_ALLOCA]]
+  llvm.store volatile %0, %5 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.call @g() : () -> ()
+  llvm.store %1, %6 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.br ^bb3
+^bb3:  // 2 preds: ^bb1, ^bb2
+  %13 = llvm.load %6 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.store %13, %4 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.br ^bb4
+^bb4:  // pred: ^bb3
+  %14 = llvm.load %4 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.return %14 : i32
+}
+llvm.mlir.global external @j() {addr_space = 0 : i32} : !llvm.array<1 x struct<"struct.__jmp_buf_tag", (array<6 x i32>, i32, struct<"struct.__sigset_t", (array<32 x i32>)>)>>
+llvm.func @_setjmp(!llvm.ptr) -> i32 attributes {passthrough = ["returns_twice"]}
+llvm.func @g()
+
+// -----
+
+// CHECK-LABEL: llvm.func amdgpu_kernelcc @addrspace_discard
+// CHECK-NOT: = llvm.alloca
+llvm.func amdgpu_kernelcc @addrspace_discard() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(2 : i64) : i64
+  %2 = llvm.alloca %0 x i8 {alignment = 8 : i64} : (i32) -> !llvm.ptr<5>
+  %3 = llvm.addrspacecast %2 : !llvm.ptr<5> to !llvm.ptr
+  llvm.intr.lifetime.start 2, %3 : !llvm.ptr
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @ignore_atomic
+// CHECK-SAME: (%[[arg0:.*]]: i32) -> i32
+llvm.func @ignore_atomic(%arg0: i32) -> i32 {
+  // CHECK-NOT: = llvm.alloca
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.store %arg0, %1 atomic seq_cst {alignment = 4 : i64} : i32, !llvm.ptr
+  %2 = llvm.load %1 atomic seq_cst {alignment = 4 : i64} : !llvm.ptr -> i32
+  // CHECK: llvm.return %[[arg0]] : i32
+  llvm.return %2 : i32
+}
+
+// -----
+
+// CHECK: llvm.func @landing_pad
+// CHECK-NOT: = llvm.alloca
+llvm.func @landing_pad() -> i32 attributes {personality = @__gxx_personality_v0} {
+  // CHECK-NOT: = llvm.alloca
+  // CHECK: %[[POISON:.*]] = llvm.mlir.poison : i32
+  // CHECK-NOT: = llvm.alloca
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  // CHECK: %[[v2:.*]] = llvm.invoke
+  %2 = llvm.invoke @landing_padf() to ^bb1 unwind ^bb3 : () -> i32
+// CHECK: ^{{.*}}:
+^bb1:// pred: ^bb0
+  llvm.store %2, %1 {alignment = 4 : i64} : i32, !llvm.ptr
+  // CHECK: llvm.br ^[[BB2:.*]](%[[v2]] : i32)
+  llvm.br ^bb2
+// CHECK: ^[[BB2]]([[v3:.*]]: i32):
+^bb2:// 2 preds: ^bb1, ^bb3
+  %3 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i32
+  // CHECK: llvm.return [[v3]] : i32
+  llvm.return %3 : i32
+// CHECK: ^{{.*}}:
+^bb3:// pred: ^bb0
+  %4 = llvm.landingpad cleanup : !llvm.struct<(ptr, i32)>
+  // CHECK: llvm.br ^[[BB2:.*]](%[[POISON]] : i32)
+  llvm.br ^bb2
+}
+llvm.func @landing_padf() -> i32
+llvm.func @__gxx_personality_v0(...) -> i32
+
+// -----
+
+// CHECK-LABEL: llvm.func @unreachable_defines
+llvm.func @unreachable_defines() -> i32 {
+  // CHECK-NOT: = llvm.alloca
+  // CHECK: %[[POISON:.*]] = llvm.mlir.poison : i32
+  // CHECK-NOT: = llvm.alloca
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.br ^bb1
+^bb1:  // 2 preds: ^bb0, ^bb2
+  %2 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i32
+  // CHECK: llvm.return %[[POISON]] : i32
+  llvm.return %2 : i32
+^bb2:  // no predecessors
+  %3 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.store %3, %1 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.br ^bb1
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @unreachable_jumps_to_merge_point
+// CHECK-NOT: = llvm.alloca
+llvm.func @unreachable_jumps_to_merge_point(%arg0: i1) -> i32 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(6 : i32) : i32
+  %2 = llvm.mlir.constant(5 : i32) : i32
+  %3 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.cond_br %arg0, ^bb1, ^bb2
+^bb1:  // 2 preds: ^bb0, ^bb4
+  llvm.store %1, %3 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.br ^bb4
+^bb2:  // pred: ^bb0
+  llvm.store %2, %3 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.br ^bb4
+^bb3:  // no predecessors
+  llvm.br ^bb4
+^bb4:  // 3 preds: ^bb1, ^bb2, ^bb3
+  %4 = llvm.load %3 {alignment = 4 : i64} : !llvm.ptr -> i32
+  llvm.return %4 : i32
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @ignore_lifetime
+// CHECK-NOT: = llvm.alloca
+llvm.func @ignore_lifetime() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.intr.lifetime.start 2, %1 : !llvm.ptr
+  llvm.store %0, %1 {alignment = 4 : i64} : i32, !llvm.ptr
+  llvm.intr.lifetime.end 2, %1 : !llvm.ptr
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @ignore_discardable_tree
+// CHECK-NOT: = llvm.alloca
+llvm.func @ignore_discardable_tree() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(0 : i16) : i16
+  %2 = llvm.mlir.constant(0 : i8) : i8
+  %3 = llvm.mlir.undef : !llvm.struct<(i8, i16)>
+  %4 = llvm.insertvalue %2, %3[0] : !llvm.struct<(i8, i16)> 
+  %5 = llvm.insertvalue %1, %4[1] : !llvm.struct<(i8, i16)> 
+  %6 = llvm.alloca %0 x !llvm.struct<(i8, i16)> {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  %7 = llvm.getelementptr %6[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i8, i16)>
+  llvm.intr.lifetime.start 2, %7 : !llvm.ptr
+  llvm.store %5, %6 {alignment = 2 : i64} : !llvm.struct<(i8, i16)>, !llvm.ptr
+  llvm.intr.lifetime.end 2, %7 : !llvm.ptr
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @store_load_forward
+llvm.func @store_load_forward() -> i32 {
+  // CHECK-NOT: = llvm.alloca
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  // CHECK: %[[RES:.*]] = llvm.mlir.constant(0 : i32) : i32
+  %1 = llvm.mlir.constant(0 : i32) : i32
+  %2 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.store %1, %2 {alignment = 4 : i64} : i32, !llvm.ptr
+  %3 = llvm.load %2 {alignment = 4 : i64} : !llvm.ptr -> i32
+  // CHECK: llvm.return %[[RES]] : i32
+  llvm.return %3 : i32
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @store_load_wrong_type
+llvm.func @store_load_wrong_type() -> i16 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(0 : i32) : i32
+  // CHECK: = llvm.alloca
+  %2 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  llvm.store %1, %2 {alignment = 4 : i64} : i32, !llvm.ptr
+  %3 = llvm.load %2 {alignment = 2 : i64} : !llvm.ptr -> i16
+  llvm.return %3 : i16
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @merge_point_cycle
+llvm.func @merge_point_cycle() {
+  // CHECK: %[[POISON:.*]] = llvm.mlir.poison : i32
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(7 : i32) : i32
+  %2 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  // CHECK: llvm.br ^[[bb1:.*]](%[[POISON]] : i32)
+  llvm.br ^bb1
+// CHECK: ^[[bb1]](%[[barg:.*]]: i32):
+^bb1:  // 2 preds: ^bb0, ^bb1
+  %3 = llvm.load %2 {alignment = 4 : i64} : !llvm.ptr -> i32
+  // CHECK: = llvm.call @use(%[[barg]])
+  %4 = llvm.call @use(%3) : (i32) -> i1
+  // CHECK: %[[def:.*]] = llvm.call @def
+  %5 = llvm.call @def(%1) : (i32) -> i32
+  llvm.store %5, %2 {alignment = 4 : i64} : i32, !llvm.ptr
+  // CHECK: llvm.cond_br %{{.*}}, ^[[bb1]](%[[def]] : i32), ^{{.*}}
+  llvm.cond_br %4, ^bb1, ^bb2
+^bb2:  // pred: ^bb1
+  llvm.return
+}
+
+llvm.func @def(i32) -> i32
+llvm.func @use(i32) -> i1
+
+// -----
+
+// CHECK-LABEL: llvm.func @no_unnecessary_arguments
+llvm.func @no_unnecessary_arguments() {
+  // CHECK: %[[POISON:.*]] = llvm.mlir.poison : i32
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.alloca %0 x i32 {alignment = 4 : i64} : (i32) -> !llvm.ptr
+  // CHECK: llvm.br ^[[bb1:.*]]
+  llvm.br ^bb1
+// CHECK: ^[[bb1]]:
+^bb1:  // 2 preds: ^bb0, ^bb1
+  %2 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i32
+  // CHECK: = llvm.call @use(%[[POISON]])
+  %3 = llvm.call @use(%2) : (i32) -> i1
+  // CHECK: llvm.cond_br %{{.*}}, ^[[bb1]], ^{{.*}}
+  llvm.cond_br %3, ^bb1, ^bb2
+^bb2:  // pred: ^bb1
+  llvm.return
+}
+
+llvm.func @use(i32) -> i1
+
+// -----
+
+// CHECK-LABEL: llvm.func @discardable_use_tree
+// CHECK-NOT: = llvm.alloca
+llvm.func @discardable_use_tree() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(2 : i64) : i64
+  %2 = llvm.alloca %0 x i8 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  %3 = llvm.bitcast %2 : !llvm.ptr to !llvm.ptr
+  %4 = llvm.bitcast %3 : !llvm.ptr to !llvm.ptr
+  llvm.intr.lifetime.start 2, %3 : !llvm.ptr
+  llvm.intr.lifetime.start 2, %4 : !llvm.ptr
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @non_discardable_use_tree
+llvm.func @non_discardable_use_tree() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(2 : i64) : i64
+  // CHECK: = llvm.alloca
+  %2 = llvm.alloca %0 x i8 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  %3 = llvm.bitcast %2 : !llvm.ptr to !llvm.ptr
+  %4 = llvm.bitcast %3 : !llvm.ptr to !llvm.ptr
+  llvm.intr.lifetime.start 2, %3 : !llvm.ptr
+  llvm.intr.lifetime.start 2, %4 : !llvm.ptr
+  llvm.call @use(%4) : (!llvm.ptr) -> i1
+  llvm.return
+}
+llvm.func @use(!llvm.ptr) -> i1
+
+// -----
+
+// CHECK-LABEL: llvm.func @trivial_get_element_ptr
+// CHECK-NOT: = llvm.alloca
+llvm.func @trivial_get_element_ptr() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(2 : i64) : i64
+  %2 = llvm.alloca %0 x i8 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  %3 = llvm.bitcast %2 : !llvm.ptr to !llvm.ptr
+  %4 = llvm.getelementptr %3[0, 0, 0] : (!llvm.ptr) -> !llvm.ptr, i8
+  llvm.intr.lifetime.start 2, %3 : !llvm.ptr
+  llvm.intr.lifetime.start 2, %4 : !llvm.ptr
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @nontrivial_get_element_ptr
+llvm.func @nontrivial_get_element_ptr() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(2 : i64) : i64
+  // CHECK: = llvm.alloca
+  %2 = llvm.alloca %0 x i8 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  %3 = llvm.bitcast %2 : !llvm.ptr to !llvm.ptr
+  %4 = llvm.getelementptr %3[0, 1, 0] : (!llvm.ptr) -> !llvm.ptr, i8
+  llvm.intr.lifetime.start 2, %3 : !llvm.ptr
+  llvm.intr.lifetime.start 2, %4 : !llvm.ptr
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @dynamic_get_element_ptr
+llvm.func @dynamic_get_element_ptr() {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  %1 = llvm.mlir.constant(2 : i64) : i64
+  // CHECK: = llvm.alloca
+  %2 = llvm.alloca %0 x i8 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  %3 = llvm.bitcast %2 : !llvm.ptr to !llvm.ptr
+  %4 = llvm.getelementptr %3[0, %0] : (!llvm.ptr, i32) -> !llvm.ptr, i8
+  llvm.intr.lifetime.start 2, %3 : !llvm.ptr
+  llvm.intr.lifetime.start 2, %4 : !llvm.ptr
+  llvm.return
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @live_cycle
+// CHECK-SAME: (%[[arg0:.*]]: i64, %{{.*}}: i1, %[[arg2:.*]]: i64) -> i64
+llvm.func @live_cycle(%arg0: i64, %arg1: i1, %arg2: i64) -> i64 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  // CHECK-NOT: = llvm.alloca
+  %1 = llvm.alloca %0 x i64 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  llvm.store %arg2, %1 {alignment = 4 : i64} : i64, !llvm.ptr
+  // CHECK: llvm.cond_br %{{.*}}, ^[[bb1:.*]](%[[arg2]] : i64), ^[[bb2:.*]](%[[arg2]] : i64)
+  llvm.cond_br %arg1, ^bb1, ^bb2
+// CHECK: ^[[bb1]](%[[v1:.*]]: i64):
+^bb1:
+  %2 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i64
+  // CHECK: llvm.call @use(%[[v1]])
+  llvm.call @use(%2) : (i64) -> ()
+  llvm.store %arg0, %1 {alignment = 4 : i64} : i64, !llvm.ptr
+  // CHECK: llvm.br ^[[bb2]](%[[arg0]] : i64)
+  llvm.br ^bb2
+// CHECK: ^[[bb2]](%[[v2:.*]]: i64):
+^bb2:
+  // CHECK: llvm.br ^[[bb1]](%[[v2]] : i64)
+  llvm.br ^bb1
+}
+
+llvm.func @use(i64)
+
+// -----
+
+// This test should no longer be an issue once promotion within subregions
+// is supported.
+// CHECK-LABEL: llvm.func @subregion_block_promotion
+// CHECK-SAME: (%[[arg0:.*]]: i64, %[[arg1:.*]]: i64) -> i64
+llvm.func @subregion_block_promotion(%arg0: i64, %arg1: i64) -> i64 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  // CHECK: %[[ALLOCA:.*]] = llvm.alloca
+  %1 = llvm.alloca %0 x i64 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  // CHECK: llvm.store %[[arg1]], %[[ALLOCA]]
+  llvm.store %arg1, %1 {alignment = 4 : i64} : i64, !llvm.ptr
+  // CHECK: scf.execute_region {
+  scf.execute_region {
+    // CHECK: llvm.store %[[arg0]], %[[ALLOCA]]
+    llvm.store %arg0, %1 {alignment = 4 : i64} : i64, !llvm.ptr
+    scf.yield
+  }
+  // CHECK: }
+  // CHECK: %[[RES:.*]] = llvm.load %[[ALLOCA]]
+  %2 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i64
+  // CHECK: llvm.return %[[RES]] : i64
+  llvm.return %2 : i64
+}
+
+// -----
+
+// CHECK-LABEL: llvm.func @subregion_simple_transitive_promotion
+// CHECK-SAME: (%[[arg0:.*]]: i64, %[[arg1:.*]]: i64) -> i64
+llvm.func @subregion_simple_transitive_promotion(%arg0: i64, %arg1: i64) -> i64 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  // CHECK-NOT: = llvm.alloca
+  %1 = llvm.alloca %0 x i64 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  llvm.store %arg1, %1 {alignment = 4 : i64} : i64, !llvm.ptr
+  %2 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i64
+  // CHECK: scf.execute_region {
+  scf.execute_region {
+    // CHECK: llvm.call @use(%[[arg1]])
+    llvm.call @use(%2) : (i64) -> ()
+    scf.yield
+  }
+  // CHECK: }
+  // CHECK: llvm.return %[[arg1]] : i64
+  llvm.return %2 : i64
+}
+
+llvm.func @use(i64)
+
+// -----
+
+// This behavior is specific to the LLVM dialect, because LLVM semantics are
+// that reaching an alloca multiple times allocates on the stack multiple
+// times. Promoting an alloca that is reached multiple times could lead to
+// changes in observable behavior. Thus only allocas in the entry block are
+// promoted.
+
+// CHECK-LABEL: llvm.func @no_inner_alloca_promotion
+// CHECK-SAME: (%[[ARG:.*]]: i64) -> i64
+llvm.func @no_inner_alloca_promotion(%arg: i64) -> i64 {
+  %0 = llvm.mlir.constant(1 : i32) : i32
+  llvm.br ^bb1
+^bb1:
+  // CHECK: %[[ALLOCA:.*]] = llvm.alloca
+  %1 = llvm.alloca %0 x i64 {alignment = 8 : i64} : (i32) -> !llvm.ptr
+  // CHECK: llvm.store %[[ARG]], %[[ALLOCA]]
+  llvm.store %arg, %1 {alignment = 4 : i64} : i64, !llvm.ptr
+  // CHECK: %[[RES:.*]] = llvm.load %[[ALLOCA]]
+  %2 = llvm.load %1 {alignment = 4 : i64} : !llvm.ptr -> i64
+  // CHECK: llvm.return %[[RES]] : i64
+  llvm.return %2 : i64
+}