X-Git-Url: http://plrg.eecs.uci.edu/git/?p=cdsspec-compiler.git;a=blobdiff_plain;f=scanalysis.cc;h=8556831c2b091920303ef90372b0c179a587a860;hp=701c50b2f1913ec694e72199658170e2b88e6c2f;hb=9508fe09d2eeaaf7fbe7193d9cb81b3bc66316b5;hpb=4541dc5155c69e168beedf3bd2a8f5ece0e0e65b;ds=sidebyside

diff --git a/scanalysis.cc b/scanalysis.cc
index 701c50b..8556831 100644
--- a/scanalysis.cc
+++ b/scanalysis.cc
@@ -1,10 +1,103 @@
 #include "scanalysis.h"
-#include "model.h"
+#include "action.h"
+#include "threads-model.h"
+#include "clockvector.h"
 
 SCAnalysis::SCAnalysis() {
+	cvmap=new HashTable<const ModelAction *, ClockVector *, uintptr_t, 4>();
+}
+
+SCAnalysis::~SCAnalysis() {
+	delete(cvmap);
 }
 
 void SCAnalysis::analyze(action_list_t * actions) {
-	
+ 	buildVectors(actions);
+	computeCV(actions);
+}
+
+void SCAnalysis::buildVectors(action_list_t *list) {
+	maxthreads=0;
+	for (action_list_t::iterator it = list->begin(); it != list->end(); it++) {
+		ModelAction *act = *it;
+		int threadid=id_to_int(act->get_tid());
+		if (threadid > maxthreads)
+			maxthreads=threadid;
+	}
+}
+
+bool SCAnalysis::processRead(ModelAction *read, ClockVector *cv) {
+	bool changed=false;
+
+	/* Merge in the clock vector from the write */
+	const ModelAction *write=read->get_reads_from();
+	ClockVector *writecv=cvmap->get(write);
+	changed|= ( writecv == NULL || cv->merge(writecv) && (*read < *write));
+
+	for(int i=0;i<=maxthreads;i++) {
+		thread_id_t tid=int_to_id(i);
+		if (tid==read->get_tid())
+			continue;
+		action_list_t * list=model->get_actions_on_obj(read->get_location(), tid);
+		if (list==NULL)
+			continue;
+		for (action_list_t::reverse_iterator rit = list->rbegin(); rit != list->rend(); rit++) {
+			ModelAction *write2 = *rit;
+			ClockVector *write2cv = cvmap->get(write2);
+			if (write2cv == NULL)
+				continue;
+			
+			/* write -sc-> write2 &&
+				 write -rf-> R =>
+				 R -sc-> write2 */
+			if (write2cv->synchronized_since(write)) {
+				changed |= write2cv->merge(cv);
+			}
+		
+			//looking for earliest write2 in iteration to satisfy this
+			/* write2 -sc-> R &&
+				 write -rf-> R =>
+				 write2 -sc-> write */
+			if (cv->synchronized_since(write2)) {
+				changed |= writecv == NULL || writecv->merge(write2cv);
+				break;
+			}
+		}
+	}
+	return changed;
+}
+
+
+void SCAnalysis::computeCV(action_list_t *list) {
+	bool changed=true;
+	bool firsttime=true;
+	ModelAction **last_act=(ModelAction **)model_calloc(1,(maxthreads+1)*sizeof(ModelAction *));
+	while(changed) {
+		changed=changed&firsttime;
+		firsttime=false;
 
+		for (action_list_t::iterator it = list->begin(); it != list->end(); it++) {
+			ModelAction *act = *it;
+			ModelAction *lastact = last_act[id_to_int(act->get_tid())];
+			if (act->is_thread_start())
+				lastact=model->get_thread(act)->get_creation();
+			ClockVector *lastcv=(lastact != NULL) ? cvmap->get(lastact) : NULL;
+			last_act[id_to_int(act->get_tid())]=act;
+			ClockVector *cv=cvmap->get(act);
+			if ( cv == NULL ) {
+				cv = new ClockVector(lastcv, act);
+				cvmap->put(act, cv);
+			} else if ( lastcv != NULL ) {
+					cv->merge(lastcv);
+			}
+			if (act->is_read()) {
+				changed|=processRead(act, cv);
+			}
+		}
+		/* Reset the last action array */
+		if (changed) {
+			bzero(last_act, (maxthreads+1)*sizeof(ModelAction *));
+		}
+	}
+	model_free(last_act);
 }