PostfixExpression: Introduce CFANode

[labath]

Summary

This node represents the "Canonical Frame Address" of the current frame,
and is used by various DWARF expressions to express adresses of various
objects relative to the frame.

The motivation for this is the ability to translate breakpad register
unwind rules (strings like: ".cfa 8 - ^") back into dwarf.

This patch introduces the new node type, and teaches the dwarf codegen
how to handle it. A slight complication here is that the value of CFA is
provided differently depending on the context where the dwarf expression
is used. In unwind rules, it is made available implicitly via the
initial dwarf stack. It variable location expressions, it needs to be
referred to explicitly via a special opcode.

As currently, the only usage of this is in the unwind rules, I made the
dwarf generator use this convention, but this can be easily made
configurable, if necessary. The implementation does this via keeping
track of the DWARF stack depth an any given point, and then copying the
CFA value from the bottom of the stack via the DW_OP_pick opcode. This
could be made more efficient for simple expressions, but here I chose to
start with the most general implementation possible.

[labath]

PS: Although this patch is technically dependency free, for this to work as a part of the bigger picture, we'll need to get lldb's dwarf evaluator to actually push the CFA value to the dwarf stack (D61018) and fix its implementation of DW_OP_pick (D61182).

[clayborg]

FYI: for all DWARF expressions found in EH frame stuff, they expect the CFA address to be pushed onto the stack prior to executing the expression. Do we just want to follow suit with the these expressions and avoid the extra needed node?

[labath]

In D61183#1480948, @clayborg wrote:

FYI: for all DWARF expressions found in EH frame stuff, they expect the CFA address to be pushed onto the stack prior to executing the expression. Do we just want to follow suit with the these expressions and avoid the extra needed node?

That is exactly what I am doing, and that's why I need D61018 for this to work, because right now we actually *aren't* pushing the cfa value to the dwarf stack.

However, I still need some kind of a node in the expression AST, so that the DWARF generator knows that it should insert a reference to the initial value.

Now theoretically, the dwarf codegen could be made smarter and try to optimize the generated expression. So for instance for an expression like ".cfa 8 +" it could be made to generate "DW_OP_lit8, DW_OP_plus" instead of the current "DW_OP_pick 0, DW_OP_uconst 8, DW_OP_plus". However, I don't see a need for that now, particularly, as this expression can be completely optimized away by using the "isCFAPlusOffset" mode of the UnwindPlan (which is something I plan to look at).

However, this got me thinking about the name of the special node, and I concluded that a better name would be the "InitialValueNode", reflecting it's usage instead of what it is supposed to contain. That way, it can be used in other situations where an initial value is present on the dwarf stack, and the name CFANode can remain free for the cases where one has to emit an explicit opcode (DW_OP_call_frame_cfa) in order to retrieve it.

[labath]

s/CFA/InitialValue/

[amccarth]

LGTM, but I found one comment a bit confusing for me.

source/Symbol/PostfixExpression.cpp

150 ↗

(On Diff #197086)

I'm having trouble understanding this comment.

"will contain their value" -- What does "their" refer to here? I guessed InitialValueNodes, but then I'd expect "value" to be "values" (plural), and I'm not sure how that relates to the stack depth.

[labath]

source/Symbol/PostfixExpression.cpp

150 ↗

(On Diff #197086)

I've rephrased this so that it is (hopefully) more understandable. The reason for the singular-plural schism is that the expression can theoretically contain multiple InitialValueNodes (I'm not sure why would anyone want to do that in practice, but the option is there), but they will all refer to the same value, which is the value pushed onto the dwarf stack before the expression evaluation began.

lldb/trunk/include/lldb/Symbol/PostfixExpression.h

 
 namespace postfix {
 
 /// The base class for all nodes in the parsed postfix tree.
 class Node {
 public:
   enum Kind {
     BinaryOp,
+    InitialValue,
     Integer,
     Register,
     Symbol,
     UnaryOp,
   };
 
 protected:
   Node(Kind kind) : m_kind(kind) {}
public:
   static bool classof(const Node *node) { return node->GetKind() == BinaryOp; }
 
 private:
   OpType m_op_type;
   Node *m_left;
   Node *m_right;
 };
 
+/// A node representing the canonical frame address.
+class InitialValueNode: public Node {
+public:
+  InitialValueNode() : Node(InitialValue) {}
+
+  static bool classof(const Node *node) {
+    return node->GetKind() == InitialValue;
+  }
+};
+
 /// A node representing an integer literal.
 class IntegerNode : public Node {
 public:
   IntegerNode(uint32_t value) : Node(Integer), m_value(value) {}
 
   uint32_t GetValue() const { return m_value; }
 
   static bool classof(const Node *node) { return node->GetKind() == Integer; }

 ///   a different one.
 /// - The class is templatized on the return type of the Visit functions, which
 ///   means it's possible to return values from them.
 template <typename ResultT = void> class Visitor {
 protected:
   virtual ~Visitor() = default;
 
   virtual ResultT Visit(BinaryOpNode &binary, Node *&ref) = 0;
+  virtual ResultT Visit(InitialValueNode &val, Node *&ref) = 0;
   virtual ResultT Visit(IntegerNode &integer, Node *&) = 0;
   virtual ResultT Visit(RegisterNode &reg, Node *&) = 0;
   virtual ResultT Visit(SymbolNode &symbol, Node *&ref) = 0;
   virtual ResultT Visit(UnaryOpNode &unary, Node *&ref) = 0;
 
   /// Invoke the correct Visit function based on the dynamic type of the given
   /// node.
   ResultT Dispatch(Node *&node) {
     switch (node->GetKind()) {
     case Node::BinaryOp:
       return Visit(llvm::cast<BinaryOpNode>(*node), node);
+    case Node::InitialValue:
+      return Visit(llvm::cast<InitialValueNode>(*node), node);
     case Node::Integer:
       return Visit(llvm::cast<IntegerNode>(*node), node);
     case Node::Register:
       return Visit(llvm::cast<RegisterNode>(*node), node);
     case Node::Symbol:
       return Visit(llvm::cast<SymbolNode>(*node), node);
     case Node::UnaryOp:
       return Visit(llvm::cast<UnaryOpNode>(*node), node);
inline T *MakeNode(llvm::BumpPtrAllocator &alloc, Args &&... args) {
   return new (alloc.Allocate<T>()) T(std::forward<Args>(args)...);
 }
 
 /// Parse the given postfix expression. The parsed nodes are placed into the
 /// provided allocator.
 Node *Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc);
 
 /// Serialize the given expression tree as DWARF. The result is written into the
-/// given stream. The AST should not contain any SymbolNodes.
+/// given stream. The AST should not contain any SymbolNodes. If the expression
+/// contains InitialValueNodes, the generated expression will assume that their
+/// value will be provided as the top value of the initial evaluation stack (as
+/// is the case with the CFA value in register eh_unwind rules).
 void ToDWARF(Node &node, Stream &stream);
 
 } // namespace postfix
 } // namespace lldb_private
 
 #endif // LLDB_SYMBOL_POSTFIXEXPRESSION_H

lldb/trunk/source/Symbol/PostfixExpression.cpp

public:
 
   using Visitor<bool>::Dispatch;
 
 private:
   bool Visit(BinaryOpNode &binary, Node *&) override {
     return Dispatch(binary.Left()) && Dispatch(binary.Right());
   }
 
-  bool Visit(IntegerNode &integer, Node *&) override { return true; }
-  bool Visit(RegisterNode &reg, Node *&) override { return true; }
+  bool Visit(InitialValueNode &, Node *&) override { return true; }
+  bool Visit(IntegerNode &, Node *&) override { return true; }
+  bool Visit(RegisterNode &, Node *&) override { return true; }
 
   bool Visit(SymbolNode &symbol, Node *&ref) override {
     if (Node *replacement = m_replacer(symbol)) {
       ref = replacement;
       if (replacement != &symbol)
         return Dispatch(ref);
       return true;
     }

 public:
   DWARFCodegen(Stream &stream) : m_out_stream(stream) {}
 
   using Visitor<>::Dispatch;
 
 private:
   void Visit(BinaryOpNode &binary, Node *&);
 
+  void Visit(InitialValueNode &val, Node *&);
+
   void Visit(IntegerNode &integer, Node *&) {
     m_out_stream.PutHex8(DW_OP_constu);
     m_out_stream.PutULEB128(integer.GetValue());
+    ++m_stack_depth;
   }
 
   void Visit(RegisterNode &reg, Node *&);
 
   void Visit(SymbolNode &symbol, Node *&) {
     llvm_unreachable("Symbols should have been resolved by now!");
   }
 
   void Visit(UnaryOpNode &unary, Node *&);
 
   Stream &m_out_stream;
+
+  /// The number keeping track of the evaluation stack depth at any given
+  /// moment. Used for implementing InitialValueNodes. We start with
+  /// m_stack_depth = 1, assuming that the initial value is already on the
+  /// stack. This initial value will be the value of all InitialValueNodes. If
+  /// the expression does not contain InitialValueNodes, then m_stack_depth is
+  /// not used, and the generated expression will run correctly even without an
+  /// initial value.
+  size_t m_stack_depth = 1;
 };
 } // namespace
 
 void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) {
   Dispatch(binary.Left());
   Dispatch(binary.Right());
 
   switch (binary.GetOpType()) {
case BinaryOpNode::Align:
     // NOTE: implicitly assuming that b is power of 2
     m_out_stream.PutHex8(DW_OP_lit1);
     m_out_stream.PutHex8(DW_OP_minus);
     m_out_stream.PutHex8(DW_OP_not);
 
     m_out_stream.PutHex8(DW_OP_and);
     break;
   }
+  --m_stack_depth; // Two pops, one push.
+}
+
+void DWARFCodegen::Visit(InitialValueNode &, Node *&) {
+  // We never go below the initial stack, so we can pick the initial value from
+  // the bottom of the stack at any moment.
+  assert(m_stack_depth >= 1);
+  m_out_stream.PutHex8(DW_OP_pick);
+  m_out_stream.PutHex8(m_stack_depth - 1);
+  ++m_stack_depth;
 }
 
 void DWARFCodegen::Visit(RegisterNode &reg, Node *&) {
   uint32_t reg_num = reg.GetRegNum();
   assert(reg_num != LLDB_INVALID_REGNUM);
 
   if (reg_num > 31) {
     m_out_stream.PutHex8(DW_OP_bregx);
     m_out_stream.PutULEB128(reg_num);
   } else
     m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
 
   m_out_stream.PutSLEB128(0);
+  ++m_stack_depth;
 }
 
 void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
   Dispatch(unary.Operand());
 
   switch (unary.GetOpType()) {
   case UnaryOpNode::Deref:
     m_out_stream.PutHex8(DW_OP_deref);
     break;
   }
+  // Stack depth unchanged.
 }
 
 bool postfix::ResolveSymbols(
     Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) {
   return SymbolResolver(replacer).Dispatch(node);
 }
 
 void postfix::ToDWARF(Node &node, Stream &stream) {
   Node *ptr = &node;
   DWARFCodegen(stream).Dispatch(ptr);
 }

lldb/trunk/unittests/Symbol/PostfixExpressionTest.cpp

 
 struct ASTPrinter : public Visitor<std::string> {
 protected:
   std::string Visit(BinaryOpNode &binary, Node *&) override {
     return llvm::formatv("{0}({1}, {2})", ToString(binary.GetOpType()),
                          Dispatch(binary.Left()), Dispatch(binary.Right()));
   }
 
+  std::string Visit(InitialValueNode &, Node *&) override { return "InitialValue"; }
+
   std::string Visit(IntegerNode &integer, Node *&) override {
     return llvm::formatv("int({0})", integer.GetValue());
   }
 
   std::string Visit(RegisterNode &reg, Node *&) override {
     return llvm::formatv("reg({0})", reg.GetRegNum());
   }
 

 }
 
 static std::string ParseAndGenerateDWARF(llvm::StringRef expr) {
   llvm::BumpPtrAllocator alloc;
   Node *ast = Parse(expr, alloc);
   if (!ast)
     return "Parse failed.";
   if (!ResolveSymbols(ast, [&](SymbolNode &symbol) -> Node * {
+        if (symbol.GetName() == "INIT")
+          return MakeNode<InitialValueNode>(alloc);
+
         uint32_t num;
         if (to_integer(symbol.GetName().drop_front(), num))
           return MakeNode<RegisterNode>(alloc, num);
         return nullptr;
       })) {
     return "Resolution failed.";
   }
 

 
 TEST(PostfixExpression, ToDWARF) {
   EXPECT_EQ("DW_OP_constu 0x0", ParseAndGenerateDWARF("0"));
 
   EXPECT_EQ("DW_OP_breg1 +0", ParseAndGenerateDWARF("R1"));
 
   EXPECT_EQ("DW_OP_bregx 65 0", ParseAndGenerateDWARF("R65"));
 
+  EXPECT_EQ("DW_OP_pick 0x00", ParseAndGenerateDWARF("INIT"));
+
+  EXPECT_EQ("DW_OP_pick 0x00, DW_OP_pick 0x01, DW_OP_plus ",
+            ParseAndGenerateDWARF("INIT INIT +"));
+
+  EXPECT_EQ("DW_OP_breg1 +0, DW_OP_pick 0x01, DW_OP_plus ",
+            ParseAndGenerateDWARF("R1 INIT +"));
+
+  EXPECT_EQ("DW_OP_constu 0x1, DW_OP_pick 0x01, DW_OP_deref , DW_OP_plus ",
+            ParseAndGenerateDWARF("1 INIT ^ +"));
+
   EXPECT_EQ("DW_OP_constu 0x4, DW_OP_constu 0x5, DW_OP_plus ",
             ParseAndGenerateDWARF("4 5 +"));
 
   EXPECT_EQ("DW_OP_constu 0x4, DW_OP_constu 0x5, DW_OP_minus ",
             ParseAndGenerateDWARF("4 5 -"));
 
   EXPECT_EQ("DW_OP_constu 0x4, DW_OP_deref ", ParseAndGenerateDWARF("4 ^"));
 
   EXPECT_EQ("DW_OP_breg6 +0, DW_OP_constu 0x80, DW_OP_lit1 "
             ", DW_OP_minus , DW_OP_not , DW_OP_and ",
             ParseAndGenerateDWARF("R6 128 @"));
 }