diff -r 33ca11b010e2 -r 2673006f7989 mercurial/localrepo.py
--- a/mercurial/localrepo.py	Fri Jan 06 10:04:20 2012 +0100
+++ b/mercurial/localrepo.py	Wed Jan 04 01:12:31 2012 +0100
@@ -1632,21 +1632,60 @@
                     # XXX If push failed we should use strict common and not
                     # future to avoir pushing phase data on unknown changeset.
                     # This is to done later.
-                    futctx = [self[n] for n in fut if n != nullid]
-                    for phase in phases.trackedphases[::-1]:
-                        prevphase = phase -1
-                        # get all candidate for head in previous phase
-                        inprev = [ctx for ctx in futctx
-                                      if ctx.phase() == prevphase]
-                        for newremotehead in  self.set('heads(%ld & (%ln::))',
-                                              inprev, rroots[phase]):
-                            r = remote.pushkey('phases',
-                                               newremotehead.hex(),
-                                               str(phase), str(prevphase))
-                            if not r:
-                                self.ui.warn(_('updating phase of %s'
-                                               'to %s failed!\n')
-                                                % (newremotehead, prevphase))
+
+                    # element we want to push
+                    topush = []
+
+                    # store details of known remote phase of several revision
+                    # /!\ set of index I holds rev where: I <= rev.phase()
+                    # /!\ public phase (index 0) is ignored
+                    remdetails = [set() for i in xrange(len(phases.allphases))]
+                    _revs = set()
+                    for relremphase in phases.trackedphases[::-1]:
+                        # we iterate backward because the list alway grows
+                        # when filled in this direction.
+                        _revs.update(self.revs('%ln::%ln',
+                                               rroots[relremphase], fut))
+                        remdetails[relremphase].update(_revs)
+
+                    for phase in phases.allphases[:-1]:
+                        # We don't need the last phase as we will never want to
+                        # move anything to it while moving phase backward.
+
+                        # Get the list of all revs on remote which are in a
+                        # phase higher than currently processed phase.
+                        relremrev = remdetails[phase + 1]
+
+                        if not relremrev:
+                            # no candidate to remote push anymore
+                            # break before any expensive revset
+                            break
+
+                        #dynamical inject appropriate phase symbol
+                        phasename = phases.phasenames[phase]
+                        odrevset = 'heads(%%ld and %s())' % phasename
+                        outdated =  self.set(odrevset, relremrev)
+                        for od in outdated:
+                            candstart = len(remdetails) - 1
+                            candstop = phase + 1
+                            candidateold = xrange(candstart, candstop, -1)
+                            for oldphase in candidateold:
+                                if od.rev() in remdetails[oldphase]:
+                                    break
+                            else: # last one: no need to search
+                                oldphase = phase + 1
+                            topush.append((oldphase, phase, od))
+
+                    # push every needed data
+                    for oldphase, newphase, newremotehead in topush:
+                        r = remote.pushkey('phases',
+                                           newremotehead.hex(),
+                                           str(oldphase), str(newphase))
+                        if not r:
+                            self.ui.warn(_('updating phase of %s '
+                                           'to %s from %s failed!\n')
+                                            % (newremotehead, newphase,
+                                               oldphase))
             finally:
                 locallock.release()
         finally: