State Machine Compiler

Go To Last Post
28 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

My application uses several communications interfaces (I2C, CAN, USART) which are all implemented using some level of state machine.  In addition, the application objects lend themselves to being implemented using State Machines (they all respond to external stimulus). 

 

Up to now I have hand-coded these SMs using traditional methods (switch statements, etc.) but my application has outgrown this and I am looking for a richer State Machine environment* such as that provided by "SMC" (State Machine Compiler, Source Forge) but I fear I may be in for a steep learning curve and I do not know if SMC is suitable for the GCC/AVRMega environment (I use AVRMega1284P processors).

 

* some things I am looking for: "guard" functions, multiple actions per state, internal and external events, nested state machines, etc.

 

In a past life I wrote a State Machine compiler using yacc/lex along with an execution engine but I'm not anxious to re-do that effort.

 

Ideal would be something that also supports a graphical description of the state machine, produces a graphical document describing the SM, produces C++ code suitable for targeting to AVR processors, and supports state tracing, etc. for debugging on the target.

 

Any suggestions?

 

Regards,

 

Chuck Hackett
 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ChuckH wrote:
... but I fear I may be in for a steep learning curve and I do not know if SMC is suitable for the GCC/AVRMega environment (I use AVRMega1284P processors)
Fear not!

  1. Search this forum for Ragel (AMAZING!)
  2. Quantum Platform (QP) and QM (QP Modeler); http://www.state-machine.com/index.php

 For an OOTB experience, both of those can likely or will target Arduino and/or Arduino IDE.

mega1284P and QP - OOTB is STK600-ATMEGA2560 and Atmel Studio 6; STK500 might work with a bit of effort.

"Dare to be naïve." - Buckminster Fuller

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks much - I'll check them out.  One thing I want to be sure of is that, if I convert the code to use third-party software, is that I either have the source or it will be around for awhile as I don't want to go through this again or hamstring whoever inherits this.   :-)

 

Chuck

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Why not just organize your SM code to be resuable in your future projects... C/C++, maybe a class. So you can have several concurrent SMs.

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ChuckH wrote:
... if I convert the code to use third-party software, is that I either have the source or it will be around for awhile ...
Good point.

Definitely more tools than these that are immediate to my mind.

awhile - lots of PC software can still run on late-ish or the latest Microsoft Windows; make certain you have a durable backup of the tool.

There's a number of emulators of old operating systems.

An example are old and well used CPLD tools that ran on DOS; ABEL being one of many.

If a tool works reasonably on Wine then you're likely good to go.

"Dare to be naïve." - Buckminster Fuller

Last Edited: Sun. Oct 12, 2014 - 07:46 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Small note about switch statements....

 

While switch statements are easy to use, and are used everywhere on larger platforms (i.e. Windows code), there was a paper written a few years back that did a study on the efficiency of switch statements and how they were compiled by GCC (this paper was presented at one of the GCC Summit conferences that I went to). The author of the paper also tested the AVR GCC compiler as a comparison to see how it compiled switch statements. Come to find out, it wasn't very efficient at all, and was very dependent on the coding of the switch statement itself. This means that the underlying assembly implementation of the switch statement could change dramatically depending on the data used, the number of cases, etc., even just modifying the table. The compilation is controlled by a set of heuristics, that are not particularly tuned for the underlying device. After seeing that paper, I highly recommend to everyone that I talk to that they never code a switch statement in an embedded system and the AVR specifically.

 

The research showed that the best way was to write code that does not depend on compiler heuristics, for example, code it instead as a dispatch table (i.e. table of pointers to functions), preferably with a table index that is contiguous (i.e. no holes). It will execute the fastest, and has no difference in execution time based on the individual case.

 

My 2 cents.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Got a link to the paper?

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience.  Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast.  Cheap.  Good.  Pick two."

"We see a lot of arses on handlebars around here." - [J Ekdahl]

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

joeymorin wrote:

Got a link to the paper?

 

I don't off-hand. I'll have to do some digging....

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

EW wrote:

 

joeymorin wrote:

 

Got a link to the paper?

 

 

 

I don't off-hand. I'll have to do some digging....

 

Ok, I think this was the paper:

http://www.nextmovesoftware.com/...

 

I know that it from the GCC Summit, and the author / presenter is Roger Sayle. I spoke with him quite a bit that evening after he presented. Just because it was unusual for one of the GCC developers to do any research with the AVR. 

 

IIRC, the paper doesn't really have the information that he gave in the presentation. He had a number of slides showing the test results of GCC compiling all these different kinds of switch statements on a number of platforms. Of course x86 was one of those platforms. He threw in the AVR as one of those outliers showing exactly how bad the compilation was. What this showed was that switch statement heuristics in GCC were really best tuned for the x86, of course. They weren't exactly perfect, but he showed how these tunings were out of line for other platforms. And also how difficult it is to have different tunings for different target back-ends.

 

All of this was an eye-opener to me when I first saw it. It boils down to the fact that switch statements should not be written for embedded systems for the sheer fact that you are relying on an imperfect compiler to decide how it's going to be implemented. It is way better to use a coding structure where you know how the compiler will implement it. It gives you back the control on the implementation of the code. If I want the compiler to implement a series of if-else-if structures, then I will code it that way in C. If I want the compiler to implement a dispatch table, then I will code it that way in C. If I want the compiler to use some funky hash structure, then I would rather code it that way myself in C. I would much rather know what's going on inside my code in an embedded system with limited resources, than to just give over that control to unknown heuristics (i.e. wild ass guesses) in a program.

 

YMMV.

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

After seeing that paper, I highly recommend to everyone that I talk to that they never code a switch statement in an embedded system and the AVR specifically.

 

First--I haven't seen you post for awhile.  Good to [not--based on avatar] see you again.

 

Next:  LOL.  "AVR specifically"?  Sheesh.  Alternatives?  (yes, I see that you proposed one; more on that later)

 

I tend to use switch() in AVR8 apps.  For my eye, after the first couple of if/elseif I find it easier to read and modify later when I use a switch.

 

Small switch() is probably implemented as if/elseif anyway.  Maybe a microsecond more for the setup.  There is also the benefit of default: for robustness.

 

Now, your recommendation of a dispatch table.  And then you want to make it non-sparse as well!  Sure, that might be most efficient.  In the real world, these cases aren't always that conveniently laid out.

 

There are AVR apps, and then there are AVR apps.  Most of you think "big iron".  I think "Mega88-class".  You've seen my posted heretical beliefs before.  Not quite 95 points:

 

--  Use a flat program structure.  Only use subroutines when they make sense.  Generally a huge main().

--  Few if any local variables.

--  Global scratchpad register variables, and use the heck out of them.

 

The result is a tight and fast app.  Bye-bye function dispatch table...

 

I lost in the thread why switch() is being questioned.  If my main loop, or dispatch functionality, takes two microseconds more I probably don't care.  If the state machine compiler wants to make switch() then let it.

 

Two words:  "Duff's device".  I thought that was the best way to do some operations.  And you can do better without switch()?

 

All of the above IME/IMO.  FWIW, I've done scores of Mega88-class production AVR8 apps.

 

Indeed, once I get into "big iron" apps, say Mega64 and larger, I introduce more structure into the app.  Also, IME/IMO more structure is better when the programming team size is greater than one.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you really want to control conditional code, you have to use asm.

I have yet to find a version of avr-gcc that will optimally compile:

if (val && 1 == 1)
    PORTB = 0;
else
    PORTD = 0;

with optimal being sbrc, out, sbrs, out.

 

I have no special talents.  I am only passionately curious. - Albert Einstein

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Maybe my brain is sub optimal this morning, but what, exactly, is

if (val && 1 == 1)

supposed to do? If == takes precedence over && then aren't you effectively saying

if(val)

??

 

As I say, maybe I'm being thick today.

Four legs good, two legs bad, three legs stable.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I do try to organize my code so that it is reusable but, in this case, I am looking for a tool that provides added features such as a graphical too to design and document State Machines.

 

Chuck

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

gchapman wrote:

 

Quantum Platform (QP) and QM (QP Modeler); http://www.state-machine.com/index.php

 

(I apologize if the above quote does not come out right - it's my first try quoting with this forum)

 

Status Update: 

 

I contacted the Quantum Leaps (maker of QM/QP) and explaining that I wanted to use QM/QP for my project.

 

The 'free' version of their license requires that the project source code be made available to purchasers of the product.  The 'commercial' (fee) license removes this restriction.

 

I explained that my project (ATMega1284p based, custom PCB, automatic railroad signal system) is for my hobby (7.5" gauge live steam ride-on railroad).  The system is currently installed at our club track in Florida and one other railroad that has purchased the components from me.

 

I explained to Quantum Leaps that:

  • I do charge for the signal controllers but I do not distribute the source code (this would violate their 'free' license)
  • I have arranged for the source to become 'public domain' if something were to happen to me.
  • What I charge for the controllers basically just covers my cost in them.  This is not a large hobby and I do not have expectations that this will ever be a 'for profit' activity
  • The revenue would not justify even the lowest level of their 'commercial' license.

 

I received a very nice reply from Miro Samek containing an application for a 'free' commercial license which allows me to use their product free of charge for named 'single products' (I have two).  This allows me to use QM/QP and continue to sell the boards and not release the source.

 

I have ordered his book:

 

Practical UML Statecharts in C/C++: Event-Driven Programming for Embedded Systems by Miro Samek

 

which describes Qm/QP in detail.

 

I cannot yet say how good the product is, but I'm going to give it a try.

 

So, if you are looking for something like QM/QP to streamline the generation, support, and maintenance of state driven code you might want to take a look at it.  (I have no connection with Quantum Leaps other than a user/customer).

 

BTW: The free (non-commercial) license DOES let you sell Arduino based products without releasing your source.

 

I'll try to remember to report back on my experience with QM/QP.

 

Regards,

 

Chuck Hackett

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

John_A_Brown wrote:
Maybe my brain is sub optimal this morning, but what, exactly, is

if (val && 1 == 1)

supposed to do? If == takes precedence over && then aren't you effectively saying

if(val)

??

 

As I say, maybe I'm being thick today.

Actually he's saying:

if (val && (1 == 1))

... which is the same as:

if (val && 1)

... which is what probably what was intended, but only by chance.

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience.  Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast.  Cheap.  Good.  Pick two."

"We see a lot of arses on handlebars around here." - [J Ekdahl]

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thank you for the AVR GCC insight.

EW wrote:
The research showed that the best way was to write code that does not depend on compiler heuristics, for example, code it instead as a dispatch table (i.e. table of pointers to functions), preferably with a table index that is contiguous (i.e. no holes). It will execute the fastest, and has no difference in execution time based on the individual case.
Have used dispatch tables but these can be difficult to maintain.

My usage was by manual conversion from FSMs into dispatch tables.

A tool that converts FSMs into dispatch tables would be useful.

One is trading cyclomatic complexity for data complexity; the complexity is still there.

Static source code analyzers may not be useful for a dispatch table; some source code analyzers can identify subtle defects.

 

"Dare to be naïve." - Buckminster Fuller

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ChuckH wrote:

  • I have arranged for the source to become 'public domain' if something were to happen to me.

Thank you.

Received a project (approx. year 1999) sometime after its creator had passed on.

ChuckH wrote:
BTW: The free (non-commercial) license DOES let you sell Arduino based products without releasing your source.

http://www.state-machine.com/licensing/QP-Arduino_GPL_Exception.txt

Mouser Electronics

Bench Talk

Make Your Own Job with Open Source Hardware: What Students Don’t Know

August 27, 2014 in Open Source

by Lynnette Reese
http://www.mouser.com/blog/make-your-own-job-with-open-source-hardware-what-students-dont-know

"Dare to be naïve." - Buckminster Fuller

Last Edited: Fri. Oct 17, 2014 - 01:49 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have yet to find a version of avr-gcc that will optimally compile:

if (val && 1 == 1)

;)  I guess I wouldn't worry about SBRC with that source.   Always true, isn't it?

 

with optimal being sbrc, out, sbrs, out.

 

Interesting.  I recall a thread discussing conditionally setting/clearing an I/O bit, and SBRC/SBI/SBRS/CBI wasn't too bad on an AVR8. 

 

Also, you indeed are working in GCC land, right?, counting on the zero-register?

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

;)  I guess I wouldn't worry about SBRC with that source.   Always true, isn't it?

Is it? I thought that the 1 == 1 part evaluates to true, so the logical and of true and val will be true if val if non-zero, and false otherwise. That's how I'd interpret it, but then I'm not a compiler.

 

Four legs good, two legs bad, three legs stable.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I think he meant:

if ((val & 1) == 1))

But I may be wrong. It happened once before in 1967

 

Four legs good, two legs bad, three legs stable.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I thought that the 1 == 1 part evaluates to true, so the logical and of true and val will be true if val if non-zero, and false otherwise. That's how I'd interpret it, but then I'm not a compiler.

+1

 

so equivalent "if (val)" as you said above.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ralphd wrote:

If you really want to control conditional code, you have to use asm.

I have yet to find a version of avr-gcc that will optimally compile:

if (val && 1 == 1)
    PORTB = 0;
else
    PORTD = 0;

with optimal being sbrc, out, sbrs, out.

 

I suspect "(val & 1) == 1" was meant for the conditional expression.

It is the same as "val & 1".

Moderation in all things. -- ancient proverb

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yup.  My mistake. Brain saw bitwise '&' instead of logical '&&' :(

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience.  Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast.  Cheap.  Good.  Pick two."

"We see a lot of arses on handlebars around here." - [J Ekdahl]

 

Last Edited: Fri. Oct 17, 2014 - 05:26 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have yet to find a version of avr-gcc that will optimally compile:

if (val && 1 == 1)
    PORTB = 0;
else
    PORTD = 0;

with optimal being sbrc, out, sbrs, out.

As you got me curious, I had to try it with CodeVision.  I had to manufacture my own zero-register.  The below sequence is the only one I could find to be "optimal" ;)

 

                 ;0000 000E 
                 ;0000 000F if ((frog & 1)) PORTD = dog;
                 _0x4:
000045 fd10      	SBRC R17,0
000046 b90b      	OUT  0xB,R16
                 ;0000 0010 if ((frog & 1) == 0) PORTB = dog;
000047 ff10      	SBRS R17,0
000048 b905      	OUT  0x5,R16

 

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

skeeve wrote:

 

ralphd wrote:

 

If you really want to control conditional code, you have to use asm.

I have yet to find a version of avr-gcc that will optimally compile:

if (val && 1 == 1)
    PORTB = 0;
else
    PORTD = 0;

with optimal being sbrc, out, sbrs, out.

 

 

I suspect "(val & 1) == 1" was meant for the conditional expression.

 

It is the same as "val & 1".

Which is exactly what I said, a few posts earlier.

 

Four legs good, two legs bad, three legs stable.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ChuckH wrote:
Ideal would be something that also supports a graphical description of the state machine, produces a graphical document describing the SM, ...

fwprofile

C Implementation of UML State Machines and Activity Diagrams for Safety-Critical, Real-Time and Embedded Applications

...

Is a GUI-Based Tool Available for the C1 Implementation?

Use of the C1 Implementation is straightforward and a GUI-based tool is hardly necessary. For convenience, a web application is provided which allows user to create state machine diagrams graphically and to generate their implementation code automatically. The web application is accessible from the FW Profile web site.

https://code.google.com/p/fwprofile/wiki/FAQs#Is_a_GUI-Based_Tool_Available_for_the_C1_Implementation?

"Dare to be naïve." - Buckminster Fuller

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ChuckH wrote:
Ideal would be something that also supports a graphical description of the state machine, produces a graphical document describing the SM, produces C++ code suitable for targeting to AVR processors, and ...
A suite of products from MathWorks would take it to code for an AVR.

Alternatively, AdaCore QGen can generate C or Ada for an emulated MCU by QEMU (not AVR); this is forthcoming 2015-June for state machines created via MathWorks Stateflow.


MathWorks

State Machine - Stateflow - Simulink

http://www.mathworks.com/products/stateflow/

MathWorks

Atmel Support from Embedded Coder - Hardware Support

http://www.mathworks.com/hardware-support/atmel.html

Home » Touchless 3Dpad gets a Matlab update

http://blog.atmel.com/2014/06/25/touchless-3dpad-gets-a-matlab-update/

AdaCore

Home / Products / QGen / FAQ

https://www.adacore.com/qgen/faq

...

When will support for Stateflow® models be available?

In version 1.0.2 planned for June 2015.

Edit : added third URL.

"Dare to be naïve." - Buckminster Fuller

Last Edited: Sat. Mar 7, 2015 - 03:44 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

 

IAR has a state machine SDK and support tools.

https://www.iar.com/iar-embedded...

 

I've not needed such - state machines I've coded are simple run to completion.

Multiple state machines on one MCU.

 

Avoiding an RTOS.