Index: llvm/lib/Transforms/Scalar/LICM.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/LICM.cpp
+++ llvm/lib/Transforms/Scalar/LICM.cpp
@@ -1201,6 +1201,18 @@
       // Widenable conditions don't actually alias anything or throw
       return true;
 
+    // FIXME: If this call uses tokens, we should not touch it. Currently,
+    // tokens may penetrate through LCSSA form and lead optimizations that
+    // believe that *all* in-loop values only go outside through LCSSA phis
+    // into making incorrect transforms. See one of such examples at PR56243.
+    // We do not want to make LCSSA even more broken than it used to be.
+    //
+    // If the contradiction between definition of LCSSA and ability of tokens
+    // to violate it will ever be resolved, we can lift this check.
+    if (any_of(CI->operands(),
+               [](const Value *V) { return V->getType()->isTokenTy(); }))
+      return false;
+
     // Handle simple cases by querying alias analysis.
     FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
     if (Behavior == FMRB_DoesNotAccessMemory)
Index: llvm/test/Transforms/LICM/pr56243.ll
===================================================================
--- llvm/test/Transforms/LICM/pr56243.ll
+++ llvm/test/Transforms/LICM/pr56243.ll
@@ -1,25 +1,54 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes='loop-mssa(licm,loop-simplifycfg)' < %s | FileCheck %s
 
-; REQUIRES: asserts
-; XFAIL: *
 
-; Here we end un sinking a user of token down from the loop, therefore breaching LCSSA form.
+; If we end un sinking a user of token down from the loop, therefore breaching LCSSA form.
 ; Then, LoopSimplifyCFG expcets that LCSSA form is maintained, and remains unaware that
 ; it may be penetrated by tokens. As result, it may end up breaking dominance between def and
 ; use by introducing fake temporary edges.
-
+; Make sure LICM doesn't do it.
 define i8 addrspace(1)* @test_gc_relocate() gc "statepoint-example" {
-; CHECK-LABEL: @test_gc_relocate
+; CHECK-LABEL: @test_gc_relocate(
+; CHECK-NEXT:    switch i32 0, label [[DOTSPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[BB57:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       .split:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    switch i32 undef, label [[BB43:%.*]] [
+; CHECK-NEXT:    i32 1, label [[BB18:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb18:
+; CHECK-NEXT:    switch i32 undef, label [[BB43]] [
+; CHECK-NEXT:    i32 0, label [[BB28:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb28:
+; CHECK-NEXT:    [[TMP34:%.*]] = call token (i64, i32, i8 addrspace(1)* (i64, i32, i32, i32)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_p1i8i64i32i32i32f(i64 2882400000, i32 0, i8 addrspace(1)* (i64, i32, i32, i32)* nonnull elementtype(i8 addrspace(1)* (i64, i32, i32, i32)) @barney.4, i32 4, i32 0, i64 undef, i32 5, i32 5, i32 undef, i32 0, i32 0) [ "deopt"(), "gc-live"(i8 addrspace(1)* undef) ]
+; CHECK-NEXT:    [[TMP35:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[TMP34]], i32 0, i32 0)
+; CHECK-NEXT:    switch i32 undef, label [[BB43]] [
+; CHECK-NEXT:    i32 1, label [[BB39:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb39:
+; CHECK-NEXT:    switch i32 undef, label [[BB43]] [
+; CHECK-NEXT:    i32 1, label [[BB45:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb43:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb45:
+; CHECK-NEXT:    br label [[BB1]]
+; CHECK:       bb57:
+; CHECK-NEXT:    ret i8 addrspace(1)* poison
+;
   br label %bb1
 
 bb1:                                              ; preds = %bb45, %0
   switch i32 undef, label %bb43 [
-    i32 1, label %bb18
+  i32 1, label %bb18
   ]
 
 bb18:                                             ; preds = %bb1
   switch i32 undef, label %bb43 [
-    i32 0, label %bb28
+  i32 0, label %bb28
   ]
 
 bb28:                                             ; preds = %bb18
@@ -29,12 +58,12 @@
 
 bb36:                                             ; preds = %bb28
   switch i32 undef, label %bb43 [
-    i32 1, label %bb39
+  i32 1, label %bb39
   ]
 
 bb39:                                             ; preds = %bb36
   switch i32 undef, label %bb43 [
-    i32 1, label %bb45
+  i32 1, label %bb45
   ]
 
 bb43:                                             ; preds = %bb39, %bb36, %bb18, %bb1