LGTM

Regarding BC:

The code runs synchronously from where you removed the $element.data(...) line to where you added it back and I don't see anything that (should be) relying on the controller being available on $element.data().

That said, I can come up with 2 (weird) cases that could break an app:

1. Trying to call $element.controller('someOtherDirective') while instantiating a controller. Something like this:

   <weird some-directive-with-controller></weird>

   .directive('weird', function weirdDirective() {
     return {
       controller: function WeirdCtrl($element) {
         // I'm the `WeirdCtrl` - I might do weird stuff !
         // (Who doesn't, right ?)
   
         // 1. Let's get access to `someDirectiveWithController`'s controller
         var otherCtrl = $element.controller('someDirectiveWithController');
   
         // 2. Let's get access to myself (aka `this`)
         var self = $element.controller('weird');
       }
     };
   })

2. Having a = scope binding, bound to a getter in the parent scope, which tries to access the element's .data(). Something like this:

   <div ng-controller="WeirdCtrl">
     <divt test="someProp"></div>
   </div>

   .directive('test', function testDirective() {
     return {
       scope: {test: '='},
       controller: function TestCtrl() {}
     };
   })
   
   .controller('WeirdCtrl', function WeirdCtrl($document, $scope) {
     var _someProp;
     Object.defineProperty($scope, 'someProp', {
       get: function () {
         // Let me do something really weird, before returning the value
         angular.element($document[0].body.querySelector('[test]')).controller('test');
   
         return _someProp;
       },
       set: function (value) {
         _someProp = value;
       }
     });
   })

tl;dr

Apart form some really twisted ways that one could have abused the .controller() or .data() APIs, this shouldn't break anything. I'd be fine without a BC notice 😃

DISCLAIMER:
I haven't really tried that these contrived usecases break with the change proposed in this PR - I just assume they will by looking at the code.
They sure work with the current implementation though :) I have proof.

Do you think this is worth doing then? I'm fine either way. Could also change this to only move the $element/data stuff out of setupControllers, but still do it twice if the controller instance changes. I still think that would be an improvement just because the $element/data would all be in one function instead of spread across two...

I wonder if/how this is affected by recent changes in 3ffdf38, cd21216, 56c3666 (especially the 2nd one).