为什么 i = v[i++] 是未定义的？

Question

从C++（C++11）标准的§1.9.15讨论评估顺序，以下是示例代码：

void g(int i, int* v) {
    i = v[i++]; // the behavior is undefined
}

正如代码示例中所指出的那样，该行为是未定义的。

（注：另一个问题的答案具有略微不同的结构i + i ++，为什么a = i + i ++是未定义的而不是未指定的行为，可能适用于此处：实质上，答案是由于历史原因，行为是未定义的，而不是必然的。但是，标准似乎暗示了一些使其未定义的理由-请参见下面的引文。此外，该链接的问题表明同意行为应该是未指定的，而在这个问题中，我正在询问为什么行为不是良好定义的。）

标准给出的未定义行为的理由如下：

如果对标量对象的副作用相对于同一标量对象上的另一个副作用或使用同一标量对象的值计算来说是无序的，则该行为是未定义的。

在这个例子中，我认为子表达式i ++会在评估子表达式v [...]之前完全被评估，并且子表达式的评估结果是i（在增量之前），但是i的值是该子表达式被完全评估后递增的值。我认为此时（在子表达式i ++被完全评估后），将进行v [...]的评估，然后是分配i = ...。

因此，尽管递增i是无意义的，但我仍然认为这应该是定义明确的。

为什么这是未定义行为呢？

- Dan Nissenbaum

---

但是，那个引用似乎在谈论序列点，这又是一个可以追溯到C的概念。当然，我可能没有理解重点（请原谅双关语）。 - NPE

嗯...为什么要踩我？我总是喜欢学习应该做些什么不同的事情。 - Dan Nissenbaum

请注意，所有经典的“i++ goo”等示例都是未定义行为和未指定行为的混合体。未定义行为是指在表达式中连续给变量赋值而没有顺序点的情况，未指定行为是指子表达式计算的顺序不确定。这两种情况同时适用。 - Lundin

@widgg 我也期望有类似的结果，但是所有这些杰出的答案和评论都揭示了现实更加复杂。 - Dan Nissenbaum

@Karoly Horvath - 性能和C/C++并不吓唬我 - 我自20世纪70年代末就开始使用C语言了。未定义行为不能使用；即使今天可以工作，也不能保证将来能够正确工作。嗯 - 快速有错误的代码与（可能）稍慢但可靠的代码相比...更糟糕的是：通过升级编译器或计算机，错误可能会出现数年后？定义行为不一定会对性能产生负面影响。例如，操作顺序：允许可预测和可靠的优化-运行更快。（顺便说一句，很抱歉评论这样一个老帖子 - 不想让别人误解我的意思。） - Alan Jay Weiner

Answer 1

我认为子表达式i++在子表达式v[...]被评估之前会完全被评估。

但是，您为什么会这么想呢？

将此代码视为UB的一个历史原因是为了允许编译器优化在序列点之间移动副作用。 序列点越少，优化的机会就越多，但程序员就越困惑。 如果代码说：

a = v[i++];

该标准的意图是发出的代码可以：

a = v[i];
++i;

可能是两个指令，具体如下：

tmp = i;
++i;
a = v[tmp];

会超过两个。

当a为i时，“优化代码”会出错，但标准仍允许进行优化，因为它说当a为i时原始代码的行为是未定义的。

标准很容易可以规定必须在赋值之前评估i++，这样行为就会被完全定义并且优化将被禁止。但C和C++不是这样做生意的。

还要注意，在这些讨论中提出的许多示例比一般情况下更容易发现UB。这导致人们说这种行为应该被定义并且优化应该被禁止是“显而易见”的。但请考虑：

void g(int *i, int* v, int *dst) {
    *dst = v[(*i)++];
}

当i != dst时，此函数的行为已定义。此时需要尽可能多的优化（这就是C99引入restrict的原因，允许比C89或C++更多的优化）。 为了给您最佳优化，当i == dst时，该行为未定义。当涉及别名时，C和C ++标准之间存在微妙的平衡，既要避免程序员不希望看到的未定义行为，又要防止在某些情况下失败的期望优化。 SO上有关它的问题数量表明，提问者更喜欢少一些优化，多一些定义的行为，但仍然很难画出界限。

除了行为是否完全被定义的问题外，还有一个问题是它是否应该是UB，还是仅仅是对应于子表达式的某些已定义操作执行顺序未指定。 C之所以选择UB，与序列点的概念有关，事实上，直到下一个序列点，编译器实际上不需要对修改对象的值有任何概念。因此，标准没有通过约束优化器来说“该”值在某个未指定的点发生变化，而是说（引用）：（1）任何依赖修改对象的值的代码在下一个序列点之前都具有未定义行为；（2）任何修改已修改对象的代码都具有未定义行为。其中“修改对象”是指自上一次序列点以来，在一个或多个子表达式的合法评估顺序中，将进行修改的任何对象。

其他语言（例如Java）完全定义了表达式副作用的执行顺序，因此肯定有反对C方法的理由。但C++并不接受这种情况。

- Steve Jessop

---

+1，还要注意在现代CPU中，不同操作的成本是不同的，编译器可能会进行其他重排列，这可能导致更多但更快的操作。如果没有对处理器架构的深入理解，几乎不可能知道在这个微观水平上什么会更快，但那是编译器的工作。 - David Rodríguez - dribeas

@David：说得好，我提到了指令数量只是举例说明为什么允许优化是有益的。还有很多很多其他原因。 - Steve Jessop

非常感谢您的出色回答。我希望我能够接受多个答案！ - Dan Nissenbaum

Answer 2

我打算设计一台病态电脑¹。它是一个多核、高延迟、单线程系统，具有线程内合并，在字节级指令下运行。因此，您发出请求，然后计算机运行（在其自己的“线程”或“任务”中）一组字节级指令，并且在若干个周期之后，操作完成。

与此同时，执行的主线程继续：

void foo(int v[], int i){
  i = v[i++];
}

变成伪代码:

input variable i // = 0x00000000
input variable v // = &[0xBAADF00D, 0xABABABABAB, 0x10101010]
task get_i_value: GET_VAR_VALUE<int>(i)
reg indx = WAIT(get_i_value)
task write_i++_back: WRITE(i, INC(indx))
task get_v_value: GET_VAR_VALUE<int*>(v)
reg arr = WAIT(get_v_value)
task get_v[i]_value = CALC(arr + sizeof(int)*indx)
reg pval = WAIT(get_v[i]_value)
task read_v[i]_value = LOAD_VALUE<int>(pval)
reg got_value = WAIT(read_v[i]_value)
task write_i_value_again = WRITE(i, got_value)
(discard, discard) = WAIT(write_i++_back, write_i_value_again)

所以你会注意到我没有等到write_i++_back在最后才执行，也没有等到我在等待write_i_value_again（我从v[]中读取的值）的同时等待，实际上这些写操作是唯一回写内存的操作。

想象一下，如果向内存写数据是计算机设计中真正缓慢的部分，并且它们被批量处理成一个由并行内存修改单元处理的队列，该单元按字节为单位进行操作。

因此，write(i, 0x00000001)和write(i, 0xBAADF00D)是无序且并行执行的。每个写操作都被转换为字节级别的写操作，并且它们被随机排序。

我们最终会写入高位字节0x00和0xBA，然后写入接下来的字节0xAD和0x00，然后写入下一个字节的0xF0 0x00，最后写入低位字节的0x0D 0x01。i中的结果值为0xBA000001，这可能出乎意料，但对于未定义的操作来说是有效的结果。

现在，我所做的只是导致一个未指定的值。我们没有崩溃系统。但是编译器可以使它完全未定义--也许在同一批指令中向内存控制器发送两个相同地址的请求实际上会使系统崩溃。这仍然是编译C++的“有效”方式和“有效”执行环境。

请记住，这是一种语言，在其中将指针大小限制为8位仍然是一个有效的执行环境。C++允许编译成相当奇怪的目标。

- Yakk - Adam Nevraumont

---

我打算设计一台病态计算机... 目标有些扭曲。如果不是很明显，Yakk所描述的与现代x86或AMD64处理器非常相似，直到写操作被分解为独立的字节写操作。指令流水线有时对性能产生巨大影响，并且序列点限制编译器等待管道中的操作完成。 - Steve Jessop

这是一个出色的答案，谢谢。我问这个问题的原因是因为我正在努力理解编译级（甚至汇编级）的细节，尽管很多/大多数这些细节并未由标准规定...然而，正如这个例子所示，它们之间存在相互影响。 - Dan Nissenbaum

正如Steve所指出的那样，现代高速CPU设计具有这些复杂的指令流水线，即使在汇编级别上也是不可见的（只是为了向后兼容）。你认为的EAX寄存器实际上只是一个瞬间带有标签EAX的随机寄存器。 - MSalters

有很多优秀的答案回答了这个问题。我很感激。这个特别的答案让我深有感触。谢谢。 - Dan Nissenbaum

多年过去了，我仍然认为这个答案是我见过的最有启发性的答案之一——它改变了我对C++的理解。现在我明白了为什么那个结构没有被定义。 - Dan Nissenbaum

Answer 3

原因不仅仅是历史的原因。例如：

int f(int& i0, int& i1) {
    return i0 + i1++;
}

现在，针对这个调用会发生什么呢：

int i = 3;
int j = f(i, i);

当然可以对f中的代码进行限制，以使此调用的结果定义良好（Java就是这样做的），但C和C++不强制施加约束；这使得优化器拥有更多自由。

- Pete Becker

---

与我的答案相比，我看到你为什么可以编辑标准而我不能。 - Steve Jessop

@SteveJessop，我很想知道你在这里看到了什么不同于你的帖子，让你说出这样的话（两个答案都很好）。 - Dan Nissenbaum

@Dan：这个要短得多 :-) - Steve Jessop

Answer 4

你特别提到了C++11标准，所以我会用C++11的答案回答。然而，它与C++03的答案非常相似，但序列化的定义不同。

C++11在单个线程的计算之间定义了一种先于排序关系。它是非对称的、可传递的和成对的。如果某个计算A不是先于某个计算B，且B也不是先于A，则这两个计算是未排序的。

计算一个表达式包括值的计算（求出某个表达式的值）和副作用。 副作用 的一种实例是对象的修改，这是回答问题最重要的一点。其他事情也算是副作用。如果一个副作用相对于同一对象上的另一个副作用或值计算未排序，则您的程序具有未定义的行为。

所以这就是设置。第一个重要规则是：

与完整表达式相关的每个值计算和副作用都先于将要计算的下一个完整表达式的每个值计算和副作用。

因此，在下一个完整表达式之前，任何完整表达式都会被完全评估。在你的问题中，我们只处理一个完整表达式，即i = v [i ++]，因此我们不需要担心这个问题。下一个重要规则是：

除非另有说明，否则各个运算符的操作数和各个表达式的子表达式的评估未排序。

这意味着在例如a + b中，对a和b的评估是未排序的（它们可以以任何顺序评估）。现在轮到我们最后一个重要规则了：

操作符的操作数的值计算先于操作符结果的值计算。

因此，对于a + b，排序关系可以用树表示，其中有向箭头表示排序关系：

a + b (value computation)
^   ^
|   |
a   b (value computation)

如果两个评估发生在树的不同分支中，则它们是无序的，因此该树表明a和b的评估相对于彼此是无序的。

现在，让我们对i = v [i ++]的示例执行相同的操作。我们利用了v [i ++]被定义为等价于 *（v +（i ++））这一事实。我们还使用了有关后缀递增顺序的一些额外知识：

“++”表达式的值计算在修改操作数对象之前排序。

因此，在这里我们进行如下操作（树的节点是值计算，除非指定为副作用）：

i = v[i++]
^     ^
|     |
i★  v[i++] = *(v + (i++))
                  ^
                  |
               v + (i++)
               ^     ^
               |     |
               v     ++ (side effect on i)★
                     ^
                     |
                     i

在这里，您可以看到对i的副作用i++在赋值运算符前面i的使用(我用★标记了每个评估)是分开的。所以我们肯定有未定义的行为！如果您想知道您的评估排序是否会引起问题，我强烈推荐绘制这些图表。

现在我们提出一个问题，即赋值运算符之前的i的值并不重要，因为我们无论如何都会覆盖它。但事实上，在一般情况下，这并不是真的。我们可以覆盖赋值运算符并利用赋值之前对象的值。标准并不关心我们不使用该值-规则被定义为具有任何值计算与副作用不排序将导致未定义的行为。没有例外。此未定义行为旨在允许编译器生成更优化的代码。如果我们为赋值运算符添加排序，就无法使用此优化。

- Joseph Mansfield

---

我认为这种推理是不正确的。如果我错了，请纠正我，但您可以使用相同的推理来解释表达式i = v[++i];，得出该表达式也将是未定义行为，但实际上它是一个定义良好的代码。我认为在此帖子（https://dev59.com/Ymgv5IYBdhLWcg3wMN-0）中给出的答案更加精确。 - domdrag

Answer 5

在这个例子中，我认为子表达式 i++ 在子表达式 v [...] 被评估之前会被完全评估，并且子表达式的评估结果是 i（增量前的值），但是在该子表达式被完全评估后，i 的值是增量后的值。在 i++ 中，增量必须在索引 v 之前进行评估，因此在分配给 i 之前，但是将该增量的值存储回内存不一定会在之前发生。在语句 i = v[i++] 中，有两个子操作修改了 i（即最终会导致从寄存器到变量 i 的存储），表达式 i++ 相当于 x=i+1，i=x，并且没有要求两个操作必须按顺序执行：

x = i+1;
y = v[i];
i = y;
i = x;

随着这种扩展，i 的结果与 v[i] 中的值无关。在另一种扩展中，i = x 赋值可能会在 i = y 赋值之前进行，结果将是 i = v[i]

- David Rodríguez - dribeas

Answer 6

有两条规则。

第一条规则是关于多次写入引起的“写-写冲突”的： 在连续两个序列点之间，同一对象不能被修改超过一次。

第二条规则是关于“读-写冲突”的。它是这样的：如果一个对象在表达式中被修改并且也被访问，则所有对其值的访问必须是为了计算新值。

像i++ + i++和你的表达式i = v[i++]违反了第一条规则。它们会修改一个对象两次。

像i + i++这样的表达式违反了第二条规则。左边的子表达式i观察到一个已修改对象的值，而没有参与计算其新值。

因此，i = v[i++]违反了不同的规则（不良写-写），与i + i++（不良读-写）违反了不同的规则。

---

这些规则过于简单，导致了一类令人困惑的表达式。看看这个例子：

p = p->next = q

这个代码片段看起来具有合理的数据流依赖，没有出现危险情况：赋值表达式 p = 在新值已知之前不会执行。新值是 p->next = q 的结果，q 的值不应该“超越” p，从而影响到 p->next。

然而，这个表达式违反了第二条规则：修改了 p，还用于与计算其新值无关的目的，即确定存储 q 值的位置！

因此，编译器可以狡猾地部分评估 p->next = q，以确定其结果为 q，并将其存储到 p 中，然后回过头来完成 p->next = 赋值。或者看起来是这样。

这里的一个关键问题是，赋值表达式的值是什么？C标准规定，赋值表达式的值是左值的值，在赋值之后。但这是模棱两可的：它既可以被解释为意味着“一旦赋值发生，左值将拥有的值”，也可以被解释为意味着“在赋值发生后可以在左值中观察到的值”。在C++中，通过用词“[在所有情况下，赋值都是在右侧和左侧操作数的值计算之后，赋值表达式的值计算之前进行的]”，这一点变得明确了。因此，p = p->next = q 看起来是有效的C++代码，但却是可疑的C代码。

- Kaz

---

有趣的是，由于您所指示的C++规范措辞，保证p = p->next = q按预期工作的保证是在将规则应用于第二个赋值时得到的：第二个赋值操作（第一个等号）的rhs（以及lhs）必须在执行赋值之前完成其副作用，并且此rhs值是第一个赋值操作（第二个等号）完成的结果。 - Dan Nissenbaum

Answer 7

如果例子是v[++i]，我会支持你的观点，但由于i++会副作用地修改i，所以无法确定值何时被修改。标准可能可以强制规定一种结果，但没有确切的方法知道i的值应该是(i + 1)还是(v[i + 1])。

- moswald

---

在求值包含表达式之前，难道不必先评估子表达式的所有副作用吗？ - Dan Nissenbaum

不，那是求值顺序。这个例子要简单得多：它使用了i的值并修改了i，没有中间的序列点。是的，在像这样的简单情况下定义它的含义是可能的，但是当你深入到一个函数内部时，由于传递的参数导致其执行类似操作时，很难看出什么是明智的规则。 - Pete Becker

@DanNissenbaum - 不，副作用必须在下一个序列点完成。有时子表达式被两个序列点限定，但并非总是如此。愚蠢的例子：i++ && i 是定义良好的，因为 && 引入了一个序列点。i++ + i 则不是；+ 不会引入序列点。 - Pete Becker

请注意，即使是在++i的情况下，也有两个操作：增量（在寄存器中执行）和写回到i。写回操作与表达式的其余部分不是顺序执行的，因此即使在索引数组之前计算增量，写回操作可能会在赋值后发生。 - David Rodríguez - dribeas

@DavidRodríguez-dribeas 已经明白了。我只是觉得其中涉及 ++i 的那个特别不直观，而且我希望早些时候能向标准委员会提出论点。 :) - moswald

Answer 8

假设已经声明如下内容，请考虑每个赋值语句所需的机器操作序列：

extern int *foo(void);
extern int *p;

*p = *foo();
*foo() = *p;

如果左侧下标的计算和右侧值的评估是无序的，则处理这两个函数调用的最有效方法可能类似于：

[For *p = *foo()]
call foo (which yields result in r0 and trashes r1)
load r0 from address held in r0
load r1 from address held in p
store r0 to address held in r1

[For *foo() = *p]
call foo (which yields result in r0 and trashes r1)
load r1 from address held in p
load r1 from address held in r1
store r1 to address held in r0

无论哪种情况，如果在调用foo之前将p或*p读入寄存器中，则除非“foo”承诺不干扰该寄存器，否则编译器需要添加额外的步骤来保存其值，然后再调用“foo”，并在调用后恢复该值。通过使用“foo”不会干扰的寄存器，可以避免这个额外的步骤，但是只有在周围代码不需要该寄存器中的值时才有帮助。

让编译器在其自由时间内读取“p”的值，可以有效地处理上述两种模式。要求在右侧操作数之前始终评估“=”的左侧操作数的地址可能会使上述第一个赋值比它本来可以更有效率，并且要求在右侧操作数之后评估左侧操作数的地址会使第二个赋值不那么有效率。

- supercat