Since the perlsub POD mentions the AUTOLOAD subroutine in the same sentence as "BEGIN", "CHECK", "INIT", "END", "CLONE" and "DESTROY", I assume it shares some of the same characteristics as the others, the important one in this case being that the sub keyword is implied. When fed your code, B::Deparse prints the following. Notice how the sub keyword is inserted for the BEGIN subs, as well as the AUTOLOAD sub:

package Foo;
use warnings;
use strict 'refs';
our $AUTOLOAD;
sub main::BEGIN {
    package main;
    no strict 'refs';
    require strict;
    do {
        'strict'->import
    };
}
sub main::BEGIN {
    package main;
    require warnings;
    do {
        'warnings'->import
    };
}
sub new {
    return bless({}, shift @_);
}
sub do_something {
    print 'did something';
}
sub AUTOLOAD {
    print "message from Foo: undefined method ($AUTOLOAD) called";
}
package main;
my $instance = 'Foo'->new;
$instance->do_something;
$instance->do_notimplemented;
[download]