Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source
Source file availexps.ml
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394(* compute available expressions, although in a somewhat
non-traditional way. the abstract state is a mapping from
variable ids to expressions as opposed to a set of
expressions *)openGoblintCilopenPrettyopenExpcompareopenLivenessmoduleE=ErrormsgmoduleDF=DataflowmoduleUD=UsedefmoduleIH=InthashmoduleU=UtilmoduleS=StatsexceptionUnimplementedofstringletdebug=reffalseletdoTime=reffalselettimesfa=if!doTimethenS.timesfaelsefa(*
When ignore_inst returns true, then
the instruction in question has no
effects on the abstract state.
When ignore_call returns true, then
the instruction only has side-effects
from the assignment if there is one.
*)letignore_inst=ref(funi->false)letignore_call=ref(funi->false)letregisterIgnoreInst(f:instr->bool):unit=letf'=!ignore_instinignore_inst:=(funi->(fi)||(f'i))letregisterIgnoreCall(f:instr->bool):unit=letf'=!ignore_callinignore_call:=(funi->(fi)||(f'i))(* exp IH.t -> exp IH.t -> bool *)leteh_equalseh1eh2=ifnot(IH.lengtheh1=IH.lengtheh2)thenfalseelseIH.fold(funvideb->ifnotbthenbelsetrylete2=IH.findeh2vidinifnot(compareExpStripCastsee2)thenfalseelsetruewithNot_found->false)eh1trueleteh_pretty()eh=line++seq~sep:line~doit:(fun(vid,e)->text"AE:vid:"++numvid++text": "++(d_exp()e))~elements:(IH.tolisteh)(* the result must be the intersection of eh1 and eh2 *)(* exp IH.t -> exp IH.t -> exp IH.t *)leteh_combineeh1eh2=if!debugthenignore(E.log"eh_combine: combining %a\n and\n %a\n"eh_prettyeh1eh_prettyeh2);leteh'=IH.copyeh1in(* eh' gets all of eh1 *)IH.iter(funvide1->trylete2l=IH.find_alleh2vidinifnot(List.exists(fune2->compareExpStripCastse1e2)e2l)(* remove things from eh' that eh2 doesn't have *)thenlete1l=IH.find_alleh'vidinlete1l'=List.filter(fune->not(compareExpStripCastsee1))e1linIH.remove_alleh'vid;List.iter(fune->IH.addeh'vide)e1l'withNot_found->IH.remove_alleh'vid)eh1;if!debugthenignore(E.log"with result %a\n"eh_prettyeh');eh'(* On a memory write, kill expressions containing memory reads
variables whose address has been taken, and globals. *)classmemReadOrAddrOfFinderClassbr=object(self)inheritnopCilVisitormethod!vexpre=matchewith|Lval(Mem_,_)->beginbr:=true;SkipChildrenend|AddrOf(Varvi,NoOffset)->(* Writing to memory won't change the address of something *)SkipChildren|_->DoChildrenmethod!vvrblvi=ifvi.vaddrof||vi.vglobthen(br:=true;SkipChildren)elseDoChildrenend(* exp -> bool *)letexp_has_mem_reade=letbr=reffalseinletvis=newmemReadOrAddrOfFinderClassbrinignore(visitCilExprvise);!brleteh_kill_memeh=IH.iter(funvide->ifexp_has_mem_readethenIH.removeehvid)eh(* need to kill exps containing a particular vi sometimes *)classviFinderClassvibr=object(self)inheritnopCilVisitormethod!vvrblvi'=ifvi.vid=vi'.vidthen(br:=true;SkipChildren)elseDoChildrenendletexp_has_vivie=letbr=reffalseinletvis=newviFinderClassvibrinignore(visitCilExprvise);!brleteh_kill_viehvi=IH.iter(funvide->ifexp_has_viviethenIH.removeehvid)eh(* need to kill exps containing a particular lval sometimes *)classlvalFinderClasslvbr=object(self)inheritnopCilVisitormethod!vlvall=ifcompareLvalllvthen(br:=true;SkipChildren)elseDoChildrenendletexp_has_lvallve=letbr=reffalseinletvis=newlvalFinderClasslvbrinignore(visitCilExprvise);!brleteh_kill_lvalehlv=IH.iter(funvide->ifexp_has_lvallvethenIH.removeehvid)ehclassvolatileFinderClassbr=object(self)inheritnopCilVisitormethod!vexpre=if(hasAttribute"volatile"(typeAttrs(typeOfe)))then(br:=true;SkipChildren)elseDoChildrenendletexp_is_volatilee:bool=letbr=reffalseinletvis=newvolatileFinderClassbrinignore(visitCilExprvise);!brletvarHash=IH.create32leteh_kill_addrof_or_globaleh=if!debugthenignore(E.log"eh_kill: in eh_kill\n");IH.iter(funvide->tryletvi=IH.findvarHashvidinifvi.vaddrofthenbeginif!debugthenignore(E.log"eh_kill: %s has its address taken\n"vi.vname);IH.removeehvidendelseifvi.vglobthenbeginif!debugthenignore(E.log"eh_kill: %s is global\n"vi.vname);IH.removeehvidendwithNot_found->())ehleteh_handle_instieh=if(!ignore_inst)ithenehelsematchiwith(* if a pointer write, kill things with read in them.
also kill mappings from vars that have had their address taken,
and globals.
otherwise kill things with lv in them and add e *)Set(lv,e,_,_)->(matchlvwith(Mem_,_)->(eh_kill_memeh;eh_kill_addrof_or_globaleh;eh)|(Varvi,NoOffset)whennot(exp_is_volatilee)->(matchewithLval(Varvi',NoOffset)->(* ignore x = x *)ifvi'.vid=vi.vidthenehelse(IH.replaceehvi.vide;eh_kill_viehvi;eh)|_->(IH.replaceehvi.vide;eh_kill_viehvi;eh))|(Varvi,_)->begin(* must remove mapping for vi *)IH.removeehvi.vid;eh_kill_lvalehlv;ehend)|Call(Some(Varvi,NoOffset),_,_,_,_)->(IH.removeehvi.vid;eh_kill_viehvi;ifnot((!ignore_call)i)thenbegineh_kill_memeh;eh_kill_addrof_or_globalehend;eh)|Call(_,_,_,_,_)->(eh_kill_memeh;eh_kill_addrof_or_globaleh;eh)|Asm(_,_,_,_,_,_)->let_,d=UD.computeUseDefInstriin(UD.VS.iter(funvi->eh_kill_viehvi)d;eh)|VarDecl_->raise(Unimplemented"VarDecl")(* VarDecl instruction is not supported for availexps, to make availexps work for programs without VLA *)(* make sure to set alwaysGenerateVarDecl in cabs2cil.ml to false. To support VLA, implement this. *)moduleAvailableExps=structletname="Available Expressions"letdebug=debug(* mapping from var id to expression *)typet=expIH.tletcopy=IH.copyletstmtStartData=IH.create64letpretty=eh_prettyletcomputeFirstPredecessorstmeh=ehletcombinePredecessors(stm:stmt)~(old:t)(eh:t)=iftime"eh_equals"(eh_equalsold)ehthenNoneelseSome(time"eh_combine"(eh_combineold)eh)letdoInstrieh=letaction=eh_handle_instiinDF.Post(action)letdoStmtstmastate=DF.SDefaultletdoGuardcastate=DF.GDefaultletfilterStmtstm=trueendmoduleAE=DF.ForwardsDataFlow(AvailableExps)(* make an exp IH.t with everything in it,
also, fill in varHash while we're here.
*)classvarHashMakerClass=object(self)inheritnopCilVisitormethod!vvrblvi=(ifnot(IH.memvarHashvi.vid)then(if!debug&&vi.vglobthenignore(E.log"%s is global\n"vi.vname);if!debug&¬(vi.vglob)thenignore(E.log"%s is not global\n"vi.vname);IH.addvarHashvi.vidvi));DoChildrenendletvarHashMaker=newvarHashMakerClassletmake_var_hashfd=IH.clearvarHash;ignore(visitCilFunctionvarHashMakerfd)(*
Computes AEs for function fd.
*)letcomputeAEsfd=tryletslst=fd.sbody.bstmtsinletfirst_stm=List.hdslstintime"make_var_hash"make_var_hashfd;IH.clearAvailableExps.stmtStartData;IH.addAvailableExps.stmtStartDatafirst_stm.sid(IH.create4);time"compute"AE.compute[first_stm]withFailure_->if!debugthenignore(E.log"fn w/ no stmts?\n")|Not_found->if!debugthenignore(E.log"no data for first_stm?\n")(* get the AE data for a statement *)letgetAEssid=trySome(IH.findAvailableExps.stmtStartDatasid)withNot_found->None(* get the AE data for an instruction list *)letinstrAEsilsidehout=letproc_onehili=matchhilwith[]->leteh'=IH.copyehinleteh''=eh_handle_instieh'ineh''::hil|eh'::ehrstasl->leteh'=IH.copyeh'inleteh''=eh_handle_instieh'ineh''::linletfolded=List.fold_leftproc_one[eh]ilinletfoldednotout=List.rev(List.tlfolded)infoldednotoutclassaeVisitorClass=object(self)inheritnopCilVisitorvalmutablesid=-1valmutableae_dat_lst=[]valmutablecur_ae_dat=Nonemethod!vstmtstm=sid<-stm.sid;matchgetAEssidwithNone->if!debugthenignore(E.log"aeVis: stm %d has no data\n"sid);cur_ae_dat<-None;DoChildren|Someeh->matchstm.skindwithInstril->if!debugthenignore(E.log"aeVist: visit il\n");ae_dat_lst<-time"instrAEs"(instrAEsilstm.sideh)false;DoChildren|_->if!debugthenignore(E.log"aeVisit: visit non-il\n");cur_ae_dat<-None;DoChildrenmethod!vinsti=if!debugthenignore(E.log"aeVist: before %a, ae_dat_lst is %d long\n"d_instri(List.lengthae_dat_lst));tryletdata=List.hdae_dat_lstincur_ae_dat<-Some(data);ae_dat_lst<-List.tlae_dat_lst;if!debugthenignore(E.log"aeVisit: data is %a\n"eh_prettydata);DoChildrenwithFailure_->if!debugthenignore(E.log"aeVis: il ae_dat_lst mismatch\n");DoChildrenmethodget_cur_eh()=matchcur_ae_datwithNone->getAEssid|Someeh->Someehend