Since it would probably help to quantify the complexity increase, I've implemented my more recent suggestion (patch attached). This patch allows 'nobuiltin' on a function declaration or definition, and adds a 'builtin' attribute which can only be present on a call site for a direct call to a function declared with the 'nobuiltin' attribute. The 'builtin' attribute has the effect of canceling out the 'nobuiltin' attribute on the declaration.
Ok. Please make "hasFnAttr(Attribute::NoBuiltin)" abort though: it will be a common bug to call this instead of your new accessor.
This (incidentally) also exactly matches what we want for another Clang feature: we want a -fno-builtin-foo which makes 'foo' not be a builtin (but we still want __builtin_foo to have the builtin behavior). This, again, is not possible with the existing 'nobuiltin' attribute, due to the function pointer problem. Instead, Clang currently just provides -fno-builtin, and even *that* only provides a broken half-implementation -- it calls TargetLibraryInfo::disableAllFunctions, whose effect is not preserved across "clang -fno-builtin -emit-llvm | opt", nor across LTO.
There are several problems in this space. While your new attribute may be useful to help in this area, it is definitely not sufficient to solve the problem. -fno-builtin-strlen should disable transformations from strchr->strlen (as a random example) even if there is no LLVM IR function for strlen.