1. using structural analysis to recreate the compositional control-flow from jimple-code into a simple "WHILE"-type language
Dava does this. I think it's in the main Soot tree.
I think it shouldn't take 20 minutes to do a whole-program analysis, but I'm not current on that area. Maybe Ondrej will comment on that.
-- Helge