[PATCH 0/5] IR cleanup

[PATCH 0/5] IR cleanup

[Luc Van Oostenryck]

This series contains some cleanup of the IR as well
as some changes in the details of how the IR is defined. 

Luc Van Oostenryck (5):
  IR: fix typo in IR doc
  IR: remove now unused OP_LNOP & OP_SNOP
  IR: remove never-generated instructions
  IR: let .cond unionize with .src and not .target
  IR: let OP_COMPUTEGOTO use .src instead of .target

 Documentation/IR.md | 22 +++-------------------
 example.c           | 10 ----------
 flow.c              |  4 +---
 linearize.c         | 18 ++++--------------
 linearize.h         | 19 ++++---------------
 liveness.c          | 15 +--------------
 sparse-llvm.c       |  8 +-------
 7 files changed, 14 insertions(+), 82 deletions(-)

-- 
2.16.0

[PATCH 1/5] IR: fix typo in IR doc

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Documentation/IR.md | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/Documentation/IR.md b/Documentation/IR.md
index f18d3507d..f212fe6c4 100644
--- a/Documentation/IR.md
+++ b/Documentation/IR.md
@@ -8,7 +8,7 @@ used by which operation.
 Some of those fields are used by almost all instructions,
 some others are specific to only one or a few instructions.
 The common ones are:
-- .src1, .src2, .src2, .src3: (pseudo_t) operands of binops or ternary ops.
+- .src1, .src2, .src3: (pseudo_t) operands of binops or ternary ops.
 - .src: (pseudo_t) operand of unary ops (alias for .src1).
 - .target: (pseudo_t) result of unary, binary & ternary ops, is sometimes used
 	otherwise by some others instructions.
-- 
2.16.0

[PATCH 2/5] IR: remove now unused OP_LNOP & OP_SNOP

[Luc Van Oostenryck]

No instructions has an opcode set to OP_[LS]NOP anymore
so we can now remove all remaining traces of these opcode.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Documentation/IR.md | 6 ------
 example.c           | 2 --
 flow.c              | 4 +---
 linearize.c         | 6 ++----
 linearize.h         | 2 --
 liveness.c          | 2 --
 sparse-llvm.c       | 6 ------
 7 files changed, 3 insertions(+), 25 deletions(-)

diff --git a/Documentation/IR.md b/Documentation/IR.md
index f212fe6c4..1612f3390 100644
--- a/Documentation/IR.md
+++ b/Documentation/IR.md
@@ -354,12 +354,6 @@ Invalid operation (should never be generated).
 #### OP_NOP
 No-op (should never be generated).
 
-#### OP_SNOP
-Store no-op (removed store operation).
-
-#### OP_LNOP
-Load no-op (removed load operation).
-
 #### OP_DEATHNOTE
 Annotation telling the pseudo will be death after the next
 instruction (other than some other annotation, that is).
diff --git a/example.c b/example.c
index 691e0f97c..e3d2a6c26 100644
--- a/example.c
+++ b/example.c
@@ -89,8 +89,6 @@ static const char *opcodes[] = {
 	[OP_VANEXT] = "va_next",
 	[OP_VAARG] = "va_arg",
 	[OP_SLICE] = "slice",
-	[OP_SNOP] = "snop",
-	[OP_LNOP] = "lnop",
 	[OP_NOP] = "nop",
 	[OP_DEATHNOTE] = "dead",
 	[OP_ASM] = "asm",
diff --git a/flow.c b/flow.c
index 495b118d2..aa3671af9 100644
--- a/flow.c
+++ b/flow.c
@@ -690,8 +690,6 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 			mod |= MOD_ADDRESSABLE;
 			goto external_visibility;
 		case OP_NOP:
-		case OP_SNOP:
-		case OP_LNOP:
 		case OP_PHI:
 			continue;
 		default:
@@ -964,7 +962,7 @@ void pack_basic_blocks(struct entrypoint *ep)
 			if (!first->bb)
 				continue;
 			switch (first->opcode) {
-			case OP_NOP: case OP_LNOP: case OP_SNOP:
+			case OP_NOP:
 			case OP_INLINED_CALL:
 				continue;
 			case OP_CBR:
diff --git a/linearize.c b/linearize.c
index 3b4b0d9b4..7cc60c4f1 100644
--- a/linearize.c
+++ b/linearize.c
@@ -261,8 +261,6 @@ static const char *opcodes[] = {
 	[OP_VANEXT] = "va_next",
 	[OP_VAARG] = "va_arg",
 	[OP_SLICE] = "slice",
-	[OP_SNOP] = "snop",
-	[OP_LNOP] = "lnop",
 	[OP_NOP] = "nop",
 	[OP_DEATHNOTE] = "dead",
 	[OP_ASM] = "asm",
@@ -437,10 +435,10 @@ const char *show_instruction(struct instruction *insn)
 		} END_FOR_EACH_PTR(phi);
 		break;
 	}	
-	case OP_LOAD: case OP_LNOP:
+	case OP_LOAD:
 		buf += sprintf(buf, "%s <- %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
 		break;
-	case OP_STORE: case OP_SNOP:
+	case OP_STORE:
 		buf += sprintf(buf, "%s -> %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
 		break;
 	case OP_INLINED_CALL:
diff --git a/linearize.h b/linearize.h
index 15a6be9c9..6640fcf2e 100644
--- a/linearize.h
+++ b/linearize.h
@@ -235,8 +235,6 @@ enum opcode {
 	OP_VANEXT,
 	OP_VAARG,
 	OP_SLICE,
-	OP_SNOP,
-	OP_LNOP,
 	OP_NOP,
 	OP_DEATHNOTE,
 	OP_ASM,
diff --git a/liveness.c b/liveness.c
index 424979656..07a95d68b 100644
--- a/liveness.c
+++ b/liveness.c
@@ -150,8 +150,6 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	case OP_GET_ELEMENT_PTR:
 	case OP_VANEXT:
 	case OP_VAARG:
-	case OP_SNOP:
-	case OP_LNOP:
 	case OP_NOP:
 	case OP_CONTEXT:
 		break;
diff --git a/sparse-llvm.c b/sparse-llvm.c
index 3a1778083..beb3a5f24 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -1029,15 +1029,9 @@ static void output_insn(struct function *fn, struct instruction *insn)
 	case OP_LOAD:
 		output_op_load(fn, insn);
 		break;
-	case OP_LNOP:
-		assert(0);
-		break;
 	case OP_STORE:
 		output_op_store(fn, insn);
 		break;
-	case OP_SNOP:
-		assert(0);
-		break;
 	case OP_INLINED_CALL:
 		break;
 	case OP_CALL:
-- 
2.16.0

[PATCH 3/5] IR: remove never-generated instructions

[Luc Van Oostenryck]

Some of the IR instructions have been defined but are
never generated.

Remove them as they have no purposes.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Documentation/IR.md | 10 ----------
 example.c           |  8 --------
 linearize.c         |  8 --------
 linearize.h         | 10 +---------
 liveness.c          |  8 --------
 5 files changed, 1 insertion(+), 43 deletions(-)

diff --git a/Documentation/IR.md b/Documentation/IR.md
index 1612f3390..27adc91a6 100644
--- a/Documentation/IR.md
+++ b/Documentation/IR.md
@@ -357,13 +357,3 @@ No-op (should never be generated).
 #### OP_DEATHNOTE
 Annotation telling the pseudo will be death after the next
 instruction (other than some other annotation, that is).
-
-### Unused ops
-#### OP_VANEXT
-#### OP_VAARG
-#### OP_MALLOC
-#### OP_FREE
-#### OP_ALLOCA
-#### OP_GET_ELEMENT_PTR
-#### OP_INVOKE
-#### OP_UNWIND
diff --git a/example.c b/example.c
index e3d2a6c26..7aa8f8c17 100644
--- a/example.c
+++ b/example.c
@@ -25,9 +25,7 @@ static const char *opcodes[] = {
 	[OP_BR] = "br",
 	[OP_CBR] = "cbr",
 	[OP_SWITCH] = "switch",
-	[OP_INVOKE] = "invoke",
 	[OP_COMPUTEDGOTO] = "jmp *",
-	[OP_UNWIND] = "unwind",
 	
 	/* Binary */
 	[OP_ADD] = "add",
@@ -69,13 +67,9 @@ static const char *opcodes[] = {
 	[OP_SEL] = "select",
 	
 	/* Memory */
-	[OP_MALLOC] = "malloc",
-	[OP_FREE] = "free",
-	[OP_ALLOCA] = "alloca",
 	[OP_LOAD] = "load",
 	[OP_STORE] = "store",
 	[OP_SETVAL] = "set",
-	[OP_GET_ELEMENT_PTR] = "getelem",
 
 	/* Other */
 	[OP_PHI] = "phi",
@@ -86,8 +80,6 @@ static const char *opcodes[] = {
 	[OP_FPCAST] = "fpcast",
 	[OP_PTRCAST] = "ptrcast",
 	[OP_CALL] = "call",
-	[OP_VANEXT] = "va_next",
-	[OP_VAARG] = "va_arg",
 	[OP_SLICE] = "slice",
 	[OP_NOP] = "nop",
 	[OP_DEATHNOTE] = "dead",
diff --git a/linearize.c b/linearize.c
index 7cc60c4f1..0fa12c36f 100644
--- a/linearize.c
+++ b/linearize.c
@@ -172,9 +172,7 @@ static const char *opcodes[] = {
 	[OP_BR] = "br",
 	[OP_CBR] = "cbr",
 	[OP_SWITCH] = "switch",
-	[OP_INVOKE] = "invoke",
 	[OP_COMPUTEDGOTO] = "jmp *",
-	[OP_UNWIND] = "unwind",
 	
 	/* Binary */
 	[OP_ADD] = "add",
@@ -239,15 +237,11 @@ static const char *opcodes[] = {
 	[OP_SEL] = "select",
 	
 	/* Memory */
-	[OP_MALLOC] = "malloc",
-	[OP_FREE] = "free",
-	[OP_ALLOCA] = "alloca",
 	[OP_LOAD] = "load",
 	[OP_STORE] = "store",
 	[OP_SETVAL] = "set",
 	[OP_SETFVAL] = "setfval",
 	[OP_SYMADDR] = "symaddr",
-	[OP_GET_ELEMENT_PTR] = "getelem",
 
 	/* Other */
 	[OP_PHI] = "phi",
@@ -258,8 +252,6 @@ static const char *opcodes[] = {
 	[OP_PTRCAST] = "ptrcast",
 	[OP_INLINED_CALL] = "# call",
 	[OP_CALL] = "call",
-	[OP_VANEXT] = "va_next",
-	[OP_VAARG] = "va_arg",
 	[OP_SLICE] = "slice",
 	[OP_NOP] = "nop",
 	[OP_DEATHNOTE] = "dead",
diff --git a/linearize.h b/linearize.h
index 6640fcf2e..8ff40948c 100644
--- a/linearize.h
+++ b/linearize.h
@@ -143,10 +143,8 @@ enum opcode {
 	OP_BR,
 	OP_CBR,
 	OP_SWITCH,
-	OP_INVOKE,
 	OP_COMPUTEDGOTO,
-	OP_UNWIND,
-	OP_TERMINATOR_END = OP_UNWIND,
+	OP_TERMINATOR_END = OP_COMPUTEDGOTO,
 	
 	/* Binary */
 	OP_BINARY,
@@ -213,15 +211,11 @@ enum opcode {
 	OP_SEL,
 	
 	/* Memory */
-	OP_MALLOC,
-	OP_FREE,
-	OP_ALLOCA,
 	OP_LOAD,
 	OP_STORE,
 	OP_SETVAL,
 	OP_SETFVAL,
 	OP_SYMADDR,
-	OP_GET_ELEMENT_PTR,
 
 	/* Other */
 	OP_PHI,
@@ -232,8 +226,6 @@ enum opcode {
 	OP_PTRCAST,
 	OP_INLINED_CALL,
 	OP_CALL,
-	OP_VANEXT,
-	OP_VAARG,
 	OP_SLICE,
 	OP_NOP,
 	OP_DEATHNOTE,
diff --git a/liveness.c b/liveness.c
index 07a95d68b..0c525112b 100644
--- a/liveness.c
+++ b/liveness.c
@@ -142,14 +142,6 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 		break;
 
 	case OP_BADOP:
-	case OP_INVOKE:
-	case OP_UNWIND:
-	case OP_MALLOC:
-	case OP_FREE:
-	case OP_ALLOCA:
-	case OP_GET_ELEMENT_PTR:
-	case OP_VANEXT:
-	case OP_VAARG:
 	case OP_NOP:
 	case OP_CONTEXT:
 		break;
-- 
2.16.0

[PATCH 4/5] IR: let .cond unionize with .src and not .target

[Luc Van Oostenryck]

In struct instruction, .target is normally used to hold
the result. Its value is thus produced/defined by instructions.
On the contrary, .cond is used as an input value and is
thus used by instructions.

However, these two fields belong to the same union. This
creates slight complications for code, like liveness analysis
which care about which fields are used and which are defined
by the instructions.

Change this by unionizing .cond with .src, .src1 & friends instead
of with .target.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Documentation/IR.md | 2 +-
 linearize.h         | 7 +++----
 sparse-llvm.c       | 2 +-
 3 files changed, 5 insertions(+), 6 deletions(-)

diff --git a/Documentation/IR.md b/Documentation/IR.md
index 27adc91a6..8f5827dfc 100644
--- a/Documentation/IR.md
+++ b/Documentation/IR.md
@@ -12,7 +12,7 @@ The common ones are:
 - .src: (pseudo_t) operand of unary ops (alias for .src1).
 - .target: (pseudo_t) result of unary, binary & ternary ops, is sometimes used
 	otherwise by some others instructions.
-- .cond: (pseudo_t) input operands for condition (alias .target!)
+- .cond: (pseudo_t) input operands for condition (alias .src/.src1)
 - .type: (symbol*) usually the type of .result, sometimes of the operands
 
 ### Terminators
diff --git a/linearize.h b/linearize.h
index 8ff40948c..7c3a0b645 100644
--- a/linearize.h
+++ b/linearize.h
@@ -74,18 +74,17 @@ struct instruction {
 	struct basic_block *bb;
 	struct position pos;
 	struct symbol *type;
-	union {
-		pseudo_t target;
-		pseudo_t cond;		/* for branch and switch */
-	};
+	pseudo_t target;
 	union {
 		struct /* entrypoint */ {
 			struct pseudo_list *arg_list;
 		};
 		struct /* branch */ {
+			pseudo_t cond;
 			struct basic_block *bb_true, *bb_false;
 		};
 		struct /* switch */ {
+			pseudo_t _cond;
 			struct multijmp_list *multijmp_list;
 		};
 		struct /* phi_node */ {
diff --git a/sparse-llvm.c b/sparse-llvm.c
index beb3a5f24..156bd02f3 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -809,7 +809,7 @@ static void output_op_switch(struct function *fn, struct instruction *insn)
 			def = jmp->target;
 	} END_FOR_EACH_PTR(jmp);
 
-	sw_val = get_ioperand(fn, insn->type, insn->target);
+	sw_val = get_ioperand(fn, insn->type, insn->cond);
 	target = LLVMBuildSwitch(fn->builder, sw_val,
 				 def ? def->priv : NULL, n_jmp);
 
-- 
2.16.0

[PATCH 5/5] IR: let OP_COMPUTEGOTO use .src instead of .target

[Luc Van Oostenryck]

In struct instruction, .target is normally used to hold
the result. Its value is thus produced/defined by instructions.

However, OP_COMPUTEDGOTO use .target as an input. This
creates slight complications for code, like liveness analysis,
which care about which fields are used and which are defined
by the instructions.

Change this by letting OP_COMPUTEDGOTO use .src for its
operand instead of .target.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Documentation/IR.md | 2 +-
 linearize.c         | 4 ++--
 liveness.c          | 5 +----
 3 files changed, 4 insertions(+), 7 deletions(-)

diff --git a/Documentation/IR.md b/Documentation/IR.md
index 8f5827dfc..ef486ed5a 100644
--- a/Documentation/IR.md
+++ b/Documentation/IR.md
@@ -39,7 +39,7 @@ Switch / multi-branch
 
 #### OP_COMPUTEDGOTO
 Computed goto / branch to register
-- .target: target address (type is irrelevant, void*)
+- .src: address to branch to (void*)
 - .multijmp_list: list of possible destination basic blocks
 
 ### Arithmetic binops
diff --git a/linearize.c b/linearize.c
index 0fa12c36f..370c6c7d7 100644
--- a/linearize.c
+++ b/linearize.c
@@ -399,7 +399,7 @@ const char *show_instruction(struct instruction *insn)
 	}
 	case OP_COMPUTEDGOTO: {
 		struct multijmp *jmp;
-		buf += sprintf(buf, "%s", show_pseudo(insn->target));
+		buf += sprintf(buf, "%s", show_pseudo(insn->src));
 		FOR_EACH_PTR(insn->multijmp_list, jmp) {
 			buf += sprintf(buf, ", .L%u", jmp->target->nr);
 		} END_FOR_EACH_PTR(jmp);
@@ -2120,7 +2120,7 @@ static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stm
 
 		pseudo = linearize_expression(ep, expr);
 		goto_ins = alloc_instruction(OP_COMPUTEDGOTO, 0);
-		use_pseudo(goto_ins, pseudo, &goto_ins->target);
+		use_pseudo(goto_ins, pseudo, &goto_ins->src);
 		add_one_insn(ep, goto_ins);
 
 		FOR_EACH_PTR(stmt->target_list, sym) {
diff --git a/liveness.c b/liveness.c
index 0c525112b..568e2d5f2 100644
--- a/liveness.c
+++ b/liveness.c
@@ -53,6 +53,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 
 	switch (insn->opcode) {
 	case OP_RET:
+	case OP_COMPUTEDGOTO:
 		USES(src);
 		break;
 
@@ -61,10 +62,6 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 		USES(cond);
 		break;
 
-	case OP_COMPUTEDGOTO:
-		USES(target);
-		break;
-	
 	/* Binary */
 	case OP_BINARY ... OP_BINARY_END:
 	case OP_FPCMP ... OP_FPCMP_END:
-- 
2.16.0

Re: [PATCH 3/5] IR: remove never-generated instructions

[Dibyendu Majumdar]

On 14 February 2018 at 01:08, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Some of the IR instructions have been defined but are
> never generated.
>
> -### Unused ops
> -#### OP_VANEXT
> -#### OP_VAARG
> -#### OP_MALLOC
> -#### OP_FREE
> -#### OP_ALLOCA
> -#### OP_GET_ELEMENT_PTR
> -#### OP_INVOKE
> -#### OP_UNWIND

Hi Luc, I would argue for not removing some of these instructions.

The VA instructions are definitely needed as today Sparse backend code
generators cannot handle var args because no instructions are
generated.
Similarly alloca should perhaps be emitted to indicate stack
allocations - this would make the stack usage explicit.

Thanks and Regards
Dibyendu

Re: [PATCH 3/5] IR: remove never-generated instructions

[Luc Van Oostenryck]

On Wed, Feb 14, 2018 at 05:08:06AM +0000, Dibyendu Majumdar wrote:
> On 14 February 2018 at 01:08, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Some of the IR instructions have been defined but are
> > never generated.
> >
> > -### Unused ops
> > -#### OP_VANEXT
> > -#### OP_VAARG
> > -#### OP_MALLOC
> > -#### OP_FREE
> > -#### OP_ALLOCA
> > -#### OP_GET_ELEMENT_PTR
> > -#### OP_INVOKE
> > -#### OP_UNWIND
> 
> Hi Luc, I would argue for not removing some of these instructions.
> 
> The VA instructions are definitely needed as today Sparse backend code
> generators cannot handle var args because no instructions are
> generated.
> Similarly alloca should perhaps be emitted to indicate stack
> allocations - this would make the stack usage explicit.

Yes, backends need support for that. Be assured that I'm acutely
aware of it. What is present here is just some definitions with
nothing behind.

It should also be noted that:
- something like OP_VANEXT is not really needed (depending on how
  OP_VAARG is specified),
- we don't need a new instruction for sparse-llvm to be able to
  generate LLVM's alloca (our handling of symbol together with
  OP_SYMADDR is enough)

So these defines I propose here to remove are totally useless. I can
leave the definition of OP_VAARG but I prefer to reintroduce it when :
- its semantic will be specified and documented
- I'll add the code that will really use it.

Best regards,
-- Luc