Basic Blocks

The basic block (node of control flow graph) is defined as a structure:

typedef struct basic_block_def {

  /* The first and last insns of the block.  */
  rtx head, end;

  /* The first and last trees of the block.  */
  tree head_tree;
  tree end_tree;

  /* The edges into and out of the block.  */
  edge pred, succ;

  /* Liveness info.  */

  /* The registers that are modified within
     this block.  */
  regset local_set;
  /* The registers that are conditionally
     modified within this block.
     In other words, registers that are set only
     as part of a COND_EXEC.  */

  regset cond_local_set;
  /* The registers that are live on entry to this block.  */
  regset global_live_at_start;
  /* The registers that are live on exit from this block.  */
  regset global_live_at_end;

  /* Auxiliary info specific to a pass.  */
  void *aux;

  /* The index of this block.  */
  int index;

  /* Loop info.  */

  /* The loop depth of this block.  */
  int loop_depth;

  /* Outermost loop containing the block.  */
  struct loop *loop_father;

  /* Immediate dominator.  */
  struct basic_block_def *dominator;

  /* Expected number of executions: calculated in profile.c.  */
  gcov_type count;

  /* Expected frequency.
     Normalized to be in range 0 to BB_FREQ_MAX.  */
  int frequency;

  /* Various flags.  See BB_* below.  */
  int flags;
}

Basic block is a straight-line sequence of code that can be entered only at the beginning and leaved only at the end. Basic blocks are represented using basic_block data type that contains pointers to the head (first instruction of the basic block) and the end (last instruction) as well as other information maintained about each block.

In the RTL function representation, the head pointer always points either to NOTE_INSN_BASIC_BLOCK or to CODE_LABEL, if present. Basic block ends by control flow instruction or last instruction before following CODE_LABEL.

Special basic blocks ENTRY_BLOCK_PTR and EXIT_BLOCK_PTR represent possible entry points and exits from the compiled function.

The BASIC_BLOCK array contains all basic blocks in the order they appear in the insn stream.

The RTL instruction stream contains not only the ``real'' instructions, but also notes. Notes may or may not appear inside basic block. Any function that moves or duplicates the basic blocks needs to take care of updating of these notes. Many of notes expect that code consists of linear regions making such updates difficult.

Additionally the jump table vectors are represented as ``instructions'' inside the insn chain. These vectors never appear in the basic block and should be always placed just after table jump instructions referencing them. After removing the table-jump it is difficult to eliminate the code computing address and referencing the vector, so cleaning up the vectors is postponed to liveness analysis and thus the vectors may appear in the insn chain without any purpose. Before any edge is made fall-thru, the existence of such construct in the way needs to be checked by calling can_fallthru function.