1. Apparatus for prefetching instructions for execution, comprising: a history based branch prediction table for storing information about previously executed segments of sequentially addressed instructions, said segments terminating with a taken branch instruction; said table storing for each of said segments a target address for said each segment, said target address being an address of a next executed instruction following said each segment when said each segment was previously executed; said table also storing for said each segment, an address tag identifying a first instruction of said each segment and information to determine a length of said each segment, said length being variable from segment to segment; means for holding in an instruction buffer a prefetched sequence of instructions for execution, said prefetched sequence including a last instruction having a last instruction address; address comparing means for comparing said last instruction address to said address tags stored in said table in order to detect a matching address tag stored in said table; and prefetching means responsive to detection of a matching address tag in said table for prefetching storage said segment of instructions identified by said matching address tag, adding said prefetched segment to said prefetched sequence, and making said target address of said prefetched segment said last instruction address of said prefetched sequence.