+static bool
+is_defined_before_loop(nir_ssa_def *def, nir_loop *loop)
+{
+ nir_instr *instr = def->parent_instr;
+ nir_block *block_before_loop =
+ nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node));
+
+ return instr->block->index <= block_before_loop->index;
+}
+
+typedef enum instr_invariance {
+ undefined = 0,
+ invariant,
+ not_invariant,
+} instr_invariance;
+
+static instr_invariance
+instr_is_invariant(nir_instr *instr, nir_loop *loop);
+
+static bool
+def_is_invariant(nir_ssa_def *def, nir_loop *loop)
+{
+ if (is_defined_before_loop(def, loop))
+ return invariant;
+
+ if (def->parent_instr->pass_flags == undefined)
+ def->parent_instr->pass_flags = instr_is_invariant(def->parent_instr, loop);
+
+ return def->parent_instr->pass_flags == invariant;
+}
+
+static bool
+src_is_invariant(nir_src *src, void *state)
+{
+ assert(src->is_ssa);
+ return def_is_invariant(src->ssa, (nir_loop *)state);
+}
+
+static instr_invariance
+phi_is_invariant(nir_phi_instr *instr, nir_loop *loop)
+{
+ /* Base case: it's a phi at the loop header
+ * Loop-header phis are updated in each loop iteration with
+ * the loop-carried value, and thus control-flow dependent
+ * on the loop itself.
+ */
+ if (instr->instr.block == nir_loop_first_block(loop))
+ return not_invariant;
+
+ nir_foreach_phi_src(src, instr) {
+ if (!src_is_invariant(&src->src, loop))
+ return not_invariant;
+ }
+
+ /* All loop header- and LCSSA-phis should be handled by this point. */
+ nir_cf_node *prev = nir_cf_node_prev(&instr->instr.block->cf_node);
+ assert(prev && prev->type == nir_cf_node_if);
+
+ /* Invariance of phis after if-nodes also depends on the invariance
+ * of the branch condition.
+ */
+ nir_if *if_node = nir_cf_node_as_if(prev);
+ if (!def_is_invariant(if_node->condition.ssa, loop))
+ return not_invariant;
+
+ return invariant;
+}
+
+
+/* An instruction is said to be loop-invariant if it
+ * - has no sideeffects and
+ * - solely depends on variables defined outside of the loop or
+ * by other invariant instructions
+ */
+static instr_invariance
+instr_is_invariant(nir_instr *instr, nir_loop *loop)
+{
+ assert(instr->pass_flags == undefined);
+
+ switch (instr->type) {
+ case nir_instr_type_load_const:
+ case nir_instr_type_ssa_undef:
+ return invariant;
+ case nir_instr_type_call:
+ return not_invariant;
+ case nir_instr_type_phi:
+ return phi_is_invariant(nir_instr_as_phi(instr), loop);
+ case nir_instr_type_intrinsic: {
+ nir_intrinsic_instr *intrinsic = nir_instr_as_intrinsic(instr);
+ if (!(nir_intrinsic_infos[intrinsic->intrinsic].flags & NIR_INTRINSIC_CAN_REORDER))
+ return not_invariant;
+ /* fallthrough */
+ }
+ default:
+ return nir_foreach_src(instr, src_is_invariant, loop) ? invariant : not_invariant;
+ }
+
+ return invariant;
+}
+