Global Null Pointer Test Elimination

September 20, 1999

We are pleased to announce that Cygnus Solutions has donated a global null pointer test elimination pass to GCC.

If all paths to a null pointer test use the same pointer in a memory load/store, then the pointer must have a non-null value at the test. Otherwise, one of the load/stores leading to the test would have faulted.

The optimizer computes which blocks have loads/stores using a register as the memory address and in which the register is not potentially reset to zero before the end of the block. The optimizer also computes what blocks can potentially set a register to a zero value.

That information is propagated through the function's cfg to provide a global view of what registers are known to have non-null values at the start and end of each basic block.

The optimizer then examines each basic block to determine if it ends with a null pointer test and whether or not the register tested is known to have a non-null value.

It is important to realize the compiler does not care what value is in the register, only whether or not the register is known to have a non-null value.

Here is a trivial example showing the value of this optimization.

foo (char *x)
{
  char ret = *x;

  if (x)
    com();
  else
    bar ();
  return ret;
}

	Before				After
foo:
        pushl   %ebp			pushl   %ebp
        movl    %esp, %ebp		movl    %esp, %ebp
        subl    $20, %esp		subl    $20, %esp
        pushl   %ebx			pushl   %ebx
        movl    8(%ebp), %eax		movl    8(%ebp), %eax
        movb    (%eax), %bl		movsbl  (%eax),%ebx
        testl   %eax, %eax
        je      .L3
        call    com			call    com
        jmp     .L4
        .p2align 4,,7
.L3:
        call    bar
.L4:
        movsbl  %bl,%eax		movl    %ebx, %eax
        popl    %ebx			popl    %ebx
        movl    %ebp, %esp		movl    %ebp, %esp
        popl    %ebp			popl    %ebp
        ret				ret

Note how the compiler eliminated the test instruction and the entire else arm of the if/else conditional.

Programs which rely on dereferencing of a null pointer not halting the program are relying on undefined behavior according to ISO/ANSI standards. For such programs the option -fno-delete-null-pointer-checks will disable this optimization.

Please send FSF & GNU inquiries & questions to gnu@gnu.org. There are also other ways to contact the FSF.

These pages are maintained by the GCC team.

For questions related to the use of GCC, please consult these web pages and the GCC manuals. If that fails, the gcc-help@gcc.gnu.org mailing list might help.
Please send comments on these web pages and the development of GCC to our developer mailing list at gcc@gnu.org or gcc@gcc.gnu.org. All of our lists have public archives.

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.

Last modified 2006-06-21