前言
IR技术应用在各个编程语言当中，它属于JIT的核心部分，确实有点点麻烦。但部分基本明了。本篇通过.Net8里面的边界检查的小例子了解下。前情提要，看这一篇之前建议看看前一篇：点击此处，以便于理解。
概括
1.前奏
先上C#代码：
[MethodImpl(MethodImplOptions.NoInlining)] private static bool Test(int[] array) { for (int i = 0; i < 0x12345; i++) { if (array[i] == 42) { return true; } } return false; } Test函数经过Roslyn编译成IL代码之后，会被JIT导入及操作变成IR。
BBnum BBid ref try hnd preds weight lp [IL range] [jump] [EH region] [flags] ----------------------------------------------------------------------------------------------------------------------------------------- BB01 [0007] 1 1 [???..???)-> BB04 ( cond ) internal BB02 [0001] 2 BB01,BB03 4 0 [004..00B)-> BB05 ( cond ) i Loop idxlen bwd bwd-target align BB03 [0003] 1 BB02 4 0 [00D..019)-> BB02 ( cond ) i bwd BB04 [0005] 2 BB01,BB03 0.50 [019..01B) (return) i BB05 [0002] 1 BB02 0.50 [00B..00D) (return) i ----------------------------------------------------------------------------------------------------------------------------------------- 可以看到IL被分割成了五个BB(basic block).注意表格的BBnum和jump列。BB01的BBnum就是BB01,它的jump是BB04。为啥是BB04?因为BB01的IR表示的是如果(i>=0x12345),则跳转到BB04，也就是BB01的正常逻辑。下面看下这个五个BB.
------------ BB01 [???..???) -> BB04 (cond), preds={} succs={BB02,BB04} ***** BB01 STMT00006 ( 0x011[E-] ... ??? ) ( 7, 9) [000038] ----------- * JTRUE void ( 5, 7) [000039] J------N--- --* GE int ( 3, 2) [000040] ----------- +--* LCL_VAR int V01 loc0 ( 1, 4) [000041] ----------- --* CNS_INT int 0x12345 ------------ BB02 [004..00B) -> BB05 (cond), preds={BB01,BB03} succs={BB03,BB05} ***** BB02 STMT00002 ( 0x004[E-] ... 0x009 ) [000013] ---XG+----- * JTRUE void [000012] N--XG+-N-U- --* EQ int [000034] ---XG+----- +--* COMMA int [000026] ---X-+----- | +--* BOUNDS_CHECK_Rng void [000008] -----+----- | | +--* LCL_VAR int V01 loc0 [000025] ---X-+----- | | --* ARR_LENGTH int [000007] -----+----- | | --* LCL_VAR ref V00 arg0 [000035] n---G+----- | --* IND int [000033] -----+----- | --* ARR_ADDR byref int[] [000032] -----+----- | --* ADD byref [000023] -----+----- | +--* LCL_VAR ref V00 arg0 [000031] -----+----- | --* ADD long [000029] -----+----- | +--* LSH long [000027] -----+---U- | | +--* CAST long <- uint [000024] -----+----- | | | --* LCL_VAR int V01 loc0 [000028] -----+-N--- | | --* CNS_INT long 2 [000030] -----+----- | --* CNS_INT long 16 [000011] -----+----- --* CNS_INT int 42 ------------ BB03 [00D..019) -> BB02 (cond), preds={BB02} succs={BB04,BB02} ***** BB03 STMT00003 ( 0x00D[E-] ... 0x010 ) [000018] -A---+----- * ASG int [000017] D----+-N--- +--* LCL_VAR int V01 loc0 [000016] -----+----- --* ADD int [000014] -----+----- +--* LCL_VAR int V01 loc0 [000015] -----+----- --* CNS_INT int 1 ***** BB03 STMT00001 ( 0x011[E-] ... 0x017 ) ( 7, 9) [000006] ----------- * JTRUE void ( 5, 7) [000005] J------N--- --* LT int ( 3, 2) [000003] ----------- +--* LCL_VAR int V01 loc0 ( 1, 4) [000004] ----------- --* CNS_INT int 0x12345 ------------ BB04 [019..01B) (return), preds={BB01,BB03} succs={} ***** BB04 STMT00005 ( 0x019[E-] ... 0x01A ) [000022] -----+----- * RETURN int [000037] -----+----- --* CNS_INT int 0 ------------ BB05 [00B..00D) (return), preds={BB02} succs={} ***** BB05 STMT00004 ( 0x00B[E-] ... 0x00C ) [000020] -----+----- * RETURN int [000036] -----+----- --* CNS_INT int 1 preds表示能在逻辑上执行到当前块的所有快，succs表示当前语句逻辑能达到的BB块。举个例子：比如BB01，首先看下这条IR表示的如果(i>=0x12345)，则跳转到BB04,也就是直接返回0。因为逻辑是索引大于了循环的最大次数，是不合理的。如果(i<0x12345),则跳转到BB02,也就是判断(array[i]是否等于42)。上面BB01的predes为空，则表示没有逻辑能达到这条语句。它的succs为BB02和BB04，跟上面的推测吻合。其它依次类推。
2.BB的IR表示
通过上面的BB01到BB05的观察，得知它们分别表示如下：
一：BB01
if(i>=0x12345) 二：BB02
if(array[i]==42) 三：BB03
i=i+1; if(i<0x12345) 四：BB04
return 0 五：BB05
return 1 以上循环被分割成了五个BB。它的实际逻辑如下：
if(i>=0x12345) { return flase; } else { for(i<0x12345;i++) { if(array[i]==42) { return true; } } return flase; } 所以呢，实际是示例的for循环，被分解成了上面的代码。但是还没完，为了确保这个array[i]不会出现内存访问的错误，BB02里面有个BOUNDS_CHECK_Rng的边界检查技术，它会判断array[i]里的i索引是否查过array.length的长度，因为在for循环里面，所以每次都会判断，会增加相应的开销。为了达到最优的效果，.Net8会去掉这开销。那么应该怎么做呢？继续看。
JIT先增加BB06,BB07,BB08,BB09四个块，然后把BOUNDS_CHECK_Rng给去掉。
去掉前后对比如下。
去掉前：
[000013] ---XG+----- * JTRUE void [000012] N--XG+-N-U- --* EQ int [000034] ---XG+----- +--* COMMA int [000026] ---X-+----- | +--* BOUNDS_CHECK_Rng void [000008] -----+----- | | +--* LCL_VAR int V01 loc0 [000025] ---X-+----- | | --* ARR_LENGTH int [000007] -----+----- | | --* LCL_VAR ref V00 arg0 [000035] n---G+----- | --* IND int [000033] -----+----- | --* ARR_ADDR byref int[] [000032] -----+----- | --* ADD byref [000023] -----+----- | +--* LCL_VAR ref V00 arg0 [000031] -----+----- | --* ADD long [000029] -----+----- | +--* LSH long [000027] -----+---U- | | +--* CAST long <- uint [000024] -----+----- | | | --* LCL_VAR int V01 loc0 [000028] -----+-N--- | | --* CNS_INT long 2 [000030] -----+----- | --* CNS_INT long 16 [000011] -----+----- --* CNS_INT int 42 去掉后：
[000013] ----G+----- * JTRUE void [000012] N---G+-N-U- --* EQ int [000034] ----G+-N--- +--* COMMA int [000026] -----+----- | +--* NOP void [000035] n---G+----- | --* IND int [000033] -----+----- | --* ARR_ADDR byref int[] [000032] -----+----- | --* ADD byref [000023] -----+----- | +--* LCL_VAR ref V00 arg0 [000031] -----+----- | --* ADD long [000029] -----+----- | +--* LSH long [000027] -----+---U- | | +--* CAST long <- uint [000024] -----+----- | | | --* LCL_VAR int V01 loc0 [000028] -----+-N--- | | --* CNS_INT long 2 [000030] -----+----- | --* CNS_INT long 16 [000011] -----+----- --* CNS_INT int 42 然后再新增BB10,BB11,BB12,BB13四个BB块。这些BB块如下所示：
------------ BB01 [???..???) -> BB12 (cond), preds={} succs={BB02,BB12} ***** BB01 STMT00006 ( 0x011[E-] ... ??? ) ( 7, 9) [000038] ----------- * JTRUE void ( 5, 7) [000039] J------N--- --* GE int ( 3, 2) [000040] ----------- +--* LCL_VAR int V01 loc0 ( 1, 4) [000041] ----------- --* CNS_INT int 0x12345 ------------ BB02 [???..???), preds={BB01} succs={BB03} ------------ BB03 [???..???) -> BB09 (cond), preds={BB02} succs={BB04,BB09} ***** BB03 STMT00010 ( ??? ... ??? ) ( 7, 6) [000072] ----------- * JTRUE void ( 5, 4) [000071] J------N--- --* EQ int ( 3, 2) [000069] ----------- +--* LCL_VAR ref V00 arg0 ( 1, 1) [000070] ----------- --* CNS_INT ref null ------------ BB04 [???..???) -> BB09 (cond), preds={BB03} succs={BB05,BB09} ***** BB04 STMT00011 ( ??? ... ??? ) ( 7, 6) [000076] ----------- * JTRUE void ( 5, 4) [000075] J------N--- --* LT int ( 3, 2) [000073] ----------- +--* LCL_VAR int V01 loc0 ( 1, 1) [000074] ----------- --* CNS_INT int 0 ------------ BB05 [???..???) -> BB09 (cond), preds={BB04} succs={BB06,BB09} ***** BB05 STMT00012 ( ??? ... ??? ) ( 9, 11) [000081] ---X------- * JTRUE void ( 7, 9) [000080] J--X---N--- --* LT int ( 5, 4) [000079] ---X------- +--* ARR_LENGTH int ( 3, 2) [000078] ----------- | --* LCL_VAR ref V00 arg0 ( 1, 4) [000077] ----------- --* CNS_INT int 0x12345 ------------ BB06 [004..00B) -> BB13 (cond), preds={BB05,BB07} succs={BB07,BB13} ***** BB06 STMT00002 ( 0x004[E-] ... 0x009 ) [000013] ----G+----- * JTRUE void [000012] N---G+-N-U- --* EQ int [000034] ----G+-N--- +--* COMMA int [000026] -----+----- | +--* NOP void [000035] n---G+----- | --* IND int [000033] -----+----- | --* ARR_ADDR byref int[] [000032] -----+----- | --* ADD byref [000023] -----+----- | +--* LCL_VAR ref V00 arg0 [000031] -----+----- | --* ADD long [000029] -----+----- | +--* LSH long [000027] -----+---U- | | +--* CAST long <- uint [000024] -----+----- | | | --* LCL_VAR int V01 loc0 [000028] -----+-N--- | | --* CNS_INT long 2 [000030] -----+----- | --* CNS_INT long 16 [000011] -----+----- --* CNS_INT int 42 ------------ BB07 [00D..019) -> BB06 (cond), preds={BB06} succs={BB08,BB06} ***** BB07 STMT00003 ( 0x00D[E-] ... 0x010 ) [000018] -A---+----- * ASG int [000017] D----+-N--- +--* LCL_VAR int V01 loc0 [000016] -----+----- --* ADD int [000014] -----+----- +--* LCL_VAR int V01 loc0 [000015] -----+----- --* CNS_INT int 1 ***** BB07 STMT00001 ( 0x011[E-] ... 0x017 ) ( 7, 9) [000006] ----------- * JTRUE void ( 5, 7) [000005] J------N--- --* LT int ( 3, 2) [000003] ----------- +--* LCL_VAR int V01 loc0 ( 1, 4) [000004] ----------- --* CNS_INT int 0x12345 ------------ BB08 [???..???) -> BB12 (always), preds={BB07} succs={BB12} ------------ BB09 [???..???), preds={BB03,BB04,BB05} succs={BB10} ------------ BB10 [004..00B) -> BB13 (cond), preds={BB09,BB11} succs={BB11,BB13} ***** BB10 STMT00007 ( 0x004[E-] ... ??? ) [000042] ---XGO----- * JTRUE void [000043] N--XGO-N-U- --* EQ int [000044] ---XGO----- +--* COMMA int [000045] ---X-O----- | +--* BOUNDS_CHECK_Rng void [000046] ----------- | | +--* LCL_VAR int V01 loc0 [000047] ---X------- | | --* ARR_LENGTH int [000048] ----------- | | --* LCL_VAR ref V00 arg0 [000049] n---GO----- | --* IND int [000050] -----O----- | --* ARR_ADDR byref int[] [000051] ----------- | --* ADD byref [000052] ----------- | +--* LCL_VAR ref V00 arg0 [000053] ----------- | --* ADD long [000054] ----------- | +--* LSH long [000055] ---------U- | | +--* CAST long <- uint [000056] ----------- | | | --* LCL_VAR int V01 loc0 [000057] -------N--- | | --* CNS_INT long 2 [000058] ----------- | --* CNS_INT long 16 [000059] ----------- --* CNS_INT int 42 ------------ BB11 [00D..019) -> BB10 (cond), preds={BB10} succs={BB12,BB10} ***** BB11 STMT00008 ( 0x00D[E-] ... ??? ) [000060] -A--------- * ASG int [000061] D------N--- +--* LCL_VAR int V01 loc0 [000062] ----------- --* ADD int [000063] ----------- +--* LCL_VAR int V01 loc0 [000064] ----------- --* CNS_INT int 1 ***** BB11 STMT00009 ( 0x011[E-] ... ??? ) ( 7, 9) [000065] ----------- * JTRUE void ( 5, 7) [000066] J------N--- --* LT int ( 3, 2) [000067] ----------- +--* LCL_VAR int V01 loc0 ( 1, 4) [000068] ----------- --* CNS_INT int 0x12345 ------------ BB12 [019..01B) (return), preds={BB01,BB08,BB11} succs={} ***** BB12 STMT00005 ( 0x019[E-] ... 0x01A ) [000022] -----+----- * RETURN int [000037] -----+----- --* CNS_INT int 0 ------------ BB13 [00B..00D) (return), preds={BB06,BB10} succs={} ***** BB13 STMT00004 ( 0x00B[E-] ... 0x00C ) [000020] -----+----- * RETURN int [000036] -----+----- --* CNS_INT int 1 ------------------------------------------------------------------------------------------------------------------- 3.BB块分析
通过去掉的边界检查，进行的优化之后。新增了7个BB块，总共有13个BB块。那么这些BB干嘛的呢？实际上就是为了去掉边界检查（因为在for循环里，每次都要判断），而确保内存array[i]在正确内存范围内。逐一来看下：
BB01:
if(i>=0x12345)判断索引是否大于循环最大值 BB02
无 BB03
if(array==null) //这里是判断数组的地址是否等于0 BB04
if(i<0)判断索引是否小于0 BB05
if(array.length<0x12345)判断数组长度是否小于循环最大数0x12345 BB06
if(array[i]==42) BB07
i=i+1索引自增 BB08
无 BB09
无 BB10
if(i<array.length) //这里跟上面的BB06一样，但是多了边界检查。BB06去掉，这里没去掉。是因为这里需要边界检查，而BB06不需要。一个快速路径，一个慢速路径。 if(array[i]==42) BB11
i=i+1 BB12
return 0 BB02
return 1 它实际逻辑是：
if(i<0x12345 && array!= null && i>0 && array.Length >= 0x12345 )//再去掉边界检查之后的优化里，这进行大量的检查，确保array[i],在正确内存范围内。 { for (int i = 0; i < 0x12345; i++) { if (array[i] == 42) 不检查边界，因为上面的if检查过了 { return true; } } } else //如果上面的if有一个条件不符合，则进行边界检查。优化不成功 { for (int i = 0; i < 0x12345; i++) { if (array[i] == 42) 这里需要边界检查也就是BOUNDS_CHECK_Rng { return true; } } }
结尾
作者:江湖评谈
欢迎关注公众号，第一时间首发分享技术文章。
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/1.jpg&w=218&h=124&zc=1)
