顯示具有 analyser 標籤的文章。 顯示所有文章
顯示具有 analyser 標籤的文章。 顯示所有文章

2014年2月9日 星期日

carCV

purpose

car and lane detection example
ScreenShot

method

-lane detection
  • houghlines
  • houghlinesP
  • fitlines
-car detection
  • haar cascades

how to run it?

step1. get video source %python get_video.py
step2. lane detection %python detect_lane.py
step3. car detection %python detect_car.py
Ref

remote openCV with raspberry pi




this is an example about how to use remote object detection based on openCV and zeromq framework.

requirements

  • opencv(python) as cv(opencv) and cv2(numpy)
  • zeromq(python)
  • gevent(light weight switch)
  • knowledge about img process
  • profile, logging each stage mem and cpu time

method

  • Server
    • capture img
    • send img to clinet
    • wait for next command from client
    • update status by new command
  • Client
    • receive img
    • run all detection
    • build up a new command based on detection results

detections

  • face detect
  • circle detect
  • line detect
  • find attribute obj

how to run it?

  • python poll_camera.py (using cv to capture/show img via remote protocol)
  • python poll_camera2.py (using cv2 to capture/show img ...)
  • python poll_thread_run2.py (using cv2 to run all thread detection based on CPU num)
  • python poll_series_run2.py (using cv2 to run all series detection ...)

2013年8月19日 星期一

machine learning note1


  • supervised learning
    • requirement
      • it must have the target/answer in it's training phase
      • using training phase to build up the 
      • using test phase to predict the next value 
    • regression
      • find the next value based on it's regression times, such as the temperature value in tomorrow, stock price in next open time....
      • example

    • classification
      • find the next classification value based on it's regression times, such as the it will rain or not tomorrow?, stock price will go up or down?... 
      • example
        •  
  • non-supervised learning
    • cluster
  • definition
    • http://en.wikipedia.org/wiki/Machine_learninghttp://www.gnu.org/software/octave/

https://class.coursera.org/ml-003/lecture/5
https://sites.google.com/site/octavetech/home

2013年7月14日 星期日

Demo for interview

最近為了 interview 寫了幾個小 project. 有興趣的就參考看看吧!!

jenkins + python = regression env

Hi all,
this is a python unittest regression flow by jenkins that can help designer daily run testsuites and support the GUI output reports(coverage pass rate)

github:

  • https://github.com/funningboy/ijenkins/blob/master/README
ref:
  • http://jenkins-ci.org/content/python-love-story-virtualenv-and-hudson

2013年3月1日 星期五

ECO tool for NetList Verilog

hi all,

if your are a CAD Engineer in IC design house, i think you always take a lot of time to do recourse jobs... like reassign wire names, add new cells, check netlist...that's really suck things. why not try this tool that can help you insert ECO cell automatically, and double check the ECO cell inserted is ok when you running this script.

features
1. ECO cell insert
2. ECO cell check
3. Module output Fanin check
4. Module input Fanout check
5. cell, port, net, width check

more to do
1. support Graph alg(NetworkX)
2. support assign statement
3. support STA, Timing check
4. support simulation???

Example:
Definition about input/output, ECO file...

# our org NetList file
        vtest = \
"""
module TOP( in, out );
input [1:0] in;
output [1:0] out;
INVD1 U0( .I( in[0] ), .ZN( out[0] ) );
INVD1 U1( .I( in[1] ), .ZN( out[1] ) );
endmodule
"""

# our cell lib file
        ytest = \
"""
AN2D1:
  inputs:
    A1: 1
    A2: 1
  outputs:
    Z: 1
  primitive: A1 and A2

INVD1:
  inputs:
    I: 1
  outputs:
    ZN: 1
  primitive: not I
"""

# our ECO file description, define where is the Input, Output link coming from, and it's assign value
        etest = \
"""
AN2D1:
  inputs:
    A1: new_in
    A2: in[0]
  outputs:
    Z:  new_out
  primitive: A1 and A2
"""

# our expect value
        exptest = \
"""
module TOP( new_in, new_out, in, out );

    output [  1: 0 ] out;
    input  [  1: 0 ] in;
    input new_in;
    output new_out;

    AN2D1 ECO_AN2D1( .A1( new_in ), .A2( in[0]), .Z( new_out ) );
    INVD1 U0( .I( in[0] ), .ZN( out[0] ) );
    INVD1 U1( .I( in[1] ), .ZN( out[1] ) );
endmodule                                                                                                                                                                            
"""


How to run
    Add new ECO cell in org NetList file.
    >>> eco = ECO()                                                                                                                                                                  
    >>> eco.readYAML("test/gates.yml") # read cell libs
    >>> eco.readVerilog("test/Iface_test.gv") # read org verilog Netlist file
    >>> eco.link("Iface_test") # link top module
    >>> eco.checkDesign() # check pre load design is ok
    >>> eco.report()
    >>> eco.readECO("test/ECO.yml") # read eco file
    >>> eco.runECO() # run eco
    >>> eco.checkDesign() # recheck design again when the ECO is done
    >>> eco.report()
    >>> eco.writeVerilog("test/new_Iface_test.gv")

How to run unittest nosetests
project

2013年2月18日 星期一

example MyHDL

hi all,

this is a speech about MyHDL in python taipei meeting,
the free project code can download from git
thanks


2013年1月13日 星期日

multiprocessing VS serial

底下用 how to sync IPXACT with UVM 改寫成 multiprocessing vs serial 的版本. 發現如果 parallel 的 IO access counts 越小, performance serial > multiprocessing. 如果 IO access count 越大 performance multiprocessing > serial


from StringIO import *
import sys
import os
import time
import pprint
# add third party module to PyPy path

from lxml import etree
import multiprocessing
import subprocess
import math


class Parser:

    _prefixmap = {  'spirit' : 'http://www.spiritconsortium.org/XMLSchema/SPIRIT/1.4',
      'vendorExtensions' : '$UVM_REG_GEN/XMLSchema/SPIRIT',
      'xsi' : 'http://www.w3.org/2001/XMLSchema-instance',
  }

    def __init__(self):
     self._tree  = None

    def __del__(self):
     self._tree  = None

    def open(self, ifile):
     """ open from IP-XACT file and build up etree by lxml """
 try:
     self._ifile = StringIO(open(ifile, 'r').read())
     self._tree  = etree.parse(self._ifile)
     self._ifile.close()
 except IOError as e:
     print "%s not found or build up lxml etree fail" %(ifile)

    def close(self):
     """ close """
 self._tree = None

    def findAll(self, stmt, dtype='text'):
     """ return  list in ['text', 'tag', 'tail', attrib' ]dtype
     return  list in [element ]
     """
 found = filter(lambda i: i !=None, self._tree.xpath(stmt, namespaces=self._prefixmap))
 if dtype == 'text':
     return map(lambda i: i.text, found)
 elif dtype == 'tag':
     return map(lambda i: i.tag, found)
 elif dtype == 'tail':
     return map(lambda i: i.tail, found)
 elif dtype == 'attrib':
     return map(lambda i: i.attrib, found)
 elif dtype == 'obj':
     return found
 else:
     raise valueError("dtype not support %s" %(dtype))


def test_run_lxml(ifile=None, query=None):
    """ stackless test """
    pp = Parser()
    pp.open(ifile)
    rst = pp.findAll(stmt=query, dtype='text')
    del pp
    return rst


def serial_test_lxml(nums):
    """ serial test lxml """

    start_time = time.time()
    rsts = []
    for i in nums:
     rsts.append(test_run_lxml(ifile=i, query='//spirit:vendor'))
    print "sriial nums(%d) runtime(%s)" %(len(nums), time.time() - start_time)


def multiprocess_test_lxml(nums, nprocs=4):
    """ multiprocess test lxml """

    start_time = time.time()
    procs = []

    def worker(nums, out_q):
 """
 The worker function, invoked in a process.
 """
 outdict = {}
 for i in nums:
     outdict[i] = test_run_lxml(ifile=i, query='//spirit:vendor')
 out_q.put(outdict)

    # Each process will get 'chunksize' nums and a queue to put his out
    # dict into
    out_q = multiprocessing.Queue()
    chunksize = int(math.ceil(len(nums) / float(nprocs)))
    procs = []

    for i in range(nprocs):
        p = multiprocessing.Process(
                target=worker,
  args=(nums[chunksize * i:chunksize * (i + 1)],
                      out_q))
        procs.append(p)
        p.start()

    # Collect all results into a single result dict. We know how many dicts
    # with results to expect.
    resultdict = {}
    for i in range(nprocs):
        resultdict.update(out_q.get())

    # Wait for all worker processes to finish
    for p in procs:
        p.join()

    print "multis nums(%d) procs(%d) runtime(%s)" %(len(nums), nprocs, time.time() - start_time)


def regression_test(num, npros=4):

    for i in range(1,num):
     cmd = "cp 0.xml %d.xml" %(i)
  os.system(cmd)

    nums = [ "%s.xml" %(i) for i in range(num)]

    multiprocess_test_lxml(nums, npros)
    serial_test_lxml(nums)

    for i in range(1,num):
     cmd = "rm %d.xml" %(i)
     os.system(cmd)

def main():
    regression_test(10,1)
    regression_test(10,4)
    regression_test(10,8)

    regression_test(1000,1)
    regression_test(1000,4)
    regression_test(1000,8)


if __name__ == '__main__':
    main()

Download
results
multis nums(10) procs(1) runtime(0.0143690109253)
sriial nums(10) runtime(0.00273704528809)
multis nums(10) procs(4) runtime(0.0109529495239)
sriial nums(10) runtime(0.00267791748047)
multis nums(10) procs(8) runtime(0.0175120830536)
sriial nums(10) runtime(0.00293707847595)
multis nums(1000) procs(1) runtime(0.229081869125)
sriial nums(1000) runtime(0.233665943146)
multis nums(1000) procs(4) runtime(0.116140127182)
sriial nums(1000) runtime(0.237390041351)
multis nums(1000) procs(8) runtime(0.122074127197)
sriial nums(1000) runtime(0.275545120239)

2013年1月5日 星期六

vcd file info tracer



在 IP 驗證時, 除了用 synopsys VIP 來驗證 bus 的 protocol 跟 performance 的分析. 但有時候為了 customer design 時, 會把 protocol 作些變形, 這樣就不符合 standard protocol 的方式. 底下就用大家都熟知的 VCD 擋把 bus info 錄出來轉到 data base 讓使用者可以直接用 query 的方式把 performance 跟 dynamic power 算出來. 底下用 vcdparser.py 把 vcd info 讀出來.之後再透過後端的 big data 處理把資料寫到 data base 上.
python db link
"""
conn = sqlite3.connect('example.db')
c = conn.cursor()

c.execute('''CREATE TABLE vcd
      (version, timeType(s,ns,fs...), time''')
c.execute('''CREATE TABLE _scopes_
      (scopeDomain, scopeType(fork,module,...), top(scopeNm)''')
c.execute('''CREATE TABLE _signals_
      (scopeDomain, signalID, signalType(Real,Bit,...), width, name''')
c.execute('''CREATE TABLE _signalID_ # _0_
             (time , val)''')

# ex :
#
# module top();
# #0 clk =1;
# #5 clk =0; ...
# endmodule

# header create
c.execute('''CREATE TABLE _scopes_
      (scopeDomain, scopeType, scopeNm''')
c.execute('''CREATE TABLE _signals_
      (scopeDomain, signalID, signalType, width, name''')
c.execute('''CREATE TABLE _signalID_ # _0_
             (time , val)''')

# body create
c.execute("INSERT INTO _scopes_ VALUES (0, 1(module), "top")")
c.execute("INSERT INTO _signals_ VALUES (0, 0, 0(bit), "top.clk")")

c.execute("INSERT INTO _0_ VALUES (0, 1)")
c.execute("INSERT INTO _1_ VALUES (5, 0)")

#
conn.commit()
c.close()
"""
VcdParser.py
from __future__ import with_statement
from itertools import dropwhile, takewhile, izip
from collections import defaultdict
from pprint import pprint as pp

from os import *
import io
from src.vcdDB  import *
from src.vcdErr import *
from src.vcdContext import *


class VcdParser(object):
  """ parser VCD 2 VcdDB """

  def __init__(self,vcd=None):
    self._vfile = None

    try:
      if not isinstance(vcd,VcdDB):
       raise VcdParserError("vcdDB ptr is None")
    except VcdDBError, e:
      print e._msg

    self._vcd   = vcd


  def parse_error(self,tokeniser, keyword):
    raise "Don't understand keyword: " + keyword


  def do_drop_declaration(self,tokeniser, keyword):
    dropwhile(lambda x: x != "$end", tokeniser).next()


  def do_vcd_date(self,tokeniser, keyword):
    """ parser vcd date and set 2 VcdDB::date """

    date = ' '.join(takewhile(lambda x: x != "$end", tokeniser))
    self._vcd.set_date(date)


  def do_vcd_timescale(self,tokeniser, keyword):
    """ parser vcd timescale and set 2 VcdDB::timescale """

    val, scale = tuple(takewhile(lambda x: x!= "$end", tokeniser))
    self._vcd.set_timescale(scale,val)


  def do_vcd_version(self,tokeniser, keyword):
    """ parser vcd version and set 2 VcdDB::version """

    version = ' '.join(takewhile(lambda x: x!= "$end", tokeniser))
    self._vcd.set_version(version)


  def do_vcd_enddefinitions(self,tokeniser, keyword):
    """ parser vcd enddefinitions """

    self.do_drop_declaration(tokeniser, keyword)
    self._vcd.set_enddefinition(1)


  def do_vcd_scope(self,tokeniser, keyword):
    """ parser vcd scope and set 2 VcdDB::scope """

    scope, name = tuple(takewhile(lambda x: x != "$end", tokeniser))
    self._vcd.set_scope(self._vcd,scope,name)


  def do_vcd_upscope(self,tokeniser, keyword):
    """ parser vcd upscope """

    tokeniser.next()


  def do_vcd_var(self,tokeniser, keyword):
    """ parser vcd signalInfo and set 2 vcdDB::nameMap """

    varTyp, width, uniqNm, refNm = tuple(takewhile(lambda x: x != "$end", tokeniser))
    scope = self._vcd.get_end_scope()
    maptb = self._vcd.get_mapTb()

    scope.set_signals(scope,varTyp,refNm,width)
    signal = scope.get_signal(refNm)
    maptb.set_tb(uniqNm,signal)


  def do_vcd_dumpall(tokeniser, keyword): pass
  def do_vcd_dumpoff(tokeniser, keyword): pass
  def do_vcd_dumpon(tokeniser, keyword): pass
  def do_vcd_dumpvars(tokeniser, keyword): pass
  def do_vcd_end(tokeniser, keyword): pass


  def vcd_2_VcdDB(self,vcdfile=None):
    """ parser vcd file 2 VcdDB format """

  # define key 2 proc
    keyword2handler = {
        # declaration_keyword ::=
        "$comment":        self.do_drop_declaration,
        "$date":           self.do_vcd_date,
        "$enddefinitions": self.do_vcd_enddefinitions,
        "$scope":          self.do_vcd_scope,
        "$timescale":      self.do_vcd_timescale,
        "$upscope":        self.do_vcd_upscope,
        "$var":            self.do_vcd_var,
        "$version":        self.do_vcd_version,
        # simulation_keyword ::=
        "$dumpall":        self.do_vcd_dumpall,
        "$dumpoff":        self.do_vcd_dumpoff,
        "$dumpon":         self.do_vcd_dumpon,
        "$dumpvars":       self.do_vcd_dumpvars,
        "$end":            self.do_vcd_end,
        }

    keyword2handler = defaultdict(self.parse_error, keyword2handler)

    f = io.open(vcdfile,"r")
    tokeniser = (word for line in f for word in line.split() if word)
    time = 0
    for count,token in enumerate(tokeniser):
      if self._vcd.get_enddefinition() != 1:
        keyword2handler[token](tokeniser, token)
      else:
        c, rest = token[0], token[1:]
        if c == '$':
          # skip $dump* tokens and $end tokens in sim section
          continue
        # time info
        elif c == '#':
          time = rest
        # (1)bit info
        elif c in '01xXzZ':
          uniqNm = rest
          val    = c
          maptb  = self._vcd.get_mapTb()
     signal = maptb.get_tb(uniqNm)
          signal.set_NodeInfoList(signal,time,"bit",val)
        # binary info
        elif c in 'bB':
   uniqNm = tokeniser.next()
   val    = rest
   maptb  = self._vcd.get_mapTb()
   signal = maptb.get_tb(uniqNm)
   signal.set_NodeInfoList(signal,time,"binary",val)
        # real info
        elif c in 'rR':
   uniqNm = tokeniser.next()
   val    = rest
   maptb  = self._vcd.get_mapTb()
   signal = maptb.get_tb(uniqNm)
   signal.set_NodeInfoList(signal,time,"real",val)
        else:
          raise "Don't understand: %s After %i words" % (token, count)

    f.close()

    return self._vcd

code download 主要改寫 writing-vcd-to-toggle-count-generator 成我們要跟底層溝通的api




Refs:
http://www.semiwiki.com/forum/content/753-what-changes-expect-verification-ip-landscape-after-synopsys-acquisition-nsys.html
VMM performance user guide
http://vmmcentral.org/pdfs/perf_user_guide.pdf
http://i.cmpnet.com/eetimes/news/online/2010/09/Whitepaper_Mediatek_2010.pdf


2011年8月23日 星期二

Loop unswitching

# Original
# int i, w, x[1000], y[1000];
#  for (i = 0; i < 1000; i++) {
#    x[i] = x[i] + y[i];
#    if (w)
#      y[i] = 0;
#  }
#
#----------------------------------
# Loop unswitching
#
#  int i, w, x[1000], y[1000];
#  if (w) {
#    for (i = 0; i < 1000; i++) {
#      x[i] = x[i] + y[i];
#      y[i] = 0;
#    }
#  } else {
#    for (i = 0; i < 1000; i++) {
#      x[i] = x[i] + y[i];
#    }
#  }

1.可確保在for loop 中的 lp_body 是 clean 的,
  表示在 lp_body 中,只有 DFG 的 (BasicBlock)BB, 可避免不必要的條件中斷(Branch).

2.可透過 struct 的分析,把 for loop 當成個 node, 可以簡化成 sample BB with CFG control.
之後利用 BDD (Binary decision diagram) 的方式做出每個 Output condition 的機率,
有利於 compiler 做 branch jump 的 predict

x1,x2,x3,Y
---------
[0,0,0] = 0
[0,0,1] = 0 
[0,1,0] = 1
[0,1,1] = 1
[1,0,0] = 1
[1,0,1] = 1
[1,1,0] = 1
[1,1,1] = 0

@ y = 0 prb(3/8)
@ y = 1 prb(5/8) <= predict better

3. key notes
判斷 condition branch 是否 stable, 會不會在 for loop 內改變狀態, 如果是 stable 才做 Loop unswitching

2011年8月22日 星期一

unroll loop

#
# for(i=0; i<2; i++) {
#     c[i] = a[i] + a[i+1];
# }
#
#----------------------------
#
# c[0] = a[0] + a[1];
# c[1] = a[1] + a[2];
#
#---------------------------- 
# @ deepest loop case without subloop  loop *lp         =

cfg->get_LoopInfo();
Condition *cond  = lp->get_Condition();
loop_node *Entry = lp->get_LoopEntry();
loop_node *Body  = lp->get_LoopBody();
loop_node *Exit  = lp->get_LoopExit();
#loop lp->get_SubLoops();

faltList<>       = cond->get_Flattens();

int run_size = do_run_size();

InstructionList<> = Body->get_Instructions();

tmp_InstructionList = [];

for(int i =0; iget_Operand_Src1();
     Operand  *src2 = (Instruction)ii->get_Opernad_Src2();
     Operand  *dst  = (Instruction)ii->get_Opernad_Dst();
     Operator *op   = (Instruction)ii->get_Operator();

     if( src1->isArrayAccess() && faltList.find(src1->get_Array_ID()) != faltList.end() ) {
         int      new_src1_inx = faltList.find(src1->get_Array_ID())->get_Lists()->get_Value(i) +
                                 src1->get_Array_ID()->get_Offset();

         Operand *new_src1 = new Operand(src1->get_Array(),new_src1_inx);
     }


     if( src2->isArrayAccess() && faltList.find(src2->get_Array_ID()) != faltList.end() ) {
         int      new_src2_inx = faltList.find(src2->get_Array_ID())->get_Lists()->get_Value(i) +
                                 src2->get_Array_ID()->get_Offset();

         Operand *new_src2 = new Operand(src2->get_Array(),new_src2_inx);
     }



     if( dst->isArrayAccess() && faltList.find(dst->get_Array_ID()) != faltList.end() ) {
         int      new_dst_inx = faltList.find(dst->get_Array_ID())->get_Lists()->get_Value(i) +
                                dst->get_Array_ID()->get_Offset();

         Operand *new_dst = new Operand(dst->get_Array(),new_dst_inx);
     }


     Instruction *new_ii = new Instruction(new_dst,new_src1,op,new_src2);
     tmp_InstructionList.push(new_ii);
 }
}


BasicBlock *lp_pre = Entry->get_Proc();
BasicBlock *lp_nxt = Exit->get_Succ();

cfg->del_Loop_BB([Entry,Pre_Header,Header,Body,Exit]);
cfg->del_Loop_Edge([{lp_pre,Entry},{Entry,Pre_Header},{Pre_Header,Header},{Header,Body},{Body,Exit},{Exit,Header}]);

BasicBlock *bb_entry = new BasicBlock();
BasicBlock *bb_exit  = new BasicBlock();
BasicBlock *bb_cont  = new BasicBlock();

cfg->set_BasicBlock([bb_entry,bb_exit,bb_cont]);
cfg->set_Edge([{lp_pre,bb_entry},{bb_entry,bb_cont},{bb_cont,bb_exit},{bb_exit,lp_nxt}]);


foreach ii in tmp_InstructionList
      bb_cont.set_Instruction(ii);





# { i:[0,1], ... }
int do_run_size() {

int num = 0;

foreach flat in faltList {

 foreach id in flat->get_IDs() {

     if ( num == 0 )
          num = id->get_Lists().size()
     else
          assert( id->get_Lists().size() == num && "size error in loop condition" );  
 }
}

return num;
}

2011年8月21日 星期日

BDD (Binary decision diagram)

binary decision tree.以前唸書的時候,邏輯設計課要學卡諾圖(Karnaugh map)化簡,不過現在有一個比較好用的tool,BDD(binary decision diagram)可以幫我們判斷出條件 Path 的路徑 跟 Output 的 case 解.當然這也可以分析出 code 的 condition coverage 跟做些 reduction 的 methods. 可參考底下的教學跟安裝. Refs: http://en.wikipedia.org/wiki/Binary_decision_diagram http://lyle.smu.edu/~bxu/SimpleADD.html

2011年8月19日 星期五

pre_header


#
# for (int i=0; i<10; i++) {
#     c = a + b + i;
# }
#
#------------------------------
# i = 0;
# do {
#   j = a + b
#   c = j + i;
#   i++;
# } while(i<10)
#
# @ predict jump
#-------------------------------
#
# loop(entry):{}
# loop(lp_eader):{ i=0; }
# loop(lp_body):{ j=a+b; c=j+i; i=i+1; }
# loop(lp_exit):{ i<10; }
# loop(exit):{}
# 
# E0:{loop(entry)->loop(lp_header)}
# E1:{loop(lp_header)->loop(lp_body)}
# E2:{loop(lp_body)->loop(lp_exit)}
# E3:{loop(lp_exit)->loop(lp_body)}
# E4:{loop(lp_exit)->loop(exit)}

#------------------------------
# j = a + b;
# for (int i=0; i<10; i++) {
#      c = j + i;
# }
#------------------------------
#
# j = a + b;
# i = 0;
# do {
#    c = j + i;
# } while(i<10)
#
# loop(entry):{}
# loop(lp_pre_header):{ j=a+b; }
# loop(lp_header):{ i=0; }
# loop(lp_body):{ c=j+i; i=i+1; }
# loop(lp_exit):{ i<10; }
# loop(exit):{}
# 
# E0:{loop(entry)->loop(lp_pre_header); }
# E1:{loop(lp_pre_header)->loop(lp_header); }
# E2:{loop(lp_header)->loop(lp_body); }
# E3:{loop(lp_body)->loop(lp_exit); }
# E4:{loop(lp_exit)->loop(lp_header); }
# E5:{loop(lp_exit)->loop(exiy); }



loop *lp          = cfg->get_LoopInfo();
loop_node *entry  = lp->get_LoopEntry();
loop_node *exit   = lp->get_LoopExit();
loop_node *header = lp->get_LoopHeader();
loop_node *body   = lp->get_LoopBody();

InstructionList<> = body->get_Instructions();

pre_header_list = [];

foreach ii in InstructionList {

     if ( ii->isMoveAble2PreHeader() ) 
          pre_header_list.push(ii);
}

if ( !pre_header_list.empty() ){

 loop *pre_header = new loop();
 cfg->set_Loop(pre_header);

 entry->del_Succ(header);
 entry->set_Succ(pre_header);

 pre_header->set_Succ(header);
 pre_header->set_Proc(entry);

 header->del_Proc(entry);
 header->set_Proc(pre_header);


  foreach ii in pre_header_list { 
          pre_header->set_Instruction(ii);
          header->del_Instruction(ii);
  }

}




bool isMoveAble2PreHeader() {

     OperandList<> = Instruction(this)->get_Operands();

     bool change = true;

     foreach op in OperandList {
 
       if( (Operand)op != result ) {

         if( (Operand)op->get_Parent() != loopInfo && (Opernand)op->isStable() )
             change &= true;
         else
             change &= false;

       }
    }

return change;
}
form wiki definition: loop pre-header Suppose block M is a dominator with several incoming edges, some of them being back edges (so M is a loop header). It is advantageous to several optimization passes to break M up into two blocks Mpre and Mloop. The contents of M and back edges are moved to Mloop, the rest of the edges are moved to point into Mpre, and a new edge from Mpre to Mloop is inserted (so that Mpre is the immediate dominator of Mloop). In the beginning, Mpre would be empty, but passes like loop-invariant code motion could populate it. Mpre is called the loop pre-header, and Mloop would be the loop header. refs: http://en.wikipedia.org/wiki/Control_flow_graph

cycle graph


DataFlowGraph *dfg DataFlowGraph();

  dfg = dfg->run_Structure_analysis();  # reduce dead code
  dfg = dfg->run_LoadStore_analysis();  # reduce memory access
  dfg = dfg->run_reSchedule_analysis(); # parallel / serial
  dfg = dfg->run_Hardware_analysis();   # SIMD / MIMD ...

  assert( dfg->run_Pass() && "run BB analysis fail" );


  # assignment cycle graph for each BB
  #   
  BasicBlockList<> = dfg->get_BasicBlocks();  

  float tmp_time;

  while ( !BasicBlockList.empty() ) {

       (BasicBlock) bb = BasicBlockList.pop();
      
       tmp_time = 0;

       float { start_time:0, end_time:0 } = bb->init_time();

       tmp_time = start_time;

       foreach (Instruction)ii in bb->get_Instructons() {
  
             tmp_time =  max(tmp_time + ii->get_Operate_time(), tmp_time);

             if( tmp_time > Clock_Freq ) {

                 bb->set_end_time = ( tmp_time - ii->get_Operate_time() );

                 BasicBlock *new_bb = dfg->split_BB(bb,ii); 

                 if( dfg->run_Pass() && "split_BB fail" );

                 # split BB before ii, update "nALive", "outALive" for old.new BB 
                             
                 BasicBlockList.push(new_bb);
            }
       }
  }


  # cycle graph schdule
  #
  dfg->run_ASAP_schedule();
  dfg->run_ALAP_schedule();
  dfg->run_Force_Directed_schedule();

  # Hardware export
  #
  dfg->Module_export();
  dfg->Interface_export();
  dfg->Register_export();
  dfg->Memory_export();
  dfg->FSM_export();
  dfg->DataPath_export();
  dfg->Linker_export();
  dfg->test_bench_export();

2011年8月17日 星期三

SSA (static single assignment)

DataFlowGraph *dfg = DataFlowGraph([]);

foreach (BasicBlock)bb in (DataFlowGraph)dfg->get_BasicBlocks() {

    foreach (BasicBlock)preProc in (BasicBlock)bb->get_PreProcessor() {  

        pre_aLiveOutList = preProc->get_aLiveOutRegs();

        foreach (Register)inReg in (BasicBlock)bb->get_aLiveInRegs() {

            if( pre_aLiveOutList.find(inReg) != Pre_aLiveOutList.end() ) {

                (Register)OutReg = preProc->get_Reg(inReg->get_ID());

                if( !PHI_Exist(OutReg,InReg) ) {

                     # deep copy the old register items 2 new register, such as "procs", "succs"...
                     { new_OutReg, new_InReg } = PHI_Insert(OutReg,InReg);

                     # remove the old register pointer
                     bb->remove_reg(InReg);
                     bb->set_reg(new_InReg);

                     # update the graph
                     preProc->remove_reg(OutReg);
                     PreProc->set_reg(new_OutReg);   
               }

            }
       }
   }
}


#########################
# B1:{ a=1; }; B2:{ a=2; };  B3:{ a=a+1; }
# E1:{B1->B3}; E2{B2->B3};
#
# SSA graph
# B1: { a(1)=1; }; B2:{ a(2)=2; }; B3:{ phi a(3):[ B1:a(1), B2:a(2)]; a(3)=a(3)+1; }
Refs: SSA wiki http://en.wikipedia.org/wiki/Static_single_assignment_form Use-define_chain for load store http://en.wikipedia.org/wiki/Use-define_chain