Compiler for evaluating Boolean expressions4722071Abstract An intelligent compiler particularly useful for evaluating Boolean expressions such as those associated with ladder structures. True/false paths are defined through the expressions. In a first pass for the code generation, the start code for examining each element is set out. In a second pass the relative offsets for branching from one element to the next element along both the true and false paths are filled in. In practice, execution time for evaluating ladder structures is reduced by an order of magnitude over prior techniques which use source code and an interpreter. Claims We claim: Description BACKGROUND OF THE INVENTION
__________________________________________________________________________
CYCLES
__________________________________________________________________________
READ NEXT INSTRUCTlON SUBROUTINE
RNI CLRA 2
LDB O, Y ;GET OP CODE 4
ANDB #$FO 2
LSRB ;SHIFT RIGHT 3 BIT POSN
2
LSRB 2
LSRB 2
ADDD #PTRTBL
;ADD TO POINTER TABLE BASE
4
TFR D, X ;POINTER ADDRESS TO X
6
LDX X ;SUBROUTINE ADDRESS TO X
5
JSR X ;EXECUTE INSTRUCTION
7
LEAY 2, Y ;ADVANCE PROGRAM CTR.
6
RTS 5
47
EXAMINE ON SUBROUTINE
EXON00
TST RUNG ;RUNG STILL TRUE? 7
BEQ EXON03
;NO-QUIT 3
LDB L,Y ;WORD ADDRESS TO B 5
CLRA 2
ADDD #RMBASE
;ADD TO RAM BASE ADDRESS
4
TFR D,X ;RAM ADDRESS TO X 6
LDA X ;GET BYTE WITH DESIRED BIT
4
LDB #1 ;MASK BIT TO WORKING REG.
2
STB WR1 5
LDB Y ;GET BIT ADDRESS 4
ANDB #$0E ;MASK OUT OTHER BITS
2
LSRB ;RIGHT JUSTIFY 2
EXON01
DECB ;MASK SHIFTED ENOUGH?
2
BMI EXON02
;YES 3
LSL WR1 ;NO-SHIFT LEFT 7
BRA EXON01
;REPEAT TEST 3
EXON02
ANDA WR1 ;MASK OUT UNDESIRED BITS
5
BNE EXON03
;RUNG STILL TRUE 3
CLR RUNG ;RUNG NOW FALSE 7
EXON03
RTS 5
81
__________________________________________________________________________
Execution time of EXON is a function of the bit position of the desired bit, if the bit position is zero (right end of byte), 71 cycles are required; if the bit position is 7 (left end of byte), 176 cycles are required. Thus to summarize this prior art method, each element is examined and the cumulative logical result of each level is maintained to determine the rung's output. To increase the speed at which rungs are evaluated, faster processes are utilized. This prior art method has the advantage of requiring a minimum of instructions, that is, not much random access memory (RAM) is required to store the program since it is stored in source code. OVERVIEW OF COMPILER OF THE PRESENT INVENTION With the compiler of the present invention, intelligence or logic is built-in to the compiled program thereby shortening the processing time. A program for evaluating a rung is compiled into machine executable code. The actual operation to be performed and all necessary parameters are contained in each element in a machine executable form. This eliminates the need for retrieval of encoded elements and the need for decoding of encoded elements into operand and operational code. As will be seen, true and false paths or other condition determining paths are built-in such that the value of the rung is simply the value of the last element evaluated. This eliminates the combining steps and additionally enables an examination of only those elements whose values must be known to determine the value of a rung. Referring to FIG. 2, the first step in preparibg a program with the present invention is the preparation of a Boolean expression or statement for each rung as represented by block 20. Examples of such expressions are described later in the application in conjunction with FIG. 1. Next, these statements can be optimized or simplified to reduce the amount of compilation. Simple mathematical operations are used to optimize the expressions as will be described. This step is represented by clock 21 of FIG. 2. Now condition determining paths or control paths within the expressions are identified. For each element, the next element in the statement which determines the rung's output based on the condition of the current element is listed. For a Boolean expression, this requires the creation of true/false tables. These tables determine the branching used to shorten the computation time. This step is shown by block 22 in FIG. 2. In the presently preferred embodiment, two passes are used to generate the machine executable code. Skeletal code is prepared for each element in a first pass which includes instructions for the examination of each element. In a second pass, relative offsets to these next elements are included permitting the program to follow the paths. This is shown as blocks 23 and 24 in FIG. 2. CREATION AND SIMPLIFICATION OF BOOLEAN EXPRESSIONS Before describing the Boolean expressions, the formatting used in the presently preferred embodiment should be noted. Each rung is treated as having up to three levels and a single output. Each level may have up to five elements across. This particular formatting was chosen since it is convenient for video displays. Moreover, it permits the establishment of conventions for compiling, for instance, fixed word widths for offsets. Where a rung is larger than 3.times.5 elements, it is broken into several rungs and special instructions are used to permit the continuing evaluation of a larger rung represented by several 3.times.5 rungs. By way of example, a "dummy" action element is used to permit the breaking up of larger rungs. This dummy element is placed at the end of a "subrung" and is treated as an ordinary element in the continued representation of the rung. In this manner, rungs of any size can be examined conveniently on a video display. The Boolean expression for each rung is developed by maintaining independent expressions for each level of the rung (one column at a time) and by proceeding from left to right for the rungs shown in FIG. 1. The expressions for a level is the logical conjunction of its previous expression and the current element. The values of two levels connected together by a branch is the logical disjunction of the expressions for the two levels. These rules permit the mechanized creation of the Boolean expressions. Referring to FIG. 1, the Boolean expression for rung 10 is shown to the right of the rung. I0 and I2 being at different levels are ORed (disjunctive) which is represented by I0+I2. This term is conjunctively combined with I1 to produce the total expression for the rung. Similarly for rung 11 the independent expression for the first level is combined with I6. This term is then combined with I5 and finally, the last branch comprising I718 is disjunctively combined. The condition of the elements, of course, determines whether or not the output 02 will be on or off. The expression for a given rung is the expression of the top level at the end of the processing, that is, for the given format at the end of the fifth element. The expressions may be optimized for the invented method. Two forms of optimization are currently employed. Common terms may be factored. For instance, the expression ab+ac is converted to a(b+c). Also redundant parenthesis are removed. For instance, (a+(b+c) is converted to (a+b+c). PREPARING CONDITION DETERMINING PATHS The portion of the compilation represented by block 22 of FIG. 2 for the Boolean expressions consist of preparing a true/false table for the elements of the expression. The true path is determined such that if a current element has been determined to be true, other elements that are disjunctive from the element are ignored. In the expression a(b+c)d+e, the true path for the element b is element "d". The false path is determined by ignoring conjunctive elements when an element is false. For the expression a(b+c)d+e, the false path if element "a" is false is "e". In effect, for the element under consideration (current element) the next elements in the expression which can determine the output of the rung based on the state of this current element is identified. These next elements point the way along the condition determining paths. In FIG. 3, truth tables are set forth for the two expressions of FIG. 1 representing rungs 10 and 11. For example, for element I0, if this element is true, the disjunctive element I2 of the expression is ignored and the next element in the true path is I1. On the other hand, if I0 is false, there being no conjunctive element to ignore, the next element in the false path is the disjunctive element I2. Similarly, for I2 if the element is true, there being no disjunctive element to consider, the next element is I1. If I2 is false, the conjuctive element I1 is ignored and the rung itself is off, that is, false. if I1 is true, the rung itself is true and similarly, if it is false, the rung is off. The same logic when followed results in the table shown in FIG. 3 for rung 11. When a numeric value is to be ANDed with a logical value, true is evaluated as ffff(hex) while false is evaluated as a zero. The value of both levels connected together by a branch element is the logical disjunctive of the two levels. The value of the rung is the value at the end of the processing. If a rung has a numerical value and its execution level requires a logical value, non zero is evaluated as true, while zero is evaluated as false. As will be appreciated in the compiler itself, this step is easily implemented by testing for disjunctive and conjunctive terms and ignoring them for the true and false condition, respectively, and then identifying the next element for each of the paths. GENERATING CODE As mentioned, a two pass operation is used to generate the code. In the first pass, skeletal code (code with no operands) outlining the operation of each element is laid in place. All of the operands except the branches are filled in using the position of the elements operand in an input/output map. Then, for each element, the start of the code to execute the element and the position of the true and false branches to the next element for the current element's code are set out. In the second pass, each element's branches are resolved by determining the relative offset from the element's true/false path to the next element along the path. With the currently preferred formatting (i.e., 3.times.5 rungs), the following demonstrates these steps for rung 10 of FIG. 1. The ladder source is represented as follows:
______________________________________
1-0-0 1-0-1 . . . 2-1-0
1-0-2 0-0-0 . . . 0-0-0
0-0-0 0-0-0 . . . 0-0-0
______________________________________
Where the first digit of each triplet represents the operation (0 being equal to no operation, 1 to "examine" on, and 2 to energize). The second digit represents the input/output word and the third digit represents the bit position within the word. The skeletal code for this rung is sown in FIG. 4. Each of the instructions have been numbered for purposes of discussion. For element I0, the first instruction consists of loading register a with input word 0. Next, the bit 0 is tested with the immediate operand shown. The third instruction is a long branch if the bit is not equal (true condition for the test used). For element I0, the true path is a branch to I1 as may be seen from the first line of truth table for rung 10 (FIG. 3). On the second path, the relative offset to I1 is filled in for "xxxx" of instruction 3 since on the second pass the physical address for I1 will be determined. The fourth instruction is a long branch for the false path, that is, "xxxx" is replaced with the offset to I3. Similarly, the skeletal code for each element is developed as shown by instructions 1-12. Also shown in FIG. 4 is the code to energize the output element assuming, for instance, that it is a relay. As shown by instruction 130, the output word 1 is loaded into accumulator "a" and an ORring operation is used to test bit 0 and store the result in accumulator "a." Similarly, the instructions for a false rung (instructions 134-137) are set out in FIG. 4. While the above discussion is based on a Boolean example, other expressions where condition determining paths are defined may be used. For instance, where each element is tested for "greater than", "less than", or "equal to ", three branches from this element along three condition determining paths would be used. COMPILER FOR 6809 MICROPROCESSOR Tables 1 and 2 are a compiler developed in accordance with the present invention for the 6809 microprocessor. The conventions discussed above are used for the compiler. Table 1 performs the steps represented by blocks 20 through 22 of FIG. 2. This program is written in the C programming language for execution on a Z-80 board computer. Table 2 contains the program for blocks 23 and 24 of FIG. 2; this program is written in 6809 assembly language. OPERATION OF COMPILED PROGRAM Referring to FIG. 5a, the rung 11 of FIG. 1 is redrawn. If a program is prepared as described above for determining the output of this rung, the program first tests the condition of I1. Assume that this input is true, then the offset for the LBNE instruction would next result in the examination of element I4 as indicated by line 27. If I4 is also true, the next element examined is I5 as indicated by line 28. Note with the program I6 is not examined since its condition will not effect the output of the rung if I1 and I4 are both true. Now if I5 is false, there is an offset to element I7 (line 30) and if that element is true, I8 is next examined. Finally, if I8 is true, the rung is true. If element I5 had been true, it would immediately be known that the rung is true as indicated by line 32 and no examination would occur of elements as indicated by line 32 and no examination would occur of elements I6, I7 or I8. In FIG. 5b, rung 11 of FIG. 1 is again shown to provide additional examples. If I1 is false, there is an immediate branch to element I6. Element I4 is not examined since its condition cannot affect the output as long as I1 is false. Both the true path and false path from I6 are shown as lines 34 and 35, respectively. If I6 is true, I5 is next examined. If I5 is true, the rung is true. If I5 is false, the false path from I5 is shown in FIG. 5a as line 30. This leads to element I7. If I7 is false, the rung is false, and I8 is not examined. If I7 is true, then I8 is examined and its condition will determine the output of the rung. It is important to note that in addition to not examining elements not effecting the output for given conditions, no cumulative rung condition is maintained. Rather, the last element examined determines the rung's condition. COMPARISON WITH PRIOR ART TECHNIQUE It is difficult to provide an exact comparison between the prior art technique for evaluating a ladder structure and that taught by the present invention. With the present invention, the number of instructions which are executed to evaluate a rung is not a constant as can be seen from FIGS. 5a and 5b. However, in general, it has been found that a speed increase of an order of magnitude is realized for complex rungs. The subroutines set forth earlier for "read next instruction" and "examine on" show the number of cycles required to perform these functions. It will be appreciated that by eliminating the need to examine all of the elements in the rung, considerable time saving is achieved. Thus, by using the invented compiler faster determinations are made, or prior art execution speeds can be matched with less sophisticated processors. The present invention also permits the handling of more complex ladders with less computer "hardward". It should be noted that with the present invention more RAM storage is needed to store the object code program which results from the compiling. This is considered to be a worthwhile tradeoff since RAM is relatively inexpensive. COMPUTER FOR EXECUTING PROGRAM PREPARED IN ACCORDANCE WITH THE PRESENT INVENTION While any one of a plurality of microprocessors may be used for executing a program compiled with the present invention, particularly fast execution speed can be obtained with the architecture of FIG. 6. A host computer 50 provides control functions for the invented computer. The host may include input/output means for examining the conditions of the elements and energizing coils. The host may also load the compiled program into memory 51 and provide control signals for the invented computer through the timing means 72. The invented computer includes an instruction memory, RAM 51. Object code instructions using the compiler described above are stored in memory 51 in a format which will be described below. In the presently preferred embodiment, RAM 51 is organized as a 16K.times.48 bit memory, each instruction being 48 bits wide. All addresses, input data and read/write signals are applied to memory 51 through the dual port means 52. The dual port means 52 communicates with the host computer 50 through the buses 64 and 65 and the read/write lines 66. These buses and lines are also coupled to a dual port means 54. This means communicates with a second memory, the map RAM 57. In the presently preferred embodiment, RAM 57 is organized as a 2K.times.16 memory. Each instruction within memory 51 includes two 14 bit address fields. These address fields are coupled to a multiplexer 60. The output of the multiplexer 60 is coupled through a latch 61 and along bus 62 to provide an address for memory 51. An output from the arithmetic unit 58 controls the selection made by the multiplexer 60. Eleven bits of each instruction identified as "M" are coupled through bus 70 to the dual port means 54. These bits provide an address for addressing data within the RAM 57. Nine bits from the RAM 51 along bus 71 are coupled to the dual port memory 54, accumulator 55 and arithmetic unit 58. An arithmetic unit 58 which may, for instance, be an ordinary ALU such as a 29116, receives a first field (operand 1) from accumulator 55 and a second field from RAM 57 (operand 2). The output of this arithmetic unit is coupled to the dual port means 54. The entire memory of FIG. 6 may be fabricated using well-known, commerically available components. Each instruction stored within the memory 51 is prepared, as mentioned, using the compiler described above. Each instruction includes 48 bits divided into four fields: FCN, 9 bits (function); M, 11 bits (memory address for RAM 57); address 1, 14 bits (branch address for true path); and, address 2, 14 bits (branch address for false path). The MUX 61 is in fact controlled by a flag. Address 1 is selected if the flag is set while address 2 is selected if the flag is not set. The functions, their description and the setting of this flag are set forth below:
__________________________________________________________________________
Fcn Function
Description
Flag
__________________________________________________________________________
00000XXXX
NOP No Operation
00001XXXX
CLR 0 .fwdarw. M
Set if M originally <> 0
00010aaaa
LDA (M) .fwdarw. A
Set if (M) <> 0
0011aaaa
STA A .fwdarw. M
Set if A <> 0
00100aaaa
AND (M) and A .fwdarw. M
Set if Result <> 0
00101aaaa
OR (M) or A .fwdarw. M
Set if Result <> 0
00110aaaa
XOR (M) xor A .fwdarw. M
Set if Result <> 0
00111XXXX
INC (M) + 1 .fwdarw. M
Set if Overflow
01000XXXX
DEC (M) - 1 .fwdarw. M
Set if Underflow
01001aaaa
ADD (M) + 1 .fwdarw. M
Set if Overflow
01010aaaa
MUL (M) * A .fwdarw. M
Set if Overflow (x8x) MUL)
01011XXXX
TST Test Word in (M)
Set if (M) <> 0
01100aaaa
CMP Compare (M) to A
Set if (M) > A
10000bbbb
AND B And Bit B in (M)
Set if B originally set
10001bbbb
OR B Or Bit B in (M)
Set if B originally set
10010bbbb
XOR B Xor Bit B in (M)
Set if B originally set
10011bbbb
TST B Test Bit B in (M)
Set if B set
11111XXXX
HALT
__________________________________________________________________________
aaaa = binary code of accumulator (one of sixteen)
bbbb = position of Bit B (one of sixteen)
XXXX = "don't care
In operation, as mentioned, the host computer 50 loads the compile object code program into the RAM 51. In the beginning of each scan cycle, the host updates the input status portion of RAM 57 through the dual port means 54. On signal from the host computer 50, the program in RAM 51 is executed. The timing means 72 monitors the function codes on bus 72 to generate a finish signal for the host computer. Each instruction causes the execution of an arithmetic or logic function with one or two operands (one from accumulator 55 and the other from RAM 57) and for some instructions replaces the result into the accumulator 55, thus, permitting the result to be used as one of the operands. Each instruction includes the two branch addresses needed to access the next element, one along the true path and the other along the false path. Consider the following example:
______________________________________
Fcn M Addr1 Addr2
______________________________________
001000001
00000000010
0000000000000100
00000000001000
______________________________________
The Fcn code specifies an AND operation between the contents of address 00000000010 of the RAM 54 and accumulator 55 contents 0001. If the result of the AND operation is non-zero then address 1 contains the next instruction executed; otherwise, address 2 contains the next instruction. It is apparent from the above that the invented computer performs in parallel the operations performed serially for code such as shown in FIG. 4. The speed of execution then becomes limited only by the access time particularly for the RAM 51. Thus, a method for compiling a program which is particularly useful for evaluating a ladder structure has been described. Conditioning determined paths such as true/false paths are identified through the expressions and determine the branching for the object code program. Also described is a high speed special purpose processor optimized for executing the object code compiled in accordance with the present invention. ##SPC1##
|
Same subclass Same class Consider this |
||||||||||