为什么变量 "i" 和 "j" 在控制流图中被认为是死的？
Why are the variables "i" and "j" considered dead in the control flow graph?
我正在研究红龙书上的归纳变量消除的话题，在那里我遇到了下面的例子。
Consider the control flow graph below :
Fig. 1 : Original Control Flow Graph
Now the authors apply strength reduction to the above graph to obtain the graph below:
Fig 2: Control flow graph after applying strength reduction
Example 10.4. After reduction in strength is applied to the inner loops around B2 and B3, the only use of i and j is to determine the outcome of the test in block B4. We know that the values of i and t2 satisfy the relationship t2 = 4*i, while those of j and t4 satisfy the relationship t4 = 4* j, so the test t2>=t4 is equivalent to i> = j. Once this replacement is made, i in block B2 and j in block B3 become dead variables and the assignments to them in these blocks become dead code that can be eliminated, resulting in the flow graph shown in Fig. 3 below. □
Fig 3: Flow graph after induction variable elimination
我没有得到的是“块B2中的i和块B3中的j成为死变量”的说法。但是，如果我们沿着图 2 中的绿色路径考虑下图：
变量 i 和 j 可能分别存在于块 B2 和 B3 中，如果我们沿着如图所示的绿色路径前进并计数在赋值的右侧使用 i 和 j（在各自的块中）。该特定用途是
变量不再有效，因为它们没有可观察到的效果。
它们会递增和递减，但绝不会出于任何目的查阅这些值。它们没有打印出来。没有控制流依赖于它们。没有其他变量是使用它们的值计算的。如果它们不递增和递减，没有人会注意到。
消除它们不会以任何方式影响程序输出。所以他们应该被淘汰。
作为活跃度的更正式的定义，我们可以从以下开始：
如果变量的值变得可观察（通过在程序执行之外可见，见下文），则变量是活动的（在程序中的某个点）。
如果变量的当前值用于计算活动值，则该变量也是活动的。
该递归定义排除了仅用于计算其自身或其他非活动变量的值的未使用变量的使用。这只是我在答案的第一部分所说内容的一种更准确的表达方式：如果消除赋值不会对程序的执行产生明显的影响，那么赋值是无关紧要的。
“可观察效果”的准确定义会因计算模型而异，但它基本上意味着该值以某种方式传达给程序执行之外的世界。例如，如果在控制台上打印或写入文件（包括用作要创建的文件的名称，因为文件目录也是文件），则该值是实时的。如果它存储在数据库中，或者导致指示灯闪烁，则它是实时的。 C 标准包括在可观察行为读写 volatile memory 的类别中，这是一种封装 CPUs 的方式，它使用特定内存地址的加载和存储作为一种方式从外围设备发送和接收数据。
有一个古老的哲学谜语：如果一棵树倒在无人居住的森林里，它会发出声音吗？如果我们忽略这个问题的人类中心性，那么回答似乎是合理的，“不”，许多 19 世纪的科学家也是如此。他们说，“声音”不仅仅是空气的振动，而是大气振动引起耳朵神经反应的结果。 （当然，可以想象一个根本没有任何生命的森林，而不仅仅是人类生命，所以哲学家可以在这种防御中寻求庇护。）这基本上就是这种计算活性模型的最终结果：如果计算是可观察的，则它可以被 某人 观察到。 [注1]
现在，这仍然有待解释，因为 某人 可能会，例如，通过测量计算所花费的时间量来“观察”计算。从这个意义上说，所有优化都应该是可观察的，因为如果不缩短计算时间，它们就毫无意义。
如果我们将其视为可观察行为的一部分，那么就不可能进行有用的优化。所以在大多数情况下，这并不是一个特别有用的可观察性定义。但是在极少数用例中，保留计算使用的时间量是必要的。典型的此类案例是对抗安全攻击，该攻击通过对值的各种不同用途进行计时来推断应该是秘密变量的值。如果您正在编写旨在维护高度机密的代码——例如，访问银行帐户所需的密码密钥——那么您可能希望在一些控制流中包含循环，这些循环没有任何计算目的，而是旨在与使用相同秘密值的不同控制流花费的时间完全相同。
举一个更有趣的例子，当我还年轻的时候，计算机使用更多的电力来做更慢的计算，我们注意到你可以通过调谐收音机来“收听”程序的执行CPU 产生的电磁振动。然后你可以编写不同类型的无意义循环来制作不同的音符或节奏人工制品。这种相同类型的无意义循环可用于微控制器以产生闪烁显示，甚至直接驱动音频扬声器。所以在某些情况下，您肯定希望编译器不删除“无用”代码。
尽管如此，为了实现可预测的执行时间而拒绝所有优化技术可能不是一个好主意。大多数时候，我们真的希望我们的程序尽可能快地运行，或者消耗最少的不可再生能源；换句话说，避免做不必要的工作。但是由于在某些用例中优化会影响通常被认为不可观察的行为，因此编译器需要为程序员提供一种机制来关闭特定代码段的优化。这些不是 Aho&c 正在讨论的案例，并且有充分的理由。
备注：
乔治·伯克利，1710 年写道：
… it seems no less evident that the various Sensations or Ideas imprinted on the Sense, however blended or combined together (that is, whatever Objects they compose) cannot exist otherwise than in a Mind perceiving them…
当时的一些哲学家提出了无所不知的上帝存在的必要性，以避免伯克利引发的混乱，即当他闭上眼睛时，他的写作工作室中的物体突然不复存在，并且当他再次打开它们时，眨眼间就重新创建了。在这个论证中，不断看到一切的上帝保证了伯克利主教工作室中物体存在的连续性。对于神灵来说，这一直是一种特别卑微的目的，这让我印象深刻。 （当然，她可以将这种平凡的任务委派给下属。）但每个人都是自己的。
更多参考和小讨论，可以开始here on Wikipedia. Or just listen to Bruce Cockburn's beautiful environmental anthem.
我正在研究红龙书上的归纳变量消除的话题，在那里我遇到了下面的例子。
Consider the control flow graph below :
Fig. 1 : Original Control Flow Graph
Now the authors apply strength reduction to the above graph to obtain the graph below:
Fig 2: Control flow graph after applying strength reduction
Example 10.4. After reduction in strength is applied to the inner loops around
B2andB3, the only use ofiandjis to determine the outcome of the test in blockB4. We know that the values ofiandt2satisfy the relationshipt2 = 4*i, while those ofjandt4satisfy the relationshipt4 = 4* j, so the testt2>=t4is equivalent toi> = j. Once this replacement is made,iin blockB2andjin blockB3become dead variables and the assignments to them in these blocks become dead code that can be eliminated, resulting in the flow graph shown in Fig. 3 below. □
Fig 3: Flow graph after induction variable elimination
我没有得到的是“块B2中的i和块B3中的j成为死变量”的说法。但是，如果我们沿着图 2 中的绿色路径考虑下图：
变量 i 和 j 可能分别存在于块 B2 和 B3 中，如果我们沿着如图所示的绿色路径前进并计数在赋值的右侧使用 i 和 j（在各自的块中）。该特定用途是
变量不再有效，因为它们没有可观察到的效果。
它们会递增和递减，但绝不会出于任何目的查阅这些值。它们没有打印出来。没有控制流依赖于它们。没有其他变量是使用它们的值计算的。如果它们不递增和递减，没有人会注意到。
消除它们不会以任何方式影响程序输出。所以他们应该被淘汰。
作为活跃度的更正式的定义，我们可以从以下开始：
如果变量的值变得可观察（通过在程序执行之外可见，见下文），则变量是活动的（在程序中的某个点）。
如果变量的当前值用于计算活动值，则该变量也是活动的。
该递归定义排除了仅用于计算其自身或其他非活动变量的值的未使用变量的使用。这只是我在答案的第一部分所说内容的一种更准确的表达方式：如果消除赋值不会对程序的执行产生明显的影响，那么赋值是无关紧要的。
“可观察效果”的准确定义会因计算模型而异，但它基本上意味着该值以某种方式传达给程序执行之外的世界。例如，如果在控制台上打印或写入文件（包括用作要创建的文件的名称，因为文件目录也是文件），则该值是实时的。如果它存储在数据库中，或者导致指示灯闪烁，则它是实时的。 C 标准包括在可观察行为读写 volatile memory 的类别中，这是一种封装 CPUs 的方式，它使用特定内存地址的加载和存储作为一种方式从外围设备发送和接收数据。
有一个古老的哲学谜语：如果一棵树倒在无人居住的森林里，它会发出声音吗？如果我们忽略这个问题的人类中心性，那么回答似乎是合理的，“不”，许多 19 世纪的科学家也是如此。他们说，“声音”不仅仅是空气的振动，而是大气振动引起耳朵神经反应的结果。 （当然，可以想象一个根本没有任何生命的森林，而不仅仅是人类生命，所以哲学家可以在这种防御中寻求庇护。）这基本上就是这种计算活性模型的最终结果：如果计算是可观察的，则它可以被 某人 观察到。 [注1]
现在，这仍然有待解释，因为 某人 可能会，例如，通过测量计算所花费的时间量来“观察”计算。从这个意义上说，所有优化都应该是可观察的，因为如果不缩短计算时间，它们就毫无意义。
如果我们将其视为可观察行为的一部分，那么就不可能进行有用的优化。所以在大多数情况下，这并不是一个特别有用的可观察性定义。但是在极少数用例中，保留计算使用的时间量是必要的。典型的此类案例是对抗安全攻击，该攻击通过对值的各种不同用途进行计时来推断应该是秘密变量的值。如果您正在编写旨在维护高度机密的代码——例如，访问银行帐户所需的密码密钥——那么您可能希望在一些控制流中包含循环，这些循环没有任何计算目的，而是旨在与使用相同秘密值的不同控制流花费的时间完全相同。
举一个更有趣的例子，当我还年轻的时候，计算机使用更多的电力来做更慢的计算，我们注意到你可以通过调谐收音机来“收听”程序的执行CPU 产生的电磁振动。然后你可以编写不同类型的无意义循环来制作不同的音符或节奏人工制品。这种相同类型的无意义循环可用于微控制器以产生闪烁显示，甚至直接驱动音频扬声器。所以在某些情况下，您肯定希望编译器不删除“无用”代码。
尽管如此，为了实现可预测的执行时间而拒绝所有优化技术可能不是一个好主意。大多数时候，我们真的希望我们的程序尽可能快地运行，或者消耗最少的不可再生能源；换句话说，避免做不必要的工作。但是由于在某些用例中优化会影响通常被认为不可观察的行为，因此编译器需要为程序员提供一种机制来关闭特定代码段的优化。这些不是 Aho&c 正在讨论的案例，并且有充分的理由。
备注：
乔治·伯克利，1710 年写道：
… it seems no less evident that the various Sensations or Ideas imprinted on the Sense, however blended or combined together (that is, whatever Objects they compose) cannot exist otherwise than in a Mind perceiving them…
当时的一些哲学家提出了无所不知的上帝存在的必要性，以避免伯克利引发的混乱，即当他闭上眼睛时，他的写作工作室中的物体突然不复存在，并且当他再次打开它们时，眨眼间就重新创建了。在这个论证中，不断看到一切的上帝保证了伯克利主教工作室中物体存在的连续性。对于神灵来说，这一直是一种特别卑微的目的，这让我印象深刻。 （当然，她可以将这种平凡的任务委派给下属。）但每个人都是自己的。
更多参考和小讨论，可以开始here on Wikipedia. Or just listen to Bruce Cockburn's beautiful environmental anthem.