Doesn't the absence of an empty prototype in the assignment *$AUTOLOAD = sub { $val } mean that these are just normal (non-constant) subs, and will therefore never be inlined, and therefore, called everytime they are used?

Eh, yes. And no. They will indeed by called everytime they are used - just as I said: The second time, the sub is there and the sub is called. (But a subsequent call to the same constant will not invoke AUTOLOAD again). However, it does not matter whether there's a prototype present or not - the calling code is already compiled, so it's too late for inlining. Although it might matter if there's future code to be string-evalled that uses a previous called constant.