flat assembler
Message board for the users of flat assembler.

 Index > Main > Convert text to SSE2 code ! Breaking your brain :) Goto page Previous  1, 2
Author
Roman

Joined: 21 Apr 2012
Posts: 1718
Roman 26 Jul 2013, 07:37
Phew.
Finally, I was able to correctly break the example for operations !

If we write 5+4/(8*2+4*2/2+3*9/7)+11
My parser break this example like this:
4/(8*2+4*2/2+3*9/7)+5+11

If we write 5*4+(8*2+4*2/2+3*9/7)+11
My parser break this example like this:
5*4+8*2+4*2/2+3*9/7+11

If we write 5+4+(8*2+4*2/2+3*9/7)+11
My parser break this example like this:
8*2+4*2/2+3*9/7+5+4+11

Quote:
A feast for the brain
Do this parser
26 Jul 2013, 07:37
tthsqe

Joined: 20 May 2009
Posts: 767
tthsqe 27 Jul 2013, 05:52
Here is what I am talking about:

First, we define a function RegCount which gives the minimum number of registers necessary to evaluate an expression. It can be calculated by calling the following function on the root of the tree.
Code:
```RegCount(node x):
if x.ChildCount = 0,                ; if we are at a leaf number
x.RegCount = 1,                   ;   then we need 1 register to load this number
else
call RegCount on all of the children of x and put the results into a list S;
sort S in decreasing order;
for 0 <= i < x.ChildCount, do S[i] += i;
x.RegCount = max(S)
end if
return x.RegCount    ```

If you call this on the root, then the RegCount member of each node will be filled in.
Now, when you are generating code, start at the root and handle the children in decreasing order of their RegCount member. This will insure that the minimum number of registers is used.
In the parsing phase, operators with more than 2 operands should should be left associated into binary operators, since we can't operate on more than two numbers at a time in x86.
EX: 2+2/(1+4*4)/17
Code:
```Tree:                        '+'
/ \
/   \
'2'   '/'
/ | \
/  |  \
/   |   \
'2'   |   '17'
'+'
/ \
/   \
/     \
'1'     '*'
/ \
/   \
/     \
'4'     '4'

RegCount:                     3
/ \
/   \
1     3
/ | \
/  |  \
/   |   \
1    |    1
2
/ \
/   \
/     \
1       2
/ \
/   \
/     \
1       1

RegAlloc:                    x1
/ \
/   \
x2    x1
/ | \
/  |  \
/   |   \
x2    |   x3
x1
/ \
/   \
/     \
x2      x1
/ \
/   \
/     \
x1      x2

Code:
x1 = 4
x2 = 4
x1 = x1 * x2
x2 = 1
x1 = x2 + x1
x2 = 2
x3 = 17
x1 = x2 / x1 / x3
x2 = 2
x1 = x2 + x1    ```
27 Jul 2013, 05:52
pabloreda

Joined: 24 Jan 2007
Posts: 115
Location: Argentina
pabloreda 29 Jul 2013, 12:28
Roman:
if you have the expresion in postfix notation is the same of forth notation.
an optimiced forth compile try to hold in registers the cells on stack. it's all.
operations between constant numbers in the tree not have sense, first evaluate and then compile.
29 Jul 2013, 12:28
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page Previous  1, 2

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum