1. A processor comprising: a fetching unit to fetch instructions at a fetching stage of said processor that repeats an execution cycle including at least the fetching stage for fetching the instructions from an instruction storage source and an execution stage for processing the instructions; an address control unit to determine an instruction address defined as a storage source of the instruction fetched by said fetching unit; a branch instruction predicting unit to predict, based on history information of the instructions processed in the past, whether the instruction processed by said processor at a next execution stage is a branch instruction or not; and an execution unit to process at least one of the fetched instructions at the execution stage, said address control unit including: an encoding unit to compress a high-order bit field among said high-order bit field and a predetermined low-order bit field each contained in the instruction address into high-order compressed address information, at least a bit pattern among bit patterns of the high-order compressed address information being decompressible into an original bit pattern of the high-order bit field, by segmenting the high-order bit field into a plurality of address ranges to generate first high-order address information for identifying a first segmented address range and second high-order address information for identifying an address ranges excluding the first segmented address range; and a decompressing unit to decompress the first high-order address information into the high-order bit field associated with the first segmented address range when the branch instruction is a branch instruction to branch to the first segmented address range identified by the first high-order address information, and to restore the high-order bit field corresponding to a type of the branch instruction when the branch instruction is a branch instruction to branch to an address range identified by the second high-order address information, said branch instruction predicting unit including a history storage unit to store a compressed address which includes a combination of the high-order compressed address information and the low-order bit field as history information associated with a branch destination address of the processed branch instruction in any one of a plurality of storage locations determined from the high-order compressed address information and the low-order bit field associated with the instruction address of the storage source of the branch instruction.