1 /* Jitter: Forth-style stacks with optional TOS optimization: header. 2 3 Copyright (C) 2017, 2018, 2019, 2020 Luca Saiu 4 Updated in 2021 by Luca Saiu 5 Written by Luca Saiu 6 7 This file is part of Jitter. 8 9 Jitter is free software: you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation, either version 3 of the License, or 12 (at your option) any later version. 13 14 Jitter is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with Jitter. If not, see <http://www.gnu.org/licenses/>. */ 21 22 23 #ifndef JITTER_STACK_H_ 24 #define JITTER_STACK_H_ 25 26 #include <stdlib.h> /* for size_t . */ 27 #include <stdbool.h> 28 29 #include <jitter/jitter.h> 30 #include <jitter/jitter-malloc.h> 31 #include <jitter/jitter-cpp.h> 32 33 34 /* Stack backing data structures. 35 * ************************************************************************** */ 36 37 /* A stack @dfn{backing} points to the beginning of the memory buffer used to 38 implement the stack, along with some debugging meta-information. 39 40 The stack runtime data structure is more compact, and suitable to be stored 41 efficiently in registers; in particular the runtime structure contains no 42 pointer to the *beginning* of the memory or no information about the current 43 stack height. Only the runtime stack structure, and not the backing, is 44 manipulated at run time after initialization. */ 45 46 /* A stack may be either TOS-optimized or not. */ 47 enum jitter_stack_optimization 48 { 49 /* The stack is TOS-optimized: the top of the stack is held in a separate 50 field of the struct, hopefully allocated to a machine register in order 51 to reduce memory accesses. */ 52 jitter_stack_optimization_tos, 53 54 /* The stack is not TOS-optimized: the top element is held in memory just 55 like any other. This makes some operations slower (and some marginally 56 faster), but has the advantage of freeing up one machine register. */ 57 jitter_stack_optimization_no_tos 58 }; 59 60 /* The stack @dfn{backing} is a data structure containing some information about 61 it such as the number of elements and whether the stack is TOS-optimized or 62 not; it also holds a pointer to the *beginning* of the memory used to back 63 elements, which makes initialization and finalization easier. */ 64 65 /* The stack backing. */ 66 struct jitter_stack_backing 67 { 68 /* The stack optimization, either TOS-optimized or not. */ 69 enum jitter_stack_optimization optimization; 70 71 /* How many bytes each element takes. */ 72 jitter_uint element_size_in_bytes; 73 74 /* How many elements are allocated for this stack, not including the TOS 75 element in the case of TOS optimization. This is always at least as 76 large as the number of elements requested at initialisation, but may 77 be larger in order to accommodate guard pages which must begin at page 78 boundaries. */ 79 jitter_uint element_no; 80 81 /* How many bytes were allocated with mmap. Only used if mmap is available 82 and guard pages are used for this backing. */ 83 jitter_uint mmapped_memory_size; 84 85 /* A local malloc-allocated copy of the initial element, if any; NULL if there 86 is no initial element. */ 87 char *initial_element_copy; 88 89 /* A Boolean, non-false iff the backing memory contains a guard page for, 90 respectively, underflow and overflow. */ 91 bool guard_underflow; 92 bool guard_overflow; 93 94 /* These fields, recording the beginning of the underflow and overflow guard 95 pages and the page length in bytes, are useful for debugging or for 96 trapping underflow and overflow, for example using GNU libsigsegv. */ 97 char *underflow_page_beginning; 98 char *overflow_page_beginning; 99 size_t page_length_in_bytes; 100 101 /* A pointer to the beginning of the memory holding the stack elements. 102 When stack elements are pushed or popped a pointer moves in the stack 103 data structure, but this field keeps pointing the the beginning of the 104 allocated space, making initialization and finalization easier. The 105 memory is heap-allocated, and its beginning is aligned like the result of 106 malloc . 107 This points to the beginning of usable memory, past the underflow guard 108 page if present. */ 109 char *memory; 110 }; 111 112 /* These operations should be not critical for performance on any reasonable 113 application, and therefore their implementation can safely involve non-inline 114 C functions. */ 115 116 /* Initialise the pointed stack backing, allocating space from the heap for the 117 given number of elements, each of the given size. Also store implementation 118 data in the backing, in order to make finalisation possible and to enable 119 debugging. 120 If initial_element_p_or_NULL is non-NULL initialise every stack element with 121 a copy of the given object. 122 If guard_underflow is non-false, add an underflow guard page (in 123 configurations where this is possible; ignore the option otherwise) before 124 the beginning of usable memory. 125 The same for guard_overflow, adding a page after the end of usable memory. */ 126 void 127 jitter_stack_initialize_tos_backing (struct jitter_stack_backing *backing, 128 jitter_int element_size_in_bytes, 129 jitter_int element_no, 130 char *initial_element_p_or_NULL, 131 bool guard_underflow, 132 bool guard_overflow) 133 __attribute__ ((nonnull (1))); 134 135 /* Like jitter_stack_initialize_tos_backing, for a non-TOS stack. */ 136 void 137 jitter_stack_initialize_ntos_backing (struct jitter_stack_backing *backing, 138 jitter_int element_size_in_bytes, 139 jitter_int element_no, 140 char *initial_element_p_or_NULL, 141 bool guard_underflow, 142 bool guard_overflow) 143 __attribute__ ((nonnull (1))); 144 145 /* Reset an existing stack backing which has already been initialised and 146 possibly used, without re-allocating its resources. This will re-initialise 147 stack elements where needed, and do nothign else. */ 148 void 149 jitter_stack_reset_backing (struct jitter_stack_backing *backing) 150 __attribute__ ((nonnull (1))); 151 152 /* Finalize the pointed stack backing, releasing memory. */ 153 void 154 jitter_stack_finalize_backing (struct jitter_stack_backing *backing) 155 __attribute__ ((nonnull (1))); 156 157 158 159 160 /* Stack data structure definitions. 161 * ************************************************************************** */ 162 163 /* Since the stack element type is a parameter and adding one indirection level 164 would be unacceptable for performance, we cannot use a C struct to define a 165 TOS-optimized stack; we would need something like C++ templates. Anyway it 166 is quite easy to treat two separate variables as "the stack". */ 167 168 /* The @var{stack_container} argument is meant to be part of an expression 169 containing the stack variables, for example "mystruct." . Of course it is 170 allowed to be empty. */ 171 172 /* Expand to the variable name or struct field holding the stack top, as an 173 l-value. */ 174 #define JITTER_STACK_TOS_TOP_NAME(type, stack_container, name) \ 175 stack_container \ 176 JITTER_CONCATENATE_THREE(jitter_tos_optimized_stack_, name, _top) 177 178 /* Expand to the the variable name or struct field holding the stack 179 under-top-pointer, as an l-value */ 180 #define JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name) \ 181 stack_container \ 182 JITTER_CONCATENATE_THREE(jitter_tos_optimized_stack_, name, _under_top_p) 183 #define JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) \ 184 stack_container \ 185 JITTER_CONCATENATE_THREE(jitter_non_tos_optimized_stack_, name, _top_p) 186 187 /* Declare a stack. This exapnds to one or more non-extern C variable 188 declarations, suitable for automatic variables or struct members. */ 189 #define JITTER_STACK_TOS_DECLARATION(type, name) \ 190 type JITTER_STACK_TOS_TOP_NAME(type, , name); \ 191 type * restrict JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, , name) 192 #define JITTER_STACK_NTOS_DECLARATION(type, name) \ 193 type * restrict JITTER_STACK_NTOS_TOP_POINTER_NAME(type, , name) 194 195 /* Expand to a statement initializing a stack from a backing. */ 196 #define JITTER_STACK_TOS_INITIALIZE(type, stack_container, name, backing) \ 197 do \ 198 { \ 199 /* Initialize the under-top pointer to point to one element below \ 200 the beginning of the backing for an "empty" stack, so that the \ 201 first element to be pushed will increment the pointer to the \ 202 first valid position, and store the (unspecified) initial TOS \ 203 there. This is as empty as a TOS-optimized stack can get. */ \ 204 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name) \ 205 = ((type *) ((backing).memory)) - 1; \ 206 /* Initialise the TOS. The backing contains a pointer to a copy of \ 207 the initial element chosen by the user, non-NULL iff any was \ 208 specified. */ \ 209 if ((backing).initial_element_copy != NULL) \ 210 JITTER_STACK_TOS_TOP_NAME(type, stack_container, name) \ 211 = * (type *) ((backing).initial_element_copy); \ 212 } \ 213 while (false) 214 #define JITTER_STACK_NTOS_INITIALIZE(type, stack_container, name, backing) \ 215 do \ 216 { \ 217 /* Initialize the top pointer to point to one element below \ 218 the beginning of the backing for an empty stack, so that the \ 219 first element to be pushed will increment the pointer to the \ 220 first valid position. */ \ 221 JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) \ 222 = ((type *) ((backing).memory)) - 1; \ 223 } \ 224 while (false) 225 226 /* There is no finalization facility for stacks: stacks are meant to be either 227 automatic variables or struct fields, so their storage is not heap-allocated. 228 Stack *backings* have their own finalization function. */ 229 230 /* FIXME: comment. 231 232 Stacks are meant to be used in the style of Forth, for accessing the top 233 elements only and not as arrays. 234 235 Stacks do not perform any overflow, underflow or TOS-type checking; their 236 operations are implemented as macros and are meant to be fast, but inherently 237 unsafe. 238 239 Stacks do *not* point to their backing: since every field of stack structures 240 is meant to be allocated to a register it's important not to waste space. */ 241 242 243 244 245 /* Fundamental stack operations. 246 * ************************************************************************** */ 247 248 /* FIXME: comment. 249 250 The @var{stack} argument must be an l-value expression without side effects, 251 of type struct jitter_stack_tos ; it is meant to be an automatic variable. 252 253 By using GCC extensions it would be easy to have macros expanding to 254 side-effecting expressions, altering the stack and evaluating to the new top; 255 but that feels very difficult to do in a portable macro evaluating the stack 256 only once, and here avoiding function overhead is paramount. */ 257 258 /* Expand to an expression returning the top element of the given stack. 259 Undefined behavior on empty stack. The expression this macro expands to is 260 an l-value. */ 261 #define JITTER_STACK_TOS_TOP(type, stack_container, name) \ 262 JITTER_STACK_TOS_TOP_NAME(type, stack_container, name) 263 #define JITTER_STACK_NTOS_TOP(type, stack_container, name) \ 264 (* JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name)) 265 266 /* Expand to an expression returning the under-top element of the given stack. 267 Undefined behavior on empty stack. The expression this macro expands to is 268 an l-value. */ 269 #define JITTER_STACK_TOS_UNDER_TOP(type, stack_container, name) \ 270 (* JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name)) 271 #define JITTER_STACK_NTOS_UNDER_TOP(type, stack_container, name) \ 272 (JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) [-1]) 273 274 /* Expand to an expression returning the under-under-top element of the given 275 stack. Undefined behavior on underflow. The expression this macro expands 276 to is an l-value. */ 277 #define JITTER_STACK_TOS_UNDER_UNDER_TOP(type, stack_container, name) \ 278 (JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name) [-1]) 279 #define JITTER_STACK_NTOS_UNDER_UNDER_TOP(type, stack_container, name) \ 280 (JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) [-2]) 281 282 /* Expand to an expression evaluating to the element distance positions below 283 the top of the given stack. Undefined behavior on underflow. The expression 284 this macro expands to is an r-value. 285 The distance should be a constant expression for good performance. */ 286 #define JITTER_STACK_TOS_AT_DEPTH(type, stack_container, name, distance) \ 287 ((distance == 0) \ 288 ? (JITTER_STACK_TOS_TOP(type, stack_container, name)) \ 289 : JITTER_STACK_TOS_AT_NONZERO_DEPTH(type, stack_container, name, distance)) 290 #define JITTER_STACK_NTOS_AT_DEPTH(type, stack_container, name, distance) \ 291 JITTER_STACK_NTOS_AT_NONZERO_DEPTH(type, stack_container, name, distance) 292 293 /* Like JITTER_STACK_TOS_AT_DEPTH and JITTER_STACK_NTOS_AT_DEPTH, but assume 294 that the distance is strictly positive. This expands to better code when 295 the distance is known to be non-zero but its actual value is not known. */ 296 #define JITTER_STACK_TOS_AT_NONZERO_DEPTH(type, stack_container, name, \ 297 distance) \ 298 (JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name) \ 299 [1 - (int) (distance)]) 300 #define JITTER_STACK_NTOS_AT_NONZERO_DEPTH(type, stack_container, name, \ 301 distance) \ 302 (JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) \ 303 [- (int) (distance)]) 304 305 /* Expand to a statement updating an element the given stack at the given 306 distance from the top (0 being the top, 1 being the undertop, and so on); the 307 new element will be set to the result of the expansion of the given new element. 308 Undefined behavior on underflow. 309 The distance should be a constant expression for good performance. */ 310 #define JITTER_STACK_TOS_SET_AT_DEPTH(type, stack_container, name, distance, \ 311 new_element) \ 312 do \ 313 { \ 314 /* Keeping the distance in an unsigned variable might give a useful \ 315 warning in some cases where the distance as supplied by the user is \ 316 incorrect. However the final array index computed based on the \ 317 distance can be negative, so the expression evaluating it must not \ 318 involve unsigned operands. */ \ 319 const unsigned _jitter_set_at_depth_distance_u = (distance); \ 320 const int _jitter_set_at_depth_distance = \ 321 _jitter_set_at_depth_distance_u; \ 322 if (_jitter_set_at_depth_distance == 0) \ 323 JITTER_STACK_TOS_TOP_NAME(type, stack_container, name) \ 324 = (new_element); \ 325 else \ 326 JITTER_STACK_TOS_SET_AT_NONZERO_DEPTH(type, stack_container, name, \ 327 _jitter_set_at_depth_distance, \ 328 (new_element)); \ 329 } \ 330 while (false) 331 #define JITTER_STACK_NTOS_SET_AT_DEPTH(type, stack_container, name, distance, \ 332 new_element) \ 333 do \ 334 { \ 335 (JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) \ 336 [- (int) (distance)]) = (new_element); \ 337 } \ 338 while (false) 339 340 /* Like JITTER_STACK_TOS_SET_AT_DEPTH and JITTER_STACK_NTOS_SET_AT_DEPTH, but 341 assume that the distance is strictly positive. This expands to better code 342 when the distance is known to be non-zero but its actual value is not 343 known. */ 344 #define JITTER_STACK_TOS_SET_AT_NONZERO_DEPTH(type, stack_container, name, \ 345 distance, new_element) \ 346 do \ 347 { \ 348 (JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name) \ 349 [1 - (int) (distance)]) = (new_element); \ 350 } \ 351 while (false) 352 #define JITTER_STACK_NTOS_SET_AT_NONZERO_DEPTH(type, stack_container, name, \ 353 distance, new_element) \ 354 JITTER_STACK_NTOS_SET_AT_DEPTH(type, stack_container, name, distance, \ 355 new_element) 356 357 /* Expand to a statement pushing an unspecified object on top of the given 358 stack. Undefined behavior on overflow. There is no result. This operation 359 is more efficient than JITTER_STACK_*_PUSH , and is preferred when the top 360 element is about to be replaced by another operation before it is first 361 used. */ 362 #define JITTER_STACK_TOS_PUSH_UNSPECIFIED(type, stack_container, name) \ 363 do \ 364 { \ 365 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, \ 366 name) [1] \ 367 = JITTER_STACK_TOS_TOP_NAME(type, stack_container, name); \ 368 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, \ 369 name) ++; \ 370 /* JITTER_STACK_TOS_TOP_NAME(type, stack_container, name) is */ \ 371 /* left with its previous value, which happens to be equal to */ \ 372 /* the new under-top -- but this might change in the future. */ \ 373 } \ 374 while (false) 375 /* #define JITTER_STACK_TOS_PUSH_UNSPECIFIED(type, stack_container, name) \ */ 376 /* do \ */ 377 /* { \ */ 378 /* * (++ JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, \ */ 379 /* name)) \ */ 380 /* = JITTER_STACK_TOS_TOP_NAME(type, stack_container, name); \ */ 381 /* /\* JITTER_STACK_TOS_TOP_NAME(type, stack_container, name) is *\/ \ */ 382 /* /\* left with its previous value, which happens to be equal to the *\/ \ */ 383 /* /\* new under-top -- but this might change in the future. *\/ \ */ 384 /* } \ */ 385 /* while (false) */ 386 /* For some reason this version generates one instruction too many on MIPS, 387 and x86_64, but not on PowerPC: 388 MIPS: 389 # 0x436a30: stackpushunspecified (12 bytes): 390 7676b04c 26e20004 addiu $2,$23,4 391 7676b050 aefe0004 sw $30,4($23) 392 7676b054 0040b825 or $23,$2,$0 393 x86_64: 394 # 0xef01f0: stackpushunspecified (13 bytes): 395 00007fd95b54c045 4d 8d 44 24 08 leaq 0x8(%r12),%r8 396 00007fd95b54c04a 49 89 6c 24 08 movq %rbp,0x8(%r12) 397 00007fd95b54c04f 4d 89 c4 movq %r8,%r12 398 PowerPC: 399 # 0x10033d18: stackpushunspecified (8 bytes): 400 f678c040 92 af 00 04 stw r21,4(r15) 401 f678c044 39 ef 00 04 addi r15,r15,4 402 This seems to be the same problem affecting the commented-out version of 403 JITTER_STACK_TOS_DROP . I might be forgetting a restrict qualifier 404 somewhere. But why is PowerPC immune to it? By the way, the uncommented 405 definition above is better on PowerPC as well, as it uses a post-incrementing 406 store-word-and-update instruction. Why is this version different? 407 Tested on GCC 8.0.0 20170430 , the same on every architecture. */ 408 #define JITTER_STACK_NTOS_PUSH_UNSPECIFIED(type, stack_container, name) \ 409 do \ 410 { \ 411 JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) ++; \ 412 } \ 413 while (false) 414 415 /* Expand to a statement pushing the given new element on top of the given 416 stack; the new element expression is evaluated only once. Undefined behavior 417 on overflow. There is no result. */ 418 #define JITTER_STACK_TOS_PUSH(type, stack_container, name, new_element) \ 419 do \ 420 { \ 421 const type _jitter_stack_new_element_temp = (new_element); \ 422 JITTER_STACK_TOS_PUSH_UNSPECIFIED(type, stack_container, name); \ 423 JITTER_STACK_TOS_TOP_NAME(type, stack_container, name) \ 424 = (type) _jitter_stack_new_element_temp; \ 425 } \ 426 while (false) 427 #define JITTER_STACK_NTOS_PUSH(type, stack_container, name, new_element) \ 428 do \ 429 { \ 430 const type _jitter_stack_new_element_temp = (new_element); \ 431 (JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name)) \ 432 [1] = (type) (_jitter_stack_new_element_temp); \ 433 JITTER_STACK_NTOS_PUSH_UNSPECIFIED(type, stack_container, name); \ 434 } \ 435 while (false) 436 437 /* A stack height should be treated like an abstract type, only to be used with 438 JITTER_STACK_*_HEIGHT and JITTER_STACK_*_SET_HEIGHT . It represents the 439 "height" of a stack, which is to say the distance from its bottom. Given a 440 stack it is possible to obtain its height---and then to restore the same 441 height on the same (and only the same) stack, which restores its complete 442 state including the top element. 443 It is safe, and supported, to compare two jitter_stack_height objects for 444 equality, in order to check whether one given stack has kept the same height 445 in different program states; this may be useful as a form of defensive 446 programming, perhaps in an assertion. Heights taken from *distinct* stacks 447 will always compare as different. 448 Implementation note: the actual saved value is currently a pointer to the 449 undertop element for a TOS-optimized stack, and a pointer to the top element 450 for a non-TOS-optimized stack. */ 451 typedef void * restrict 452 jitter_stack_height; 453 454 /* Return the height of the given stack as a jitter_stack_height object. The 455 result can be used in a JITTER_STACK_*_SET_HEIGHT operation. */ 456 #define JITTER_STACK_TOS_HEIGHT(type, stack_container, name) \ 457 ((const jitter_stack_height) \ 458 (JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name))) 459 #define JITTER_STACK_NTOS_HEIGHT(type, stack_container, name) \ 460 ((const jitter_stack_height) \ 461 JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name)) 462 463 /* Restore the height of a stack to the given value, which must have been saved 464 in advance. A height should always be used to pop elements, never to push 465 them back if the user wishes to reconstruct the state saved beefore in a 466 consistent and deterministic way. */ 467 #define JITTER_STACK_TOS_SET_HEIGHT(type, stack_container, name, height) \ 468 do \ 469 { \ 470 const jitter_stack_height _jitter_new_height = (height); \ 471 const jitter_stack_height _jitter_old_height \ 472 = JITTER_STACK_TOS_HEIGHT(type, stack_container, name); \ 473 if (__builtin_expect (_jitter_old_height != _jitter_new_height, \ 474 true)) \ 475 { \ 476 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name) \ 477 = _jitter_new_height; \ 478 JITTER_STACK_TOS_TOP_NAME(type, stack_container, name) \ 479 = JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, \ 480 name) [1]; \ 481 } \ 482 } \ 483 while (false) 484 #define JITTER_STACK_NTOS_SET_HEIGHT(type, stack_container, name, height) \ 485 do \ 486 { \ 487 JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) \ 488 = (const jitter_stack_height) (height); \ 489 } \ 490 while (false) 491 492 493 494 495 /* Forth-style stack operations. 496 * ************************************************************************** */ 497 498 /* Push another copy of the top element to the stack; this expands to a 499 statement, and there is no result. Undefined behavior on overflow. This 500 operation is called "dup" in Forth. */ 501 #define JITTER_STACK_TOS_DUP(type, stack_container, name) \ 502 do \ 503 { \ 504 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name) [1] \ 505 = JITTER_STACK_TOS_TOP_NAME(type, stack_container, name); \ 506 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name) ++; \ 507 } \ 508 while (false) 509 /* #define JITTER_STACK_TOS_DUP(type, stack_container, name) \ */ 510 /* do \ */ 511 /* { \ */ 512 /* * (++ JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, \ */ 513 /* name)) \ */ 514 /* = JITTER_STACK_TOS_TOP_NAME(type, stack_container, name); \ */ 515 /* } \ */ 516 /* while (false) */ 517 /* This version generates one instruction too many on MIPS, x86_64 and Aarch64 518 but is good on PowerPC, ARM and SH. Why? 519 x86_64: 520 # 0x10791f0: stackdup (11 bytes): 521 00007fa1f6a3205b 49 8d 7e 08 leaq 0x8(%r14),%rdi 522 00007fa1f6a3205f 4d 89 6e 08 movq %r13,0x8(%r14) 523 00007fa1f6a32063 49 89 fe movq %rdi,%r14 524 MIPS: 525 # 0x434a30: stackdup (12 bytes): 526 7676b06c 26af0004 addiu $15,$21,4 527 7676b070 aeb70004 sw $23,4($21) 528 7676b074 01e0a825 or $21,$15,$0 529 Aarch64: 530 # 0x42f1f0: stackdup (12 bytes): 531 00000040009ac050 91002345 add x5, x26, #0x8 532 00000040009ac054 f900075b str x27, [x26,#8] 533 00000040009ac058 aa0503fa mov x26, x5 534 PowerPC: 535 # 0x10032d18: stackdup (8 bytes): 536 f678c05c 92 11 00 04 stw r16,4(r17) 537 f678c060 3a 31 00 04 addi r17,r17,4 538 ARM: 539 # 0x3ba30: stackdup (8 bytes): 540 f6661050 e5876004 str r6, [r7, #4] 541 f6661054 e2877004 add r7, r7, #4 542 SH: 543 # 0x423a30: stackdup (4 bytes): 544 f664e034 e1 1b mov.l r14,@(4,r11) 545 f664e036 04 7b add #4,r11 546 The uncommented version is better even on PowerPC and ARM, using a single 547 post-incrementing store, like on Aarch64 which goes from three down to one. 548 Tested on GCC 8.0.0 20170430 , the same on every architecture. */ 549 #define JITTER_STACK_NTOS_DUP(type, stack_container, name) \ 550 do \ 551 { \ 552 const type _jitter_stack_top_element_copy \ 553 = * (JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name)); \ 554 * (++ JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name)) \ 555 = _jitter_stack_top_element_copy; \ 556 } \ 557 while (false) 558 559 /* Remove the top element from the stack; this expands to a statement, and there 560 is no result. Undefined behavior on empty stack. This operation is called 561 "drop" in Forth. */ 562 #define JITTER_STACK_TOS_DROP(type, stack_container, name) \ 563 do \ 564 { \ 565 /* Load the under-top element into the top. */ \ 566 JITTER_STACK_TOS_TOP_NAME (type, stack_container, name) \ 567 = JITTER_STACK_TOS_UNDER_TOP (type, stack_container, name); \ 568 /* Decrement the under-top pointer. */ \ 569 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, \ 570 stack_container, \ 571 name) --; \ 572 } \ 573 while (false) 574 /* #define JITTER_STACK_TOS_DROP(type, stack_container, name) \ */ 575 /* do \ */ 576 /* { \ */ 577 /* JITTER_STACK_TOS_TOP_NAME(type, stack_container, name) \ */ 578 /* = * (JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, \ */ 579 /* stack_container, \ */ 580 /* name) --); \ */ 581 /* } \ */ 582 /* while (false) */ 583 /* FIXME: why is this version generating three instructions? 584 This yields (MIPS): 585 # 0x436a00: stackdrop (12 bytes): 586 7676b050 26eefffc addiu $14,$23,-4 587 7676b054 8efe0000 lw $30,0($23) 588 7676b058 01c0b825 or $23,$14,$0 589 or (PowerPC): 590 # 0x10033ce8: stackdrop (12 bytes): 591 f678c040 38 af ff fc addi r5,r15,-4 592 f678c044 82 af 00 00 lwz r21,0(r15) 593 f678c048 7c af 2b 78 mr r15,r5 594 or (x86_64): 595 # 0x15c11f0: stackdrop (12 bytes): 596 00007fc8726cf04a 49 8d 54 24 f8 leaq -0x8(%r12),%rdx 597 00007fc8726cf04f 49 8b 2c 24 movq (%r12),%rbp 598 00007fc8726cf053 49 89 d4 movq %rdx,%r12 599 or (SH -- here one of the four instructions is justified by SH's two-operand 600 arithmetic, but the problem of keeping two different pointers is still 601 the same): 602 # 0x423a30: stackdrop (8 bytes): 603 f664e02e b3 63 mov r11,r3 604 f664e030 b2 6e mov.l @r11,r14 605 f664e032 fc 73 add #-4,r3 606 f664e034 33 6b mov r3,r11 607 The uncommented version above does the right thing, yielding two 608 instructions (or just one on Aarch64 and ARM, using a post-decrementing load). 609 The under-top pointer is declared restrict , so GCC cannot assume 610 that the under-top pointer may alias the top; and in fact the top is 611 correctly held in a register, even with this three-instruction version. 612 Tested on GCC 8.0.0 20170430 , the same on every architecture. */ 613 #define JITTER_STACK_NTOS_DROP(type, stack_container, name) \ 614 do \ 615 { \ 616 JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) --; \ 617 } \ 618 while (false) 619 620 /* Push a copy of the under-top element. Undefined behavior on empty 621 stack. This operation is called "over" in Forth. 622 I currently have two variants of the TOS version, one generating 623 shorter code and not using temporary registers, but with a 624 shorter-distance memory dependency; the other version generates 625 one more instruction and uses a register, but behaves better with 626 respect to dependencies. FIXME: benchmark, and possibly choose 627 differently according to the configuration. */ 628 #define JITTER_STACK_TOS_OVER_LONGER(type, stack_container, name) \ 629 do \ 630 { \ 631 const type _jitter_stack_over_under_top_temp \ 632 = JITTER_STACK_TOS_UNDER_TOP(type, stack_container, name); \ 633 JITTER_STACK_TOS_PUSH(type, stack_container, name, \ 634 _jitter_stack_over_under_top_temp); \ 635 } \ 636 while (false) 637 #define JITTER_STACK_TOS_OVER_SHORTER(type, stack_container, name) \ 638 do \ 639 { \ 640 /* Name the old top as a temporary. This does not require a load, but \ 641 having a separate temporary read early might help the compiler with \ 642 alias analysis. */ \ 643 const type _jitter_stack_over_top_old \ 644 = JITTER_STACK_TOS_TOP (type, stack_container, name); \ 645 /* Write the old top into memory, at the over-under-top position, which \ 646 means at the top. */ \ 647 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME (type, stack_container, name) [1] \ 648 = _jitter_stack_over_top_old; \ 649 /* Read the old under-top, which we have not touched, into the top. */ \ 650 JITTER_STACK_TOS_TOP (type, stack_container, name) \ 651 = JITTER_STACK_TOS_UNDER_TOP (type, stack_container, name); \ 652 /* Increment the under-top stack pointer. */ \ 653 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME (type, stack_container, name) ++; \ 654 } \ 655 while (false) 656 #define JITTER_STACK_TOS_OVER(type, stack_container, name) \ 657 /* FIXME: benchmark and choose either JITTER_STACK_TOS_OVER_SHORTER or \ 658 JITTER_STACK_TOS_OVER_LONGER . */ \ 659 JITTER_STACK_TOS_OVER_SHORTER (type, stack_container, name) 660 #define JITTER_STACK_NTOS_OVER(type, stack_container, name) \ 661 do \ 662 { \ 663 const type _jitter_stack_old_under_top_element_copy \ 664 = JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) [-1]; \ 665 * (++ JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name)) \ 666 = _jitter_stack_old_under_top_element_copy; \ 667 } \ 668 while (false) 669 670 /* Insert a copy of the top element as the new under-under-top element, moving 671 the under-top and top elements one position up each; after the execution of 672 the operation the stack will be one element taller. Undefined behavior on 673 underflow. This operation is called "tuck" in Forth, and has stack effect 674 ( a b -- b a b ). */ 675 #define JITTER_STACK_TOS_TUCK(type, stack_container, name) \ 676 do \ 677 { \ 678 /* Do not disturb the top, which has already the correct value for the \ 679 final state. Instead load a copy of the under-top element, whose \ 680 memory content will need to change. */ \ 681 const type _jitter_stack_tuck_under_top_old \ 682 = JITTER_STACK_TOS_UNDER_TOP (type, stack_container, name); \ 683 /* Change the stack height. From now on we can think about stack \ 684 elements in the positions they will occupy in the final state. */ \ 685 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME (type, stack_container, name) ++; \ 686 /* We have to change both the under-under-top and the under-top elements, \ 687 which now are sure to have values different from the ones in the final \ 688 state. */ \ 689 JITTER_STACK_TOS_UNDER_UNDER_TOP (type, stack_container, name) \ 690 = JITTER_STACK_TOS_TOP (type, stack_container, name); \ 691 JITTER_STACK_TOS_UNDER_TOP (type, stack_container, name) \ 692 = _jitter_stack_tuck_under_top_old; \ 693 } \ 694 while (false) 695 #define JITTER_STACK_NTOS_TUCK(type, stack_container, name) \ 696 do \ 697 { \ 698 /* This version will not be as nice and fast as the TOS case. The \ 699 top three elements in the stack all need to change. */ \ 700 /* Load the current under-top and top. */ \ 701 const type _jitter_stack_tuck_under_top_old \ 702 = JITTER_STACK_NTOS_UNDER_TOP (type, stack_container, name); \ 703 const type _jitter_stack_tuck_top_old \ 704 = JITTER_STACK_NTOS_TOP (type, stack_container, name); \ 705 /* Change the stack height. The height will be what we need in the \ 706 final state after this. */ \ 707 JITTER_STACK_NTOS_TOP_POINTER_NAME (type, stack_container, name) ++; \ 708 /* Store the changed elements. */ \ 709 JITTER_STACK_NTOS_UNDER_UNDER_TOP (type, stack_container, name) \ 710 = _jitter_stack_tuck_top_old; \ 711 JITTER_STACK_NTOS_UNDER_TOP (type, stack_container, name) \ 712 = _jitter_stack_tuck_under_top_old; /* The height has changed. */ \ 713 JITTER_STACK_NTOS_TOP (type, stack_container, name) \ 714 = _jitter_stack_tuck_top_old; /* Again, not the same height. */ \ 715 } \ 716 while (false) 717 718 /* Swap the top and under-top element on the stack; this expands to a statement, 719 and there is no result. Undefined behavior on underflow. This operation is 720 called "swap" in Forth. */ 721 #define JITTER_STACK_TOS_SWAP(type, stack_container, name) \ 722 do \ 723 { \ 724 const type _jitter_stack_swap_under_top_temp \ 725 = JITTER_STACK_TOS_UNDER_TOP(type, stack_container, name); \ 726 JITTER_STACK_TOS_UNDER_TOP(type, stack_container, name) \ 727 = JITTER_STACK_TOS_TOP(type, stack_container, name); \ 728 JITTER_STACK_TOS_TOP(type, stack_container, name) \ 729 = _jitter_stack_swap_under_top_temp; \ 730 } \ 731 while (false) 732 #define JITTER_STACK_NTOS_SWAP(type, stack_container, name) \ 733 do \ 734 { \ 735 const type _jitter_stack_swap_top_temp \ 736 = JITTER_STACK_NTOS_TOP(type, stack_container, name); \ 737 const type _jitter_stack_swap_under_top_temp \ 738 = JITTER_STACK_NTOS_UNDER_TOP(type, stack_container, name); \ 739 JITTER_STACK_NTOS_UNDER_TOP(type, stack_container, name) \ 740 = _jitter_stack_swap_top_temp; \ 741 JITTER_STACK_NTOS_TOP(type, stack_container, name) \ 742 = _jitter_stack_swap_under_top_temp; \ 743 } \ 744 while (false) 745 746 /* Swap the under-top and the under-under-top elements on the stack; this 747 expands to a statement, and there is no result. Undefined behavior on 748 underflow. This operation does not exist in Forth, but following its 749 naming pattern I would call it "quake"; the metaphore being an earth 750 movement right below the surface. 751 The stack effect is ( a b c -- b a c ). */ 752 #define JITTER_STACK_TOS_QUAKE(type, stack_container, name) \ 753 do \ 754 { \ 755 const type _jitter_stack_quake_under_under_top_old \ 756 = JITTER_STACK_TOS_UNDER_UNDER_TOP(type, stack_container, name); \ 757 const type _jitter_stack_quake_under_top_old \ 758 = JITTER_STACK_TOS_UNDER_TOP(type, stack_container, name); \ 759 JITTER_STACK_TOS_UNDER_UNDER_TOP(type, stack_container, name) \ 760 = _jitter_stack_quake_under_top_old; \ 761 JITTER_STACK_TOS_UNDER_TOP(type, stack_container, name) \ 762 = _jitter_stack_quake_under_under_top_old; \ 763 } \ 764 while (false) 765 #define JITTER_STACK_NTOS_QUAKE(type, stack_container, name) \ 766 do \ 767 { \ 768 const type _jitter_stack_quake_under_under_top_old \ 769 = JITTER_STACK_NTOS_UNDER_UNDER_TOP(type, stack_container, name); \ 770 const type _jitter_stack_quake_under_top_old \ 771 = JITTER_STACK_NTOS_UNDER_TOP(type, stack_container, name); \ 772 JITTER_STACK_NTOS_UNDER_UNDER_TOP(type, stack_container, name) \ 773 = _jitter_stack_quake_under_top_old; \ 774 JITTER_STACK_NTOS_UNDER_TOP(type, stack_container, name) \ 775 = _jitter_stack_quake_under_under_top_old; \ 776 } \ 777 while (false) 778 779 /* Remove the under-top element from the stack, without affecting the top; this 780 expands to a statement, and there is no result. Undefined behavior on an 781 empty or one-element stack. This operation is called "nip" in Forth. */ 782 #define JITTER_STACK_TOS_NIP(type, stack_container, name) \ 783 do \ 784 { \ 785 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name) --; \ 786 } \ 787 while (false) 788 #define JITTER_STACK_NTOS_NIP(type, stack_container, name) \ 789 do \ 790 { \ 791 const type _jitter_stack_nip_top_temp \ 792 = JITTER_STACK_NTOS_TOP(type, stack_container, name); \ 793 * (-- JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name)) \ 794 = _jitter_stack_nip_top_temp; \ 795 } \ 796 while (false) 797 798 /* Expand to a statement rearranging the topmost three elements of the stack 799 so that their configuration (top on the right) changes from 800 a b c 801 to 802 b c a 803 . Undefined behavior on underflow. This operation is called "rot" in 804 Forth. */ 805 #define JITTER_STACK_TOS_ROT(type, stack_container, name) \ 806 JITTER_STACK_TOS_ROLL (type, stack_container, name, 2) 807 #define JITTER_STACK_NTOS_ROT(type, stack_container, name) \ 808 JITTER_STACK_NTOS_ROLL (type, stack_container, name, 2) 809 810 /* Expand to a statement rearranging the topmost three elements of the stack 811 so that their configuration (top on the right) changes from 812 a b c 813 to 814 c a b 815 . Undefined behavior on underflow. This operation is called "-rot" in 816 Forth. */ 817 #define JITTER_STACK_TOS_MROT(type, stack_container, name) \ 818 JITTER_STACK_TOS_MROLL (type, stack_container, name, 2) 819 #define JITTER_STACK_NTOS_MROT(type, stack_container, name) \ 820 JITTER_STACK_NTOS_MROLL (type, stack_container, name, 2) 821 822 823 824 825 /* Potentially inefficient stack operations. 826 * ************************************************************************** */ 827 828 /* The stack operations defined in this section may expand to inefficient code 829 and are not recommended for production use, unless the arguments are known 830 small constants. Anyway they are convenient for testing. */ 831 832 833 /* Expand to a statement rearranging the topmost roll_depth + 1 elements of 834 the given stack so that the element originally at depth roll_depth goes to 835 top, and every element originally above it is moved down one position to 836 make place. 837 For example, passing roll_depth with a value of 3 turns 838 a b c d e f 839 into 840 a b d e f c 841 . In Forth the depth argument is taken from the stack. Here 842 JITTER_STACK_TOS_ROLL(type, stack_container, name, N) 843 behaves like 844 N roll 845 in Forth. 846 Just like in Forth, roll is a potentially inefficient operation, as it 847 requires O(roll_depth) memory accesses. In production it should only be 848 used with small and constant values of roll_depth . */ 849 #define JITTER_STACK_TOS_ROLL(type, stack_container, name, roll_depth) \ 850 do \ 851 { \ 852 /* Use an unsigned variable to get a warning in case the user passes a \ 853 negative constant by mistake. Then convert to int, so that we may \ 854 safely compute negative indices from other index operands, as it may \ 855 be needed fo termination conditions. */ \ 856 unsigned jitter_roll_depthu = (roll_depth); \ 857 int jitter_roll_depth = jitter_roll_depthu; \ 858 if (jitter_roll_depth == 0) \ 859 break; \ 860 /* Slide values down from depth i to i + 1. Keep the next value to be \ 861 written in the temporary jitter_roll_old , initialized with the top \ 862 out of the loop. */ \ 863 type jitter_roll_old \ 864 = JITTER_STACK_TOS_TOP (type, stack_container, name); \ 865 int jitter_roll_depth_i; \ 866 for (jitter_roll_depth_i = 1; \ 867 jitter_roll_depth_i <= jitter_roll_depth; \ 868 jitter_roll_depth_i ++) \ 869 { \ 870 /* Before overwriting a value, save it: it will become the next \ 871 jitter_roll_old . Then perform the overwrite, and update \ 872 jitter_roll_old . Here I can afford the faster _AT_NONZERO_DEPTH \ 873 macros, as the only case dealing with the top is handled out of \ 874 the loop. */ \ 875 const type jitter_roll_to_be_overwritten \ 876 = JITTER_STACK_TOS_AT_NONZERO_DEPTH (type, stack_container, name, \ 877 jitter_roll_depth_i); \ 878 JITTER_STACK_TOS_SET_AT_NONZERO_DEPTH(type, stack_container, name, \ 879 jitter_roll_depth_i, \ 880 jitter_roll_old); \ 881 jitter_roll_old = (type) jitter_roll_to_be_overwritten; \ 882 } \ 883 /* Now after the loop jitter_roll_old has the old value of the deepest \ 884 value. That goes to the top. */ \ 885 JITTER_STACK_TOS_TOP (type, stack_container, name) = jitter_roll_old; \ 886 } \ 887 while (false) 888 #define JITTER_STACK_NTOS_ROLL(type, stack_container, name, roll_depth) \ 889 do \ 890 { \ 891 /* Use an unsigned variable to get a warning in case the user passes a \ 892 negative constant by mistake. Then convert to int, so that we may \ 893 safely compute negative indices from other index operands, as it may \ 894 be needed fo termination conditions. */ \ 895 unsigned jitter_roll_depthu = (roll_depth); \ 896 int jitter_roll_depth = jitter_roll_depthu; \ 897 /* Do nothing if the deepest element to be affected is at depth zero. */ \ 898 if (jitter_roll_depth == 0) \ 899 break; \ 900 /* Slide values down from depth i to i + 1. Keep the next value to be \ 901 written in the temporary jitter_roll_old , initialized with the top \ 902 out of the loop. */ \ 903 type jitter_roll_old \ 904 = JITTER_STACK_NTOS_TOP (type, stack_container, name); \ 905 int jitter_roll_depth_i; \ 906 for (jitter_roll_depth_i = 1; \ 907 jitter_roll_depth_i <= jitter_roll_depth; \ 908 jitter_roll_depth_i ++) \ 909 { \ 910 /* Before overwriting a value, save it: it will become the next \ 911 jitter_roll_old . Then perform the overwrite, and update \ 912 jitter_roll_old . */ \ 913 const type jitter_roll_to_be_overwritten \ 914 = JITTER_STACK_NTOS_AT_DEPTH (type, stack_container, name, \ 915 jitter_roll_depth_i); \ 916 JITTER_STACK_NTOS_SET_AT_DEPTH(type, stack_container, name, \ 917 jitter_roll_depth_i, \ 918 jitter_roll_old); \ 919 jitter_roll_old = (type) jitter_roll_to_be_overwritten; \ 920 } \ 921 /* Now after the loop jitter_roll_old has the old value of the deepest \ 922 value. That goes to the top. */ \ 923 JITTER_STACK_NTOS_TOP (type, stack_container, name) = jitter_roll_old; \ 924 } \ 925 while (false) 926 927 /* Expand to a statement performing a stack change similar in spirit to the roll 928 operation, but rearranging the stack elements the opposite way: the old top 929 becomes the deepest element, and all the elements originally below it are 930 moved up by one position to make place. 931 For example, given that roll (3) turns 932 a b c d e f 933 into 934 a b d e f c 935 , -roll (3) turns 936 a b c d e f 937 into 938 a b f c d e 939 . This "-roll" is not actually a predefined operation in Forth, but has its 940 place as a sensible variant of roll. 941 This "-roll" is to "roll" like "-rot" is to "rot". */ 942 #define JITTER_STACK_TOS_MROLL(type, stack_container, name, mroll_depth) \ 943 do \ 944 { \ 945 /* Use an unsigned variable to get a warning in case the user passes a \ 946 negative constant by mistake. Then convert to int, so that we may \ 947 safely compute negative indices from other index operands, as it may \ 948 be needed fo termination conditions. */ \ 949 unsigned jitter_mroll_depthu = (mroll_depth); \ 950 int jitter_mroll_depth = jitter_mroll_depthu; \ 951 if (jitter_mroll_depth == 0) \ 952 break; \ 953 /* Slide values up from depth i to i - 1. Keep the next value to be \ 954 written in the temporary jitter_roll_old , initialized with the top \ 955 out of the loop. Compared to roll, I iterate in the opposite \ 956 direction, so that here again the old top is the first value to be \ 957 read. */ \ 958 type jitter_mroll_old \ 959 = JITTER_STACK_TOS_TOP (type, stack_container, name); \ 960 int jitter_mroll_depth_i; \ 961 for (jitter_mroll_depth_i = jitter_mroll_depth; \ 962 jitter_mroll_depth_i > 0; /* Differently from the TOS case this \ 963 needs to be a strict > . */ \ 964 jitter_mroll_depth_i --) \ 965 { \ 966 /* Before overwriting a value, save it: it will become the next \ 967 jitter_mroll_old . Then perform the overwrite, and update \ 968 jitter_mroll_old . */ \ 969 const type jitter_mroll_to_be_overwritten \ 970 = JITTER_STACK_TOS_AT_NONZERO_DEPTH (type, stack_container, name, \ 971 jitter_mroll_depth_i); \ 972 JITTER_STACK_TOS_SET_AT_NONZERO_DEPTH (type, stack_container, name, \ 973 jitter_mroll_depth_i, \ 974 jitter_mroll_old); \ 975 jitter_mroll_old = (type) jitter_mroll_to_be_overwritten; \ 976 } \ 977 /* Differently from the non-TOS case, here the final update must be out \ 978 of the loop: this is the only case where _AT_NONZERO_DEPTH macros \ 979 would not work. */ \ 980 JITTER_STACK_TOS_TOP (type, stack_container, name) = jitter_mroll_old; \ 981 } \ 982 while (false) 983 #define JITTER_STACK_NTOS_MROLL(type, stack_container, name, mroll_depth) \ 984 do \ 985 { \ 986 /* Use an unsigned variable to get a warning in case the user passes a \ 987 negative constant by mistake. Then convert to int, so that we may \ 988 safely compute negative indices from other index operands, as it may \ 989 be needed fo termination conditions. */ \ 990 unsigned jitter_mroll_depthu = (mroll_depth); \ 991 int jitter_mroll_depth = jitter_mroll_depthu; \ 992 /* Do nothing if the deepest element to be affected is at depth zero. */ \ 993 if (jitter_mroll_depth == 0) \ 994 break; \ 995 /* Slide values up from depth i to i - 1. Keep the next value to be \ 996 written in the temporary jitter_roll_old , initialized with the top \ 997 out of the loop. Compared to roll, I iterate in the opposite \ 998 direction, so that here again the old top is the first value to be \ 999 read. */ \ 1000 type jitter_mroll_old \ 1001 = JITTER_STACK_NTOS_TOP (type, stack_container, name); \ 1002 int jitter_mroll_depth_i; \ 1003 for (jitter_mroll_depth_i = jitter_mroll_depth; \ 1004 jitter_mroll_depth_i > 0; /* Here a guard with >= instead of >, and \ 1005 no statement after the loop, would be \ 1006 correct, differenrtly from the TOS \ 1007 case. But GCC 9 as of early 2019 \ 1008 appears to do a better job at \ 1009 unrolling this way, without a load not \ 1010 followed by a use of the loaded \ 1011 value. */ \ 1012 jitter_mroll_depth_i --) \ 1013 { \ 1014 /* Before overwriting a value, save it: it will become the next \ 1015 jitter_mroll_old . Then perform the overwrite, and update \ 1016 jitter_mroll_old . */ \ 1017 const type jitter_mroll_to_be_overwritten \ 1018 = JITTER_STACK_NTOS_AT_DEPTH (type, stack_container, name, \ 1019 jitter_mroll_depth_i); \ 1020 JITTER_STACK_NTOS_SET_AT_DEPTH (type, stack_container, name, \ 1021 jitter_mroll_depth_i, \ 1022 jitter_mroll_old); \ 1023 jitter_mroll_old = (type) jitter_mroll_to_be_overwritten; \ 1024 } \ 1025 /* Now after the loop jitter_mroll_old has the old value of the deepest \ 1026 value. That goes to the top. \ 1027 See the comment above: this would not be needed if the loop guard had \ 1028 a non-strict comparison. */ \ 1029 JITTER_STACK_NTOS_TOP (type, stack_container, name) = jitter_mroll_old; \ 1030 } \ 1031 while (false) 1032 1033 /* Expand to a statement performing a stack change to delete a given number of 1034 non-top elements at the given depth. 1035 * The element_no argument is the number of elements to delete. It must be 1036 non-negative; 1037 * the depth argument is the depth of the deepest element to delete. It must 1038 be strictly positive. 1039 For good performance both arguments should be known at compile time. 1040 It is forbidden for this operation to change the top element: the metaphor of 1041 "sliding" is a landslide where some below-ground strata collapse, which cause 1042 a displacement of the surface layer down (potentially along with other layers) 1043 without changing the surface. 1044 After the operation is executed the stack will be element_no elements shorter. 1045 Undefined behavior on: 1046 * underflow; 1047 * top element write; 1048 * any over-the-top element access. 1049 For example 1050 slide 1 1 1051 is equivalent to nip, and has the stack effect 1052 ( a b -- b ) 1053 . Then 1054 slide 2 2 1055 is equivalent to nip nip, and has the stack effect 1056 ( a b c -- c ) 1057 and 1058 slide 1 2 1059 has the stack effect 1060 ( b c d -- c d ) 1061 This is a generalization of nip, fast when the arguments are known at compile 1062 time but potentially dangerous to use because of the possibility of accessing 1063 the top element or even elements above the top by mistake, which may lead to 1064 subtly incorrect results. */ 1065 #define JITTER_STACK_TOS_SLIDE(type, stack_container, name, element_no, depth) \ 1066 do \ 1067 { \ 1068 /* Use unsigned variables to get a warning in case the user passes \ 1069 negative constants by mistake. */ \ 1070 unsigned int jitter_slide_element_no = (element_no); \ 1071 unsigned int jitter_slide_depth = (depth); \ 1072 \ 1073 /* Slide values down starting from the deepest one, iterating towards \ 1074 the top. Having the jitter_slide_source_depth unsigned might help \ 1075 catching some user bugs, ifthe value is negative and the compiler \ 1076 gives a warning. */ \ 1077 unsigned int jitter_slide_source_depth; \ 1078 for (jitter_slide_source_depth \ 1079 = jitter_slide_depth - jitter_slide_element_no; \ 1080 /* The top is never modified, and the old under-top element is the \ 1081 shallowest element that can be read; instead the under-under-top \ 1082 element is the shallowest to be written. */ \ 1083 jitter_slide_source_depth != 0; /* !=: stop before the top. */ \ 1084 jitter_slide_source_depth --) \ 1085 { \ 1086 unsigned int jitter_slide_target_depth \ 1087 = jitter_slide_source_depth + jitter_slide_element_no; \ 1088 const type jitter_slide_source \ 1089 = JITTER_STACK_TOS_AT_NONZERO_DEPTH (type, stack_container, name, \ 1090 jitter_slide_source_depth); \ 1091 JITTER_STACK_TOS_SET_AT_NONZERO_DEPTH (type, stack_container, name, \ 1092 jitter_slide_target_depth, \ 1093 jitter_slide_source); \ 1094 } \ 1095 /* Decrement the (under-top) stack pointer. */ \ 1096 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME(type, stack_container, name) \ 1097 -= jitter_slide_element_no; \ 1098 /* Notice that the top element has not been updated. This TOS version \ 1099 will *always* leave it as it was, which satisfies the specification \ 1100 above but will lead to subtle bugs if this operation is used \ 1101 carelessly.*/ \ 1102 } \ 1103 while (false) 1104 #define JITTER_STACK_NTOS_SLIDE(type, stack_container, name, element_no, depth) \ 1105 do \ 1106 { \ 1107 /* Use unsigned variables to get a warning in case the user passes \ 1108 negative constants by mistake. Then convert to signed types and use \ 1109 the signed versions which are more convenient later; we need a sign \ 1110 test in the loop guard. */ \ 1111 unsigned int jitter_slide_element_nou = (element_no); \ 1112 unsigned int jitter_slide_depthu = (depth); \ 1113 int jitter_slide_element_no = jitter_slide_element_nou; \ 1114 int jitter_slide_depth = jitter_slide_depthu; \ 1115 \ 1116 /* Slide values down starting from the deepest one, iterating towards \ 1117 the top. */ \ 1118 int jitter_slide_source_depth; \ 1119 for (jitter_slide_source_depth \ 1120 = jitter_slide_depth - jitter_slide_element_no; \ 1121 /* In the non-TOS case the top element is the last to be read. */ \ 1122 jitter_slide_source_depth >= 0; \ 1123 jitter_slide_source_depth --) \ 1124 { \ 1125 int jitter_slide_target_depth \ 1126 = jitter_slide_source_depth + jitter_slide_element_no; \ 1127 const type jitter_slide_source \ 1128 = JITTER_STACK_NTOS_AT_DEPTH (type, stack_container, name, \ 1129 jitter_slide_source_depth); \ 1130 JITTER_STACK_NTOS_SET_AT_NONZERO_DEPTH (type, stack_container, name, \ 1131 jitter_slide_target_depth, \ 1132 jitter_slide_source); \ 1133 } \ 1134 /* Decrement the top stack pointer. */ \ 1135 JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) \ 1136 -= jitter_slide_element_no; \ 1137 } \ 1138 while (false) 1139 1140 /* Duplicate a non-top element at the given depth, moving every shallower 1141 element up by one position. At the end of the operation the stack becomes 1142 one position taller. 1143 Undefined behavior on: 1144 * underflow; 1145 * non-positive argument. 1146 For good performance the argument should be known at compile time. 1147 bulge 1 is equivalent to over swap, and has effect 1148 ( a b -- a a b ) 1149 bulge 2 has effect 1150 ( a b c -- a a b c ) */ 1151 #define JITTER_STACK_TOS_BULGE(type, stack_container, name, depth) \ 1152 do \ 1153 { \ 1154 /* Use unsigned variables to get a warning in case the user passes a \ 1155 negative constant by mistake, or reaches a negative depth. Also use \ 1156 unsigned variables for depths, so that user errors causing a \ 1157 wraparound are more catastrophic and therefore easier to see. */ \ 1158 unsigned int jitter_bulge_depth_old = (depth); \ 1159 /* The given depth is relative to the old state. Immediately increment \ 1160 the (under-top) stack pointer, and only reason about depths in the \ 1161 new state. */ \ 1162 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME (type, stack_container, name) ++; \ 1163 unsigned int jitter_bulge_max_source_depth = jitter_bulge_depth_old + 1; \ 1164 unsigned int jitter_bulge_max_target_depth \ 1165 = jitter_bulge_max_source_depth - 1; \ 1166 /* No special handling is needed for the top in the TOS case, as it \ 1167 already has the correct value. */ \ 1168 /* Iterate from shallow to deep positions, up to an update to the top \ 1169 element, *not included* (this is different from the TOS case). This \ 1170 makes elements at the depth mentioned by the user or above but below \ 1171 the top slide up by one position. \ 1172 Notice the inconsistency in behavior with respect to a zero depth \ 1173 argument and the non-TOS case below: the TOS case with zero depth \ 1174 degenerates to push-unspecified rather than dup. */ \ 1175 unsigned int jitter_bulge_target_depth; \ 1176 for (jitter_bulge_target_depth = 1; /* Different from non-TOS. */ \ 1177 jitter_bulge_target_depth <= jitter_bulge_max_target_depth; \ 1178 jitter_bulge_target_depth ++) \ 1179 { \ 1180 unsigned int jitter_bulge_source_depth \ 1181 = jitter_bulge_target_depth + 1; \ 1182 JITTER_STACK_TOS_AT_NONZERO_DEPTH (type, stack_container, name, \ 1183 jitter_bulge_target_depth) \ 1184 = JITTER_STACK_TOS_AT_NONZERO_DEPTH (type, stack_container, name, \ 1185 jitter_bulge_source_depth); \ 1186 } \ 1187 } \ 1188 while (false) 1189 #define JITTER_STACK_NTOS_BULGE(type, stack_container, name, depth) \ 1190 do \ 1191 { \ 1192 /* Use unsigned variables to get a warning in case the user passes a \ 1193 negative constant by mistake, or reaches a negative depth. Also use \ 1194 unsigned variables for depths, so that user errors causing a \ 1195 wraparound are more catastrophic and therefore easier to see. */ \ 1196 unsigned int jitter_bulge_depth_old = (depth); \ 1197 /* The given depth is relative to the old state. Immediately increment \ 1198 the stack pointer and only reason about new-state depths. */ \ 1199 JITTER_STACK_NTOS_TOP_POINTER_NAME (type, stack_container, name) ++; \ 1200 unsigned int jitter_bulge_max_source_depth = jitter_bulge_depth_old + 1; \ 1201 unsigned int jitter_bulge_max_target_depth \ 1202 = jitter_bulge_max_source_depth - 1; \ 1203 /* Iterate from shallow to deep positions, up to an update to the top \ 1204 element, included. This makes elements at the depth mentioned by \ 1205 the user or above slide up by one position. \ 1206 Notice that specifying a depth of 0, in the non-TOS case, degenerates \ 1207 to dup. This behavior must *not* be relied upon, as it is not \ 1208 consistent with the TOS case. */ \ 1209 unsigned int jitter_bulge_target_depth; \ 1210 for (jitter_bulge_target_depth = 0; \ 1211 jitter_bulge_target_depth <= jitter_bulge_max_target_depth; \ 1212 jitter_bulge_target_depth ++) \ 1213 { \ 1214 unsigned int jitter_bulge_source_depth \ 1215 = jitter_bulge_target_depth + 1; \ 1216 JITTER_STACK_NTOS_AT_DEPTH (type, stack_container, name, \ 1217 jitter_bulge_target_depth) \ 1218 = JITTER_STACK_NTOS_AT_DEPTH (type, stack_container, name, \ 1219 jitter_bulge_source_depth); \ 1220 } \ 1221 } \ 1222 while (false) 1223 1224 /* Exchange the top element with a deeper element, deleting the element_no 1225 elements in between. 1226 Undefined behavior on: 1227 * underflow; 1228 * negative element_no. 1229 This is fast when the argument is known at compile time. 1230 The metaphor is two objects dancing around a central pivot exchanging their 1231 places, and at the same time squashing the pivot. 1232 The stack effect for whirl 1 is 1233 ( a b c -- c a ) 1234 , equivalent to 1235 ( a b c ) nip ( a c ) swap ( c a ). 1236 For whirl 2 the effect will be 1237 ( a b c d -- d a ) 1238 . The case of whirl 0 degenerates to swap: 1239 ( a b -- b a ) */ 1240 #define JITTER_STACK_TOS_WHIRL(type, stack_container, name, element_no) \ 1241 do \ 1242 { \ 1243 /* As long as the argument is a known constant this is just an typical \ 1244 exchange between a memory location and a register, followed by a \ 1245 stack increment. */ \ 1246 /* Use an unsigned variable to get a warning in case the user passes \ 1247 a negative constant by mistake. */ \ 1248 unsigned int _jitter_whirl_element_no = (element_no); \ 1249 /* The stack depth of the deepest element to be touched, in the old \ 1250 state. */ \ 1251 unsigned int _jitter_whirl_deepest_depth_old \ 1252 = _jitter_whirl_element_no + 1; \ 1253 /* Name the two source elements. This will only cost one load, since \ 1254 there is no need to modify the top-element register until near the \ 1255 end. */ \ 1256 const type _jitter_stack_swirl_deepest_old \ 1257 = JITTER_STACK_TOS_AT_NONZERO_DEPTH (type, stack_container, name, \ 1258 _jitter_whirl_deepest_depth_old); \ 1259 const type _jitter_stack_swirl_top_old \ 1260 = JITTER_STACK_TOS_TOP (type, stack_container, name); \ 1261 /* Write the two target elements and adjust the stack (under-top) \ 1262 pointer. The deepest element is always in memory, at the same \ 1263 address where the old version of it was. This will cost one store, \ 1264 one register copy, plus the register increment. */ \ 1265 JITTER_STACK_TOS_SET_AT_NONZERO_DEPTH (type, stack_container, name, \ 1266 _jitter_whirl_deepest_depth_old, \ 1267 _jitter_stack_swirl_top_old); \ 1268 JITTER_STACK_TOS_TOP (type, stack_container, name) \ 1269 = _jitter_stack_swirl_deepest_old; \ 1270 JITTER_STACK_TOS_UNDER_TOP_POINTER_NAME (type, stack_container, name) \ 1271 -= _jitter_whirl_element_no; \ 1272 } \ 1273 while (false) 1274 #define JITTER_STACK_NTOS_WHIRL(type, stack_container, name, element_no) \ 1275 do \ 1276 { \ 1277 /* This is not properly an exchange between two memory locations: \ 1278 the new top element will end up at a different address from the \ 1279 old top element. */ \ 1280 /* Use an unsigned variable to get a warning in case the user passes \ 1281 a negative constant by mistake. */ \ 1282 unsigned int _jitter_whirl_element_no = (element_no); \ 1283 /* The stack depth of the deepest element to be touched, in the old \ 1284 state. */ \ 1285 unsigned int _jitter_whirl_deepest_depth_old \ 1286 = _jitter_whirl_element_no + 1; \ 1287 /* Read the two source elements from memory. */ \ 1288 const type _jitter_stack_swirl_deepest_old \ 1289 = JITTER_STACK_NTOS_AT_DEPTH (type, stack_container, name, \ 1290 _jitter_whirl_deepest_depth_old); \ 1291 const type _jitter_stack_swirl_top_old \ 1292 = JITTER_STACK_NTOS_TOP (type, stack_container, name); \ 1293 /* Adjust the stack pointer and write the two target elements, again \ 1294 in memory. */ \ 1295 JITTER_STACK_NTOS_SET_AT_DEPTH (type, stack_container, name, \ 1296 _jitter_whirl_deepest_depth_old, \ 1297 _jitter_stack_swirl_top_old); \ 1298 JITTER_STACK_NTOS_TOP_POINTER_NAME (type, stack_container, name) \ 1299 -= _jitter_whirl_element_no; \ 1300 JITTER_STACK_NTOS_TOP (type, stack_container, name) \ 1301 = _jitter_stack_swirl_deepest_old; \ 1302 } \ 1303 while (false) 1304 1305 /* Expand to a statement destructively reversing the order of the topmost n 1306 elements of the given stack. */ 1307 #define JITTER_STACK_TOS_REVERSE(type, stack_container, name, element_no) \ 1308 do \ 1309 { \ 1310 /* Use an unsigned variable to get a warning in case the user passes a \ 1311 negative constant by mistake. Then convert to int, so that we may \ 1312 safely compute negative indices from other index operands, as it may \ 1313 be needed fo termination conditions. */ \ 1314 unsigned jitter_reverse_element_nou = (element_no); \ 1315 int jitter_reverse_element_no = jitter_reverse_element_nou; \ 1316 /* Do nothing unless we have at least two elements to swap. If we do, \ 1317 then of course we have to handle the TOS specially, and swap it with \ 1318 the deepest element. */ \ 1319 if (jitter_reverse_element_no < 2) \ 1320 break; \ 1321 JITTER_SWAP (type, \ 1322 JITTER_STACK_TOS_TOP_NAME(type, stack_container, name), \ 1323 JITTER_STACK_TOS_AT_NONZERO_DEPTH \ 1324 (type, stack_container, name, \ 1325 (jitter_reverse_element_no - 1))); \ 1326 /* Every other element to swap will be at a non-zero depth. Have two \ 1327 indices moving towards one another; keep swapping element pairs \ 1328 until the two indices meet or cross. */ \ 1329 int jitter_reverse_up_depth = 1; \ 1330 int jitter_reverse_down_depth = jitter_reverse_element_no - 2; \ 1331 while (jitter_reverse_down_depth > jitter_reverse_up_depth) \ 1332 { \ 1333 JITTER_SWAP (type, \ 1334 JITTER_STACK_TOS_AT_NONZERO_DEPTH \ 1335 (type, stack_container, name, \ 1336 jitter_reverse_up_depth), \ 1337 JITTER_STACK_TOS_AT_NONZERO_DEPTH \ 1338 (type, stack_container, name, \ 1339 jitter_reverse_down_depth)); \ 1340 jitter_reverse_up_depth ++; \ 1341 jitter_reverse_down_depth --; \ 1342 } \ 1343 } \ 1344 while (false) 1345 #define JITTER_STACK_NTOS_REVERSE(type, stack_container, name, element_no) \ 1346 do \ 1347 { \ 1348 /* Use an unsigned variable to get a warning in case the user passes a \ 1349 negative constant by mistake. Then convert to int, so that we may \ 1350 safely compute negative indices from other index operands, as it may \ 1351 be needed fo termination conditions. */ \ 1352 unsigned jitter_reverse_element_nou = (element_no); \ 1353 int jitter_reverse_element_no = jitter_reverse_element_nou; \ 1354 /* Have two depth indices moving into opposite directions. Keep \ 1355 swapping elements at the dephts described by the two indices, until \ 1356 the indices meet or cross. */ \ 1357 int jitter_reverse_up_depth = 0; \ 1358 int jitter_reverse_down_depth = jitter_reverse_element_no - 1; \ 1359 while (jitter_reverse_down_depth > jitter_reverse_up_depth) \ 1360 { \ 1361 JITTER_SWAP (type, \ 1362 JITTER_STACK_NTOS_AT_DEPTH (type, stack_container, name, \ 1363 jitter_reverse_up_depth), \ 1364 JITTER_STACK_NTOS_AT_DEPTH (type, stack_container, name, \ 1365 jitter_reverse_down_depth)); \ 1366 jitter_reverse_up_depth ++; \ 1367 jitter_reverse_down_depth --; \ 1368 } \ 1369 } \ 1370 while (false) 1371 1372 1373 1374 1375 /* Generic stack operations with user-specified functions. 1376 * ************************************************************************** */ 1377 1378 /* Compute the given "setter" on the top element of the stack, replacing it 1379 with the result. 1380 This expands to a statement, and there is no result. Undefined behavior 1381 on an empty or one-element stack. 1382 The "setter" is supposed to be the name of a two-argument macro expanding 1383 to a statement which modifies its first argument (an l-value expression) 1384 using the other (an r-value expression). The setter body may be 1385 protected with the usual do .. while (false) idiom. 1386 1387 Example: 1388 #define SETSUCC(res, a) do { res.field = a.field + 1; } while (0) 1389 JITTER_STACK_TOS_UNARY(union my_union, stack, , SETSUCC); 1390 #undef SETSUCC */ 1391 #define JITTER_STACK_TOS_UNARY(type, stack_container, name, setter) \ 1392 do \ 1393 { \ 1394 { \ 1395 setter(JITTER_STACK_TOS_TOP(type, stack_container, name), \ 1396 JITTER_STACK_TOS_TOP(type, stack_container, name)); \ 1397 } \ 1398 } \ 1399 while (false) 1400 #define JITTER_STACK_NTOS_UNARY(type, stack_container, name, setter) \ 1401 do \ 1402 { \ 1403 { \ 1404 setter(JITTER_STACK_NTOS_TOP(type, stack_container, name), \ 1405 JITTER_STACK_NTOS_TOP(type, stack_container, name)); \ 1406 } \ 1407 } \ 1408 while (false) 1409 1410 /* Compute the given "setter" on the under-top and top elements of the stack, in 1411 that order, replacing both with the result. 1412 This expands to a statement, and there is no result. Undefined behavior 1413 on an empty or one-element stack. 1414 The "setter" is supposed to be the name of a three-argument macro expanding 1415 to a statement which modifies its first argument (an l-value expression) 1416 using the other two (r-value expressions), in order. The setter body may be 1417 protected with the usual do .. while (false) idiom, but does not need to be. 1418 1419 Example: 1420 #define SETPLUS(res, a, b) do { res.field = a.field + b.field; } while (0) 1421 JITTER_STACK_TOS_BINARY(union my_union, stack, , SETPLUS); 1422 #undef SETPLUS */ 1423 #define JITTER_STACK_TOS_BINARY(type, stack_container, name, setter) \ 1424 do \ 1425 { \ 1426 { \ 1427 setter(JITTER_STACK_TOS_TOP(type, stack_container, name), \ 1428 JITTER_STACK_TOS_UNDER_TOP(type, stack_container, name), \ 1429 JITTER_STACK_TOS_TOP(type, stack_container, name)); \ 1430 } \ 1431 JITTER_STACK_TOS_NIP(type, stack_container, name); \ 1432 } \ 1433 while (false) 1434 #define JITTER_STACK_NTOS_BINARY(type, stack_container, name, setter) \ 1435 do \ 1436 { \ 1437 { \ 1438 setter(JITTER_STACK_NTOS_UNDER_TOP(type, stack_container, name), \ 1439 JITTER_STACK_NTOS_UNDER_TOP(type, stack_container, name), \ 1440 JITTER_STACK_NTOS_TOP(type, stack_container, name)); \ 1441 } \ 1442 JITTER_STACK_NTOS_TOP_POINTER_NAME(type, stack_container, name) --; \ 1443 } \ 1444 while (false) 1445 1446 1447 1448 1449 /* Helper macros, not for the user. 1450 * ************************************************************************** */ 1451 1452 /* Expand to a statement destructively swapping the values of the two given 1453 l-values, which must have both the given type. Either a or b may be 1454 evaluated twice. */ 1455 #define JITTER_SWAP(type, a, b) \ 1456 do \ 1457 { \ 1458 const type _jitter_swap_tmp = (a); \ 1459 (a) = (b); \ 1460 (b) = (type) _jitter_swap_tmp; \ 1461 } \ 1462 while (false) 1463 1464 #endif // #ifndef JITTER_STACK_H_ 1465