1.6.3. Create node for array type
When invoking build_array_type, the second parameter index_type should be node of index created in previous sector.
3790 tree
3791 build_array_type (tree elt_type, tree index_type) in tree.c
3792 {
3793 tree t;
3794 unsigned int hashcode;
3795
3796 if (TREE_CODE (elt_type) == FUNCTION_TYPE)
3797 {
3798 error ("arrays of functions are not meaningful");
3799 elt_type = integer_type_node;
3800 }
3801
3802
3803 build_pointer_type (elt_type);
3804
3805
3807 t = make_node (ARRAY_TYPE);
3808 TREE_TYPE (t) = elt_type;
3809 TYPE_DOMAIN (t) = index_type;
3810
3811 if (index_type == 0)
3812 {
3813 return t;
3814 }
3815
3816 hashcode = TYPE_HASH (elt_type) + TYPE_HASH (index_type);
3817 t = type_hash_canon (hashcode, t);
3818
3819 if (!COMPLETE_TYPE_P (t))
3820 layout_type (t);
3821 return t;
3822 }
In C++, array name can be used as the starting address, and array name plus index is the pointer the element. For example:
int a[5];
int *p = a + 3; // but can’t be int &p = a +3;
So at line 3803, it creates pointer type for the element (at the time of creating array type, the type of element should be ready, but may not for its pointer type).
1.6.3.1. Layout the type
For array type, the extra information need be recorded includes size of array in bits, size of array in bytes and alignment, tegother with that information of element.
1528 void
1529 layout_type (tree type) in stor-layout.c
1530 {
1531 if (type == 0)
1532 abort ();
1533
1534
1535 if (TYPE_SIZE (type))
1536 return;
1537
1538 switch (TREE_CODE (type))
1539 {
…
1619 case ARRAY_TYPE:
1620 {
1621 tree index = TYPE_DOMAIN (type);
1622 tree element = TREE_TYPE (type);
1623
1624 build_pointer_type (element);
1625
1626
1627 if (index && TYPE_MAX_VALUE (index) && TYPE_MIN_VALUE (index)
1628 && TYPE_SIZE (element))
1629 {
1630 tree ub = TYPE_MAX_VALUE (index);
1631 tree lb = TYPE_MIN_VALUE (index);
1632 tree length;
1633 tree element_size;
1634
1635
1637 length = size_binop (PLUS_EXPR, size_one_node,
1638 convert (sizetype,
1639 fold (build (MINUS_EXPR,
1640 TREE_TYPE (lb),
1641 ub, lb))));
C++ allows array definition like “int a[] = {…};”. For such definition, laying out the array type should be deferred to the time of finishing parsing the part of “{…}”. At the same time, as the advent of template, the element can be a template. The size of template usually is unfixed and depends on template argments at instantiation. So compiler will define this size as 0, under which situation, the layout should also be deferred to the time of instantiation.
1.6.3.1.1. Get array’s boundary
However, even we defer the time of layout; we will still come here eventually. Otherwise, the compiler will give out an error message sooner or later and stop. Since without layout information, it doesn’t know how to create instance of the type in memory.
At line 1637 above, size_binop combines operands arg0 and arg1 with arithmetic operation code. Here the expression to be evaluated is (high boundary – low boundary)+1, it is the number of elements in the array. Notice that size_one_node at line 1637 is the tree node of numeric value 1 of integer mode. It is used as constant 1.
1594 tree
1595 size_binop (enum tree_code code, tree arg0, tree arg1) in fold-const.c
1596 {
1597 tree type = TREE_TYPE (arg0);
1598
1599 if (TREE_CODE (type) != INTEGER_TYPE || ! TYPE_IS_SIZETYPE (type)
1600 || type != TREE_TYPE (arg1))
1601 abort ();
1602
1603
1604 if (TREE_CODE (arg0) == INTEGER_CST && TREE_CODE (arg1) == INTEGER_CST)
1605 {
1606
1607 if (code == PLUS_EXPR && integer_zerop (arg0))
1608 return arg1;
1609 else if ((code == MINUS_EXPR || code == PLUS_EXPR)
1610 && integer_zerop (arg1))
1611 return arg0;
1612 else if (code == MULT_EXPR && integer_onep (arg0))
1613 return arg1;
1614
1615
1616 return int_const_binop (code, arg0, arg1, 0);
1617 }
1618
1619 if (arg0 == error_mark_node || arg1 == error_mark_node)
1620 return error_mark_node;
1621
1622 return fold (build (code, type, arg0, arg1));
1623 }
If arg0 and arg1 are not both integer constant, the expression requires more complex processing, and it is handed to fold at line 1622.
1.6.3.1.1.1. Operate integer constants
First it checks if there is any operand can be cancelled. Routine integer_zerop returns 1 if argument expr is the integer constant zero or a complex constant of zero.
579 int
580 integer_zerop (tree expr) in tree.c
581 {
582 STRIP_NOPS (expr);
583
584 return ((TREE_CODE (expr) == INTEGER_CST
585 && ! TREE_CONSTANT_OVERFLOW (expr)
586 && TREE_INT_CST_LOW (expr) == 0
587 && TREE_INT_CST_HIGH (expr) == 0)
588 || (TREE_CODE (expr) == COMPLEX_CST
589 && integer_zerop (TREE_REALPART (expr))
590 && integer_zerop (TREE_IMAGPART (expr))));
591 }
While STRIP_NOPS, given an expression as a tree, strip any outmost NOP_EXPRs and NON_LVALUE_EXPRs that don't change the machine mode.
405 #define STRIP_NOPS(EXP) / in tree.h
406 while ((TREE_CODE (EXP) == NOP_EXPR /
407 || TREE_CODE (EXP) == CONVERT_EXPR /
408 || TREE_CODE (EXP) == NON_LVALUE_EXPR) /
409 && TREE_OPERAND (EXP, 0) != error_mark_node /
410 && (TYPE_MODE (TREE_TYPE (EXP)) /
411 == TYPE_MODE (TREE_TYPE (TREE_OPERAND (EXP, 0))))) /
412 (EXP) = TREE_OPERAND (EXP, 0)
NOP_EXPR represents a conversion expected to require no code to be generated. NON_LVALUE_EXPR returns value is same as argument EXP, but guarantees it is not a l-value. See that expressions of above types will not affect the value of their single argument.
Then at line 1612, integer_onep returns 1 if expr is the integer constant 1 or the corresponding complex constant.
596 int
597 integer_onep (tree expr) in tree.c
598 {
599 STRIP_NOPS (expr);
600
601 return ((TREE_CODE (expr) == INTEGER_CST
602 && ! TREE_CONSTANT_OVERFLOW (expr)
603 && TREE_INT_CST_LOW (expr) == 1
604 && TREE_INT_CST_HIGH (expr) == 0)
605 || (TREE_CODE (expr) == COMPLEX_CST
606 && integer_onep (TREE_REALPART (expr))
607 && integer_zerop (TREE_IMAGPART (expr))));
608 }
If no operants can be cancelled, it needs int_const_binop at line 1616 does the calcultaion.
1185 static tree
1186 int_const_binop (enum tree_code code, tree arg1, tree arg2, int notrunc) in fold-const.c
1187 {
1188 unsigned HOST_WIDE_INT int1l, int2l;
1189 HOST_WIDE_INT int1h, int2h;
1190 unsigned HOST_WIDE_INT low;
1191 HOST_WIDE_INT hi;
1192 unsigned HOST_WIDE_INT garbagel;
1193 HOST_WIDE_INT garbageh;
1194 tree t;
1195 tree type = TREE_TYPE (arg1);
1196 int uns = TREE_UNSIGNED (type);
1197 int is_sizetype
1198 = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type));
1199 int overflow = 0;
1200 int no_overflow = 0;
1201
1202 int1l = TREE_INT_CST_LOW (arg1);
1203 int1h = TREE_INT_CST_HIGH (arg1);
1204 int2l = TREE_INT_CST_LOW (arg2);
1205 int2h = TREE_INT_CST_HIGH (arg2);
1206
1207 switch (code)
1208 {
1209 case BIT_IOR_EXPR:
1210 low = int1l | int2l, hi = int1h | int2h;
1211 break;
1212
1213 case BIT_XOR_EXPR:
1214 low = int1l ^ int2l, hi = int1h ^ int2h;
1215 break;
1216
1217 case BIT_AND_EXPR:
1218 low = int1l & int2l, hi = int1h & int2h;
1219 break;
1220
1221 case RSHIFT_EXPR:
1222 int2l = -int2l;
1223 case LSHIFT_EXPR:
1224
1227 lshift_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1228 &low, &hi, !uns);
1229 no_overflow = 1;
1230 break;
1231
1232 case RROTATE_EXPR:
1233 int2l = - int2l;
1234 case LROTATE_EXPR:
1235 lrotate_double (int1l, int1h, int2l, TYPE_PRECISION (type),
1236 &low, &hi);
1237 break;
For bit operation, it is straight forward. Just handles the low and high part respectively (remember the constant is 128 bits in front-end).
1.6.3.1.1.1.1. Left shift
For shift operation, sign extension is required for signed number. In lshift_double, paramter ll is the lower part of the number being shifted, and hl is the high part, while count is the bits to shift. Then lv and hv hold the result. And arith if nonzero indicates it is arithmetic shifting; otherwise is logical shift.
364 void
365 lshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1, in fold-const.c
366 HOST_WIDE_INT count, unsigned int prec,
367 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, int arith)
368 {
369 unsigned HOST_WIDE_INT signmask;
370
371 if (count < 0)
372 {
373 rshift_double (l1, h1, -count, prec, lv, hv, arith);
374 return;
375 }
376
377 #ifdef SHIFT_COUNT_TRUNCATED
378 if (SHIFT_COUNT_TRUNCATED)
379 count %= prec;
380 #endif
381
382 if (count >= 2 * HOST_BITS_PER_WIDE_INT)
383 {
384
386 *hv = 0;
387 *lv = 0;
388 }
389 else if (count >= HOST_BITS_PER_WIDE_INT)
390 {
391 *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
392 *lv = 0;
393 }
394 else
395 {
396 *hv = (((unsigned HOST_WIDE_INT) h1 << count)
397 | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
398 *lv = l1 << count;
399 }
400
401
402
403 signmask = -((prec > HOST_BITS_PER_WIDE_INT
404 ? ((unsigned HOST_WIDE_INT) *hv
405 >> (prec - HOST_BITS_PER_WIDE_INT - 1))
406 : (*lv >> (prec - 1))) & 1);
407
408 if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
409 ;
410 else if (prec >= HOST_BITS_PER_WIDE_INT)
411 {
412 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
413 *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
414 }
415 else
416 {
417 *hv = signmask;
418 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
419 *lv |= signmask << prec;
420 }
421 }
Though left shift hasn’t signed extension, as below figure demonstrates, when the precision is less than 2*HOST_WIDE_INT, bits beyond the precision needs be signed extended. If the result of shift overflows, the bits moved out of the precision should be signed extended too.
figure 2 Bits beyond precision is signed extended
figure 3 Bits moved out of precision is signed extended.