Source: http://www.google.com.br/patents/US8166450
Timestamp: 2018-01-17 06:51:07
Document Index: 286036815

Matched Legal Cases: ['application No. 60', 'art2', 'art2', 'art2', 'art 3', 'art 3']

Patente US8166450 - Methods and apparatus for compiling instructions for a data processor - Patentes do Google
Methods and apparatus optimized for compiling instructions in a data processor are disclosed. In one aspect, a method of address calculation is disclosed, comprising operating a compiler to generate at least one instruction; canonicalizing the address calculation in a plurality of different approaches:...http://www.google.com.br/patents/US8166450?utm_source=gb-gplus-sharePatente US8166450 - Methods and apparatus for compiling instructions for a data processor
Número da publicação US8166450 B2
Número do pedido US 11/906,519
Data de publicação 24 abr. 2012
Data de depósito 1 out. 2007
Data da prioridade 26 dez. 2001
Também publicado como US7278137, US20080320246
Número da publicação 11906519, 906519, US 8166450 B2, US 8166450B2, US-B2-8166450, US8166450 B2, US8166450B2
Inventores Richard A. Fuhler, Thomas J. Pennello, Michael Lee Jalkut, Peter Warnes
Cessionário original Synopsys, Inc.
Citações de patente (90), Citações de não patente (38), Citada por (35), Classificações (8), Eventos legais (3)
Methods and apparatus for compiling instructions for a data processor
US 8166450 B2
1. A method of register allocation for use by a pipelined digital processor having a mixed-length instruction set architecture, the method executed by the processor and comprising:
storing data in a register from a first set of registers, the first set of registers associated with a first instruction set of a first length;
evaluating, using graph theory, whether spilling of the register from the first set of registers to a second set of registers is required, the second set of registers associated with a second instruction set of a second length; and
responsive to evaluating that spilling is required, reassigning the data in the register from the first set of registers to a register from the second set of registers.
2. The method of claim 1, wherein the first instruction set of the first length comprises instructions of a 16-bit length and the second instruction set of the second length comprises instructions of a 32-bit length.
responsive to evaluating that spilling is required, coalescing instructions associated with one or more registers from the first set of registers and the second set of registers to reduce a number of instructions.
4. The method of claim 3, wherein coalescing instructions comprises:
determining a first version of a plurality of instructions associated with the first set of registers and the second set of registers, the first version determined according to the first instruction set of the first length;
determining a second version of the plurality of instructions associated with the first set of registers and the second set of registers, the second version determined according to the second instruction set of the second length;
determining for a portion of the plurality of instructions whether the first version or the second version is better in terms of size of instruction or number of instructions; and
selecting the better version of the portion of the plurality of instructions.
5. The method of claim 4, wherein determining whether the first version or the second version is better is based on size of the portion of the plurality of instructions in the first version and second version.
6. The method of claim 4, wherein determining whether the first version or the second version is better is based on a number of instructions in the first version and second version of the portion of the plurality of instructions.
assigning a different characteristic to the register that is going to be spilled; and
performing a common sub-expression elimination process.
assigning a priority to each register from the first set of registers.
assigning a specific characteristic for at least one register from the first set of registers based at least in part on at least one of: (i) compressing a size of an instruction of the at least one register, or (ii) reducing an overall size of a compiled function.
assigning characteristics to each register from the first set of registers and the second set of registers; and
assigning a different characteristic to the register from the first set of registers that is going to be spilled.
11. A digital processor having a mixed-length instruction set architecture, the processor comprising:
a first set of registers associated with a first instruction set of a first length; and
a second set of registers associated with a second instruction set of a second length;
wherein data stored in a register from the first set of registers is reassigned to a register from the second set of registers responsive to evaluating that spilling is required.
12. The digital processor of claim 11, wherein the first instruction set of the first length comprises instructions of a 16-bit length and the second instruction set of the second length comprises instructions of a 32-bit length.
13. The digital processor of claim 11, wherein instructions associated with one or more registers from the first set of registers and the second set of registers is coalesced to reduce a number of instructions responsive to spilling.
14. The digital processor of claim 13, wherein the digital processor is configured to reduce the number of instructions by:
15. The digital processor of claim 14, wherein determining whether the first version or the second version is better is based on size of the portion of the plurality of instructions in the first version and second version.
16. The digital processor of claim 14, wherein determining whether the first version or the second version is better is based on a number of instructions in the first version and second version of the portion of the plurality of instructions.
17. The digital processor of claim 11, wherein the digital processor is configured to:
assign a different characteristic to the register that is going to be spilled; and
perform a common sub-expression elimination process.
18. The digital processor of claim 11, wherein each register from the first set of registers is assigned a priority.
19. The digital processor of claim 11, wherein the digital processor is configured to:
assign characteristics to each register from the first set of registers and the second set of registers; and
assign a different characteristic to the register from the first set of registers that is going to be spilled.
20. The digital processor of claim 11, wherein evaluating that spilling is required comprising using graph coloring for the evaluation.
This application is a divisional of U.S. application Ser. No. 10/330,632, filed Dec. 26, 2002 now U.S. Pat. No. 7,278,137 and claims priority benefit of U.S. provisional patent application Ser. No. 60/343,730 filed Dec. 26, 2001 and entitled “Methods and Apparatus for Compiling Instructions for a Data Processor” both of which are incorporated herein by reference in their entirety.
U.S. Pat. No. 6,090,156 to MacLeod issued Jul. 18, 2000 and entitled “System for local context spilling for graph coloring register allocators” discloses a register allocator for allocating machine registers' during compilation of a computer program. The register allocator performs the steps of building an interference graph, reducing the graph using graph coloring techniques, attempting to assign colors (i.e. allocate machine registers to symbolic registers), and generating spill code. The spill code is generated by a local context spiller which processes a basic block on an instruction by instruction basis. The local context spiller attempts to allocate a machine register which is free in the basic block. If the basic block does not have any free machine registers, the local context spiller looks ahead to select a machine register for spilling. The register allocator improves the performance of a compiler by limiting the rebuilding of the interference graph and the number of the graph reduction operations.
Another area of interest in compiler and instruction set optimization relates to address canonicalization; see, e.g., the “canonical reduction sequence” on pg. 152 of “Principles of Compiler Design” by Aho and Ullman, April 1979. In practice, addresses are canonicalized to the specifics of the machine for which code is being generated. Typical decisions are made to base/index/scale operations as well as size of displacements and allowed formats (for example, a load instruction may have a base register plus either an immediate offset or an index register with a scaling factor). By generating the same sequence of instructions for the address (no matter how redundant), one hopes to take advantage of global common sub-expression elimination, such as that defined in “Global Optimization by Suppression of Partial Redundancies” by Morel and Renvoise, CACM February 1979; “The Pascal XT Code Generator” by Drechsler and Stadel, SIGPLAN Notices, August 1987; and Cliff Click, “Global code motion/global value numbering”, ACM SIGPLAN Notices, v. 30 n. 6, p. 246-257, June 1995.
Such stages may comprise, for example, instruction fetch, decode, execution, and writeback stages.
Lastly, any references to hardware description language (HDL) or VHSIC HDL (VHDL) contained herein are also meant to include other hardware description languages such as Verilogg. Furthermore, an exemplary Synopsys® synthesis engine such as the Design Compiler 2000.05 (DC00) may be used to synthesize the various embodiments set forth herein, or alternatively other synthesis engines such as Buildgates® available from, inter alia, Cadence Design Systems, Inc., may be used. IEEE std. 1076.3-1997, IEEE Standard VHDL Synthesis Packages, describes an industry-accepted language for specifying a Hardware Definition Language-based design and the synthesis capabilities that may be expected to be available to one of ordinary skill in the art.
The ARCtangent-A5 processor is a 32-bit four stage pipeline RISC architecture that implements the ARCompact™ instruction set. The ARCompact ISA is described in detail in co-owned, co-pending U.S. provisional patent application No. 60/353,647 filed Jan. 31, 2002 and entitled “Configurable Data Processor With Multi-Length Instruction Set Architecture” which is incorporated herein by reference in its entirety. ARCompact™ is an instruction set architecture (ISA) that allows designers to mix 16 and 32-bit instructions on its 32-bit user-configurable processor. The key benefit of the ISA is the ability to cut memory requirements on a SoC (system-on-chip) by significant percentages, resulting in lower power consumption and lower cost devices in deeply embedded applications such as wireless communications and high volume consumer electronics products.
The main features of the ARCompact ISA include 32-bit instructions aimed at providing better code density, a set of 16-bit instructions for the most commonly used operations, and freeform mixing of 16- and 32-bit instructions without a mode switch—significant because it reduces the complexity of compiler usage compared to competing mode-switching architectures. The ARCompact instruction set expands the number of custom extension instructions that users can add to the base-case ARCtangent™ processor instruction set. The ARCtangent processor architecture allows users to add as many as 69 new instructions to speed up critical routines and algorithms. With the ARCompact ISA, users can add as many as 256 new instructions. Users can also add new core registers, auxiliary registers, and condition codes. The ARCompact ISA thus maintains and expands the user-customizable features of ARC's configurable processor technology.
// that allows −32/31 would divide the offset by 64 and use that “page”
1) Common sub-expression elimination:-
2) Moving code out of loops -
for (int I = 10; I < n; I++) {
3) Eliminating dead code -
The first calculation of ‘x+2’ would be killed if no other use
of it and the assignment into ‘a’ would be killed generally.
4) Strength reduction -
int x = y+y; // strength reduced into simpler and faster instruction.
5) Induction variable elimination -
int a1 = a,*b1 = b;
while (n−−) *a1++ = *b1++ dx;
6) Register assignment -
if (f->type == REG_i && oREG(*f) == r) {
// call foo <-- 4 bytes
// ld r1,[pc-rel zpool] <-- 2 bytes + (4 for store)
// So this only benefits when called 3 or more times....
© 2000-2002 ARC International. All rights reserved.
As illustrated in the foregoing code example, the availability of the constant pool and the 16-bit pc-relative load instruction, plus the 16-bit jump-indirect instruction, further reduces the size of the resulting code as the number of occurrences calling the one function increases. In this particular instance, the trade-off in ld/jmp is beneficial when 3 or more occurrences of the function are found within the function.
// which is one 32-bit instruction that reduces the instruction
//and clock count for the program
CMP status32 <- r1,r2 // added CMP to allow
for further optimizations
ADD r0,r0,r16; unchanged in size, still 2bytes since we have
; an ADD encoding that allows addition of a
; compressed and a non-compressed register together
; with the destination being the same compressed
register as the source
static void delete_EA_opd(IL_entry *il, int which_one) {
_arc_case type t = _arc_case_type (PSEUDO_NO(il));
case DUAL_EA_LOAD_UNCACHED_BITS_func: {
SET_PSEUDO_NO (il, LOAD_UNCACHED_BITS_func);
goto ldbits;
case DUAL_EA_LOADU_UNCACHED_BITS func:
SET_PSEUDO_NO (il, LOADU_UNCACHED_BITS_func);
case DUAL_EA_LOAD_BITS_func:
SET_PSEUDO_NO (il, LOAD_BITS_func);
case DUAL_EA_LOADU_BITS_func:
SET_PSEUDO_NO (il, LOADU_BITS_func);
ldbits: ;
if (which_one == 1) SRC1 (il) = SRC2 (il);
SRC2 (il) = SRC3 (il);
SRC3 (il) = SRC4 (il);
il->set_src_cnt (3);
case DUAL_EA_LOAD_func: {
il.op = il_LOAD;
il.cond = Cond_NULL;
goto fixit;
case DUAL_EA_LA_func:
il->op = il_LA;
il->cond = Cond_NULL;
case DUAL_EA_LOADU_func:
il.op = il_LOADU;
fixit: ;
il->set_src_cnt(1);
case DUAL_EAT_STORE_UNCACHED_BITU_func: {
SET_ PSEUDO_NO (il, STORE_UNCACHED_BITU_func);
goto stbits;
case DUAL_EA_STORE_UNCACHED_BITS_func:
SET_PSEUEO_NO (il, STORE_UNCACHED_BITS_func);
case DUAL_EA_STORE_BITU_func:
SET_PSEUDO_NO (il, STORE_BITU_func);
case DUAL_EA_STORE_BITS_func:
SET_PSEUDO_NO (il, STORE_BITS_func);
stbits: ;
if (il_src_cnt(il) != 5) {
print_il (il);
system_error(“arc:ssa:delete_ea_opd”,
“wrong src cnt for storebits”, ABORT);
if (il_def_cnt (il) != 2) {
“wrong def cnt for storebits”, ABORT);
if (which_one == 1) {
DEST1(il) =DEST2 (il);
SRC4 (il) = SRC5 (il);
il->set_def_cnt (1);
il->set_src_cnt (4);
case DUAL_EA_STORE_func:
if (which_one == 1) DEST1(il) = DEST2 (il);
il->set_def_cnt(1);
il.op =il_STORE;
system_error(“SSA-delete-ea-opd”,“unknown IL”, ABORT);
static int do_canonicalization(bool *live_dead_bad) {
determine_ref_counts(1);
int deleted_something = 0;
if (trace_ssa_tog)
printf(“[ssa] deal with dual-EA instructions . . . \n”);
for_each_node(bp, n) {
for_each_il(il, bp) {
if (trace_ssa_tog) {
printf(“looking at: ”); print_il (il); fflush(stdout);
EA_entry *ep = NULL;
int ldst_common(void) {
if (ep.base.type == REG_i) {
cnt += REG_REFS_CNT(oREG(ep.base));
if (ep.index.type == REG_i) {
cnt += REG_REFS_CNT(oREG(ep.index));
return cnt ? cnt : 1;
if (il.op == il_PSEUDO)
switch (_arc_case_type(PSEUDO_NO(il))) {
case DUAL_EA_MOVE_func: {
// take care of srcs
ep = oEA(SRC1(il));
int cnt1 =ldst common( );
ep = oEA(SRC3 (il));
int cnt2 = ldst_common( );
if (cnt2 >= cnt1) {
SRC1(il) = SRC3 (il);
il->set_src_cnt(2);
// take care of defs
ep = oEA(DEST1 (il));
int cnt3 = ldst_common( );
ep = oEA(DEST2 (il));
int cnt4 = ldst_common( );
if (cnt4 >= cnt3) {
DEST1(il) = DEST2 (il);
il->op = il_MOVE;
deleted_something++;
case DUAL_EA_LOADU_UNCACHED_BITS_func:
case DUAL_EA_LOAD_UNCACHED_BITS_func:
case DUAL_EA_LOADU_BITS_func: case DUAL_EA_LOAD_BITS_func:
case DUAL_EA_LOAD_func: case DUAL_EA_LOADU_func: {
ep = oEA(SRC1 (il));
int cntl = ldst_common( );
ep = oEA(SRC2 (il));
delete_EA_opd (il,l+ (cnt2 >= cnt1));
case DUAL_EA_STORE_UNCACHED_BITU_func:
case DUAL_EA_STORE_func: {
ep =oEA(DEST1(il));
int cntl =ldstcommon();
ep =oEA(DEST2(il));
int cnt2 =ldst common();
delete EA_opd(il,1+(cnt2 >=cnt1));
if (deleted_something && live_dead_bad) *live_dead_bad = TRUE;
// so no other dual-EAs emitted . . . .
return deleted_something;
// example of converting an existing 32-bit instruction into
// something use-able by compressed instruction set.
static void modify_r_imm_r_instr(gentab **_gp, bool is_delay_slot) {
if (is_delay_slot) return;
gentab *gp = *_gp;
Register a = get(r_imm_r, a);
Register b = get(r_imm_r, c);
long limm = get(r_imm_r, limm);
IL_condition cc = get(r_imm_r, cc);
bool f = get(r_imm_r, f);
switch (gp_op(gp)) {
case_32_16 (g_ASL): case_32_16(g_ LSL): {
if (a != b && !f) {
cg_opcode op = gp_op(gp);
if (limm == 1) {
limm =0;
op = g_BSET;
gentab *mov = Alloc_gen_entry(gp_prev(gp) , g_MOV, r_imm);
copyto_(mov, r_imm, a, a);
copyto_(mov, r_imm, limm, limm);
copyto_(mov, r_imm, cc, cc);
cvt_to_rrr_instr(gp, op, a, a, b, cc, f);
*_gp = gp_prev(mov);
case_32_16(g_SUB): case_32_16(g_CMP):
case g_RSUB: case g_RCMP: {
// communative as long as reversed . . . .
switch (gp_op (gp)) {
case_32_16 (g_SUB): gp_op(gp) = g_RSUB; break;
case g_RSUB: gp_op (gp) = g_SUB; break;
case_32_16(g_CMP): gp_op (gp) = g_RCMP; break;
case g_RCMP: gp_op (gp) = g_CMP; break;
cvt_to_rr_imm_instr(gp, gp_op (gp) , a, b, limm, cc, f);
if (DEBUG_CVT_ARC4_INSTRS | {
printf(“. . cvt'ed to:\t” | ;
print_gp (gp);
if (a == null_reg && f) {
// this is a compare . . .
if (DEBUG_CVT_ARC4_INSTRS) {
printf(“. . chg to compare. . . \n”);
// first swap above took care of r_imm_r to rr_imm.
// this one converts it fully to a compare.
case_32_16 (g_SUB): gp_op (gp) = g_CMP; break;
case g_RSUB: gp_op (gp) = g_RCMP; break;
cvt_to_r_imm_instr(gp, gp_op (gp), b, limm, cc, FALSE);
print(“. . into:\t”); print_gp (gp);
*_gp = gp_prev(gp);
case_32_16 (g_ADD): case_32_16 (g_AND):
case_32_16 (g_OR): case_32_16 (g_XOR):
case g_MAX: case g_MIN: {
cvt_to_rr_imm_instr(gp, cg_opcode (gp_op (gp)), a, b, limm, cc, f);
*_gp = gp_prev (gp);
Register c = null_reg;
if (a != b) c = a;
else if (!Oneof2 (TEMP_REG, a, b)) c = TEMP_REG;
printf(“. . trying to use mov %%r%d. . .\n”,c-1);
// see if using r12 (or the dest) here would reduce the size of the
// instruction. answer should be yes if we use the dest.
int size1 = size_instr(&gp, NULL, NULL, hte_query_only);
if Oneof2(size1, unk, bogus) return;
gentab g, *gl = &g;
cvt_to_r_imm_instr(&g, g_MOV, c, limm, cc, f);
int size2 = size_instr(&gl, NULL, NULL, hte_query_only);
cvt_to_rrr_instr(&g, gp_op(gp), a, c, b, cc, f);
int size3 = size_instr(&gl, NULL, NULL, hte_query_only);
if (size2+size3 < size1) {
// the 2-pair sequence will be better . . . .
gentab *mov = Alloc_gen_entry(gp_prev (gp), g_MOV, r_imm);
cvt_to_r_imm_instr (mov, g_MOV, c, limm, cc, f);
printf(“. .deleting (size=%d):\t”, size1);
printf(“. . added (size=%d):\t”, size2);
print_gp (mov);
cvt_to_rrr_instr(gp, gp_op (gp), a, c, b, cc, f);
printf(“. . cvt'ed to (size=%d):\t”, size3);
*_gp = mov;
// example of 16-bit instruction selection.
static int size16_jmp_instr(gentab **_gp, int *isize, int *psize, int hte) {
if (cpt_phase < cpt_shrink_disp_related_instrs) {
// gathering constants, doing cmp-branch, and doing offsets. . .
return size32_jmp_instr(_gp, isize, psize, hte);
arc_delay dd;
IL_condition cc;
get_jmp_call_info(gp, dd, cc);
long that_off = aa55aa55, howfar = that_off;
long this_off = gp.off;
bool found_lab = find_posted_lab(gp, curr_gen_sect, &that_off);
if (dd == delay_d) this_off = next_gen_executable(gp) .off;
if (found_lab) howfar = that_off - this_off;
if (DEBUG_GEN_ARC5) }
printf(“[size16_jmp]”); print_gp (gp);
printf(“[jmp]
found=%c, howfar=%d, this_off=0x%x, that_off=0x%x\n”, “FT”[found_lab], howfar, th
is_off, that_off);
case_32_16(g_Bcc) : {
if (found_lab) switch (cc) }
Cond_GT: case Cond_GE: case Cond_GTU: case Cond_GEU:
Cond_LT: case Cond_LE: case Cond_LTU: case Cond_LEU: {
if (is_s7(howfar)) {
if (hte & hte_query_only) {
chg_to_16b(gp, asi_d7, hte);
return sizeit16(gp, 2, isize, psize);
else if (dd == delay_none) {
// Section 6.15
// bgt s7
// bge s7
// blt s7
// ble s7
// bhi s7
// bhs s7
// blo s7
// bls s7
gp.isize_is_constant = TRUE;
int x = sizeit16(gp, 2, isize, psize);
// need to rewire since no .d on 16-bit
// instructions. To do this, return size of the
// next instruction after rewiring this one to be
// the true next instruction.
gentab *gpl = next_gen_executable (gp);
*_gp = gp1;
rewire(gp, gp1);
if (DEBUG_GEN_ARC5) {
printf(“after rewiring, sizing: ”);
print_gp(*_gp);
printf(“gp-next=”);
print_gp(gp_next(*_gp));
return size_instr(_gp, isize, psize, hte);
case Cond_NULL: case Cond_EQ: case Cond_NE: {
if (is_s9(howfar)) }
if (hte & hte_query_only) }
chg_to_16b(gp, asi_d9, hte);
else if (dd == delay_none) }
// Section 6.14
// b s9
// beq s9
// bne s9
gentab *gp1 = next_gen_executable (gp);
case_32_16(g_BLcc): {
if (cc == Cond_NULL && found_lab) {
if (is_s13(howfar)) {
chg_to_16b (gp, asi_d13, hte);
// Section 6.16
// b1 s13
// instructions. To do this, return the size of the
return size16_unknown(_gp, isize, psize, hte, size32_jmp_instr);
static void try_to_fold_cmp_0(gentab *p, gentab *cmp, gentab *cjmp,
IL_condition cc, Register cmp_ a)
// we expanded a op.f, cjmp to a op, cmp0, cjmp during expand.
// in hopes of saving 2 bytes. But the cjmp turns out to
// be long anyway. So now we attempt to revert back to the
// original op.f,cjmp form for speed since the space saving
// is a wash.
bool *fp = 0; // pointer to .f flag in instr
Register rd = null_reg;
class_type k = gp_klass(p);
case rrr_INSTR: case rrr_16b_INSTR:
rd = get_(p, rrr, a);
fp = &p->un.rrr.f;
k = rrr_INSTR;
case rr_INSTR: case rr_16b_INSTR:
rd = get_(p, rr, a);
fp = &p->un.rr.f;
k = rr _INSTR;
case rr_imm_INSTR: case rr_imm_16b_INSTR:
rd = get_(p, rr_imm, a);
fp = &p->un.rr_imm.f;
k = rr_imm_INSTR;
case r_imm_INSTR: case r_imm_16b_INSTR:
rd = get_(p, r_imm, a);
fp = &p->un.r_imm.f;
k = r_imm_INSTR;
if (rd == cmp_a)
cg_opcode newop = gp_op(p);
// select 32-bit form
switch (newop)
case g_ADD_16: newop = g_ADD; break;
case g_AND_16: newop = g_AND; break;
case g_ASL_16: newop = g_ASL; break;
case g_ASR_16: newop = g_ASR; break;
case g_BIC_16: newop = g_BIC; break;
case g_EXT_16: newop = g_EXT; break;
case g_LSL_16: newop = g_LSL; break;
case g_LSR_16: newop = g_LSR; break;
case g_MOV_16: newop = g_MOV; break;
case g_OR_16: newop = g_OR; break;
case g_SEX_16: newop = g_SEX; break;
case g_SUB_16: newop = g_SUB; break;
case g_XOR_16: newop = g_XOR; break;
case g_BSET_16: newop = g_BSET; break;
case g_BCLR_16: newop = g_BCLR; break;
case g_BXOR_16: newop = g_BX0R; break;
case g_BMSK_16: newop = g_BMSK; break;
case g_NOT_16: newop = g_NOT; break;
// case g_NEG_16: newop = g_NEG; break;
case g_ADD1_16: newop = g_ADD1; break;
case g_ADD2_16: newop = g_ADD2; break;
case g_ADD3_16: newop = g_ADD3; break;
// do the transform . . .
gp_op(p) = newop;
gp_klass(p) = k;
*fp = TRUE; // set .f
p->isize = p->isize >4 ? 8 : 4; // modify size
// convert cjmp
gp_klass(cjmp) = jmp_INSTR;
gp_op(cjmp) = g_Bcc;
cjmp->isize = 4;
cjmp->un.jmp.cc = cc == Cond_LT ? Cond_MI : CondPL;
// remove cmp, but keep linked becaus do_branch is using it.
unlink_gen(cmp);
static void do_branch_reductions(void) {
if (!branch_reductions_tog)
start_phase(CMPJMP_PHASE);
do_lp_count_nop_reduction( );
if (DEBUG_CMPJMP) {
print_info(“gentab before branch reduction”, NULL);
int did_something = 0;
for _gp <- each_gentab_entry(func_gentab_block) do {
gentab *cmp = *_gp;
if (!Oneof4(gp_op(cmp), g_CMP, g_CMP_16, g_BTST, g_BTST_16)) continue;
gentab *pjmp = prev_gen_exec_or_lab(cmp);
if (pjmp) {
// bits_INSTR can have a CMP in the delay slot since the code
// preserves %status across the call that we generate
IL_condition pcc;
arc_delay pdd;
get_jmp_call_info(pjmp, pdd, pcc);
if (pdd == delay_d) continue;
IL_ condition cc = Cond_EQ;
printf(“[cmpjmp] looking at: ”); print_gp(cmp);
Register cmp_a = null_reg,cmp_b = null_reg;
int cmp_val = 0;
bool isimm = FALSE;
switch (gp_klass(cmp)) {
case rr_16b INSTR: case rr_INSTR:
cc = get_Tcmp, rr, cc);
cmp_a = get_(cmp, rr, a);
cmp_b = get_(cmp, rr, b);
case r_imm_16b_INSTR: case r_imm_INSTR:
cc = get_(cmp, r_imm, cc);
cmp_a = get (cmp, r_imm, a);
cmp_val= get_(cmp, r_imm, limm);
isimm = TRUE;
if (cc != Cond NULL) {
if (DEBUG_CMPJMP) printf(“. . cmp has condition code: failed!\n”);
gentab *branch = cmp;
int validate(gentab **branch) {
if (is_bb_delimiter(*branch)) {
printf(“. . this interferes with cmp moving: ”);
print_gp(*branch);
*branch = NULL;
for r,rut <- gen_reg_used(*branch) do {
if (rut == used_referenced && r == STATUS_REG | |
rut == used_defined && Oneof3(r, cmp_a, cmp_b, STATUSREG)) {
// we can't move the compare down since instruction
// redefines one of the cmp regs. (or needs the status
// reg itself)
printf(“. . skip over: ”); print_gp(*branch);
while (branch = gp_next(branch),branch != NULL &&
!Oneof2(gp_op(branch), g_Bcc_16, g_Bcc)) {
if (!validate(&branch)) goto L1;
L1: ;
if (!(branch && Oneof2(gp_klass(branch), jmp_INSTR, jmp_16b_INSTR))) {
printf(“. . cmp can't be moved: failed!\n”);
printf(“. . found: ”); print_gp(branch);
gentab *delay_slot = NULL;
if (get_(branch, jmp, dd) != delay_none) {
delay_slot = gp_next(branch);
if (!validate(&delay_slot)) {
else if (DEBUG_CMPJMP) {
printf(“. . found delay slot: ”); print_gp(delay_slot);
// we now have something like:
// 001a 0000 cmp_s %r0,0
// 001c 0000 bgt_s .LN178.6
IL_condition cjmp_cc = get_(branch, jmp, cc);
int keep_delay_slot_as_delay_slot = 1;
switch (cjmp_cc) {
case Cond_EQ: case Cond_NE:
// there are no compressed forms of the rest of the Conds.
// we rewire the delay-slot for these 2 only in the hope
// that we compress this cmpjmp instruction.
keep_delay_slot_as_delay_slot = 0;
case Cond_GEU: case Cond_LTU:
case Cond_LT: case Cond_GE:
case Cond_LEU: case Cond_GTU:
case Cond_LE: case Cond GT:
if (DEBUG_CMPJMP) printf(“. . bad IL_condition: failed!\n”);
if (get_(branch, jmp, ccreg_live)) {
if (DEBUG_CMPJMP) printf(“. . status reg must be set: failed\n”);
long that_off = 0;
bool found_lab = find_posted_lab(branch, curr_gen_sect, &that_off);
if (!found_lab) {
if (DEBUG_CMPJMP) printf(“. . labdef not found: failed!\n”);
long this_off = branch.off - cmp.isize;
if (delay_slot) {
if (this_off > that_off && !keep_delay_slot_as_delay_slot) {
// backword branch, account for the size of the delay slot
// that will be moved up
this_off += delay_slot->isize;
// adjust for possible PCL truncation. Problem is that we think
// we're on an OK address (0×1660) and we're jumping to 0×175c
// which looks ok. But after we delete the CMP, the jmp is at
// 0×165e which the processor will back up to 0×165c (PCL is used
// for branch instructions). So we need to always take the size
// of the cmp into account and adjust our offset and then
// truncate it down to what the PCL will use. Note: for backward
// branches, this gives us a little more room since the
// PCL will be to our advantage. Forward references thus have a
// offset of 252 bytes due to the PCL. Backward branches have
// an offset of −256 (under some rare conditions, we could go
// back −258, but the assembler may not allow it). So for forward
// jumps, we'll back up 2.
if (this_off & 3) this_off &= ~3;
printf(“. . found
lab,lab offset=0x%04.4x,t his_off=0x%04.4x,howfar=%d, is-
s9=%c\n”, that_off, this_off, that_off-this_off, “FT”[is_s9(that_off-
this_off)]);
if (!is_s9(that_off-this_off)) {
// before continue, look to remove the compare
// We might have a comp 0 that can be folded into the
// previous .f instr. This happens because we unfolded
// them in code.cc to try to eliminate 4-byte PL/MI cjmps
if (isimm && cmp_val== 0 && Oneof2(cjmp_cc, Cond_GE, Cond_LT)) {
gentab *p = gp_prev(cmp);
if (p) try_to_fold_cmp_0(p, cmp, branch, cjmp_cc, cmp_a);
// merge them . . . Note: if there was a delay slot, then we'll
// be inserting the new instruction after the delay slot.
int rewire = delay_slot && !keep_delay_slot_as_delay_slot;
gentab *after = branch;
if (rewire) after = delay_slot;
gentab *cjmp = merge(cmp, branch, after, rewire);
cjmp.off = this_off;
compression_pass_type scpt = cpt_phase;
// size the cmp and branch as well as the cmpjmp to see if
// we really want to use the cmpjmp. If the actual size is going
// to be bigger, then we don't want to use it. To get the actual
// size though will require us to change the phase so that
// gen_arc5.cc doesn't assume worst case. It's ok though, we're
// querying it only, so we will get the actual size, but the
// instruction won't be changed.
cpt_phase = cpt_shrink_disp_related_instrs;
int csize = size_instr(&cmp, NULL, NULL, hte_query_only);
int bsize = size_instr(&branch, NULL, NULL, hte_query_only);
int cbsize = size_instr(&cjmp, NULL, NULL, hte_query_only);
cpt_phase = scpt;
int osize = csize + bsize;
if (Oneof3(unk, csize, bsize, cbsize) | |
Oneof3(bogus, csize, bsize, cbsize) | |
cbsize > osize) {
printf(“. . csize=%d, bsize=%d, cbsize=%d: too big: failed!\n”,
csize,bsize,cbsize);
delete_gen(cjmp);
redo_downstream_ offsets(cmp);
// ok, 1 now we can use it . . . .
printf(“chg (size=%d) : ”, cmp.isize); print_gp(cmp);
printf(“and (size=%d): ”, branch.isize); print_gp(branch);
printf(“into: (size=%d): ”, cjmp.isize); print_gp(cjmp);
gentab *pgp = gp_prev(cmp);
delete_gen(cmp);
delete_gen(branch);
if (delay_slot) delay_slot->stopper = st_no_stopper;
did_ something++;
*_gp = cjmp;
redo_downstream_offsets(pgp);
if (did_ something) {
// may have shrunk enough branches down to allow other reductions
do_branch_reductions( );
else if (trace_compress_tog | | DEBUG_CMPJMP) {
print_info(“gentab after branch reduction”, NULL);
stop_phase(CMPJMP_PHASE);
// routine to determine if number-of-instrs (cnt) is within
// the limit based on cuirrent model.
static bool icount_within_range(int cnt)
int max_ops = 0;
if (xmult32_tog) {
if (optimize_for_space) max_ops = 1;
// the fast multiplier is 2 clks. The slow is 10.
// maybe we need a -X to tell us to use the slow . . .
max_ops = 2;
else if (optimize_for_space) max_ops = 8;
else max_ops = 17;
//fprintf(stderr, “cnt=%d,max_ops=%d\n”, cnt, max_ops);
return (max_ops >= cnt);
// insert_mpyadd
// used to generate pseudo.MPYADD/MPYSUB instruction
static IL_entry * insert_mpy_pseudo(IL_entry *p, int pseudo, int
Register dest, Register src1, Register src2)
p = alloc_n_after(p, il_PSEUDO, REGSIZE, 1, 3);
DEST1(p).type = REG_i; SET_oREG(DEST1(p), dest);
SRC1(p).type = REG_i; SET_oREG(SRC1(p), src1);
SRC2(p).type = REG_i; SET_oREG(SRC2(p), src2);
make_int_opd(&SRC3(p), multiplier);
SET_ PSEUDO _NO(p,pseudo);
// mikes_screwy_factors(. .)
// return list of factors; return 0 if cant be factored conveniently.
// If this routine returns 0, then we fall back on original constmpy
// These are actial factors -- not just bit shifts. So the
// array is an int array.
// e.g. . . . .
// 30 --> 2 * 5 * 3
// −28 -> −7 * 4
// work area (saved for posterity. . . . .
// 1: neg
// 2:lsl 1 add,ne (4)
// 3:addl sub2 (4)
// 4: lsl 2 lsl 2; neg (4)
// 5 add2 add2; neg (4)
// 6: add; add1; (4) add; sub3 (6)
// 7: lsl 3; sub (4) sub3; (4)
// 8: lsl 3 lsl 3; neg (4)
// 9: add3; neg; add3 (4)
// 10: add; add2 (4) neg (6)
// 11: add3; add1 (6) neg (8)
// 12: lsl 2; add1 (4) lsl 2; sub2 (6)
// 13:
// 14: lsl 4; sub1 (6) add; sub3 (6)
// 15: add1; add2 (4) sub2; add2 (6)
// 16: lsl 4 neg
// 17: lsl 4; add (4) neg
// 18: add; add3 (4) neg
// 19: lsl 4; add2; sub (6) neg
// 20: lsl 2; add 2 neg
// 21: 7 * 3 (6) sub3, add1
static int mikes_screwy_factors(int *factors, int val);
static void display_factors(int val, int fc, int *facts)
printf(“FACTORS FOR %3d cnt=%d”, val, fc);
for (x = 0; x < fc; x++) printf (“ %d”, facts[x]);
printf(“\n”) ;
static int find_fact(int val, int *facts, int *rem)
int *xp;
for (xp = facts; *xp; xp ++)
int fl = val / *xp;
int ml = val % *xp;
if (ml == 0) { *rem = fl; return *xp; }
static int factor (int *factors, int m, int rem)
factors [0] = m;
if (rem == 1) return 1;
int x = mikes_screwy_factors (factors + 1, rem);
if (x) x ++;
static int mikes_ screwy_ factors(int *factors, int val)
// arrays of optimal factors for positve and negative multipliers
static int pfacts[ ] ={ 9, 5, 3, 0 };
static int nfacts[ ] ={ 7, 3, 0 };
int fc = 0;
int x, rem;
int av = _abs (val);
if (val == 0×80000000) return 0;
x = find_fact(av, nfacts, &rem);
// special caveate for factor −3. . . if −9 is also a factor, abort
if (x == 0 | | x == 3 && (av % 9) == 0) x = 1, rem = av;
return factor(factors, −x, rem);
// positive val
// look for power of 2
if ((val & 3) == 2) x++, val >>= 1);
else if (xbarrel_shifter_tog)
for (x = 0; (val & 1) == 0; x++, val >>= 1);
if (x) return ( factor(factors, 1<<x, val));
// now try screwy positive factors
x = find_fact(val, pfacts, &rem);
if (x) return factor(factors, x, rem);
static bool reduce_mikes _screwy_factors(IL_entry *il, int fc, int *facts)
Register src = oREG(SRC1(il));
Register dest = oREG(DEST(il));
IL_entry *p = il;
int shiftby = 0;
// According to factor, produce mult instruction
for (int x = 0; x < fc; x++)
int f = facts[x];
// negative factors are either −1, −3 or −7
if (f == −1)
p = insert_rr(p, il_NEG, 4, dest, src, FALSE);
// −3 or −7
p = insert_mpy_pseudo(p, MPYSUB_func, −f + 1, dest, src, src);
else, if (power_of_two(f, &shiftby))
p = insert_rrr(p, il_ADD, 4, dest, src, FALSE, src, FALSE);
p= insert_rri(p, il_SLL, 4, dest, src, FALSE, shiftby);
else // positive factor
p = insert_mpy_pseudo(p, MPYADD_func, f-1, dest, src, src);
// now set src to dest -- all other computation is destructive
src = dest;
if (trace_expand) {printf(“. . added: ”); print_il (p);)
unlink_il(il, NULL);
static int shift_cnt(unsigned x) {
// examples . . .
// x=y*32
// mov z,0
// add3 t1, z, y; y*8
// add2 x, z, t1; (y*8)*4
// x=y*256
// add3 t1, z, y; y*8
// add3 t2, z, t1; (y*8)*8
// add2 x, z, t2; ((y*8)*8)*4)
if (xswap_tog && x >= 16) {
// easy way to get rid of 16-bits: mask and then swap
swap = 2; x -= 16;
int add3s = x / 3; x -= (add3s * 3);
int add2s = x / 2; x -= (add2s * 2);
int add1s = x;
return add3s+add2s+add1s+swap;
// Rotine to take a stand-alone multiplier const and determine
// if it is factorable or reducable without knowing anything
// else about its context.This is required for immediat_opd_permitted
PUBLIC bool will_reduce_mpy(Register dst, Register src, long multiplier,
signed char stack[17], int *sp, int from_ssa);
PUBLIC bool mpy_is_factorable(int val)
int facts[32];
int ic = mikes_screwy_factors(facts, val);
if (ic) return icount_within_range(ic);
signed char stack[17];
return will_reduce_mpy(R0, R1, val, stack, &dummy, FALSE);
// Routine to examine an IL as to whether it is recudable
PUBLIC bool will_ reduce_mpy(Register dst, Register src, long multiplier,
signed char stack[17], int *sp, int from_ssa) {
static int facts[32];
int ic = mikes_screwy_factors(facts, multiplier);
*sp = constmpy(multiplier < 0 ? -multiplier : multiplier, stack);
// calculate out how many instructions this will take
int k = *sp, cnt = (src == dst | | from_ssa) ? 2 : 0;
int ts = stack[--k];
int shift = _abs(ts);
case 1. . 3:
if (ts > 0) {
// we can generate MPYADD sequence
/* fall-thru */
if (!xbarrel_shifter_tog) {
// we can only do one bit at a time (unless we can
// generate a smaller sequence off addX/shifts)
int icnt = shift_cnt(shift);
cnt += icnt;
// see comments below on why we need to generate SUB
// each shift-by requres a shift and an add/sub
if (multiplier < 0 && (-multiplier != multiplier)) {
// we need to negate the results
// ok, we now have the number of shifts/adds, mpyadds, and mpysubs
// that we will need. Is it profitable to do so?
return icount_within _range(cnt);
PUBLIC bool a5_reduce_MPY(IL_entry *il, int from_ssa,
Register (*get_reg)(type_class tc, int len, IL_entry *il)) {
if (il->len > REGSIZE) return FALSE;
int fstack[17];
long multiplier = int_value(SRC2(il));
if (il->op == il_SLL) multiplier = 1 << multiplier;
int len = il->len;
il->op = il_LI;
make_int_opd(&SRC1(i1),0);
// fc indicates number of factors
// if we found a way to reduce it to these factors, then
// the sequence will always be smaller/faster then the normal way
// So jump to the special routine for these factors
int fc = mikes _ screwy_ factors(fstack, multiplier);
if (fc) return reduce mikes_screwy_factors(il, fc, fstack);
Register dest = oREG(DEST1(il));
if (!will_reduce_mpy(dest, src, multiplier, stack, &sp, from_ssa))
// ok, now generate the instructions
Register original_src = src;
// for non-fc model use temp reg if needed
if (sp > 1 && src == dest) {
original_src = TEMP_REG;
p = insert_rr(p, il_COPY, len, original src, src, TRUE);
if (trace_expand) {printf(“. . added: ”); print_il(p); }
Register zreg = null_reg;
int ts = 0,shift_amount = 0;
IL_opcode op = il_ADD;
void make_mpyadd(int shift_amount, Register original_src) {
p = alloc_IL_after(p, il_PSEUDO, REGSIZE, 1, 3);
SRC1(p).type = REG_i; SET_oREG(SRC1(p), original_src);
SRC2(p).type = REG_i; SET_oREG(SRC2(p), src);
make_int_opd (&SRC(p), 1 << shift_amount);
SET_PSEUEDO_NO (p, MPYADD func);
if trace_expand) {printf (“. . added: ”); print_il(p); }
void maybe_cvt_to_lsl (void) {
if (p->op == il_PSEUDO &&
int_value(SRC3(p) ) == 2 && oREG(SRC1(p) ) == zreg) {
// let this shrink down to a compresssable instr.
p->op = il_SLL;
p->cond = Cond_NULL;
SRC1(p) = SRC2(p);
make_int_opd (&SRC2(p),1);
p->set_src_cnt(2);
if (trace_expand) {printf(“. . changed: ”); print_il(p);}
void do _shifts(void) {
if (zreg == null_reg) (
IL_entry *li = alloc_IL_after(p, il_LI, REGSIZE,1,1);
make_int_opd (&SRC1(li), 0);
zreg = get_reg(tc_INT, REGSIZE, li);
DEST1(li).type = REG_i;
SET_oREG (DEST1(li), zreg);
p = li;
if (trace_expand) {printf(“. . added: ”); print_il(p);}
if (xswap_tog && shift_amount >= 16) {
p = insert_rri(p,il_AND, len, dest, src, FALSE, 0xffff);
p = insert_rr(p,il PSEUDO, len, dest, src, FALSE);
SET_PSEUDO_NO (p, ARC_SWAP_func);
shift_ amount −= 16;
if (trace_expand) {printf (“. . added: ”); print_il(p);)
int add3s = shift_amount / 3; shift_amount −=(add3s * 3);
for (int i = 0; i < add3s; i++) {
make_mpyadd(3, zreg);
int add2s = shift_amount / 2; shift_amount −=(add2s * 2);
for (int j = 0; j < add2s; j++) {
make_mpyadd(2, zreg);
int addls = shift_amount;
for (int k = 0; k < addls; k++) {
make_mpyadd(1, zreg);
while (sp > 1) {
ts = stack[--sp];
if (ts < 0) {shift_amount = −ts; op = il_SUB; }
else {shift_amount = ts; op = il_ADD; }
if (Oneof3(shift_amount, 1, 2, 3) && op == il_ADD) {
make_mpyadd(shift_amount, original_src);
else if (xbarrel_shifter_tog) {
p = insert_rri(p, il_SLL, len, dest, src, FALSE, shift_amount);
if (trace_expand) {printf(“. . added: ”); print_il(p);)
p = insert_rrr(p, op, len, dest, dest, FALSE, original_src, FALSE);
if (trace_expand) (printf(“. . added: ”); print_il (p);)
do_shifts( );
if (op == il_ADD) {
// fixup last mpyadd to reflect the next add as well
SET_oREG(SRC1(p), original_src);
if (trace_expand) {printf(“. . added: ”); print_il (p);}
// we need to generate the SUB because of
// signedness problems. The problem is that we
// don't know the sign of the first src.
maybe_cvt_to_lsl( );
insert_rrr(p, il_SUB, len, dest, dest, 0, original_src,0);
if (stack[0]) {
// this last one is always a positive shift
shift_amount = stack[0];
if (xbarrel_shifter_tog) {
p = insert_rri(p, il_SLL, len, dest, src, FALSE, stack[0]);
if (trace_expand) (printf(“ . . added: ”); print_il(p);}
if (multiplier < 0 && (−multiplier != multiplier)) {
p = insert_rr(p, il_NEG, len, dest, src, FALSE);
if (src != dest) {
p = insert_rr(p, il_COPY, len, dest, src, FALSE);
US4571678 5 nov. 1982 18 fev. 1986 International Business Machines Corporation Register allocation and spilling via graph coloring
US4763242 23 out. 1985 9 ago. 1988 Hewlett-Packard Company Computer providing flexible processor extension, flexible instruction set extension, and implicit emulation for upward software compatibility
US4827427 5 mar. 1987 2 maio 1989 Hyduke Stanley M Instantaneous incremental compiler for producing logic circuit designs
US4956800 17 jun. 1988 11 set. 1990 Hitachi, Ltd. Arithmetic operation processing apparatus of the parallel processing type and compiler which is used in this apparatus
US4965724 29 fev. 1988 23 out. 1990 Oki Electric Industry Co., Ltd. Compiler system using reordering of microoperations to eliminate interlocked instructions for pipelined processing of assembler source program
US5088034 25 jan. 1989 11 fev. 1992 Hitachi, Ltd. Compiling method for determining programs to be executed parallelly by respective processors in a parallel computer which transfer data with a data identifier to other processors
US5105353 11 ago. 1989 14 abr. 1992 International Business Machines Corporation Compressed LR parsing table and method of compressing LR parsing tables
US5247668 8 dez. 1992 21 set. 1993 Vlsi Technology, Inc. Methods of realizing digital signal processors using a programmed compiler
US5249295 8 mar. 1993 28 set. 1993 Rice University Digital computer register allocation and code spilling using interference graph coloring
US5274818 3 fev. 1992 28 dez. 1993 Thinking Machines Corporation System and method for compiling a fine-grained array based source program onto a course-grained hardware
US5287510 11 fev. 1991 15 fev. 1994 International Business Machines Corporation Method for improving the efficiency of arithmetic code generation in an optimizing compiler using machine independent update instruction generation
US5293631 6 ago. 1991 8 mar. 1994 Hewlett-Packard Company Analysis and optimization of array variables in compiler for instruction level parallel processor
US5339424 17 abr. 1992 16 ago. 1994 Mitsubishi Denki Kabushiki Kaisha System and method for compiling and executing a computer program written in more than one programming language
US5428793 13 nov. 1989 27 jun. 1995 Hewlett-Packard Company Method and apparatus for compiling computer programs with interproceduural register allocation
US5448746 25 jan. 1994 5 set. 1995 International Business Machines Corporation System for comounding instructions in a byte stream prior to fetching and identifying the instructions for execution
US5450585 15 maio 1991 12 set. 1995 International Business Machines Corporation Compiler with delayed conditional branching
US5481723 27 fev. 1995 2 jan. 1996 Digital Equipment Corporation System and method for controlling execution of nested loops in parallel in a computer including multiple processors, and compiler for generating code therefore
US5488710 10 fev. 1992 30 jan. 1996 Fujitsu Limited Cache memory and data processor including instruction length decoding circuitry for simultaneously decoding a plurality of variable length instructions
US5546552 12 maio 1995 13 ago. 1996 Seiko Epson Corporation Method for translating non-native instructions to native instructions and combining them into a final bucket for processing on a host processor
US5555417 23 jan. 1995 10 set. 1996 Hewlett-Packard Company Method and apparatus for compiling computer programs with interprocedural register allocation
US5586020 23 fev. 1995 17 dez. 1996 Nec Corporation Program transformation processing system and method
US5636352 16 dez. 1994 3 jun. 1997 International Business Machines Corporation Method and apparatus for utilizing condensed instructions
US5638525 10 fev. 1995 10 jun. 1997 Intel Corporation Processor capable of executing programs that contain RISC and CISC instructions
US5740461 22 out. 1996 14 abr. 1998 Advanced Risc Machines Limited Data processing with multiple instruction sets
US5752035 * 7 jun. 1995 12 maio 1998 Xilinx, Inc. Method for compiling and executing programs for reprogrammable instruction set accelerator
US5790854 3 ago. 1995 4 ago. 1998 Motorola Inc. Efficient stack utilization for compiling and executing nested if-else constructs in a vector data processing system
US5790877 3 jul. 1996 4 ago. 1998 Hitachi, Ltd. Method for controlling a processor for power-saving in a computer for executing a program, compiler medium and processor system
US5794010 10 jun. 1996 11 ago. 1998 Lsi Logic Corporation Method and apparatus for allowing execution of both compressed instructions and decompressed instructions in a microprocessor
US5809272 29 nov. 1995 15 set. 1998 Exponential Technology Inc. Early instruction-length pre-decode of variable-length instructions in a superscalar processor
US5809306 16 jan. 1996 15 set. 1998 Matsushita Electric Industrial Co., Ltd. Variable address length compiler and processor improved in address management
US5819058 28 fev. 1997 6 out. 1998 Vm Labs, Inc. Instruction compression and decompression system and method for a processor
US5828884 23 maio 1996 27 out. 1998 Advanced Micro Devices, Inc. Method for compiling a software program and executing on a system which converts data between different endian formats
US5845127 15 jul. 1996 1 dez. 1998 Nec Corporation Language processor and language processing method to generate object programs by compiling source programs
US5850551 22 jan. 1996 15 dez. 1998 Matsushita Electric Industrial Co., Ltd. Compiler and processor for processing loops at high speed
US5864704 10 out. 1995 26 jan. 1999 Chromatic Research, Inc. Multimedia processor using variable length instructions with opcode specification of source operand as result of prior instruction
US5867681 23 maio 1996 2 fev. 1999 Lsi Logic Corporation Microprocessor having register dependent immediate decompression
US5870576 16 dez. 1996 9 fev. 1999 Hewlett-Packard Company Method and apparatus for storing and expanding variable-length program instructions upon detection of a miss condition within an instruction cache containing pointers to compressed instructions for wide instruction word processor architectures
US5878267 29 maio 1998 2 mar. 1999 Philips Electronics North America Corporation Compressed instruction format for use in a VLIW processor and processor for processing such instructions
US5881260 9 fev. 1998 9 mar. 1999 Hewlett-Packard Company Method and apparatus for sequencing and decoding variable length instructions with an instruction boundary marker within each instruction
US5884057 8 maio 1995 16 mar. 1999 Exponential Technology, Inc. Temporal re-alignment of a floating point pipeline to an integer pipeline for emulation of a load-operate architecture on a load/store processor
US5896519 10 jun. 1996 20 abr. 1999 Lsi Logic Corporation Apparatus for detecting instructions from a variable-length compressed instruction set having extended and non-extended instructions
US5905893 10 jun. 1996 18 maio 1999 Lsi Logic Corporation Microprocessor adapted for executing both a non-compressed fixed length instruction set and a compressed variable length instruction set
US5946491 6 jun. 1996 31 ago. 1999 International Business Machines Corporation Register allocation method and apparatus for gernerating spill code as a function of register pressure compared to dual thresholds
US5946492 19 fev. 1997 31 ago. 1999 International Business Machines Corporation Compiler that reduces call stack size through identification of stackless variables
US5948100 17 nov. 1997 7 set. 1999 Industrial Technology Research Institute Branch prediction and fetch mechanism for variable length instruction, superscalar pipelined processor
US5961632 25 jul. 1997 5 out. 1999 Texas Instruments Incorporated Microprocessor with circuits, systems, and methods for selecting alternative pipeline instruction paths based on instruction leading codes
US6090156 15 maio 1998 18 jul. 2000 International Business Machines Corporation System for local context spilling for graph coloring register allocators
US6158046 21 fev. 1997 5 dez. 2000 Sharp Kabushiki Kaisha Computer device and method for processing data utilizing pseudoinstruction words
US6209079 1 maio 2000 27 mar. 2001 Mitsubishi Denki Kabushiki Kaisha Processor for executing instruction codes of two different lengths and device for inputting the instruction codes
US6260189 14 set. 1998 10 jul. 2001 Lucent Technologies Inc. Compiler-controlled dynamic instruction dispatch in pipelined processors
US6275830 18 mar. 1998 14 ago. 2001 Oracle Corporation Compile time variable size paging of constant pools
US6282633 13 nov. 1998 28 ago. 2001 Tensilica, Inc. High data density RISC processor
US6292940 26 jan. 1999 18 set. 2001 Nec Corporation Program complete system and its compile method for efficiently compiling a source program including an indirect call for a procedure
US6305013 1 abr. 1999 16 out. 2001 Nec Corporation Compiling method for generating target program in accordance with target processor type, compiling device, recording medium with compiling program recorded therein and recording medium with conversion table used in compiling recorded therein
US6308323 27 maio 1999 23 out. 2001 Kabushiki Kaisha Toshiba Apparatus and method for compiling a plurality of instruction sets for a processor and a media for recording the compiling method
US6334212 31 mar. 1999 25 dez. 2001 Matsushita Electric Industrial Co., Ltd. Compiler
US6367071 2 mar. 1999 2 abr. 2002 Lucent Technologies Inc. Compiler optimization techniques for exploiting a zero overhead loop mechanism
US6408382 21 out. 1999 18 jun. 2002 Bops, Inc. Methods and apparatus for abbreviated instruction sets adaptable to configurable processor architecture
US6412066 5 abr. 2001 25 jun. 2002 Lsi Logic Corporation Microprocessor employing branch instruction to set compression mode
US6425070 18 mar. 1998 23 jul. 2002 Qualcomm, Inc. Variable length instruction decoder
US6463520 4 mar. 1997 8 out. 2002 Mitsubishi Denki Kabushiki Kaisha Processor for executing instruction codes of two different lengths and device for inputting the instruction codes
US6477683 5 fev. 1999 5 nov. 2002 Tensilica, Inc. Automated processor generation system for designing a configurable processor and method for the same
US6477697 28 maio 1999 5 nov. 2002 Tensilica, Inc. Adding complex instruction extensions defined in a standardized language to a microprocessor design to produce a configurable definition of a target instruction set, and hdl description of circuitry necessary to implement the instruction set, and development and verification tools for the instruction set
US6564314 7 jun. 1995 13 maio 2003 Sgs-Thomson Microelectronics Limited Computer instruction compression
US6678818 2 maio 2000 13 jan. 2004 Stmicroelectronics S.A. Decoding next instruction of different length without length mode indicator change upon length change instruction detection
US6694511 4 dez. 1998 17 fev. 2004 Sony Corporation Data processing method and device
US6701515 27 maio 1999 2 mar. 2004 Tensilica, Inc. System and method for dynamically designing and evaluating configurable processor instructions
US6732238 10 jun. 2002 4 maio 2004 Tensilica, Inc. Set-associative cache memory having variable time decay rewriting algorithm
US6760888 1 nov. 2002 6 jul. 2004 Tensilica, Inc. Automated processor generation system for designing a configurable processor and method for the same
US6763327 17 fev. 2000 13 jul. 2004 Tensilica, Inc. Abstraction of configurable processor functionality for operating systems portability
US6826681 * 18 jun. 2001 30 nov. 2004 Mips Technologies, Inc. Instruction specified register value saving in allocated caller stack or not yet allocated callee stack
US6862563 14 out. 1999 1 mar. 2005 Arc International Method and apparatus for managing the configuration and functionality of a semiconductor design
US6889313 2 maio 2000 3 maio 2005 Stmicroelectronics S.A. Selection of decoder output from two different length instruction decoders
US7103881 10 dez. 2002 5 set. 2006 Intel Corporation Virtual machine to provide compiled code to processing elements embodied on a processor device
US7120903 24 set. 2002 10 out. 2006 Nec Corporation Data processing apparatus and method for generating the data of an object program for a parallel operation apparatus
US7140008 25 nov. 2002 21 nov. 2006 Microsoft Corporation Dynamic temporal optimization framework
US7203935 5 dez. 2002 10 abr. 2007 Nec Corporation Hardware/software platform for rapid prototyping of code compression technologies
US7558462 1 jul. 2003 7 jul. 2009 Sony Corporation Reproduction device and content information reproduction method
US20010013093 * 7 fev. 2001 9 ago. 2001 Kabushiki Kaisha Toshiba Instruction code conversion unit and information processing system and instruction code generation method
US20020004897 27 dez. 2000 10 jan. 2002 Min-Cheng Kao Data processing apparatus for executing multiple instruction sets
US20020073299 28 set. 2001 13 jun. 2002 Pechanek Gerald G. Methods and apparatus for scalable instruction set architecture with dynamic compact instructions
US20020073407 19 out. 2001 13 jun. 2002 Shuichi Takayama Processor for executing instructions in units that are unrelated to the units in which instructions are read, and a compiler, an optimization apparatus, an assembler, a linker, a debugger and a disassembler for such processor
US20020116603 21 fev. 2001 22 ago. 2002 Ownership Configurable instruction sequence generation
US20030140337 21 dez. 2001 24 jul. 2003 Celoxica Ltd. System, method, and article of manufacture for data transfer reporting for an application
US20030225998 31 jan. 2003 4 dez. 2003 Khan Mohammed Noshad Configurable data processor with multi-length instruction set architecture
WO2003091914A1 25 abr. 2003 6 nov. 2003 Arc International Apparatus and method for managing integrated circuit designs
1 "An Introduction to Thumb", Version 2.0, Mar. 1995.
2 "Embedded Control Problems, Thumb, and the ARM7TDMI"; Segas, et al.; 1995; IEEE.
3 "TriCore 1.3, Architecture Overview Handbook", V1.3.3, May 2002.
4 An Overview of the PL.8 Compiler by M. Auslander and M. Hopkins, IBM T.J. Watson Research Center, 1982, pp. 22-31.
5 Article entitled "The JCN Embedded Processor" by AT&T Laboratories Cambridge (modified Jun. 6, 2002, © 2001) (3 pages) (http://www.uk.research.att.com/jen/).
6 Avaz Product Information Sheets on Mozart2 Fully Synthesizable DSP Core, 2 pages, [Online] [Retrieved on Jun. 30, 2003] Retrieved from the Internet.
7 Avaz Product Information Sheets on Mozart2 Fully Synthesizable DSP Core, 2 pages, [Online] [Retrieved on Jun. 30, 2003] Retrieved from the Internet<URL:http://www.avaz.com/products/cores/dspcore/mozart2/>.
8 Chaitin, G., "Register Allocation and Spilling Via Graph Coloring," Best of PLI 1979-1999, ACM SIGPLAN, 1982, pp. 66-74.
9 Collin, M. et al., "Low Power Instruction Fetch Using Profiled Variable Length Instructions," Dept. of Microelectronics and Information Technology, 2003 Proceedings of the IEEE International Systems-on-Chip Conference, Sep. 17-20, 2003, 17 pages.
10 Drinic, et al, "Code Optimization for Code Compression", IEEE, pp. 315-324, 2003.
11 * G. J. Chaitin, "Register Allocation $ Spilling Via Graph Coloring", 1982 ACM 0-89791-074-5/82/006/0098.
12 Global Optimization by Suppression of Partial Redundancies by E. Morel and C. Renvoise, CII Honeywell Bull, Communications of the ACM, Feb. 1979, vol. 22, No. 2, pp. 96-103.
13 Heads and Tails: A Variable-Length Instruction Format Supporting Parallel Fetch and Decode by Heidi Pan and Krste Asanovic, Nov. 16-17, 2001, 8 pages.
14 High Performance, Variable-Length Instruction Encodings by Heidi Pan, submitted to the Dept. of Electrical Engineering and Computer Science, Mass. Instit. of Technology, May 2002, 53 pages.
15 IEEE Std. 1076.3-1997 IEEE Standard VHDL Synthesis Packages-Description, Abstract only, copyright 2004, 2 pages.
16 IEEE Std. 1076.3-1997 IEEE Standard VHDL Synthesis Packages—Description, Abstract only, copyright 2004, 2 pages.
17 Improving Register Allocation for Subscripted Variables by David Callahan, Steve Carr and Ken Kennedy, copyright 2003, 2 pages.
18 Intel 80386 Programmer's Reference Manual-Section 17.1, "17.1 Operand-Size and Address-Size Attributes," [Online] [Retrieved on Jun. 30, 2003] Retrieved from the Internet.
19 Intel 80386 Programmer's Reference Manual—Section 17.1, "17.1 Operand-Size and Address-Size Attributes," [Online] [Retrieved on Jun. 30, 2003] Retrieved from the Internet<URL:http://webster.cs.ucr.edu>.
20 Intel Pentium Processor Family Developer's Manual-vol. 3: Architecture and Programming Manual (1995) (cover pages, pp. 3-15 to 3-18, pp. 25-189 to 25-192).
21 Intel Pentium Processor Family Developer's Manual—vol. 3: Architecture and Programming Manual (1995) (cover pages, pp. 3-15 to 3-18, pp. 25-189 to 25-192).
22 Krishna, R. et al. "Efficient Software Decoder Design," Advanced Computer Architecture Laboratory, IEEE Computer Society Technical, 2001, 10 pages.
23 Liao, S. et al., "Storage Assignment to Decrease Code Size," ACM Transactions on Programming Languages and Systems, May 1996, pp. 235-253, vol. 18, No. 3.
24 Motorola Product Brief MCF5202 Embedded Microprocessor, 1996 Motorola, Inc., 6 pages.
25 Omondi, A.R. "The Microarchitecture of Pipelined and Superscalar Computers" 1999, pp. 98-99, Kluwer Academic Publishers Boston.
26 Ozturk et al, "Access Pattern-Based Code Compression for Memory-Constrained Systems", ACM Transactions on Design Automation of Electronic Systems, vol. 13, No. 4, Article 62; pp. 60:1-60:30, Sep. 2008.
27 Ozturk, et al, "Access Pattern-Based Code Compression for Memory-Constrained Embedded Systems", IEEE, Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05), pp. 1-6, 2005.
28 PICO: Automatically Designing Custom Computers by Vinod Kathail, et al., Hewlett-Packard Laboratories, Sep. 2002, 17 pages, http://www.hpl.hp.com/research/papers/2002/pico.pdf.
29 Richardson, N. et al., "Chapter 16-The iCore(TM) 520MHz Synthesizable CPU Code," Closing the Gap Between ASIC & Custom, 2004, pp. 361-381, Part 3.
30 Richardson, N. et al., "Chapter 16—The iCore™ 520MHz Synthesizable CPU Code," Closing the Gap Between ASIC & Custom, 2004, pp. 361-381, Part 3.
31 Ros, et al, "A Post-Compilation Register Reassignment Technique for Improving Hamming Distance Code Compression", CASES'05, ACM, pp. 97-104, Sep. 24-27, 2005.
32 SilAria Puts the Squeeze on Code With Tuned Instruction Set by Chris Edwards, EE Times, 2 pages, Oct. 17, 2001, http://www.eetuk.com/tech/news/OEG20011017S0018.
33 Slechta, B. et al., "Dynamic Optimization of Micro-Operations," Center for Reliable and High-Performance Computing, Dept. of Electrical and Computer Engineering, Univ. of Illinois at Urbana-Champaign, The Ninth International Symposium on High Performance Computer Architecture (HPCA'03), Feb. 8-12, 2003, 12 pages.
34 The 801 Minicomputer by George Radin, IBM J. Res. Develop. vol. 44 No. 1/2 Jan./Mar. 2000, pp. 37-46.
35 The Evolution of RISC Technology at IBM by John Cocke and V. Markstein, IBM J. Res. Develop. vol. 34, No. 1, Jan. 1990, pp. 4-11.
36 The GNU 64-bit PL8 Compiler: Toward an Open Standard Environment for Firmware Development by W. Gellerich, et al., IBM J. Res. & Dev. vol. 48 No. 3/4 May/Jul. 2004, pp. 543-556.
37 The History of Language Technology in IBM by F.E. Allen, IBM J. Res. Develop., vol. 25, No. 5, Sep. 1981, pp. 535-548.
38 Xtensa: A Configurable and Extensible Processor; Gonzalez; 2000; IEEE.
US8434059 * 1 maio 2009 30 abr. 2013 Apple Inc. Systems, methods, and computer-readable media for fertilizing machine-executable code
US8539458 * 10 jun. 2011 17 set. 2013 Microsoft Corporation Transforming addressing alignment during code generation
US8677186 15 dez. 2010 18 mar. 2014 Microsoft Corporation Debugging in data parallel computations
US8677322 29 jun. 2011 18 mar. 2014 Microsoft Corporation Debugging in a multiple address space environment
US8863103 * 11 maio 2009 14 out. 2014 Intel Corporation Method and apparatus for implementing a bi-endian capable compiler
US8893095 * 26 jul. 2012 18 nov. 2014 International Business Machines Corporation Methods for generating code for an architecture encoding an extended register specification
US8997066 27 dez. 2010 31 mar. 2015 Microsoft Technology Licensing, Llc Emulating pointers
US9081561 * 21 abr. 2014 14 jul. 2015 Shenzhen Zhongweidian Technology Limited Method for improving execution performance of multiply-add instruction during compiling
US9128722 27 mar. 2013 8 set. 2015 Apple Inc. Systems, methods, and computer-readable media for fertilizing machine-executable code
US9268540 * 16 out. 2013 23 fev. 2016 International Business Machines Corporation Code generation using data marking
US9411715 * 12 dez. 2012 9 ago. 2016 Nvidia Corporation System, method, and computer program product for optimizing the management of thread stack memory
US9710241 * 22 set. 2009 18 jul. 2017 Samsung Electronics Co., Ltd. Apparatus and method for providing instruction for heterogeneous processor
US20090222800 * 11 maio 2009 3 set. 2009 Adiletta Matthew J Method and apparatus for implementing a bi-endian capable compiler
US20100211760 * 22 set. 2009 19 ago. 2010 Egger Bernhard Apparatus and method for providing instruction for heterogeneous processor
US20100281459 * 1 maio 2009 4 nov. 2010 Apple Inc. Systems, methods, and computer-readable media for fertilizing machine-executable code
US20120297373 * 26 jul. 2012 22 nov. 2012 International Business Machines Corporation Methods for generating code for an architecture encoding an extended register specification
US20120317394 * 10 jun. 2011 13 dez. 2012 Microsoft Corporation Transforming addressing alignment during code generation
US20140123102 * 16 out. 2013 1 maio 2014 International Business Machines Corporation Code generation using data marking
US20140164727 * 12 dez. 2012 12 jun. 2014 Nvidia Corporation System, method, and computer program product for optimizing the management of thread stack memory
US20140325190 * 21 abr. 2014 30 out. 2014 Shenzhen Zhongweidian Technology Limited Method for improving execution performance of multiply-add instruction during compiling
Classificação nos Estados Unidos 717/101, 717/140, 717/146
Classificação cooperativa G06F9/44, G06F8/4434
Classificação europeia G06F8/4434
6 maio 2008 AS Assignment
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:FUHLER, RICHARD;PENNELLO, THOMAS J.;JALKUT, MICHAEL LEE;AND OTHERS;REEL/FRAME:020908/0739;SIGNING DATES FROM 20030507 TO 20030509
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:FUHLER, RICHARD;PENNELLO, THOMAS J.;JALKUT, MICHAEL LEE;AND OTHERS;SIGNING DATES FROM 20030507 TO 20030509;REEL/FRAME:020908/0739
8 out. 2010 AS Assignment
7 out. 2015 FPAY Fee payment