12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301 |
- /*****************************************************************************
- * Project: dcc
- * File: dataflow.c
- * Purpose: Data flow analysis module.
- * (C) Cristina Cifuentes
- ****************************************************************************/
- #include "dcc.h"
- #include "project.h"
- #include "msvc_fixes.h"
- #include <boost/range.hpp>
- #include <boost/range/adaptor/filtered.hpp>
- #include <boost/range/adaptor/reversed.hpp>
- #include <boost/range/algorithm.hpp>
- #include <boost/assign.hpp>
- #include <stdint.h>
- #include <cstring>
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- using namespace boost;
- using namespace boost::adaptors;
- using namespace std;
- namespace
- {
- struct ExpStack
- {
- Function *func;
- typedef std::list<Expr *> EXP_STK;
- EXP_STK expStk; /* local expression stack */
- void init(Function *f);
- void push(Expr *);
- Expr * pop();
- Expr * top() const {
- if(not expStk.empty())
- return expStk.back();
- return nullptr;
- }
- int numElem();
- bool empty();
- void processExpPush(int &numHlIcodes, ICODE &picode)
- {
- RegisterNode *rn = dynamic_cast<RegisterNode *>(picode.hlU()->expr());
- if(rn)
- assert(rn->m_syms==&func->localId);
- push(picode.hlU()->expr());
- picode.invalidate();
- numHlIcodes--;
- }
- };
- ExpStack g_exp_stk;
- /** Returns a string with the source operand of Icode */
- Expr *srcIdent (const LLInst &ll_insn, Function * pProc, iICODE i, ICODE & duIcode, operDu du)
- {
- const LLOperand * src_op = ll_insn.get(SRC);
- if (src_op->isImmediate()) /* immediate operand ll_insn.testFlags(I)*/
- {
- //if (ll_insn.testFlags(B))
- return new Constant(src_op->getImm2(), src_op->byteWidth());
- }
- // otherwise
- return AstIdent::id (ll_insn, SRC, pProc, i, duIcode, du);
- }
- /** Returns the destination operand */
- Expr *dstIdent (const LLInst & ll_insn, Function * pProc, iICODE i, ICODE & duIcode, operDu du)
- {
- Expr *n;
- n = AstIdent::id (ll_insn, DST, pProc, i, duIcode, du);
- /** Is it needed? (pIcode->ll()->flg) & NO_SRC_B **/
- return (n);
- }
- /* Substitutes the rhs (or lhs if rhs not possible) of ticode for the expression exp given */
- void forwardSubsLong (int longIdx, Expr *_exp, ICODE &picode, ICODE &ticode, int *numHlIcodes)
- {
- bool res;
- if (_exp == nullptr) /* In case expression popped is NULL */
- return;
- /* Insert on rhs of ticode, if possible */
- res = Expr::insertSubTreeLongReg (_exp, ticode.hlU()->asgn.m_rhs, longIdx);
- if (res)
- {
- picode.invalidate();
- (*numHlIcodes)--;
- }
- else
- {
- /* Try to insert it on lhs of ticode*/
- res = Expr::insertSubTreeLongReg (_exp, ticode.hlU()->asgn.m_lhs, longIdx);
- if (res)
- {
- picode.invalidate();
- (*numHlIcodes)--;
- }
- }
- }
- } // end of anonymous namespace
- /***************************************************************************
- * Expression stack functions
- **************************************************************************/
- /* Reinitalizes the expression stack (expStk) to NULL, by freeing all the
- * space allocated (if any). */
- void ExpStack::init(Function *f)
- {
- func=f;
- expStk.clear();
- }
- /* Pushes the given expression onto the local stack (expStk). */
- void ExpStack::push(Expr *expr)
- {
- expStk.push_back(expr);
- }
- /* Returns the element on the top of the local expression stack (expStk),
- * and deallocates the space allocated by this node.
- * If there are no elements on the stack, returns NULL. */
- Expr *ExpStack::pop()
- {
- if(expStk.empty())
- return nullptr;
- Expr *topExp = expStk.back();
- expStk.pop_back();
- return topExp;
- }
- /* Returns the number of elements available in the expression stack */
- int ExpStack::numElem()
- {
- return expStk.size();
- }
- /* Returns whether the expression stack is empty or not */
- bool ExpStack::empty()
- {
- return expStk.empty();
- }
- /* Returns the index of the local variable or parameter at offset off, if it
- * is in the stack frame provided. */
- size_t STKFRAME::getLocVar(int off)
- {
- auto iter=findByLabel(off);
- return distance(begin(),iter);
- }
- /* Eliminates all condition codes and generates new hlIcode instructions */
- void Function::elimCondCodes ()
- {
- // int i;
- uint8_t use; /* Used flags bit vector */
- uint8_t def; /* Defined flags bit vector */
- bool notSup; /* Use/def combination not supported */
- Expr *rhs; /* Source operand */
- Expr *lhs; /* Destination operand */
- BinaryOperator *_expr; /* Boolean expression */
- //BB * pBB; /* Pointer to BBs in dfs last ordering */
- riICODE useAt; /* Instruction that used flag */
- riICODE defAt; /* Instruction that defined flag */
- //lhs=rhs=_expr=0;
- auto valid_reversed_bbs = (m_dfsLast | reversed | filtered(BB::ValidFunctor()) );
- for( BB * pBB : valid_reversed_bbs)
- {
- //auto reversed_instructions = pBB->range() | reversed;
- for (useAt = pBB->rbegin(); useAt != pBB->rend(); useAt++)
- {
- llIcode useAtOp = llIcode(useAt->ll()->getOpcode());
- use = useAt->ll()->flagDU.u;
- if ((useAt->type != LOW_LEVEL_ICODE) or ( not useAt->valid() ) or ( 0 == use ))
- continue;
- /* Find definition within the same basic block */
- defAt=useAt;
- ++defAt;
- for (; defAt != pBB->rend(); defAt++)
- {
- ICODE &defIcode(*defAt);
- def = defAt->ll()->flagDU.d;
- if ((use & def) != use)
- continue;
- notSup = false;
- LLOperand *dest_ll = defIcode.ll()->get(DST);
- if ((useAtOp >= iJB) and (useAtOp <= iJNS))
- {
- iICODE befDefAt = (++riICODE(defAt)).base();
- switch (defIcode.ll()->getOpcode())
- {
- case iCMP:
- rhs = srcIdent (*defIcode.ll(), this, befDefAt,*useAt, eUSE);
- lhs = dstIdent (*defIcode.ll(), this, befDefAt,*useAt, eUSE);
- break;
- case iOR:
- lhs = defIcode.hl()->asgn.lhs()->clone();
- useAt->copyDU(*defAt, eUSE, eDEF);
- //if (defAt->ll()->testFlags(B))
- rhs = new Constant(0, dest_ll->byteWidth());
- break;
- case iTEST:
- rhs = srcIdent (*defIcode.ll(),this, befDefAt,*useAt, eUSE);
- lhs = dstIdent (*defIcode.ll(),this, befDefAt,*useAt, eUSE);
- lhs = BinaryOperator::And(lhs, rhs);
- // if (defAt->ll()->testFlags(B))
- rhs = new Constant(0, dest_ll->byteWidth());
- break;
- case iINC:
- case iDEC: //WARNING: verbatim copy from iOR needs fixing ?
- lhs = defIcode.hl()->asgn.lhs()->clone();
- useAt->copyDU(*defAt, eUSE, eDEF);
- rhs = new Constant(0, dest_ll->byteWidth());
- break;
- default:
- notSup = true;
- std::cout << hex<<defIcode.loc_ip;
- reportError (JX_NOT_DEF, defIcode.ll()->getOpcode());
- flg |= PROC_ASM; /* generate asm */
- }
- if (not notSup)
- {
- assert(lhs);
- assert(rhs);
- _expr = BinaryOperator::Create(condOpJCond[useAtOp-iJB],lhs,rhs);
- useAt->setJCond(_expr);
- }
- }
- else if (useAtOp == iJCXZ)
- {
- //NOTICE: was rCX, 0
- lhs = new RegisterNode(LLOperand(rCX, 0 ), &localId);
- useAt->setRegDU (rCX, eUSE);
- rhs = new Constant(0, 2);
- _expr = BinaryOperator::Create(EQUAL,lhs,rhs);
- useAt->setJCond(_expr);
- }
- // else if (useAt->getOpcode() == iRCL)
- // {
- // }
- else
- {
- ICODE &a(*defAt);
- ICODE &b(*useAt);
- reportError (NOT_DEF_USE,a.ll()->label,a.ll()->getOpcode(),b.ll()->getOpcode());
- flg |= PROC_ASM; /* generate asm */
- }
- break;
- }
- /* Check for extended basic block */
- if ((pBB->size() == 1) and(useAtOp >= iJB) and (useAtOp <= iJNS))
- {
- ICODE & _prev(pBB->back()); /* For extended basic blocks - previous icode inst */
- if (_prev.hl()->opcode == HLI_JCOND)
- {
- _expr = dynamic_cast<BinaryOperator *>(_prev.hl()->expr()->clone());
- assert(_expr);
- _expr->changeBoolOp (condOpJCond[useAtOp-iJB]);
- useAt->copyDU(_prev, eUSE, eUSE);
- useAt->setJCond(_expr);
- }
- }
- /* Error - definition not found for use of a cond code */
- else if (defAt == pBB->rend())
- {
- reportError(DEF_NOT_FOUND,useAtOp);
- }
- }
- }
- }
- /** Generates the LiveUse() and Def() sets for each basic block in the graph.
- \note these sets are constant and could have been constructed during
- the construction of the graph, but since the code hasn't been
- analyzed yet for idioms, the procedure preamble misleads the
- analysis (eg: push si, would include si in LiveUse; although it
- is not really meant to be a register that is used before defined). */
- void Function::genLiveKtes ()
- {
- BB * pbb;
- LivenessSet liveUse, def;
- for (size_t i = 0; i < numBBs; i++)
- {
- liveUse.reset();
- def.reset();
- pbb = m_dfsLast[i];
- if (pbb->flg & INVALID_BB)
- continue; // skip invalid BBs
- for(ICODE &insn : *pbb)
- {
- if ((insn.type == HIGH_LEVEL_ICODE) and ( insn.valid() ))
- {
- liveUse |= (insn.du.use - def);
- def |= insn.du.def;
- }
- }
- pbb->liveUse = liveUse;
- pbb->def = def;
- }
- }
- /* Generates the liveIn() and liveOut() sets for each basic block via an
- * iterative approach.
- * Propagates register usage information to the procedure call. */
- void Function::liveRegAnalysis (LivenessSet &in_liveOut)
- {
- using namespace boost::adaptors;
- using namespace boost::assign;
- //BB * pbb=0; /* pointer to current basic block */
- Function * pcallee; /* invoked subroutine */
- //ICODE *ticode /* icode that invokes a subroutine */
- ;
- LivenessSet prevLiveOut, /* previous live out */
- prevLiveIn; /* previous live in */
- bool change; /* is there change in the live sets?*/
- /* liveOut for this procedure */
- liveOut = in_liveOut;
- change = true;
- while (change)
- {
- /* Process nodes in reverse postorder order */
- change = false;
- auto valid_reversed_bbs = (m_dfsLast | reversed | filtered(BB::ValidFunctor()) );
- for( BB * pbb : valid_reversed_bbs) // for each valid pbb in reversed dfs order
- {
- /* Get current liveIn() and liveOut() sets */
- prevLiveIn = pbb->liveIn;
- prevLiveOut = pbb->liveOut;
- /* liveOut(b) = U LiveIn(s); where s is successor(b)
- * liveOut(b) = {liveOut}; when b is a HLI_RET node */
- if (pbb->edges.empty()) /* HLI_RET node */
- {
- pbb->liveOut = in_liveOut;
- /* Get return expression of function */
- if (flg & PROC_IS_FUNC)
- {
- auto picode = pbb->rbegin(); /* icode of function return */
- if (picode->hl()->opcode == HLI_RET)
- {
- picode->hlU()->expr(AstIdent::idID(&retVal, &localId, (++pbb->rbegin()).base()));
- picode->du.use = in_liveOut;
- }
- }
- }
- else /* Check successors */
- {
- for(TYPEADR_TYPE &e : pbb->edges)
- {
- pbb->liveOut |= e.BBptr->liveIn;
- }
- /* propagate to invoked procedure */
- if (pbb->nodeType == CALL_NODE)
- {
- ICODE &ticode(pbb->back());
- pcallee = ticode.hl()->call.proc;
- /* user/runtime routine */
- if (not (pcallee->flg & PROC_ISLIB))
- {
- if (pcallee->liveAnal == false) /* hasn't been processed */
- pcallee->dataFlow (pbb->liveOut);
- pbb->liveOut = pcallee->liveIn;
- }
- else /* library routine */
- {
- if ( (pcallee->flg & PROC_IS_FUNC) and /* returns a value */
- (pcallee->liveOut & pbb->edges[0].BBptr->liveIn).any()
- )
- pbb->liveOut = pcallee->liveOut;
- else
- pbb->liveOut.reset();
- }
- if ((not (pcallee->flg & PROC_ISLIB)) or ( pbb->liveOut.any() ))
- {
- switch (pcallee->retVal.type) {
- case TYPE_LONG_SIGN:
- case TYPE_LONG_UNSIGN:
- ticode.du1.setDef(rAX).addDef(rDX);
- //TODO: use Calling convention to properly set regs here
- break;
- case TYPE_WORD_SIGN: case TYPE_WORD_UNSIGN:
- case TYPE_BYTE_SIGN: case TYPE_BYTE_UNSIGN:
- ticode.du1.setDef(rAX);
- break;
- default:
- ticode.du1 = ICODE::DU1(); // was .numRegsDef = 0
- //fprintf(stderr,"Function::liveRegAnalysis : Unknown return type %d, assume 0\n",pcallee->retVal.type);
- } /*eos*/
- /* Propagate def/use results to calling icode */
- ticode.du.use = pcallee->liveIn;
- ticode.du.def = pcallee->liveOut;
- }
- }
- }
- /* liveIn(b) = liveUse(b) U (liveOut(b) - def(b) */
- pbb->liveIn = LivenessSet(pbb->liveUse + (pbb->liveOut - pbb->def));
- /* Check if live sets have been modified */
- if ((prevLiveIn != pbb->liveIn) or (prevLiveOut != pbb->liveOut))
- change = true;
- }
- }
- BB *pbb = m_dfsLast.front();
- /* Propagate liveIn(b) to procedure header */
- if (pbb->liveIn.any()) /* uses registers */
- liveIn = pbb->liveIn;
- /* Remove any references to register variables */
- if (flg & SI_REGVAR)
- {
- liveIn.clrReg(rSI);
- pbb->liveIn.clrReg(rSI);
- }
- if (flg & DI_REGVAR)
- {
- liveIn.clrReg(rDI);
- pbb->liveIn.clrReg(rDI);
- }
- }
- /* Check remaining instructions of the BB for all uses
- * of register regi, before any definitions of the
- * register */
- bool BB::FindUseBeforeDef(eReg regi, int defRegIdx, iICODE start_at)
- {
- if ((regi == rDI) and (flg & DI_REGVAR))
- return true;
- if ((regi == rSI) and (flg & SI_REGVAR))
- return true;
- if (distance(start_at,end())>1) /* several instructions */
- {
- iICODE ticode=end();
- // Only check uses of HIGH_LEVEL icodes
- auto hl_range=make_iterator_range(start_at,end()) | filtered(ICODE::select_high_level);
- auto checked_icode=hl_range.begin();
- ++checked_icode;
- for (; checked_icode != hl_range.end(); ++checked_icode)
- {
- ICODE &ic(*checked_icode);
- /* if used, get icode index */
- if ( ic.du.use.testRegAndSubregs(regi) )
- start_at->du1.recordUse(defRegIdx,checked_icode.base());
- /* if defined, stop finding uses for this reg */
- if (ic.du.def.testRegAndSubregs(regi))
- {
- ticode=checked_icode.base();
- break;
- }
- }
- if(ticode==end())
- ticode=(++riICODE(rbegin())).base();
- /* Check if last definition of this register */
- if (not ticode->du.def.testRegAndSubregs(regi) and liveOut.testRegAndSubregs(regi) )
- start_at->du.lastDefRegi.addReg(regi);
- }
- else /* only 1 instruction in this basic block */
- {
- /* Check if last definition of this register */
- if ( liveOut.testRegAndSubregs(regi) )
- start_at->du.lastDefRegi.addReg(regi);
- }
- return false;
- }
- /* Find target icode for HLI_CALL icodes to procedures
- * that are functions. The target icode is in the
- * next basic block (unoptimized code) or somewhere else
- * on optimized code. */
- void BB::ProcessUseDefForFunc(eReg regi, int defRegIdx, ICODE &picode)
- {
- if (not ((picode.hl()->opcode == HLI_CALL) and (picode.hl()->call.proc->flg & PROC_IS_FUNC)))
- return;
- BB *tbb = this->edges[0].BBptr;
- auto target_instructions = tbb->instructions | filtered(ICODE::select_high_level);
- for (auto iter=target_instructions.begin(); iter!=target_instructions.end(); ++iter)
- {
- /* if used, get icode index */
- if ( iter->du.use.testRegAndSubregs(regi) )
- picode.du1.recordUse(defRegIdx,iter.base());
- /* if defined, stop finding uses for this reg */
- if (iter->du.def.testRegAndSubregs(regi))
- break;
- }
- /* if not used in this basic block, check if the
- * register is live out, if so, make it the last
- * definition of this register */
- if ( picode.du1.used(defRegIdx) and tbb->liveOut.testRegAndSubregs(regi))
- picode.du.lastDefRegi.addReg(regi);
- }
- /* If not used within this bb or in successors of this
- * bb (ie. not in liveOut), then register is useless,
- * thus remove it. Also check that this is not a return
- * from a library function (routines such as printf
- * return an integer, which is normally not taken into
- * account by the programmer). */
- void BB::RemoveUnusedDefs(eReg regi, int defRegIdx, iICODE picode)
- {
- if (picode->valid() and not picode->du1.used(defRegIdx) and
- (not picode->du.lastDefRegi.testRegAndSubregs(regi)) and
- (not ((picode->hl()->opcode == HLI_CALL) and
- (picode->hl()->call.proc->flg & PROC_ISLIB))))
- {
- if (not (this->liveOut.testRegAndSubregs(regi))) /* not liveOut */
- {
- bool res = picode->removeDefRegi (regi, defRegIdx+1,&Parent->localId);
- if (res == true)
- {
- /* Backpatch any uses of this instruction, within
- * the same BB, if the instruction was invalidated */
- rICODE the_rest(begin(),picode);
- for ( ICODE &back_patch_at : the_rest|reversed)
- {
- back_patch_at.du1.remove(0,picode);
- }
- }
- }
- else /* liveOut */
- picode->du.lastDefRegi.addReg(regi);
- }
- }
- void BB::genDU1()
- {
- /* Process each register definition of a HIGH_LEVEL icode instruction.
- * Note that register variables should not be considered registers.
- */
- assert(nullptr!=Parent);
- auto all_high_levels = instructions | filtered(ICODE::select_high_level);
- for (auto picode=all_high_levels.begin(); picode!=all_high_levels.end(); ++picode)
- {
- ICODE &ic = *picode;
- int defRegIdx = 0;
- // foreach defined register
- for (int k = rAX; k < INDEX_BX_SI; k++)
- {
- if (not ic.du.def.testReg(k))
- continue;
- eReg regi = (eReg)(k); /* Register that was defined */
- picode->du1.regi[defRegIdx] = regi;
- if(FindUseBeforeDef(regi,defRegIdx, picode.base()))
- continue;
- ProcessUseDefForFunc(regi, defRegIdx,ic);
- RemoveUnusedDefs(regi, defRegIdx, picode.base());
- defRegIdx++;
- /* Check if all defined registers have been processed */
- if ((defRegIdx >= picode->du1.getNumRegsDef()) or (defRegIdx == MAX_REGS_DEF))
- break;
- }
- }
- }
- /* Generates the du chain of each instruction in a basic block */
- void Function::genDU1 ()
- {
- /* Traverse tree in dfsLast order */
- assert(m_dfsLast.size()==numBBs);
- for(BB *pbb : m_dfsLast | filtered(BB::ValidFunctor()))
- {
- pbb->genDU1();
- }
- }
- /* Substitutes the rhs (or lhs if rhs not possible) of ticode for the rhs of picode. */
- void LOCAL_ID::forwardSubs (Expr *lhs, Expr *rhs, ICODE &picode, ICODE &ticode, int &numHlIcodes) const
- {
- bool res;
- UnaryOperator *lhs_unary;
- while( (lhs_unary = dynamic_cast<UnaryOperator *>(lhs)) )
- {
- if(dynamic_cast<AstIdent *>(lhs_unary))
- break;
- lhs = lhs_unary->unaryExp;
- }
- RegisterNode * lhs_reg=dynamic_cast<RegisterNode *>(lhs_unary);
- assert(lhs_reg);
- if (rhs == nullptr) /* In case expression popped is NULL */
- return;
- /* Insert on rhs of ticode, if possible */
- res = Expr::insertSubTreeReg (ticode.hlU()->asgn.m_rhs,rhs, id_arr[lhs_reg->regiIdx].id.regi, this);
- if (res)
- {
- picode.invalidate();
- numHlIcodes--;
- }
- else
- {
- /* Try to insert it on lhs of ticode*/
- RegisterNode *op = dynamic_cast<RegisterNode *>(ticode.hlU()->asgn.m_lhs);
- if(op)
- {
- eReg inserted = id_arr[lhs_reg->regiIdx].id.regi;
- eReg lhsReg = id_arr[op->regiIdx].id.regi;
- if((lhsReg==inserted) or Machine_X86::isSubRegisterOf(lhsReg,inserted))
- {
- // Do not replace ax = XYZ; given ax = H << P; with H << P =
- return;
- }
- }
- res = Expr::insertSubTreeReg (ticode.hlU()->asgn.m_lhs,rhs, id_arr[lhs_reg->regiIdx].id.regi, this);
- if (res)
- {
- picode.invalidate();
- numHlIcodes--;
- }
- }
- }
- /** Returns whether the elements of the expression rhs are all x-clear from
- * instruction f up to instruction t. */
- bool UnaryOperator::xClear(rICODE range_to_check, iICODE lastBBinst, const LOCAL_ID &locs)
- {
- if(nullptr==unaryExp)
- return false;
- return unaryExp->xClear ( range_to_check, lastBBinst, locs);
- }
- bool BinaryOperator::xClear(rICODE range_to_check, iICODE lastBBinst, const LOCAL_ID &locs)
- {
- if(nullptr==m_rhs)
- return false;
- if ( not m_rhs->xClear (range_to_check, lastBBinst, locs) )
- return false;
- if(nullptr==m_lhs)
- return false;
- return m_lhs->xClear (range_to_check, lastBBinst, locs);
- }
- bool AstIdent::xClear(rICODE range_to_check, iICODE lastBBinst, const LOCAL_ID &locId)
- {
- if (ident.idType != REGISTER)
- return true;
- assert(false);
- return false;
- }
- /** Checks the type of the formal argument as against to the actual argument,
- whenever possible, and then places the actual argument on the procedure's
- argument list.
- @returns the type size of the stored Arg
- */
- int C_CallingConvention::processCArg (Function * callee, Function * pProc, ICODE * picode, size_t numArgs)
- {
- Expr *_exp;
- bool res;
- int size_of_arg=0;
- PROG &prog(Project::get()->prog);
- /* if (numArgs == 0)
- return; */
- assert(pProc==g_exp_stk.func);
- _exp = g_exp_stk.pop();
- if (callee->isLibrary() ) /* library function */
- {
- if (callee->args.numArgs > 0)
- {
- if (callee->getFunctionType()->isVarArg())
- {
- if (numArgs < callee->args.size()) {
- if(_exp==nullptr)
- fprintf(stderr,"Would try to adjustForArgType with null _exp\n");
- else
- _exp = pProc->adjustActArgType (_exp, callee->args[numArgs].type);
- }
- }
- else {
- if(numArgs<callee->args.size()) {
- if(prog.addressingMode=='l') {
- if((callee->args[numArgs].type==TYPE_STR) or (callee->args[numArgs].type==TYPE_PTR)) {
- RegisterNode *rn = dynamic_cast<RegisterNode *>(g_exp_stk.top());
- AstIdent *idn = dynamic_cast<AstIdent *>(g_exp_stk.top());
- if(rn) {
- const ID &_id(pProc->localId.id_arr[rn->regiIdx]);
- assert(&pProc->localId==rn->m_syms);
- if(_id.id.regi==rDS) {
- g_exp_stk.pop(); // pop segment
- size_of_arg += 2;
- }
- } else if(idn) {
- Expr *tmp1 = new Constant(2,1);
- Expr *tmp2 = BinaryOperator::createSHL(_exp,tmp1);
- _exp = BinaryOperator::CreateAdd(g_exp_stk.top(),tmp2);
- g_exp_stk.pop(); // pop segment
- size_of_arg += 2;
- }
- }
- }
- _exp = pProc->adjustActArgType (_exp, callee->args[numArgs].type);
- } else {
- fprintf(stderr,"processCArg tried to query non existent arg\n");
- }
- }
- }
- }
- else /* user function */
- {
- if (callee->args.numArgs > 0)
- {
- if(_exp==nullptr)
- fprintf(stderr,"Would try to adjustForArgType with null _exp\n");
- else
- callee->args.adjustForArgType (numArgs, _exp->expType (pProc));
- }
- }
- res = picode->newStkArg (_exp, picode->ll()->getOpcode(), pProc);
- /* Do not update the size of k if the expression was a segment register
- * in a near call */
- if (res == false)
- {
- if(_exp==nullptr)
- return 2+size_of_arg;
- return _exp->hlTypeSize (pProc)+size_of_arg;
- }
- return 0; // be default we do not know the size of the argument
- }
- /** Eliminates extraneous intermediate icode instructions when finding
- * expressions. Generates new hlIcodes in the form of expression trees.
- * For HLI_CALL hlIcodes, places the arguments in the argument list. */
- void LOCAL_ID::processTargetIcode(ICODE &picode, int &numHlIcodes, ICODE &ticode,bool isLong) const
- {
- bool res;
- HLTYPE &p_hl(*picode.hlU());
- HLTYPE &t_hl(*ticode.hlU());
- AstIdent *lhs_ident = dynamic_cast<AstIdent *>(p_hl.asgn.lhs());
- switch (t_hl.opcode)
- {
- case HLI_ASSIGN:
- assert(lhs_ident);
- if(isLong)
- {
- forwardSubsLong (lhs_ident->ident.idNode.longIdx,
- p_hl.asgn.m_rhs, picode,ticode,
- &numHlIcodes);
- }
- else
- this->forwardSubs (lhs_ident, p_hl.asgn.m_rhs, picode, ticode, numHlIcodes);
- break;
- case HLI_JCOND: case HLI_PUSH: case HLI_RET:
- if(isLong)
- {
- assert(lhs_ident);
- res = Expr::insertSubTreeLongReg (
- p_hl.asgn.m_rhs,
- t_hl.exp.v,
- lhs_ident->ident.idNode.longIdx);
- }
- else
- {
- RegisterNode *lhs_reg = dynamic_cast<RegisterNode *>(p_hl.asgn.lhs());
- assert(lhs_reg);
- res = Expr::insertSubTreeReg (
- t_hl.exp.v,
- p_hl.asgn.m_rhs,
- id_arr[lhs_reg->regiIdx].id.regi,
- this);
- }
- if (res)
- {
- picode.invalidate();
- numHlIcodes--;
- }
- break;
- case HLI_CALL: /* register arguments */
- newRegArg ( picode, ticode);
- picode.invalidate();
- numHlIcodes--;
- break;
- default:
- fprintf(stderr,"unhandled LOCAL_ID::processTargetIcode opcode %d\n",t_hl.opcode);
- }
- }
- void C_CallingConvention::processHLI(Function *func,Expr *_exp, iICODE picode) {
- Function * pp;
- int cb, numArgs;
- int k;
- pp = picode->hl()->call.proc;
- cb = picode->hl()->call.args->cb;
- numArgs = 0;
- k = 0;
- if (cb)
- {
- while ( k < cb )
- {
- k+=processCArg (pp, func, &(*picode), numArgs);
- numArgs++;
- }
- }
- else if ((cb == 0) and picode->ll()->testFlags(REST_STK))
- {
- while (not g_exp_stk.empty())
- {
- k+=processCArg (pp, func, &(*picode), numArgs);
- numArgs++;
- }
- }
- }
- void Pascal_CallingConvention::processHLI(Function *func,Expr *_exp, iICODE picode) {
- Function * pp;
- int cb, numArgs;
- bool res;
- int k;
- pp = picode->hl()->call.proc;
- cb = pp->cbParam; /* fixed # arguments */
- k = 0;
- numArgs = 0;
- while(k<cb)
- {
- _exp = g_exp_stk.pop();
- if (pp->isLibrary() ) /* library function */
- {
- if (pp->args.numArgs > 0)
- _exp = func->adjustActArgType(_exp, pp->args[numArgs].type);
- res = picode->newStkArg (_exp, picode->ll()->getOpcode(), func);
- }
- else /* user function */
- {
- if (pp->args.numArgs >0)
- {
- if(_exp==nullptr)
- {
- fprintf(stderr,"Would try to adjustForArgType with null _exp\n");
- }
- else
- pp->args.adjustForArgType (numArgs,_exp->expType (func));
- }
- res = picode->newStkArg (_exp, picode->ll()->getOpcode(), func);
- }
- if (res == false)
- k += _exp->hlTypeSize (func);
- numArgs++;
- }
- }
- void Function::processHliCall(Expr *_exp, iICODE picode)
- {
- Function * pp = picode->hl()->call.proc;
- pp->callingConv()->processHLI(this,_exp,picode);
- }
- void BB::findBBExps(LOCAL_ID &locals,Function *fnc)
- {
- bool res;
- ID *_retVal; // function return value
- Expr *_exp; // expression pointer - for HLI_POP and HLI_CALL */
- iICODE ticode; // Target icode */
- HLTYPE *ti_hl=nullptr;
- uint8_t regi;
- numHlIcodes = 0;
- assert(&fnc->localId==&locals);
- // register(s) to be forward substituted */
- auto valid_and_highlevel = instructions | filtered(ICODE::TypeAndValidFilter<HIGH_LEVEL_ICODE>());
- for (auto picode = valid_and_highlevel.begin(); picode != valid_and_highlevel.end(); picode++)
- {
- ICODE &_ic(*picode);
- HLTYPE &_icHl(*_ic.hlU());
- numHlIcodes++;
- if (_ic.du1.getNumRegsDef() == 1) /* uint8_t/uint16_t regs */
- {
- /* Check for only one use of this register. If this is
- * the last definition of the register in this BB, check
- * that it is not liveOut from this basic block */
- if (_ic.du1.numUses(0)==1)
- {
- /* Check that this register is not liveOut, if it
- * is the last definition of the register */
- regi = _ic.du1.regi[0];
- /* Check if we can forward substitute this register */
- switch (_icHl.opcode)
- {
- case HLI_ASSIGN:
- /* Replace rhs of current icode into target
- * icode expression */
- ticode = _ic.du1.idx[0].uses.front();
- if ((_ic.du.lastDefRegi.testRegAndSubregs(regi)) and
- ((ticode->hl()->opcode != HLI_CALL) and
- (ticode->hl()->opcode != HLI_RET)))
- continue;
- if (_icHl.asgn.m_rhs->xClear (make_iterator_range(picode.base(),_ic.du1.idx[0].uses[0]),
- end(), locals))
- {
- locals.processTargetIcode(_ic, numHlIcodes, *ticode,false);
- }
- break;
- case HLI_POP:
- // TODO: sometimes picode->du1.idx[0].uses.front() points to next basic block ?
- // pop X
- // lab1:
- // call F() <- somehow this is marked as user of POP ?
- ticode = _ic.du1.idx[0].uses.front();
- ti_hl = ticode->hlU();
- if ((_ic.du.lastDefRegi.testRegAndSubregs(regi)) and
- ((ti_hl->opcode != HLI_CALL) and
- (ti_hl->opcode != HLI_RET)))
- continue;
- _exp = g_exp_stk.pop(); /* pop last exp pushed */
- switch (ticode->hl()->opcode) {
- case HLI_ASSIGN:
- locals.forwardSubs(_icHl.expr(), _exp, _ic, *ticode, numHlIcodes);
- break;
- case HLI_JCOND: case HLI_PUSH: case HLI_RET:
- {
- RegisterNode *v = dynamic_cast<RegisterNode *>(_icHl.expr());
- assert(v);
- res = Expr::insertSubTreeReg (ti_hl->exp.v,
- _exp,
- locals.id_arr[v->regiIdx].id.regi,
- &locals);
- if (res)
- {
- _ic.invalidate();
- numHlIcodes--;
- }
- }
- break;
- /****case HLI_CALL: // register arguments
- newRegArg (pProc, picode, ticode);
- picode->invalidate();
- numHlIcodes--;
- break; */
- default:
- fprintf(stderr,"unhandled BB::findBBExps target opcode %d\n",ticode->hl()->opcode);
- } // eos
- break;
- case HLI_CALL:
- ticode = _ic.du1.idx[0].uses.front();
- ti_hl = ticode->hlU();
- _retVal = &_icHl.call.proc->retVal;
- switch (ti_hl->opcode)
- {
- case HLI_ASSIGN:
- assert(ti_hl->asgn.m_rhs);
- _exp = _icHl.call.toAst();
- res = Expr::insertSubTreeReg (ti_hl->asgn.m_rhs,_exp, _retVal->id.regi, &locals);
- if (not res)
- Expr::insertSubTreeReg (ti_hl->asgn.m_lhs, _exp,_retVal->id.regi, &locals);
- //TODO: HERE missing: 2 regs
- _ic.invalidate();
- numHlIcodes--;
- break;
- case HLI_PUSH: case HLI_RET:
- ti_hl->expr( _icHl.call.toAst() );
- _ic.invalidate();
- numHlIcodes--;
- break;
- case HLI_JCOND:
- _exp = _icHl.call.toAst();
- res = Expr::insertSubTreeReg (ti_hl->exp.v, _exp, _retVal->id.regi, &locals);
- if (res) /* was substituted */
- {
- _ic.invalidate();
- numHlIcodes--;
- }
- else /* cannot substitute function */
- {
- auto lhs = AstIdent::idID(_retVal,&locals,picode.base());
- _ic.setAsgn(lhs, _exp);
- }
- break;
- default:
- fprintf(stderr,"unhandled BB::findBBExps HLI_CALL target opcode %d\n",ti_hl->opcode);
- } /* eos */
- break;
- default:
- fprintf(stderr,"BB::findBBExps Unhandled HLI %d\n",_icHl.opcode);
- } /* eos */
- }
- }
- else if (_ic.du1.getNumRegsDef() == 2) /* long regs */
- {
- /* Check for only one use of these registers */
- if ((_ic.du1.numUses(0) == 1) and (_ic.du1.numUses(1) == 1))
- {
- regi = _ic.du1.regi[0]; //TODO: verify that regi actually should be assigned this
- switch (_icHl.opcode)
- {
- case HLI_ASSIGN:
- /* Replace rhs of current icode into target
- * icode expression */
- if (_ic.du1.idx[0].uses[0] == _ic.du1.idx[1].uses[0])
- {
- ticode = _ic.du1.idx[0].uses.front();
- if ((_ic.du.lastDefRegi.testRegAndSubregs(regi)) and
- ((ticode->hl()->opcode != HLI_CALL) and
- (ticode->hl()->opcode != HLI_RET)))
- continue;
- locals.processTargetIcode(_ic, numHlIcodes, *ticode,true);
- }
- break;
- case HLI_POP:
- if (_ic.du1.idx[0].uses[0] == _ic.du1.idx[1].uses[0])
- {
- ticode = _ic.du1.idx[0].uses.front();
- if ((_ic.du.lastDefRegi.testRegAndSubregs(regi)) and
- ((ticode->hl()->opcode != HLI_CALL) and
- (ticode->hl()->opcode != HLI_RET)))
- continue;
- _exp = g_exp_stk.pop(); /* pop last exp pushed */
- switch (ticode->hl()->opcode) {
- case HLI_ASSIGN:
- forwardSubsLong (dynamic_cast<AstIdent *>(_icHl.expr())->ident.idNode.longIdx,
- _exp, _ic, *ticode, &numHlIcodes);
- break;
- case HLI_JCOND: case HLI_PUSH:
- res = Expr::insertSubTreeLongReg (_exp,
- ticode->hlU()->exp.v,
- dynamic_cast<AstIdent *>(_icHl.asgn.lhs())->ident.idNode.longIdx);
- if (res)
- {
- _ic.invalidate();
- numHlIcodes--;
- }
- break;
- case HLI_CALL: /*** missing ***/
- break;
- default:
- fprintf(stderr,"BB::findBBExps Unhandled target op %d\n",ticode->hl()->opcode);
- } /* eos */
- }
- break;
- case HLI_CALL: /* check for function return */
- ticode = _ic.du1.idx[0].uses.front();
- switch (ticode->hl()->opcode)
- {
- case HLI_ASSIGN:
- _exp = _icHl.call.toAst();
- ticode->hlU()->asgn.lhs(
- AstIdent::Long(&locals, DST,
- ticode,HIGH_FIRST, picode.base(),
- eDEF, *(++iICODE(ticode))->ll()));
- ticode->hlU()->asgn.m_rhs = _exp;
- _ic.invalidate();
- numHlIcodes--;
- break;
- case HLI_PUSH:
- case HLI_RET:
- ticode->hlU()->expr( _icHl.call.toAst() );
- _ic.invalidate();
- numHlIcodes--;
- break;
- case HLI_JCOND:
- _exp = _icHl.call.toAst();
- _retVal = &_ic.hl()->call.proc->retVal;
- res = Expr::insertSubTreeLongReg (_exp,
- ticode->hlU()->exp.v,
- locals.newLongReg ( _retVal->type, _retVal->longId(), picode.base()));
- if (res) /* was substituted */
- {
- _ic.invalidate();
- numHlIcodes--;
- }
- else /* cannot substitute function */
- {
- auto lhs = locals.createId(_retVal,picode.base());
- _ic.setAsgn(lhs, _exp);
- }
- break;
- default:
- fprintf(stderr,"BB::findBBExps Unhandled target op %d\n",ticode->hl()->opcode);
- } /* eos */
- break;
- default:
- fprintf(stderr,"BB::findBBExps Unhandled HLI %d\n",_icHl.opcode);
- } /* eos */
- }
- }
- /* HLI_PUSH doesn't define any registers, only uses registers.
- * Push the associated expression to the register on the local
- * expression stack */
- else if (_icHl.opcode == HLI_PUSH)
- {
- g_exp_stk.processExpPush(numHlIcodes, *picode);
- }
- else if(_ic.du1.getNumRegsDef()!=0)
- printf("Num def %d\n",_ic.du1.getNumRegsDef());
- /* For HLI_CALL instructions that use arguments from the stack,
- * pop them from the expression stack and place them on the
- * procedure's argument list */
- if(_icHl.opcode == HLI_CALL)
- {
- if ( not _icHl.call.proc->hasRegArgs())
- {
- fnc->processHliCall(_exp, picode.base());
- }
- /* If we could not substitute the result of a function,
- * assign it to the corresponding registers */
- if ( not _icHl.call.proc->isLibrary() and (not _ic.du1.used(0)) and (_ic.du1.getNumRegsDef() > 0))
- {
- _exp = new FuncNode(_icHl.call.proc, _icHl.call.args);
- auto lhs = AstIdent::idID (&_icHl.call.proc->retVal, &locals, picode.base());
- _ic.setAsgn(lhs, _exp);
- }
- }
- }
- /* Store number of high-level icodes in current basic block */
- }
- void Function::findExps()
- {
- /* Initialize expression stack */
- g_exp_stk.init(this);
- /* Traverse tree in dfsLast order */
- for(BB *pbb : m_dfsLast | filtered(BB::ValidFunctor()))
- {
- /* Process one valid BB */
- pbb->findBBExps( this->localId, this);
- }
- }
- void Function::preprocessReturnDU(LivenessSet &_liveOut)
- {
- if (_liveOut.any())
- {
- // int idx;
- bool isAx, isBx, isCx, isDx;
- eReg bad_regs[] = {rES,rCS,rDS,rSS};
- constexpr const char * names[] ={"ES","CS","DS","SS"};
- for(int i=0; i<4; ++i)
- if(_liveOut.testReg(bad_regs[i]))
- {
- fprintf(stderr,"LivenessSet probably screwed up, %s register as an liveOut in preprocessReturnDU\n",names[i]);
- _liveOut.clrReg(bad_regs[i]);
- if(not _liveOut.any())
- return;
- }
- flg |= PROC_IS_FUNC;
- isAx = _liveOut.testReg(rAX);
- isBx = _liveOut.testReg(rBX);
- isCx = _liveOut.testReg(rCX);
- isDx = _liveOut.testReg(rDX);
- bool isAL = not isAx and _liveOut.testReg(rAL);
- bool isAH = not isAx and _liveOut.testReg(rAH);
- bool isBL = not isBx and _liveOut.testReg(rBL);
- bool isBH = not isBx and _liveOut.testReg(rBH);
- bool isCL = not isCx and _liveOut.testReg(rCL);
- bool isCH = not isCx and _liveOut.testReg(rCH);
- bool isDL = not isDx and _liveOut.testReg(rDL);
- bool isDH = not isDx and _liveOut.testReg(rDH);
- if(isAL and isAH)
- {
- isAx = true;
- isAH=isAL=false;
- }
- if(isDL and isDH)
- {
- isDx = true;
- isDH=isDL=false;
- }
- if(isBL and isBH)
- {
- isBx = true;
- isBH=isBL=false;
- }
- if(isCL and isCH)
- {
- isCx = true;
- isCH=isCL=false;
- }
- if (isAx and isDx) /* long or pointer */
- {
- retVal.type = TYPE_LONG_SIGN;
- retVal.loc = REG_FRAME;
- retVal.longId() = LONGID_TYPE(rDX,rAX);
- /*idx = */localId.newLongReg(TYPE_LONG_SIGN, LONGID_TYPE(rDX,rAX), Icode.begin());
- localId.propLongId (rAX, rDX, "");
- }
- else if (isAx or isBx or isCx or isDx) /* uint16_t */
- {
- retVal.type = TYPE_WORD_SIGN;
- retVal.loc = REG_FRAME;
- if (isAx)
- retVal.id.regi = rAX;
- else if (isBx)
- retVal.id.regi = rBX;
- else if (isCx)
- retVal.id.regi = rCX;
- else
- retVal.id.regi = rDX;
- /*idx = */localId.newByteWordReg(TYPE_WORD_SIGN,retVal.id.regi);
- }
- else if(isAL or isBL or isCL or isDL)
- {
- retVal.type = TYPE_BYTE_SIGN;
- retVal.loc = REG_FRAME;
- if (isAL)
- retVal.id.regi = rAL;
- else if (isBL)
- retVal.id.regi = rBL;
- else if (isCL)
- retVal.id.regi = rCL;
- else
- retVal.id.regi = rDL;
- /*idx = */localId.newByteWordReg(TYPE_BYTE_SIGN,retVal.id.regi);
- }
- else if(isAH or isBH or isCH or isDH)
- {
- retVal.type = TYPE_BYTE_SIGN;
- retVal.loc = REG_FRAME;
- if (isAH)
- retVal.id.regi = rAH;
- else if (isBH)
- retVal.id.regi = rBH;
- else if (isCH)
- retVal.id.regi = rCH;
- else
- retVal.id.regi = rDH;
- /*idx = */localId.newByteWordReg(TYPE_BYTE_SIGN,retVal.id.regi);
- }
- }
- }
- /** Invokes procedures related with data flow analysis.
- * Works on a procedure at a time basis.
- \note indirect recursion in liveRegAnalysis is possible. */
- void Function::dataFlow(LivenessSet &_liveOut)
- {
- /* Remove references to register variables */
- if (flg & SI_REGVAR)
- _liveOut.clrReg(rSI);
- if (flg & DI_REGVAR)
- _liveOut.clrReg(rDI);
- /* Function - return value register(s) */
- preprocessReturnDU(_liveOut);
- /* Data flow analysis */
- liveAnal = true;
- elimCondCodes();
- genLiveKtes();
- liveRegAnalysis (_liveOut); /* calls dataFlow() recursively */
- if (not (flg & PROC_ASM)) /* can generate C for pProc */
- {
- genDU1 (); /* generate def/use level 1 chain */
- findExps (); /* forward substitution algorithm */
- }
- }
|