It becomes hard when the app uses reflection. When you want to remove some method foo, you not only have to make sure that it isn't referenced by some code, but also make sure that no code is passing the string "foo" to reflection API. This may be hard for many apps and is undecidable in general.
Actually, even in plain, reflection-less java it may be quite complicated because subclass methods can be invoked by superclass-typed variables. For every method invocation you need to find all possible subclasses whose objects can be assigned to variable on which the method is invoked. You need to know which subclasses are ever passed as superclass/interface arguments to methods. You need to know which subclasses are assigned to superclass/interface member/static variables. You need to know which subclasses are stored in superclass collections. And so on.
The compiler would have to see all code that is linked with the app, including the Android runtime that calls into the app's code in various ways.
In Java land these kinds of fancy optimizations usually happen in the JVM JIT at runtime. Would this help the size of those tables in Android's Dalvik/dexopt setup? In any case you can't ship a custom version of Dalvik with your app.
You've got class foo, with methods "DoBar" which calls "DoBazStep1(), DoBazStep2(), SomeHelper.CalcPosition()".
You use a Java bytecode toolkit and identify leaf functions, small functions, whatever the criteria needs to be. Then you check every callsite for those functions, and if found, remove the call, and inline the code, doing fixup on locals and parameters. Now, "DoBar" has a lot more bytecode in it, as the bodies of DoBazStep1 and the others are now contained in it. The small functions are completely removed.
This process can be done totally offline, on the compiled Java code. The runtime just sees that you wrote one big function, versus a bunch of small ones.
The only real work is making sure you got everything, and perhaps being clever with stack local allocations. As the FB team says they moved to a new style with lots of small functions, I'm assuming they aren't doing all sorts of metaprogramming and inheritance, but have just split things up at the function level.
