From 2d3aaecf2a81ab8ce14d2518f80309ef48cd9f17 Mon Sep 17 00:00:00 2001 From: Dirk Steinke Date: Mon, 25 Aug 2014 16:05:00 +0200 Subject: [PATCH] Several bug fixes to DFG. Also some (outcommented) debug messages. --- src/src/dfg_analysis.cpp | 71 ++++++++++++++++++++++++++++++++++++----- src/x86/src/x86_xx_ins2reg.lcpp | 12 +++++-- tests/test_dfg_analysis.cpp | 24 ++++++++++---- 3 files changed, 91 insertions(+), 16 deletions(-) diff --git a/src/src/dfg_analysis.cpp b/src/src/dfg_analysis.cpp index 993ecf7..2083f25 100644 --- a/src/src/dfg_analysis.cpp +++ b/src/src/dfg_analysis.cpp @@ -8,6 +8,8 @@ #include "jitcs_callingconvention.h" #include "jitcs_int_machine.h" +//#include + jitcs::DFGAnalysis::DFGAnalysis() {} @@ -22,6 +24,9 @@ void jitcs::DFGAnalysis::init(FunctionImpl& f, AMode m, Slice touchedFixed) Slice data = alloc.allocTypedArray(bbn * 4 * rn2); Slice nextbits = alloc.allocTypedArray(bbn * rn2); Slice nextdata = alloc.allocTypedArray(bbn * rn); + +//printf("dfa init/0\n"); +//PrintFDumper dump; data.fill(0); nextbits.fill(0); @@ -47,10 +52,13 @@ void jitcs::DFGAnalysis::init(FunctionImpl& f, AMode m, Slice touchedFixed) bd.useRangeIsValid = BitSlice(nextbits.ptr(), rn); nextbits.popFront(rn2); bd.instructions = alloc.allocTypedArray(bb->instr_size()); +//printf("bb %d: sbri init\n", bb->id()); sbri.init(bd.instructions, bd.defined, bd.used, bd.useRangeIsValid, bd.useRangeData, touchedFixed); +//printf("bb %d: before extract\n", bb->id()); details->extractDefUse(bb->cinsns(), bb, sbri); +//printf("bb %d: after extract\n", bb->id()); if (m == M_Local) { bd.liveOut.setAll(); @@ -72,6 +80,8 @@ void jitcs::DFGAnalysis::init(FunctionImpl& f, AMode m, Slice touchedFixed) DynBitSlice<64> handled(bbn, true); size_t worklistn = 0; +//printf("dfa global\n"); + { std::shared_ptr cc = f.getCallingConvention(); for (FunctionImpl::const_bb_range r = f.bbs_crange(); !!r; ++r) { @@ -88,15 +98,29 @@ void jitcs::DFGAnalysis::init(FunctionImpl& f, AMode m, Slice touchedFixed) inworklist.mark(bb->id()); } } +//printf("dfa after exit nodes\n"); while (worklistn > 0) { BasicBlockImpl const* bb = worklist[--worklistn]; size_t bbid = bb->id(); +//printf("worklist: bb %d\n", bb->id()); BlockData& bbi = _blocks[bbid]; inworklist.clear(bbid); handled.mark(bbid); // update live out from live in of successors for (BasicBlockImpl::const_bb_range r = bb->succ_range(); !!r; ++r) bbi.liveOut.uniteWith(_blocks[(*r)->id()].liveIn); +//printf("liveout: "); +//bbi.liveOut.dump(dump); +//printf("\n"); +//printf("use: "); +//bbi.used.dump(dump); +//printf("\n"); +//printf("def: "); +//bbi.defined.dump(dump); +//printf("\n"); +//printf("livein: "); +//bbi.liveIn.dump(dump); +//printf("\n"); // calculate live in from use, def and live out bool changed = false; size_t nout = bbi.liveIn.wordSize(); @@ -108,18 +132,23 @@ void jitcs::DFGAnalysis::init(FunctionImpl& f, AMode m, Slice touchedFixed) changed |= pin[i] != newval; pin[i] = newval; } +//printf("new livein (%s): ", changed ? "changed" : "not changed"); +//bbi.liveIn.dump(dump); +//printf("\n"); // put predecessors into worklist for (BasicBlockImpl::const_bb_range r = bb->pred_crange(); !!r; ++r) { size_t predid = (*r)->id(); if (changed || !handled.test(predid)) { //handled.clear(predid); if (!inworklist.testAndMark(predid)) { +//printf("add bb %d to worklist\n", predid); worklist[worklistn++] = *r; } } } } } +//printf("dfa done\n"); } #if 0 @@ -174,9 +203,13 @@ void jitcs::DFGAnalysis::dump(IDumper& o) const { #endif void jitcs::GatherResourceList::_addFixed(ResClassId rclid, u32 id, u32 mask, u32 usedef) { +//printf("addfixed: %d, %d, %d, %d\n", rclid, id, mask, usedef); _JITCS_DBG_CHECK_(IsPowerOf2(mask)); - classInit |= 1 << rclid; ClassWise& cw = byClass[rclid]; + if (!(classInit & (1 << rclid))) { + cw.numFixed = cw.numNonFixed = 0; + classInit |= 1 << rclid; + } for (uint i = NUM - cw.numFixed; i < NUM; ++i) { if ((cw.touchedResources[i].resInfo >> DFGAnalysis::ResourceData::E_ResShift) == (id >> DFGAnalysis::ResourceData::E_ResShift)) { @@ -189,9 +222,13 @@ void jitcs::GatherResourceList::_addFixed(ResClassId rclid, u32 id, u32 mask, u3 _JITCS_DBG_CHECK_(cw.numFixed + cw.numNonFixed <= NUM); } void jitcs::GatherResourceList::_addNonFixed(ResClassId rclid, u32 id, u32 mask, u32 usedef) { +//printf("addnonfixed: %d, %d, %d, %d\n", rclid, id, mask, usedef); _JITCS_DBG_CHECK_(mask != 0); - classInit |= 1 << rclid; ClassWise& cw = byClass[rclid]; + if (!(classInit & (1 << rclid))) { + cw.numFixed = cw.numNonFixed = 0; + classInit |= 1 << rclid; + } for (uint i = 0; i < cw.numNonFixed; ++i) { if ((cw.touchedResources[i].resInfo >> DFGAnalysis::ResourceData::E_ResShift) == (id >> DFGAnalysis::ResourceData::E_ResShift)) { @@ -220,6 +257,7 @@ void jitcs::SetupBlockResourceInfo::init(Slice ins _next = next; _JITCS_DBG_CHECK_(def.isAllZeroes() && use.isAllZeroes()); _JITCS_DBG_CHECK_(nextValid.isAllZeroes()); + _ins = ins; _idx = ins.size(); _touchedFixed = touchedFixed; } @@ -306,8 +344,10 @@ static void _SortNonFixed(jitcs::Slice d) { void jitcs::SetupBlockResourceInfo::push_front(GatherResourceList & grl) { +//printf("pushfront -> %d\n", _idx - 1); _JITCS_DBG_CHECK_(_idx > 0); --_idx; +//printf("pushfront: ins data: (%p,%d)\n", _ins.ptr(), _ins.size()); DFGAnalysis::InstructionData& id = _ins[_idx]; size_t num = 0; u32 ci = grl.classInit; @@ -323,6 +363,7 @@ void jitcs::SetupBlockResourceInfo::push_front(GatherResourceList & grl) { ci >>= dci; ci >>= 1; rclid += dci; +//printf(" prehandle class %d\n", rclid); GatherResourceList::ClassWise& cw = grl.byClass[rclid]; _JITCS_DBG_CHECK_(cw.numFixed + cw.numNonFixed > 0 && cw.numFixed + cw.numNonFixed <= 15); while (currclid < rclid) { @@ -332,6 +373,7 @@ void jitcs::SetupBlockResourceInfo::push_front(GatherResourceList & grl) { u32 resMaskDef = 0; u32 bitcnt[GatherResourceList::NUM]; +//printf(" prehandle fixed\n"); // set use/def masks for all fixed registers/resources for (size_t i = 0; i < cw.numFixed; ++i) { size_t ix = GatherResourceList::NUM - cw.numFixed + i; @@ -342,6 +384,7 @@ void jitcs::SetupBlockResourceInfo::push_front(GatherResourceList & grl) { resMaskDef |= e.mask; } _touchedFixed[rclid] |= resMaskUse | resMaskDef; +//printf(" prehandle nonfixed\n"); // clear bits for overlapping fixed registers for (size_t i = 0; i < cw.numNonFixed; ++i) { GatherResourceList::Entry& e = cw.touchedResources[i]; @@ -353,13 +396,16 @@ void jitcs::SetupBlockResourceInfo::push_front(GatherResourceList & grl) { } // sort non fixed by number of mask bits // (fixed only have a single bit set anyway) - if (cw.numNonFixed >= 2) + if (cw.numNonFixed >= 2) { +//printf(" prehandle sort nonfixed\n"); _SortNonFixed(jitcs::Slice (cw.touchedResources, cw.numNonFixed)); + } num += cw.numFixed + cw.numNonFixed; rclids[rclnum++] = rclid; ++rclid; +//printf(" prehandle: cur num = %d\n", num); } while (currclid < _rclCnt) { id.resClassEnd[currclid++] = 0; @@ -370,13 +416,16 @@ void jitcs::SetupBlockResourceInfo::push_front(GatherResourceList & grl) { } id.ptr = _remaining.ptr(); _remaining.popFront(num); +//printf(" handle data ptr: %p\n", id.ptr); DFGAnalysis::ResourceData *p = id.ptr; for (size_t j = 0; j < rclnum; ++j) { - GatherResourceList::ClassWise& cw = grl.byClass[j]; + GatherResourceList::ClassWise& cw = grl.byClass[rclids[j]]; +//printf(" handle class %d\n", rclids[j]); for (size_t i = 0, n = cw.numFixed + cw.numNonFixed; i < n; ++i) { size_t ix = i < cw.numFixed ? GatherResourceList::NUM - cw.numFixed + i : i - cw.numFixed; const GatherResourceList::Entry& e = cw.touchedResources[ix]; +//printf(" handle copy reg %d: resid %d\n", i, e.resInfo >> 2); u32 res = e.resInfo; p->resInfo = res; p->allowedMask = e.mask; @@ -391,23 +440,29 @@ void jitcs::SetupBlockResourceInfo::push_front(GatherResourceList & grl) { } _next[r].next = (res & DFGAnalysis::ResourceData::E_Use) ? (2 * _idx) : ~0; // mark def/use +//printf(" handle reg %d: mark %s\n", i, +// (res & 3) == 1 ? "use" : +// (res & 3) == 2 ? "def" : +// (res & 3) == 3 ? "use/def" : "error"); if (res & DFGAnalysis::ResourceData::E_Def) _def.mark(r); if (res & DFGAnalysis::ResourceData::E_Use) _use.mark(r); else _use.clear(r); ++p; +//printf(" handle reg %d done\n", i); } } +//printf("pushfront end\n"); } bool jitcs::DFGAnalysis::isUsed(Ref bb, Ref v) const { - return _blocks[bb->id()].used.test(v->id); + return _blocks[bb->id()].used.test(v->res); } bool jitcs::DFGAnalysis::isDefined(Ref bb, Ref v) const { - return _blocks[bb->id()].defined.test(v->id); + return _blocks[bb->id()].defined.test(v->res); } bool jitcs::DFGAnalysis::isLiveIn(Ref bb, Ref v) const { - return _blocks[bb->id()].liveIn.test(v->id); + return _blocks[bb->id()].liveIn.test(v->res); } bool jitcs::DFGAnalysis::isLiveOut(Ref bb, Ref v) const { - return _blocks[bb->id()].liveOut.test(v->id); + return _blocks[bb->id()].liveOut.test(v->res); } bool jitcs::DFGAnalysis::isUsed(Ref bb, Ref v) const { return isUsed(Ref(reinterpret_cast(bb.ptr())), v); diff --git a/src/x86/src/x86_xx_ins2reg.lcpp b/src/x86/src/x86_xx_ins2reg.lcpp index af2f7ba..2e37c77 100644 --- a/src/x86/src/x86_xx_ins2reg.lcpp +++ b/src/x86/src/x86_xx_ins2reg.lcpp @@ -22,7 +22,8 @@ #include "jitcs_int_virtualregister.h" #include "jitcs_int_dfg_analysis.h" -#include +//#include +//#include "jitcs_dumper.h" /*| local data= runfile("../../data/x86_inslist.dat") /*| local function hex2(n) return string.format("0x%02x", n) end @@ -140,9 +141,15 @@ void jitcs::x86_%(N)::X86_%(N)MachineInfo::extractDefUse Ref bb, SetupBlockResourceInfo& dfh) const { + //PrintFDumper dumper; + //MachineDumper mdumper(dumper, *this); + GatherResourceList grl; - for (size_t ii = insns.size() - 1; ii > 0; --ii) { + for (size_t ii = insns.size(); ii > 0; --ii) { Ref ins = insns[ii - 1]; + //mdumper.write("extract ins "); + //mdumper.write(ins); + //mdumper.write("\n"); InsId i = ins->getInsId(); grl.init(); if (i == I_None) { @@ -153,6 +160,7 @@ void jitcs::x86_%(N)::X86_%(N)MachineInfo::extractDefUse assert(IsValid(icl)); u32 dfcl = ReadFromInsClassArray(_X86_%(N)UseDefClass, icl); + //mdumper.writef(" dfclass: %d\n", dfcl); switch (dfcl) { default: assert( 0 && "unsupported use/def class" ); diff --git a/tests/test_dfg_analysis.cpp b/tests/test_dfg_analysis.cpp index d723f1f..6fa096e 100644 --- a/tests/test_dfg_analysis.cpp +++ b/tests/test_dfg_analysis.cpp @@ -5,8 +5,6 @@ #include "jitcs_int_dfg_analysis.h" #include "jitcs_int_adt_dynslice.h" -#include - using namespace jitcs; static void test(UnitTest& t) { @@ -53,6 +51,7 @@ static void test(UnitTest& t) { ibuf.start(bb1); host::MOV_RI32U(ibuf, v1, 0); + host::MOV_RI32U(ibuf, v3, 4); host::JMP_FT(ibuf, bb2); ibuf.end(); @@ -86,16 +85,29 @@ static void test(UnitTest& t) { DynSlice touchedFixed(mi->details()->getResClassCount()); DFGAnalysis a; -printf("post-func-construction\n"); a.init(reinterpret_cast(*fn), DFGAnalysis::M_Global, touchedFixed); -printf("post-analysis\n"); t.check("v1/bb1/use", !a.isUsed(bb1, v1)); t.check("v1/bb1/def", a.isDefined(bb1, v1)); t.check("v1/bb1/live-in", !a.isLiveIn(bb1, v1)); t.check("v1/bb1/live-out", a.isLiveOut(bb1, v1)); + t.check("v1/bb2/use", a.isUsed(bb2, v1)); + t.check("v1/bb2/def", !a.isDefined(bb2, v1)); + t.check("v1/bb2/live-in", a.isLiveIn(bb2, v1)); + t.check("v1/bb2/live-out", a.isLiveOut(bb2, v1)); + + t.check("v1/bb3/use", a.isUsed(bb3, v1)); + t.check("v1/bb3/def", a.isDefined(bb3, v1)); + t.check("v1/bb3/live-in", a.isLiveIn(bb3, v1)); + t.check("v1/bb3/live-out", a.isLiveOut(bb3, v1)); + + t.check("v1/bb4/use", a.isUsed(bb4, v1)); + t.check("v1/bb4/def", a.isDefined(bb4, v1)); + t.check("v1/bb4/live-in", a.isLiveIn(bb4, v1)); + t.check("v1/bb4/live-out", a.isLiveOut(bb4, v1)); + t.check("v1/bb5/use", a.isUsed(bb5, v1)); t.check("v1/bb5/def", a.isDefined(bb5, v1)); t.check("v1/bb5/live-in", a.isLiveIn(bb5, v1)); @@ -146,8 +158,8 @@ printf("post-analysis\n"); t.check("v3/bb6/live-in", a.isLiveIn(bb6, v3)); t.check("v3/bb6/live-out", !a.isLiveOut(bb6, v3)); - t.check("v4/bb4/use", a.isUsed(bb4, v4)); - t.check("v4/bb4/def", !a.isDefined(bb4, v4)); + t.check("v4/bb4/use", !a.isUsed(bb4, v4)); + t.check("v4/bb4/def", a.isDefined(bb4, v4)); t.check("v4/bb4/live-in", !a.isLiveIn(bb4, v4)); t.check("v4/bb4/live-out", !a.isLiveOut(bb4, v4)); -- 2.11.4.GIT