Methods and apparatus are disclosed for eliminating explicit control flow instructions (for example, branch instructions) from atomic instruction blocks according to a block-based instructions set architecture (ISA). In one example of the disclosed technology, an explicit data graph execution (EDGE) ISA processor is configured to fetch instruction blocks from a memory and execute at least one of the instruction blocks, each of the instruction blocks being encoded to have one or more exit points determining a target location of a next instruction block. Processor control circuitry evaluates oneor more predicates for instructions encoded within a first one of the instruction blocks, and based on the evaluating, transfers control of the processor to a second instruction block at a target location that is not specified by a control flow instruction in the first instruction block.