ianyappy:

One thing you have to understand about the statement  sub name { ... } is that it always executes at compile time if it is not in a string eval (i.e., is in a block  eval or is a nested subroutine definition in another subroutine). So your impression that "AUTOLOAD isn't even being called" is correct. See example below.

>perl -wMstrict -le
"{ package Foo;
   use warnings;  use strict;
   our $AUTOLOAD;
   sub AUTOLOAD {
     eval { sub foo { return 'FOO'; } };
     sub bar { return 'BAR'; }
     print qq{AUTOLOADing '$AUTOLOAD'};
     no strict 'refs';
     *$AUTOLOAD = sub { return uc $AUTOLOAD };
     goto &$AUTOLOAD;
     }
   }
 ;;
 print 'foo? ', exists &Foo::foo;  print Foo->foo;
 print 'bar? ', exists &Foo::bar;  print Foo->bar;
 print 'baz? ', exists &Foo::baz;  print Foo->baz;
 print 'baz? ', exists &Foo::baz;  print Foo->baz;
"
foo? 1
FOO
bar? 1
BAR
baz?
AUTOLOADing 'Foo::baz'
FOO::BAZ
baz? 1
FOO::BAZ
[download]

In this example,  Foo::foo and  Foo::bar already exist at runtime, so  AUTOLOAD is never called for them. The first time  Foo::baz is called,  AUTOLOAD is called and defines the subroutine and also executes the just-defined subroutine. When  Foo::baz is called subsequently, it exists.

Update: To pound the point about nested subroutine definitions even further into the ground, remove the  sub bar { return 'BAR'; } statement from the  AUTOLOAD function in the example above and replace the  eval statement with
    eval { sub foo { sub bar { return 'BAR'; }  return 'FOO'; } };
or the even more pathological
    eval { sub foo { return 'FOO';  sub bar { return 'BAR'; } } };
The results of execution are the same.