I have not looked at this at all, but here's a testcase reduced by bugpoint. 
This comes from 176.gcc:

----
implementation   ; Functions:

void %.subst_48() {
entry:
        br bool false, label %loopentry.0, label %UnifiedReturnBlock

loopentry.0:            ; preds = %entry, %loopentry.0
        br bool false, label %loopentry.0, label %loopentry.2

loopentry.2:            ; preds = %loopentry.0, %loopentry.2
        %tmp.968 = setle int 0, 3               ; <bool> [#uses=1]
        br bool %tmp.968, label %loopentry.2, label %UnifiedReturnBlock

UnifiedReturnBlock:             ; preds = %entry, %loopentry.2
        ret void
}
----

$ opt -licm bugpoint-reduced-simplified.bc 
Instruction does not dominate all uses!
        %tmp.968 = setle int 0, 3               ; <bool> [#uses=1]
        br bool %tmp.968, label %loopentry.2, label %UnifiedReturnBlock.loopexit
Broken module found, compilation aborted!
Abort

-Chris

As it turns out, the problem is that loop simplify is munging the dominator
information instead of updating it correctly to reflect the change it makes.

The transformation performed by LICM is correct, it's just that the verifier is
using the bogus dominator information to perform its checks.

-Chris

Fixed.  Testcase here: LoopSimplify/2004-02-05-DominatorInfoCorruption.ll

Patch here:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20040202/011175.html

-Chris