analyzeWork can occasionally get into an infinite loop

[james0x0A]

The reaching set of an address representing a return ( 0xEE) can somehow have itself as a successor. This can result in an infinite loop.

function analyzeWork() {
// ...
var here = fringe.pop();
var prevret = reaching[here]['rets']; // can contain address `here`
// ....
var children = successors(here, prevret); // enlists `prevret` as `children` if  `here` is a return, potentially including `here`

//eventually `child` == `here`
fringe.push(child);
//repeat
}

[JohnEarnest]

Hmm. I'd really like to see a minimal ROM which causes this misbehavior. To get to the heart of this issue we need to see how a return instruction has its own address in its reaching set.

[james0x0A]

Starting from the deep8 sample that exhibits the behavior, I was able to reduce down to this program:

edit: a little more reduction
edit2: last of the cruft

[
 0x12, 0x28, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x22, 0x0E, 0x00,
 0xEE, 0x00, 0xEE, 0x22, 0x0A, 0x00, 0xEE, 0x12, 0x10, 0x22, 0x0E, 0x22, 0x0E,
 0x00, 0xEE, 0xA2, 0x02, 0xF2, 0x65, 0x22, 0x14, 0xA2, 0x02, 0xF2, 0x55, 0x00,
 0xEE, 0x22, 0x0A, 0x22, 0x0E, 0x22, 0x1C
]

: scratch      0 0 0 0 0 0 0 0 

: func-1-0
    func-0
;

: func-0
;

: func-1-1-0
    func-1-0
;


: jmp-func-2
    jump func-1-1-0

    func-0
    func-0
;

: smc
    i := scratch load v2 jmp-func-2 i := scratch save v2
;

: main
    func-1-0
    func-0
    smc

[james0x0A]

I've stepped through the decompile of the above program and identified the point where the return gets its own adress in its reaching set.

: scratch  0 0 0 0 0 0 0 0  #0x200

: func-1-0
    func-0

;   # 524, 525 : 0x00EE : children = 530, 546, 554, 558;  output['rets'] = 530, 546, 554, 558
    # successor(524, prevret) and apply(524) eventually return the same values.
    # apply(524) calls chaseReturns()  which adds reaching[(556)]['rets'] to the output including addr 530
    # reaching[each in children] merge with output;  return at addr 530 gets itself in its reaching set


: func-0
;

: func-1-1-0
    func-1-0

;   # 530, 531 : 0x00EE

: jmp-func-2
    jump func-1-1-0

    func-0
    func-0
;

: smc
    i := scratch 
    load v2 
    jmp-func-2 
    i := scratch    # 546, 547 : 0xA202
    save v2
;

: main
    func-1-0
    func-0      # 554, 555
    smc         # 556, 557
                # 558 : 0x00

[james0x0A]

I was able to reproduce this with no other code except nested calls and returns

[
 0x12, 0x12,
 0x00, 0xEE,
 0x22, 0x02,
 0x00, 0xEE,
 0x22, 0x04,
 0x00, 0xEE,
 0x22, 0x08,
 0x22, 0x02,
 0x00, 0xEE,
 0x22, 0x02,
 0x22, 0x0C
]

: sub-0
;

: sub-1
    sub-0
;

: sub-2
    sub-1
;

: sub-3
    sub-2
    sub-0
;

: main
    sub-0
    sub-3

[james0x0A]

This is about as minimal as can be, but it relies on sharing a return instruction, so it may be a different edge case?

[
 0x22, 0x02,
 0x00, 0xEE
]

: main
    sub-0

: sub-0
;

[james0x0A]

This is pretty close to minimal without sharing instructions.

[
 0x22, 0x06,
 0x22, 0x08,
 0x00, 0xEE,
 0x00, 0xEE,
 0x22, 0x06,
 0x00, 0xEE
]

: main
    sub-0
    sub-1
;

: sub-0
;

: sub-1
    sub-0
;

[JohnEarnest]

Well, the shared example clearly has a return instruction which should have itself in its own successor set due to fallthrough. I'm surprised the analyzer keeps iterating in that case, though, as it shouldn't be inferring any new reaching values.

[james0x0A]

It keeps iterating because the return instruction will always be a child of itself and be pushed back into fringe.

[JohnEarnest]

Yes, I see now. Returns were treated specially, defeating the implicit check of whether we expanded the set of reaching definitions.