1------------------------------------------------------------------------------ 2-- -- 3-- GNAT COMPILER COMPONENTS -- 4-- -- 5-- E X P _ P A K D -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 1992-2010, Free Software Foundation, Inc. -- 10-- -- 11-- GNAT is free software; you can redistribute it and/or modify it under -- 12-- terms of the GNU General Public License as published by the Free Soft- -- 13-- ware Foundation; either version 3, or (at your option) any later ver- -- 14-- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- 15-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- 16-- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -- 17-- for more details. You should have received a copy of the GNU General -- 18-- Public License distributed with GNAT; see file COPYING3. If not, go to -- 19-- http://www.gnu.org/licenses for a complete copy of the license. -- 20-- -- 21-- GNAT was originally developed by the GNAT team at New York University. -- 22-- Extensive contributions were provided by Ada Core Technologies Inc. -- 23-- -- 24------------------------------------------------------------------------------ 25 26-- Expand routines for manipulation of packed arrays 27 28with Types; use Types; 29 30package Exp_Pakd is 31 32 ------------------------------------- 33 -- Implementation of Packed Arrays -- 34 ------------------------------------- 35 36 -- When a packed array (sub)type is frozen, we create a corresponding 37 -- type that will be used to hold the bits of the packed value, and 38 -- store the entity for this type in the Packed_Array_Type field of the 39 -- E_Array_Type or E_Array_Subtype entity for the packed array. 40 41 -- This packed array type has the name xxxPn, where xxx is the name 42 -- of the packed type, and n is the component size. The expanded 43 -- declaration declares a type that is one of the following: 44 45 -- For an unconstrained array with component size 1,2,4 or any other 46 -- odd component size. These are the cases in which we do not need 47 -- to align the underlying array. 48 49 -- type xxxPn is new Packed_Bytes1; 50 51 -- For an unconstrained array with component size that is divisible 52 -- by 2, but not divisible by 4 (other than 2 itself). These are the 53 -- cases in which we can generate better code if the underlying array 54 -- is 2-byte aligned (see System.Pack_14 in file s-pack14 for example). 55 56 -- type xxxPn is new Packed_Bytes2; 57 58 -- For an unconstrained array with component size that is divisible 59 -- by 4, other than powers of 2 (which either come under the 1,2,4 60 -- exception above, or are not packed at all). These are cases where 61 -- we can generate better code if the underlying array is 4-byte 62 -- aligned (see System.Pack_20 in file s-pack20 for example). 63 64 -- type xxxPn is new Packed_Bytes4; 65 66 -- For a constrained array with a static index type where the number 67 -- of bits does not exceed the size of Unsigned: 68 69 -- type xxxPn is new Unsigned range 0 .. 2 ** nbits - 1; 70 71 -- For a constrained array with a static index type where the number 72 -- of bits is greater than the size of Unsigned, but does not exceed 73 -- the size of Long_Long_Unsigned: 74 75 -- type xxxPn is new Long_Long_Unsigned range 0 .. 2 ** nbits - 1; 76 77 -- For all other constrained arrays, we use one of 78 79 -- type xxxPn is new Packed_Bytes1 (0 .. m); 80 -- type xxxPn is new Packed_Bytes2 (0 .. m); 81 -- type xxxPn is new Packed_Bytes4 (0 .. m); 82 83 -- where m is calculated (from the length of the original packed array) 84 -- to hold the required number of bits, and the choice of the particular 85 -- Packed_Bytes{1,2,4} type is made on the basis of alignment needs as 86 -- described above for the unconstrained case. 87 88 -- When a variable of packed array type is allocated, gigi will allocate 89 -- the amount of space indicated by the corresponding packed array type. 90 -- However, we do NOT attempt to rewrite the types of any references or 91 -- to retype the variable itself, since this would cause all kinds of 92 -- semantic problems in the front end (remember that expansion proceeds 93 -- at the same time as analysis). 94 95 -- For an indexed reference to a packed array, we simply convert the 96 -- reference to the appropriate equivalent reference to the object 97 -- of the packed array type (using unchecked conversion). 98 99 -- In some cases (for internally generated types, and for the subtypes 100 -- for record fields that depend on a discriminant), the corresponding 101 -- packed type cannot be easily generated in advance. In these cases, 102 -- we generate the required subtype on the fly at the reference point. 103 104 -- For the modular case, any unused bits are initialized to zero, and 105 -- all operations maintain these bits as zero (where necessary all 106 -- unchecked conversions from corresponding array values require 107 -- these bits to be clear, which is done automatically by gigi). 108 109 -- For the array cases, there can be unused bits in the last byte, and 110 -- these are neither initialized, nor treated specially in operations 111 -- (i.e. it is allowable for these bits to be clobbered, e.g. by not). 112 113 --------------------------- 114 -- Endian Considerations -- 115 --------------------------- 116 117 -- The standard does not specify the way in which bits are numbered in 118 -- a packed array. There are two reasonable rules for deciding this: 119 120 -- Store the first bit at right end (low order) word. This means 121 -- that the scaled subscript can be used directly as a left shift 122 -- count (if we put bit 0 at the left end, then we need an extra 123 -- subtract to compute the shift count). 124 125 -- Layout the bits so that if the packed boolean array is overlaid on 126 -- a record, using unchecked conversion, then bit 0 of the array is 127 -- the same as the bit numbered bit 0 in a record representation 128 -- clause applying to the record. For example: 129 130 -- type Rec is record 131 -- C : Bits4; 132 -- D : Bits7; 133 -- E : Bits5; 134 -- end record; 135 136 -- for Rec use record 137 -- C at 0 range 0 .. 3; 138 -- D at 0 range 4 .. 10; 139 -- E at 0 range 11 .. 15; 140 -- end record; 141 142 -- type P16 is array (0 .. 15) of Boolean; 143 -- pragma Pack (P16); 144 145 -- Now if we use unchecked conversion to convert a value of the record 146 -- type to the packed array type, according to this second criterion, 147 -- we would expect field D to occupy bits 4..10 of the Boolean array. 148 149 -- Although not required, this correspondence seems a highly desirable 150 -- property, and is one that GNAT decides to guarantee. For a little 151 -- endian machine, we can also meet the first requirement, but for a 152 -- big endian machine, it will be necessary to store the first bit of 153 -- a Boolean array in the left end (most significant) bit of the word. 154 -- This may cost an extra instruction on some machines, but we consider 155 -- that a worthwhile price to pay for the consistency. 156 157 -- One more important point arises in the case where we have a constrained 158 -- subtype of an unconstrained array. Take the case of 20 bits. For the 159 -- unconstrained representation, we would use an array of bytes: 160 161 -- Little-endian case 162 -- 8-7-6-5-4-3-2-1 16-15-14-13-12-11-10-9 x-x-x-x-20-19-18-17 163 164 -- Big-endian case 165 -- 1-2-3-4-5-6-7-8 9-10-11-12-13-14-15-16 17-18-19-20-x-x-x-x 166 167 -- For the constrained case, we use a 20-bit modular value, but in 168 -- general this value may well be stored in 32 bits. Let's look at 169 -- what it looks like: 170 171 -- Little-endian case 172 173 -- x-x-x-x-x-x-x-x-x-x-x-x-20-19-18-17-...-10-9-8-7-6-5-4-3-2-1 174 175 -- which stored in memory looks like 176 177 -- 8-7-...-2-1 16-15-...-10-9 x-x-x-x-20-19-18-17 x-x-x-x-x-x-x 178 179 -- An important rule is that the constrained and unconstrained cases 180 -- must have the same bit representation in memory, since we will often 181 -- convert from one to the other (e.g. when calling a procedure whose 182 -- formal is unconstrained). As we see, that criterion is met for the 183 -- little-endian case above. Now let's look at the big-endian case: 184 185 -- Big-endian case 186 187 -- x-x-x-x-x-x-x-x-x-x-x-x-1-2-3-4-5-6-7-8-9-10-...-17-18-19-20 188 189 -- which stored in memory looks like 190 191 -- x-x-x-x-x-x-x-x x-x-x-x-1-2-3-4 5-6-...11-12 13-14-...-19-20 192 193 -- That won't do, the representation value in memory is NOT the same in 194 -- the constrained and unconstrained case. The solution is to store the 195 -- modular value left-justified: 196 197 -- 1-2-3-4-5-6-7-8-9-10-...-17-18-19-20-x-x-x-x-x-x-x-x-x-x-x 198 199 -- which stored in memory looks like 200 201 -- 1-2-...-7-8 9-10-...15-16 17-18-19-20-x-x-x-x x-x-x-x-x-x-x-x 202 203 -- and now, we do indeed have the same representation for the memory 204 -- version in the constrained and unconstrained cases. 205 206 ----------------- 207 -- Subprograms -- 208 ----------------- 209 210 procedure Create_Packed_Array_Type (Typ : Entity_Id); 211 -- Typ is a array type or subtype to which pragma Pack applies. If the 212 -- Packed_Array_Type field of Typ is already set, then the call has no 213 -- effect, otherwise a suitable type or subtype is created and stored 214 -- in the Packed_Array_Type field of Typ. This created type is an Itype 215 -- so that Gigi will simply elaborate and freeze the type on first use 216 -- (which is typically the definition of the corresponding array type). 217 -- 218 -- Note: although this routine is included in the expander package for 219 -- packed types, it is actually called unconditionally from Freeze, 220 -- whether or not expansion (and code generation) is enabled. We do this 221 -- since we want gigi to be able to properly compute type characteristics 222 -- (for the Data Decomposition Annex of ASIS, and possible other future 223 -- uses) even if code generation is not active. Strictly this means that 224 -- this procedure is not part of the expander, but it seems appropriate 225 -- to keep it together with the other expansion routines that have to do 226 -- with packed array types. 227 228 procedure Expand_Packed_Boolean_Operator (N : Node_Id); 229 -- N is an N_Op_And, N_Op_Or or N_Op_Xor node whose operand type is a 230 -- packed boolean array. This routine expands the appropriate operations 231 -- to carry out the logical operation on the packed arrays. It handles 232 -- both the modular and array representation cases. 233 234 procedure Expand_Packed_Element_Reference (N : Node_Id); 235 -- N is an N_Indexed_Component node whose prefix is a packed array. In 236 -- the bit packed case, this routine can only be used for the expression 237 -- evaluation case, not the assignment case, since the result is not a 238 -- variable. See Expand_Bit_Packed_Element_Set for how the assignment case 239 -- is handled in the bit packed case. For the enumeration case, the result 240 -- of this call is always a variable, so the call can be used for both the 241 -- expression evaluation and assignment cases. 242 243 procedure Expand_Bit_Packed_Element_Set (N : Node_Id); 244 -- N is an N_Assignment_Statement node whose name is an indexed 245 -- component of a bit-packed array. This procedure rewrites the entire 246 -- assignment statement with appropriate code to set the referenced 247 -- bits of the packed array type object. Note that this procedure is 248 -- used only for the bit-packed case, not for the enumeration case. 249 250 procedure Expand_Packed_Eq (N : Node_Id); 251 -- N is an N_Op_Eq node where the operands are packed arrays whose 252 -- representation is an array-of-bytes type (the case where a modular 253 -- type is used for the representation does not require any special 254 -- handling, because in the modular case, unused bits are zeroes. 255 256 procedure Expand_Packed_Not (N : Node_Id); 257 -- N is an N_Op_Not node where the operand is packed array of Boolean 258 -- in standard representation (i.e. component size is one bit). This 259 -- procedure expands the corresponding not operation. Note that the 260 -- non-standard representation case is handled by using a loop through 261 -- elements generated by the normal non-packed circuitry. 262 263 function Involves_Packed_Array_Reference (N : Node_Id) return Boolean; 264 -- N is the node for a name. This function returns true if the name 265 -- involves a packed array reference. A node involves a packed array 266 -- reference if it is itself an indexed component referring to a bit- 267 -- packed array, or it is a selected component whose prefix involves 268 -- a packed array reference. 269 270 procedure Expand_Packed_Address_Reference (N : Node_Id); 271 -- The node N is an attribute reference for the 'Address reference, where 272 -- the prefix involves a packed array reference. This routine expands the 273 -- necessary code for performing the address reference in this case. 274 275 procedure Expand_Packed_Bit_Reference (N : Node_Id); 276 -- The node N is an attribute reference for the 'Bit reference, where the 277 -- prefix involves a packed array reference. This routine expands the 278 -- necessary code for performing the bit reference in this case. 279 280end Exp_Pakd; 281