[mono/mono] 3e14c8db: [jit] Add a simple loop invariant loop motion pass for use with LLVM, which moves loop invariant instructions out of loop headers into the preceeding bblock.

   Branch: refs/heads/master
     Home: https://github.com/mono/mono
  Compare: https://github.com/mono/mono/compare/25a3e0e4b843...3e14c8db3d43

   Commit: 3e14c8db3d43ff4c466a0cd7e66f02e7bebdea1e
   Author: Zoltan Varga <[email protected]> (vargaz)
     Date: 2013-11-10 20:11:06 GMT
      URL: https://github.com/mono/mono/commit/3e14c8db3d43ff4c466a0cd7e66f02e7bebdea1e

[jit] Add a simple loop invariant loop motion pass for use with LLVM, which moves loop invariant instructions out of loop headers into the preceeding bblock.

Changed paths:
  M mono/mini/arrays.cs
  M mono/mini/mini.c
  M mono/mini/mini.h
  M mono/mini/ssa.c

Modified: mono/mini/arrays.cs
===================================================================
@@ -791,6 +791,21 @@ public enum UintEnum : uint {
 			return 5;
 		return 0;
 	}
+
+	static int llvm_ldlen_licm (int[] arr) {
+		int sum = 0;
+		// The ldlen should be moved out of the loop
+		for (int i = 0; i < arr.Length; ++i)
+			sum += arr [i];
+		return sum;
+	}
+
+	public static int test_10_llvm_ldlen_licm () {
+		int[] arr = new int [10];
+		for (int i = 0; i < 10; ++i)
+			arr [i] = 1;
+		return llvm_ldlen_licm (arr);
+	}
 }
 
 

Modified: mono/mini/mini.c
===================================================================
@@ -5362,6 +5362,7 @@ void *mono_global_codeman_reserve (int size)
 #endif
 
 	if (cfg->comp_done & MONO_COMP_SSA && COMPILE_LLVM (cfg)) {
+		mono_ssa_loop_invariant_code_motion (cfg);
 		/* This removes MONO_INST_FAULT flags too so perform it unconditionally */
 		if (cfg->opt & MONO_OPT_ABCREM)
 			mono_perform_abc_removal (cfg);

Modified: mono/mini/mini.h
===================================================================
@@ -462,7 +462,7 @@ enum {
 
 /* FIXME: Add more instructions */
 /* INEG sets the condition codes, and the OP_LNEG decomposition depends on this on x86 */
-#define MONO_INS_HAS_NO_SIDE_EFFECT(ins) (MONO_IS_MOVE (ins) || (ins->opcode == OP_ICONST) || (ins->opcode == OP_I8CONST) || MONO_IS_ZERO (ins) || (ins->opcode == OP_ADD_IMM) || (ins->opcode == OP_R8CONST) || (ins->opcode == OP_LADD_IMM) || (ins->opcode == OP_ISUB_IMM) || (ins->opcode == OP_IADD_IMM) || (ins->opcode == OP_LNEG) || (ins->opcode == OP_ISUB) || (ins->opcode == OP_CMOV_IGE) || (ins->opcode == OP_ISHL_IMM) || (ins->opcode == OP_ISHR_IMM) || (ins->opcode == OP_ISHR_UN_IMM) || (ins->opcode == OP_IAND_IMM) || (ins->opcode == OP_ICONV_TO_U1) || (ins->opcode == OP_ICONV_TO_I1) || (ins->opcode == OP_SEXT_I4) || (ins->opcode == OP_LCONV_TO_U1) || (ins->opcode == OP_ICONV_TO_U2) || (ins->opcode == OP_ICONV_TO_I2) || (ins->opcode == OP_LCONV_TO_I2) || (ins->opcode == OP_LDADDR))
+#define MONO_INS_HAS_NO_SIDE_EFFECT(ins) (MONO_IS_MOVE (ins) || (ins->opcode == OP_ICONST) || (ins->opcode == OP_I8CONST) || MONO_IS_ZERO (ins) || (ins->opcode == OP_ADD_IMM) || (ins->opcode == OP_R8CONST) || (ins->opcode == OP_LADD_IMM) || (ins->opcode == OP_ISUB_IMM) || (ins->opcode == OP_IADD_IMM) || (ins->opcode == OP_LNEG) || (ins->opcode == OP_ISUB) || (ins->opcode == OP_CMOV_IGE) || (ins->opcode == OP_ISHL_IMM) || (ins->opcode == OP_ISHR_IMM) || (ins->opcode == OP_ISHR_UN_IMM) || (ins->opcode == OP_IAND_IMM) || (ins->opcode == OP_ICONV_TO_U1) || (ins->opcode == OP_ICONV_TO_I1) || (ins->opcode == OP_SEXT_I4) || (ins->opcode == OP_LCONV_TO_U1) || (ins->opcode == OP_ICONV_TO_U2) || (ins->opcode == OP_ICONV_TO_I2) || (ins->opcode == OP_LCONV_TO_I2) || (ins->opcode == OP_LDADDR) || (ins
 ->opcode == OP_PHI) || (ins->opcode == OP_NOP) || (ins->opcode == OP_ZEXT_I4) || (ins->opcode == OP_NOT_NULL))
 
 #define MONO_METHOD_IS_FINAL(m) (((m)->flags & METHOD_ATTRIBUTE_FINAL) || ((m)->klass && ((m)->klass->flags & TYPE_ATTRIBUTE_SEALED)))
 
@@ -2470,6 +2470,7 @@ MonoBoolean ves_icall_get_frame_info            (gint32 skip, MonoBoolean need_f
 void        mono_ssa_deadce                     (MonoCompile *cfg) MONO_INTERNAL;
 void        mono_ssa_strength_reduction         (MonoCompile *cfg) MONO_INTERNAL;
 void        mono_free_loop_info                 (MonoCompile *cfg) MONO_INTERNAL;
+void        mono_ssa_loop_invariant_code_motion (MonoCompile *cfg) MONO_INTERNAL;
 
 void        mono_ssa_compute2                   (MonoCompile *cfg);
 void        mono_ssa_remove2                    (MonoCompile *cfg);

Modified: mono/mini/ssa.c
===================================================================
@@ -1350,4 +1350,114 @@
 }
 #endif
 
+void
+mono_ssa_loop_invariant_code_motion (MonoCompile *cfg)
+{
+	MonoBasicBlock *bb, *h, *idom;
+	MonoInst *ins, *n, *tins;
+	int i;
+
+	g_assert (cfg->comp_done & MONO_COMP_SSA);
+	if (!(cfg->comp_done & MONO_COMP_LOOPS) || !(cfg->comp_done & MONO_COMP_SSA_DEF_USE))
+		return;
+
+	for (bb = cfg->bb_entry->next_bb; bb; bb = bb->next_bb) {
+		GList *lp = bb->loop_blocks;
+
+		if (!lp)
+			continue;
+		h = (MonoBasicBlock *)lp->data;
+		if (bb != h)
+			continue;
+		MONO_BB_FOR_EACH_INS_SAFE (bb, n, ins) {
+			gboolean is_class_init = FALSE;
+
+			/*
+			 * Try to move instructions out of loop headers into the preceeding bblock.
+			 */
+			if (ins->opcode == OP_VOIDCALL) {
+				MonoCallInst *call = (MonoCallInst*)ins;
+
+				if (call->fptr_is_patch) {
+					MonoJumpInfo *ji = (MonoJumpInfo*)call->fptr;
+
+					if (ji->type == MONO_PATCH_INFO_CLASS_INIT)
+						is_class_init = TRUE;
+				}
+			}
+			if (ins->opcode == OP_LDLEN || ins->opcode == OP_STRLEN || ins->opcode == OP_CHECK_THIS || ins->opcode == OP_AOTCONST || is_class_init) {
+				gboolean skip;
+				int sreg;
+
+				idom = h->idom;
+				/*
+				 * h->nesting is needed to work around:
+				 * http://llvm.org/bugs/show_bug.cgi?id=17868
+				 */
+				if (!(idom && idom->last_ins && idom->last_ins->opcode == OP_BR && idom->last_ins->inst_target_bb == h && h->nesting == 1)) {
+					continue;
+				}
+
+				/*
+				 * Make sure there are no instructions with side effects before ins.
+				 */
+				skip = FALSE;
+				MONO_BB_FOR_EACH_INS (bb, tins) {
+					if (tins == ins)
+						break;
+					if (!MONO_INS_HAS_NO_SIDE_EFFECT (tins)) {
+						skip = TRUE;
+						break;
+					}
+				}
+				if (skip) {
+					/*
+					  printf ("%s\n", mono_method_full_name (cfg->method, TRUE));
+					  mono_print_ins (tins);
+					*/
+					continue;
+				}
+
+				/* Make sure we don't move the instruction before the def of its sreg */
+				if (ins->opcode == OP_LDLEN || ins->opcode == OP_STRLEN || ins->opcode == OP_CHECK_THIS)
+					sreg = ins->sreg1;
+				else
+					sreg = -1;
+				if (sreg != -1) {
+					skip = FALSE;
+					MONO_BB_FOR_EACH_INS (bb, tins) {
+						const char *spec = INS_INFO (tins->opcode);
+
+						if (tins->opcode == OP_MOVE && tins->dreg == sreg) {
+							sreg = tins->sreg1;
+						} else if (spec [MONO_INST_DEST] != ' ' && tins->dreg == ins->sreg1) {
+							skip = TRUE;
+							break;
+						}
+					}
+					if (skip)
+						continue;
+				}
+
+				if (cfg->verbose_level > 1) {
+					printf ("licm in BB%d on ", bb->block_num);
+					mono_print_ins (ins);
+				}
+				//{ static int count = 0; count ++; printf ("%d\n", count); }
+				MONO_REMOVE_INS (bb, ins);
+				mono_bblock_insert_before_ins (idom, idom->last_ins, ins);
+				if (ins->opcode == OP_LDLEN || ins->opcode == OP_STRLEN)
+					idom->has_array_access = TRUE;
+			}
+		}
+	}
+
+	cfg->comp_done &=  ~MONO_COMP_SSA_DEF_USE;
+	for (i = 0; i < cfg->num_varinfo; i++) {
+		MonoMethodVar *info = MONO_VARINFO (cfg, i);
+		info->def = NULL;
+		info->uses = NULL;
+	}
+}
+
 #endif /* DISABLE_JIT */


_______________________________________________
Mono-patches maillist  -  [email protected]
http://lists.ximian.com/mailman/listinfo/mono-patches