Loop unswitching

# Original
# int i, w, x[1000], y[1000];
#  for (i = 0; i < 1000; i++) {
#    x[i] = x[i] + y[i];
#    if (w)
#      y[i] = 0;
#  }
#
#----------------------------------
# Loop unswitching
#
#  int i, w, x[1000], y[1000];
#  if (w) {
#    for (i = 0; i < 1000; i++) {
#      x[i] = x[i] + y[i];
#      y[i] = 0;
#    }
#  } else {
#    for (i = 0; i < 1000; i++) {
#      x[i] = x[i] + y[i];
#    }
#  }

1.可確保在for loop 中的 lp_body 是 clean 的,
  表示在 lp_body 中,只有 DFG 的 (BasicBlock)BB, 可避免不必要的條件中斷(Branch).

2.可透過 struct 的分析,把 for loop 當成個 node, 可以簡化成 sample BB with CFG control.
之後利用 BDD (Binary decision diagram) 的方式做出每個 Output condition 的機率,
有利於 compiler 做 branch jump 的 predict

x1,x2,x3,Y
---------
[0,0,0] = 0
[0,0,1] = 0 
[0,1,0] = 1
[0,1,1] = 1
[1,0,0] = 1
[1,0,1] = 1
[1,1,0] = 1
[1,1,1] = 0

@ y = 0 prb(3/8)
@ y = 1 prb(5/8) <= predict better

3. key notes
判斷 condition branch 是否 stable, 會不會在 for loop 內改變狀態, 如果是 stable 才做 Loop unswitching