Bug 70256 – Live range splitting bug

• Status: NEW
• Component: JavaScriptCore

[Oliver Hunt]

There's a live range splitting issue with this nested loop:
function f(a) {
    for (var i = 0; i < 100; i++)
        for (var j = 0; j < a.length; j++)
            a[j] =j;
}
f([1,2,3,4,5,6,7,8,9,10])

We end up predicting j as Int32|Other rather than Int32

[Filip Pizlo]

Doesn't happen in ToT.  I get the following code:


Dynamic [@24, bc#19] prediction: Int
Argument [0] prediction: Other
Argument [1] prediction: Array
Preserved vars: 11-------------------------------------------------------------
Num callee registers: 5
Graph after propagation:
Block #0 (bc#0):  
  vars: (Top, TOP) (Array, TOP) : (None, []) (None, []) (None, [])
   0:  skipped  < 0:->	SetArgument(arg0(A))
   1:           < 1:->	SetArgument(arg1(K))  predicting Array
   2:  skipped  < 0:->	JSConstant($2 = Undefined)
   3:  skipped  < 0:->	SetLocal(@2, r0(C))
   4:  skipped  < 0:->	SetLocal(@2, r1(D))
   5:           < 1:2>	JSConstant($0 = Int32: 0)
   6:           < 1:->	SetLocal(@5, r0(N))  predicting Int
   7:           <!0:->	Jump(T:#6)
Block #1 (bc#6):   (OSR target)
  vars: (None, []) (Array, TOP) : (Int, []) (None, []) (None, [])
   8:           < 1:2>	JSConstant($0 = Int32: 0)
   9:           < 1:->	SetLocal(@8, r1(I))  predicting Int
  10:           <!0:->	Jump(T:#4)
Block #2 (bc#12):   (OSR target)
  vars: (None, []) (Array, TOP) : (Int, []) (Int, []) (None, [])
  11:           < 2:->	Phi(@24, arg1(K))  predicting Array
  12:           < 1:2>	GetLocal(@11, arg1(K))  predicting Array
  13:           < 2:->	Phi(@28, r1(I))  predicting Int
  14:           < 2:3>	GetLocal(@13, r1(I))  predicting Int
  15:           <!0:->	PutByVal(@12, @14, @14)
  16:           <!0:->	Jump(T:#3)
Block #3 (bc#17):  
  vars: (None, []) (Array, TOP) : (Int, []) (Int, []) (None, [])
  17:           < 1:->	Phi(@13, r1(I))  predicting Int
  18:           < 1:3>	GetLocal(@17, r1(I))  predicting Int
  19:           <!1:3>	ValueToNumber(@18, UsedAsNum|NeedsNegZero)
  20:           < 1:2>	JSConstant($3 = Int32: 1)
  21:           < 1:2>	ArithAdd(@19, @20, UsedAsNum|NeedsNegZero)
  22:           < 1:->	SetLocal(@21, r1(I))  predicting Int
  23:           <!0:->	Jump(T:#4)
Block #4 (bc#19):  
  vars: (None, []) (Array, TOP) : (Int, []) (Int, []) (None, [])
  24:           < 3:->	Phi(@50, @51, arg1(K))  predicting Array
  25:           < 1:2>	GetLocal(@24, arg1(K))  predicting Array
  26:           < 2:2>	GetArrayLength(@25)
  27:  skipped  < 0:->	SetLocal(@26, r2(L))
  28:           < 2:->	Phi(@9, @22, r1(I))  predicting Int
  29:           < 1:3>	GetLocal(@28, r1(I))  predicting Int
  30:           <!1:3>	CompareLess(@29, @26)
  31:           <!0:->	Branch(@30, T:#2, F:#5)
Block #5 (bc#31):  
  vars: (None, []) (Array, TOP) : (Int, []) (None, []) (None, [])
  32:           < 1:->	Phi(@46, r0(N))  predicting Int
  33:           < 1:3>	GetLocal(@32, r0(N))  predicting Int
  34:           <!1:3>	ValueToNumber(@33, UsedAsNum|NeedsNegZero)
  35:           < 1:4>	JSConstant($3 = Int32: 1)
  36:           < 1:4>	ArithAdd(@34, @35, UsedAsNum|NeedsNegZero)
  37:           < 1:->	SetLocal(@36, r0(N))  predicting Int
  38:           <!0:->	Jump(T:#6)
Block #6 (bc#33):  
  vars: (None, []) (Array, TOP) : (Int, []) (None, []) (None, [])
  39:           < 2:->	Phi(@6, @37, r0(N))  predicting Int
  40:           < 1:4>	GetLocal(@39, r0(N))  predicting Int
  41:           < 1:3>	JSConstant($1 = Int32: 100)
  42:           <!1:3>	CompareLess(@40, @41)
  43:           <!0:->	Branch(@42, T:#1, F:#7)
Block #7 (bc#37):  
  vars: (None, []) (None, []) : (None, []) (None, []) (None, [])
  44:           < 1:3>	JSConstant($2 = Undefined)
  45:           <!0:->	Return(@44)
Phi Nodes:
  46:           < 2:->	Phi(@47, @48, r0(N))  predicting Int
  47:           < 1:->	Phi(@39, r0(N))  predicting Int
  48:           < 1:->	Phi(@49, r0(N))  predicting Int
  49:           < 1:->	Phi(@46, r0(N))  predicting Int
  50:           < 1:->	Phi(@52, arg1(K))  predicting Array
  51:           < 1:->	Phi(@11, arg1(K))  predicting Array
  52:           < 1:->	Phi(@1, @53, arg1(K))  predicting Array
  53:           < 1:->	Phi(@24, arg1(K))  predicting Array
SpeculativeJIT skipping Node @0 (bc#0) at JIT offset 0x58     
SpeculativeJIT generating Node @1 (bc#0) at JIT offset 0x58       
SpeculativeJIT skipping Node @2 (bc#0) at JIT offset 0x58     
SpeculativeJIT skipping Node @3 (bc#0) at JIT offset 0x58     
SpeculativeJIT skipping Node @4 (bc#0) at JIT offset 0x58     
SpeculativeJIT generating Node @5 (bc#1) at JIT offset 0x58   -> None, vr#2    
SpeculativeJIT generating Node @6 (bc#1) at JIT offset 0x58   SpecInt@5       
SpeculativeJIT generating Node @7 (bc#4) at JIT offset 0x5e       
SpeculativeJIT generating Node @8 (bc#7) at JIT offset 0x63   -> None, vr#2    
SpeculativeJIT generating Node @9 (bc#7) at JIT offset 0x63   SpecInt@8       
SpeculativeJIT generating Node @10 (bc#10) at JIT offset 0x69       
SpeculativeJIT skipping Node @11 (bc#13) at JIT offset 0x6e     
SpeculativeJIT generating Node @12 (bc#13) at JIT offset 0x6e   -> JSCell, vr#2, rbx    
SpeculativeJIT skipping Node @13 (bc#13) at JIT offset 0x72     
SpeculativeJIT generating Node @14 (bc#13) at JIT offset 0x72   -> Integer, vr#3, rdi    
SpeculativeJIT generating Node @15 (bc#13) at JIT offset 0x76   SpecCell@12   SpecInt@14       
SpeculativeJIT generating Node @16 (bc#17) at JIT offset 0xe5       
SpeculativeJIT skipping Node @17 (bc#17) at JIT offset 0xe5     
SpeculativeJIT generating Node @18 (bc#17) at JIT offset 0xe5   -> Integer, vr#3, r9    
SpeculativeJIT generating Node @19 (bc#17) at JIT offset 0xe9   SpecInt@18   -> Integer, vr#3, r9    
SpeculativeJIT generating Node @20 (bc#17) at JIT offset 0xfd   -> None, vr#2    
SpeculativeJIT generating Node @21 (bc#17) at JIT offset 0xfd   SpecInt@19   -> Integer, vr#2, r10    
SpeculativeJIT generating Node @22 (bc#17) at JIT offset 0x11e   SpecInt@21       
SpeculativeJIT generating Node @23 (bc#19) at JIT offset 0x122       
SpeculativeJIT skipping Node @24 (bc#19) at JIT offset 0x122     
SpeculativeJIT generating Node @25 (bc#19) at JIT offset 0x122   -> JSCell, vr#2, rax    
SpeculativeJIT generating Node @26 (bc#19) at JIT offset 0x126   SpecCell@25   -> Integer, vr#2, rdx    
SpeculativeJIT skipping Node @27 (bc#19) at JIT offset 0x149     
SpeculativeJIT skipping Node @28 (bc#27) at JIT offset 0x149     
SpeculativeJIT generating Node @29 (bc#27) at JIT offset 0x149   -> Integer, vr#3, rcx    
SpeculativeJIT generating Node @30 (bc#27) at JIT offset 0x14d   SpecInt@29   SpecInt@26   -> Integer, vr#3, rcx    
SpeculativeJIT skipping Node @32 (bc#31) at JIT offset 0x155     
SpeculativeJIT generating Node @33 (bc#31) at JIT offset 0x155   -> Integer, vr#3, rbx    
SpeculativeJIT generating Node @34 (bc#31) at JIT offset 0x159   SpecInt@33   -> Integer, vr#3, rbx    
SpeculativeJIT generating Node @35 (bc#31) at JIT offset 0x16d   -> None, vr#4    
SpeculativeJIT generating Node @36 (bc#31) at JIT offset 0x16d   SpecInt@34   -> Integer, vr#4, rdi    
SpeculativeJIT generating Node @37 (bc#31) at JIT offset 0x18d   SpecInt@36       
SpeculativeJIT generating Node @38 (bc#33) at JIT offset 0x191       
SpeculativeJIT skipping Node @39 (bc#33) at JIT offset 0x191     
SpeculativeJIT generating Node @40 (bc#33) at JIT offset 0x191   -> Integer, vr#4, rsi    
SpeculativeJIT generating Node @41 (bc#33) at JIT offset 0x195   -> None, vr#3    
SpeculativeJIT generating Node @42 (bc#33) at JIT offset 0x195   SpecInt@40   -> None, vr#3    
SpeculativeJIT generating Node @44 (bc#37) at JIT offset 0x19e   -> None, vr#3    
SpeculativeJIT generating Node @45 (bc#37) at JIT offset 0x19e       
OSR exit for Node @0 (bc#0) at JIT offset 0x1b5  -- : ---   -> 0x38076c4014bf
OSR exit for Node @0 (bc#0) at JIT offset 0x231  -- : ---   -> 0x38076c4014bf
OSR exit for Node @21 (bc#17) at JIT offset 0x2ad  -(cell) : (int32)(int32)-  UnboxedInt32  -> 0x38076c4015ec
OSR exit for Node @26 (bc#19) at JIT offset 0x339  -(cell) : (int32)(int32)-  UnboxedInt32  -> 0x38076c401609
OSR exit for Node @36 (bc#31) at JIT offset 0x3c5  -(cell) : (int32)--  UnboxedInt32  -> 0x38076c40169d
JIT code for 0x7ff0ac80a800 start at [0x38076c401a20, 0x38076c401ec5). Size = 1189.

[Oliver Hunt]

It turns out we need to return j to trigger this issue.

function f(a) {
    for (var i = 0; i < 100; i++)
        for (var j = 0; j < a.length; j++)
            a[j] =j;

    return j;
}
f([1,2,3,4,5,6,7,8,9,10])

[Filip Pizlo]

Aha!  So it's not live range splitting's fault, per se.  Live range splitting is doing the right thing: indeed the j = undefined coexists with j = 0.

From the standpoint of the propagator, if we ignore local variables, an addition of undefined (i.e. PredictOther) and 1 (i.e. PredctInt32) should not speculate integer, since the following code:

var j;
j++;
j;

produces NaN, which is not an integer.

The problem is that the propagator is not flow-sensitive with respect to variables, so it fails to see that in all of the places where we do j++, j must be an integer.  So the solution is two-fold:

1) Make the propagator flow-sensitive with respect to variables.

2) After we do this, GetLocal(j)/SetLocal(j) will still think that j is Int|Other since the variable j does indeed have stores of both Other and Int32.  So SpeculateIntegerOperand will have to fall back on the CFA's proof that at the point where we do Add(GetLocal(j), JSConstant(1)), GetLocal(j) must be an integer even though j is not strictly an integer variable.

Yucky.  I'll do this after the horror of inlining is complete.