Data structure for assembly code? [study]

Question

I plan to create a data structure optimized for storing assembly code. Thus, I can be fully responsible for the optimization algorithms that will work on this structure. If I can compile while running. It will be a kind of dynamic execution. Is it possible? Has anyone seen something like this?

Should I use structures to bind the structure to the program stream. Are objects improved?

struct asm_code { int type; int value; int optimized; asm_code *next_to_execute; } asm_imp; 

Update: I think it will work out like a linked list.

Update: I know there are other compilers. But this is a military secret project. Therefore, we cannot trust any code. We must do it all ourselves.

Update: OK, I think I’ll just create the basic i386 machine code. But how can I go into my memory when it's finished?

Answer 1

It is possible. Dynamic code generation is even a major topic in some areas, such as software rendering and graphics. You often use all kinds of script languages ​​in the dynamic compilation of bytecode into machine code (.NET, Java, as far as I know, Perl. Recently JavaScript joined it).

You will also find that it is used in applications with very great math. It matters if, for example, you remove all multiplications with zero from the matrix multiplication, if you plan to do such a multiplication several thousand times.

I highly recommend you read the SSA code submission. This is a representation in which each primitive turns into the so-called three-dimensional form, and each variable is assigned only once (hence the same form of static single assignment).

You can run high-order optimization on such code, and it directly translates this code into executable code. You will not write this code to generate code on the weekend, though ...

To understand what SSA looks like, you can try the LLVM compiler. On their website, they have a small "Try" widget that you can play with. You paste the C code into the window and you get something that is close to the SSA form.

A small example of what it looks like:

Let's take this integer square-root algorithm in C. (arbitrary example, I just took something simple but non-trivial):

 unsigned int isqrt32 (unsigned int value) { unsigned int g = 0; unsigned int bshift = 15; unsigned int b = 1<<bshift; do { unsigned int temp = (g+g+b)<<bshift; if (value >= temp) { g += b; value -= temp; } b>>=1; } while (bshift--); return g; } 

LLVM turns it into:

 define i32 @isqrt32(i32 %value) nounwind { entry: br label %bb bb: ; preds = %bb, %entry %indvar = phi i32 [ 0, %entry ], [ %indvar.next, %bb ] %b.0 = phi i32 [ 32768, %entry ], [ %tmp23, %bb ] %g.1 = phi i32 [ 0, %entry ], [ %g.0, %bb ] %value_addr.1 = phi i32 [ %value, %entry ], [ %value_addr.0, %bb ] %bshift.0 = sub i32 15, %indvar %tmp5 = shl i32 %g.1, 1 %tmp7 = add i32 %tmp5, %b.0 %tmp9 = shl i32 %tmp7, %bshift.0 %tmp12 = icmp ult i32 %value_addr.1, %tmp9 %tmp17 = select i1 %tmp12, i32 0, i32 %b.0 %g.0 = add i32 %tmp17, %g.1 %tmp20 = select i1 %tmp12, i32 0, i32 %tmp9 %value_addr.0 = sub i32 %value_addr.1, %tmp20 %tmp23 = lshr i32 %b.0, 1 %indvar.next = add i32 %indvar, 1 %exitcond = icmp eq i32 %indvar.next, 16 br i1 %exitcond, label %bb30, label %bb bb30: ; preds = %bb ret i32 %g.0 } 

I know that at first it looks awful. This is not even a pure SSA form. The more you read on this presentation, the more it will make sense. And you will also find out why this concept is so widely used today.

Encapsulating all the necessary information in a data structure is easy. In the end, you need to decide if you want to use enumerations or strings for the opcode code ect name.

Btw - I know that I did not give you a data structure, but a more formal, but practical language and advice on where to look further.

This is a very interesting and interesting area of ​​research.

Edit: And before I forget this: don't miss the built-in functions of .NET and Java. These words allow you to compile from bytecode or source code from a program and execute the result.

Cheers, Nils

---

Regarding your editing: how to execute binary with code:

The hint in your binary is OS and platform dependent. In short, you have an insider command cache, you may need to back up the data cache, and you may need to include execution rights in the memory area into which you entered the code.

In win32, this is relatively simple since clearing the command cache seems sufficient if you put your code in a heap.

You can use this stub to start:

 typedef void (* voidfunc) (void); void * generate_code (void) { // reserve some space unsigned char * buffer = (unsigned char *) malloc (1024); // write a single RET-instruction buffer[0] = 0xc3; return buffer; } int main (int argc, char **args) { // generate some code: voidfunc func = (voidfunc) generate_code(); // flush instruction cache: FlushInstructionCache(GetCurrentProcess(), func, 1024); // execute the code (it does nothing atm) func(); // free memory and exit. free (func); } 

Answer 2

I assume that you want the data structure to store some kind of instruction template, probably parsed from existing machine code, similarly:

 add r1, r2, <int> 

You will have an array of this structure, and you will perform some optimization on this array, possibly changing its size or creating a new one, and generate the appropriate machine code.

If your target machine uses variable-width instructions (for example, x86), you cannot determine the size of your array without actually ending up parsing the instructions from which you are building the array. Also, you cannot determine exactly how much buffer you need before generating all instructions from an optimized array. However, you can make a good mark.

Check out GNU Lightning . This may be helpful for you.

Answer 3

In 99% of cases, the difference in performance is negligible. The main advantage of classes is that the code created by OOP is better and more understandable than procedural code.

I'm not sure what language you are coding in - note that in C # the main difference between classes and structures is that structures are value types and classes are reference types. In this case, you may need to start with structs, but at the same time add behavior to them (constructor, methods).

Answer 4

Without discussing the technical value of optimizing your code, in C ++ code, choosing between a POD structure or a complete object is basically an encapsulation point.

Embedding the code will allow the compiler to optimize (or not) the used constructors / accessors. There will be no performance loss.

First install the constructor

If you are working with a C ++ compiler, create at least one constructor:

 struct asm_code { asm_code() : type(0), value(0), optimized(0) {} asm_code(int type_, int value_, int optimized_) : type(type_), value(value_), optimized(_optimized) {} int type; int value; int optimized; }; 

At least you will not have undefined structs in your code.

Is every combination of data possible?

Using the structure you use means that any type is possible, with any value and any optimized. For example, if I set type = 25, value = 1205 and optimized = -500, then this is Ok.

If you do not want the user to place random values ​​in your structure, add inline accessors:

 struct asm_code { int getType() { return type ; } void setType(int type_) { VERIFY_TYPE(type_) ; type = type_ ; } // Etc. private : int type; int value; int optimized; }; 

This will allow you to control what is installed inside your structure and debug your code more easily (or even check the execution time of the code)

Answer 5

After some reading, my conclusion is that generic lisp is best suited for this task. With lisp macros, I have tremendous power.