[DAGCombiner] Eliminate dead stores to stack.

Summary:
A store to an object whose lifetime is about to end can be removed.

See PR40550 for motivation.

Reviewers: niravd

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D57541

llvm-svn: 354244

3 files changed, 55 insertions, 2 deletions

diff --git a/llvm/include/llvm/CodeGen/SelectionDAG.h b/llvm/include/llvm/CodeGen/SelectionDAG.h
index c4755995526..93c8ba4fdc9 100644
--- a/llvm/include/llvm/CodeGen/SelectionDAG.h
+++ b/llvm/include/llvm/CodeGen/SelectionDAG.h
@@ -1016,6 +1016,12 @@ public:
                               ArrayRef<SDValue> Ops, EVT MemVT,
                               MachineMemOperand *MMO);
 
+  /// Creates a LifetimeSDNode that starts (`IsStart==true`) or ends
+  /// (`IsStart==false`) the lifetime of the portion of `FrameIndex` between
+  /// offsets `Offset` and `Offset + Size`.
+  SDValue getLifetimeNode(bool IsStart, const SDLoc &dl, SDValue Chain,
+                          int FrameIndex, int64_t Size, int64_t Offset = -1);
+
   /// Create a MERGE_VALUES node from the given operands.
   SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl);
 
diff --git a/llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h b/llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h
index f168b846fda..4173cbe635b 100644
--- a/llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h
+++ b/llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h
@@ -48,14 +48,30 @@ public:
   SDValue getIndex() { return Index; }
   SDValue getIndex() const { return Index; }
 
+  // Returns true if `Other` and `*this` are both some offset from the same base
+  // pointer. In that case, `Off` is set to the offset between `*this` and
+  // `Other` (negative if `Other` is before `*this`).
+  bool equalBaseIndex(const BaseIndexOffset &Other, const SelectionDAG &DAG,
+                      int64_t &Off) const;
+
   bool equalBaseIndex(const BaseIndexOffset &Other,
                       const SelectionDAG &DAG) const {
     int64_t Off;
     return equalBaseIndex(Other, DAG, Off);
   }
 
-  bool equalBaseIndex(const BaseIndexOffset &Other, const SelectionDAG &DAG,
-                      int64_t &Off) const;
+  // Returns true if `Other` (with size `OtherSize`) can be proven to be fully
+  // contained in `*this` (with size `Size`).
+  bool contains(int64_t Size, const BaseIndexOffset &Other, int64_t OtherSize,
+                const SelectionDAG &DAG) const;
+
+  // Returns true `BasePtr0` and `BasePtr1` can be proven to alias/not alias, in
+  // which case `IsAlias` is set to true/false.
+  static bool computeAliasing(const BaseIndexOffset &BasePtr0,
+                              const int64_t NumBytes0,
+                              const BaseIndexOffset &BasePtr1,
+                              const int64_t NumBytes1, const SelectionDAG &DAG,
+                              bool &IsAlias);
 
   /// Parses tree in Ptr for base, index, offset addresses.
   static BaseIndexOffset match(const LSBaseSDNode *N, const SelectionDAG &DAG);
diff --git a/llvm/include/llvm/CodeGen/SelectionDAGNodes.h b/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
index c0dd9d1e12f..a5d494ff4e0 100644
--- a/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -1692,6 +1692,37 @@ public:
   }
 };
 
+/// This SDNode is used for LIFETIME_START/LIFETIME_END values, which indicate
+/// the offet and size that are started/ended in the underlying FrameIndex.
+class LifetimeSDNode : public SDNode {
+  int64_t Size;
+  int64_t Offset; // -1 if offset is unknown.
+public:
+  LifetimeSDNode(unsigned Opcode, unsigned Order, const DebugLoc &dl,
+                 SDVTList VTs, int64_t Size, int64_t Offset)
+      : SDNode(Opcode, Order, dl, VTs), Size(Size), Offset(Offset) {}
+
+  int64_t getFrameIndex() const {
+    return cast<FrameIndexSDNode>(getOperand(1))->getIndex();
+  }
+
+  bool hasOffset() const { return Offset >= 0; }
+  int64_t getOffset() const {
+    assert(hasOffset() && "offset is unknown");
+    return Offset;
+  }
+  int64_t getSize() const {
+    assert(hasOffset() && "offset is unknown");
+    return Size;
+  }
+
+  // Methods to support isa and dyn_cast
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::LIFETIME_START ||
+           N->getOpcode() == ISD::LIFETIME_END;
+  }
+};
+
 class JumpTableSDNode : public SDNode {
   friend class SelectionDAG;