Python CFG Basic blocks
Hi, I am looking into how the python compiler generates basic blocks during the CFG generation process and my expectations from CFG theory seems to be at odds with how the python compiler actually generates its CFG. Take the following code snippet for example: def median(pool): copy = sorted(pool) size = len(copy) if size % 2 == 1: return copy[(size - 1) / 2] else: return (copy[size/2 - 1] + copy[size/2]) / 2 From my understanding of basic blocks in compilers, the above code snippet should have at least 3 basic blocks as follows: 1. Block 1 - all instructions up to and including those for the if test. 2. Block 2 - all instructions for the if body i.e the first return statement. 3. Block 3 - instructions for the else block i.e. the second return statement. My understanding of the the section on Control flow Graphs in the “Design of the CPython Compiler” also alludes to this -
As an example, consider an ‘if’ statement with an ‘else’ block. The guard on the ‘if’ is a basic block which is pointed to by the basic block containing the code leading to the ‘if’ statement. The ‘if’ statement block contains jumps (which are exit points) to the true body of the ‘if’ and the ‘else’ body (which may be NULL), each of which are their own basic blocks. Both of those blocks in turn point to the basic block representing the code following the entire ‘if’ statement.
The CPython compiler however seems to generate 2 basic blocks for the above snippets - 1. Block 1 - all instructions up to and including the if statement and the body of the if statement (the first return statement in this case) 2. Block 2 - instructions for the else block (the second return statement) Is there any reason for this or have I somehow missed something in the CFG generation process? Regards, Obi
On Mon, 11 Jul 2016 at 14:02 Obiesie ike-nwosu via Python-Dev < python-dev@python.org> wrote:
Hi,
I am looking into how the python compiler generates basic blocks during the CFG generation process and my expectations from CFG theory seems to be at odds with how the python compiler actually generates its CFG. Take the following code snippet for example:
def median(pool): copy = sorted(pool) size = len(copy) if size % 2 == 1: return copy[(size - 1) / 2] else: return (copy[size/2 - 1] + copy[size/2]) / 2
From my understanding of basic blocks in compilers, the above code snippet should have at least 3 basic blocks as follows: 1. Block 1 - all instructions up to and including those for the if test. 2. Block 2 - all instructions for the if body i.e the first return statement. 3. Block 3 - instructions for the else block i.e. the second return statement.
My understanding of the the section on Control flow Graphs in the “Design of the CPython Compiler” also alludes to this -
As an example, consider an ‘if’ statement with an ‘else’ block. The guard on the ‘if’ is a basic block which is pointed to by the basic block containing the code leading to the ‘if’ statement. The ‘if’ statement block contains jumps (which are exit points) to the true body of the ‘if’ and the ‘else’ body (which may be NULL), each of which are their own basic blocks. Both of those blocks in turn point to the basic block representing the code following the entire ‘if’ statement.
The CPython compiler however seems to generate 2 basic blocks for the above snippets - 1. Block 1 - all instructions up to and including the if statement and the body of the if statement (the first return statement in this case) 2. Block 2 - instructions for the else block (the second return statement)
Is there any reason for this or have I somehow missed something in the CFG generation process?
I have not looked at the code or the CFGs that are generated from your example code, but my guess is it's two blocks instead of three is because two block is all that's necessary to generate jump targets (since there's only one jump in that function). Since Python doesn't have block-level scope there's no need to generate a separate block in the `if` statement. And since the `if` statement will have a jump to the `else` block and otherwise fall through then there's only a need to have the block that starts the function and then the second block that the `if` jump goes to and that's it.
participants (2)
-
Brett Cannon -
Obiesie ike-nwosu