Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
lir: use sortable list
  • Loading branch information
indutny committed Nov 17, 2012
1 parent 549189a commit 58412e5
Show file tree
Hide file tree
Showing 11 changed files with 327 additions and 126 deletions.
1 change: 1 addition & 0 deletions Makefile
Expand Up @@ -21,6 +21,7 @@ test-runner: build

test: test-runner can
@./test-runner splaytree
@./test-runner list
@./test-runner parser
@./test-runner scope
# @./test-runner fullgen
Expand Down
4 changes: 2 additions & 2 deletions src/lir-inl.h
Expand Up @@ -313,13 +313,13 @@ inline LInterval::Type LInterval::type() {

inline int LInterval::start() {
assert(ranges()->length() > 0);
return ranges()->head()->value()->start();
return ranges()->head()->start();
}


inline int LInterval::end() {
assert(ranges()->length() > 0);
return ranges()->tail()->value()->end();
return ranges()->tail()->end();
}

} // namespace internal
Expand Down
59 changes: 25 additions & 34 deletions src/lir.cc
Expand Up @@ -312,7 +312,7 @@ void LGen::BuildIntervals() {
res->AddRange(instr->id, instr->id + 1);
} else if (l->live_in.Get(NumberKey::New(res->id)) == NULL) {
// Shorten first range
res->ranges()->head()->value()->start(instr->id);
res->ranges()->head()->start(instr->id);
}
}

Expand Down Expand Up @@ -393,9 +393,8 @@ void LGen::WalkIntervals() {
inactive_.Push(interval);
} else if (interval->is_const()) {
// Rematerialize const intervals before their uses
LUseList::Item* utail = interval->uses()->tail();
for (; utail != NULL; utail = utail->prev()) {
LUse* use = utail->value();
for (int i = interval->uses()->length() - 1; i >= 0; i--) {
LUse* use = interval->uses()->At(i);

// Skip constant definition
if (use->instr()->result == use) continue;
Expand All @@ -411,6 +410,9 @@ void LGen::WalkIntervals() {
// Replace interval in use
use->interval(reg);
reg->AddRange(use->instr()->id - 1, use->instr()->id);

// Current use could be probably moved
if (interval->uses()->At(i) != use) i++;
}
} else if (interval->is_stackslot()) {
// Fix gap's stackslots
Expand Down Expand Up @@ -913,7 +915,7 @@ void LGen::ResultFromFixed(LInstruction* instr, Register reg) {
res->register_hint = move->inputs[0];

instr->SetResult(ireg, LUse::kRegister);
instr->Propagate(res->uses()->head()->value());
instr->Propagate(res->uses()->head());
}


Expand All @@ -925,31 +927,25 @@ LInterval* LGen::Split(LInterval* i, int pos) {
LInterval* child = CreateVirtual();

// Move uses from parent to child
LUseList::Item* utail = i->uses()->tail();
LUseList::Item* uprev;
for (; utail != NULL; utail = uprev) {
LUse* use = utail->value();
uprev = utail->prev();
for (int j = i->uses()->length() - 1; j >= 0; j--) {
LUse* use = i->uses()->At(j);

// Uses are sorted - so break early
if (use->instr()->id < pos) break;
if (use->instr()->id < pos) continue;

i->uses()->Remove(utail);
i->uses()->RemoveAt(j);
child->uses()->Unshift(use);
use->interval(child);
}

// Move ranges from parent to child
LRangeList::Item* rtail = i->ranges()->tail();
LRangeList::Item* rprev;
for (; rtail != NULL; rtail = rprev) {
LRange* range = rtail->value();
rprev = rtail->prev();
for (int j = i->ranges()->length() - 1; j >= 0; j--) {
LRange* range = i->ranges()->At(j);

// Ranges are sorted too
if (range->end() <= pos) break;
if (range->end() <= pos) break;

i->ranges()->Remove(rtail);
i->ranges()->RemoveAt(j);
if (range->start() < pos) {
// Range needs to be splitted first
i->ranges()->Push(new LRange(i, range->start(), pos));
Expand Down Expand Up @@ -1042,7 +1038,7 @@ LUse* LInterval::Use(LUse::Type type, LInstruction* instr) {
void LInterval::AddRange(int start, int end) {
// Check if current range can be extended
if (ranges_.length() > 0) {
LRange* head = ranges_.head()->value();
LRange* head = ranges_.head();
if (head->start() == end) {
head->start(start);
return;
Expand All @@ -1059,9 +1055,8 @@ void LInterval::AddRange(int start, int end) {


bool LInterval::Covers(int pos) {
LRangeList::Item* head = ranges_.head();
for (; head != NULL; head = head->next()) {
LRange* range = head->value();
for (int i = 0; i < ranges_.length(); i++) {
LRange* range = ranges_.At(i);
if (range->start() > pos) return false;
if (range->end() > pos) return true;
}
Expand All @@ -1071,9 +1066,8 @@ bool LInterval::Covers(int pos) {


LUse* LInterval::UseAt(int pos) {
LUseList::Item* head = uses_.head();
for (; head != NULL; head = head->next()) {
LUse* use = head->value();
for (int i = 0; i < uses_.length(); i++) {
LUse* use = uses_.At(i);
if (use->instr()->id == pos) return use;
}

Expand All @@ -1082,9 +1076,8 @@ LUse* LInterval::UseAt(int pos) {


LUse* LInterval::UseAfter(int pos, LUse::Type use_type) {
LUseList::Item* head = uses_.head();
for (; head != NULL; head = head->next()) {
LUse* use = head->value();
for (int i = 0; i < uses_.length(); i++) {
LUse* use = uses_.At(i);
if (use->instr()->id >= pos &&
(use_type == LUse::kAny || use->type() == use_type)) {
return use;
Expand All @@ -1096,11 +1089,9 @@ LUse* LInterval::UseAfter(int pos, LUse::Type use_type) {


int LInterval::FindIntersection(LInterval* with) {
LRangeList::Item* ahead = ranges()->head();
for (; ahead != NULL; ahead = ahead->next()) {
LRangeList::Item* bhead = with->ranges()->head();
for (; bhead != NULL; bhead = bhead->next()) {
int r = ahead->value()->FindIntersection(bhead->value());
for (int i = 0; i < ranges()->length(); i++) {
for (int j = 0; j < with->ranges()->length(); j++) {
int r = ranges()->At(i)->FindIntersection(with->ranges()->At(j));
if (r != -1) return r;
}
}
Expand Down
7 changes: 5 additions & 2 deletions src/lir.h
Expand Up @@ -12,6 +12,7 @@
#include "macroassembler.h" // Register
#include "zone.h" // Zone
#include "utils.h" // Lists and etc
#include "list.h"

namespace candor {
namespace internal {
Expand All @@ -26,8 +27,8 @@ class LRange;
class LUse;
class SourceMap;
typedef ZoneList<LInterval*> LIntervalList;
typedef ZoneList<LRange*> LRangeList;
typedef ZoneList<LUse*> LUseList;
typedef SortableList<LRange, NopPolicy, ZonePolicy> LRangeList;
typedef SortableList<LUse, NopPolicy, ZonePolicy> LUseList;
typedef ZoneMap<NumberKey, LUse, ZoneObject> LUseMap;

class LRange : public ZoneObject {
Expand Down Expand Up @@ -110,6 +111,8 @@ class LInterval : public ZoneObject {
type_(type),
definition_(NULL),
index_(index),
ranges_(10),
uses_(10),
fixed_(false),
split_parent_(NULL) {
}
Expand Down
182 changes: 182 additions & 0 deletions src/list.h
@@ -0,0 +1,182 @@
#ifndef _SRC_SORTED_LIST_H_
#define _SRC_SORTED_LIST_H_

namespace candor {
namespace internal {

template <class T, class Policy, class Allocator>
class SortableList {
public:
SortableList(int size) : map_(NULL), size_(0), grow_(size), len_(0) {
Grow();
}

~SortableList() {
delete[] map_;
map_ = NULL;
}

inline T* At(int i) {
if (i < 0 || i >= len_) return NULL;
return map_[i];
}


inline void RemoveAt(int i) {
if (i < 0 || i >= len_) return;

// Shift left
len_--;
for (int j = i; j < len_; j++) {
map_[j] = map_[j + 1];
}
}


inline void Push(T* item) {
if (len_ == size_) Grow();

map_[len_++] = item;
}


inline void Unshift(T* item) {
if (len_ == size_) Grow();

// Shift right
len_++;
for (int i = len_ - 1; i > 0; i--) {
map_[i] = map_[i - 1];
}
map_[0] = item;
}


inline T* Pop() {
if (len_ == 0) return NULL;

return map_[--len_];
}


inline T* Shift() {
if (len_ == 0) return NULL;

T* res = map_[0];

// Shift left
len_--;
for (int i = 0; i < len_; i++) {
map_[i] = map_[i + 1];
}

return res;
}


template <class Shape>
inline void Sort() {
QuickSort<Shape>(0, length());
}


template <class Shape>
inline void InsertSorted(T* value) {
if (len_ == 0) {
Push(value);
return;
}

if (len_ == size_) Grow();

// Perform binary search for correct position
int middle_pos;
int cmp;
for (int i = 0, j = length() - 1; i < j; ) {
middle_pos = (i + j) >> 1;
T* middle = map_[middle_pos];

cmp = Shape::Compare(value, middle);
if (cmp < 0) {
j = middle_pos - 1;
} else if (cmp > 0) {
i = middle_pos + 1;
} else {
break;
}
}

int insert_pos;
if (cmp <= 0) {
insert_pos = middle_pos;
} else {
insert_pos = middle_pos + 1;
}

len_++;
for (int i = len_ - 1; i > insert_pos; i--) {
assert(map_[i - 1] != NULL);
map_[i] = map_[i - 1];
}
map_[insert_pos] = value;
}

inline T* head() { return At(0); }
inline T* tail() { return At(length() - 1); }
inline int length() { return len_; }

protected:
inline void Grow() {
// Allocate new map
int new_size = size_ + grow_;
T** new_map = new T*[new_size];

// Copy old entries
if (map_ != NULL) memcpy(new_map, map_, sizeof(*new_map) * size_);

// Replace map
delete[] map_;
map_ = new_map;
size_ = new_size;
}

template <class Shape>
inline void QuickSort(int start, int end) {
if (start + 1 >= end) return;

int marker_pos = (start + end) >> 1;
T* marker = map_[marker_pos];

int i = start;
int j = end - 1;
do {
while (Shape::Compare(map_[i], marker) < 0) {
i++;
}
while (Shape::Compare(marker, map_[j]) < 0) {
j--;
}

// Swap them out!
if (i < j) {
T* tmp = map_[i];
map_[i++] = map_[j];
map_[j--] = tmp;
}
} while (i < j);

// Sort lesser halves
QuickSort<Shape>(start, i);
QuickSort<Shape>(j, end);
}

T** map_;
int size_;
int grow_;
int len_;
};

} // namespace internal
} // namespace candor

#endif // _SRC_SORTED_LIST_H_
5 changes: 5 additions & 0 deletions src/zone.cc
Expand Up @@ -20,5 +20,10 @@ void* Zone::Allocate(size_t size) {
}
}


void* ZonePolicy::Allocate(size_t size) {
return Zone::current()->Allocate(size);
}

} // namespace internal
} // namespace candor
5 changes: 5 additions & 0 deletions src/zone.h
Expand Up @@ -73,6 +73,11 @@ class Zone {
size_t page_size_;
};

class ZonePolicy {
public:
static void* Allocate(size_t size);
};

// Base class for objects that will be bound to some zone
class ZoneObject {
public:
Expand Down

0 comments on commit 58412e5

Please sign in to comment.