Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

6846 lines (5625 sloc) 172.192 kB
/* Copyright (c) 2008-2009, Avian Contributors
Permission to use, copy, modify, and/or distribute this software
for any purpose with or without fee is hereby granted, provided
that the above copyright notice and this permission notice appear
in all copies.
There is NO WARRANTY for this software. See license.txt for
details. */
#include "compiler.h"
#include "assembler.h"
using namespace vm;
namespace {
namespace local {
const bool DebugAppend = false;
const bool DebugCompile = false;
const bool DebugResources = false;
const bool DebugFrame = false;
const bool DebugControl = false;
const bool DebugReads = false;
const bool DebugSites = false;
const bool DebugMoves = false;
const bool DebugBuddies = false;
const int AnyFrameIndex = -2;
const int NoFrameIndex = -1;
const unsigned StealRegisterReserveCount = 2;
// this should be equal to the largest number of registers used by a
// compare instruction:
const unsigned ResolveRegisterReserveCount = (BytesPerWord == 8 ? 2 : 4);
const unsigned RegisterCopyCost = 1;
const unsigned AddressCopyCost = 2;
const unsigned ConstantCopyCost = 3;
const unsigned MemoryCopyCost = 4;
const unsigned CopyPenalty = 10;
class Context;
class Value;
class Stack;
class Site;
class ConstantSite;
class AddressSite;
class RegisterSite;
class MemorySite;
class Event;
class PushEvent;
class Read;
class MultiRead;
class StubRead;
class Block;
class Snapshot;
void NO_RETURN abort(Context*);
void
apply(Context* c, UnaryOperation op,
unsigned s1Size, Site* s1Low, Site* s1High);
void
apply(Context* c, BinaryOperation op,
unsigned s1Size, Site* s1Low, Site* s1High,
unsigned s2Size, Site* s2Low, Site* s2High);
void
apply(Context* c, TernaryOperation op,
unsigned s1Size, Site* s1Low, Site* s1High,
unsigned s2Size, Site* s2Low, Site* s2High,
unsigned s3Size, Site* s3Low, Site* s3High);
class Cell {
public:
Cell(Cell* next, void* value): next(next), value(value) { }
Cell* next;
void* value;
};
class Local {
public:
Value* value;
};
class SiteMask {
public:
SiteMask(): typeMask(~0), registerMask(~0), frameIndex(AnyFrameIndex) { }
SiteMask(uint8_t typeMask, uint32_t registerMask, int frameIndex):
typeMask(typeMask), registerMask(registerMask), frameIndex(frameIndex)
{ }
uint8_t typeMask;
uint32_t registerMask;
int frameIndex;
};
class Site {
public:
Site(): next(0) { }
virtual Site* readTarget(Context*, Read*) { return this; }
virtual unsigned toString(Context*, char*, unsigned) = 0;
virtual unsigned copyCost(Context*, Site*) = 0;
virtual bool match(Context*, const SiteMask&) = 0;
virtual bool loneMatch(Context*, const SiteMask&) = 0;
virtual bool matchNextWord(Context*, Site*, unsigned) = 0;
virtual void acquire(Context*, Value*) { }
virtual void release(Context*, Value*) { }
virtual void freeze(Context*, Value*) { }
virtual void thaw(Context*, Value*) { }
virtual bool frozen(Context*) { return false; }
virtual OperandType type(Context*) = 0;
virtual void asAssemblerOperand(Context*, Site*, Assembler::Operand*) = 0;
virtual Site* copy(Context*) = 0;
virtual Site* copyLow(Context*) = 0;
virtual Site* copyHigh(Context*) = 0;
virtual Site* makeNextWord(Context*, unsigned) = 0;
virtual SiteMask mask(Context*) = 0;
virtual SiteMask nextWordMask(Context*, unsigned) = 0;
virtual unsigned registerSize(Context*) { return BytesPerWord; }
virtual unsigned registerMask(Context*) { return 0; }
virtual bool isVolatile(Context*) { return false; }
Site* next;
};
class Stack {
public:
Stack(unsigned index, Value* value, Stack* next):
index(index), value(value), next(next)
{ }
unsigned index;
Value* value;
Stack* next;
};
class ForkElement {
public:
Value* value;
MultiRead* read;
bool local;
};
class ForkState: public Compiler::State {
public:
ForkState(Stack* stack, Local* locals, Cell* saved, Event* predecessor,
unsigned logicalIp):
stack(stack),
locals(locals),
saved(saved),
predecessor(predecessor),
logicalIp(logicalIp),
readCount(0)
{ }
Stack* stack;
Local* locals;
Cell* saved;
Event* predecessor;
unsigned logicalIp;
unsigned readCount;
ForkElement elements[0];
};
class MySubroutine: public Compiler::Subroutine {
public:
MySubroutine(): forkState(0) { }
ForkState* forkState;
};
class LogicalInstruction {
public:
LogicalInstruction(int index, Stack* stack, Local* locals):
firstEvent(0), lastEvent(0), immediatePredecessor(0), stack(stack),
locals(locals), machineOffset(0), subroutine(0), index(index)
{ }
Event* firstEvent;
Event* lastEvent;
LogicalInstruction* immediatePredecessor;
Stack* stack;
Local* locals;
Promise* machineOffset;
MySubroutine* subroutine;
int index;
};
class Resource {
public:
Resource(bool reserved = false):
value(0), site(0), freezeCount(0), referenceCount(0), reserved(reserved)
{ }
virtual void freeze(Context*, Value*) = 0;
virtual void thaw(Context*, Value*) = 0;
virtual unsigned toString(Context*, char*, unsigned) = 0;
Value* value;
Site* site;
uint8_t freezeCount;
uint8_t referenceCount;
bool reserved;
};
class RegisterResource: public Resource {
public:
RegisterResource(bool reserved):
Resource(reserved)
{ }
virtual void freeze(Context*, Value*);
virtual void thaw(Context*, Value*);
virtual unsigned toString(Context* c, char* buffer, unsigned bufferSize) {
return vm::snprintf(buffer, bufferSize, "register %d", index(c));
}
virtual unsigned index(Context*);
};
class FrameResource: public Resource {
public:
virtual void freeze(Context*, Value*);
virtual void thaw(Context*, Value*);
virtual unsigned toString(Context* c, char* buffer, unsigned bufferSize) {
return vm::snprintf(buffer, bufferSize, "frame %d", index(c));
}
virtual unsigned index(Context*);
};
class ConstantPoolNode {
public:
ConstantPoolNode(Promise* promise): promise(promise), next(0) { }
Promise* promise;
ConstantPoolNode* next;
};
class Read {
public:
Read():
value(0), event(0), eventNext(0)
{ }
virtual bool intersect(SiteMask* mask, unsigned depth = 0) = 0;
virtual Value* high(Context* c) { abort(c); }
virtual Value* successor() = 0;
virtual bool valid() = 0;
virtual void append(Context* c, Read* r) = 0;
virtual Read* next(Context* c) = 0;
Value* value;
Event* event;
Read* eventNext;
};
int
intersectFrameIndexes(int a, int b)
{
if (a == NoFrameIndex or b == NoFrameIndex) return NoFrameIndex;
if (a == AnyFrameIndex) return b;
if (b == AnyFrameIndex) return a;
if (a == b) return a;
return NoFrameIndex;
}
SiteMask
intersect(const SiteMask& a, const SiteMask& b)
{
return SiteMask(a.typeMask & b.typeMask, a.registerMask & b.registerMask,
intersectFrameIndexes(a.frameIndex, b.frameIndex));
}
class Value: public Compiler::Operand {
public:
Value(Site* site, Site* target, ValueType type):
reads(0), lastRead(0), sites(site), source(0), target(target), buddy(this),
nextWord(this), home(NoFrameIndex), type(type), wordIndex(0)
{ }
Read* reads;
Read* lastRead;
Site* sites;
Site* source;
Site* target;
Value* buddy;
Value* nextWord;
int8_t home;
ValueType type;
uint8_t wordIndex;
};
uint32_t
registerMask(Assembler::Architecture* arch)
{
return arch->generalRegisterMask() | arch->floatRegisterMask();
}
unsigned
maskStart(uint32_t mask)
{
for (int i = 0; i <= 31; ++i) {
if (mask & (1 << i)) return i;
}
return 32;
}
unsigned
maskLimit(uint32_t mask)
{
for (int i = 31; i >= 0; --i) {
if (mask & (1 << i)) return i + 1;
}
return 0;
}
class Context {
public:
Context(System* system, Assembler* assembler, Zone* zone,
Compiler::Client* client):
system(system),
assembler(assembler),
arch(assembler->arch()),
zone(zone),
client(client),
stack(0),
locals(0),
saved(0),
predecessor(0),
logicalCode(0),
registerStart(maskStart(registerMask(arch))),
registerLimit(maskLimit(registerMask(arch))),
generalRegisterStart(maskStart(arch->generalRegisterMask())),
generalRegisterLimit(maskLimit(arch->generalRegisterMask())),
floatRegisterStart(maskStart(arch->floatRegisterMask())),
floatRegisterLimit(maskLimit(arch->floatRegisterMask())),
registerResources
(static_cast<RegisterResource*>
(zone->allocate(sizeof(RegisterResource) * registerLimit))),
frameResources(0),
firstConstant(0),
lastConstant(0),
machineCode(0),
firstEvent(0),
lastEvent(0),
forkState(0),
subroutine(0),
logicalIp(-1),
constantCount(0),
logicalCodeLength(0),
parameterFootprint(0),
localFootprint(0),
machineCodeSize(0),
alignedFrameSize(0),
availableGeneralRegisterCount(generalRegisterLimit - generalRegisterStart)
{
for (unsigned i = generalRegisterStart; i < generalRegisterLimit; ++i) {
new (registerResources + i) RegisterResource(arch->reserved(i));
if (registerResources[i].reserved) {
-- availableGeneralRegisterCount;
}
}
for (unsigned i = floatRegisterStart; i < floatRegisterLimit; ++i) {
new (registerResources + i) RegisterResource(arch->reserved(i));
}
}
System* system;
Assembler* assembler;
Assembler::Architecture* arch;
Zone* zone;
Compiler::Client* client;
Stack* stack;
Local* locals;
Cell* saved;
Event* predecessor;
LogicalInstruction** logicalCode;
uint8_t registerStart;
uint8_t registerLimit;
uint8_t generalRegisterStart;
uint8_t generalRegisterLimit;
uint8_t floatRegisterStart;
uint8_t floatRegisterLimit;
RegisterResource* registerResources;
FrameResource* frameResources;
ConstantPoolNode* firstConstant;
ConstantPoolNode* lastConstant;
uint8_t* machineCode;
Event* firstEvent;
Event* lastEvent;
ForkState* forkState;
MySubroutine* subroutine;
int logicalIp;
unsigned constantCount;
unsigned logicalCodeLength;
unsigned parameterFootprint;
unsigned localFootprint;
unsigned machineCodeSize;
unsigned alignedFrameSize;
unsigned availableGeneralRegisterCount;
};
unsigned
RegisterResource::index(Context* c)
{
return this - c->registerResources;
}
unsigned
FrameResource::index(Context* c)
{
return this - c->frameResources;
}
class PoolPromise: public Promise {
public:
PoolPromise(Context* c, int key): c(c), key(key) { }
virtual int64_t value() {
if (resolved()) {
return reinterpret_cast<intptr_t>
(c->machineCode + pad(c->machineCodeSize) + (key * BytesPerWord));
}
abort(c);
}
virtual bool resolved() {
return c->machineCode != 0;
}
Context* c;
int key;
};
class CodePromise: public Promise {
public:
CodePromise(Context* c, CodePromise* next):
c(c), offset(0), next(next)
{ }
CodePromise(Context* c, Promise* offset):
c(c), offset(offset), next(0)
{ }
virtual int64_t value() {
if (resolved()) {
return reinterpret_cast<intptr_t>(c->machineCode + offset->value());
}
abort(c);
}
virtual bool resolved() {
return c->machineCode != 0 and offset and offset->resolved();
}
Context* c;
Promise* offset;
CodePromise* next;
};
unsigned
machineOffset(Context* c, int logicalIp)
{
return c->logicalCode[logicalIp]->machineOffset->value();
}
class IpPromise: public Promise {
public:
IpPromise(Context* c, int logicalIp):
c(c),
logicalIp(logicalIp)
{ }
virtual int64_t value() {
if (resolved()) {
return reinterpret_cast<intptr_t>
(c->machineCode + machineOffset(c, logicalIp));
}
abort(c);
}
virtual bool resolved() {
return c->machineCode != 0;
}
Context* c;
int logicalIp;
};
inline void NO_RETURN
abort(Context* c)
{
abort(c->system);
}
#ifndef NDEBUG
inline void
assert(Context* c, bool v)
{
assert(c->system, v);
}
#endif // not NDEBUG
inline void
expect(Context* c, bool v)
{
expect(c->system, v);
}
unsigned
count(Cell* c)
{
unsigned count = 0;
while (c) {
++ count;
c = c->next;
}
return count;
}
Cell*
cons(Context* c, void* value, Cell* next)
{
return new (c->zone->allocate(sizeof(Cell))) Cell(next, value);
}
Cell*
append(Context* c, Cell* first, Cell* second)
{
if (first) {
if (second) {
Cell* start = cons(c, first->value, second);
Cell* end = start;
for (Cell* cell = first->next; cell; cell = cell->next) {
Cell* n = cons(c, cell->value, second);
end->next = n;
end = n;
}
return start;
} else {
return first;
}
} else {
return second;
}
}
Cell*
reverseDestroy(Cell* cell)
{
Cell* previous = 0;
while (cell) {
Cell* next = cell->next;
cell->next = previous;
previous = cell;
cell = next;
}
return previous;
}
class StubReadPair {
public:
Value* value;
StubRead* read;
};
class JunctionState {
public:
JunctionState(unsigned frameFootprint): frameFootprint(frameFootprint) { }
unsigned frameFootprint;
StubReadPair reads[0];
};
class Link {
public:
Link(Event* predecessor, Link* nextPredecessor, Event* successor,
Link* nextSuccessor, ForkState* forkState):
predecessor(predecessor), nextPredecessor(nextPredecessor),
successor(successor), nextSuccessor(nextSuccessor), forkState(forkState),
junctionState(0)
{ }
Event* predecessor;
Link* nextPredecessor;
Event* successor;
Link* nextSuccessor;
ForkState* forkState;
JunctionState* junctionState;
};
Link*
link(Context* c, Event* predecessor, Link* nextPredecessor, Event* successor,
Link* nextSuccessor, ForkState* forkState)
{
return new (c->zone->allocate(sizeof(Link))) Link
(predecessor, nextPredecessor, successor, nextSuccessor, forkState);
}
unsigned
countPredecessors(Link* link)
{
unsigned c = 0;
for (; link; link = link->nextPredecessor) ++ c;
return c;
}
Link*
lastPredecessor(Link* link)
{
while (link->nextPredecessor) link = link->nextPredecessor;
return link;
}
unsigned
countSuccessors(Link* link)
{
unsigned c = 0;
for (; link; link = link->nextSuccessor) ++ c;
return c;
}
class Event {
public:
Event(Context* c):
next(0), stackBefore(c->stack), localsBefore(c->locals),
stackAfter(0), localsAfter(0), promises(0), reads(0),
junctionSites(0), snapshots(0), predecessors(0), successors(0),
visitLinks(0), block(0), logicalInstruction(c->logicalCode[c->logicalIp]),
readCount(0)
{ }
virtual const char* name() = 0;
virtual void compile(Context* c) = 0;
virtual bool isBranch() { return false; }
virtual bool allExits() { return false; }
Event* next;
Stack* stackBefore;
Local* localsBefore;
Stack* stackAfter;
Local* localsAfter;
CodePromise* promises;
Read* reads;
Site** junctionSites;
Snapshot* snapshots;
Link* predecessors;
Link* successors;
Cell* visitLinks;
Block* block;
LogicalInstruction* logicalInstruction;
unsigned readCount;
};
unsigned
totalFrameSize(Context* c)
{
return c->alignedFrameSize
+ c->arch->frameHeaderSize()
+ c->arch->argumentFootprint(c->parameterFootprint);
}
int
frameIndex(Context* c, int localIndex)
{
assert(c, localIndex >= 0);
int index = c->alignedFrameSize + c->parameterFootprint - localIndex - 1;
if (localIndex < static_cast<int>(c->parameterFootprint)) {
index += c->arch->frameHeaderSize();
} else {
index -= c->arch->frameFooterSize();
}
assert(c, index >= 0);
assert(c, static_cast<unsigned>(index) < totalFrameSize(c));
return index;
}
unsigned
frameIndexToOffset(Context* c, unsigned frameIndex)
{
assert(c, frameIndex < totalFrameSize(c));
return (frameIndex + c->arch->frameFooterSize()) * BytesPerWord;
}
unsigned
offsetToFrameIndex(Context* c, unsigned offset)
{
assert(c, static_cast<int>
((offset / BytesPerWord) - c->arch->frameFooterSize()) >= 0);
assert(c, ((offset / BytesPerWord) - c->arch->frameFooterSize())
< totalFrameSize(c));
return (offset / BytesPerWord) - c->arch->frameFooterSize();
}
unsigned
frameBase(Context* c)
{
return c->alignedFrameSize
- c->arch->frameReturnAddressSize()
- c->arch->frameFooterSize()
+ c->arch->frameHeaderSize();
}
class FrameIterator {
public:
class Element {
public:
Element(Value* value, unsigned localIndex):
value(value), localIndex(localIndex)
{ }
Value* const value;
const unsigned localIndex;
};
FrameIterator(Context* c, Stack* stack, Local* locals,
bool includeEmpty = false):
stack(stack), locals(locals), localIndex(c->localFootprint - 1),
includeEmpty(includeEmpty)
{ }
bool hasMore() {
if (not includeEmpty) {
while (stack and stack->value == 0) stack = stack->next;
while (localIndex >= 0 and locals[localIndex].value == 0) -- localIndex;
}
return stack != 0 or localIndex >= 0;
}
Element next(Context* c) {
Value* v;
unsigned li;
if (stack) {
Stack* s = stack;
v = s->value;
li = s->index + c->localFootprint;
stack = stack->next;
} else {
Local* l = locals + localIndex;
v = l->value;
li = localIndex;
-- localIndex;
}
return Element(v, li);
}
Stack* stack;
Local* locals;
int localIndex;
bool includeEmpty;
};
int
frameIndex(Context* c, FrameIterator::Element* element)
{
return frameIndex(c, element->localIndex);
}
class SiteIterator {
public:
SiteIterator(Context* c, Value* v, bool includeBuddies = true,
bool includeNextWord = true):
c(c),
originalValue(v),
currentValue(v),
includeBuddies(includeBuddies),
includeNextWord(includeNextWord),
pass(0),
next_(findNext(&(v->sites))),
previous(0)
{ }
Site** findNext(Site** p) {
while (true) {
if (*p) {
if (pass == 0 or (*p)->registerSize(c) > BytesPerWord) {
return p;
} else {
p = &((*p)->next);
}
} else {
if (includeBuddies) {
Value* v = currentValue->buddy;
if (v != originalValue) {
currentValue = v;
p = &(v->sites);
continue;
}
}
if (includeNextWord and pass == 0) {
Value* v = originalValue->nextWord;
if (v != originalValue) {
pass = 1;
originalValue = v;
currentValue = v;
p = &(v->sites);
continue;
}
}
return 0;
}
}
}
bool hasMore() {
if (previous) {
next_ = findNext(&((*previous)->next));
previous = 0;
}
return next_ != 0;
}
Site* next() {
previous = next_;
return *previous;
}
void remove(Context* c) {
(*previous)->release(c, originalValue);
*previous = (*previous)->next;
next_ = findNext(previous);
previous = 0;
}
Context* c;
Value* originalValue;
Value* currentValue;
bool includeBuddies;
bool includeNextWord;
uint8_t pass;
Site** next_;
Site** previous;
};
bool
hasSite(Context* c, Value* v)
{
SiteIterator it(c, v);
return it.hasMore();
}
bool
findSite(Context*, Value* v, Site* site)
{
for (Site* s = v->sites; s; s = s->next) {
if (s == site) return true;
}
return false;
}
bool
uniqueSite(Context* c, Value* v, Site* s)
{
SiteIterator it(c, v);
Site* p UNUSED = it.next();
if (it.hasMore()) {
// the site is not this word's only site, but if the site is
// shared with the next word, it may be that word's only site
if (v->nextWord != v and s->registerSize(c) > BytesPerWord) {
SiteIterator nit(c, v->nextWord);
Site* p = nit.next();
if (nit.hasMore()) {
return false;
} else {
return p == s;
}
} else {
return false;
}
} else {
assert(c, p == s);
return true;
}
}
void
addSite(Context* c, Value* v, Site* s)
{
if (not findSite(c, v, s)) {
if (DebugSites) {
char buffer[256]; s->toString(c, buffer, 256);
fprintf(stderr, "add site %s to %p\n", buffer, v);
}
s->acquire(c, v);
s->next = v->sites;
v->sites = s;
}
}
void
removeSite(Context* c, Value* v, Site* s)
{
for (SiteIterator it(c, v); it.hasMore();) {
if (s == it.next()) {
if (DebugSites) {
char buffer[256]; s->toString(c, buffer, 256);
fprintf(stderr, "remove site %s from %p\n", buffer, v);
}
it.remove(c);
break;
}
}
if (DebugSites) {
fprintf(stderr, "%p has more: %d\n", v, hasSite(c, v));
}
assert(c, not findSite(c, v, s));
}
void
clearSites(Context* c, Value* v)
{
if (DebugSites) {
fprintf(stderr, "clear sites for %p\n", v);
}
for (SiteIterator it(c, v); it.hasMore();) {
it.next();
it.remove(c);
}
}
bool
valid(Read* r)
{
return r and r->valid();
}
Read*
live(Value* v)
{
Value* p = v;
do {
if (valid(p->reads)) {
return p->reads;
}
p = p->buddy;
} while (p != v);
return 0;
}
Read*
liveNext(Context* c, Value* v)
{
Read* r = v->reads->next(c);
if (valid(r)) return r;
for (Value* p = v->buddy; p != v; p = p->buddy) {
if (valid(p->reads)) return p->reads;
}
return 0;
}
unsigned
sitesToString(Context* c, Value* v, char* buffer, unsigned size);
void
deadWord(Context* c, Value* v)
{
Value* nextWord = v->nextWord;
assert(c, nextWord != v);
for (SiteIterator it(c, v, true, false); it.hasMore();) {
Site* s = it.next();
if (s->registerSize(c) > BytesPerWord) {
it.remove(c);
addSite(c, nextWord, s);
}
}
}
void
deadBuddy(Context* c, Value* v, Read* r UNUSED)
{
assert(c, v->buddy != v);
assert(c, r);
if (DebugBuddies) {
fprintf(stderr, "remove dead buddy %p from", v);
for (Value* p = v->buddy; p != v; p = p->buddy) {
fprintf(stderr, " %p", p);
}
fprintf(stderr, "\n");
}
assert(c, v->buddy);
Value* next = v->buddy;
v->buddy = v;
Value* p = next;
while (p->buddy != v) p = p->buddy;
p->buddy = next;
assert(c, p->buddy);
for (SiteIterator it(c, v, false, false); it.hasMore();) {
Site* s = it.next();
it.remove(c);
addSite(c, next, s);
}
}
void
popRead(Context* c, Event* e UNUSED, Value* v)
{
assert(c, e == v->reads->event);
if (DebugReads) {
fprintf(stderr, "pop read %p from %p next %p event %p (%s)\n",
v->reads, v, v->reads->next(c), e, (e ? e->name() : 0));
}
v->reads = v->reads->next(c);
if (not valid(v->reads)) {
Value* nextWord = v->nextWord;
if (nextWord != v) {
if (valid(nextWord->reads)) {
deadWord(c, v);
} else {
deadWord(c, nextWord);
}
}
Read* r = live(v);
if (r) {
deadBuddy(c, v, r);
} else {
clearSites(c, v);
}
}
}
bool
buddies(Value* a, Value* b)
{
if (a == b) return true;
for (Value* p = a->buddy; p != a; p = p->buddy) {
if (p == b) return true;
}
return false;
}
void
addBuddy(Value* original, Value* buddy)
{
buddy->buddy = original;
Value* p = original;
while (p->buddy != original) p = p->buddy;
p->buddy = buddy;
if (DebugBuddies) {
fprintf(stderr, "add buddy %p to", buddy);
for (Value* p = buddy->buddy; p != buddy; p = p->buddy) {
fprintf(stderr, " %p", p);
}
fprintf(stderr, "\n");
}
}
void
decrementAvailableGeneralRegisterCount(Context* c)
{
assert(c, c->availableGeneralRegisterCount);
-- c->availableGeneralRegisterCount;
if (DebugResources) {
fprintf(stderr, "%d registers available\n",
c->availableGeneralRegisterCount);
}
}
void
incrementAvailableGeneralRegisterCount(Context* c)
{
++ c->availableGeneralRegisterCount;
if (DebugResources) {
fprintf(stderr, "%d registers available\n",
c->availableGeneralRegisterCount);
}
}
void
increment(Context* c, RegisterResource* r)
{
if (not r->reserved) {
if (DebugResources) {
char buffer[256]; r->toString(c, buffer, 256);
fprintf(stderr, "increment %s to %d\n", buffer, r->referenceCount + 1);
}
++ r->referenceCount;
if (r->referenceCount == 1
and ((1 << r->index(c)) & c->arch->generalRegisterMask()))
{
decrementAvailableGeneralRegisterCount(c);
}
}
}
void
decrement(Context* c, RegisterResource* r)
{
if (not r->reserved) {
if (DebugResources) {
char buffer[256]; r->toString(c, buffer, 256);
fprintf(stderr, "decrement %s to %d\n", buffer, r->referenceCount - 1);
}
assert(c, r->referenceCount > 0);
-- r->referenceCount;
if (r->referenceCount == 0
and ((1 << r->index(c)) & c->arch->generalRegisterMask()))
{
incrementAvailableGeneralRegisterCount(c);
}
}
}
void
freezeResource(Context* c, Resource* r, Value* v)
{
if (DebugResources) {
char buffer[256]; r->toString(c, buffer, 256);
fprintf(stderr, "%p freeze %s to %d\n", v, buffer, r->freezeCount + 1);
}
++ r->freezeCount;
}
void
RegisterResource::freeze(Context* c, Value* v)
{
if (not reserved) {
freezeResource(c, this, v);
if (freezeCount == 1
and ((1 << index(c)) & c->arch->generalRegisterMask()))
{
decrementAvailableGeneralRegisterCount(c);
}
}
}
void
FrameResource::freeze(Context* c, Value* v)
{
freezeResource(c, this, v);
}
void
thawResource(Context* c, Resource* r, Value* v)
{
if (not r->reserved) {
if (DebugResources) {
char buffer[256]; r->toString(c, buffer, 256);
fprintf(stderr, "%p thaw %s to %d\n", v, buffer, r->freezeCount - 1);
}
assert(c, r->freezeCount);
-- r->freezeCount;
}
}
void
RegisterResource::thaw(Context* c, Value* v)
{
if (not reserved) {
thawResource(c, this, v);
if (freezeCount == 0
and ((1 << index(c)) & c->arch->generalRegisterMask()))
{
incrementAvailableGeneralRegisterCount(c);
}
}
}
void
FrameResource::thaw(Context* c, Value* v)
{
thawResource(c, this, v);
}
class Target {
public:
static const unsigned MinimumRegisterCost = 0;
static const unsigned MinimumFrameCost = 1;
static const unsigned StealPenalty = 2;
static const unsigned StealUniquePenalty = 4;
static const unsigned IndirectMovePenalty = 4;
static const unsigned LowRegisterPenalty = 10;
static const unsigned Impossible = 20;
Target(): cost(Impossible) { }
Target(int index, OperandType type, unsigned cost):
index(index), type(type), cost(cost)
{ }
int16_t index;
OperandType type;
uint8_t cost;
};
ValueType
valueType(Context* c, Compiler::OperandType type)
{
switch (type) {
case Compiler::ObjectType:
case Compiler::AddressType:
case Compiler::IntegerType:
case Compiler::VoidType:
return ValueGeneral;
case Compiler::FloatType:
return ValueFloat;
default:
abort(c);
}
}
class CostCalculator {
public:
virtual unsigned cost(Context* c, uint8_t typeMask, uint32_t registerMask,
int frameIndex) = 0;
};
unsigned
resourceCost(Context* c, Value* v, Resource* r, uint8_t typeMask,
uint32_t registerMask, int frameIndex,
CostCalculator* costCalculator)
{
if (r->reserved or r->freezeCount or r->referenceCount) {
return Target::Impossible;
} else {
unsigned baseCost = costCalculator ? costCalculator->cost
(c, typeMask, registerMask, frameIndex) : 0;
if (r->value) {
assert(c, findSite(c, r->value, r->site));
if (v and buddies(r->value, v)) {
return baseCost;
} else if (uniqueSite(c, r->value, r->site)) {
return baseCost + Target::StealUniquePenalty;
} else {
return baseCost = Target::StealPenalty;
}
} else {
return baseCost;
}
}
}
bool
pickRegisterTarget(Context* c, int i, Value* v, uint32_t mask, int* target,
unsigned* cost, CostCalculator* costCalculator = 0)
{
if ((1 << i) & mask) {
RegisterResource* r = c->registerResources + i;
unsigned myCost = resourceCost
(c, v, r, 1 << RegisterOperand, 1 << i, NoFrameIndex, costCalculator)
+ Target::MinimumRegisterCost;
if ((static_cast<uint32_t>(1) << i) == mask) {
*cost = myCost;
return true;
} else if (myCost < *cost) {
*cost = myCost;
*target = i;
}
}
return false;
}
int
pickRegisterTarget(Context* c, Value* v, uint32_t mask, unsigned* cost,
CostCalculator* costCalculator = 0)
{
int target = NoRegister;
*cost = Target::Impossible;
if (mask & c->arch->generalRegisterMask()) {
for (int i = c->generalRegisterLimit - 1;
i >= c->generalRegisterStart; --i)
{
if (pickRegisterTarget(c, i, v, mask, &target, cost, costCalculator)) {
return i;
}
}
}
if (mask & c->arch->floatRegisterMask()) {
for (int i = c->floatRegisterStart;
i < static_cast<int>(c->floatRegisterLimit); ++i)
{
if (pickRegisterTarget(c, i, v, mask, &target, cost, costCalculator)) {
return i;
}
}
}
return target;
}
Target
pickRegisterTarget(Context* c, Value* v, uint32_t mask,
CostCalculator* costCalculator = 0)
{
unsigned cost;
int number = pickRegisterTarget(c, v, mask, &cost, costCalculator);
return Target(number, RegisterOperand, cost);
}
unsigned
frameCost(Context* c, Value* v, int frameIndex, CostCalculator* costCalculator)
{
return resourceCost
(c, v, c->frameResources + frameIndex, 1 << MemoryOperand, 0, frameIndex,
costCalculator)
+ Target::MinimumFrameCost;
}
Target
pickFrameTarget(Context* c, Value* v, CostCalculator* costCalculator)
{
Target best;
Value* p = v;
do {
if (p->home >= 0) {
Target mine
(p->home, MemoryOperand, frameCost(c, v, p->home, costCalculator));
if (mine.cost == Target::MinimumFrameCost) {
return mine;
} else if (mine.cost < best.cost) {
best = mine;
}
}
p = p->buddy;
} while (p != v);
return best;
}
Target
pickAnyFrameTarget(Context* c, Value* v, CostCalculator* costCalculator)
{
Target best;
unsigned count = totalFrameSize(c);
for (unsigned i = 0; i < count; ++i) {
Target mine(i, MemoryOperand, frameCost(c, v, i, costCalculator));
if (mine.cost == Target::MinimumFrameCost) {
return mine;
} else if (mine.cost < best.cost) {
best = mine;
}
}
return best;
}
Target
pickTarget(Context* c, Value* value, const SiteMask& mask,
unsigned registerPenalty, Target best,
CostCalculator* costCalculator)
{
if (mask.typeMask & (1 << RegisterOperand)) {
Target mine = pickRegisterTarget
(c, value, mask.registerMask, costCalculator);
mine.cost += registerPenalty;
if (mine.cost == Target::MinimumRegisterCost) {
return mine;
} else if (mine.cost < best.cost) {
best = mine;
}
}
if (mask.typeMask & (1 << MemoryOperand)) {
if (mask.frameIndex >= 0) {
Target mine(mask.frameIndex, MemoryOperand,
frameCost(c, value, mask.frameIndex, costCalculator));
if (mine.cost == Target::MinimumFrameCost) {
return mine;
} else if (mine.cost < best.cost) {
best = mine;
}
} else if (mask.frameIndex == AnyFrameIndex) {
Target mine = pickFrameTarget(c, value, costCalculator);
if (mine.cost == Target::MinimumFrameCost) {
return mine;
} else if (mine.cost < best.cost) {
best = mine;
}
}
}
return best;
}
Target
pickTarget(Context* c, Read* read, bool intersectRead,
unsigned registerReserveCount, CostCalculator* costCalculator)
{
unsigned registerPenalty
= (c->availableGeneralRegisterCount > registerReserveCount
? 0 : Target::LowRegisterPenalty);
Value* value = read->value;
uint32_t registerMask
= (value->type == ValueFloat ? ~0 : c->arch->generalRegisterMask());
SiteMask mask(~0, registerMask, AnyFrameIndex);
read->intersect(&mask);
if (value->type == ValueFloat) {
uint32_t floatMask = mask.registerMask & c->arch->floatRegisterMask();
if (floatMask) {
mask.registerMask = floatMask;
}
}
Target best;
Value* successor = read->successor();
if (successor) {
Read* r = live(successor);
if (r) {
SiteMask intersection = mask;
if (r->intersect(&intersection)) {
best = pickTarget
(c, value, intersection, registerPenalty, best, costCalculator);
if (best.cost <= Target::MinimumFrameCost) {
return best;
}
}
}
}
best = pickTarget(c, value, mask, registerPenalty, best, costCalculator);
if (best.cost <= Target::MinimumFrameCost) {
return best;
}
if (intersectRead) {
if (best.cost == Target::Impossible) {
fprintf(stderr, "mask type %d reg %d frame %d\n",
mask.typeMask, mask.registerMask, mask.frameIndex);
abort(c);
}
return best;
}
{ Target mine = pickRegisterTarget(c, value, registerMask, costCalculator);
mine.cost += registerPenalty;
if (mine.cost == Target::MinimumRegisterCost) {
return mine;
} else if (mine.cost < best.cost) {
best = mine;
}
}
{ Target mine = pickFrameTarget(c, value, costCalculator);
if (mine.cost == Target::MinimumFrameCost) {
return mine;
} else if (mine.cost < best.cost) {
best = mine;
}
}
if (best.cost >= Target::StealUniquePenalty
and c->availableGeneralRegisterCount == 0)
{
// there are no free registers left, so moving from memory to
// memory isn't an option - try harder to find an available frame
// site:
best = pickAnyFrameTarget(c, value, costCalculator);
assert(c, best.cost <= 3);
}
if (best.cost == Target::Impossible) {
abort(c);
}
return best;
}
void
acquire(Context* c, Resource* resource, Value* value, Site* site);
void
release(Context* c, Resource* resource, Value* value, Site* site);
ConstantSite*
constantSite(Context* c, Promise* value);
ShiftMaskPromise*
shiftMaskPromise(Context* c, Promise* base, unsigned shift, int64_t mask)
{
return new (c->zone->allocate(sizeof(ShiftMaskPromise)))
ShiftMaskPromise(base, shift, mask);
}
CombinedPromise*
combinedPromise(Context* c, Promise* low, Promise* high)
{
return new (c->zone->allocate(sizeof(CombinedPromise)))
CombinedPromise(low, high);
}
class ConstantSite: public Site {
public:
ConstantSite(Promise* value): value(value) { }
virtual unsigned toString(Context*, char* buffer, unsigned bufferSize) {
if (value->resolved()) {
return vm::snprintf
(buffer, bufferSize, "constant %"LLD, value->value());
} else {
return vm::snprintf(buffer, bufferSize, "constant unresolved");
}
}
virtual unsigned copyCost(Context*, Site* s) {
return (s == this ? 0 : ConstantCopyCost);
}
virtual bool match(Context*, const SiteMask& mask) {
return mask.typeMask & (1 << ConstantOperand);
}
virtual bool loneMatch(Context*, const SiteMask&) {
return true;
}
virtual bool matchNextWord(Context* c, Site* s, unsigned) {
return s->type(c) == ConstantOperand;
}
virtual OperandType type(Context*) {
return ConstantOperand;
}
virtual void asAssemblerOperand(Context* c, Site* high,
Assembler::Operand* result)
{
Promise* v = value;
if (high != this) {
v = combinedPromise(c, value, static_cast<ConstantSite*>(high)->value);
}
new (result) Assembler::Constant(v);
}
virtual Site* copy(Context* c) {
return constantSite(c, value);
}
virtual Site* copyLow(Context* c) {
return constantSite(c, shiftMaskPromise(c, value, 0, 0xFFFFFFFF));
}
virtual Site* copyHigh(Context* c) {
return constantSite(c, shiftMaskPromise(c, value, 32, 0xFFFFFFFF));
}
virtual Site* makeNextWord(Context* c, unsigned) {
abort(c);
}
virtual SiteMask mask(Context*) {
return SiteMask(1 << ConstantOperand, 0, NoFrameIndex);
}
virtual SiteMask nextWordMask(Context*, unsigned) {
return SiteMask(1 << ConstantOperand, 0, NoFrameIndex);
}
Promise* value;
};
ConstantSite*
constantSite(Context* c, Promise* value)
{
return new (c->zone->allocate(sizeof(ConstantSite))) ConstantSite(value);
}
ResolvedPromise*
resolved(Context* c, int64_t value)
{
return new (c->zone->allocate(sizeof(ResolvedPromise)))
ResolvedPromise(value);
}
ConstantSite*
constantSite(Context* c, int64_t value)
{
return constantSite(c, resolved(c, value));
}
AddressSite*
addressSite(Context* c, Promise* address);
class AddressSite: public Site {
public:
AddressSite(Promise* address): address(address) { }
virtual unsigned toString(Context*, char* buffer, unsigned bufferSize) {
if (address->resolved()) {
return vm::snprintf
(buffer, bufferSize, "address %"LLD, address->value());
} else {
return vm::snprintf(buffer, bufferSize, "address unresolved");
}
}
virtual unsigned copyCost(Context*, Site* s) {
return (s == this ? 0 : AddressCopyCost);
}
virtual bool match(Context*, const SiteMask& mask) {
return mask.typeMask & (1 << AddressOperand);
}
virtual bool loneMatch(Context*, const SiteMask&) {
return false;
}
virtual bool matchNextWord(Context* c, Site*, unsigned) {
abort(c);
}
virtual OperandType type(Context*) {
return AddressOperand;
}
virtual void asAssemblerOperand(Context* c UNUSED, Site* high UNUSED,
Assembler::Operand* result)
{
assert(c, high == this);
new (result) Assembler::Address(address);
}
virtual Site* copy(Context* c) {
return addressSite(c, address);
}
virtual Site* copyLow(Context* c) {
abort(c);
}
virtual Site* copyHigh(Context* c) {
abort(c);
}
virtual Site* makeNextWord(Context* c, unsigned) {
abort(c);
}
virtual SiteMask mask(Context*) {
return SiteMask(1 << AddressOperand, 0, NoFrameIndex);
}
virtual SiteMask nextWordMask(Context* c, unsigned) {
abort(c);
}
Promise* address;
};
AddressSite*
addressSite(Context* c, Promise* address)
{
return new (c->zone->allocate(sizeof(AddressSite))) AddressSite(address);
}
RegisterSite*
freeRegisterSite(Context* c, uint32_t mask);
class RegisterSite: public Site {
public:
RegisterSite(uint32_t mask, int number):
mask_(mask), number(number)
{ }
virtual unsigned toString(Context*, char* buffer, unsigned bufferSize) {
if (number != NoRegister) {
return vm::snprintf(buffer, bufferSize, "%p register %d", this, number);
} else {
return vm::snprintf(buffer, bufferSize,
"%p register unacquired (mask %d)", this, mask_);
}
}
virtual unsigned copyCost(Context* c, Site* s) {
assert(c, number != NoRegister);
if (s and
(this == s or
(s->type(c) == RegisterOperand
and (static_cast<RegisterSite*>(s)->mask_ & (1 << number)))))
{
return 0;
} else {
return RegisterCopyCost;
}
}
virtual bool match(Context* c UNUSED, const SiteMask& mask) {
assert(c, number != NoRegister);
if ((mask.typeMask & (1 << RegisterOperand))) {
return ((static_cast<uint64_t>(1) << number) & mask.registerMask);
} else {
return false;
}
}
virtual bool loneMatch(Context* c UNUSED, const SiteMask& mask) {
assert(c, number != NoRegister);
if ((mask.typeMask & (1 << RegisterOperand))) {
return ((static_cast<uint64_t>(1) << number) == mask.registerMask);
} else {
return false;
}
}
virtual bool matchNextWord(Context* c, Site* s, unsigned) {
assert(c, number != NoRegister);
if (s->type(c) != RegisterOperand) {
return false;
}
RegisterSite* rs = static_cast<RegisterSite*>(s);
unsigned size = rs->registerSize(c);
if (size > BytesPerWord) {
assert(c, number != NoRegister);
return number == rs->number;
} else {
uint32_t mask = c->arch->generalRegisterMask();
return ((1 << number) & mask) and ((1 << rs->number) & mask);
}
}
virtual void acquire(Context* c, Value* v) {
Target target;
if (number != NoRegister) {
target = Target(number, RegisterOperand, 0);
} else {
target = pickRegisterTarget(c, v, mask_);
expect(c, target.cost < Target::Impossible);
}
RegisterResource* resource = c->registerResources + target.index;
local::acquire(c, resource, v, this);
number = target.index;
}
virtual void release(Context* c, Value* v) {
assert(c, number != NoRegister);
local::release(c, c->registerResources + number, v, this);
}
virtual void freeze(Context* c, Value* v) {
assert(c, number != NoRegister);
c->registerResources[number].freeze(c, v);
}
virtual void thaw(Context* c, Value* v) {
assert(c, number != NoRegister);
c->registerResources[number].thaw(c, v);
}
virtual bool frozen(Context* c UNUSED) {
assert(c, number != NoRegister);
return c->registerResources[number].freezeCount != 0;
}
virtual OperandType type(Context*) {
return RegisterOperand;
}
virtual void asAssemblerOperand(Context* c UNUSED, Site* high,
Assembler::Operand* result)
{
assert(c, number != NoRegister);
int highNumber;
if (high != this) {
highNumber = static_cast<RegisterSite*>(high)->number;
assert(c, highNumber != NoRegister);
} else {
highNumber = NoRegister;
}
new (result) Assembler::Register(number, highNumber);
}
virtual Site* copy(Context* c) {
uint32_t mask;
if (number != NoRegister) {
mask = 1 << number;
} else {
mask = mask_;
}
return freeRegisterSite(c, mask);
}
virtual Site* copyLow(Context* c) {
abort(c);
}
virtual Site* copyHigh(Context* c) {
abort(c);
}
virtual Site* makeNextWord(Context* c, unsigned) {
assert(c, number != NoRegister);
assert(c, ((1 << number) & c->arch->generalRegisterMask()));
return freeRegisterSite(c, c->arch->generalRegisterMask());
}
virtual SiteMask mask(Context* c UNUSED) {
return SiteMask(1 << RegisterOperand, mask_, NoFrameIndex);
}
virtual SiteMask nextWordMask(Context* c, unsigned) {
assert(c, number != NoRegister);
if (registerSize(c) > BytesPerWord) {
return SiteMask
(1 << RegisterOperand, number, NoFrameIndex);
} else {
return SiteMask
(1 << RegisterOperand, c->arch->generalRegisterMask(), NoFrameIndex);
}
}
virtual unsigned registerSize(Context* c) {
assert(c, number != NoRegister);
if ((1 << number) & c->arch->floatRegisterMask()) {
return c->arch->floatRegisterSize();
} else {
return BytesPerWord;
}
}
virtual unsigned registerMask(Context* c UNUSED) {
assert(c, number != NoRegister);
return 1 << number;
}
uint32_t mask_;
int number;
};
RegisterSite*
registerSite(Context* c, int number)
{
assert(c, number >= 0);
assert(c, (1 << number) & (c->arch->generalRegisterMask()
| c->arch->floatRegisterMask()));
return new (c->zone->allocate(sizeof(RegisterSite)))
RegisterSite(1 << number, number);
}
RegisterSite*
freeRegisterSite(Context* c, uint32_t mask)
{
return new (c->zone->allocate(sizeof(RegisterSite)))
RegisterSite(mask, NoRegister);
}
MemorySite*
memorySite(Context* c, int base, int offset = 0, int index = NoRegister,
unsigned scale = 1);
class MemorySite: public Site {
public:
MemorySite(int base, int offset, int index, unsigned scale):
acquired(false), base(base), offset(offset), index(index), scale(scale)
{ }
virtual unsigned toString(Context*, char* buffer, unsigned bufferSize) {
if (acquired) {
return vm::snprintf(buffer, bufferSize, "memory %d 0x%x %d %d",
base, offset, index, scale);
} else {
return vm::snprintf(buffer, bufferSize, "memory unacquired");
}
}
virtual unsigned copyCost(Context* c, Site* s) {
assert(c, acquired);
if (s and
(this == s or
(s->type(c) == MemoryOperand
and static_cast<MemorySite*>(s)->base == base
and static_cast<MemorySite*>(s)->offset == offset
and static_cast<MemorySite*>(s)->index == index
and static_cast<MemorySite*>(s)->scale == scale)))
{
return 0;
} else {
return MemoryCopyCost;
}
}
virtual bool match(Context* c, const SiteMask& mask) {
assert(c, acquired);
if (mask.typeMask & (1 << MemoryOperand)) {
if (mask.frameIndex >= 0) {
if (base == c->arch->stack()) {
assert(c, index == NoRegister);
return static_cast<int>(frameIndexToOffset(c, mask.frameIndex))
== offset;
} else {
return false;
}
} else {
return true;
}
} else {
return false;
}
}
virtual bool loneMatch(Context* c, const SiteMask& mask) {
assert(c, acquired);
if (mask.typeMask & (1 << MemoryOperand)) {
if (base == c->arch->stack()) {
assert(c, index == NoRegister);
if (mask.frameIndex == AnyFrameIndex) {
return false;
} else {
return true;
}
}
}
return false;
}
virtual bool matchNextWord(Context* c, Site* s, unsigned index) {
if (s->type(c) == MemoryOperand) {
MemorySite* ms = static_cast<MemorySite*>(s);
return ms->base == this->base
and ((index == 1 and ms->offset == static_cast<int>
(this->offset + BytesPerWord))
or (index == 0 and this->offset == static_cast<int>
(ms->offset + BytesPerWord)))
and ms->index == this->index
and ms->scale == this->scale;
} else {
return false;
}
}
virtual void acquire(Context* c, Value* v) {
increment(c, c->registerResources + base);
if (index != NoRegister) {
increment(c, c->registerResources + index);
}
if (base == c->arch->stack()) {
assert(c, index == NoRegister);
assert
(c, not c->frameResources[offsetToFrameIndex(c, offset)].reserved);
local::acquire
(c, c->frameResources + offsetToFrameIndex(c, offset), v, this);
}
acquired = true;
}
virtual void release(Context* c, Value* v) {
if (base == c->arch->stack()) {
assert(c, index == NoRegister);
assert
(c, not c->frameResources[offsetToFrameIndex(c, offset)].reserved);
local::release
(c, c->frameResources + offsetToFrameIndex(c, offset), v, this);
}
decrement(c, c->registerResources + base);
if (index != NoRegister) {
decrement(c, c->registerResources + index);
}
acquired = false;
}
virtual void freeze(Context* c, Value* v) {
if (base == c->arch->stack()) {
c->frameResources[offsetToFrameIndex(c, offset)].freeze(c, v);
} else {
increment(c, c->registerResources + base);
if (index != NoRegister) {
increment(c, c->registerResources + index);
}
}
}
virtual void thaw(Context* c, Value* v) {
if (base == c->arch->stack()) {
c->frameResources[offsetToFrameIndex(c, offset)].thaw(c, v);
} else {
decrement(c, c->registerResources + base);
if (index != NoRegister) {
decrement(c, c->registerResources + index);
}
}
}
virtual bool frozen(Context* c) {
return base == c->arch->stack()
and c->frameResources[offsetToFrameIndex(c, offset)].freezeCount != 0;
}
virtual OperandType type(Context*) {
return MemoryOperand;
}
virtual void asAssemblerOperand(Context* c UNUSED, Site* high UNUSED,
Assembler::Operand* result)
{
// todo: endianness?
assert(c, high == this
or (static_cast<MemorySite*>(high)->base == base
and static_cast<MemorySite*>(high)->offset
== static_cast<int>(offset + BytesPerWord)
and static_cast<MemorySite*>(high)->index == index
and static_cast<MemorySite*>(high)->scale == scale));
assert(c, acquired);
new (result) Assembler::Memory(base, offset, index, scale);
}
virtual Site* copy(Context* c) {
return memorySite(c, base, offset, index, scale);
}
Site* copyHalf(Context* c, bool add) {
if (add) {
return memorySite(c, base, offset + BytesPerWord, index, scale);
} else {
return copy(c);
}
}
virtual Site* copyLow(Context* c) {
return copyHalf(c, c->arch->bigEndian());
}
virtual Site* copyHigh(Context* c) {
return copyHalf(c, not c->arch->bigEndian());
}
virtual Site* makeNextWord(Context* c, unsigned index) {
// todo: endianness?
return memorySite
(c, base, offset + (index == 1 ? BytesPerWord : -BytesPerWord),
this->index, scale);
}
virtual SiteMask mask(Context* c) {
return SiteMask(1 << MemoryOperand, 0, (base == c->arch->stack())
? static_cast<int>(offsetToFrameIndex(c, offset))
: NoFrameIndex);
}
virtual SiteMask nextWordMask(Context* c, unsigned index) {
// todo: endianness?
int frameIndex;
if (base == c->arch->stack()) {
assert(c, this->index == NoRegister);
frameIndex = static_cast<int>(offsetToFrameIndex(c, offset))
+ (index == 1 ? 1 : -1);
} else {
frameIndex = NoFrameIndex;
}
return SiteMask(1 << MemoryOperand, 0, frameIndex);
}
virtual bool isVolatile(Context* c) {
return base != c->arch->stack();
}
bool acquired;
int base;
int offset;
int index;
unsigned scale;
};
MemorySite*
memorySite(Context* c, int base, int offset, int index, unsigned scale)
{
return new (c->zone->allocate(sizeof(MemorySite)))
MemorySite(base, offset, index, scale);
}
MemorySite*
frameSite(Context* c, int frameIndex)
{
assert(c, frameIndex >= 0);
return memorySite
(c, c->arch->stack(), frameIndexToOffset(c, frameIndex), NoRegister, 0);
}
void
move(Context* c, Value* value, Site* src, Site* dst);
unsigned
sitesToString(Context* c, Site* sites, char* buffer, unsigned size)
{
unsigned total = 0;
for (Site* s = sites; s; s = s->next) {
total += s->toString(c, buffer + total, size - total);
if (s->next) {
assert(c, size > total + 2);
memcpy(buffer + total, ", ", 2);
total += 2;
}
}
assert(c, size > total);
buffer[total] = 0;
return total;
}
unsigned
sitesToString(Context* c, Value* v, char* buffer, unsigned size)
{
unsigned total = 0;
Value* p = v;
do {
if (total) {
assert(c, size > total + 2);
memcpy(buffer + total, "; ", 2);
total += 2;
}
if (p->sites) {
total += vm::snprintf(buffer + total, size - total, "%p has ", p);
total += sitesToString(c, p->sites, buffer + total, size - total);
} else {
total += vm::snprintf(buffer + total, size - total, "%p has nothing", p);
}
p = p->buddy;
} while (p != v);
return total;
}
Site*
pickTargetSite(Context* c, Read* read, bool intersectRead = false,
unsigned registerReserveCount = 0,
CostCalculator* costCalculator = 0)
{
Target target
(pickTarget
(c, read, intersectRead, registerReserveCount, costCalculator));
expect(c, target.cost < Target::Impossible);
if (target.type == MemoryOperand) {
return frameSite(c, target.index);
} else {
return registerSite(c, target.index);
}
}
class SingleRead: public Read {
public:
SingleRead(const SiteMask& mask, Value* successor):
next_(0), mask(mask), high_(0), successor_(successor)
{ }
virtual bool intersect(SiteMask* mask, unsigned) {
*mask = local::intersect(*mask, this->mask);
return true;
}
virtual Value* high(Context*) {
return high_;
}
virtual Value* successor() {
return successor_;
}
virtual bool valid() {
return true;
}
virtual void append(Context* c UNUSED, Read* r) {
assert(c, next_ == 0);
next_ = r;
}
virtual Read* next(Context*) {
return next_;
}
Read* next_;
SiteMask mask;
Value* high_;
Value* successor_;
};
SingleRead*
read(Context* c, const SiteMask& mask, Value* successor = 0)
{
assert(c, (mask.typeMask != 1 << MemoryOperand) or mask.frameIndex >= 0);
return new (c->zone->allocate(sizeof(SingleRead)))
SingleRead(mask, successor);
}
bool
acceptMatch(Context* c, Site* s, Read*, const SiteMask& mask)
{
return s->match(c, mask);
}
Site*
pickSourceSite(Context* c, Read* read, Site* target = 0,
unsigned* cost = 0, SiteMask* extraMask = 0,
bool intersectRead = true, bool includeBuddies = true,
bool includeNextWord = true,
bool (*accept)(Context*, Site*, Read*, const SiteMask&)
= acceptMatch)
{
SiteMask mask;
if (extraMask) {
mask = intersect(mask, *extraMask);
}
if (intersectRead) {
read->intersect(&mask);
}
Site* site = 0;
unsigned copyCost = 0xFFFFFFFF;
for (SiteIterator it(c, read->value, includeBuddies, includeNextWord);
it.hasMore();)
{
Site* s = it.next();
if (accept(c, s, read, mask)) {
unsigned v = s->copyCost(c, target);
if (v < copyCost) {
site = s;
copyCost = v;
}
}
}
if (DebugMoves and site and target) {
char srcb[256]; site->toString(c, srcb, 256);
char dstb[256]; target->toString(c, dstb, 256);
fprintf(stderr, "pick source %s to %s for %p cost %d\n",
srcb, dstb, read->value, copyCost);
}
if (cost) *cost = copyCost;
return site;
}
Site*
maybeMove(Context* c, Read* read, bool intersectRead, bool includeNextWord,
unsigned registerReserveCount = 0)
{
Value* value = read->value;
unsigned size = value == value->nextWord ? BytesPerWord : 8;
class MyCostCalculator: public CostCalculator {
public:
MyCostCalculator(Value* value, unsigned size, bool includeNextWord):
value(value),
size(size),
includeNextWord(includeNextWord)
{ }
virtual unsigned cost(Context* c, uint8_t typeMask, uint32_t registerMask,
int frameIndex)
{
uint8_t srcTypeMask;
uint64_t srcRegisterMask;
uint8_t tmpTypeMask;
uint64_t tmpRegisterMask;
c->arch->planMove
(size, &srcTypeMask, &srcRegisterMask,
&tmpTypeMask, &tmpRegisterMask,
typeMask, registerMask);
SiteMask srcMask(srcTypeMask, srcRegisterMask, AnyFrameIndex);
SiteMask dstMask(typeMask, registerMask, frameIndex);
for (SiteIterator it(c, value, true, includeNextWord); it.hasMore();) {
Site* s = it.next();
if (s->match(c, srcMask) or s->match(c, dstMask)) {
return 0;
}
}
return Target::IndirectMovePenalty;
}
Value* value;
unsigned size;
bool includeNextWord;
} costCalculator(value, size, includeNextWord);
Site* dst = pickTargetSite
(c, read, intersectRead, registerReserveCount, &costCalculator);
uint8_t srcTypeMask;
uint64_t srcRegisterMask;
uint8_t tmpTypeMask;
uint64_t tmpRegisterMask;
c->arch->planMove
(size, &srcTypeMask, &srcRegisterMask,
&tmpTypeMask, &tmpRegisterMask,
1 << dst->type(c), dst->registerMask(c));
SiteMask srcMask(srcTypeMask, srcRegisterMask, AnyFrameIndex);
unsigned cost = 0xFFFFFFFF;
Site* src = 0;
for (SiteIterator it(c, value, true, includeNextWord); it.hasMore();) {
Site* s = it.next();
unsigned v = s->copyCost(c, dst);
if (v == 0) {
src = s;
cost = 0;
break;
}
if (not s->match(c, srcMask)) {
v += CopyPenalty;
}
if (v < cost) {
src = s;
cost = v;
}
}
if (cost) {
if (DebugMoves) {
char srcb[256]; src->toString(c, srcb, 256);
char dstb[256]; dst->toString(c, dstb, 256);
fprintf(stderr, "maybe move %s to %s for %p to %p\n",
srcb, dstb, value, value);
}
src->freeze(c, value);
addSite(c, value, dst);
src->thaw(c, value);
if (not src->match(c, srcMask)) {
src->freeze(c, value);
dst->freeze(c, value);
SiteMask tmpMask(tmpTypeMask, tmpRegisterMask, AnyFrameIndex);
SingleRead tmpRead(tmpMask, 0);
tmpRead.value = value;
tmpRead.successor_ = value;
Site* tmp = pickTargetSite(c, &tmpRead, true);
addSite(c, value, tmp);
move(c, value, src, tmp);
dst->thaw(c, value);
src->thaw(c, value);
src = tmp;
}
move(c, value, src, dst);
}
return dst;
}
Site*
maybeMove(Context* c, Value* v, const SiteMask& mask, bool intersectMask,
bool includeNextWord, unsigned registerReserveCount = 0)
{
SingleRead read(mask, 0);
read.value = v;
read.successor_ = v;
return maybeMove
(c, &read, intersectMask, includeNextWord, registerReserveCount);
}
Site*
pickSiteOrMove(Context* c, Read* read, bool intersectRead,
bool includeNextWord, unsigned registerReserveCount = 0)
{
Site* s = pickSourceSite
(c, read, 0, 0, 0, intersectRead, true, includeNextWord);
if (s) {
return s;
} else {
return maybeMove
(c, read, intersectRead, includeNextWord, registerReserveCount);
}
}
Site*
pickSiteOrMove(Context* c, Value* v, const SiteMask& mask, bool intersectMask,
bool includeNextWord, unsigned registerReserveCount = 0)
{
SingleRead read(mask, 0);
read.value = v;
read.successor_ = v;
return pickSiteOrMove
(c, &read, intersectMask, includeNextWord, registerReserveCount);
}
void
steal(Context* c, Resource* r, Value* thief)
{
if (DebugResources) {
char resourceBuffer[256]; r->toString(c, resourceBuffer, 256);
char siteBuffer[1024]; sitesToString(c, r->value, siteBuffer, 1024);
fprintf(stderr, "%p steal %s from %p (%s)\n",
thief, resourceBuffer, r->value, siteBuffer);
}
if ((not (thief and buddies(thief, r->value))
and uniqueSite(c, r->value, r->site)))
{
r->site->freeze(c, r->value);
maybeMove(c, live(r->value), false, true, StealRegisterReserveCount);
r->site->thaw(c, r->value);
}
removeSite(c, r->value, r->site);
}
void
acquire(Context* c, Resource* resource, Value* value, Site* site)
{
assert(c, value);
assert(c, site);
if (not resource->reserved) {
if (DebugResources) {
char buffer[256]; resource->toString(c, buffer, 256);
fprintf(stderr, "%p acquire %s\n", value, buffer);
}
if (resource->value) {
assert(c, findSite(c, resource->value, resource->site));
assert(c, not findSite(c, value, resource->site));
steal(c, resource, value);
}
resource->value = value;
resource->site = site;
}
}
void
release(Context* c, Resource* resource, Value* value UNUSED, Site* site UNUSED)
{
if (not resource->reserved) {
if (DebugResources) {
char buffer[256]; resource->toString(c, buffer, 256);
fprintf(stderr, "%p release %s\n", resource->value, buffer);
}
assert(c, resource->value);
assert(c, resource->site);
assert(c, buddies(resource->value, value));
assert(c, site == resource->site);
resource->value = 0;
resource->site = 0;
}
}
SiteMask
generalRegisterMask(Context* c)
{
return SiteMask
(1 << RegisterOperand, c->arch->generalRegisterMask(), NoFrameIndex);
}
SiteMask
generalRegisterOrConstantMask(Context* c)
{
return SiteMask
((1 << RegisterOperand) | (1 << ConstantOperand),
c->arch->generalRegisterMask(), NoFrameIndex);
}
SiteMask
fixedRegisterMask(int number)
{
return SiteMask(1 << RegisterOperand, 1 << number, NoFrameIndex);
}
class MultiRead: public Read {
public:
MultiRead():
reads(0), lastRead(0), firstTarget(0), lastTarget(0), visited(false)
{ }
virtual bool intersect(SiteMask* mask, unsigned depth) {
if (depth > 0) {
// short-circuit recursion to avoid poor performance in
// deeply-nested branches
return reads != 0;
}
bool result = false;
if (not visited) {
visited = true;
for (Cell** cell = &reads; *cell;) {
Read* r = static_cast<Read*>((*cell)->value);
bool valid = r->intersect(mask, depth + 1);
if (valid) {
result = true;
cell = &((*cell)->next);
} else {
*cell = (*cell)->next;
}
}
visited = false;
}
return result;
}
virtual Value* successor() {
return 0;
}
virtual bool valid() {
bool result = false;
if (not visited) {
visited = true;
for (Cell** cell = &reads; *cell;) {
Read* r = static_cast<Read*>((*cell)->value);
if (r->valid()) {
result = true;
cell = &((*cell)->next);
} else {
*cell = (*cell)->next;
}
}
visited = false;
}
return result;
}
virtual void append(Context* c, Read* r) {
Cell* cell = cons(c, r, 0);
if (lastRead == 0) {
reads = cell;
} else {
lastRead->next = cell;
}
lastRead = cell;
// fprintf(stderr, "append %p to %p for %p\n", r, lastTarget, this);
lastTarget->value = r;
}
virtual Read* next(Context* c) {
abort(c);
}
void allocateTarget(Context* c) {
Cell* cell = cons(c, 0, 0);
// fprintf(stderr, "allocate target for %p: %p\n", this, cell);
if (lastTarget) {
lastTarget->next = cell;
} else {
firstTarget = cell;
}
lastTarget = cell;
}
Read* nextTarget() {
// fprintf(stderr, "next target for %p: %p\n", this, firstTarget);
Read* r = static_cast<Read*>(firstTarget->value);
firstTarget = firstTarget->next;
return r;
}
Cell* reads;
Cell* lastRead;
Cell* firstTarget;
Cell* lastTarget;
bool visited;
};
MultiRead*
multiRead(Context* c)
{
return new (c->zone->allocate(sizeof(MultiRead))) MultiRead;
}
class StubRead: public Read {
public:
StubRead():
next_(0), read(0), visited(false), valid_(true)
{ }
virtual bool intersect(SiteMask* mask, unsigned depth) {
if (not visited) {
visited = true;
if (read) {
bool valid = read->intersect(mask, depth);
if (not valid) {
read = 0;
}
}
visited = false;
}
return valid_;
}
virtual Value* successor() {
return 0;
}
virtual bool valid() {
return valid_;
}
virtual void append(Context* c UNUSED, Read* r) {
assert(c, next_ == 0);
next_ = r;
}
virtual Read* next(Context*) {
return next_;
}
Read* next_;
Read* read;
bool visited;
bool valid_;
};
StubRead*
stubRead(Context* c)
{
return new (c->zone->allocate(sizeof(StubRead))) StubRead;
}
Site*
pickSite(Context* c, Value* v, Site* s, unsigned index, bool includeNextWord)
{
for (SiteIterator it(c, v, true, includeNextWord); it.hasMore();) {
Site* candidate = it.next();
if (s->matchNextWord(c, candidate, index)) {
return candidate;
}
}
return 0;
}
Site*
pickSiteOrMove(Context* c, Value* v, Site* s, unsigned index)
{
Site* n = pickSite(c, v, s, index, false);
if (n) {
return n;
}
return maybeMove(c, v, s->nextWordMask(c, index), true, false);
}
Site*
pickSiteOrMove(Context* c, Value* v, Site* s, Site** low, Site** high)
{
if (v->wordIndex == 0) {
*low = s;
*high = pickSiteOrMove(c, v->nextWord, s, 1);
return *high;
} else {
*low = pickSiteOrMove(c, v->nextWord, s, 0);
*high = s;
return *low;
}
}
Site*
pickSiteOrGrow(Context* c, Value* v, Site* s, unsigned index)
{
Site* n = pickSite(c, v, s, index, false);
if (n) {
return n;
}
n = s->makeNextWord(c, index);
addSite(c, v, n);
return n;
}
Site*
pickSiteOrGrow(Context* c, Value* v, Site* s, Site** low, Site** high)
{
if (v->wordIndex == 0) {
*low = s;
*high = pickSiteOrGrow(c, v->nextWord, s, 1);
return *high;
} else {
*low = pickSiteOrGrow(c, v->nextWord, s, 0);
*high = s;
return *low;
}
}
bool
isHome(Value* v, int frameIndex)
{
Value* p = v;
do {
if (p->home == frameIndex) {
return true;
}
p = p->buddy;
} while (p != v);
return false;
}
bool
acceptForResolve(Context* c, Site* s, Read* read, const SiteMask& mask)
{
if (acceptMatch(c, s, read, mask) and (not s->frozen(c))) {
if (s->type(c) == RegisterOperand) {
return c->availableGeneralRegisterCount > ResolveRegisterReserveCount;
} else {
assert(c, s->match(c, SiteMask(1 << MemoryOperand, 0, AnyFrameIndex)));
return isHome(read->value, offsetToFrameIndex
(c, static_cast<MemorySite*>(s)->offset));
}
} else {
return false;
}
}
void
move(Context* c, Value* value, Site* src, Site* dst)
{
if (DebugMoves) {
char srcb[256]; src->toString(c, srcb, 256);
char dstb[256]; dst->toString(c, dstb, 256);
fprintf(stderr, "move %s to %s for %p to %p\n",
srcb, dstb, value, value);
}
assert(c, findSite(c, value, dst));
src->freeze(c, value);
dst->freeze(c, value);
unsigned srcSize;
unsigned dstSize;
if (value->nextWord == value) {
srcSize = BytesPerWord;
dstSize = BytesPerWord;
} else {
srcSize = src->registerSize(c);
dstSize = dst->registerSize(c);
}
if (srcSize == dstSize) {
apply(c, Move, srcSize, src, src, dstSize, dst, dst);
} else if (srcSize > BytesPerWord) {
Site* low, *high, *other = pickSiteOrGrow(c, value, dst, &low, &high);
other->freeze(c, value->nextWord);
apply(c, Move, srcSize, src, src, srcSize, low, high);
other->thaw(c, value->nextWord);
} else {
Site* low, *high, *other = pickSiteOrMove(c, value, src, &low, &high);
other->freeze(c, value->nextWord);
apply(c, Move, dstSize, low, high, dstSize, dst, dst);
other->thaw(c, value->nextWord);
}
dst->thaw(c, value);
src->thaw(c, value);
}
void
asAssemblerOperand(Context* c, Site* low, Site* high,
Assembler::Operand* result)
{
low->asAssemblerOperand(c, high, result);
}
class OperandUnion: public Assembler::Operand {
// must be large enough and aligned properly to hold any operand
// type (we'd use an actual union type here, except that classes
// with constructors cannot be used in a union):
uintptr_t padding[4];
};
void
apply(Context* c, UnaryOperation op,
unsigned s1Size, Site* s1Low, Site* s1High)
{
assert(c, s1Low->type(c) == s1High->type(c));
OperandType s1Type = s1Low->type(c);
OperandUnion s1Union; asAssemblerOperand(c, s1Low, s1High, &s1Union);
c->assembler->apply(op, s1Size, s1Type, &s1Union);
}
void
apply(Context* c, BinaryOperation op,
unsigned s1Size, Site* s1Low, Site* s1High,
unsigned s2Size, Site* s2Low, Site* s2High)
{
assert(c, s1Low->type(c) == s1High->type(c));
assert(c, s2Low->type(c) == s2High->type(c));
OperandType s1Type = s1Low->type(c);
OperandUnion s1Union; asAssemblerOperand(c, s1Low, s1High, &s1Union);
OperandType s2Type = s2Low->type(c);
OperandUnion s2Union; asAssemblerOperand(c, s2Low, s2High, &s2Union);
c->assembler->apply(op, s1Size, s1Type, &s1Union,
s2Size, s2Type, &s2Union);
}
void
apply(Context* c, TernaryOperation op,
unsigned s1Size, Site* s1Low, Site* s1High,
unsigned s2Size, Site* s2Low, Site* s2High,
unsigned s3Size, Site* s3Low, Site* s3High)
{
assert(c, s1Low->type(c) == s1High->type(c));
assert(c, s2Low->type(c) == s2High->type(c));
assert(c, s3Low->type(c) == s3High->type(c));
OperandType s1Type = s1Low->type(c);
OperandUnion s1Union; asAssemblerOperand(c, s1Low, s1High, &s1Union);
OperandType s2Type = s2Low->type(c);
OperandUnion s2Union; asAssemblerOperand(c, s2Low, s2High, &s2Union);
OperandType s3Type = s3Low->type(c);
OperandUnion s3Union; asAssemblerOperand(c, s3Low, s3High, &s3Union);
c->assembler->apply(op, s1Size, s1Type, &s1Union,
s2Size, s2Type, &s2Union,
s3Size, s3Type, &s3Union);
}
void
addRead(Context* c, Event* e, Value* v, Read* r)
{
if (DebugReads) {
fprintf(stderr, "add read %p to %p last %p event %p (%s)\n",
r, v, v->lastRead, e, (e ? e->name() : 0));
}
r->value = v;
if (e) {
r->event = e;
r->eventNext = e->reads;
e->reads = r;
++ e->readCount;
}
if (v->lastRead) {
// if (DebugReads) {
// fprintf(stderr, "append %p to %p for %p\n", r, v->lastRead, v);
// }
v->lastRead->append(c, r);
} else {
v->reads = r;
}
v->lastRead = r;
}
void
addRead(Context* c, Event* e, Value* v, const SiteMask& mask,
Value* successor = 0)
{
addRead(c, e, v, read(c, mask, successor));
}
void
addReads(Context* c, Event* e, Value* v, unsigned size,
const SiteMask& lowMask, Value* lowSuccessor,
const SiteMask& highMask, Value* highSuccessor)
{
SingleRead* r = read(c, lowMask, lowSuccessor);
addRead(c, e, v, r);
if (size > BytesPerWord) {
r->high_ = v->nextWord;
addRead(c, e, v->nextWord, highMask, highSuccessor);
}
}
void
addReads(Context* c, Event* e, Value* v, unsigned size,
const SiteMask& lowMask, const SiteMask& highMask)
{
addReads(c, e, v, size, lowMask, 0, highMask, 0);
}
void
clean(Context* c, Value* v, unsigned popIndex)
{
for (SiteIterator it(c, v); it.hasMore();) {
Site* s = it.next();
if (not (s->match(c, SiteMask(1 << MemoryOperand, 0, AnyFrameIndex))
and offsetToFrameIndex
(c, static_cast<MemorySite*>(s)->offset)
>= popIndex))
{
if (false and
s->match(c, SiteMask(1 << MemoryOperand, 0, AnyFrameIndex)))
{
char buffer[256]; s->toString(c, buffer, 256);
fprintf(stderr, "remove %s from %p at %d pop offset 0x%x\n",
buffer, v, offsetToFrameIndex
(c, static_cast<MemorySite*>(s)->offset),
frameIndexToOffset(c, popIndex));
}
it.remove(c);
}
}
}
void
clean(Context* c, Event* e, Stack* stack, Local* locals, Read* reads,
unsigned popIndex)
{
for (FrameIterator it(c, stack, locals); it.hasMore();) {
FrameIterator::Element e = it.next(c);
clean(c, e.value, popIndex);
}
for (Read* r = reads; r; r = r->eventNext) {
popRead(c, e, r->value);
}
}
CodePromise*
codePromise(Context* c, Event* e)
{
return e->promises = new (c->zone->allocate(sizeof(CodePromise)))
CodePromise(c, e->promises);
}
CodePromise*
codePromise(Context* c, Promise* offset)
{
return new (c->zone->allocate(sizeof(CodePromise))) CodePromise(c, offset);
}
void
append(Context* c, Event* e);
void
saveLocals(Context* c, Event* e)
{
for (unsigned li = 0; li < c->localFootprint; ++li) {
Local* local = e->localsBefore + li;
if (local->value) {
if (DebugReads) {
fprintf(stderr, "local save read %p at %d of %d\n",
local->value, local::frameIndex(c, li), totalFrameSize(c));
}
addRead(c, e, local->value, SiteMask
(1 << MemoryOperand, 0, local::frameIndex(c, li)));
}
}
}
class CallEvent: public Event {
public:
CallEvent(Context* c, Value* address, unsigned flags,
TraceHandler* traceHandler, Value* result, unsigned resultSize,
Stack* argumentStack, unsigned argumentCount,
unsigned stackArgumentFootprint):
Event(c),
address(address),
traceHandler(traceHandler),
result(result),
returnAddressSurrogate(0),
framePointerSurrogate(0),
popIndex(0),
stackArgumentIndex(0),
flags(flags),
resultSize(resultSize),
stackArgumentFootprint(stackArgumentFootprint)
{
uint32_t registerMask = c->arch->generalRegisterMask();
if (argumentCount) {
assert(c, (flags & Compiler::TailJump) == 0);
assert(c, stackArgumentFootprint == 0);
Stack* s = argumentStack;
unsigned frameIndex = 0;
unsigned index = 0;
while (true) {
SiteMask targetMask;
if (index < c->arch->argumentRegisterCount()) {
int number = c->arch->argumentRegister(index);
if (DebugReads) {
fprintf(stderr, "reg %d arg read %p\n", number, s->value);
}
targetMask = fixedRegisterMask(number);
registerMask &= ~(1 << number);
} else {
if (DebugReads) {
fprintf(stderr, "stack %d arg read %p\n", frameIndex, s->value);
}
targetMask = SiteMask(1 << MemoryOperand, 0, frameIndex);
++ frameIndex;
}
addRead(c, this, s->value, targetMask);
if ((++ index) < argumentCount) {
s = s->next;
} else {
break;
}
}
}
if (DebugReads) {
fprintf(stderr, "address read %p\n", address);
}
{ bool thunk;
uint8_t typeMask;
uint64_t planRegisterMask;
c->arch->plan
((flags & Compiler::Aligned) ? AlignedCall : Call, BytesPerWord,
&typeMask, &planRegisterMask, &thunk);
assert(c, not thunk);
addRead(c, this, address, SiteMask
(typeMask, registerMask & planRegisterMask, AnyFrameIndex));
}
Stack* stack = stackBefore;
if (stackArgumentFootprint) {
RUNTIME_ARRAY(Value*, arguments, stackArgumentFootprint);
for (int i = stackArgumentFootprint - 1; i >= 0; --i) {
Value* v = stack->value;
stack = stack->next;
if ((BytesPerWord == 8 and (v == 0 or (i >= 1 and stack->value == 0)))
or (BytesPerWord == 4 and v->nextWord != v))
{
assert(c, BytesPerWord == 8 or v->nextWord == stack->value);
RUNTIME_ARRAY_BODY(arguments)[i--] = stack->value;
stack = stack->next;
}
RUNTIME_ARRAY_BODY(arguments)[i] = v;
}
int returnAddressIndex;
int framePointerIndex;
int frameOffset;
if (TailCalls and (flags & Compiler::TailJump)) {
assert(c, argumentCount == 0);
int base = frameBase(c);
returnAddressIndex = base + c->arch->returnAddressOffset();
framePointerIndex = base + c->arch->framePointerOffset();
frameOffset = totalFrameSize(c)
- c->arch->argumentFootprint(stackArgumentFootprint);
} else {
returnAddressIndex = -1;
framePointerIndex = -1;
frameOffset = 0;
}
for (unsigned i = 0; i < stackArgumentFootprint; ++i) {
Value* v = RUNTIME_ARRAY_BODY(arguments)[i];
if (v) {
int frameIndex = i + frameOffset;
if (DebugReads) {
fprintf(stderr, "stack arg read %p at %d of %d\n",
v, frameIndex, totalFrameSize(c));
}
if (static_cast<int>(frameIndex) == returnAddressIndex) {
returnAddressSurrogate = v;
addRead(c, this, v, generalRegisterMask(c));
} else if (static_cast<int>(frameIndex) == framePointerIndex) {
framePointerSurrogate = v;
addRead(c, this, v, generalRegisterMask(c));
} else {
addRead(c, this, v, SiteMask(1 << MemoryOperand, 0, frameIndex));
}
}
}
}
if ((not TailCalls) or (flags & Compiler::TailJump) == 0) {
stackArgumentIndex = c->localFootprint;
if (stackBefore) {
stackArgumentIndex += stackBefore->index + 1 - stackArgumentFootprint;
}
popIndex
= c->alignedFrameSize
+ c->parameterFootprint
- c->arch->frameFooterSize()
- stackArgumentIndex;
assert(c, static_cast<int>(popIndex) >= 0);
while (stack) {
if (stack->value) {
unsigned logicalIndex = local::frameIndex
(c, stack->index + c->localFootprint);
if (DebugReads) {
fprintf(stderr, "stack save read %p at %d of %d\n",
stack->value, logicalIndex, totalFrameSize(c));
}
addRead(c, this, stack->value, SiteMask
(1 << MemoryOperand, 0, logicalIndex));
}
stack = stack->next;
}
saveLocals(c, this);
}
}
virtual const char* name() {
return "CallEvent";
}
virtual void compile(Context* c) {
UnaryOperation op;
if (TailCalls and (flags & Compiler::TailJump)) {
if (flags & Compiler::LongJumpOrCall) {
if (flags & Compiler::Aligned) {
op = AlignedLongJump;
} else {
op = LongJump;
}
} else if (flags & Compiler::Aligned) {
op = AlignedJump;
} else {
op = Jump;
}
assert(c, returnAddressSurrogate == 0
or returnAddressSurrogate->source->type(c) == RegisterOperand);
assert(c, framePointerSurrogate == 0
or framePointerSurrogate->source->type(c) == RegisterOperand);
int ras;
if (returnAddressSurrogate) {
returnAddressSurrogate->source->freeze(c, returnAddressSurrogate);
ras = static_cast<RegisterSite*>
(returnAddressSurrogate->source)->number;
} else {
ras = NoRegister;
}
int fps;
if (framePointerSurrogate) {
framePointerSurrogate->source->freeze(c, framePointerSurrogate);
fps = static_cast<RegisterSite*>
(framePointerSurrogate->source)->number;
} else {
fps = NoRegister;
}
int offset
= static_cast<int>(c->arch->argumentFootprint(stackArgumentFootprint))
- static_cast<int>(c->arch->argumentFootprint(c->parameterFootprint));
c->assembler->popFrameForTailCall(c->alignedFrameSize, offset, ras, fps);
} else if (flags & Compiler::LongJumpOrCall) {
if (flags & Compiler::Aligned) {
op = AlignedLongCall;
} else {
op = LongCall;
}
} else if (flags & Compiler::Aligned) {
op = AlignedCall;
} else {
op = Call;
}
apply(c, op, BytesPerWord, address->source, address->source);
if (traceHandler) {
traceHandler->handleTrace(codePromise(c, c->assembler->offset()),
stackArgumentIndex);
}
if (TailCalls) {
if (flags & Compiler::TailJump) {
if (returnAddressSurrogate) {
returnAddressSurrogate->source->thaw(c, returnAddressSurrogate);
}
if (framePointerSurrogate) {
framePointerSurrogate->source->thaw(c, framePointerSurrogate);
}
} else {
unsigned footprint = c->arch->argumentFootprint
(stackArgumentFootprint);
if (footprint > c->arch->stackAlignmentInWords()) {
c->assembler->adjustFrame
(footprint - c->arch->stackAlignmentInWords());
}
}
}
clean(c, this, stackBefore, localsBefore, reads, popIndex);
if (resultSize and live(result)) {
addSite(c, result, registerSite(c, c->arch->returnLow()));
if (resultSize > BytesPerWord and live(result->nextWord)) {
addSite(c, result->nextWord, registerSite(c, c->arch->returnHigh()));
}
}
}
virtual bool allExits() {
return (flags & Compiler::TailJump) != 0;
}
Value* address;
TraceHandler* traceHandler;
Value* result;
Value* returnAddressSurrogate;
Value* framePointerSurrogate;
unsigned popIndex;
unsigned stackArgumentIndex;
unsigned flags;
unsigned resultSize;
unsigned stackArgumentFootprint;
};
void
appendCall(Context* c, Value* address, unsigned flags,
TraceHandler* traceHandler, Value* result, unsigned resultSize,
Stack* argumentStack, unsigned argumentCount,
unsigned stackArgumentFootprint)
{
append(c, new (c->zone->allocate(sizeof(CallEvent)))
CallEvent(c, address, flags, traceHandler, result,
resultSize, argumentStack, argumentCount,
stackArgumentFootprint));
}
bool
unreachable(Event* event)
{
for (Link* p = event->predecessors; p; p = p->nextPredecessor) {
if (not p->predecessor->allExits()) return false;
}
return event->predecessors != 0;
}
class ReturnEvent: public Event {
public:
ReturnEvent(Context* c, unsigned size, Value* value):
Event(c), value(value)
{
if (value) {
addReads(c, this, value, size, fixedRegisterMask(c->arch->returnLow()),
fixedRegisterMask(c->arch->returnHigh()));
}
}
virtual const char* name() {
return "ReturnEvent";
}
virtual void compile(Context* c) {
for (Read* r = reads; r; r = r->eventNext) {
popRead(c, this, r->value);
}
if (not unreachable(this)) {
c->assembler->popFrameAndPopArgumentsAndReturn
(c->arch->argumentFootprint(c->parameterFootprint));
}
}
Value* value;
};
void
appendReturn(Context* c, unsigned size, Value* value)
{
append(c, new (c->zone->allocate(sizeof(ReturnEvent)))
ReturnEvent(c, size, value));
}
void
maybeMove(Context* c, BinaryOperation type, unsigned srcSize,
unsigned srcSelectSize, Value* src, unsigned dstSize, Value* dst,
const SiteMask& dstMask)
{
Read* read = live(dst);
bool isStore = read == 0;
Site* target;
if (dst->target) {
target = dst->target;
} else if (isStore) {
return;
} else {
target = pickTargetSite(c, read);
}
unsigned cost = src->source->copyCost(c, target);
if (srcSelectSize < dstSize) cost = 1;
if (cost) {
// todo: let c->arch->planMove decide this:
bool useTemporary = ((target->type(c) == MemoryOperand
and src->source->type(c) == MemoryOperand)
or (srcSelectSize < dstSize
and target->type(c) != RegisterOperand));
src->source->freeze(c, src);
addSite(c, dst, target);
src->source->thaw(c, src);
bool addOffset = srcSize != srcSelectSize
and c->arch->bigEndian()
and src->source->type(c) == MemoryOperand;
if (addOffset) {
static_cast<MemorySite*>(src->source)->offset
+= (srcSize - srcSelectSize);
}
target->freeze(c, dst);
if (target->match(c, dstMask) and not useTemporary) {
if (DebugMoves) {
char srcb[256]; src->source->toString(c, srcb, 256);
char dstb[256]; target->toString(c, dstb, 256);
fprintf(stderr, "move %s to %s for %p to %p\n",
srcb, dstb, src, dst);
}
src->source->freeze(c, src);
apply(c, type, min(srcSelectSize, dstSize), src->source, src->source,
dstSize, target, target);
src->source->thaw(c, src);
} else {
// pick a temporary register which is valid as both a
// destination and a source for the moves we need to perform:
removeSite(c, dst, target);
bool thunk;
uint8_t srcTypeMask;
uint64_t srcRegisterMask;
c->arch->planSource(type, dstSize, &srcTypeMask, &srcRegisterMask,
dstSize, &thunk);
if (src->type == ValueGeneral) {
srcRegisterMask &= c->arch->generalRegisterMask();
}
assert(c, thunk == 0);
assert(c, dstMask.typeMask & srcTypeMask & (1 << RegisterOperand));
Site* tmpTarget = freeRegisterSite
(c, dstMask.registerMask & srcRegisterMask);
src->source->freeze(c, src);
addSite(c, dst, tmpTarget);
tmpTarget->freeze(c, dst);
if (DebugMoves) {
char srcb[256]; src->source->toString(c, srcb, 256);
char dstb[256]; tmpTarget->toString(c, dstb, 256);
fprintf(stderr, "move %s to %s for %p to %p\n",
srcb, dstb, src, dst);
}
apply(c, type, srcSelectSize, src->source, src->source,
dstSize, tmpTarget, tmpTarget);
tmpTarget->thaw(c, dst);
src->source->thaw(c, src);
if (useTemporary or isStore) {
if (DebugMoves) {
char srcb[256]; tmpTarget->toString(c, srcb, 256);
char dstb[256]; target->toString(c, dstb, 256);
fprintf(stderr, "move %s to %s for %p to %p\n",
srcb, dstb, src, dst);
}
addSite(c, dst, target);
tmpTarget->freeze(c, dst);
apply(c, Move, dstSize, tmpTarget, tmpTarget, dstSize, target, target);
tmpTarget->thaw(c, dst);
if (isStore) {
removeSite(c, dst, tmpTarget);
}
}
}
target->thaw(c, dst);
if (addOffset) {
static_cast<MemorySite*>(src->source)->offset
-= (srcSize - srcSelectSize);
}
} else {
target = src->source;
if (DebugMoves) {
char dstb[256]; target->toString(c, dstb, 256);
fprintf(stderr, "null move in %s for %p to %p\n", dstb, src, dst);
}
}
if (isStore) {
removeSite(c, dst, target);
}
}
Site*
pickMatchOrMove(Context* c, Read* r, Site* nextWord, unsigned index,
bool intersectRead)
{
Site* s = pickSite(c, r->value, nextWord, index, true);
SiteMask mask;
if (intersectRead) {
r->intersect(&mask);
}
if (s and s->match(c, mask)) {
return s;
}
return pickSiteOrMove
(c, r->value, intersect(mask, nextWord->nextWordMask(c, index)),
true, true);
}
Site*
pickSiteOrMove(Context* c, Value* src, Value* dst, Site* nextWord,
unsigned index)
{
if (live(dst)) {
Read* read = live(src);
Site* s;
if (nextWord) {
s = pickMatchOrMove(c, read, nextWord, index, false);
} else {
s = pickSourceSite(c, read, 0, 0, 0, false, true, true);
if (s == 0 or s->isVolatile(c)) {
s = maybeMove(c, read, false, true);
}
}
assert(c, s);
addBuddy(src, dst);
if (src->source->isVolatile(c)) {
removeSite(c, src, src->source);
}
return s;
} else {
return 0;
}
}
Value*
value(Context* c, ValueType type, Site* site = 0, Site* target = 0)
{
return new (c->zone->allocate(sizeof(Value))) Value(site, target, type);
}
void
grow(Context* c, Value* v)
{
assert(c, v->nextWord == v);
Value* next = value(c, v->type);
v->nextWord = next;
next->nextWord = v;
next->wordIndex = 1;
}
void
split(Context* c, Value* v)
{
grow(c, v);
for (SiteIterator it(c, v); it.hasMore();) {
Site* s = it.next();
removeSite(c, v, s);
addSite(c, v, s->copyLow(c));
addSite(c, v->nextWord, s->copyHigh(c));
}
}
void
maybeSplit(Context* c, Value* v)
{
if (v->nextWord == v) {
split(c, v);
}
}
class MoveEvent: public Event {
public:
MoveEvent(Context* c, BinaryOperation type, unsigned srcSize,
unsigned srcSelectSize, Value* src, unsigned dstSize, Value* dst,
const SiteMask& srcLowMask, const SiteMask& srcHighMask):
Event(c), type(type), srcSize(srcSize), srcSelectSize(srcSelectSize),
src(src), dstSize(dstSize), dst(dst)
{
assert(c, srcSelectSize <= srcSize);
bool noop = srcSelectSize >= dstSize;
if (dstSize > BytesPerWord) {
grow(c, dst);
}
if (srcSelectSize > BytesPerWord) {
maybeSplit(c, src);
}
addReads(c, this, src, srcSelectSize, srcLowMask, noop ? dst : 0,
srcHighMask, noop and dstSize > BytesPerWord ? dst->nextWord : 0);
}
virtual const char* name() {
return "MoveEvent";
}
virtual void compile(Context* c) {
uint8_t dstTypeMask;
uint64_t dstRegisterMask;
c->arch->planDestination
(type,
srcSelectSize,
1 << src->source->type(c),
(static_cast<uint64_t>(src->nextWord->source->registerMask(c)) << 32)
| static_cast<uint64_t>(src->source->registerMask(c)),
dstSize,
&dstTypeMask,
&dstRegisterMask);
SiteMask dstLowMask(dstTypeMask, dstRegisterMask, AnyFrameIndex);
SiteMask dstHighMask(dstTypeMask, dstRegisterMask >> 32, AnyFrameIndex);
if (srcSelectSize >= BytesPerWord
and dstSize >= BytesPerWord
and srcSelectSize >= dstSize)
{
if (dst->target) {
if (dstSize > BytesPerWord
and src->source->registerSize(c) > BytesPerWord)
{
apply(c, Move, srcSelectSize, src->source, src->source,
dstSize, dst->target, dst->target);
if (live(dst) == 0) {
removeSite(c, dst, dst->target);
if (dstSize > BytesPerWord) {
removeSite(c, dst->nextWord, dst->nextWord->target);
}
}
} else {
maybeMove(c, Move, BytesPerWord, BytesPerWord, src,
BytesPerWord, dst, dstLowMask);
if (dstSize > BytesPerWord) {
maybeMove(c, Move, BytesPerWord, BytesPerWord, src->nextWord,
BytesPerWord, dst->nextWord, dstHighMask);
}
}
} else {
Site* low = pickSiteOrMove(c, src, dst, 0, 0);
if (dstSize > BytesPerWord) {
pickSiteOrMove(c, src->nextWord, dst->nextWord, low, 1);
}
}
} else if (srcSelectSize <= BytesPerWord and dstSize <= BytesPerWord) {
maybeMove(c, type, srcSize, srcSelectSize, src, dstSize, dst,
dstLowMask);
} else {
assert(c, srcSize == BytesPerWord);
assert(c, srcSelectSize == BytesPerWord);
if (dst->nextWord->target or live(dst->nextWord)) {
assert(c, dstLowMask.typeMask & (1 << RegisterOperand));
Site* low = freeRegisterSite(c, dstLowMask.registerMask);
src->source->freeze(c, src);
addSite(c, dst, low);
low->freeze(c, dst);
if (DebugMoves) {
char srcb[256]; src->source->toString(c, srcb, 256);
char dstb[256]; low->toString(c, dstb, 256);
fprintf(stderr, "move %s to %s for %p\n",
srcb, dstb, src);
}
apply(c, Move, BytesPerWord, src->source, src->source,
BytesPerWord, low, low);
low->thaw(c, dst);
src->source->thaw(c, src);
assert(c, dstHighMask.typeMask & (1 << RegisterOperand));
Site* high = freeRegisterSite(c, dstHighMask.registerMask);
low->freeze(c, dst);
addSite(c, dst->nextWord, high);
high->freeze(c, dst->nextWord);
if (DebugMoves) {
char srcb[256]; low->toString(c, srcb, 256);
char dstb[256]; high->toString(c, dstb, 256);
fprintf(stderr, "extend %s to %s for %p %p\n",
srcb, dstb, dst, dst->nextWord);
}
apply(c, Move, BytesPerWord, low, low, dstSize, low, high);
high->thaw(c, dst->nextWord);
low->thaw(c, dst);
} else {
pickSiteOrMove(c, src, dst, 0, 0);
}
}
for (Read* r = reads; r; r = r->eventNext) {
popRead(c, this, r->value);
}
}
BinaryOperation type;
unsigned srcSize;
unsigned srcSelectSize;
Value* src;
unsigned dstSize;
Value* dst;
};
void
appendMove(Context* c, BinaryOperation type, unsigned srcSize,
unsigned srcSelectSize, Value* src, unsigned dstSize, Value* dst)
{
bool thunk;
uint8_t srcTypeMask;
uint64_t srcRegisterMask;
c->arch->planSource
(type, srcSelectSize, &srcTypeMask, &srcRegisterMask, dstSize, &thunk);
assert(c, not thunk);
append(c, new (c->zone->allocate(sizeof(MoveEvent)))
MoveEvent
(c, type, srcSize, srcSelectSize, src, dstSize, dst,
SiteMask(srcTypeMask, srcRegisterMask, AnyFrameIndex),
SiteMask(srcTypeMask, srcRegisterMask >> 32, AnyFrameIndex)));
}
ConstantSite*
findConstantSite(Context* c, Value* v)
{
for (SiteIterator it(c, v); it.hasMore();) {
Site* s = it.next();
if (s->type(c) == ConstantOperand) {
return static_cast<ConstantSite*>(s);
}
}
return 0;
}
void
preserve(Context* c, Value* v, Read* r, Site* s)
{
s->freeze(c, v);
maybeMove(c, r, false, true, 0);
s->thaw(c, v);
}
Site*
getTarget(Context* c, Value* value, Value* result, const SiteMask& resultMask)
{
Site* s;
Value* v;
Read* r = liveNext(c, value);
if (value->source->match
(c, static_cast<const SiteMask&>(resultMask))
and (r == 0 or value->source->loneMatch
(c, static_cast<const SiteMask&>(resultMask))))
{
s = value->source;
v = value;
if (r and uniqueSite(c, v, s)) {
preserve(c, v, r, s);
}
} else {
SingleRead r(resultMask, 0);
r.value = result;
r.successor_ = result;
s = pickTargetSite(c, &r, true);
v = result;
addSite(c, result, s);
}
removeSite(c, v, s);
s->freeze(c, v);
return s;
}
void
freezeSource(Context* c, unsigned size, Value* v)
{
v->source->freeze(c, v);
if (size > BytesPerWord) {
v->nextWord->source->freeze(c, v->nextWord);
}
}
void
thawSource(Context* c, unsigned size, Value* v)
{
v->source->thaw(c, v);
if (size > BytesPerWord) {
v->nextWord->source->thaw(c, v->nextWord);
}
}
class CombineEvent: public Event {
public:
CombineEvent(Context* c, TernaryOperation type,
unsigned firstSize, Value* first,
unsigned secondSize, Value* second,
unsigned resultSize, Value* result,
const SiteMask& firstLowMask,
const SiteMask& firstHighMask,
const SiteMask& secondLowMask,
const SiteMask& secondHighMask):
Event(c), type(type), firstSize(firstSize), first(first),
secondSize(secondSize), second(second), resultSize(resultSize),
result(result)
{
addReads(c, this, first, firstSize, firstLowMask, firstHighMask);
if (resultSize > BytesPerWord) {
grow(c, result);
}
bool condensed = c->arch->alwaysCondensed(type);
addReads(c, this, second, secondSize,
secondLowMask, condensed ? result : 0,
secondHighMask, condensed ? result->nextWord : 0);
}
virtual const char* name() {
return "CombineEvent";
}
virtual void compile(Context* c) {
assert(c, first->source->type(c) == first->nextWord->source->type(c));
if (second->source->type(c) != second->nextWord->source->type(c)) {
fprintf(stderr, "%p %p %d : %p %p %d\n",
second, second->source, second->source->type(c),
second->nextWord, second->nextWord->source,
second->nextWord->source->type(c));
}
assert(c, second->source->type(c) == second->nextWord->source->type(c));
freezeSource(c, firstSize, first);
uint8_t cTypeMask;
uint64_t cRegisterMask;
c->arch->planDestination
(type,
firstSize,
1 << first->source->type(c),
(static_cast<uint64_t>(first->nextWord->source->registerMask(c)) << 32)
| static_cast<uint64_t>(first->source->registerMask(c)),
secondSize,
1 << second->source->type(c),
(static_cast<uint64_t>(second->nextWord->source->registerMask(c)) << 32)
| static_cast<uint64_t>(second->source->registerMask(c)),
resultSize,
&cTypeMask,
&cRegisterMask);
SiteMask resultLowMask(cTypeMask, cRegisterMask, AnyFrameIndex);
SiteMask resultHighMask(cTypeMask, cRegisterMask >> 32, AnyFrameIndex);
Site* low = getTarget(c, second, result, resultLowMask);
unsigned lowSize = low->registerSize(c);
Site* high
= (resultSize > lowSize
? getTarget(c, second->nextWord, result->nextWord, resultHighMask)
: low);
// fprintf(stderr, "combine %p:%p and %p:%p into %p:%p\n",
// first, first->nextWord,
// second, second->nextWord,
// result, result->nextWord);
apply(c, type,
firstSize, first->source, first->nextWord->source,
secondSize, second->source, second->nextWord->source,
resultSize, low, high);
thawSource(c, firstSize, first);
for (Read* r = reads; r; r = r->eventNext) {
popRead(c, this, r->value);
}
low->thaw(c, second);
if (resultSize > lowSize) {
high->thaw(c, second->nextWord);
}
if (live(result)) {
addSite(c, result, low);
if (resultSize > lowSize and live(result->nextWord)) {
addSite(c, result->nextWord, high);
}
}
}
TernaryOperation type;
unsigned firstSize;
Value* first;
unsigned secondSize;
Value* second;
unsigned resultSize;
Value* result;
};
void
removeBuddy(Context* c, Value* v)
{
if (v->buddy != v) {
if (DebugBuddies) {
fprintf(stderr, "remove buddy %p from", v);
for (Value* p = v->buddy; p != v; p = p->buddy) {
fprintf(stderr, " %p", p);
}
fprintf(stderr, "\n");
}
assert(c, v->buddy);
Value* next = v->buddy;
v->buddy = v;
Value* p = next;
while (p->buddy != v) p = p->buddy;
p->buddy = next;
assert(c, p->buddy);
if (not live(next)) {
clearSites(c, next);
}
if (not live(v)) {
clearSites(c, v);
}
}
}
Site*
copy(Context* c, Site* s)
{
Site* start = 0;
Site* end = 0;
for (; s; s = s->next) {
Site* n = s->copy(c);
if (end) {
end->next = n;
} else {
start = n;
}
end = n;
}
return start;
}
class Snapshot {
public:
Snapshot(Context* c, Value* value, Snapshot* next):
value(value), buddy(value->buddy), sites(copy(c, value->sites)), next(next)
{ }
Value* value;
Value* buddy;
Site* sites;
Snapshot* next;
};
Snapshot*
snapshot(Context* c, Value* value, Snapshot* next)
{
if (DebugControl) {
char buffer[256]; sitesToString(c, value->sites, buffer, 256);
fprintf(stderr, "snapshot %p buddy %p sites %s\n",
value, value->buddy, buffer);
}
return new (c->zone->allocate(sizeof(Snapshot))) Snapshot(c, value, next);
}
Snapshot*
makeSnapshots(Context* c, Value* value, Snapshot* next)
{
next = snapshot(c, value, next);
for (Value* p = value->buddy; p != value; p = p->buddy) {
next = snapshot(c, p, next);
}
return next;
}
Stack*
stack(Context* c, Value* value, Stack* next)
{
return new (c->zone->allocate(sizeof(Stack)))
Stack(next ? next->index + 1 : 0, value, next);
}
Value*
maybeBuddy(Context* c, Value* v);
Value*
pushWord(Context* c, Value* v)
{
if (v) {
v = maybeBuddy(c, v);
}
Stack* s = stack(c, v, c->stack);
if (DebugFrame) {
fprintf(stderr, "push %p\n", v);
}
if (v) {
v->home = frameIndex(c, s->index + c->localFootprint);
}
c->stack = s;
return v;
}
void
push(Context* c, unsigned footprint, Value* v)
{
assert(c, footprint);
bool bigEndian = c->arch->bigEndian();
Value* low = v;
if (bigEndian) {
v = pushWord(c, v);
}
Value* high;
if (footprint > 1) {
assert(c, footprint == 2);
if (BytesPerWord == 4) {
maybeSplit(c, low);
high = pushWord(c, low->nextWord);
} else {
high = pushWord(c, 0);
}
} else {
high = 0;
}
if (not bigEndian) {
v = pushWord(c, v);
}
if (high) {
v->nextWord = high;
high->nextWord = v;
high->wordIndex = 1;
}
}
void
popWord(Context* c)
{
Stack* s = c->stack;
assert(c, s->value == 0 or s->value->home >= 0);
if (DebugFrame) {
fprintf(stderr, "pop %p\n", s->value);
}
c->stack = s->next;
}
Value*
pop(Context* c, unsigned footprint)
{
assert(c, footprint);
Stack* s = 0;
bool bigEndian = c->arch->bigEndian();
if (not bigEndian) {
s = c->stack;
}
if (footprint > 1) {
assert(c, footprint == 2);
#ifndef NDEBUG
Stack* low;
Stack* high;
if (bigEndian) {
high = c->stack;
low = high->next;
} else {
low = c->stack;
high = low->next;
}
assert(c, (BytesPerWord == 8
and low->value->nextWord == low->value and high->value == 0)
or (BytesPerWord == 4 and low->value->nextWord == high->value));
#endif // not NDEBUG
popWord(c);
}
if (bigEndian) {
s = c->stack;
}
popWord(c);
return s->value;
}
Value*
storeLocal(Context* c, unsigned footprint, Value* v, unsigned index, bool copy)
{
assert(c, index + footprint <= c->localFootprint);
if (copy) {
unsigned sizeInBytes = sizeof(Local) * c->localFootprint;
Local* newLocals = static_cast<Local*>(c->zone->allocate(sizeInBytes));
memcpy(newLocals, c->locals, sizeInBytes);
c->locals = newLocals;
}
Value* high;
if (footprint > 1) {
assert(c, footprint == 2);
unsigned highIndex;
unsigned lowIndex;
if (c->arch->bigEndian()) {
highIndex = index + 1;
lowIndex = index;
} else {
lowIndex = index + 1;
highIndex = index;
}
if (BytesPerWord == 4) {
assert(c, v->nextWord != v);
high = storeLocal(c, 1, v->nextWord, highIndex, false);
} else {
high = 0;
}
index = lowIndex;
} else {
high = 0;
}
v = maybeBuddy(c, v);
if (high != 0) {
v->nextWord = high;
high->nextWord = v;
high->wordIndex = 1;
}
Local* local = c->locals + index;
local->value = v;
if (DebugFrame) {
fprintf(stderr, "store local %p at %d\n", local->value, index);
}
local->value->home = frameIndex(c, index);
return v;
}
Value*
loadLocal(Context* c, unsigned footprint, unsigned index)
{
assert(c, index + footprint <= c->localFootprint);
if (footprint > 1) {
assert(c, footprint == 2);
if (not c->arch->bigEndian()) {
++ index;