[RFC,9/X,libsanitizer] Put tags into each stack variable pointer

This patch makes sure that every pointer to a stack variable includes a
tag of some sort on it.

The way tagging works is:
  1) For every new stack frame, a random tag is generated.
  2) A base register is formed from the stack pointer value and this
     random tag.
  3) References to stack variables are now formed with RTL describing an
     offset from this base in both tag and value.

The random tag generation is handled by a backend hook.  This is
currently a dummy that keeps the tag of the original pointer.
Using a dummy means that every stack frame has the initial colour of
zero and variables are coloured with incrementing tags from 1, which
makes debugging a bit easier.

We have a more complicated method of handling the tag&value offsets than
is needed for HWASAN.  This complexity is added to allow for backend
specific requirements when the HWASAN framework is adapted to hardware
memory tagging such as AArch64 MTE.

The tag and value increments are handled by emitting a new RTL
expression ADDTAG.  This new expression is a ternary operator returning
the final pointer from operands of the initial pointer plus a tag offset
and value offset.

This expression can then be expanded in the backend in whatever manner
is needed.  The flexibility of being able to use define_expand instead
of define_insn is needed for MTE, since that needs a temporary register
when the value offset is too large.

(NOTE I am looking into another method to allow backend specific
expansion of the tag addition -- by using a hook in force_operand and
hwasan_with_tag -- the method of adding a new RTL expression is under
flux).

gcc/ChangeLog:

2019-09-06  Matthew Malcomson  <matthew.malcomson@arm.com>

	* asan.c (hwasan_record_base): New function.
	(hwasan_increment_tag):New function.
	(hwasan_with_tag):New function.
	(hwasan_tag_init):New function.
	* asan.h (hwasan_record_base): New declaration.
	(hwasan_increment_tag): New declaration.
	(hwasan_with_tag): New declaration.
	(hwasan_tag_init): New declaration.
	* cfgexpand.c (expand_one_stack_var_at): Account for tags in
	variables when using HWASAN.
	(expand_stack_vars): Ensure variables are offset from a tagged
	base.
	(expand_one_stack_var_1): Pass new argument to
	expand_one_stack_var_at.
	(init_vars_expansion): Initialise hwasan internal variables when
	starting variable expansion.
	* config/aarch64/aarch64.md (addtag): Define new addtag pattern.
	* config/aarch64/predicates.md (aarch64_MTE_add_temp): New
	predicate.
	(aarch64_MTE_tag_offset): New predicate.
	* doc/tm.texi (TARGET_MEMTAG_GENTAG): Document.
	* doc/tm.texi.in (TARGET_MEMTAG_GENTAG): Document.
	* dwarf2out.c (is_based_loc): Handle ADDTAG.
	(mem_loc_descriptor): Handle ADDTAG.
	* explow.c (memory_address_addr_space): Handle ADDTAG.
	(get_dynamic_stack_base): Parametrise stack vars RTX base.
	* explow.h (get_dynamic_stack_base): New declaration.
	* expr.c (force_operand): Account for ADDTAG.
	* optabs.def (OPTAB_NL): New ADDTAG optab.
	* rtl.def (ADDTAG): New ADDTAG RTX.
	* simplify-rtx.c (simplify_ternary_operation): Account for
	ADDTAG.
	* target.def (TARGET_MEMTAG_GENTAG): Introduce new hook.
	* targhooks.c (default_memtag_gentag): Define default hook.
	* targhooks.h (default_memtag_gentag): Declare default hook.



###############     Attachment also inlined for ease of reply    ###############
diff --git a/gcc/asan.h b/gcc/asan.h
index d78f6b821c7d1e859cc53f124e071eac27a5e9b8..127c24aa6b0e4e6d0ba332004145ec498034c955 100644
--- a/gcc/asan.h
+++ b/gcc/asan.h
@@ -23,6 +23,11 @@ along with GCC; see the file COPYING3.  If not see
 
 extern void asan_function_start (void);
 extern void asan_finish_file (void);
+extern void hwasan_record_base (rtx);
+extern void hwasan_increment_tag ();
+extern rtx hwasan_with_tag (rtx, poly_int64);
+extern void hwasan_tag_init ();
+extern bool memory_tagging_p (void);
 extern rtx_insn *asan_emit_stack_protection (rtx, rtx, unsigned int,
 					     HOST_WIDE_INT *, tree *, int);
 extern rtx_insn *asan_emit_allocas_unpoison (rtx, rtx, rtx_insn *);
@@ -33,7 +38,7 @@ extern bool asan_expand_check_ifn (gimple_stmt_iterator *, bool);
 extern bool asan_expand_mark_ifn (gimple_stmt_iterator *);
 extern bool asan_expand_poison_ifn (gimple_stmt_iterator *, bool *,
 				    hash_map<tree, tree> &);
-extern bool memory_tagging_p (void);
+
 extern gimple_stmt_iterator create_cond_insert_point
      (gimple_stmt_iterator *, bool, bool, bool, basic_block *, basic_block *);
 
diff --git a/gcc/asan.c b/gcc/asan.c
index 42e990675e740bd37dad0704fd34b7a04740121e..a6ff503ceec294f2c09b0bd723a3d8043e4de6a1 100644
--- a/gcc/asan.c
+++ b/gcc/asan.c
@@ -257,6 +257,9 @@ hash_set<tree> *asan_handled_variables = NULL;
 
 hash_set <tree> *asan_used_labels = NULL;
 
+static uint8_t tag_offset = 0;
+static rtx hwasan_base_ptr = NULL_RTX;
+
 /* Sets shadow offset to value in string VAL.  */
 
 bool
@@ -3692,4 +3695,69 @@ make_pass_asan_O0 (gcc::context *ctxt)
   return new pass_asan_O0 (ctxt);
 }
 
+void
+hwasan_record_base (rtx base)
+{
+  /* Initialise base colour of the base register.
+     This has to be done as soon as the stack is getting expanded to ensure
+     anything emitted with `get_dynamic_stack_base` will use the value set here
+     instead of using a register without a value.
+     This is important for large aligned values.  */
+  targetm.memtag.gentag (base, virtual_stack_vars_rtx);
+  hwasan_base_ptr = base;
+}
+
+void
+hwasan_increment_tag ()
+{
+  uint8_t tag_bits = HWASAN_TAG_SIZE;
+  tag_offset = (tag_offset + 1) % (1 << tag_bits);
+  /* TODO Having the offset at STACK_BACKGROUND is not a problem, it's having
+     offset + base at STACK_BACKGROUND.
+
+     Eventually, the base will be randomly generated on every function entry
+     and there will be no way to tell at compile time what tag that base will
+     be.
+
+     For now the base is always zero, which means we can use this clause to
+     avoid allocating any object a tag of the stack background.
+
+     That's a help when debugging -- every variable should have a non-zero
+     colour.  */
+  if (tag_offset == HWASAN_STACK_BACKGROUND)
+    tag_offset += 1;
+}
+
+rtx
+hwasan_with_tag (rtx base, poly_int64 offset)
+{
+  gcc_assert (tag_offset < (1 << HWASAN_TAG_SIZE));
+  rtx x;
+
+  /* No point incrementing the tag by a value of zero.  */
+  if (tag_offset)
+    x = gen_rtx_ADDTAG (
+			Pmode,
+			base,
+			gen_int_mode (offset, Pmode),
+			const_int_rtx[MAX_SAVED_CONST_INT + tag_offset]);
+  else
+    x = plus_constant (Pmode, base, offset);
+
+  return x;
+}
+
+/* Clear internal state for the next function.
+   This function is called after the stack has been expanded in
+   `expand_stack_vars`.  */
+void
+hwasan_tag_init ()
+{
+  delete asan_used_labels;
+  asan_used_labels = NULL;
+
+  hwasan_base_ptr = NULL_RTX;
+  tag_offset = HWASAN_STACK_BACKGROUND + 1;
+}
+
 #include "gt-asan.h"
diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c
index c5585d83c6e155856e7a4278e21c35ee5675bbdd..10739bc25940374c686c191ca76b1dfe8f000562 100644
--- a/gcc/cfgexpand.c
+++ b/gcc/cfgexpand.c
@@ -987,7 +987,7 @@ dump_stack_var_partition (void)
 
 static void
 expand_one_stack_var_at (tree decl, rtx base, unsigned base_align,
-			 poly_int64 offset)
+			 poly_int64 offset, rtx stack_base)
 {
   unsigned align;
   rtx x;
@@ -995,7 +995,11 @@ expand_one_stack_var_at (tree decl, rtx base, unsigned base_align,
   /* If this fails, we've overflowed the stack frame.  Error nicely?  */
   gcc_assert (known_eq (offset, trunc_int_for_mode (offset, Pmode)));
 
-  x = plus_constant (Pmode, base, offset);
+  if (memory_tagging_p ())
+    x = hwasan_with_tag (base, offset);
+  else
+    x = plus_constant (Pmode, base, offset);
+
   x = gen_rtx_MEM (TREE_CODE (decl) == SSA_NAME
 		   ? TYPE_MODE (TREE_TYPE (decl))
 		   : DECL_MODE (SSAVAR (decl)), x);
@@ -1005,7 +1009,7 @@ expand_one_stack_var_at (tree decl, rtx base, unsigned base_align,
       /* Set alignment we actually gave this decl if it isn't an SSA name.
          If it is we generate stack slots only accidentally so it isn't as
 	 important, we'll simply use the alignment that is already set.  */
-      if (base == virtual_stack_vars_rtx)
+      if (base == stack_base)
 	offset -= frame_phase;
       align = known_alignment (offset);
       align *= BITS_PER_UNIT;
@@ -1096,6 +1100,12 @@ expand_stack_vars (bool (*pred) (size_t), struct stack_vars_data *data)
 	}
     }
 
+  if (memory_tagging_p () && data->asan_base == NULL)
+    {
+      data->asan_base = gen_reg_rtx (Pmode);
+      hwasan_record_base (data->asan_base);
+    }
+
   for (si = 0; si < n; ++si)
     {
       rtx base;
@@ -1121,6 +1131,7 @@ expand_stack_vars (bool (*pred) (size_t), struct stack_vars_data *data)
       if (pred && !pred (i))
 	continue;
 
+      base = memory_tagging_p () ? data->asan_base : virtual_stack_vars_rtx;
       alignb = stack_vars[i].alignb;
       if (alignb * BITS_PER_UNIT <= MAX_SUPPORTED_STACK_ALIGNMENT)
 	{
@@ -1147,7 +1158,6 @@ expand_stack_vars (bool (*pred) (size_t), struct stack_vars_data *data)
 	      gcc_assert (stack_vars[i].alignb >= HWASAN_TAG_GRANULE_SIZE);
 	      alloc_stack_frame_space (0, HWASAN_TAG_GRANULE_SIZE);
 	    }
-	  base = virtual_stack_vars_rtx;
 	  /* ASAN description strings don't yet have a syntax for expressing
 	     polynomial offsets.  */
 	  HOST_WIDE_INT prev_offset;
@@ -1238,22 +1248,39 @@ expand_stack_vars (bool (*pred) (size_t), struct stack_vars_data *data)
 	     space.  */
 	  if (maybe_ne (large_size, 0U) && ! large_allocation_done)
 	    {
-	      poly_int64 loffset;
 	      rtx large_allocsize;
+	      poly_int64 loffset;
 
 	      large_allocsize = gen_int_mode (large_size, Pmode);
 	      get_dynamic_stack_size (&large_allocsize, 0, large_align, NULL);
 	      loffset = alloc_stack_frame_space
 		(rtx_to_poly_int64 (large_allocsize),
 		 PREFERRED_STACK_BOUNDARY / BITS_PER_UNIT);
-	      large_base = get_dynamic_stack_base (loffset, large_align);
+	      large_base = get_dynamic_stack_base (loffset, large_align, base);
 	      large_allocation_done = true;
 	    }
-	  gcc_assert (large_base != NULL);
 
+	  gcc_assert (large_base != NULL);
 	  large_alloc = aligned_upper_bound (large_alloc, alignb);
 	  offset = large_alloc;
 	  large_alloc += stack_vars[i].size;
+	  if (memory_tagging_p ())
+	    {
+	      /*
+		 The fact that these are all aligned objects means that we
+		 don't need to handle alignment of the object for tagging.
+
+		 However, we do need to ensure that the sizes we colour are
+		 also HWASAN_TAG_GRANULE_SIZE byte aligned.
+
+		 This clause is where we ensure that by rounding the size up.
+		 We know there will be no overlaps, since we know the start of
+		 the next object will be aligned to something greater than
+		 HWASAN_TAG_GRANULE_SIZE bytes.
+		 */
+	      poly_int64 align_again =
+		aligned_upper_bound (large_alloc, HWASAN_TAG_GRANULE_SIZE);
+	    }
 
 	  base = large_base;
 	  base_align = large_align;
@@ -1265,8 +1292,13 @@ expand_stack_vars (bool (*pred) (size_t), struct stack_vars_data *data)
 	{
 	  expand_one_stack_var_at (stack_vars[j].decl,
 				   base, base_align,
-				   offset);
+				   offset,
+				   memory_tagging_p ()
+				   ? data->asan_base
+				   : virtual_stack_vars_rtx);
 	}
+      if (memory_tagging_p ())
+	hwasan_increment_tag ();
     }
 
   gcc_assert (known_eq (large_alloc, large_size));
@@ -1362,7 +1394,8 @@ expand_one_stack_var_1 (tree var)
   offset = alloc_stack_frame_space (size, byte_align);
 
   expand_one_stack_var_at (var, virtual_stack_vars_rtx,
-			   crtl->max_used_stack_slot_alignment, offset);
+			   crtl->max_used_stack_slot_alignment, offset,
+			   virtual_stack_vars_rtx);
 }
 
 /* Wrapper for expand_one_stack_var_1 that checks SSA_NAMEs are
@@ -1964,6 +1997,8 @@ init_vars_expansion (void)
   /* Initialize local stack smashing state.  */
   has_protected_decls = false;
   has_short_buffer = false;
+  if (memory_tagging_p ())
+    hwasan_tag_init ();
 }
 
 /* Free up stack variable graph data.  */
diff --git a/gcc/config/aarch64/aarch64.md b/gcc/config/aarch64/aarch64.md
index 5a1894063a1ed2db1cc947c9c449d48808ed96ae..cb0d3ae6bbf3ed439c7b27683726f4c30b04777d 100644
--- a/gcc/config/aarch64/aarch64.md
+++ b/gcc/config/aarch64/aarch64.md
@@ -409,6 +409,23 @@ (define_expand "cbranch<mode>4"
   "
 )
 
+(define_expand "addtag<mode>4"
+  [(set (match_operand:GPI 0 "register_operand" "")
+    (addtag:GPI (match_operand:GPI 1 "register_operand" "")
+     (match_operand:GPI 2 "aarch64_MTE_add_temp" "")
+     (match_operand:GPI 3 "aarch64_MTE_tag_offset" "")))]
+  ""
+{
+  gcc_assert (can_create_pseudo_p ());
+  /* Simply add the two values as a constant and use that.  The adddi pattern
+     will handle the fact that the integer is out of range for ADD.  */
+  poly_int64 val = rtx_to_poly_int64 (operands[2]);
+  val += ((uint64_t)INTVAL(operands[3]) << 56);
+  emit_insn (gen_add<mode>3 (operands[0], operands[1],
+			     immed_wide_int_const (val, <MODE>mode)));
+  DONE;
+})
+
 (define_expand "cbranchcc4"
   [(set (pc) (if_then_else
 	      (match_operator 0 "aarch64_comparison_operator"
diff --git a/gcc/config/aarch64/predicates.md b/gcc/config/aarch64/predicates.md
index 10100ca830a0cd753ef5759e3ce09914b1046d26..e2aa0290f833fbffedec1d8dab219f72eb17419e 100644
--- a/gcc/config/aarch64/predicates.md
+++ b/gcc/config/aarch64/predicates.md
@@ -134,6 +134,13 @@ (define_predicate "aarch64_pluslong_immediate"
   (and (match_code "const_int")
        (match_test "(INTVAL (op) < 0xffffff && INTVAL (op) > -0xffffff)")))
 
+(define_predicate "aarch64_MTE_add_temp"
+  (ior (match_code "const_int") (match_code "const_poly_int")))
+
+(define_predicate "aarch64_MTE_tag_offset"
+  (and (match_code "const_int")
+       (match_test "IN_RANGE (INTVAL (op), 0, 16)")))
+
 (define_predicate "aarch64_pluslong_strict_immedate"
   (and (match_operand 0 "aarch64_pluslong_immediate")
        (not (match_operand 0 "aarch64_plus_immediate"))))
diff --git a/gcc/doc/tm.texi b/gcc/doc/tm.texi
index 622e8cf240fbf4834a7a39317aff844989b8b65f..67d79a23799cd3057f7d91bd538c7ee76c836f82 100644
--- a/gcc/doc/tm.texi
+++ b/gcc/doc/tm.texi
@@ -2968,6 +2968,11 @@ This hook defines the machine mode to use for the boolean result of  conditional
 A target hook which lets a backend compute the set of pressure classes to  be used by those optimization passes which take register pressure into  account, as opposed to letting IRA compute them.  It returns the number of  register classes stored in the array @var{pressure_classes}.
 @end deftypefn
 
+@deftypefn {Target Hook} void TARGET_MEMTAG_GENTAG (rtx @var{base}, rtx @var{untagged})
+Set the BASE argument to UNTAGGED with some random tag.
+This function is used to generate a tagged base for the current stack frame.
+@end deftypefn
+
 @node Stack and Calling
 @section Stack Layout and Calling Conventions
 @cindex calling conventions
diff --git a/gcc/doc/tm.texi.in b/gcc/doc/tm.texi.in
index 17560fce6b7a2cb0148e4dbac565eca588d5302e..e1ec503befadb4061fbd3b95e55757fe22d33c39 100644
--- a/gcc/doc/tm.texi.in
+++ b/gcc/doc/tm.texi.in
@@ -2370,6 +2370,8 @@ in the reload pass.
 
 @hook TARGET_COMPUTE_PRESSURE_CLASSES
 
+@hook TARGET_MEMTAG_GENTAG
+
 @node Stack and Calling
 @section Stack Layout and Calling Conventions
 @cindex calling conventions
diff --git a/gcc/dwarf2out.c b/gcc/dwarf2out.c
index 5979ac68fa86bf24fd096ad7754be05b59bc92f6..18364bbf8ee6e374678dcc9370750e297fb6daa2 100644
--- a/gcc/dwarf2out.c
+++ b/gcc/dwarf2out.c
@@ -14424,7 +14424,7 @@ based_loc_descr (rtx reg, poly_int64 offset,
 static inline int
 is_based_loc (const_rtx rtl)
 {
-  return (GET_CODE (rtl) == PLUS
+  return ((GET_CODE (rtl) == PLUS || GET_CODE (rtl) == ADDTAG)
 	  && ((REG_P (XEXP (rtl, 0))
 	       && REGNO (XEXP (rtl, 0)) < FIRST_PSEUDO_REGISTER
 	       && CONST_INT_P (XEXP (rtl, 1)))));
@@ -15877,6 +15877,7 @@ mem_loc_descriptor (rtx rtl, machine_mode mode,
 
       /* fall through */
 
+    case ADDTAG:
     case PLUS:
     plus:
       if (is_based_loc (rtl)
diff --git a/gcc/explow.h b/gcc/explow.h
index 5110ad82d6a024fda1d3a3eaf80de40c5e6ad3b6..333948e0c69a1b1132e9a1d06707dc63f1226262 100644
--- a/gcc/explow.h
+++ b/gcc/explow.h
@@ -102,7 +102,7 @@ extern rtx allocate_dynamic_stack_space (rtx, unsigned, unsigned,
 extern void get_dynamic_stack_size (rtx *, unsigned, unsigned, HOST_WIDE_INT *);
 
 /* Returns the address of the dynamic stack space without allocating it.  */
-extern rtx get_dynamic_stack_base (poly_int64, unsigned);
+extern rtx get_dynamic_stack_base (poly_int64, unsigned, rtx);
 
 /* Return an rtx doing runtime alignment to REQUIRED_ALIGN on TARGET.  */
 extern rtx align_dynamic_address (rtx, unsigned);
diff --git a/gcc/explow.c b/gcc/explow.c
index ba06458ebdc64db0859127df880742ae1007bd8c..07665b28a1ff3a0067f3bc559eb4508e0f3a96e4 100644
--- a/gcc/explow.c
+++ b/gcc/explow.c
@@ -477,7 +477,8 @@ memory_address_addr_space (machine_mode mode, rtx x, addr_space_t as)
 	    }
 	}
 
-      else if (GET_CODE (x) == MULT || GET_CODE (x) == MINUS)
+      else if (GET_CODE (x) == MULT || GET_CODE (x) == MINUS
+	       || GET_CODE (x) == ADDTAG)
 	x = force_operand (x, NULL_RTX);
 
       /* If we have a register that's an invalid address,
@@ -1586,10 +1587,15 @@ allocate_dynamic_stack_space (rtx size, unsigned size_align,
    OFFSET is the offset of the area into the virtual stack vars area.
 
    REQUIRED_ALIGN is the alignment (in bits) required for the region
-   of memory.  */
+   of memory.
+
+   BASE is the rtx of the base of this virtual stack vars area.
+   The only time this is not `virtual_stack_vars_rtx` is when tagging pointers
+   on the stack.
+   */
 
 rtx
-get_dynamic_stack_base (poly_int64 offset, unsigned required_align)
+get_dynamic_stack_base (poly_int64 offset, unsigned required_align, rtx base)
 {
   rtx target;
 
@@ -1597,7 +1603,7 @@ get_dynamic_stack_base (poly_int64 offset, unsigned required_align)
     crtl->preferred_stack_boundary = PREFERRED_STACK_BOUNDARY;
 
   target = gen_reg_rtx (Pmode);
-  emit_move_insn (target, virtual_stack_vars_rtx);
+  emit_move_insn (target, base);
   target = expand_binop (Pmode, add_optab, target,
 			 gen_int_mode (offset, Pmode),
 			 NULL_RTX, 1, OPTAB_LIB_WIDEN);
diff --git a/gcc/expr.c b/gcc/expr.c
index c78bc74c0d9f9005f284741863652852a295125b..fa4ee4e2068c26328e651c04f838b354225e4970 100644
--- a/gcc/expr.c
+++ b/gcc/expr.c
@@ -7464,6 +7464,16 @@ force_operand (rtx value, rtx target)
       return subtarget;
     }
 
+  if (code == ADDTAG)
+    {
+      /* Instead of just letting an ADD_TAG go through directly, call the
+         expand_ternary_op() function to ensure it gets expanded as the backend
+         requires.  */
+      return expand_ternary_op (GET_MODE (value), addtag_optab,
+				XEXP (value, 0), XEXP (value, 1),
+				XEXP (value, 2), target, 0);
+
+    }
   if (ARITHMETIC_P (value))
     {
       op2 = XEXP (value, 1);
diff --git a/gcc/optabs.def b/gcc/optabs.def
index 8af3a2f43fd99a36b69999d3fb50b9a6d5379964..7c73fc18bce72f88a7427359d966a5d9a8d51c05 100644
--- a/gcc/optabs.def
+++ b/gcc/optabs.def
@@ -99,6 +99,8 @@ OPTAB_CD (while_ult_optab, "while_ult$a$b")
 OPTAB_NL(add_optab, "add$P$a3", PLUS, "add", '3', gen_int_fp_fixed_libfunc)
 OPTAB_NX(add_optab, "add$F$a3")
 OPTAB_NX(add_optab, "add$Q$a3")
+/* TODO Currently don"t know what the gen_int_fp_fixed_libfunc field is for. */
+OPTAB_NL(addtag_optab, "addtag$P$a4", ADDTAG, "addtag", '4', gen_int_fp_fixed_libfunc)
 OPTAB_VL(addv_optab, "addv$I$a3", PLUS, "add", '3', gen_intv_fp_libfunc)
 OPTAB_VX(addv_optab, "add$F$a3")
 OPTAB_NL(ssadd_optab, "ssadd$Q$a3", SS_PLUS, "ssadd", '3', gen_signed_fixed_libfunc)
diff --git a/gcc/rtl.def b/gcc/rtl.def
index f4c9d946cb5aedb74b4cc9181987762151231855..4d6879481b5565248b8a3b188de58a7184547231 100644
--- a/gcc/rtl.def
+++ b/gcc/rtl.def
@@ -471,6 +471,14 @@ DEF_RTL_EXPR(COMPARE, "compare", "ee", RTX_BIN_ARITH)
 /* plus */
 DEF_RTL_EXPR(PLUS, "plus", "ee", RTX_COMM_ARITH)
 
+/* add_tag. This is used for memory tagging instructions.
+    Operands:
+      0:  Original
+      1:  Offset
+      2:  Tag Offset  */
+
+DEF_RTL_EXPR(ADDTAG, "addtag", "eee", RTX_TERNARY)
+
 /* Operand 0 minus operand 1.  */
 DEF_RTL_EXPR(MINUS, "minus", "ee", RTX_BIN_ARITH)
 
diff --git a/gcc/simplify-rtx.c b/gcc/simplify-rtx.c
index 89a46a933facaded1b23a84fa9a0924595b01e5a..91bf885e9e26459743caf11c91fa160585179905 100644
--- a/gcc/simplify-rtx.c
+++ b/gcc/simplify-rtx.c
@@ -5699,6 +5699,9 @@ simplify_ternary_operation (enum rtx_code code, machine_mode mode,
 
   switch (code)
     {
+    case ADDTAG:
+      return NULL_RTX;
+
     case FMA:
       /* Simplify negations around the multiplication.  */
       /* -a * -b + c  =>  a * b + c.  */
diff --git a/gcc/target.def b/gcc/target.def
index 7d52102c8153b4c86f6541da5e04c39251c2d42f..5326cb070dec78f19bfe0844a9d5e50c69e7dcc1 100644
--- a/gcc/target.def
+++ b/gcc/target.def
@@ -6705,6 +6705,18 @@ DEFHOOK
 HOOK_VECTOR_END (mode_switching)
 
 #undef HOOK_PREFIX
+#define HOOK_PREFIX "TARGET_MEMTAG_"
+HOOK_VECTOR (TARGET_MEMTAG_, memtag)
+
+DEFHOOK
+(gentag,
+ "Set the BASE argument to UNTAGGED with some random tag.\n\
+This function is used to generate a tagged base for the current stack frame.",
+  void, (rtx base, rtx untagged),
+  default_memtag_gentag)
+
+HOOK_VECTOR_END (memtag)
+#undef HOOK_PREFIX
 #define HOOK_PREFIX "TARGET_"
 
 #define DEF_TARGET_INSN(NAME, PROTO) \
diff --git a/gcc/targhooks.h b/gcc/targhooks.h
index 229aacd7b6597d75774e82594cfa332f37afcf3c..493ff3bb29263f8360bea0f7ead1092b4d0c646a 100644
--- a/gcc/targhooks.h
+++ b/gcc/targhooks.h
@@ -288,4 +288,5 @@ extern rtx default_speculation_safe_value (machine_mode, rtx, rtx, rtx);
 extern void default_remove_extra_call_preserved_regs (rtx_insn *,
 						      HARD_REG_SET *);
 
+extern void default_memtag_gentag (rtx, rtx);
 #endif /* GCC_TARGHOOKS_H */
diff --git a/gcc/targhooks.c b/gcc/targhooks.c
index b27111639f4960426ff2fc39a10ddc9237deaf61..58ec711ce81ee67d692e81d2616bd3422f6bd092 100644
--- a/gcc/targhooks.c
+++ b/gcc/targhooks.c
@@ -2391,4 +2391,16 @@ default_remove_extra_call_preserved_regs (rtx_insn *, HARD_REG_SET *)
 {
 }
 
+void
+default_memtag_gentag (rtx base, rtx untagged)
+{
+  /* TODO This function should emit instructions to calculate a random tag and
+     insert it into the `base` rtx.  At the moment we have a dummy function
+     that keeps `base` without a tag.  That helps for debugging since it means
+     variables are tagged starting from 1 in each function frame, which is
+     a bit easier to view.  */
+  emit_move_insn (base, untagged);
+}
+
+
 #include "gt-targhooks.h"