This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

PATCH RFA: Change MIPS ffs<mode>2 from define_insn to define_expand

The MIPS backend implements ffs<mode>2 using an inline loop.  This
dates back to the original implementation of in 1992.  Like
the recently removed abs<mode>2, I believe this was due to a desire to
fill branch delay slots.

If we simply remove the ffs<mode>2 insn, then calls to __builtin_ffs
will be expanded into calls to the library function ffs.  Eric felt,
in an offline discussion, that this would not be the best approach.

However, using a define_insn for ffs<mode>2 means that we can not
rearrange any of the instructions in the loop for, e.g., scheduling,
branch delay slot filling, or jump threading.  If we are going to keep
the insn, it seems desirable to at least use a define_expand so that
the instructions are exposed to the RTL optimizers.

For a simple example, this function:

int bar (int i) { return __builtin_ffs (i) ? quux (i) : quux (i + 1); }

currently expands to this:

	.set	noreorder
	move	$2,$0
	move	$6,$4
	beq	$6,$0,2f
1:	and	$5,$6,0x0001
	addu	$2,$2,1
	beq	$5,$0,1b
	srl	$6,$6,1
	.set	reorder
	bne	$2,$0,$L8
	addiu	$4,$4,1
	j	quux

With the appended patch, it expands to this:

	.set	noreorder
	.set	nomacro
	beq	$4,$0,$L9
	move	$3,$0
	.set	macro
	.set	reorder

	andi	$2,$4,0x1
	addiu	$3,$3,1
	.set	noreorder
	.set	nomacro
	beq	$2,$0,$L15
	srl	$4,$4,1
	.set	macro
	.set	reorder

	bne	$3,$0,$L18
	addiu	$4,$4,1
	j	quux

Note that the initial branch now avoids testing the same value twice.

Of course, it would be even better if we expanded earlier, into trees,
so that the instructions were exposed to the tree optimizers.  And for
that matter this code is essentially generic and not really MIPS
specific at all.

Tested by running the gcc testsuite against a simulator.


2005-07-08  Ian Lance Taylor  <>

	* config/mips/ (ffs<mode>2): Rewrite as define_expand.

Index: config/mips/
RCS file: /cvs/gcc/gcc/gcc/config/mips/,v
retrieving revision 1.325
diff -u -r1.325
--- config/mips/	8 Jul 2005 05:24:51 -0000	1.325
+++ config/mips/	8 Jul 2005 21:11:28 -0000
@@ -1913,36 +1913,57 @@
 ;;  ....................
-(define_insn "ffs<mode>2"
-  [(set (match_operand:GPR 0 "register_operand" "=&d")
-	(ffs:GPR (match_operand:GPR 1 "register_operand" "d")))
-   (clobber (match_scratch:GPR 2 "=&d"))
-   (clobber (match_scratch:GPR 3 "=&d"))]
-  if (optimize && find_reg_note (insn, REG_DEAD, operands[1]))
-    return "%(\
-  return "%(\
-  [(set_attr "type" "multi")
-   (set_attr "mode" "<MODE>")
-   (set_attr "length" "28")])
+;; We expand ffs into an inline loop.  This exists for historical
+;; purposes, because there has been a define_insn for ffs<mode>2 since
+;; the original MIPS port.  If we are going to use a loop at all, we
+;; should really expanded it at the tree level in non-target-specific
+;; code.
+;; The generated code looks like this (this is .set reorder
+;; mode--i.e. delay slots are not filled yet):
+;; 	move	$reg1, $0
+;;	move	$reg2, op1
+;;	beq	$reg2, $0, 2f
+;;   1:
+;;	addu	$reg1, $reg1, 1
+;;	and	$reg3, $reg2, 1
+;;	srl	$reg2, $reg2, 1
+;;	beq	$reg3, $0, 1b
+;;   2:
+;;	move	op0, $reg1
+(define_expand "ffs<mode>2"
+  [(set (match_operand:GPR 0 "nonimmediate_operand" "")
+	(ffs:GPR (match_operand:GPR 1 "move_operand" "")))]
+  rtx lab1 = gen_label_rtx ();
+  rtx lab2 = gen_label_rtx ();
+  rtx reg1 = gen_reg_rtx (<MODE>mode);
+  rtx reg2;
+  rtx reg3 = gen_reg_rtx (<MODE>mode);
+  rtx target;
+  emit_move_insn (reg1, const0_rtx);
+  reg2 = force_reg (<MODE>mode, operands[1]);
+  target = gen_rtx_IF_THEN_ELSE (VOIDmode,
+				 gen_rtx_EQ (<MODE>mode, reg2, const0_rtx),
+				 gen_rtx_LABEL_REF (VOIDmode, lab2),
+				 pc_rtx);
+  emit_jump_insn (gen_rtx_SET (VOIDmode, pc_rtx, target));
+  emit_label (lab1);
+  emit_insn (gen_add3_insn (reg1, reg1, const1_rtx));
+  emit_insn (gen_and<mode>3 (reg3, reg2, const1_rtx));
+  emit_insn (gen_lshr<mode>3 (reg2, reg2, const1_rtx));
+  target = gen_rtx_IF_THEN_ELSE (VOIDmode,
+				 gen_rtx_EQ (<MODE>mode, reg3, const0_rtx),
+				 gen_rtx_LABEL_REF (VOIDmode, lab1),
+				 pc_rtx);
+  emit_jump_insn (gen_rtx_SET (VOIDmode, pc_rtx, target));
+  emit_label (lab2);
+  emit_move_insn (operands[0], reg1);
+  DONE;
 ;;  ...................

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]