gcc/doc/gccint/control-flow-graph/basic-blocks.rst

   1 ..
   2   Copyright 1988-2022 Free Software Foundation, Inc.
   3   This is part of the GCC manual.
   4   For copying conditions, see the copyright.rst file.
   5
   6 .. index:: basic block, basic_block
   7
   8 .. _basic-blocks:
   9
  10 Basic Blocks
  11 ************
  12
  13 A basic block is a straight-line sequence of code with only one entry
  14 point and only one exit.  In GCC, basic blocks are represented using
  15 the ``basic_block`` data type.
  16
  17 .. index:: ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR
  18
  19 Special basic blocks represent possible entry and exit points of a
  20 function.  These blocks are called ``ENTRY_BLOCK_PTR`` and
  21 ``EXIT_BLOCK_PTR``.  These blocks do not contain any code.
  22
  23 .. index:: BASIC_BLOCK
  24
  25 The ``BASIC_BLOCK`` array contains all basic blocks in an
  26 unspecified order.  Each ``basic_block`` structure has a field
  27 that holds a unique integer identifier ``index`` that is the
  28 index of the block in the ``BASIC_BLOCK`` array.
  29 The total number of basic blocks in the function is
  30 ``n_basic_blocks``.  Both the basic block indices and
  31 the total number of basic blocks may vary during the compilation
  32 process, as passes reorder, create, duplicate, and destroy basic
  33 blocks.  The index for any block should never be greater than
  34 ``last_basic_block``.  The indices 0 and 1 are special codes
  35 reserved for ``ENTRY_BLOCK`` and ``EXIT_BLOCK``, the
  36 indices of ``ENTRY_BLOCK_PTR`` and ``EXIT_BLOCK_PTR``.
  37
  38 .. index:: next_bb, prev_bb, FOR_EACH_BB, FOR_ALL_BB
  39
  40 Two pointer members of the ``basic_block`` structure are the
  41 pointers ``next_bb`` and ``prev_bb``.  These are used to keep
  42 doubly linked chain of basic blocks in the same order as the
  43 underlying instruction stream.  The chain of basic blocks is updated
  44 transparently by the provided API for manipulating the CFG.  The macro
  45 ``FOR_EACH_BB`` can be used to visit all the basic blocks in
  46 lexicographical order, except ``ENTRY_BLOCK`` and ``EXIT_BLOCK``.
  47 The macro ``FOR_ALL_BB`` also visits all basic blocks in
  48 lexicographical order, including ``ENTRY_BLOCK`` and ``EXIT_BLOCK``.
  49
  50 .. index:: post_order_compute, inverted_post_order_compute, walk_dominator_tree
  51
  52 The functions ``post_order_compute`` and ``inverted_post_order_compute``
  53 can be used to compute topological orders of the CFG.  The orders are
  54 stored as vectors of basic block indices.  The ``BASIC_BLOCK`` array
  55 can be used to iterate each basic block by index.
  56 Dominator traversals are also possible using
  57 ``walk_dominator_tree``.  Given two basic blocks A and B, block A
  58 dominates block B if A is *always* executed before B.
  59
  60 Each ``basic_block`` also contains pointers to the first
  61 instruction (the :dfn:`head`) and the last instruction (the :dfn:`tail`)
  62 or :dfn:`end` of the instruction stream contained in a basic block.  In
  63 fact, since the ``basic_block`` data type is used to represent
  64 blocks in both major intermediate representations of GCC (``GIMPLE``
  65 and RTL), there are pointers to the head and end of a basic block for
  66 both representations, stored in intermediate representation specific
  67 data in the ``il`` field of ``struct basic_block_def``.
  68
  69 .. index:: CODE_LABEL, NOTE_INSN_BASIC_BLOCK
  70
  71 For RTL, these pointers are ``BB_HEAD`` and ``BB_END``.
  72
  73 .. index:: insn notes, notes, NOTE_INSN_BASIC_BLOCK
  74
  75 In the RTL representation of a function, the instruction stream
  76 contains not only the 'real' instructions, but also :dfn:`notes`
  77 or :dfn:`insn notes` (to distinguish them from :dfn:`reg notes`).
  78 Any function that moves or duplicates the basic blocks needs
  79 to take care of updating of these notes.  Many of these notes expect
  80 that the instruction stream consists of linear regions, so updating
  81 can sometimes be tedious.  All types of insn notes are defined
  82 in :samp:`insn-notes.def`.
  83
  84 In the RTL function representation, the instructions contained in a
  85 basic block always follow a ``NOTE_INSN_BASIC_BLOCK``, but zero
  86 or more ``CODE_LABEL`` nodes can precede the block note.
  87 A basic block ends with a control flow instruction or with the last
  88 instruction before the next ``CODE_LABEL`` or
  89 ``NOTE_INSN_BASIC_BLOCK``.
  90 By definition, a ``CODE_LABEL`` cannot appear in the middle of
  91 the instruction stream of a basic block.
  92
  93 .. index:: can_fallthru, table jump
  94
  95 In addition to notes, the jump table vectors are also represented as
  96 'pseudo-instructions' inside the insn stream.  These vectors never
  97 appear in the basic block and should always be placed just after the
  98 table jump instructions referencing them.  After removing the
  99 table-jump it is often difficult to eliminate the code computing the
 100 address and referencing the vector, so cleaning up these vectors is
 101 postponed until after liveness analysis.   Thus the jump table vectors
 102 may appear in the insn stream unreferenced and without any purpose.
 103 Before any edge is made :dfn:`fall-thru`, the existence of such
 104 construct in the way needs to be checked by calling
 105 ``can_fallthru`` function.
 106
 107 .. index:: GIMPLE statement iterators
 108
 109 For the ``GIMPLE`` representation, the PHI nodes and statements
 110 contained in a basic block are in a ``gimple_seq`` pointed to by
 111 the basic block intermediate language specific pointers.
 112 Abstract containers and iterators are used to access the PHI nodes
 113 and statements in a basic blocks.  These iterators are called
 114 :dfn:`GIMPLE statement iterators` (GSIs).  Grep for ``^gsi``
 115 in the various :samp:`gimple-*` and :samp:`tree-*` files.
 116 There is a ``gimple_stmt_iterator`` type for iterating over
 117 all kinds of statement, and a ``gphi_iterator`` subclass for
 118 iterating over PHI nodes.
 119 The following snippet will pretty-print all PHI nodes the statements
 120 of the current function in the GIMPLE representation.
 121
 122 .. code-block:: c++
 123
 124   basic_block bb;
 125
 126   FOR_EACH_BB (bb)
 127     {
 128      gphi_iterator pi;
 129      gimple_stmt_iterator si;
 130
 131      for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
 132        {
 133          gphi *phi = pi.phi ();
 134          print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 135        }
 136      for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 137        {
 138          gimple stmt = gsi_stmt (si);
 139          print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 140        }
 141     }