URL
https://opencores.org/ocsvn/thor/thor/trunk
Subversion Repositories thor
[/] [thor/] [trunk/] [FT64v5/] [software/] [CC64/] [source/] [Peepgen.cpp] - Rev 59
Go to most recent revision | Compare with Previous | Blame | View Log
// ============================================================================ // __ // \\__/ o\ (C) 2012-2018 Robert Finch, Waterloo // \ __ / All rights reserved. // \/_// robfinch<remove>@finitron.ca // || // // CC64 - 'C' derived language compiler // - 64 bit CPU // // This source file is free software: you can redistribute it and/or modify // it under the terms of the GNU Lesser General Public License as published // by the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // This source file is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see <http://www.gnu.org/licenses/>. // // ============================================================================ // #include "stdafx.h" static void AddToPeepList(OCODE *newc); void PrintPeepList(); static void Remove(); void peep_add(OCODE *ip); static void PeepoptSub(OCODE *ip); void peep_cmp(OCODE *ip); static void opt_peep(); void put_ocode(OCODE *p); void CreateControlFlowGraph(); extern void ComputeLiveVars(); extern void DumpLiveVars(); extern Instruction *GetInsn(int); void CreateVars(); void ComputeLiveRanges(); void DumpLiveRanges(); void RemoveMoves(); void DumpVarForests(); void DumpLiveRegs(); void CreateVarForests(); void DeleteSets(); void RemoveCode(); bool Coalesce(); void ComputeSpillCosts(); extern void CalcDominatorTree(); Var *FindVar(int num); void ExpandReturnBlocks(); bool RemoveEnabled = true; unsigned int ArgRegCount; int count; Map map; OCODE *LabelTable[50000]; OCODE *peep_head = NULL, *peep_tail = NULL; extern Var *varlist; IGraph iGraph; int optimized; // something got optimized void GenerateZeradic(int op) { dfs.printf("<GenerateZeradic>"); OCODE *cd; dfs.printf("A"); cd = (OCODE *)allocx(sizeof(OCODE)); dfs.printf("B"); cd->insn = GetInsn(op); cd->opcode = op; cd->length = 0; cd->oper1 = NULL; dfs.printf("C"); cd->oper2 = NULL; cd->oper3 = NULL; cd->oper4 = NULL; dfs.printf("D"); cd->loop_depth = looplevel; AddToPeepList(cd); dfs.printf("</GenerateZeradic>\r\n"); } void GenerateMonadic(int op, int len, Operand *ap1) { dfs.printf("<GenerateMonadic>"); OCODE *cd; dfs.printf("A"); cd = (OCODE *)allocx(sizeof(OCODE)); dfs.printf("B"); cd->insn = GetInsn(op); cd->opcode = op; cd->length = len; cd->oper1 = ap1->Clone(); dfs.printf("C"); cd->oper2 = NULL; cd->oper3 = NULL; cd->oper4 = NULL; dfs.printf("D"); cd->loop_depth = looplevel; AddToPeepList(cd); dfs.printf("</GenerateMonadic>\n"); } void GenerateDiadic(int op, int len, Operand *ap1, Operand *ap2) { OCODE *cd; cd = (OCODE *)xalloc(sizeof(OCODE)); cd->insn = GetInsn(op); cd->opcode = op; cd->length = len; cd->oper1 = ap1->Clone(); cd->oper2 = ap2->Clone(); if (ap2) { if (ap2->mode == am_ind || ap2->mode==am_indx) { //if (ap2->preg==regSP || ap2->preg==regFP) // cd->opcode |= op_ss; } } cd->oper3 = NULL; cd->oper4 = NULL; cd->loop_depth = looplevel; AddToPeepList(cd); } void GenerateTriadic(int op, int len, Operand *ap1, Operand *ap2, Operand *ap3) { OCODE *cd; cd = (OCODE *)allocx(sizeof(OCODE)); cd->insn = GetInsn(op); cd->opcode = op; cd->length = len; cd->oper1 = ap1->Clone(); cd->oper2 = ap2->Clone(); cd->oper3 = ap3->Clone(); cd->oper4 = NULL; cd->loop_depth = looplevel; AddToPeepList(cd); } void Generate4adic(int op, int len, Operand *ap1, Operand *ap2, Operand *ap3, Operand *ap4) { OCODE *cd; cd = (OCODE *)allocx(sizeof(OCODE)); cd->insn = GetInsn(op); cd->opcode = op; cd->length = len; cd->oper1 = ap1->Clone(); cd->oper2 = ap2->Clone(); cd->oper3 = ap3->Clone(); cd->oper4 = ap4->Clone(); cd->loop_depth = looplevel; AddToPeepList(cd); } static void AddToPeepList(OCODE *cd) { if (!dogen) return; if( peep_head == NULL ) { ArgRegCount = regFirstArg; peep_head = peep_tail = cd; cd->fwd = nullptr; cd->back = nullptr; } else { cd->fwd = nullptr; cd->back = peep_tail; peep_tail->fwd = cd; peep_tail = cd; } if (cd->opcode!=op_label) { if (cd->oper1 && IsArgumentReg(cd->oper1->preg)) ArgRegCount = max(ArgRegCount,cd->oper1->preg); if (cd->oper2 && IsArgumentReg(cd->oper2->preg)) ArgRegCount = max(ArgRegCount,cd->oper2->preg); if (cd->oper3 && IsArgumentReg(cd->oper3->preg)) ArgRegCount = max(ArgRegCount,cd->oper3->preg); if (cd->oper4 && IsArgumentReg(cd->oper4->preg)) ArgRegCount = max(ArgRegCount,cd->oper4->preg); } } // Count the length of the peep list from the current position to the end of // the list. int PeepCount(OCODE *ip) { int cnt; for (cnt = 0; ip && ip != peep_tail; cnt++) ip = ip->fwd; return (cnt); } /* * add a compiler generated label to the peep list. */ void GenerateLabel(int labno) { OCODE *newl; newl = (OCODE *)allocx(sizeof(OCODE)); newl->opcode = op_label; newl->oper1 = (Operand *)labno; newl->oper2 = (Operand *)my_strdup((char *)currentFn->sym->name->c_str()); AddToPeepList(newl); } // Detect references to labels void PeepOpt::SetLabelReference() { OCODE *p, *q; struct clit *ct; int nn; ZeroMemory(LabelTable, sizeof(LabelTable)); for (p = peep_head; p; p = p->fwd) { if (p->opcode == op_label) { LabelTable[(int)p->oper1] = p; p->isReferenced = false; } } for (q = peep_head; q; q = q->fwd) { if (q->opcode!=op_label && q->opcode!=op_nop) { if (q->oper1 && (q->oper1->mode==am_direct || q->oper1->mode==am_imm)) { if (p = PeepList::FindLabel(q->oper1->offset->i)) { p->isReferenced = true; } } if (q->oper2 && (q->oper2->mode==am_direct || q->oper2->mode==am_imm)) { if (p = PeepList::FindLabel(q->oper2->offset->i)) { p->isReferenced = true; } } if (q->oper3 && (q->oper3->mode==am_direct || q->oper3->mode==am_imm)) { if (p = PeepList::FindLabel(q->oper3->offset->i)) { p->isReferenced = true; } } if (q->oper4 && (q->oper4->mode==am_direct || q->oper4->mode==am_imm)) { if (p = PeepList::FindLabel(q->oper4->offset->i)) { p->isReferenced = true; } } // Now search case tables for label for (ct = casetab; ct; ct = ct->next) { for (nn = 0; nn < ct->num; nn++) if (p = PeepList::FindLabel(ct->cases[nn].label)) p->isReferenced = true; } } } } void PeepOpt::EliminateUnreferencedLabels() { OCODE *p; for (p = peep_head; p; p = p->fwd) { if (p->opcode == op_label) p->remove = false; if (p->opcode == op_label && !p->isReferenced) { MarkRemove(p); optimized++; } } } // // Output all code and labels in the peep list. // void flush_peep() { opt_peep(); /* do the peephole optimizations */ while( peep_head != NULL ) { if( peep_head->opcode == op_label ) put_label((int)peep_head->oper1,"",GetNamespace(),'C'); else peep_head->store(ofs); peep_head = peep_head->fwd; } } void peep_add(OCODE *ip) { Operand *a; // IF add to SP is followed by a move to SP, eliminate the add if (ip==NULL) return; if (ip->fwd==NULL) return; if (ip->fwd->opcode == op_bra) { if (ip->oper3->offset) { if (ip->oper1->preg == ip->oper2->preg && ip->oper3->offset->i == 1) { ip->opcode = op_ibne; ip->insn = GetInsn(op_ibne); ip->oper2->preg = 0; ip->oper3 = ip->fwd->oper1; MarkRemove(ip->fwd); optimized++; } } return; } if (ip->oper1) { a = ip->oper1; if (a->mode==am_reg) { if (a->preg==regSP) { if (ip->fwd->opcode==op_mov) { if (ip->fwd->oper1->mode==am_reg) { if (ip->fwd->oper1->preg == regSP) { if (ip->back==NULL) return; ip->back->fwd = ip->fwd; ip->fwd->back = ip->back; optimized++; } } } } } } return; } static bool IsSubiSP(OCODE *ip) { if (ip->opcode == op_sub) { if (ip->oper3->mode == am_imm) { if (ip->oper1->preg == regSP && ip->oper2->preg == regSP) { return (true); } } } return (false); } // 'subui' followed by a 'bne' gets turned into 'loop' // static void PeepoptSub(OCODE *ip) { if (IsSubiSP(ip) && ip->fwd) if (IsSubiSP(ip->fwd)) { ip->oper3->offset->i += ip->fwd->oper3->offset->i; MarkRemove(ip->fwd); } if (IsSubiSP(ip) && ip->oper3->offset->i == 0) MarkRemove(ip); return; if (ip->opcode==op_subui) { if (ip->oper3) { if (ip->oper3->mode==am_imm) { if (ip->oper3->offset->nodetype==en_icon && ip->oper3->offset->i==1) { if (ip->fwd) { if (ip->fwd->opcode==op_ne && ip->fwd->oper2->mode==am_reg && ip->fwd->oper2->preg==0) { if (ip->fwd->oper1->preg==ip->oper1->preg) { ip->opcode = op_loop; ip->oper2 = ip->fwd->oper3; ip->oper3 = NULL; if (ip->fwd->back) ip->fwd->back = ip; ip->fwd = ip->fwd->fwd; optimized++; return; } } } } } } } return; } static void MergeSubi(OCODE *first, OCODE *last, int64_t amt) { OCODE *ip; if (first==nullptr) return; // First remove all the excess subtracts for (ip = first; ip && ip != last; ip = ip->fwd) { if (IsSubiSP(ip)) { MarkRemove(ip); optimized++; } } // Set the amount of the last subtract to the total amount if (ip) {// there should be one ip->oper3->offset->i = amt; } } // 'subui' // static void PeepoptSubSP() { OCODE *ip; OCODE *first_subi = nullptr; OCODE *last_subi = nullptr; int64_t amt = 0; for (ip = peep_head; ip; ip = ip->fwd) { if (IsSubiSP(ip)) { if (first_subi==nullptr) last_subi = first_subi = ip; else last_subi = ip; amt += ip->oper3->offset->i; } else if (ip->opcode==op_push || ip->insn->IsFlowControl()) { MergeSubi(first_subi, last_subi, amt); first_subi = last_subi = nullptr; amt = 0; } } } /* * peephole optimization for compare instructions. */ void peep_cmp(OCODE *ip) { return; } /* * changes multiplies and divides by convienient values * to shift operations. op should be either op_asl or * op_asr (for divide). */ void PeepoptMuldiv(OCODE *ip, int op) { int shcnt; int64_t num; if( ip->oper1->mode != am_imm ) return; if( ip->oper1->offset->nodetype != en_icon ) return; num = ip->oper1->offset->i; // remove multiply / divide by 1 // This shouldn't get through Optimize, but does sometimes. if (num==1) { if (ip->back) ip->back->fwd = ip->fwd; if (ip->fwd) ip->fwd->back = ip->back; optimized++; return; } for (shcnt = 1; shcnt < 32; shcnt++) { if (num == (int64_t)1 << shcnt) { num = shcnt; optimized++; break; } } if (shcnt==32) return; ip->oper1->offset->i = num; ip->opcode = op; ip->length = 2; optimized++; } // Optimize unconditional control flow transfers // Instructions that follow an unconditional transfer won't be executed // unless there is a label to branch to them. // void PeepoptUctran(OCODE *ip) { if (uctran_off) return; while( ip->fwd != NULL && ip->fwd->opcode != op_label) { ip->fwd = ip->fwd->fwd; if( ip->fwd != NULL ) ip->fwd->back = ip; optimized++; } } void PeepoptJAL(OCODE *ip) { if (ip->oper1->preg!=0) return; PeepoptUctran(ip); } // Remove instructions that branch to the next label. // void PeepoptBranch(OCODE *ip) { OCODE *p; for (p = ip->fwd; p && p->opcode==op_label; p = p->fwd) if (ip->oper1->offset->i == (int)p->oper1) { MarkRemove(ip); optimized++; return; } return; } // Look for the following sequence and convert it into a set operation. // Bcc lab1 // ldi rn,#1 // bra lab2 // lab1: // ldi rn,#0 // lab2: void PeepoptBcc(OCODE * ip) { OCODE *fwd1, *fwd2, *fwd3, *fwd4, *fwd5; if (!ip->fwd) return; fwd1 = ip->fwd; if (fwd1->opcode != op_ldi || fwd1->oper2->mode != am_imm) return; fwd2 = fwd1->fwd; if (!fwd2) return; if (fwd2->opcode != op_bra) return; fwd3 = fwd2->fwd; if (!fwd3) return; if (fwd3->opcode != op_label) return; fwd4 = fwd3->fwd; if (!fwd4) return; if (fwd4->opcode != op_ldi || fwd4->oper2->mode != am_imm) return; fwd5 = fwd4->fwd; if (!fwd5) return; if (fwd5->opcode != op_label) return; // now check labels match up if (ip->oper2!=fwd3->oper1) return; if (fwd2->oper1!=fwd5->oper1) return; // check for same target register if (!OCODE::IsEqualOperand(fwd1->oper1,fwd4->oper1)) return; // check ldi values if (fwd1->oper2->offset->i != 1) return; if (fwd4->oper2->offset->i != 0) return; // ***** // need to check branch targets to make sure no other code targets the label. // or this code might not work. } void PeepoptLc(OCODE *ip) { if (ip->fwd) { if (ip->fwd->opcode==op_sext16 || ip->fwd->opcode==op_sxc || (ip->fwd->opcode==op_bfext && ip->fwd->oper3->offset->i==0 && ip->fwd->oper4->offset->i==15)) { if (ip->fwd->oper1->preg == ip->oper1->preg) { if (ip->fwd->fwd) { ip->fwd->fwd->back = ip; } ip->fwd = ip->fwd->fwd; } } } } // LEA followed by a push of the same register gets translated to PEA. // If LEA is followed by the push of more than one register, then leave it // alone. The register order of the push matters. void PeepoptLea(OCODE *ip) { OCODE *ip2; int whop; return; whop = 0; ip2 = ip->fwd; if (!ip2) return; if (ip2->opcode != op_push) return; whop = ((ip2->oper1 != NULL) ? 1 : 0) + ((ip2->oper2 != NULL) ? 1 : 0) + ((ip2->oper3 != NULL) ? 1 : 0) + ((ip2->oper4 != NULL) ? 1 : 0); if (whop > 1) return; // Pushing a single register if (ip2->oper1->mode != am_reg) return; // And it's the same register as the LEA if (ip2->oper1->preg != ip->oper1->preg) return; ip->opcode = op_pea; ip->oper1 = ip->oper2->Clone(); ip->oper2 = NULL; ip->fwd = ip2->fwd; } // LW followed by a push of the same register gets translated to PUSH. void PeepoptLw(OCODE *ip) { OCODE *ip2; return; ip2 = ip->fwd; if (!ip2) return; if (ip2->opcode != op_push) return; if (ip2->oper1->mode != am_reg) return; if (ip->oper2->mode != am_ind && ip->oper2->mode != am_indx) return; if (ip->oper1->preg != ip2->oper1->preg) return; ip->opcode = op_push; ip->oper1 = ip->oper2->Clone(); ip->oper2 = NULL; ip->fwd = ip2->fwd; } // LC0I followed by a push of the same register gets translated to PUSH. void PeepoptLc0i(OCODE *ip) { OCODE *ip2; if (!isFISA64) return; ip2 = ip->fwd; if (!ip2) return; if (ip2->opcode != op_push) return; if (ip->oper2->offset->i > 0x1fffLL || ip->oper2->offset->i <= -0x1fffLL) return; ip->opcode = op_push; ip->oper1 = ip->oper2->Clone(); ip->oper2 = NULL; ip->fwd = ip2->fwd; } // Combine a chain of push operations into a single push void PeepoptPushPop(OCODE *ip) { OCODE *ip2,*ip3,*ip4; return; if (ip->opcode==op_pop) { ip2 = ip->fwd; if (ip2 && ip2->opcode==op_push) { ip3 = ip2->fwd; if (ip3 && ip3->opcode==op_ldi) { if (ip3->oper1->preg==ip2->oper1->preg && ip3->oper1->preg==ip->oper1->preg) { ip->back->fwd = ip2->fwd; ip->back->fwd->comment = ip2->comment; } } } } return; if (!isTable888) return; if (ip->oper1->mode == am_imm) return; ip2 = ip->fwd; if (!ip2) return; if (ip2->opcode!=ip->opcode) return; if (ip2->oper1->mode==am_imm) return; ip->oper2 = ip2->oper1->Clone(); ip->fwd = ip2->fwd; ip3 = ip2->fwd; if (!ip3) return; if (ip3->opcode!=ip->opcode) return; if (ip3->oper1->mode==am_imm) return; ip->oper3 = ip3->oper1->Clone(); ip->fwd = ip3->fwd; ip4 = ip3->fwd; if (!ip4) return; if (ip4->opcode!=ip->opcode) return; if (ip4->oper1->mode==am_imm) return; ip->oper4 = ip4->oper1->Clone(); ip->fwd = ip4->fwd; } // Strip out useless masking operations generated by type conversions. void peep_ld(OCODE *ip) { if (ip->oper2->mode != am_imm) return; if (ip->oper2->offset->i==0) { ip->opcode = op_mov; ip->oper2->mode = am_reg; ip->oper2->preg = 0; optimized++; return; } if (!ip->fwd) return; if (ip->fwd->opcode!=op_and) return; if (ip->fwd->oper1->preg != ip->oper1->preg) return; if (ip->fwd->oper2->preg != ip->oper1->preg) return; if (ip->fwd->oper3->mode != am_imm) return; ip->oper2->offset->i = ip->oper2->offset->i & ip->fwd->oper3->offset->i; if (ip->fwd->fwd) ip->fwd->fwd->back = ip; ip->fwd = ip->fwd->fwd; optimized++; } void PeepoptLd(OCODE *ip) { return; } // Remove extra labels at end of subroutines void PeepoptLabel(OCODE *ip) { if (!ip) return; if (ip->fwd) return; if (ip->back) ip->back->fwd = nullptr; optimized++; } // Optimize away duplicate sign extensions that the compiler sometimes // generates. This handles sxb, sxcm and sxh. void PeepoptSxb(OCODE *ip) { // Optimize away sign extension of a signed load if (ip->back) { if (ip->back->opcode == op_lb && ip->opcode == op_sxb) { if (ip->back->oper1->preg == ip->oper1->preg && ip->oper1->preg==ip->oper2->preg) { MarkRemove(ip); optimized++; return; } } if (ip->back->opcode == op_lc && ip->opcode == op_sxc) { if (ip->back->oper1->preg == ip->oper1->preg && ip->oper1->preg == ip->oper2->preg) { MarkRemove(ip); optimized++; return; } } if (ip->back->opcode == op_lh && ip->opcode == op_sxh) { if (ip->back->oper1->preg == ip->oper1->preg && ip->oper1->preg == ip->oper2->preg) { MarkRemove(ip); optimized++; return; } } } if (!ip->fwd) return; if (ip->fwd->opcode != ip->opcode) return; if (ip->fwd->oper1->preg != ip->oper1->preg) return; if (ip->fwd->oper2->preg != ip->oper2->preg) return; // Now we must have the same instruction twice in a row. ELiminate the // duplicate. ip->fwd = ip->fwd->fwd; if (ip->fwd->fwd) ip->fwd->fwd->back = ip; optimized++; } void PeepoptSxbAnd(OCODE *ip) { if (!ip->fwd) return; if (ip->opcode != op_sxb) return; if (ip->fwd->opcode != op_and) return; if (ip->fwd->oper3->mode != am_imm) return; if (ip->fwd->oper3->offset->i != 255) return; MarkRemove(ip); optimized++; } // Eliminate branchs to the next line of code. static void opt_nbr() { OCODE *ip,*pip; ip = peep_head; pip = peep_head; while(ip) { if (ip->opcode==op_label) { if (pip->opcode==op_br || pip->opcode==op_bra) { if ((int64_t)ip->oper1==pip->oper1->offset->i) { pip->back->fwd = pip->fwd; ip->back = pip->back; optimized++; } } } pip = ip; ip = ip->fwd; } } // Process compiler hint opcodes static void PeepoptHint(OCODE *ip) { OCODE *fwd, *back; Operand *am; if ((ip->back && ip->back->opcode==op_label) || (ip->fwd && ip->fwd->opcode==op_label)) return; if (ip->remove) return; switch (ip->oper1->offset->i) { // hint #1 // Takes care of redundant moves at the parameter setup point // Code Like: // MOV r3,#constant // MOV r18,r3 // Translated to: // MOV r18,#constant case 1: if (ip->fwd && ip->fwd->opcode != op_mov) { MarkRemove(ip); optimized++; return; } if (ip->fwd && ip->fwd->oper1->preg >= 18 && ip->fwd->oper1->preg < 24) { if (OCODE::IsEqualOperand(ip->fwd->oper2, ip->back->oper1)) { ip->back->oper1 = ip->fwd->oper1; MarkRemove(ip); MarkRemove(ip->fwd); optimized++; return; } } if (ip->back && ip->back->opcode != op_mov) { MarkRemove(ip); optimized++; return; } if (OCODE::IsEqualOperand(ip->fwd->oper2, ip->back->oper1)) { ip->back->oper1 = ip->fwd->oper1; MarkRemove(ip); MarkRemove(ip->fwd); optimized++; } else { MarkRemove(ip); optimized++; } break; // Can't do this optimization: // what if x = (~(y=(a & b))) // The embedded assignment to y which might be used later would be lost. // // hint #2 // Takes care of redundant moves at the function return point // Code like: // MOV R3,arg // MOV R1,R3 // Translated to: // MOV r1,arg case 2: return; if (ip->fwd==nullptr || ip->back==nullptr) break; if (ip->fwd->remove || ip->back->remove) break; if (OCODE::IsEqualOperand(ip->fwd->oper2, ip->back->oper1)) { if (ip->back->HasTargetReg()) { if (!(ip->fwd->oper1->mode == am_fpreg && ip->back->opcode==op_ldi)) { ip->back->oper1 = ip->fwd->oper1; MarkRemove(ip->fwd); optimized++; } } } else { MarkRemove(ip); optimized++; } break; // hint #3 // and r5,r2,r3 // com r1,r5 // Translates to: // nand r5,r2,r3 case 3: if (ip->back == nullptr || ip->fwd == nullptr) break; if (ip->fwd->remove || ip->back->remove) break; // If not all in registers if (ip->back->oper1->mode != am_reg || ip->back->oper2->mode != am_reg || (ip->back->oper3 && ip->back->oper3->mode != am_reg)) break; if (ip->back->opcode != op_and && ip->back->opcode != op_or && ip->back->opcode != op_xor ) break; if (ip->fwd->opcode != op_com) break; if (ip->fwd->oper2->mode != am_reg) break; if (ip->back->oper1->preg != ip->fwd->oper2->preg) break; if (ip->fwd->opcode != op_com) break; switch (ip->back->opcode) { case op_and: ip->back->opcode = op_nand; ip->back->insn = GetInsn(op_nand); ip->back->oper1->preg = ip->fwd->oper1->preg; MarkRemove(ip->fwd); optimized++; break; case op_or: ip->back->opcode = op_nor; ip->back->insn = GetInsn(op_nor); ip->back->oper1->preg = ip->fwd->oper1->preg; MarkRemove(ip->fwd); optimized++; break; case op_xor: ip->back->opcode = op_xnor; ip->back->insn = GetInsn(op_xnor); ip->back->oper1->preg = ip->fwd->oper1->preg; MarkRemove(ip->fwd); optimized++; break; } break; // hint #9 // Index calc. // shl r1,r3,#3 // sw r4,[r11+r1] // Becomes: // sw r4,[r11+r3*8] case 9: if (ip->fwd==nullptr || ip->back==nullptr) break; if (ip->fwd->oper2==nullptr || ip->back->oper3==nullptr) break; if (ip->fwd->oper2->mode != am_indx2) break; if (ip->fwd->oper2->preg == ip->back->oper1->preg) { if ((ip->back->opcode == op_shl) && ip->back->oper3->offset && (ip->back->oper3->offset->i == 1 || ip->back->oper3->offset->i == 2 || ip->back->oper3->offset->i == 3)) { ip->fwd->oper2->preg = ip->back->oper2->preg; ip->fwd->oper2->scale = 1 << ip->back->oper3->offset->i; MarkRemove(ip->back); optimized++; am = ip->back->oper1; fwd = ip->fwd->fwd; back = ip->back->back; while (back->opcode == op_hint) // It should be back = back->back; // We search backwards for another shl related to a forward op to // accomodate assignment operations. Assignment operations may // generate indexed code like the following: // shl for target // shl for source // load source // store target if (fwd->oper2) { if ((back->opcode == op_shl) && back->oper3->offset && (am->preg != fwd->oper2->preg && am->preg != fwd->oper2->sreg) && (back->oper3->offset->i == 1 || back->oper3->offset->i == 2 || back->oper3->offset->i == 3) ) { fwd->oper2->preg = back->oper2->preg; fwd->oper2->scale = 1 << back->oper3->offset->i; MarkRemove(back); optimized++; } } } } break; } } // A store followed by a load of the same address removes // the load operation. // Eg. // SH r3,Address // LH r3,Address // Turns into // SH r3,Address // Note this optimization won't be performed for volatile // addresses. static void Swap(OCODE *ip1, OCODE *ip2) { OCODE *ip1b = ip1->back, *ip1f = ip1->fwd; OCODE *ip2b = ip2->back, *ip2f = ip2->fwd; ip1b->fwd = ip2; ip2f->back = ip1; ip1->fwd = ip2f; ip1->back = ip2; ip2->fwd = ip1; ip2->back = ip1b; } static void PeepoptSh(OCODE *ip) { if (ip->back && (ip->back->opcode==op_bfextu || ip->back->opcode==op_bfext)) { if (ip->back->oper1->preg==ip->oper1->preg) { if (ip->back->oper3->offset->i == 0 && ip->back->oper4->offset->i==31) { Swap(ip->back,ip); } } } } static void PeepoptStore(OCODE *ip) { if (ip->opcode==op_sh) PeepoptSh(ip); if (ip->opcode==op_label || ip->fwd->opcode==op_label) return; if (!OCODE::IsEqualOperand(ip->oper1, ip->fwd->oper1)) return; if (!OCODE::IsEqualOperand(ip->oper2, ip->fwd->oper2)) return; if (ip->opcode==op_sh && ip->fwd->opcode!=op_lh) return; if (ip->opcode==op_sw && ip->fwd->opcode!=op_lw) return; if (ip->fwd->isVolatile) return; MarkRemove(ip->fwd); optimized++; } // This optimization eliminates an 'AND' instruction when the value // in the register is a constant less than one of the two special // constants 255 or 65535. This is typically a result of a zero // extend operation. // // So code like: // ld r3,#4 // and r3,r3,#255 // Eliminates the useless 'and' operation. static void PeepoptAnd(OCODE *ip) { // This doesn't work properly yet in all cases. if (ip->oper1 && ip->oper2 && ip->oper3) { if (ip->oper1->mode==am_reg && ip->oper2->mode==am_reg && ip->oper3->mode == am_imm) { if (ip->oper1->preg==ip->oper2->preg && ip->oper3->offset->i==-1) { MarkRemove(ip); optimized++; } } } return; if (ip->oper2==nullptr || ip->oper3==nullptr) throw new C64PException(ERR_NULLPOINTER,0x50); if (ip->oper2->offset == nullptr || ip->oper3->offset==nullptr) return; if (ip->oper2->offset->constflag==false) return; if (ip->oper3->offset->constflag==false) return; if ( ip->oper3->offset->i != 1 && ip->oper3->offset->i != 3 && ip->oper3->offset->i != 7 && ip->oper3->offset->i != 15 && ip->oper3->offset->i != 31 && ip->oper3->offset->i != 63 && ip->oper3->offset->i != 127 && ip->oper3->offset->i != 255 && ip->oper3->offset->i != 511 && ip->oper3->offset->i != 1023 && ip->oper3->offset->i != 2047 && ip->oper3->offset->i != 4095 && ip->oper3->offset->i != 8191 && ip->oper3->offset->i != 16383 && ip->oper3->offset->i != 32767 && ip->oper3->offset->i != 65535) // Could do this up to 32 bits return; if (ip->oper2->offset->i < ip->oper3->offset->i) { MarkRemove(ip); } } // Check for references to the base pointer. If nothing refers to the // base pointer then the stack linkage instructions can be removed. static int CountBPReferences() { int refBP = 0; OCODE *ip; for (ip = peep_head; ip != NULL; ip = ip->fwd) { if (ip->opcode != op_label && ip->opcode!=op_nop && ip->opcode != op_link && ip->opcode != op_unlk) { if (ip->oper1) { if (ip->oper1->preg==regFP || ip->oper1->sreg==regFP) refBP++; } if (ip->oper2) { if (ip->oper2->preg==regFP || ip->oper2->sreg==regFP) refBP++; } if (ip->oper3) { if (ip->oper3->preg==regFP || ip->oper3->sreg==regFP) refBP++; } if (ip->oper4) { if (ip->oper4->preg==regFP || ip->oper4->sreg==regFP) refBP++; } } } return (refBP); } void MarkRemove(OCODE *ip) { ip->remove = true; } void MarkRemove2(OCODE *ip) { ip->remove2 = true; } static void MarkAllKeep() { OCODE *ip; for (ip = peep_head; ip != NULL; ip = ip->fwd ) { ip->remove = false; } } void Remove() { OCODE *ip, *ip1, *ip2; if (RemoveEnabled) for (ip = peep_head; ip; ip = ip1) { ip1 = ip->fwd; ip2 = ip->back; if (ip->remove) { if (ip1 && ip1->comment==nullptr) ip1->comment = ip->comment; if (ip2) ip2->fwd = ip1; if (ip1) ip1->back = ip2; } } } void IRemove() { Remove(); } static void Remove2() { OCODE *ip, *ip1, *ip2; if (RemoveEnabled) for (ip = peep_head; ip; ip = ip1) { ip1 = ip->fwd; ip2 = ip->back; if (ip->remove2) { if (ip1 && ip1->comment==nullptr) ip1->comment = ip->comment; if (ip2) ip2->fwd = ip1; if (ip1) ip1->back = ip2; } } } static void RemoveDoubleTargets(OCODE *ip) { OCODE *ip2; int rg1, rg2, rg3, rg4; if (!ip->HasTargetReg()) return; for (ip2 = ip->fwd; ip2 && (ip2->opcode==op_rem || ip2->opcode==op_hint); ip2 = ip2->fwd); if (ip2==nullptr) return; if (!ip2->HasTargetReg()) return; ip2->GetTargetReg(&rg1, &rg2); ip->GetTargetReg(&rg3, &rg4); if (rg1 != rg3) return; if (ip2->HasSourceReg(rg3)) return; if (rg3==regSP) return; MarkRemove(ip); optimized++; } // Remove stack linkage code for when there are no references to the base // pointer. static void RemoveLinkUnlink() { OCODE *ip; for (ip = peep_head; ip != NULL; ip = ip->fwd) { if (ip->opcode==op_link || ip->opcode==op_unlk) { MarkRemove(ip); } } } static void RemoveCompilerHints() { OCODE *ip; for(ip = peep_head; ip != NULL; ip = ip->fwd) { if (ip->opcode==op_hint) { MarkRemove(ip); } } } // Potentially any called routine could throw an exception. So call // instructions could act like branches to the default catch tacked // onto the end of a subroutine. This is important to prevent the // default catch from being optimized away. It's possible that there's // no other way to reach the catch. // A bex instruction, which isn't a real instruction, is added to the // instruction stream so that links are created in the CFG to the // catch handlers. At a later stage of the compile all the bex // instructions are removed, since they were there only to aid in // compiler optimizations. static void RemoveCompilerHints2() { OCODE *ip; for(ip = peep_head; ip != NULL; ip = ip->fwd) { if (ip->opcode==op_bex) MarkRemove(ip); } Remove(); } // // peephole optimizer. This routine calls the instruction // specific optimization routines above for each instruction // in the peep list. // static void opt_peep() { OCODE *ip; int rep; PrintPeepList(); // Move the return code pointer past the label which may be removed by // optimization. if (currentFn->rcode) currentFn->rcode = currentFn->rcode->fwd; // Remove any dead code identified by the code generator. Remove(); if (!::opt_nopeep) { opt_nbr(); // Performing peephole optimizations may lead to further optimizations so do // the optimization step a few times. optimized = 0; for (rep = 0; (rep < 5) || (optimized && rep < 10); rep++) { // Peephole optimizations might lead to unreferenced labels, which may make // further peephole optimizations possible. PeepOpt::SetLabelReference(); PeepOpt::EliminateUnreferencedLabels(); Remove(); //MarkAllKeep(); for (ip = peep_head; ip != NULL; ip = ip->fwd ) { if (!ip->remove) { switch( ip->opcode ) { case op_rem: if (ip->fwd) { ip->fwd->comment = ip; MarkRemove(ip); } break; case op_ld: peep_ld(ip); PeepoptLd(ip); break; case op_mov: ip->OptMove(); break; case op_add: case op_addu: case op_addui: peep_add(ip); break; case op_sub: PeepoptSub(ip); break; case op_cmp: peep_cmp(ip); break; case op_mul: // PeepoptMuldiv(ip,op_shl); break; case op_lc: PeepoptLc(ip); break; case op_lw: //PeepoptLw(ip); break; case op_sxb: case op_sxc: case op_sxh: PeepoptSxb(ip); PeepoptSxbAnd(ip); break; case op_br: case op_bra: PeepoptBranch(ip); PeepoptUctran(ip); break; case op_pop: case op_push: PeepoptPushPop(ip); break; case op_lea: PeepoptLea(ip); break; case op_jal: PeepoptJAL(ip); break; case op_brk: case op_jmp: case op_ret: case op_rts: case op_rte: case op_rtd: PeepoptUctran(ip); break; case op_label: PeepoptLabel(ip); break; case op_hint: PeepoptHint(ip); break; case op_sh: case op_sw: PeepoptStore(ip); break; case op_and: PeepoptAnd(ip); break; case op_redor: ip->OptRedor(); break; } } } Remove(); for (ip = peep_head; ip != NULL; ip = ip->fwd ) RemoveDoubleTargets(ip); Remove(); } //PeepoptSubSP(); // Remove the link and unlink instructions if no references // to BP. if (CountBPReferences()==0) RemoveLinkUnlink(); Remove(); } // Get rid of extra labels that clutter up the output PeepOpt::SetLabelReference(); PeepOpt::EliminateUnreferencedLabels(); // Remove all the compiler hints that didn't work out. RemoveCompilerHints(); Remove(); currentFn->RootBlock = BasicBlock::Blockize(peep_head); dfs.printf("<PeepList:1>\n"); PrintPeepList(); dfs.printf("</PeepList:1>\n"); forest.func = currentFn; // RootBlock->ExpandReturnBlocks(); CFG::Create(); RemoveMoves(); currentFn->ComputeLiveVars(); MarkAllKeep(); currentFn->DumpLiveVars(); currentFn->CreateVars(); Var::CreateForests(); Var::DumpForests(0); CFG::CalcDominanceFrontiers(); CFG::InsertPhiInsns(); RemoveCompilerHints2(); CFG::Rename(); count = 0; forest.pass = 0; do { forest.pass++; if (!opt_vreg) return; forest.Renumber(); BasicBlock::ComputeSpillCosts(); RemoveCode(); iGraph.frst = &forest; iGraph.BuildAndCoalesce(); iGraph.Print(3); forest.Simplify(); iGraph.Print(4); forest.Select(); Var::DumpForests(1); forest.SpillCode(); } while (!forest.IsAllTreesColored() && forest.pass < 32); dfs.printf("Loops for color graphing allocator: %d\n", forest.pass); // Substitute real registers for virtual ones. BasicBlock::ColorAll(); if (count == 2) { dfs.printf("Register allocator max loops.\n"); } Var::DumpForests(2); //DumpLiveRegs(); dfs.printf("<PeepList:2>\n"); PrintPeepList(); dfs.printf("</PeepList:2>\n"); } // Remove move instructions which will create false interferences. // The move instructions are just marked for removal so they aren't // considered during live variable computation. They are unmarked // later, but may be subsequently removed if ranges are coalesced. void RemoveMoves() { OCODE *ip; int reg1, reg2; bool foundMove; foundMove = false; for (ip = peep_head; ip; ip = ip->fwd) { if (ip->opcode==op_mov) { foundMove = true; reg1 = ip->oper1->preg; reg2 = ip->oper2->preg; // Registers used as register parameters cannot be coalesced. if (IsArgumentReg(reg1) || IsArgumentReg(reg2)) continue; // Remove the move instruction MarkRemove(ip); } } if (!foundMove) dfs.printf("No move instruction joins live ranges.\n"); } // Remove useless code where there are no output links from the basic block. void RemoveCode() { int nn,mm; Var *v; Tree *t; OCODE *p; int count; int rg1, rg2; count = 0; //printf((char *)currentFn->name->c_str()); //printf("\r\n"); for (v = currentFn->varlist; v; v = v->next) { if (IsCalleeSave(v->num)) continue; if (v->num < 5 || v->num==regLR || v->num==regXLR) continue; for (mm = 0; mm < v->trees.treecount; mm++) { t = v->trees.trees[mm]; nn = t->blocks->lastMember(); do { for (p = basicBlocks[nn]->lcode; p && !p->leader; p = p->back) { if (p->opcode==op_label) continue; if (p->opcode==op_ret) continue; p->GetTargetReg(&rg1, &rg2); if (rg1 == v->num && rg2==0) { if (p->bb->ohead==nullptr) { MarkRemove2(p); count++; } } if (!p->remove && p->HasSourceReg(v->num)) goto j1; } } while((nn = t->blocks->prevMember()) >= 0); j1: ; } //Remove2(); } dfs.printf("<CodeRemove>%d</CodeRemove>\n", count); } void PrintPeepList() { OCODE *ip; Instruction *insn; return; for (ip = peep_head; ip; ip = ip->fwd) { if (ip == currentFn->rcode) dfs.printf("***rcode***"); insn = GetInsn(ip->opcode); if (insn) dfs.printf("%s ", insn->mnem); else if (ip->opcode == op_label) dfs.printf("%s%d:", (char *)ip->oper2, (int)ip->oper1); else dfs.printf("op(%d)", ip->opcode); if (ip->bb) dfs.printf("bb:%d\n", ip->bb->num); else dfs.printf("bb nul\n"); } }
Go to most recent revision | Compare with Previous | Blame | View Log