diff --git a/sl/adt_op_def.cc b/sl/adt_op_def.cc index 245c557..8d85c93 100644 --- a/sl/adt_op_def.cc +++ b/sl/adt_op_def.cc @@ -33,11 +33,12 @@ class TplFactory { stor_(stor), node_(new Trace::TransientNode("TplFactory")), ptrSize_(stor.types.dataPtrSizeof()), - objSize_(IR::rngFromNum(2 * ptrSize_)) + objSize_(IR::rngFromNum(3 * ptrSize_)) // min 3 pointers { bOff_.head = 0; bOff_.next = 0; bOff_.prev = ptrSize_; + hptr_offset_ = 2*ptrSize_; // "head" pointer } TOffset headAt() const { @@ -52,6 +53,10 @@ class TplFactory { return bOff_.prev; } + TOffset hptrAt() const { + return hptr_offset_; + } + SymHeap createHeap() const { return SymHeap(stor_, node_.node()); } @@ -59,6 +64,7 @@ class TplFactory { TObjId createObj(SymHeap *pSh, EObjKind kind) const; void nullFieldsOfObj(SymHeap *pSh, TObjId obj) const; + void nullFieldsOfObjHeadPtr(SymHeap *pSh, TObjId obj) const; void dropFieldsOfObj(SymHeap *pSh, TObjId obj) const; @@ -68,6 +74,7 @@ class TplFactory { const TSizeOf ptrSize_; const TSizeRange objSize_; BindingOff bOff_; + TOffset hptr_offset_; }; TObjId TplFactory::createObj(SymHeap *pSh, const EObjKind kind) const @@ -90,6 +97,20 @@ void TplFactory::nullFieldsOfObj(SymHeap *pSh, const TObjId obj) const prevPtr.setValue(VAL_NULL); } +void TplFactory::nullFieldsOfObjHeadPtr(SymHeap *pSh, const TObjId obj) const +{ + // obtain handles for first/last fields in header region + const PtrHandle firstPtr(*pSh, obj, 0); + const PtrHandle lastPtr(*pSh, obj, ptrSize_); + // handle for "head" pointer field + const PtrHandle headPtr(*pSh, obj, hptr_offset_); + + // nullify the fields + firstPtr.setValue(VAL_NULL); + lastPtr.setValue(VAL_NULL); + headPtr.setValue(VAL_NULL); +} + void TplFactory::dropFieldsOfObj(SymHeap *pSh, const TObjId obj) const { const TValId valUnknown = pSh->valCreate(VT_UNKNOWN, VO_ASSIGNED); @@ -150,6 +171,52 @@ void connectPush( nextPtr.setValue(VAL_NULL); } +void connectPushWithHead( + SymHeap &sh, + const TplFactory &fact, + const TObjId dls, + const TObjId reg, + const EListSide side) +{ + TOffset offNext; + TOffset offPrev; + ETargetSpecifier ts; + switch (side) { + case LS_FRONT: + offNext = fact.prevAt(); + offPrev = fact.nextAt(); + ts = TS_FIRST; + break; + + case LS_BACK: + offNext = fact.nextAt(); + offPrev = fact.prevAt(); + ts = TS_LAST; + break; + + default: + CL_BREAK_IF("invalid call of connectPushWithHead()"); + return; + } + + // obtain handles for next/prev fields + const PtrHandle nextPtr(sh, reg, offNext); + const PtrHandle prevPtr(sh, reg, offPrev); + const PtrHandle hPtr (sh, reg, fact.hptrAt()); + const PtrHandle endPtr (sh, dls, offNext); + + + // chain both objects together such that they represent a linked list + const TValId regAt = sh.addrOfTarget(reg, TS_REGION, fact.headAt()); + const TValId endAt = sh.addrOfTarget(dls, ts, fact.headAt()); + const TValId hAt = sh.addrOfTarget(dls, (ts==TS_LAST?TS_FIRST:TS_LAST), + fact.headAt()); // &"head" + endPtr.setValue(regAt); + prevPtr.setValue(endAt); + nextPtr.setValue(VAL_NULL); + hPtr.setValue(hAt); +} + OpTemplate* createPushByRef(TplFactory &fact, const EListSide side) { OpTemplate *tpl = new OpTemplate((side == LS_FRONT) @@ -195,6 +262,59 @@ OpTemplate* createPushByRef(TplFactory &fact, const EListSide side) return tpl; } +// Experimental +OpTemplate* createPushByRefHeadPtr(TplFactory &fact, const EListSide side) +{ + OpTemplate *tpl = new OpTemplate((side == LS_FRONT) + ? "push_front_by_ref_with_last_ptr" + : "push_back_by_ref_with_first_ptr"); + + SymHeap sh(fact.createHeap()); + + // allocate an uninitialized region + const TObjId reg = fact.createObj(&sh, OK_REGION); + SymHeap input(sh); + Trace::waiveCloneOperation(input); + + // nullify the next/prev/hptr fields + fact.nullFieldsOfObjHeadPtr(&sh, reg); + +{// FIXME move to factory "r.hptr = &r;" + const PtrHandle hPtr(sh, reg, fact.hptrAt()); + const TValId reg_addr = sh.addrOfTarget(reg, TS_REGION, 0 ); + hPtr.setValue(reg_addr); +} + + // register pre/post pair for push_back() to an empty list + SymHeap output(sh); + Trace::waiveCloneOperation(output); + OpFootprint *fp = new OpFootprint(input, output); + fp->inArgs.push_back(reg); + tpl->addFootprint(fp); + + // drop the nullified fields of 'reg' + fact.dropFieldsOfObj(&sh, reg); + + // allocate a DLS that will represent a container shape in our template + const TObjId dls = fact.createObj(&sh, OK_DLS); + fact.nullFieldsOfObjHeadPtr(&sh, dls); + input = sh; + + // chain both objects together such that they represent a linked list + connectPushWithHead(sh, fact, dls, reg, side); + + output = sh; + + // register pre/post pair for push_back() to a non-empty list + Trace::waiveCloneOperation(input); + Trace::waiveCloneOperation(output); + fp = new OpFootprint(input, output); + fp->inArgs.push_back(reg); + tpl->addFootprint(fp); + + return tpl; +} + OpTemplate* createPushByVal(TplFactory &fact, const EListSide side) { OpTemplate *tpl = new OpTemplate((side == LS_FRONT) @@ -244,6 +364,63 @@ OpTemplate* createPushByVal(TplFactory &fact, const EListSide side) return tpl; } +// Experimental +OpTemplate* createPushByValHeadPtr(TplFactory &fact, const EListSide side) +{ + OpTemplate *tpl = new OpTemplate((side == LS_FRONT) + ? "push_front_by_val_with_last_ptr" + : "push_back_by_val_with_first_ptr"); + + SymHeap sh(fact.createHeap()); + SymHeap input(sh); + Trace::waiveCloneOperation(input); + + // allocate an uninitialized region + TObjId reg = fact.createObj(&sh, OK_REGION); + + // nullify the next/prev fields + fact.nullFieldsOfObjHeadPtr(&sh, reg); + +{// FIXME move to factory + const PtrHandle hPtr(sh, reg, fact.hptrAt()); + const TValId reg_addr = sh.addrOfTarget(reg, TS_REGION, 0 ); + hPtr.setValue(reg_addr); +} + + // register pre/post pair for push_back() to an empty list + SymHeap output(sh); + Trace::waiveCloneOperation(output); + OpFootprint *fp = new OpFootprint(input, output); + fp->outArgs.push_back(reg); + tpl->addFootprint(fp); + + // start with a fresh heap + sh = fact.createHeap(); + Trace::waiveCloneOperation(sh); + + // allocate a DLS that will represent a container shape in our template + const TObjId dls = fact.createObj(&sh, OK_DLS); + fact.nullFieldsOfObjHeadPtr(&sh, reg); + input = sh; + + // allocate an uninitialized region + reg = fact.createObj(&sh, OK_REGION); + + // chain both objects together such that they represent a linked list + connectPushWithHead(sh, fact, dls, reg, side); + + output = sh; + + // register pre/post pair for push_back() to a non-empty list + Trace::waiveCloneOperation(input); + Trace::waiveCloneOperation(output); + fp = new OpFootprint(input, output); + fp->outArgs.push_back(reg); + tpl->addFootprint(fp); + + return tpl; +} + OpTemplate* createPop(TplFactory &fact, const EListSide side) { TOffset offNext; @@ -575,8 +752,10 @@ bool loadDefaultOperations(OpCollection *pDst, const CodeStorage::Storage &stor) TplFactory fact(stor); for (int i = LS_FRONT; i <= LS_BACK; ++i) { const EListSide side = static_cast(i); - pDst->addTemplate(createPushByRef(fact, side)); - pDst->addTemplate(createPushByVal(fact, side)); +// pDst->addTemplate(createPushByRef(fact, side)); + pDst->addTemplate(createPushByRefHeadPtr(fact, side)); +// pDst->addTemplate(createPushByVal(fact, side)); + pDst->addTemplate(createPushByValHeadPtr(fact, side)); pDst->addTemplate(createPop(fact, side)); }