constant directive

Dave Hein

I don't understand the purpose for the constant directive.· Why shouldn't the Spin compiler automatically compute the value of a constant expression instead of requiring the constant directive to do it?· It will produce the same numeric result whether it is computed·at compile time or run time· -- it will just run slower if done at run time.

Mike Green

You're absolutely right. I suspect that CONSTANT() was added some time after the Spin code generator was finished and, rather than rewrite the code generator to include constant folding, CONSTANT() was added. I assume that there's a separate evaluator for constant expressions and CONSTANT() invokes it. Another complication is that constant expressions include floating point values which are evaluated as floating point.

Dave Hein

Mike,

Thanks for your response.· There also seems to be an error on page 148 of the Propeller manual.· It contains the following text in red:

CON
· _xinfreq = 4096000
· Reset = %00100000
· Initialize = %00010000
· WakeUp = Reset & Initialize

Here, WakeUp is still set to %00110000 at compile time, but it is now more obvious to future readers that the WakeUp symbol contains the binary codes for a Reset and an Initialize sequence for that particular application.

The expression Reset & Initialize actually has a value of zero.· Is there a list of errata for version 1.1 of the Propeller manual?

Dave

localroger

Automatic constant folding can get surprisingly complicated. The way you'd normally do it is to start by assuming a constant expression, then bail if you find something you can't evaluate and start over. Consider this:

x := 4 * 5 + 3 * y + 8 * 2

You start out with a constant so you get the * operator, another constant, good go go that's constant(20). Next operator is + which means you drop an order of precedence -- you put the 20 on the math stack (of the internal constant evaluator) and evaluate the next expression at multiply/div precedence. So you get 3, constant, good, times OOPS you can't use the constant evaluator. That's a var.

At this point if you bail to the start you lose the bona fide constant 4*5=20. But bailing back to the addition operation leaves you with a bit of a muddle; you need to write 20 to the runtime Spin math stack and go to the runtime interpreter, which converts spin to bytecode. So you'd need to write push 20, push 3, push y, do multiply, do add. Your next operation is add and you're in spin mode, so you get the next symbol. It's a constant, 8. What do you do with it? Write spin code to push the 8 or go back to constant mode to see what's next?

It's not impossible to make this work -- you might even see how to do it from what I just wrote, but it's VERY hard to debug. Whereas making us specify constant expressions takes all that complexity out of the proptool evaluator and gives that control to the programmer, who needs to be thinking about stuff like that anyway. Most interpreted languages don't provide a way to fold constant expressions at all; they just perform the operations at runtime. Usually you'd fold that yourself because you know 4*5 is always 20. But it might be useful for program readability to say something like bytespersector / directoryentrysize, where both of those are constants and you don't want a "magic number" making your code hard to understand. With the constant directive you can specify that single constant while leaving it clear where it came from, and letting the code self-adapt should you ever need to change one of the source values.

BradC

After re-reading what you wrote, and then having a look at the constant folding in bstc I had to go back and re-check it to make sure it gets the precedence right.

In this case, the folding is done almost at the bytecode level. The compiler compiles to an intermediate token for each operation, which is then assembled into bytecode. All bstc does is scan the tokens. It increments a counter every time it sees a constant, ignores operators and zeros the counter if it sees anything else. When the counter >= 2 it knows there is a constant expression that can be reduced. The precedence is handled by the math evaluator in the main compiler, so the constant folder does not have to worry about any of the finer details.

Here is your example above compiled straight out. Constant values in the listing are displayed in Hex.

2                       x := 4 * 5 + 3 * y + 8 * 2
Addr : 0018:          38 04  : Constant 1 Bytes - 04 
Addr : 001A:          38 05  : Constant 1 Bytes - 05 
Addr : 001C:             F4  : Math Op *     
Addr : 001D:          38 03  : Constant 1 Bytes - 03 
Addr : 001F:             68  : Variable Operation Local Offset - 2 Read
Addr : 0020:             F4  : Math Op *     
Addr : 0021:             EC  : Math Op +     
Addr : 0022:          38 08  : Constant 1 Bytes - 08 
Addr : 0024:          38 02  : Constant 1 Bytes - 02 
Addr : 0026:             F4  : Math Op *     
Addr : 0027:             EC  : Math Op +     
Addr : 0028:             65  : Variable Operation Local Offset - 1 Write
Addr : 0029:             32  : Return                                           

And with constants folded

2                       x := 4 * 5 + 3 * y + 8 * 2
Addr : 0018:          38 14  : Constant 1 Bytes - 14 
Addr : 001A:          38 03  : Constant 1 Bytes - 03 
Addr : 001C:             68  : Variable Operation Local Offset - 2 Read
Addr : 001D:             F4  : Math Op *     
Addr : 001E:             EC  : Math Op +     
Addr : 001F:          38 10  : Constant 1 Bytes - 10 
Addr : 0021:             EC  : Math Op +     
Addr : 0022:             65  : Variable Operation Local Offset - 1 Write
Addr : 0023:             32  : Return                                        

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Life may be "too short", but it's the longest thing we ever do.

localroger

Yeah Brad that is one of the ways -- actually one of the more elegant ways -- to handle that. Expression evaluators generally are kind of hard to wrap your head around, and constant folding kind of requires you to write an interpreter and a compiler that work in tandem. Do-able, and tight when you get it right, but get one little thing wrong and it blows up in your face.

BradC

localroger said...
Yeah Brad that is one of the ways -- actually one of the more elegant ways -- to handle that. Expression evaluators generally are kind of hard to wrap your head around, and constant folding kind of requires you to write an interpreter and a compiler that work in tandem. Do-able, and tight when you get it right, but get one little thing wrong and it blows up in your face.

Yep, I lost count of the complete rip-up and re-writes I went through when writing the bstc math evaluator. At least 6. I had plenty that worked, but would all give slightly different output than the Parallax evaluator, or fail in strange ways on odd corner cases.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Life may be "too short", but it's the longest thing we ever do.

Phil Pilgrim (PhiPi)

Actually, constant folding is not that difficult. All you need to do is associate a one-bit flag with each element on the compile stack that tells whether it's a constant or not. Then, when it comes time to emit code for an operation, if both operands are constants, perform the operation instead of emitting code for it, and push the constant result value back on the compile stack.

-Phil

Bill Henning

You are 100% correct!

This is why my PropellerBasic code generator is taking so long to get written/debugged; not only do I do constant folding, but I am also trying to generate near-optimal code in one pass, without a peep hole optimizer to back me up (yet).

To make it even more challenging, I am not even using an expression stack!

localroger said...
Automatic constant folding can get surprisingly complicated. The way you'd normally do it is to start by assuming a constant expression, then bail if you find something you can't evaluate and start over. Consider this:

x := 4 * 5 + 3 * y + 8 * 2

You start out with a constant so you get the * operator, another constant, good go go that's constant(20). Next operator is + which means you drop an order of precedence -- you put the 20 on the math stack (of the internal constant evaluator) and evaluate the next expression at multiply/div precedence. So you get 3, constant, good, times OOPS you can't use the constant evaluator. That's a var.

At this point if you bail to the start you lose the bona fide constant 4*5=20. But bailing back to the addition operation leaves you with a bit of a muddle; you need to write 20 to the runtime Spin math stack and go to the runtime interpreter, which converts spin to bytecode. So you'd need to write push 20, push 3, push y, do multiply, do add. Your next operation is add and you're in spin mode, so you get the next symbol. It's a constant, 8. What do you do with it? Write spin code to push the 8 or go back to constant mode to see what's next?

It's not impossible to make this work -- you might even see how to do it from what I just wrote, but it's VERY hard to debug. Whereas making us specify constant expressions takes all that complexity out of the proptool evaluator and gives that control to the programmer, who needs to be thinking about stuff like that anyway. Most interpreted languages don't provide a way to fold constant expressions at all; they just perform the operations at runtime. Usually you'd fold that yourself because you know 4*5 is always 20. But it might be useful for program readability to say something like bytespersector / directoryentrysize, where both of those are constants and you don't want a "magic number" making your code hard to understand. With the constant directive you can specify that single constant while leaving it clear where it came from, and letting the code self-adapt should you ever need to change one of the source values.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
www.mikronauts.com E-mail: mikronauts _at_ gmail _dot_ com 5.0" VGA LCD in stock!
Morpheusdual Prop SBC w/ 512KB kit $119.95, Mem+2MB memory IO board kit $89.95, both kits $189.95
Propteus and Proteus for Propeller prototyping 6.250MHz custom Crystals run Propellers at 100MHz
Las - Large model assembler Largos - upcoming nano operating system

Bill Henning

True.

It is a bit more complicated if you don't use a compile stack, and are handling not only constants, but byte / word / long / float / string variables, arrays (of basic types), and functions.

I actually have a long full of flags for each element, I think I currently use 9 flags.

Phil Pilgrim (PhiPi) said...
Actually, constant folding is not that difficult. All you need to do is associate a one-bit flag with each element on the compile stack that tells whether it's a constant or not. Then, when it comes time to emit code for an operation, if both operands are constants, perform the operation instead of emitting code for it, and push the constant result value back on the compile stack.

-Phil

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
www.mikronauts.com E-mail: mikronauts _at_ gmail _dot_ com 5.0" VGA LCD in stock!
Morpheusdual Prop SBC w/ 512KB kit $119.95, Mem+2MB memory IO board kit $89.95, both kits $189.95
Propteus and Proteus for Propeller prototyping 6.250MHz custom Crystals run Propellers at 100MHz
Las - Large model assembler Largos - upcoming nano operating system

mpark

The really hard part is going from
x := 4 * 5 + 3 * y + 8 * 2
through
x := 20 + 3 * y + 16
to
x := 36 + 3 * y

Phil Pilgrim (PhiPi)

Yup, commutativity is a b***h! You have to be careful with that, though. There may be overflow considerations, wherein too much optimization could run counter to the programmer's intent. I can't remember: is modulo multiplication commutative? What about with signed multiplies?

-Phil

Post Edited (Phil Pilgrim (PhiPi)) : 1/23/2010 2:55:28 AM GMT

BradC

mpark said...
The really hard part is going from
x := 4 * 5 + 3 * y + 8 * 2
through
x := 20 + 3 * y + 16
to
x := 36 + 3 * y

Ooooo. That's a challenge.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Life may be "too short", but it's the longest thing we ever do.

localroger

Yeah Brad, there are serious issues with that level of optimization -- some compilers do it, and it bites people in the posterior. Particularly when you are doing Prop CNT style long-integer wraparound math it might be important to do the operations in order so that you get a tiemout period right. A compiler can optimize that stuff right back into not working right.

Bill Henning

Well put.

And that is EXACTLY how the expression parser in PropellerBasic does it.

Here is the code generated for that, assuming a declaration of "LOCAL x,y" (and adding the peep hole optimizer)

MOV mula,#3
MOV mulb,y
call #MUL32
MOV x,mulr

Mind you, it will only be that clean once the peep hole optimizer is done. For now, it is uglier:

mov t0,y
mov mula,#3
mov mulb,t0
call #MUL32
mov x,mulr

The reason it can load mulb with the constant is because there is no need for a temp register for a small constant.

mpark said...
The really hard part is going from
x := 4 * 5 + 3 * y + 8 * 2
through
x := 20 + 3 * y + 16
to
x := 36 + 3 * y

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
www.mikronauts.com E-mail: mikronauts _at_ gmail _dot_ com 5.0" VGA LCD in stock!
Morpheus dual Prop SBC w/ 512KB kit $119.95, Mem+2MB memory/IO kit $89.95, both kits $189.95 SerPlug $9.95
Propteus and Proteus for Propeller prototyping 6.250MHz custom Crystals run Propellers at 100MHz
Las - Large model assembler Largos - upcoming nano operating system

BradC

Bill Henning said...
Well put.

And that is EXACTLY how the expression parser in PropellerBasic does it.

Here is the code generated for that, assuming a declaration of "LOCAL x,y" (and adding the peep hole optimizer)

MOV mula,#3
MOV mulb,y
call #MUL32
MOV x,mulr

Err.. I can see a simple multiply by 3 there, but where are the other constants in the equation?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Life may be "too short", but it's the longest thing we ever do.

Mike Green

It's relatively easy if you use a tree as the internal format of the expression. You can have n-ary operators like "+" and "*" so you can rearrange the operands in whatever way makes sense for efficiency. You can even convert subtraction of X to addition of -X or division by X to multiplication by 1/X.

Bill Henning

Oops!

Sorry, I forgot the rest. I checked the compiler, here is how it actually handles it:

x := 4 * 5 + 3 * y + 8 * 2

turns into

x := 20 + 3*y + 16

mov mula,#3
mov mulb,y
call #MUL32
mov t0,mulr
add t0,#20
add t0,#16
mov x,t0

It is smart enough to load the source registers for the multiply subroutine with the constant and variable directly without using temporaries as long as the arguments to the multiply are not sub-expressions in parenthases, then it would be uglier. Unfortunately it is not smart enough to combine the two constants as there is a higher priority non-constant op between them.

Later I will add optimization code for the case of multiplying by a small constant, in which case the output will change to

mov t0, y
add t0, y
add t0, y
add t0,#20
add t0,#16
mov x,t0

and the peep hole optimizer will turn that into

mov t0, y
add t0, y
add t0, y
add t0,#36
mov x,t0

which is pretty good code for x := 4 * 5 + 3 * y + 8 * 2

a human (or smarter peep hole optimizer) could only improve it to

mov x, y
add x, y
add x, y
add x, #36

BradC said...

Bill Henning said...
Well put.

And that is EXACTLY how the expression parser in PropellerBasic does it.

Here is the code generated for that, assuming a declaration of "LOCAL x,y" (and adding the peep hole optimizer)

MOV mula,#3
MOV mulb,y
call #MUL32
MOV x,mulr

Err.. I can see a simple multiply by 3 there, but where are the other constants in the equation?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
www.mikronauts.com E-mail: mikronauts _at_ gmail _dot_ com 5.0" VGA LCD in stock!
Morpheus dual Prop SBC w/ 512KB kit $119.95, Mem+2MB memory/IO kit $89.95, both kits $189.95 SerPlug $9.95
Propteus and Proteus for Propeller prototyping 6.250MHz custom Crystals run Propellers at 100MHz
Las - Large model assembler Largos - upcoming nano operating system

BradC

Mike Green said...
It's relatively easy if you use a tree as the internal format of the expression. You can have n-ary operators like "+" and "*" so you can rearrange the operands in whatever way makes sense for efficiency. You can even convert subtraction of X to addition of -X or division by X to multiplication by 1/X.

Yeah, I like the concept of a tree based evaluator. It's what I tried first as it just seemed so logical to me, but for the life of me I could *not* get it to generate bytecode like the Parallax compiler does. The code was perfectly valid, but just not identical.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Life may be "too short", but it's the longest thing we ever do.

Phil Pilgrim (PhiPi)

I remember Chip saying that he used recursive descent in his compiler.

-Phil

BradC

Phil Pilgrim (PhiPi) said...
I remember Chip saying that he used recursive descent in his compiler.

Well, that would make perfect sense. I ended up build a stack based evaluator which coincidentally happened to produce identical code to the Parallax compiler out of the box. Must have been a fluke, but it took lots of near misses to get there. Michael Park poked me in the direction of some articles on recursive descent after I asked him how he made homespun work.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Life may be "too short", but it's the longest thing we ever do.