An integrated circuit may have configurable storage blocks. A configurable storage block may include a memory array, and arithmetic and control circuitry. The arithmetic and control circuitry may be used to determine whether to operate the configurable storage block in a first mode which may provide random access to the memory array or in a second mode which may provide access to the memory array in a predefined order. Thus, the configurable storage block may implement simple first-in first-out modules and shift registers in addition to implementing memory modules with random access. Arithmetic and control circuitry may include a multiplexer that determines whether the configurable storage block is implementing simple first-in first-out modules or shift registers. When the configurable storage block implements first-in first-out modules, an up-down counter may be activated to generate a count value received at the multiplexer.