[PATCH 07/13] simplify linearize_logical()

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



The linearized code for logical expressions looks like:
	.Lc
		... condition 1 ...
		cbr	%c, .L1, .L2
	.L1
		%phisrc	%phi1 <- $1
		br	.Lm
	.L2
		... condition 2 ...
		%phisrc	%phi2 <- %r
		br	.Lm
	.Lm
		%phi	%r <- %phi1, %phi2

But .L1 can easily be merged with .Lc:
	.Lc
		... condition 1 ...
		%phisrc	%phi1 <- $1
		cbr	%c, .Lm, .L2
	.L2
		... condition 2 ...
		%phisrc	%phi2 <- %r
		br	.Lm
	.Lm
		%phi	%r <- %phi1, %phi2

Do this simplification which:
* creates less basic blocks & branches
* do at linearization time a simplification not done later.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>
---
 linearize.c                 |  41 ++++-----
 validation/linear/logical.c | 160 +++++++++++++++---------------------
 2 files changed, 82 insertions(+), 119 deletions(-)

diff --git a/linearize.c b/linearize.c
index 3dfe45c0e..eeef0ba73 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1644,48 +1644,35 @@ static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *
 
 static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
 {
-	struct basic_block *merge;
+	struct basic_block *other, *merge;
 	pseudo_t phi1, phi2;
 
 	if (!ep->active || !expr->left || !expr->right)
 		return VOID;
 
-	if (expr->op == SPECIAL_LOGICAL_OR) {
-		struct expression *expr_false = expr->right;
-		struct basic_block *bb_true = alloc_basic_block(ep, expr->pos);
-		struct basic_block *bb_false = alloc_basic_block(ep, expr_false->pos);
-		pseudo_t src1, src2;
+	other = alloc_basic_block(ep, expr->right->pos);
+	merge = alloc_basic_block(ep, expr->pos);
 
-		merge = alloc_basic_block(ep, expr->pos);
-		linearize_cond_branch(ep, expr->left, bb_true, bb_false);
+	if (expr->op == SPECIAL_LOGICAL_OR) {
+		pseudo_t src2;
 
-		set_activeblock(ep, bb_true);
-		src1 = value_pseudo(1);
-		phi1 = alloc_phi(ep->active, src1, expr->ctype);
-		add_goto(ep, merge);
+		phi1 = alloc_phi(ep->active, value_pseudo(1), expr->ctype);
+		linearize_cond_branch(ep, expr->left, merge, other);
 
-		set_activeblock(ep, bb_false);
-		src2 = linearize_expression_to_bool(ep, expr_false);
+		set_activeblock(ep, other);
+		src2 = linearize_expression_to_bool(ep, expr->right);
 		src2 = cast_pseudo(ep, src2, &bool_ctype, expr->ctype);
 		phi2 = alloc_phi(ep->active, src2, expr->ctype);
 	} else {
-		struct expression *expr_true = expr->right;
-		struct basic_block *bb_true = alloc_basic_block(ep, expr_true->pos);
-		struct basic_block *bb_false = alloc_basic_block(ep, expr->pos);
-		pseudo_t src1, src2;
+		pseudo_t src1;
 
-		merge = alloc_basic_block(ep, expr->pos);
-		linearize_cond_branch(ep, expr->left, bb_true, bb_false);
+		phi2 = alloc_phi(ep->active, value_pseudo(0), expr->ctype);
+		linearize_cond_branch(ep, expr->left, other, merge);
 
-		set_activeblock(ep, bb_true);
-		src1 = linearize_expression_to_bool(ep, expr_true);
+		set_activeblock(ep, other);
+		src1 = linearize_expression_to_bool(ep, expr->right);
 		src1 = cast_pseudo(ep, src1, &bool_ctype, expr->ctype);
 		phi1 = alloc_phi(ep->active, src1, expr->ctype);
-		add_goto(ep, merge);
-
-		set_activeblock(ep, bb_false);
-		src2 = value_pseudo(0);
-		phi2 = alloc_phi(ep->active, src2, expr->ctype);
 	}
 
 	set_activeblock(ep, merge);
diff --git a/validation/linear/logical.c b/validation/linear/logical.c
index ed0dd70e9..148ad427b 100644
--- a/validation/linear/logical.c
+++ b/validation/linear/logical.c
@@ -26,15 +26,12 @@ os:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	phisrc.32   %phi1 <- $1
 	load.32     %r1 <- 0[i]
 	setne.1     %r2 <- %r1, $0
-	cbr         %r2, .L2, .L3
+	cbr         %r2, .L3, .L2
 
 .L2:
-	phisrc.32   %phi1 <- $1
-	br          .L4
-
-.L3:
 	load.64     %r3 <- 0[b]
 	load.32     %r4 <- 0[%r3]
 	lsr.32      %r5 <- %r4, $1
@@ -42,9 +39,9 @@ os:
 	setne.1     %r7 <- %r6, $0
 	zext.32     %r8 <- (1) %r7
 	phisrc.32   %phi2 <- %r8
-	br          .L4
+	br          .L3
 
-.L4:
+.L3:
 	phi.32      %r9 <- %phi1, %phi2
 	phisrc.32   %phi3(return) <- %r9
 	br          .L1
@@ -55,19 +52,16 @@ os:
 
 
 ou:
-.L5:
+.L4:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	phisrc.32   %phi5 <- $1
 	load.32     %r11 <- 0[i]
 	setne.1     %r12 <- %r11, $0
-	cbr         %r12, .L7, .L8
+	cbr         %r12, .L7, .L6
 
-.L7:
-	phisrc.32   %phi5 <- $1
-	br          .L9
-
-.L8:
+.L6:
 	load.64     %r13 <- 0[b]
 	load.32     %r14 <- 0[%r13]
 	lsr.32      %r15 <- %r14, $3
@@ -75,206 +69,188 @@ ou:
 	setne.1     %r17 <- %r16, $0
 	zext.32     %r18 <- (1) %r17
 	phisrc.32   %phi6 <- %r18
-	br          .L9
+	br          .L7
 
-.L9:
+.L7:
 	phi.32      %r19 <- %phi5, %phi6
 	phisrc.32   %phi7(return) <- %r19
-	br          .L6
+	br          .L5
 
-.L6:
+.L5:
 	phi.32      %r20 <- %phi7(return)
 	ret.32      %r20
 
 
 ol:
-.L10:
+.L8:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	phisrc.32   %phi9 <- $1
 	load.32     %r21 <- 0[i]
 	setne.1     %r22 <- %r21, $0
-	cbr         %r22, .L12, .L13
+	cbr         %r22, .L11, .L10
 
-.L12:
-	phisrc.32   %phi9 <- $1
-	br          .L14
-
-.L13:
+.L10:
 	load.64     %r23 <- 0[b]
 	load.64     %r24 <- 8[%r23]
 	setne.1     %r25 <- %r24, $0
 	zext.32     %r26 <- (1) %r25
 	phisrc.32   %phi10 <- %r26
-	br          .L14
+	br          .L11
 
-.L14:
+.L11:
 	phi.32      %r27 <- %phi9, %phi10
 	phisrc.32   %phi11(return) <- %r27
-	br          .L11
+	br          .L9
 
-.L11:
+.L9:
 	phi.32      %r28 <- %phi11(return)
 	ret.32      %r28
 
 
 od:
-.L15:
+.L12:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	phisrc.32   %phi13 <- $1
 	load.32     %r29 <- 0[i]
 	setne.1     %r30 <- %r29, $0
-	cbr         %r30, .L17, .L18
+	cbr         %r30, .L15, .L14
 
-.L17:
-	phisrc.32   %phi13 <- $1
-	br          .L19
-
-.L18:
+.L14:
 	load.64     %r31 <- 0[b]
 	load.64     %r32 <- 16[%r31]
 	setfval.64  %r33 <- 0.000000e+00
 	fcmpune.1   %r34 <- %r32, %r33
 	zext.32     %r35 <- (1) %r34
 	phisrc.32   %phi14 <- %r35
-	br          .L19
+	br          .L15
 
-.L19:
+.L15:
 	phi.32      %r36 <- %phi13, %phi14
 	phisrc.32   %phi15(return) <- %r36
-	br          .L16
+	br          .L13
 
-.L16:
+.L13:
 	phi.32      %r37 <- %phi15(return)
 	ret.32      %r37
 
 
 as:
-.L20:
+.L16:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	phisrc.32   %phi17 <- $0
 	load.32     %r38 <- 0[i]
 	setne.1     %r39 <- %r38, $0
-	cbr         %r39, .L22, .L23
+	cbr         %r39, .L18, .L19
 
-.L22:
+.L18:
 	load.64     %r40 <- 0[b]
 	load.32     %r41 <- 0[%r40]
 	lsr.32      %r42 <- %r41, $1
 	trunc.2     %r43 <- (32) %r42
 	setne.1     %r44 <- %r43, $0
 	zext.32     %r45 <- (1) %r44
-	phisrc.32   %phi17 <- %r45
-	br          .L24
-
-.L23:
-	phisrc.32   %phi18 <- $0
-	br          .L24
+	phisrc.32   %phi18 <- %r45
+	br          .L19
 
-.L24:
-	phi.32      %r46 <- %phi17, %phi18
+.L19:
+	phi.32      %r46 <- %phi18, %phi17
 	phisrc.32   %phi19(return) <- %r46
-	br          .L21
+	br          .L17
 
-.L21:
+.L17:
 	phi.32      %r47 <- %phi19(return)
 	ret.32      %r47
 
 
 au:
-.L25:
+.L20:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	phisrc.32   %phi21 <- $0
 	load.32     %r48 <- 0[i]
 	setne.1     %r49 <- %r48, $0
-	cbr         %r49, .L27, .L28
+	cbr         %r49, .L22, .L23
 
-.L27:
+.L22:
 	load.64     %r50 <- 0[b]
 	load.32     %r51 <- 0[%r50]
 	lsr.32      %r52 <- %r51, $3
 	trunc.3     %r53 <- (32) %r52
 	setne.1     %r54 <- %r53, $0
 	zext.32     %r55 <- (1) %r54
-	phisrc.32   %phi21 <- %r55
-	br          .L29
-
-.L28:
-	phisrc.32   %phi22 <- $0
-	br          .L29
+	phisrc.32   %phi22 <- %r55
+	br          .L23
 
-.L29:
-	phi.32      %r56 <- %phi21, %phi22
+.L23:
+	phi.32      %r56 <- %phi22, %phi21
 	phisrc.32   %phi23(return) <- %r56
-	br          .L26
+	br          .L21
 
-.L26:
+.L21:
 	phi.32      %r57 <- %phi23(return)
 	ret.32      %r57
 
 
 al:
-.L30:
+.L24:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	phisrc.32   %phi25 <- $0
 	load.32     %r58 <- 0[i]
 	setne.1     %r59 <- %r58, $0
-	cbr         %r59, .L32, .L33
+	cbr         %r59, .L26, .L27
 
-.L32:
+.L26:
 	load.64     %r60 <- 0[b]
 	load.64     %r61 <- 8[%r60]
 	setne.1     %r62 <- %r61, $0
 	zext.32     %r63 <- (1) %r62
-	phisrc.32   %phi25 <- %r63
-	br          .L34
-
-.L33:
-	phisrc.32   %phi26 <- $0
-	br          .L34
+	phisrc.32   %phi26 <- %r63
+	br          .L27
 
-.L34:
-	phi.32      %r64 <- %phi25, %phi26
+.L27:
+	phi.32      %r64 <- %phi26, %phi25
 	phisrc.32   %phi27(return) <- %r64
-	br          .L31
+	br          .L25
 
-.L31:
+.L25:
 	phi.32      %r65 <- %phi27(return)
 	ret.32      %r65
 
 
 ad:
-.L35:
+.L28:
 	<entry-point>
 	store.32    %arg1 -> 0[i]
 	store.64    %arg2 -> 0[b]
+	phisrc.32   %phi29 <- $0
 	load.32     %r66 <- 0[i]
 	setne.1     %r67 <- %r66, $0
-	cbr         %r67, .L37, .L38
+	cbr         %r67, .L30, .L31
 
-.L37:
+.L30:
 	load.64     %r68 <- 0[b]
 	load.64     %r69 <- 16[%r68]
 	setfval.64  %r70 <- 0.000000e+00
 	fcmpune.1   %r71 <- %r69, %r70
 	zext.32     %r72 <- (1) %r71
-	phisrc.32   %phi29 <- %r72
-	br          .L39
-
-.L38:
-	phisrc.32   %phi30 <- $0
-	br          .L39
+	phisrc.32   %phi30 <- %r72
+	br          .L31
 
-.L39:
-	phi.32      %r73 <- %phi29, %phi30
+.L31:
+	phi.32      %r73 <- %phi30, %phi29
 	phisrc.32   %phi31(return) <- %r73
-	br          .L36
+	br          .L29
 
-.L36:
+.L29:
 	phi.32      %r74 <- %phi31(return)
 	ret.32      %r74
 
-- 
2.18.0

--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html



[Index of Archives]     [Newbies FAQ]     [LKML]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Trinity Fuzzer Tool]

  Powered by Linux