Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source
Source file liveness.ml
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349(* Calculate which variables are live at
each statement.
*)openGoblintCilopenFeatureopenPrettymoduleUsedef=Usedef(* expose for zrapp *)moduleDF=DataflowmoduleUD=UsedefmoduleIH=InthashmoduleE=Errormsgletdebug=reffalse(*
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))letlive_label=ref""letlive_func=ref""moduleVS=UD.VSletdebug_print()vs=(VS.fold(funvid->d++text"name: "++textvi.vname++text" id: "++numvi.vid++text" ")vsnil)++lineletmin_print()vs=(VS.fold(funvid->d++textvi.vname++text"("++d_type()vi.vtype++text")"++text",")vsnil)++lineletprinter=refdebug_printmoduleLiveFlow=structletname="Liveness"letdebug=debugtypet=VS.tletpretty()vs=letfn=!printerinfn()vsletstmtStartData=IH.create32letfuncExitData=VS.emptyletcombineStmtStartData(stm:stmt)~(old:t)(now:t)=ifnot(VS.compareoldnow=0)thenSome(VS.unionoldnow)elseNoneletcombineSuccessors=VS.unionletdoStmtstmt=if!debugthenignore(E.log"looking at: %a\n"d_stmtstmt);lethandle_stmvs=matchstmt.skindwithInstr_->vs|s->letu,d=UD.computeUseDefStmtKindsinVS.unionu(VS.diffvsd)inDF.Posthandle_stmletdoInstrivs=lettransformvs'=if(!ignore_inst)ithenvs'elseletu,d=UD.computeUseDefInstriinVS.unionu(VS.diffvs'd)inDF.PosttransformletfilterStmtstm1stm2=trueendmoduleL=DF.BackwardsDataFlow(LiveFlow)(* XXX: This does not compute the best ordering to
give to the work-list algorithm.
*)letall_stmts=ref[]classnullAdderClass=object(self)inheritnopCilVisitormethod!vstmts=all_stmts:=s::(!all_stmts);IH.addLiveFlow.stmtStartDatas.sidVS.empty;DoChildrenendletnull_adderfdec=ignore(visitCilFunction(newnullAdderClass)fdec);!all_stmtsletcomputeLivenessfdec=IH.clearLiveFlow.stmtStartData;UD.onlyNoOffsetsAreDefs:=false;all_stmts:=[];leta=null_adderfdecintryL.computeawithE.Error->beginignore(E.log"Liveness failed on function:\n %a\n"d_global(GFun(fdec,locUnknown)));E.s"Bug in Liveness compute"endletgetLiveSetsid=trySome(IH.findLiveFlow.stmtStartDatasid)withNot_found->NoneletgetLiveness(s:stmt)=Inthash.findLiveFlow.stmtStartDatas.sidletgetPostLiveness(s:stmt):LiveFlow.t=letfoldLivenesslives=VS.unionlive(getLivenesss)inList.fold_leftfoldLivenessVS.emptys.succsletinstrLiveness(il:instrlist)(stm:stmt)(vs:VS.t)(out:bool):VS.tlist=letproc_onevsli=matchvslwith|[]->if(!ignore_inst)ithenvs::vslelseletu,d=UD.computeUseDefInstriin(VS.unionu(VS.diffvsd))::vsl|vs'::rst->if(!ignore_inst)ithenvs'::vslelseletu,d=UD.computeUseDefInstriin(VS.unionu(VS.diffvs'd))::vslinletliveout=getPostLivenessstminletfolded=List.fold_leftproc_one[liveout](List.revil)inifoutthenList.tlfoldedelsefolded(* Inherit from this to visit with liveness info at instructions.
If out is true, then gives liveness after instructions.
If out is false, then gives liveness before instructions. *)classlivenessVisitorClass(out:bool)=object(self)inheritnopCilVisitorvalmutablesid=-1valmutableliv_dat_lst=[]valmutablecur_liv_dat=Nonemethod!vstmtstm=sid<-stm.sid;matchgetLiveSetsidwith|None->beginif!debugthenE.log"livVis: stm %d has no data\n"sid;cur_liv_dat<-None;DoChildrenend|Somevs->beginmatchstm.skindwith|Instril->beginliv_dat_lst<-instrLivenessilstmvsout;DoChildrenend|_->begincur_liv_dat<-None;DoChildrenendendmethod!vinsti=tryletdata=List.hdliv_dat_lstincur_liv_dat<-Some(data);liv_dat_lst<-List.tlliv_dat_lst;if!debugthenE.log"livVis: at %a, data is %a\n"d_instridebug_printdata;DoChildrenwithFailure_->if!debugthenE.log"livnessVisitor: il liv_dat_lst mismatch\n";DoChildrenend(* Inherit from this to visit instructions with
data about which variables are newly dead after
the instruction in post_dead_vars
(and which variables are dead *before* each /statement/,
also, confusingly, in post_dead_vars).
post_live_vars contains vars that are newly live
after each instruction *)classdeadnessVisitorClass=object(self)inheritnopCilVisitorvalmutablesid=-1valmutableliv_dat_lst=[]valmutablecur_liv_dat=Nonevalmutablepost_dead_vars=VS.emptyvalmutablepost_live_vars=VS.emptymethod!vstmtstm=sid<-stm.sid;matchgetLiveSetsidwith|None->beginif!debugthenE.log"deadVis: stm %d has no data\n"sid;cur_liv_dat<-None;post_dead_vars<-VS.empty;post_live_vars<-VS.empty;DoChildrenend|Somevs->beginlet(dead,live)=List.fold_left(fun(dead,live)stm->letdvs=(* things can die in non instr statements *)matchstm.skindwith|Instr_|Block_->VS.diff(getPostLivenessstm)vs|_->VS.diff(VS.union(getLivenessstm)(getPostLivenessstm))vsinVS.uniondeaddvs,VS.unionlive(getPostLivenessstm))(VS.empty,VS.empty)stm.predsinif!debugthenE.log"deadVis: before %a, %a die, %a come to live\n"d_stmtstmdebug_printdeaddebug_printlive;post_dead_vars<-dead;post_live_vars<-VS.diffvslive;matchstm.skindwith|Instril->beginliv_dat_lst<-instrLivenessilstmvstrue;DoChildrenend|_->begincur_liv_dat<-None;DoChildrenendendmethod!vinsti=tryletdata=List.hdliv_dat_lstincur_liv_dat<-Some(data);liv_dat_lst<-List.tlliv_dat_lst;letu,d=UD.computeUseDefInstriinletinlive=VS.unionu(VS.diffdatad)in(* if both defined and used, then both dies and comes to life *)letud=VS.interudinpost_dead_vars<-VS.union(VS.diffinlivedata)ud;post_live_vars<-VS.union(VS.diffdatainlive)ud;if!debugthenE.log"deadVis: at %a, liveout: %a, inlive: %a, post_dead_vars: %a\n"d_instridebug_printdatadebug_printinlivedebug_printpost_dead_vars;DoChildrenwithFailure_->if!debugthenE.log"deadnessVisitor: il liv_dat_lst mismatch\n";post_dead_vars<-VS.empty;post_live_vars<-VS.empty;DoChildrenendletprint_everything()=letd=IH.fold(funivsd->d++numi++text": "++LiveFlow.pretty()vs)LiveFlow.stmtStartDatanilinignore(printf"%t"(fun()->d))letmatch_labellbl=matchlblwithLabel(str,_,b)->if!debugthenignore(E.log"Liveness: label seen: %s\n"str);(*b && *)(String.comparestr(!live_label)=0)|_->falseclassdoFeatureClass=object(self)inheritnopCilVisitormethod!vfuncfd=ifString.comparefd.svar.vname(!live_func)=0then(Cfg.clearCFGinfofd;ignore(Cfg.cfgFunfd);computeLivenessfd;ifString.compare(!live_label)""=0then(printer:=min_print;print_everything();SkipChildren)elseDoChildren)elseSkipChildrenmethod!vstmts=ifList.existsmatch_labels.labelsthentryletvs=IH.findLiveFlow.stmtStartDatas.sidin(printer:=min_print;ignore(printf"%a"LiveFlow.prettyvs);SkipChildren)withNot_found->if!debugthenignore(E.log"Liveness: stmt: %d not found\n"s.sid);DoChildrenelse(ifList.lengths.labels=0thenif!debugthenignore(E.log"Liveness: no label at sid=%d\n"s.sid);DoChildren)endletdo_live_feature(f:file)=visitCilFile(newdoFeatureClass)fletfeature={fd_name="Liveness";fd_enabled=false;fd_description="Spit out live variables at a label";fd_extraopt=["--live_label",Arg.String(funs->live_label:=s)," Output the variables live at this label";"--live_func",Arg.String(funs->live_func:=s)," Output the variables live at each statement in this function.";"--live_debug",Arg.Unit(funn->debug:=true)," Print lots of debugging info";];fd_doit=do_live_feature;fd_post_check=false}let()=Feature.registerfeature