目次: 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箇所目のチェックを通過してしまいます。
長くなってきたので、続きはまた次回。
目次: GCC
前回はmemmove() をmemcpy() に置き換える条件をチェックしているコードを紹介しました。より詳細に見ていきたいと思います。ここまで細かい話になると、もはや自分以外の誰得なのか全くわかりませんけど、そんなことを気にしてはいけません。
前回紹介したチェック箇所のうちvolatileの有無で動きが変わるのは、下記のoperand_equal_p() です。
// gcc/gcc/gimple-fold.c
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箇所目
}
// gcc/gcc/fold-const.c
/* Return nonzero if two operands (typically of the same tree node)
are necessarily equal. FLAGS modifies behavior as follows:
If OEP_ONLY_CONST is set, only return nonzero for constants.
This function tests whether the operands are indistinguishable;
it does not test whether they are equal using C's == operation.
The distinction is important for IEEE floating point, because
(1) -0.0 and 0.0 are distinguishable, but -0.0==0.0, and
(2) two NaNs may be indistinguishable, but NaN!=NaN.
If OEP_ONLY_CONST is unset, a VAR_DECL is considered equal to itself
even though it may hold multiple values during a function.
This is because a GCC tree node guarantees that nothing else is
executed between the evaluation of its "operands" (which may often
be evaluated in arbitrary order). Hence if the operands themselves
don't side-effect, the VAR_DECLs, PARM_DECLs etc... must hold the
same value in each operand/subexpression. Hence leaving OEP_ONLY_CONST
unset means assuming isochronic (or instantaneous) tree equivalence.
Unless comparing arbitrary expression trees, such as from different
statements, this flag can usually be left unset.
If OEP_PURE_SAME is set, then pure functions with identical arguments
are considered the same. It is used when the caller has other ways
to ensure that global memory is unchanged in between.
If OEP_ADDRESS_OF is set, we are actually comparing addresses of objects,
not values of expressions.
If OEP_LEXICOGRAPHIC is set, then also handle expressions with side-effects
such as MODIFY_EXPR, RETURN_EXPR, as well as STATEMENT_LISTs.
If OEP_BITWISE is set, then require the values to be bitwise identical
rather than simply numerically equal. Do not take advantage of things
like math-related flags or undefined behavior; only return true for
values that are provably bitwise identical in all circumstances.
Unless OEP_MATCH_SIDE_EFFECTS is set, the function returns false on
any operand with side effect. This is unnecesarily conservative in the
case we know that arg0 and arg1 are in disjoint code paths (such as in
?: operator). In addition OEP_MATCH_SIDE_EFFECTS is used when comparing
addresses with TREE_CONSTANT flag set so we know that &var == &var
even if var is volatile. */
bool
operand_compare::operand_equal_p (const_tree arg0, const_tree arg1,
unsigned int flags)
{
bool r;
if (verify_hash_value (arg0, arg1, flags, &r))
return r;
...
/* If ARG0 and ARG1 are the same SAVE_EXPR, they are necessarily equal.
We don't care about side effects in that case because the SAVE_EXPR
takes care of that for us. In all other cases, two expressions are
equal if they have no side effects. If we have two identical
expressions with side effects that should be treated the same due
to the only side effects being identical SAVE_EXPR's, that will
be detected in the recursive calls below.
If we are taking an invariant address of two identical objects
they are necessarily equal as well. */
if (arg0 == arg1 && ! (flags & OEP_ONLY_CONST)
&& (TREE_CODE (arg0) == SAVE_EXPR
|| (flags & OEP_MATCH_SIDE_EFFECTS)
|| (! TREE_SIDE_EFFECTS (arg0) && ! TREE_SIDE_EFFECTS (arg1))))
return true; //★★volatileがないときは、このチェックに引っかかるが、volatileがあると引っかからない
...
変化する箇所を見つけましたので、条件を全部バラしてvolatileの有無でどの条件が変化するか調べます。GCCはこういう訳のわからないif文を連発してくるため、非常に解析が大変です……。
// ★★下記のように条件を全て展開して差分を調べる
int a, b, c, d, e, f, g;
a = arg0 == arg1;
b = ! (flags & OEP_ONLY_CONST);
c = TREE_CODE (arg0) == SAVE_EXPR;
d = flags & OEP_MATCH_SIDE_EFFECTS;
e = ! TREE_SIDE_EFFECTS (arg0); //★★この条件が変わる
f = ! TREE_SIDE_EFFECTS (arg1); //★★この条件が変わる
g = ppa && ppb && (ppc || ppd || (ppe && ppf));
/*
* volatileなし
* (a, b, c, d, e, f, g)
* (1, 1, 0, 0, 1, 1, 1)
* volatileあり
* (a, b, c, d, e, f, g)
* (1, 1, 0, 0, 0, 0, 0)
*
* volatileありのときはside_effects_flagが1になる。
*/
// gcc/gcc/tree.h
/* In any expression, decl, or constant, nonzero means it has side effects or
reevaluation of the whole expression could produce a different value.
This is set if any subexpression is a function call, a side effect or a
reference to a volatile variable. In a ..._DECL, this is set only if the
declaration said `volatile'. This will never be set for a constant. */
#define TREE_SIDE_EFFECTS(NODE) \
(NON_TYPE_CHECK (NODE)->base.side_effects_flag)
//★★参考: side_effects_flagを設定する場所
// gcc/gcc/c-family/c-common.c
/* Apply the TYPE_QUALS to the new DECL. */
void
c_apply_type_quals_to_decl (int type_quals, tree decl)
{
tree type = TREE_TYPE (decl);
if (type == error_mark_node)
return;
if ((type_quals & TYPE_QUAL_CONST)
|| (type && TREE_CODE (type) == REFERENCE_TYPE))
/* We used to check TYPE_NEEDS_CONSTRUCTING here, but now a constexpr
constructor can produce constant init, so rely on cp_finish_decl to
clear TREE_READONLY if the variable has non-constant init. */
TREE_READONLY (decl) = 1;
if (type_quals & TYPE_QUAL_VOLATILE)
{
TREE_SIDE_EFFECTS (decl) = 1; //★★ここで設定する
TREE_THIS_VOLATILE (decl) = 1;
}
if (type_quals & TYPE_QUAL_RESTRICT)
{
while (type && TREE_CODE (type) == ARRAY_TYPE)
/* Allow 'restrict' on arrays of pointers.
FIXME currently we just ignore it. */
type = TREE_TYPE (type);
if (!type
|| !POINTER_TYPE_P (type)
|| !C_TYPE_OBJECT_OR_INCOMPLETE_P (TREE_TYPE (type)))
error ("invalid use of %<restrict%>");
}
}
もしsrcやdestにvolatile修飾子が付いていると、side_effects_flagがセットされます。このフラグがセットされていると、GCCはアドレスをチェックすることなく、問答無用でsrcとdestは「等しくない」と判断します。その結果srcとdestは重なっていないことになって、memmove() をmemcpy() に置き換える最適化が働きます。
正直な感想としてはGCCバグってるだろ……と思いますが、volatile変数はいつ書き換わってもおかしくないので、memmove() をmemcpy() に置き換えて、動作がおかしくなっても規格違反にはならない?うーん、良くわかりませんね。
ちなみにClang/LLVMはこのような最適化は行いません。memmove() はmemmove() の呼び出しのままです。
さらに厄介なことにx86_64のglibcはmemmove() を呼ぶべき場面でmemcpy() を呼んでも、正常に動いてしまいます。検証用のプログラムを下記のように変えます。
#include <stdio.h>
#include <string.h>
#define PRE "AB"
#define STR "0123456789abcdefg"
#define NOP __asm__ volatile("nop;")
int main(int argc, char *argv[])
{
volatile char s[] = PRE STR;
char *p = (char *)s;
size_t sz_pre = strlen(PRE);
size_t sz = strlen(p) - sz_pre + 1;
NOP;
memcpy(p, p + sz_pre, sz);
NOP; NOP;
if (strcmp(p, STR) == 0) {
printf(" OK: %s\n", p);
} else {
printf(" NG: %s\n", p);
}
}
オプション -fno-builtinを指定すると、GCCがmemcpy() をアセンブラへ展開しようとする最適化を抑制することができます。
$ gcc -O2 -Wall -g test.c -fno-builtin $ objdump -drS a.out ... NOP; 10b7: 90 nop size_t sz = strlen(p) - sz_pre + 1; 10b8: 48 83 c2 01 add $0x1,%rdx memcpy(p, p + sz_pre, sz); 10bc: 48 8d 74 1d 00 lea 0x0(%rbp,%rbx,1),%rsi 10c1: 48 89 ef mov %rbp,%rdi size_t sz = strlen(p) - sz_pre + 1; 10c4: 48 29 da sub %rbx,%rdx memcpy(p, p + sz_pre, sz); 10c7: e8 94 ff ff ff callq 1060 <memcpy@plt> ;★★memcpyを呼んでいる NOP; NOP; 10cc: 90 nop 10cd: 90 nop $ ./a.out OK: 0123456789abcdefg
この動作でもC言語仕様に違反するわけではありません。しかしGCCが間違ってmemmove() をmemcpy() に置き換えるようなバグがあったときに、意図せず隠蔽してしまいます。ありがたいような、ありがたくないような実装ですね。
人によると思うんですけど、私は机に対して椅子の高さが低すぎると、肘で体重を支えるようになり異常に肩が痛くなります。肩が痛いのは嫌なので椅子の高さを調節していたはずなのに、なぜか最近また肩が痛くなってきました。
これはおかしいと思って椅子の高さを確認すると、いつの間にか下がっています。高さ調整機能がヘタっているのか?時間とともにジワジワ下がっているようです。
なんてことするんだ、やめてー。
メモ: 技術系?の話はFacebookから転記しておくことにした。
目次: OpenCL
一部OpenVXの話も含まれています。
< | 2021 | > | ||||
<< | < | 03 | > | >> | ||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
- | 1 | 2 | 3 | 4 | 5 | 6 |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 | - | - | - |
合計:
本日:
管理者: Katsuhiro Suzuki(katsuhiro( a t )katsuster.net)
This is Simple Diary 1.0
Copyright(C) Katsuhiro Suzuki 2006-2023.
Powered by PHP 8.2.18.
using GD 2.3.3(png support.)