コグノスケ

GCCを調べる - memmoveのfoldingその2

目次: GCC

前回はmemmove() が030t.ccp1という最適化パスにて __builtin_memcpy() に置き換えられ、誤動作してしまうところまで見ました。今回はどこで置き換えられているのか、追いかけます。

入れ替えを行っている場所はgimple_fold_builtin_memory_op() という関数です。コールスタックは下記のようになります。今回はGCC 11というかHEADを使います。関数名は若干違いますがGCC 8くらいでも大筋は同じです。

do_ssa_ccp()  @tree-ssa-ccp.c
  ccp_finalize()
    substitute_and_fold_engine::substitute_and_fold()  @tree-ssa-propagate.c
      substitute_and_fold_dom_walker walker (CDI_DOMINATORS, this);
      walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
        dom_walker::walk()  @domwalk.c
          substitute_and_fold_dom_walker::before_dom_children()  @tree-ssa-propagate.c
            fold_stmt()  @gimple-fold.c
              fold_stmt_1()  @gimple-fold.c
                gimple_fold_call()
                  gimple_fold_builtin()
                    gimple_fold_builtin_memory_op()

置き換えている箇所はgimple_fold_builtin_memory_op() 内に3箇所ありますが、今回のケースに該当するのは下記の部分です。

// gcc/gcc/gimple-fold.c

static bool
gimple_fold_builtin_memory_op (gimple_stmt_iterator *gsi,
			       tree dest, tree src, enum built_in_function code)
{
  gimple *stmt = gsi_stmt (*gsi);
  tree lhs = gimple_call_lhs (stmt);
  tree len = gimple_call_arg (stmt, 2);
  location_t loc = gimple_location (stmt);

...

      if (code == BUILT_IN_MEMMOVE)
	{

...

	  /* If *src and *dest can't overlap, optimize into memcpy as well.  */
	  if (TREE_CODE (src) == ADDR_EXPR
	      && TREE_CODE (dest) == ADDR_EXPR)
	    {

              //...ここでチェックしている...

	      fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
	      if (!fn)
		return false;
	      gimple_call_set_fndecl (stmt, fn);    //★★ここでmemmove -> memcpyに置き換わる
	      gimple_call_set_arg (stmt, 0, dest);
	      gimple_call_set_arg (stmt, 1, src);
	      fold_stmt (gsi);
	      return true;
	    }

...

/*
 * 補足: gimple * の中身が見たいときは、下記のようにすると表示できます。
 *
 *   print_gimple_stmt (stdout, stmt, 0);       //HEAD
 *   print_gimple_stmt (stdout, stmt, 0, 0);    //GCC 8あたり
 */

検証プログラムはmemmove() の引数にポインタを渡しているので、TREE_CODE (src) == ADDR_EXPR && TREE_CODE (dest) == ADDR_EXPRの条件が成立します。

置き換えの前にはいくつかチェックがあって、memmove() をmemcpy() に置き換えるべきではないと判断したらreturn false; し、置き換え箇所に到達しない仕組みになっています。

// gcc/gcc/gimple-fold.c

	  /* If *src and *dest can't overlap, optimize into memcpy as well.  */
	  if (TREE_CODE (src) == ADDR_EXPR
	      && TREE_CODE (dest) == ADDR_EXPR)
	    {
	      tree src_base, dest_base, fn;
	      poly_int64 src_offset = 0, dest_offset = 0;
	      poly_uint64 maxsize;

              //★★src->expr.operands[0] を返す、srcvarはMEM_REFタイプ
	      srcvar = TREE_OPERAND (src, 0);
              //★★src_baseはVAR_DECLタイプ
              //★★src_offsetは2（検証用プログラムでmemmoveのsrcにs + 2を渡しているから）
	      src_base = get_addr_base_and_unit_offset (srcvar, &src_offset);
	      if (src_base == NULL)
		src_base = srcvar;

              //★★dest->expr.operands[0] を返す、destvarはMEM_REFタイプ
	      destvar = TREE_OPERAND (dest, 0);
              //★★dest_baseはVAR_DECLタイプ
              //★★dest_offsetは0（検証用プログラムでdestにsを渡しているから）
	      dest_base = get_addr_base_and_unit_offset (destvar,
							 &dest_offset);
	      if (dest_base == NULL)
		dest_base = destvar;
	      if (!poly_int_tree_p (len, &maxsize))
		maxsize = -1;
	      if (SSA_VAR_P (src_base)
		  && SSA_VAR_P (dest_base))    //★★この条件が成立する
		{
                  //★★volatileがあるとoperand_equal_p() がfalseになり
                  //★★memmoveがmemcpyに置き換えられてしまう
		  if (operand_equal_p (src_base, dest_base, 0)
		      && ranges_maybe_overlap_p (src_offset, maxsize,
						 dest_offset, maxsize))
		    return false;    //★★チェック1箇所目
		}
	      else if (TREE_CODE (src_base) == MEM_REF
		       && TREE_CODE (dest_base) == MEM_REF)
		{
		  if (! operand_equal_p (TREE_OPERAND (src_base, 0),
					 TREE_OPERAND (dest_base, 0), 0))
		    return false;
		  poly_offset_int full_src_offset
		    = mem_ref_offset (src_base) + src_offset;
		  poly_offset_int full_dest_offset
		    = mem_ref_offset (dest_base) + dest_offset;
		  if (ranges_maybe_overlap_p (full_src_offset, maxsize,
					      full_dest_offset, maxsize))
		    return false;    //★★チェック2箇所目
		}
	      else
		return false;    //★★チェック3箇所目

	      fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
	      if (!fn)
		return false;
	      gimple_call_set_fndecl (stmt, fn);    //★★ここでmemmove -> memcpyに置き換わる
	      gimple_call_set_arg (stmt, 0, dest);
	      gimple_call_set_arg (stmt, 1, src);
	      fold_stmt (gsi);
	      return true;
...


// gcc/gcc/tree-dfa.c

/* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
   denotes the starting address of the memory access EXP.
   Returns NULL_TREE if the offset is not constant or any component
   is not BITS_PER_UNIT-aligned.  */

tree
get_addr_base_and_unit_offset (tree exp, poly_int64_pod *poffset)
{
  return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
}


/* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
   denotes the starting address of the memory access EXP.
   Returns NULL_TREE if the offset is not constant or any component
   is not BITS_PER_UNIT-aligned.
   VALUEIZE if non-NULL is used to valueize SSA names.  It should return
   its argument or a constant if the argument is known to be constant.  */

tree
get_addr_base_and_unit_offset_1 (tree exp, poly_int64_pod *poffset,
				 tree (*valueize) (tree))
{
  poly_int64 byte_offset = 0;

  /* Compute cumulative byte-offset for nested component-refs and array-refs,
     and find the ultimate containing object.  */
  while (1)
    {
      switch (TREE_CODE (exp))
	{

...

	case MEM_REF:
	  {
	    tree base = TREE_OPERAND (exp, 0);
	    if (valueize
		&& TREE_CODE (base) == SSA_NAME)
	      base = (*valueize) (base);

	    /* Hand back the decl for MEM[&decl, off].  */
	    if (TREE_CODE (base) == ADDR_EXPR)
	      {
		if (!integer_zerop (TREE_OPERAND (exp, 1)))
		  {
		    poly_offset_int off = mem_ref_offset (exp);
		    byte_offset += off.force_shwi ();
		  }
		exp = TREE_OPERAND (base, 0);
	      }
	    goto done;
	  }


// gcc/gcc/tree.h

#define SSA_VAR_P(DECL)							\
	(TREE_CODE (DECL) == VAR_DECL					\
	 || TREE_CODE (DECL) == PARM_DECL				\
	 || TREE_CODE (DECL) == RESULT_DECL				\
	 || TREE_CODE (DECL) == SSA_NAME)

領域が重複している場合は、1箇所目のチェックに引っかかります。不思議なことに、配列sの宣言からvolatileを外して動かすと、1箇所目のチェックに引っかかりますが、volatileを付けるとチェックに引っかからなくなります。

int main(int argc, char *argv[])
{
	volatile char s[] = PRE STR;    //★★volatileを外すと __builtin_memcpy() への置き換えが発生しなくなる
	char *p = (char *)s;
	size_t sz_pre = strlen(PRE);
	size_t sz = strlen(p) - sz_pre + 1;

本来はvolatileがあろうがなかろうが1箇所目のチェックに引っかからないとおかしいですが、volatileがあるときは、なぜか1箇所目のチェックを通過してしまいます。

長くなってきたので、続きはまた次回。