Changeset 5227 for icGREP/icgrep-devel


Ignore:
Timestamp:
Dec 16, 2016, 4:16:28 PM (3 years ago)
Author:
nmedfort
Message:

Rewrite of the CarryManager? to support non-carry-collapsing loops.

Location:
icGREP/icgrep-devel/icgrep
Files:
1 added
1 deleted
39 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r5226 r5227  
    5050SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DUSE_BOOST")
    5151
     52SET(KERNEL_SRC kernels/kernel.cpp kernels/s2p_kernel.cpp kernels/streamset.cpp kernels/interface.cpp)
    5253SET(IDISA_SRC IDISA/types/streamtype.cpp IDISA/idisa_builder.cpp IDISA/idisa_avx_builder.cpp IDISA/idisa_i64_builder.cpp IDISA/idisa_sse_builder.cpp IDISA/idisa_nvptx_builder.cpp IDISA/idisa_target.cpp)
    5354
    5455SET(PABLO_SRC pablo/pabloAST.cpp pablo/branch.cpp pablo/codegenstate.cpp pablo/builder.cpp pablo/symbol_generator.cpp pablo/printer_pablos.cpp pablo/pablo_toolchain.cpp)
    55 SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_kernel.cpp pablo/pablo_compiler.cpp pablo/carry_manager.cpp pablo/carry_data.cpp)
    56 SET(PABLO_SRC ${PABLO_SRC} kernels/kernel.cpp kernels/s2p_kernel.cpp kernels/streamset.cpp kernels/interface.cpp)
     56SET(PABLO_SRC ${PABLO_SRC} pablo/pablo_kernel.cpp pablo/pablo_compiler.cpp pablo/carry_manager.cpp)
    5757SET(PABLO_SRC ${PABLO_SRC} pablo/analysis/pabloverifier.cpp)
    5858SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/codemotionpass.cpp pablo/passes/flattenif.cpp)
     
    6262ENDIF()
    6363
     64
     65add_library(CodeGen ${KERNEL_SRC} ${IDISA_SRC} object_cache.cpp)
    6466add_library(PabloADT ${PABLO_SRC})
    6567add_library(RegExpADT re/re_re.cpp re/re_cc.cpp re/re_rep.cpp re/re_diff.cpp re/re_intersect.cpp re/printer_re.cpp)
     
    6870add_library(UCDlib UCD/unicode_set.cpp UCD/ucd_compiler.cpp UCD/PropertyObjects.cpp UCD/resolve_properties.cpp UCD/UnicodeNameData.cpp)
    6971
    70 add_library(CodeGen object_cache.cpp ${IDISA_SRC})
    7172
    7273# add the executable
     
    111112add_executable(wc wc.cpp toolchain.cpp kernels/pipeline.cpp)
    112113add_executable(editd editd/editd.cpp editd/pattern_compiler.cpp toolchain.cpp kernels/pipeline.cpp editd/editdscan_kernel.cpp editd/editd_gpu_kernel.cpp editd/editd_cpu_kernel.cpp)
     114add_executable(array-test array-test.cpp toolchain.cpp kernels/pipeline.cpp)
    113115
    114116IF(ENABLE_PREGENERATED_UCD_FUNCTIONS)
     
    126128target_link_libraries (wc UCDlib PabloADT RegExpCompiler CCADT CodeGen ${REQ_LLVM_LIBRARIES} ${Boost_LIBRARIES} ${CUDA_LIB})
    127129target_link_libraries (editd UCDlib PabloADT RegExpCompiler CCADT CodeGen ${REQ_LLVM_LIBRARIES} ${Boost_LIBRARIES} ${CUDA_LIB})
     130target_link_libraries (array-test PabloADT CodeGen ${REQ_LLVM_LIBRARIES} ${Boost_LIBRARIES} ${CUDA_LIB})
    128131
    129132IF(ENABLE_MULTIPLEXING)
     
    134137    SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DENABLE_MULTIPLEXING")
    135138ENDIF()
    136 
    137139
    138140include_directories("${PROJECT_SOURCE_DIR}")
  • icGREP/icgrep-devel/icgrep/IDISA/idisa_builder.cpp

    r5217 r5227  
    66
    77#include "idisa_builder.h"
    8 #include <string>
    98#include <llvm/IR/IRBuilder.h>
    109#include <llvm/IR/Constants.h>
     
    1211#include <llvm/IR/Function.h>
    1312#include <llvm/Support/raw_ostream.h>
    14 #include <iostream>
     13#include <llvm/IR/TypeBuilder.h>
    1514
    1615namespace IDISA {
     
    116115}
    117116
     117Value * IDISA_Builder::CreateMalloc(Type * type, Value * size) {
     118    DataLayout DL(getModule());
     119    Type * const intTy = getIntPtrTy(DL);
     120    Type * const voidPtrTy = getVoidPtrTy();
     121    Function * malloc = cast<Function>(getModule()->getOrInsertFunction("malloc", voidPtrTy, intTy, nullptr));
     122    malloc->setDoesNotAlias(0);
     123    const auto width = ConstantExpr::getSizeOf(type);
     124    if (!width->isOneValue()) {
     125        if (isa<Constant>(size)) {
     126            size = ConstantExpr::getMul(cast<Constant>(size), width);
     127        } else {
     128            size = CreateMul(size, width);
     129        }
     130    }
     131    size = CreateTruncOrBitCast(size, intTy);
     132    CallInst * ci = CreateCall(malloc, {size});
     133    ci->setTailCall();
     134    ci->setCallingConv(malloc->getCallingConv());
     135    return CreateBitOrPointerCast(ci, type->getPointerTo());
     136}
     137
     138Value * IDISA_Builder::CreateAlignedMalloc(Type * type, Value * size, const unsigned alignment) {
     139    assert ((alignment & (alignment - 1)) == 0); // is power of 2
     140    DataLayout DL(getModule());
     141    IntegerType * const intTy = getIntPtrTy(DL);
     142    const auto byteWidth = (intTy->getBitWidth() / 8);
     143    const auto offset = ConstantInt::get(intTy, alignment + byteWidth - 1);
     144    const auto width = ConstantExpr::getSizeOf(type);
     145    if (!width->isOneValue()) {
     146        if (isa<Constant>(size)) {
     147            size = ConstantExpr::getMul(cast<Constant>(size), width);
     148        } else {
     149            size = CreateMul(size, width);
     150        }
     151    }
     152    if (isa<Constant>(size)) {
     153        size = ConstantExpr::getAdd(cast<Constant>(size), offset);
     154    } else {
     155        size = CreateAdd(size, offset);
     156    }
     157    size = CreateTruncOrBitCast(size, intTy);
     158    Value * unaligned = CreateMalloc(getInt8Ty(), size);
     159    Value * aligned = CreateBitOrPointerCast(unaligned, intTy);
     160    aligned = CreateAnd(CreateAdd(aligned, offset), ConstantExpr::getNot(ConstantInt::get(intTy, alignment - 1)));
     161    Value * ptr = CreateBitOrPointerCast(CreateSub(aligned, ConstantInt::get(intTy, byteWidth)), intTy->getPointerTo());
     162    CreateAlignedStore(CreateBitOrPointerCast(unaligned, intTy), ptr, byteWidth);
     163    return CreateBitOrPointerCast(aligned, type->getPointerTo());
     164}
     165
     166void IDISA_Builder::CreateFree(Value * ptr) {
     167    PointerType * const voidPtrTy = getVoidPtrTy();
     168    Function * const free = cast<Function>(getModule()->getOrInsertFunction("free", getVoidTy(), voidPtrTy, nullptr));
     169    CallInst * const ci = CreateCall(free, {CreateBitOrPointerCast(ptr, voidPtrTy)});
     170    ci->setTailCall();
     171    ci->setCallingConv(free->getCallingConv());
     172}
     173
     174void IDISA_Builder::CreateAlignedFree(Value * ptr) {
     175    DataLayout DL(getModule());
     176    IntegerType * const intTy = getIntPtrTy(DL);
     177    const auto byteWidth = (intTy->getBitWidth() / 8);
     178    ptr = CreateBitOrPointerCast(ptr, intTy);
     179    ptr = CreateSub(ptr, ConstantInt::get(intTy, byteWidth));
     180    ptr = CreateBitOrPointerCast(ptr, getInt8PtrTy());
     181    CreateFree(CreateAlignedLoad(ptr, byteWidth));
     182}
     183
     184Value * IDISA_Builder::CreateRealloc(Value * ptr, Value * size) {
     185    assert (ptr->getType()->isPointerTy());
     186    DataLayout DL(getModule());
     187    IntegerType * const intTy = getIntPtrTy(DL);
     188    PointerType * const voidPtrTy = getVoidPtrTy();
     189    Function * realloc = cast<Function>(getModule()->getOrInsertFunction("realloc", voidPtrTy, voidPtrTy, intTy, nullptr));
     190    realloc->setDoesNotAlias(0);
     191    Type * const type = ptr->getType();
     192    // calculate our new size parameter
     193    size = CreateMul(size, ConstantExpr::getSizeOf(type->getPointerElementType()));
     194    size = CreateTruncOrBitCast(size, intTy);
     195    // call realloc with the pointer and adjusted size
     196    CallInst * ci = CreateCall(realloc, {ptr, size});
     197    ci->setTailCall();
     198    ci->setCallingConv(realloc->getCallingConv());
     199    return CreateBitOrPointerCast(ci, type);
     200}
     201
     202Value * IDISA_Builder::CreateAlignedRealloc(Value * ptr, Value * size, const unsigned alignment) {
     203    assert ((alignment & (alignment - 1)) == 0); // is power of 2
     204    assert (ptr->getType()->isPointerTy());
     205    DataLayout DL(getModule());
     206    IntegerType * const intTy = getIntPtrTy(DL);
     207    PointerType * const bpTy = getInt8PtrTy();
     208    Type * const type = ptr->getType();
     209    // calculate our new size parameter
     210    const auto byteWidth = (intTy->getBitWidth() / 8);
     211    const auto offset = ConstantInt::get(intTy, alignment + byteWidth - 1);
     212    const auto width = ConstantExpr::getSizeOf(type);
     213    if (!width->isOneValue()) {
     214        if (isa<Constant>(size)) {
     215            size = ConstantExpr::getMul(cast<Constant>(size), width);
     216        } else {
     217            size = CreateMul(size, width);
     218        }
     219    }
     220    if (isa<Constant>(size)) {
     221        size = ConstantExpr::getAdd(cast<Constant>(size), offset);
     222    } else {
     223        size = CreateAdd(size, offset);
     224    }
     225    size = CreateTruncOrBitCast(size, intTy);
     226    // calculate the offset containing the unaligned pointer address
     227    ptr = CreateBitOrPointerCast(ptr, bpTy);
     228    ptr = CreateSub(ptr, ConstantInt::get(intTy, byteWidth));
     229    ptr = CreateBitOrPointerCast(ptr, intTy->getPointerTo());
     230    // load the unaligned pointer as an uint8 *
     231    ptr = CreateAlignedLoad(ptr, byteWidth);
     232    ptr = CreateBitOrPointerCast(ptr, bpTy);
     233    // call realloc with the unaligned pointer and adjusted size
     234    Value * unaligned = CreateRealloc(ptr, size);
     235    Value * aligned = CreateBitOrPointerCast(unaligned, intTy);
     236    aligned = CreateAnd(CreateAdd(aligned, offset), ConstantExpr::getNot(ConstantInt::get(intTy, alignment - 1)));
     237    Value * prefix = CreateBitOrPointerCast(CreateSub(aligned, ConstantInt::get(intTy, byteWidth)), intTy->getPointerTo());
     238    CreateAlignedStore(CreateBitOrPointerCast(unaligned, intTy), prefix, byteWidth);
     239    return CreateBitOrPointerCast(aligned, type);
     240}
     241
     242void IDISA_Builder::CreateMemZero(Value * ptr, Value * size, const unsigned alignment) {
     243    assert (ptr->getType()->isPointerTy() && size->getType()->isIntegerTy());
     244    Type * const type = ptr->getType();
     245    const auto width = ConstantExpr::getSizeOf(type->getPointerElementType());
     246    if (isa<Constant>(size)) {
     247        size = ConstantExpr::getMul(cast<Constant>(size), width);
     248    } else {
     249        size = CreateMul(size, width);
     250    }
     251    CreateMemSet(CreateBitOrPointerCast(ptr, getInt8PtrTy()), getInt8(0), size, alignment);
     252}
     253
     254PointerType * IDISA_Builder::getVoidPtrTy() const {
     255    return TypeBuilder<void *, false>::get(getContext());
     256}
     257
    118258Constant * IDISA_Builder::simd_himask(unsigned fw) {
    119259    return Constant::getIntegerValue(getIntNTy(mBitBlockWidth), APInt::getSplat(mBitBlockWidth, APInt::getHighBitsSet(fw, fw/2)));
  • icGREP/icgrep-devel/icgrep/IDISA/idisa_builder.h

    r5220 r5227  
    7878    void CreateBlockAlignedStore(Value * const value, Value * const ptr, std::initializer_list<Value *> indices);
    7979
     80    Value * CreateMalloc(Type * type, Value * size);
     81    Value * CreateAlignedMalloc(Type *type, Value * size, const unsigned alignment);
     82    void CreateFree(Value * ptr);
     83    void CreateAlignedFree(Value * ptr);
     84    Value * CreateRealloc(Value * ptr, Value * size);
     85    Value * CreateAlignedRealloc(Value * ptr, Value * size, const unsigned alignment);
     86    void CreateMemZero(Value * ptr, Value * size, const unsigned alignment = 1);
     87
    8088    void CallPrintRegister(const std::string & regName, Value * const value);
    8189    void CallPrintInt(const std::string & name, Value * const value);
     
    145153    }
    146154
     155    inline llvm::ConstantInt * getSize(const size_t value) const {
     156        return ConstantInt::get(getSizeTy(), value);
     157    }
     158
     159    PointerType * getVoidPtrTy() const;
     160
    147161    inline VectorType * getBitBlockType() const {
    148162        return mBitBlockType;
     163    }
     164
     165    inline unsigned getCacheAlignment() const {
     166        return mCacheLineAlignment;
    149167    }
    150168
  • icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp

    r5037 r5227  
    4545UnicodeSet::QuadAllocator UnicodeSet::mQuadAllocator;
    4646
    47 const size_t QUAD_BITS = (8 * sizeof(bitquad_t));
    48 const size_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
    49 const size_t UNICODE_QUAD_COUNT = (UNICODE_MAX + 1) / QUAD_BITS;
     47const uint64_t QUAD_BITS = (8 * sizeof(bitquad_t));
     48const uint64_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
     49const uint64_t UNICODE_QUAD_COUNT = (UNICODE_MAX + 1) / QUAD_BITS;
    5050const bitquad_t FULL_QUAD_MASK = -1;
    5151
  • icGREP/icgrep-devel/icgrep/grep_engine.cpp

    r5221 r5227  
    2323#include <llvm/Support/Debug.h>
    2424#include <llvm/IR/Verifier.h>
    25 #include <llvm/IR/TypeBuilder.h>
    2625#include <UCD/UnicodeNameData.h>
    2726#include <UCD/resolve_properties.h>
     
    275274    Type * const size_ty = iBuilder->getSizeTy();
    276275    Type * const int8PtrTy = iBuilder->getInt8PtrTy();
    277     Type * const voidTy = Type::getVoidTy(M->getContext());   
    278     Type * const voidPtrTy = TypeBuilder<void *, false>::get(M->getContext());
     276    Type * const voidTy = iBuilder->getVoidTy();
     277    Type * const voidPtrTy = iBuilder->getVoidPtrTy();
    279278    Type * const inputType = PointerType::get(ArrayType::get(ArrayType::get(iBuilder->getBitBlockType(), (UTF_16 ? 16 : 8)), 1), addrSpace);
    280279    Type * const resultTy = CountOnly ? size_ty : iBuilder->getVoidTy();
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r5217 r5227  
    114114pablo/builder.cpp
    115115pablo/builder.hpp
    116 pablo/carry_data.cpp
    117116pablo/carry_data.h
    118117pablo/carry_manager.cpp
     
    355354editd/editdscan_kernel.h
    356355editd/editdscan_kernel.cpp
     356array-test.cpp
     357cc/cc_compiler.cpp
     358cc/cc_compiler.h
     359editd/editd.cpp
     360editd/editd_cpu_kernel.cpp
     361editd/editd_cpu_kernel.h
     362editd/editd_gpu_kernel.cpp
     363editd/editd_gpu_kernel.h
     364editd/EditdCudaDriver.h
     365editd/editdscan_kernel.cpp
     366editd/editdscan_kernel.h
     367editd/pattern_compiler.cpp
     368editd/pattern_compiler.h
     369IDISA/types/streamtype.cpp
     370IDISA/types/streamtype.h
     371IDISA/CudaDriver.h
     372IDISA/idisa_avx_builder.cpp
     373IDISA/idisa_avx_builder.h
     374IDISA/idisa_builder.cpp
     375IDISA/idisa_builder.h
     376IDISA/idisa_i64_builder.cpp
     377IDISA/idisa_i64_builder.h
     378IDISA/idisa_nvptx_builder.cpp
     379IDISA/idisa_nvptx_builder.h
     380IDISA/idisa_sse_builder.cpp
     381IDISA/idisa_sse_builder.h
     382IDISA/idisa_target.cpp
     383IDISA/idisa_target.h
     384IDISA/llvm2ptx.h
     385kernels/cc_kernel.cpp
     386kernels/cc_kernel.h
     387kernels/deletion.cpp
     388kernels/deletion.h
     389kernels/interface.cpp
     390kernels/interface.h
     391kernels/kernel.cpp
     392kernels/kernel.h
     393kernels/p2s_kernel.cpp
     394kernels/p2s_kernel.h
     395kernels/pipeline.cpp
     396kernels/pipeline.h
     397kernels/radix64.cpp
     398kernels/radix64.h
     399kernels/s2p_kernel.cpp
     400kernels/s2p_kernel.h
     401kernels/scanmatchgen.cpp
     402kernels/scanmatchgen.h
     403kernels/stdout_kernel.cpp
     404kernels/stdout_kernel.h
     405kernels/streamset.cpp
     406kernels/streamset.h
     407kernels/symboltablepipeline.cpp
     408kernels/symboltablepipeline.h
     409pablo/analysis/pabloverifier.cpp
     410pablo/analysis/pabloverifier.hpp
     411pablo/optimizers/booleanreassociationpass.cpp
     412pablo/optimizers/booleanreassociationpass.h
     413pablo/optimizers/codemotionpass.cpp
     414pablo/optimizers/codemotionpass.h
     415pablo/optimizers/distributivepass.cpp
     416pablo/optimizers/distributivepass.h
     417pablo/optimizers/graph-facade.hpp
     418pablo/optimizers/maxsat.hpp
     419pablo/optimizers/pablo_automultiplexing.cpp
     420pablo/optimizers/pablo_automultiplexing.hpp
     421pablo/optimizers/pablo_bddminimization.cpp
     422pablo/optimizers/pablo_bddminimization.h
     423pablo/optimizers/pablo_simplifier.cpp
     424pablo/optimizers/pablo_simplifier.hpp
     425pablo/optimizers/schedulingprepass.cpp
     426pablo/optimizers/schedulingprepass.h
     427pablo/passes/factorizedfg.cpp
     428pablo/passes/factorizedfg.h
     429pablo/passes/flattenassociativedfg.cpp
     430pablo/passes/flattenassociativedfg.h
     431pablo/passes/flattenif.cpp
     432pablo/passes/flattenif.hpp
     433pablo/arithmetic.h
     434pablo/boolean.h
     435pablo/branch.cpp
     436pablo/branch.h
     437pablo/builder.cpp
     438pablo/builder.hpp
     439pablo/carry_data.h
     440pablo/carry_manager.cpp
     441pablo/carry_manager.h
     442pablo/codegenstate.cpp
     443pablo/codegenstate.h
     444pablo/expression_map.hpp
     445pablo/pablo_compiler.cpp
     446pablo/pablo_compiler.h
     447pablo/pablo_kernel.cpp
     448pablo/pablo_kernel.h
     449pablo/pablo_toolchain.cpp
     450pablo/pablo_toolchain.h
     451pablo/pabloAST.cpp
     452pablo/pabloAST.h
     453pablo/pe_advance.h
     454pablo/pe_call.h
     455pablo/pe_constant.h
     456pablo/pe_count.h
     457pablo/pe_infile.h
     458pablo/pe_integer.h
     459pablo/pe_lookahead.h
     460pablo/pe_matchstar.h
     461pablo/pe_ones.h
     462pablo/pe_scanthru.h
     463pablo/pe_setithbit.h
     464pablo/pe_string.h
     465pablo/pe_var.h
     466pablo/pe_zeroes.h
     467pablo/printer_pablos.cpp
     468pablo/printer_pablos.h
     469pablo/prototype.cpp
     470pablo/prototype.h
     471pablo/ps_assign.h
     472pablo/symbol_generator.cpp
     473pablo/symbol_generator.h
     474re/printer_re.cpp
     475re/printer_re.h
     476re/re_alt.h
     477re/re_analysis.cpp
     478re/re_analysis.h
     479re/re_any.h
     480re/re_assertion.h
     481re/re_cc.cpp
     482re/re_cc.h
     483re/re_compiler.cpp
     484re/re_compiler.h
     485re/re_diff.cpp
     486re/re_diff.h
     487re/re_end.h
     488re/re_intersect.cpp
     489re/re_intersect.h
     490re/re_memoizer.hpp
     491re/re_name.h
     492re/re_name_resolve.cpp
     493re/re_name_resolve.h
     494re/re_nullable.cpp
     495re/re_nullable.h
     496re/re_parser.cpp
     497re/re_parser.h
     498re/re_parser_bre.cpp
     499re/re_parser_bre.h
     500re/re_parser_ere.cpp
     501re/re_parser_ere.h
     502re/re_parser_helper.h
     503re/re_parser_pcre.cpp
     504re/re_parser_pcre.h
     505re/re_parser_prosite.cpp
     506re/re_parser_prosite.h
     507re/re_re.cpp
     508re/re_re.h
     509re/re_rep.cpp
     510re/re_rep.h
     511re/re_seq.h
     512re/re_simplifier.cpp
     513re/re_simplifier.h
     514re/re_start.h
     515re/re_toolchain.cpp
     516re/re_toolchain.h
     517re/re_utility.cpp
     518re/re_utility.h
     519UCD/Blocks.h
     520UCD/CaseFolding_txt.cpp
     521UCD/CaseFolding_txt.h
     522UCD/DerivedAge.h
     523UCD/DerivedBidiClass.h
     524UCD/DerivedBinaryProperties.h
     525UCD/DerivedCombiningClass.h
     526UCD/DerivedCoreProperties.h
     527UCD/DerivedDecompositionType.h
     528UCD/DerivedGeneralCategory.h
     529UCD/DerivedJoiningGroup.h
     530UCD/DerivedJoiningType.h
     531UCD/DerivedNormalizationProps.h
     532UCD/DerivedNumericType.h
     533UCD/EastAsianWidth.h
     534UCD/GraphemeBreakProperty.h
     535UCD/HangulSyllableType.h
     536UCD/LineBreak.h
     537UCD/PropertyAliases.h
     538UCD/PropertyObjects.cpp
     539UCD/PropertyObjects.h
     540UCD/PropertyObjectTable.h
     541UCD/PropertyValueAliases.h
     542UCD/PropList.h
     543UCD/resolve_properties.cpp
     544UCD/resolve_properties.h
     545UCD/ScriptExtensions.h
     546UCD/Scripts.h
     547UCD/SentenceBreakProperty.h
     548UCD/ucd_compiler.cpp
     549UCD/ucd_compiler.hpp
     550UCD/unicode_set.cpp
     551UCD/unicode_set.h
     552UCD/UnicodeNameData.cpp
     553UCD/UnicodeNameData.h
     554UCD/WordBreakProperty.h
     555util/papi_helper.hpp
     556util/slab_allocator.h
     557array-test.cpp
     558generate_predefined_ucd_functions.cpp
     559grep_engine.cpp
     560grep_engine.h
     561grep_type.h
     562hrtime.h
     563icgrep.cpp
     564object_cache.cpp
     565object_cache.h
     566symboltable.cpp
     567toolchain.cpp
     568toolchain.h
     569u8u16.cpp
     570utf16_encoder.cpp
     571utf16_encoder.h
     572utf8_encoder.cpp
     573utf8_encoder.h
     574wc.cpp
  • icGREP/icgrep-devel/icgrep/kernels/interface.cpp

    r5220 r5227  
    2121    }
    2222    Type * selfType = PointerType::getUnqual(mKernelStateType);
     23
    2324    // Create the accumulator get function prototypes
    2425    for (auto binding : mScalarOutputs) {
     
    3132        self->setName("self");       
    3233    }
     34
    3335    // Create the initialization function prototype
    34 
    3536    std::vector<Type *> initParameters = {selfType};
    3637    for (auto binding : mScalarInputs) {
  • icGREP/icgrep-devel/icgrep/kernels/interface.h

    r5224 r5227  
    108108    std::vector<Binding> mScalarOutputs;
    109109    std::vector<Binding> mInternalScalars;
    110     llvm::Type * mKernelStateType;
     110    llvm::StructType * mKernelStateType;
    111111    llvm::Value * mKernelInstance;
    112112    unsigned mLookAheadPositions;
  • icGREP/icgrep-devel/icgrep/kernels/kernel.cpp

    r5224 r5227  
    99#include <llvm/IR/Value.h>
    1010#include <llvm/Support/raw_ostream.h>
    11 #include <llvm/IR/TypeBuilder.h>
    1211#include <llvm/Support/ErrorHandling.h>
    1312#include <toolchain.h>
     
    2221                                 std::vector<Binding> scalar_parameters,
    2322                                 std::vector<Binding> scalar_outputs,
    24                                  std::vector<Binding> internal_scalars) :
    25     KernelInterface(builder, kernelName, stream_inputs, stream_outputs, scalar_parameters, scalar_outputs, internal_scalars) {}
    26 
    27 void KernelBuilder::addScalar(Type * t, std::string name) {
     23                                 std::vector<Binding> internal_scalars)
     24: KernelInterface(builder, kernelName, stream_inputs, stream_outputs, scalar_parameters, scalar_outputs, internal_scalars) {
     25
     26}
     27
     28unsigned KernelBuilder::addScalar(Type * type, std::string name) {
    2829    if (LLVM_UNLIKELY(mKernelStateType != nullptr)) {
    29         llvm::report_fatal_error("Illegal addition of kernel field after kernel state finalized: " + name);
    30     }
    31     unsigned index = mKernelFields.size();
    32     mKernelFields.push_back(t);
    33     mInternalStateNameMap.emplace(name, index);
     30        llvm::report_fatal_error("Cannot add kernel field " + name + " after kernel state finalized");
     31    }
     32    const auto index = mKernelFields.size();
     33    mKernelMap.emplace(name, index);
     34    mKernelFields.push_back(type);
     35    return index;
    3436}
    3537
     
    5052        throw std::runtime_error(out.str());
    5153    }
    52     addScalar(iBuilder->getSizeTy(), blockNoScalar);
    53     addScalar(iBuilder->getSizeTy(), logicalSegmentNoScalar);
    54     addScalar(iBuilder->getSizeTy(), processedItemCount);
    55     addScalar(iBuilder->getSizeTy(), producedItemCount);
    56     addScalar(iBuilder->getInt1Ty(), terminationSignal);
    5754    int streamSetNo = 0;
    5855    for (unsigned i = 0; i < mStreamSetInputs.size(); i++) {
     
    7875        addScalar(binding.type, binding.name);
    7976    }
     77    addScalar(iBuilder->getSizeTy(), blockNoScalar);
     78    addScalar(iBuilder->getSizeTy(), logicalSegmentNoScalar);
     79    addScalar(iBuilder->getSizeTy(), processedItemCount);
     80    addScalar(iBuilder->getSizeTy(), producedItemCount);
     81    addScalar(iBuilder->getInt1Ty(), terminationSignal);
    8082    mKernelStateType = StructType::create(iBuilder->getContext(), mKernelFields, mKernelName);
    8183}
     
    9597void KernelBuilder::generateKernel(std::vector<StreamSetBuffer *> input_buffers, std::vector<StreamSetBuffer*> output_buffers) {
    9698    auto savePoint = iBuilder->saveIP();
    97     Module * m = iBuilder->getModule();
     99    Module * const m = iBuilder->getModule();
    98100    mStreamSetInputBuffers = input_buffers;
    99101    mStreamSetOutputBuffers = output_buffers;
    100102    prepareKernel();  // possibly overriden by the KernelBuilder subtype
    101     KernelInterface::addKernelDeclarations(m);
     103    addKernelDeclarations(m);
    102104    generateDoBlockMethod();     // must be implemented by the KernelBuilder subtype
    103105    generateFinalBlockMethod();  // possibly overriden by the KernelBuilder subtype
     
    283285}
    284286
    285 Value * KernelBuilder::getScalarIndex(std::string fieldName) {
    286     const auto f = mInternalStateNameMap.find(fieldName);
    287     if (LLVM_UNLIKELY(f == mInternalStateNameMap.end())) {
    288         throw std::runtime_error("Kernel does not contain internal state: " + fieldName);
     287ConstantInt * KernelBuilder::getScalarIndex(const std::string & name) const {
     288    const auto f = mKernelMap.find(name);
     289    if (LLVM_UNLIKELY(f == mKernelMap.end())) {
     290        throw std::runtime_error("Kernel does not contain internal state: " + name);
    289291    }
    290292    return iBuilder->getInt32(f->second);
    291293}
    292294
    293 Value * KernelBuilder::getScalarFieldPtr(Value * self, std::string fieldName) {
     295unsigned KernelBuilder::getScalarCount() const {
     296    return mKernelFields.size();
     297}
     298
     299Value * KernelBuilder::getScalarFieldPtr(Value * self, const std::string & fieldName) {
    294300    return iBuilder->CreateGEP(self, {iBuilder->getInt32(0), getScalarIndex(fieldName)});
    295301}
     
    422428    Module * m = iBuilder->getModule();
    423429    Type * const voidTy = Type::getVoidTy(m->getContext());
    424     Type * const voidPtrTy = TypeBuilder<void *, false>::get(m->getContext());
     430    Type * const voidPtrTy = iBuilder->getVoidPtrTy();
    425431    Type * const int8PtrTy = iBuilder->getInt8PtrTy();
    426432    Type * const int1ty = iBuilder->getInt1Ty();
  • icGREP/icgrep-devel/icgrep/kernels/kernel.h

    r5224 r5227  
    108108    // Add an additional scalar field to the KernelState struct.
    109109    // Must occur before any call to addKernelDeclarations or createKernelModule.
    110     void addScalar(llvm::Type * t, std::string name);
    111    
     110    unsigned addScalar(llvm::Type * type, std::string name);
     111
     112    unsigned getScalarCount() const;
     113
    112114    // Run-time access of Kernel State and parameters of methods for
    113115    // use in implementing kernels.
    114116   
    115117    // Get the index of a named scalar field within the kernel state struct.
    116     llvm::Value * getScalarIndex(std::string);
     118    ConstantInt * getScalarIndex(const std::string & name) const;
    117119   
    118120    // Get the value of a scalar field for a given instance.
     
    128130    unsigned getStreamSetIndex(std::string name);
    129131   
    130     llvm::Value * getScalarFieldPtr(Value * self, std::string name);
     132    llvm::Value * getScalarFieldPtr(Value * self, const std::string & name);
    131133
    132134    llvm::Value * getStreamSetStructPtr(Value * self, std::string name);
     
    143145
    144146    std::vector<llvm::Type *>  mKernelFields;
    145     NameMap                    mInternalStateNameMap;
     147    NameMap                    mKernelMap;
    146148    NameMap                    mStreamSetNameMap;
    147149    std::vector<StreamSetBuffer *> mStreamSetInputBuffers;
  • icGREP/icgrep-devel/icgrep/kernels/p2s_kernel.cpp

    r5217 r5227  
    22#include "kernels/kernel.h"
    33#include "IDISA/idisa_builder.h"
    4 #include <llvm/IR/TypeBuilder.h>
    54#include <llvm/IR/Type.h>
    65#include <iostream>
  • icGREP/icgrep-devel/icgrep/kernels/pipeline.cpp

    r5224 r5227  
    44 */
    55
    6 
     6#include "pipeline.h"
    77#include <toolchain.h>
    8 #include "pipeline.h"
    9 
    108#include <IDISA/idisa_builder.h>
    11 
    129#include <kernels/interface.h>
    1310#include <kernels/kernel.h>
    1411#include <kernels/s2p_kernel.h>
    15 
    16 #include <llvm/IR/TypeBuilder.h>
    1712#include <iostream>
    1813
     
    2318    Module * m = iBuilder->getModule();
    2419    Type * const size_ty = iBuilder->getSizeTy();
    25     Type * const voidTy = Type::getVoidTy(m->getContext());
    26     Type * const voidPtrTy = TypeBuilder<void *, false>::get(m->getContext());
     20    Type * const voidTy = iBuilder->getVoidTy();
     21    Type * const voidPtrTy = iBuilder->getVoidPtrTy();
    2722    Type * const int8PtrTy = iBuilder->getInt8PtrTy();
    2823
     
    10398
    10499    Type * const size_ty = iBuilder->getSizeTy();
    105     Type * const voidPtrTy = TypeBuilder<void *, false>::get(m->getContext());
     100    Type * const voidPtrTy = iBuilder->getVoidPtrTy();
    106101    Type * const int8PtrTy = iBuilder->getInt8PtrTy();
    107102
     
    159154
    160155    Type * pthreadTy = iBuilder->getSizeTy();     
    161     Type * const voidPtrTy = TypeBuilder<void *, false>::get(m->getContext());
     156    Type * const voidPtrTy = iBuilder->getVoidPtrTy();
    162157    Type * const int8PtrTy = iBuilder->getInt8PtrTy();
    163158
  • icGREP/icgrep-devel/icgrep/pablo/arithmetic.h

    r5217 r5227  
    66namespace pablo {
    77
    8 class Add : public Statement {
     8class Operator : public PabloAST {
    99    friend class PabloBlock;
    1010public:
    1111    static inline bool classof(const PabloAST * e) {
    12         return e->getClassTypeId() == ClassTypeId::Add;
     12        switch (e->getClassTypeId()) {
     13            case ClassTypeId::Add:
     14            case ClassTypeId::Subtract:
     15            case ClassTypeId::LessThan:
     16            case ClassTypeId::LessThanEquals:
     17            case ClassTypeId::Equals:
     18            case ClassTypeId::GreaterThanEquals:
     19            case ClassTypeId::GreaterThan:
     20            case ClassTypeId::NotEquals:
     21                return true;
     22            default:
     23                return false;
     24        }
    1325    }
    1426    static inline bool classof(const void *) {
    1527        return false;
    1628    }
    17     virtual ~Add() { }
     29    PabloAST * getLH() const {
     30        return mLH;
     31    }
     32    PabloAST * getRH() const {
     33        return mRH;
     34    }
     35    virtual ~Operator() { }
    1836protected:
    19     Add(Type * const type, PabloAST * expr1, PabloAST * expr2, const String * name)
    20     : Statement(ClassTypeId::And, type, {expr1, expr2}, name)
    21     {
    22 
     37    Operator(const ClassTypeId typeId, Type * const type, PabloAST * const expr1, PabloAST * const expr2)
     38    : PabloAST(typeId, type, nullptr)
     39    , mLH(expr1)
     40    , mRH(expr2) {
     41        expr1->addUser(this);
     42        expr2->addUser(this);
    2343    }
     44private:
     45    PabloAST *          mLH;
     46    PabloAST *          mRH;
    2447};
    2548
    26 class Subtract : public Statement {
    27     friend class PabloBlock;
    28 public:
    29     static inline bool classof(const PabloAST * e) {
    30         return e->getClassTypeId() == ClassTypeId::Subtract;
    31     }
    32     static inline bool classof(const void *) {
    33         return false;
    34     }
    35     virtual ~Subtract() { }
    36 protected:
    37     Subtract(Type * const type, PabloAST * expr1, PabloAST * expr2, const String * name)
    38     : Statement(ClassTypeId::And, type, {expr1, expr2}, name)
    39     {
    40 
    41     }
     49#define CREATE_OPERATOR_TYPE(Name) \
     50class Name : public Operator { \
     51    friend class PabloBlock; \
     52public: \
     53    static inline bool classof(const PabloAST * e) { \
     54        return e->getClassTypeId() == ClassTypeId::Name; \
     55    } \
     56protected: \
     57    Name(Type * const type, PabloAST * const expr1, PabloAST * const expr2) \
     58    : Operator(ClassTypeId::Name, type, expr1, expr2) { \
     59    } \
    4260};
    4361
     62CREATE_OPERATOR_TYPE(Add)
     63CREATE_OPERATOR_TYPE(Subtract)
     64CREATE_OPERATOR_TYPE(LessThan)
     65CREATE_OPERATOR_TYPE(LessThanEquals)
     66CREATE_OPERATOR_TYPE(Equals)
     67CREATE_OPERATOR_TYPE(GreaterThanEquals)
     68CREATE_OPERATOR_TYPE(GreaterThan)
     69CREATE_OPERATOR_TYPE(NotEquals)
     70
     71#undef CREATE_OPERATOR_TYPE
    4472
    4573}
  • icGREP/icgrep-devel/icgrep/pablo/branch.cpp

    r5217 r5227  
    7373 * @brief getEscaped
    7474 ** ------------------------------------------------------------------------------------------------------------- */
    75 std::vector<Var *> Branch::getEscaped() const {
    76 
     75Branch::EscapedVars Branch::getEscaped() const {
    7776    const auto f = getParent()->getParent();
    7877    const auto n = f->getNumOfVariables();
    79 
    80     std::vector<Var *> escaped;   
     78    EscapedVars escaped;
    8179    for (unsigned i = 0; i < n; ++i) {
    8280        Var * const var = f->getVariable(i);
  • icGREP/icgrep-devel/icgrep/pablo/branch.h

    r5202 r5227  
    1414    friend class Simplifier;
    1515public:
     16    using EscapedVars = std::vector<Var *>;
    1617    static inline bool classof(const PabloAST * e) {
    1718        switch (e->getClassTypeId()) {
     
    3940    }
    4041    PabloBlock * setBody(PabloBlock * const body);
    41     std::vector<Var *> getEscaped() const;
     42    EscapedVars getEscaped() const;
    4243protected:
    4344    Branch(const ClassTypeId typeId, PabloAST * condition, PabloBlock * body);
  • icGREP/icgrep-devel/icgrep/pablo/builder.cpp

    r5217 r5227  
    9999}
    100100
    101 inline void printType(const Type * type, raw_string_ostream & out) {
    102     if (auto st = dyn_cast<IDISA::StreamType>(type)) {
    103         out << "<" << st->getNumElements() << " x s" << st->getFieldWidth() << ">";
    104     } else {
    105         type->print(out);
    106     }
    107 }
    108 
    109101using TypeId = PabloAST::ClassTypeId;
    110102
     
    201193
    202194PabloAST * PabloBuilder::createAssign(PabloAST * const variable, PabloAST * const value) {
    203     if (variable->getType() != value->getType()) {
    204         std::string tmp;
    205         raw_string_ostream out(tmp);
    206         out << "Cannot assign ";
    207         value->print(out);
    208         out << " to ";
    209         variable->print(out);
    210         out << ": type of ";
    211         value->print(out);
    212         out << " ";
    213         printType(value->getType(), out);
    214         out << " does not match ";
    215         variable->print(out);
    216         out << " ";
    217         printType(variable->getType(), out);
    218         throw std::runtime_error(out.str());
    219     }
    220195    return mPb->createAssign(variable, value);
    221196}
     
    426401    if (isa<Integer>(expr1) && isa<Integer>(expr2)) {
    427402        return getInteger(cast<Integer>(expr1)->value() + cast<Integer>(expr2)->value());
     403    } else if (isa<Integer>(expr1)) {
     404        if (cast<Integer>(expr1)->value() == 0) {
     405            return expr2;
     406        }
     407    } else if (isa<Integer>(expr2)) {
     408        if (cast<Integer>(expr2)->value() == 0) {
     409            return expr1;
     410        }
    428411    }
    429412    MAKE_BINARY(createAdd, TypeId::Add, expr1, expr2);
    430     return result;
    431 }
    432 
    433 PabloAST * PabloBuilder::createAdd(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
    434     if (isa<Integer>(expr1) && isa<Integer>(expr2)) {
    435         return getInteger(cast<Integer>(expr1)->value() + cast<Integer>(expr2)->value());
    436     }
    437     MAKE_NAMED_BINARY(createAdd, TypeId::Add, prefix, expr1, expr2);
    438413    return result;
    439414}
     
    442417    if (isa<Integer>(expr1) && isa<Integer>(expr2)) {
    443418        return getInteger(cast<Integer>(expr1)->value() - cast<Integer>(expr2)->value());
     419    } else if (isa<Integer>(expr1)) {
     420        if (cast<Integer>(expr1)->value() == 0) {
     421            return expr2;
     422        }
     423    } else if (isa<Integer>(expr2)) {
     424        if (cast<Integer>(expr2)->value() == 0) {
     425            return expr1;
     426        }
    444427    }
    445428    MAKE_BINARY(createSubtract, TypeId::Subtract, expr1, expr2);
     
    447430}
    448431
    449 PabloAST * PabloBuilder::createSubtract(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
     432PabloAST * PabloBuilder::createLessThan(PabloAST * expr1, PabloAST * expr2) {
    450433    if (isa<Integer>(expr1) && isa<Integer>(expr2)) {
    451         return getInteger(cast<Integer>(expr1)->value() - cast<Integer>(expr2)->value());
    452     }
    453     MAKE_NAMED_BINARY(createSubtract, TypeId::Subtract, prefix, expr1, expr2);
     434        return getInteger(cast<Integer>(expr1)->value() < cast<Integer>(expr2)->value() ? 1 : 0);
     435    }
     436    MAKE_BINARY(createLessThan, TypeId::LessThan, expr1, expr2);
    454437    return result;
    455438}
  • icGREP/icgrep-devel/icgrep/pablo/builder.hpp

    r5217 r5227  
    171171    PabloAST * createAdd(PabloAST * expr1, PabloAST * expr2);
    172172
    173     PabloAST * createAdd(PabloAST * expr1, PabloAST * expr2, const std::string & prefix);
    174 
    175173    PabloAST * createSubtract(PabloAST * expr1, PabloAST * expr2);
    176174
    177     PabloAST * createSubtract(PabloAST * expr1, PabloAST * expr2, const std::string & prefix);
     175    PabloAST * createLessThan(PabloAST * expr1, PabloAST * expr2);
    178176
    179177    inline If * createIf(PabloAST * condition, PabloBlock * body) {
     
    191189    inline While * createWhile(PabloAST * condition, PabloBuilder & builder) {
    192190        return mPb->createWhile(condition, builder.mPb);
     191    }
     192
     193    Type * getStreamSetTy(const uint64_t NumElements = 1, const uint64_t FieldWidth = 1) {
     194        return mPb->getStreamSetTy(NumElements, FieldWidth);
    193195    }
    194196
  • icGREP/icgrep-devel/icgrep/pablo/carry_data.h

    r4951 r5227  
    2424
    2525*/
    26 unsigned const LongAdvanceBase = 64;
    27 
    28 
    29 static unsigned power2ceil (unsigned v) {
    30     unsigned ceil = 1;
    31     while (ceil < v) ceil *= 2;
    32     return ceil;
    33 }
    34 
    35 static unsigned alignCeiling(unsigned toAlign, unsigned alignment) {
    36     return ((toAlign - 1) | (alignment - 1)) + 1;
    37 }
    38 
    39 static unsigned fullOrPartialBlocks(unsigned bits, unsigned block_size) {
    40     return alignCeiling(bits, block_size) / block_size;
    41 }
    4226
    4327namespace pablo {
    4428
    4529class PabloBlock;
     30class Statement;
    4631
    4732class CarryData {
     33    friend class CarryManager;
    4834public:
    4935
    50     CarryData(PabloBlock * b, unsigned packSize, unsigned itemsPerPack, unsigned blockSize):
    51        mPackSize(packSize),
    52        mItemsPerPack(itemsPerPack),
    53        mBlockSize(blockSize),
    54        mPositionsPerBlock(mItemsPerPack * (blockSize/mPackSize)),
    55        theScope(b),
    56        framePosition(0),
    57        ifDepth(0),
    58        whileDepth (0),
    59        maxNestingDepth(0),
    60        longAdvance({0, 0, 0}),
    61        shortAdvance({0, 0, 0}),
    62        unitAdvance({0, 0}),
    63        addWithCarry({0, 0}),
    64        nested({0, 0, 0}),
    65        summary({0, 0}),
    66        scopeCarryDataSize(0)
     36    enum SummaryType : int {
     37        NoSummary
     38        , ImplicitSummary
     39        , BorrowedSummary
     40        , ExplicitSummary
     41    };
     42
     43    CarryData()
     44    : summaryType(NoSummary)   
     45    , variableLength(false)
    6746    {
    68         enumerateLocal();
     47
     48    }
     49             
     50    bool hasSummary() const {
     51        return (summaryType != NoSummary);
     52    }
     53   
     54    bool hasImplicitSummary() const {
     55        return (summaryType == ImplicitSummary);
    6956    }
    7057
    71     friend class CarryManager;
    72    
    73     inline unsigned roomInFinalPack(unsigned allocatedBits) const {
    74         return mItemsPerPack - (allocatedBits % mItemsPerPack);
    75     }
    76    
    77     void enumerateLocal();
    78 
    79     void dumpCarryData(llvm::raw_ostream & strm);
    80    
    81     unsigned getFrameIndex()  const {
    82         return framePosition;
    83     }
    84    
    85     void setFramePosition(unsigned p) {
    86         framePosition = p;
    87     }
    88    
    89     unsigned getIfDepth()  const {
    90         return ifDepth;
    91     }
    92    
    93     void setIfDepth(unsigned d) {
    94         ifDepth = d;
    95     }
    96    
    97     unsigned getWhileDepth()  const {
    98         return whileDepth;
    99     }
    100        
    101     void setWhileDepth(unsigned d) {
    102         whileDepth = d;
    103     }
    104    
    105     unsigned longAdvanceEntries(unsigned shift_amount) const {
    106         return fullOrPartialBlocks(shift_amount, mBlockSize);
    107     }
    108    
    109     unsigned longAdvanceBufferSize(unsigned shift_amount)  const {
    110         return power2ceil(longAdvanceEntries(shift_amount));
    111     }
    112    
    113     bool hasLongAdvances() const { return longAdvance.entries > 0;}
    114    
    115     unsigned getLocalCarryPackIndex () {
    116         return shortAdvance.frameOffset / mItemsPerPack;
     58    bool hasBorrowedSummary() const {
     59        return (summaryType == BorrowedSummary);
    11760    }
    11861
    119     unsigned getLocalCarryPackCount () {
    120         return fullOrPartialBlocks(nested.frameOffset, mItemsPerPack) - shortAdvance.frameOffset / mItemsPerPack;
     62    bool hasExplicitSummary() const {
     63        return (summaryType == ExplicitSummary);
    12164    }
    122    
    123     unsigned getScopeCarryPackCount () {
    124         return fullOrPartialBlocks(scopeCarryDataSize, mItemsPerPack);
    125     }
    126    
    127     bool hasCarries() const { return scopeCarryDataSize > 0;}
    128    
    129     bool explicitSummaryRequired() const {
    130         return (ifDepth > 0) && (scopeCarryDataSize > mItemsPerPack);
    131     }
     65
    13266   
    13367protected:
    13468
    135     unsigned mPackSize, mItemsPerPack, mBlockSize, mPositionsPerBlock;
    136    
    137     PabloBlock * theScope;
    138    
    139     unsigned framePosition;
    140    
    141     unsigned ifDepth;
    142     unsigned whileDepth;
    143     unsigned maxNestingDepth;   
    144    
    145     struct {unsigned frameOffset; unsigned entries; unsigned allocatedBitBlocks;} longAdvance;
    146     struct {unsigned frameOffset; unsigned entries; unsigned allocatedBits;} shortAdvance;
    147     struct {unsigned frameOffset; unsigned entries;} unitAdvance;
    148     struct {unsigned frameOffset; unsigned entries;} addWithCarry;
    149     struct {unsigned frameOffset; unsigned entries; unsigned allocatedBits;} nested;
    150     struct {unsigned frameOffset; unsigned allocatedBits;} summary;
     69    SummaryType     summaryType;
     70    bool            variableLength;
    15171
    152     unsigned scopeCarryDataSize;
    153    
    15472};
    15573
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.cpp

    r5217 r5227  
    1414#include <llvm/IR/CallingConv.h>
    1515#include <llvm/IR/Function.h>
    16 #include <iostream>
    17 
     16#include <pablo/printer_pablos.h>
    1817
    1918namespace pablo {
    2019
     20BOOST_ATTRIBUTE_UNUSED
     21
     22inline static unsigned nearest_pow2(const unsigned v) {
     23    assert(v > 0 && v < (UINT32_MAX / 2));
     24    return (v < 2) ? 1 : (1 << (32 - __builtin_clz(v - 1)));
     25}
     26
     27inline static unsigned ceil_udiv(const unsigned x, const unsigned y) {
     28    return (((x - 1) | (y - 1)) + 1) / y;
     29}
     30
    2131/** ------------------------------------------------------------------------------------------------------------- *
    2232 * @brief initializeCarryData
    2333 ** ------------------------------------------------------------------------------------------------------------- */
    24 Type * CarryManager::initializeCarryData(PabloKernel * const kernel) {
    25     mRootScope = kernel->getEntryBlock();
    26     mCarryInfoVector.resize(mRootScope->enumerateScopes(0) + 1);
    27     mCarryPackType = mBitBlockType;
    28     const unsigned totalCarryDataSize = enumerate(mRootScope, 0, 0);
    29 
    30     mCarryPackPtr.resize(totalCarryDataSize + 1, nullptr);
    31     mCarryInPack.resize(totalCarryDataSize + 1, nullptr);
    32     mCarryOutPack.resize(totalCarryDataSize + 1, nullptr);
    33 
    34     mTotalCarryDataBitBlocks = totalCarryDataSize;
    35     ArrayType* cdArrayTy = ArrayType::get(mBitBlockType, mTotalCarryDataBitBlocks);
    36     return cdArrayTy;
     34void CarryManager::initializeCarryData(PabloKernel * const kernel) {
     35
     36    // Each scope constructs its own CarryData struct, which will be added to the final "carries" struct
     37    // that is added to the Kernel. The scope index will indicate which struct to access.
     38
     39    // A CarryData struct either contains an array of CarryPackBlocks or an integer indicating the capacity of
     40    // the variable length CarryData struct and pointer. A variable length CarryData struct is required whenever
     41    // the streams accessed by a loop could vary between iterations. When resizing a CarryData struct for a
     42    // particular loop, the current loop struct and all nested structs need to be resized. This accommodates
     43    // the fact every pablo While loop must be executed at least once.
     44
     45    // A nested loop may also contain a variable length CarryData struct
     46
     47    // To determine whether we require a variable length CarryData struct, we test the escaped variables of
     48    // each loop branch to see whether they are used as the index parameter of a nested Extract statement.
     49    // Any scope that requires variable length CarryData, requires that all nested branches have a unique
     50    // set of carries for that iteration.
     51
     52    mKernel = kernel;
     53
     54    mCurrentScope = kernel->getEntryBlock();
     55
     56    mCarryMetadata.resize(enumerate(mCurrentScope));
     57
     58    mKernel->addScalar(analyse(mCurrentScope), "carries");
    3759}
    3860
     
    4062 * @brief initializeCodeGen
    4163 ** ------------------------------------------------------------------------------------------------------------- */
    42 void CarryManager::initializeCodeGen(PabloKernel * const kernel, Value * selfPtr) {
    43     mKernelBuilder = kernel;
    44     mSelf = selfPtr;
    45    
    46     Value * cdArrayPtr = iBuilder->CreateGEP(mSelf, {ConstantInt::get(iBuilder->getSizeTy(), 0), mKernelBuilder->getScalarIndex("carries")});
    47 //#ifndef NDEBUG
    48 //    iBuilder->CallPrintInt("cdArrayPtr", iBuilder->CreatePtrToInt(cdArrayPtr, iBuilder->getSizeTy()));
    49 //#endif
    50     mCarryPackBasePtr = iBuilder->CreateBitCast(cdArrayPtr, PointerType::get(mCarryPackType, 0));
    51     mCarryBitBlockPtr = iBuilder->CreateBitCast(cdArrayPtr, PointerType::get(mBitBlockType, 0));
    52     mCurrentScope = mRootScope;
     64void CarryManager::initializeCodeGen(Value * self, Function * function) {
     65    // TODO: need to look into abstracting the Initialize creation function in KernelBuilder::generateKernel
     66    // so that we can allocate the variable length buffers if needed.
     67
     68    mSelf = self;
     69    mFunction = function;
     70
     71    assert(mCarryMetadata.size() > 0);
     72    mCarryInfo = &mCarryMetadata[0];
     73    assert (!mCarryInfo->hasSummary());
     74
     75    mCurrentFrame = iBuilder->CreateGEP(mSelf, {iBuilder->getInt32(0), mKernel->getScalarIndex("carries")}, "carries");
    5376    mCurrentFrameIndex = 0;
    54     assert(mCarryInfoVector.size() > 0);
    55     mCarryInfo = mCarryInfoVector[0];
    56     assert(summaryPack() < mCarryOutPack.size());
    57     mCarryOutPack[summaryPack()] = Constant::getNullValue(mCarryPackType);
     77
     78    assert (mCarryFrame.empty());
    5879    assert (mCarrySummary.empty());
    5980}
    6081
    6182/** ------------------------------------------------------------------------------------------------------------- *
     83 * @brief enterLoopScope
     84 ** ------------------------------------------------------------------------------------------------------------- */
     85void CarryManager::enterLoopScope(PabloBlock * const scope) {
     86    assert (scope);
     87    if (mLoopDepth++ == 0) {
     88        Value * const blockNo = mKernel->getScalarField(mSelf, blockNoScalar);
     89        mLoopSelector = iBuilder->CreateAnd(blockNo, ConstantInt::get(blockNo->getType(), 1));
     90    }
     91    enterScope(scope);
     92}
     93
     94/** ------------------------------------------------------------------------------------------------------------- *
     95 * @brief enterLoopBody
     96 ** ------------------------------------------------------------------------------------------------------------- */
     97void CarryManager::enterLoopBody(BasicBlock * const entryBlock) {
     98
     99    if (mCarryInfo->hasSummary()) {
     100        PHINode * carrySummary = iBuilder->CreatePHI(mCarryPackType, 2, "summary");
     101        assert (mCarrySummary.size() > 0);
     102        carrySummary->addIncoming(mCarrySummary.back(), entryBlock);
     103        // Replace the incoming carry summary with the phi node and add the phi node to the stack
     104        // so that we can properly OR it into the outgoing summary value.
     105        mCarrySummary.back() = carrySummary;
     106        mCarrySummary.push_back(carrySummary);
     107    }
     108
     109    if (LLVM_UNLIKELY(mCarryInfo->variableLength)) {
     110        // Check whether we need to resize the carry state
     111        PHINode * index = iBuilder->CreatePHI(iBuilder->getSizeTy(), 2);
     112        mLoopIndicies.push_back(index);
     113        index->addIncoming(iBuilder->getSize(0), entryBlock);
     114        Value * capacityPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(0)});
     115        Value * capacity = iBuilder->CreateLoad(capacityPtr, false, "carryCapacity");
     116        Value * arrayPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(1)});
     117
     118        BasicBlock * resizeBlock = BasicBlock::Create(iBuilder->getContext(), "", mFunction);
     119        BasicBlock * codeBlock = BasicBlock::Create(iBuilder->getContext(), "", mFunction);
     120
     121        Value * cond = iBuilder->CreateICmpULT(index, capacity);
     122        iBuilder->CreateCondBr(cond, codeBlock, resizeBlock);
     123        iBuilder->SetInsertPoint(resizeBlock);
     124
     125        Type * const carryStateType = arrayPtr->getType()->getPointerElementType()->getPointerElementType();
     126        Value * newCapacity = iBuilder->CreateMul(iBuilder->CreateAdd(index, iBuilder->getSize(1)), iBuilder->getSize(2));
     127        Value * newArrayPtr = iBuilder->CreateAlignedMalloc(carryStateType, newCapacity, iBuilder->getCacheAlignment());
     128        iBuilder->CreateMemCpy(newArrayPtr, arrayPtr, capacity, iBuilder->getCacheAlignment());
     129        iBuilder->CreateMemZero(iBuilder->CreateGEP(newArrayPtr, capacity), iBuilder->CreateSub(newCapacity, capacity), iBuilder->getCacheAlignment());
     130        iBuilder->CreateAlignedFree(arrayPtr);
     131        iBuilder->CreateStore(newCapacity, capacityPtr);
     132        iBuilder->CreateStore(newArrayPtr, arrayPtr);
     133        iBuilder->CreateBr(codeBlock);
     134
     135        // Load the appropriate carry stat block
     136        iBuilder->SetInsertPoint(codeBlock);
     137
     138        mCurrentFrame = iBuilder->CreateGEP(iBuilder->CreateLoad(arrayPtr), index);
     139
     140    }
     141}
     142
     143/** ------------------------------------------------------------------------------------------------------------- *
     144 * @brief leaveLoopBody
     145 ** ------------------------------------------------------------------------------------------------------------- */
     146void CarryManager::leaveLoopBody(BasicBlock * const exitBlock) {
     147    if (mCarryInfo->hasSummary()) {
     148        const auto n = mCarrySummary.size(); assert (n > 1);
     149        cast<PHINode>(mCarrySummary[n - 2])->addIncoming(mCarrySummary[n - 1], exitBlock);
     150        mCarrySummary.pop_back();
     151    }
     152    if (LLVM_UNLIKELY(mCarryInfo->variableLength)) {
     153        assert (mLoopIndicies.size() > 0);
     154        PHINode * index = mLoopIndicies.back();
     155        index->addIncoming(iBuilder->CreateAdd(index, iBuilder->getSize(1)), exitBlock);
     156        mLoopIndicies.pop_back();
     157    }
     158}
     159
     160/** ------------------------------------------------------------------------------------------------------------- *
     161 * @brief leaveLoopScope
     162 ** ------------------------------------------------------------------------------------------------------------- */
     163void CarryManager::leaveLoopScope(BasicBlock * const entryBlock, BasicBlock * const exitBlock) {
     164    assert (mLoopDepth > 0);
     165    if (--mLoopDepth == 0) {
     166        mLoopSelector = nullptr;
     167    }
     168    leaveScope();
     169}
     170
     171/** ------------------------------------------------------------------------------------------------------------- *
     172 * @brief enterIfScope
     173 ** ------------------------------------------------------------------------------------------------------------- */
     174void CarryManager::enterIfScope(PabloBlock * const scope) {
     175    ++mIfDepth;
     176    enterScope(scope);
     177    mCarrySummary.push_back(Constant::getNullValue(mCarryPackType));
     178}
     179
     180/** ------------------------------------------------------------------------------------------------------------- *
     181 * @brief generateSummaryTest
     182 ** ------------------------------------------------------------------------------------------------------------- */
     183Value * CarryManager::generateSummaryTest(Value * condition) {
     184    if (LLVM_LIKELY(mCarryInfo->hasSummary())) {
     185        ConstantInt * zero = iBuilder->getInt32(0);
     186        std::vector<Value *> indicies;
     187        // enter the (potentially nested) struct and extract the summary element (0)
     188        unsigned count = 2;
     189        if (LLVM_UNLIKELY(mCarryInfo->hasBorrowedSummary())) {
     190            Type * frameTy = mCurrentFrame->getType()->getPointerElementType();
     191            count = 1;
     192            while (frameTy->isStructTy()) {
     193                ++count;
     194                frameTy = frameTy->getStructElementType(0);
     195            }
     196        }
     197        indicies.assign(count, zero);
     198        if (LLVM_UNLIKELY(mCarryInfo->hasImplicitSummary() && mLoopDepth > 0)) {
     199            indicies.push_back(zero);
     200            indicies.push_back(mLoopSelector);
     201        }
     202        Value * ptr = iBuilder->CreateGEP(mCurrentFrame, indicies);
     203        // Sanity check: make sure we're accessing a summary value
     204        assert (ptr->getType()->getPointerElementType()->canLosslesslyBitCastTo(condition->getType()));
     205        Value * summary = iBuilder->CreateBlockAlignedLoad(ptr);
     206        condition = iBuilder->simd_or(condition, summary);
     207    }
     208    return condition;
     209}
     210
     211/** ------------------------------------------------------------------------------------------------------------- *
     212 * @brief enterIfBody
     213 ** ------------------------------------------------------------------------------------------------------------- */
     214void CarryManager::enterIfBody(BasicBlock * const entryBlock) { assert (entryBlock);
     215
     216}
     217
     218/** ------------------------------------------------------------------------------------------------------------- *
     219 * @brief leaveIfBody
     220 ** ------------------------------------------------------------------------------------------------------------- */
     221void CarryManager::leaveIfBody(BasicBlock * const exitBlock) { assert (exitBlock);
     222    const auto n = mCarrySummary.size();
     223    if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {
     224        assert (mCarrySummary.size() > 0);
     225        Value * ptr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(0)});
     226        Value * const value = iBuilder->CreateBitCast(mCarrySummary.back(), mBitBlockType);
     227        iBuilder->CreateBlockAlignedStore(value, ptr);
     228    }
     229    if (n > 1) {
     230        mCarrySummary[n - 1] = iBuilder->CreateOr(mCarrySummary[n - 1], mCarrySummary[n - 2], "summary");
     231    }
     232}
     233
     234/** ------------------------------------------------------------------------------------------------------------- *
     235 * @brief leaveIfScope
     236 ** ------------------------------------------------------------------------------------------------------------- */
     237void CarryManager::leaveIfScope(BasicBlock * const entryBlock, BasicBlock * const exitBlock) {
     238    assert (mIfDepth > 0);
     239    if (mCarryInfo->hasSummary()) {
     240        const auto n = mCarrySummary.size(); assert (n > 0);
     241        if (n > 1) {
     242            // When leaving a nested If scope with a summary value, phi out the summary to ensure the
     243            // appropriate summary is stored in the outer scope.
     244            Value * nested = mCarrySummary[n - 1];
     245            Value * outer = mCarrySummary[n - 2];
     246            if (LLVM_LIKELY(nested != outer)) {
     247                assert (nested->getType() == outer->getType());
     248                PHINode * const phi = iBuilder->CreatePHI(nested->getType(), 2, "summary");
     249                phi->addIncoming(outer, entryBlock);
     250                phi->addIncoming(nested, exitBlock);
     251                mCarrySummary[n - 2] = phi;
     252            }
     253        }       
     254    }
     255    --mIfDepth;
     256    leaveScope();
     257    mCarrySummary.pop_back();
     258}
     259
     260/** ------------------------------------------------------------------------------------------------------------ *
    62261 * @brief enterScope
    63262 ** ------------------------------------------------------------------------------------------------------------- */
    64263void CarryManager::enterScope(PabloBlock * const scope) {
    65     assert(summaryPack() < mCarryOutPack.size());
    66     Value * summaryCarry = mCarryOutPack[summaryPack()];
    67     mCarrySummary.push_back(summaryCarry);
     264    assert (scope);
     265    // Store the state of the current frame and update the scope state
     266    mCarryFrame.emplace_back(mCurrentFrame, mCurrentFrameIndex + 1);
    68267    mCurrentScope = scope;
    69     mCarryInfo = mCarryInfoVector[scope->getScopeIndex()];
    70     mCurrentFrameIndex += mCarryInfo->getFrameIndex();
    71     assert(summaryPack() < mCarryOutPack.size());
    72     mCarryOutPack[summaryPack()] = Constant::getNullValue(mCarryPackType);
     268    mCarryInfo = &mCarryMetadata[scope->getScopeIndex()];
     269    // Check whether we're still within our struct bounds; if this fails, either the Pablo program changed within
     270    // compilation or a memory corruption has occured.
     271    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
     272    mCurrentFrame = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex)});
     273    // Verify we're pointing to a carry frame struct
     274    assert(mCurrentFrame->getType()->getPointerElementType()->isStructTy());
     275    // We always use the 0-th slot for the summary value, even when it's implicit
     276    mCurrentFrameIndex = mCarryInfo->hasExplicitSummary() ? 1 : 0;
     277
    73278}
    74279
     
    77282 ** ------------------------------------------------------------------------------------------------------------- */
    78283void CarryManager::leaveScope() {
    79     assert(summaryPack() < mCarryOutPack.size());
    80     Value * summaryCarry = mCarryOutPack[summaryPack()];
    81     assert (mCurrentScope != mRootScope);
    82     mCurrentFrameIndex -= mCarryInfo->getFrameIndex();
     284
     285    // Did we use all of the packs in this carry struct?
     286    assert (mCurrentFrameIndex == mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
     287    // Sanity test: are there remaining carry frames?
     288    assert (mCarryFrame.size() > 0);
     289
     290    std::tie(mCurrentFrame, mCurrentFrameIndex) = mCarryFrame.back();
     291
     292    assert(mCurrentFrame->getType()->getPointerElementType()->isStructTy());
     293
     294    mCarryFrame.pop_back();
     295
    83296    mCurrentScope = mCurrentScope->getPredecessor();
    84     mCarryInfo = mCarryInfoVector[mCurrentScope->getScopeIndex()];
    85     assert(summaryPack() < mCarryOutPack.size());
    86     mCarryOutPack[summaryPack()] = summaryCarry;
    87     mCarrySummary.pop_back();
     297    assert (mCurrentScope);
     298    mCarryInfo = &mCarryMetadata[mCurrentScope->getScopeIndex()];   
    88299}
    89300
     
    91302 * @brief addCarryInCarryOut
    92303 ** ------------------------------------------------------------------------------------------------------------- */
    93 Value * CarryManager::addCarryInCarryOut(const unsigned localIndex, Value * const e1, Value * const e2) {
    94     std::pair<Value *, Value *> fullAdd = iBuilder->bitblock_add_with_carry(e1, e2, getCarryIn(localIndex));
    95     setCarryOut(localIndex, std::get<0>(fullAdd));
    96     return std::get<1>(fullAdd);
     304Value * CarryManager::addCarryInCarryOut(const Statement * operation, Value * const e1, Value * const e2) {
     305    Value * const carryIn = getNextCarryIn();
     306    Value * carryOut, * result;
     307    std::tie(carryOut, result) = iBuilder->bitblock_add_with_carry(e1, e2, carryIn);
     308    setNextCarryOut(carryOut);
     309    assert (result->getType() == mBitBlockType);
     310    return result;
    97311}
    98312
     
    100314 * @brief advanceCarryInCarryOut
    101315 ** ------------------------------------------------------------------------------------------------------------- */
    102 Value * CarryManager::advanceCarryInCarryOut(const unsigned localIndex, const unsigned shiftAmount, Value * const value) {
    103     if (LLVM_LIKELY(shiftAmount == 1)) {
    104         return shortAdvanceCarryInCarryOut(unitAdvancePosition(localIndex), shiftAmount, value);
    105     } else if (shiftAmount < LongAdvanceBase) {
    106         return shortAdvanceCarryInCarryOut(shortAdvancePosition(localIndex), shiftAmount, value);
     316Value * CarryManager::advanceCarryInCarryOut(const Advance * advance, Value * const value) {
     317    const auto shiftAmount = advance->getAmount();
     318    if (LLVM_LIKELY(shiftAmount <= mBitBlockWidth)) {
     319        Value * const carryIn = getNextCarryIn();
     320        Value * carryOut, * result;
     321        if (LLVM_UNLIKELY(shiftAmount == mBitBlockWidth)) {
     322            result = carryIn;
     323            carryOut = value;
     324        } else {
     325            std::tie(carryOut, result) = iBuilder->bitblock_advance(value, carryIn, shiftAmount);
     326        }
     327        setNextCarryOut(carryOut);
     328        assert (result->getType() == mBitBlockType);
     329        return result;
    107330    } else {
    108         return longAdvanceCarryInCarryOut(longAdvancePosition(localIndex), shiftAmount, value);
    109     }
    110 }
    111 
    112 /** ------------------------------------------------------------------------------------------------------------- *
    113  * @brief shortAdvanceCarryInCarryOut
    114  ** ------------------------------------------------------------------------------------------------------------- */
    115 Value * CarryManager::shortAdvanceCarryInCarryOut(const unsigned index, const unsigned shiftAmount, Value * const value) {
    116     Value * const carryIn = getCarryPack(index);
    117     assert (index < mCarryOutPack.size());
    118     std::pair<Value *, Value *> adv = iBuilder->bitblock_advance(value, carryIn, shiftAmount);
    119     mCarryOutPack[index] = std::get<0>(adv);
    120     if (mCarryInfo->getWhileDepth() == 0) {
    121         storeCarryOut(index);
    122     }
    123     if (LLVM_LIKELY(hasSummary())) {
    124         addToSummary(value);
    125     }
    126     return std::get<1>(adv);
     331        return longAdvanceCarryInCarryOut(shiftAmount, value);
     332    }
    127333}
    128334
     
    130336 * @brief longAdvanceCarryInCarryOut
    131337 ** ------------------------------------------------------------------------------------------------------------- */
    132 Value * CarryManager::longAdvanceCarryInCarryOut(const unsigned index, const unsigned shiftAmount, Value * const value) {
    133     Value * advBaseIndex = ConstantInt::get(iBuilder->getSizeTy(), index);
    134     if (shiftAmount <= mBitBlockWidth) {
    135         // special case using a single buffer entry and the carry_out value.
    136         Value * advanceDataPtr = iBuilder->CreateGEP(mCarryBitBlockPtr, advBaseIndex);
    137         Value * carry_block0 = iBuilder->CreateBlockAlignedLoad(advanceDataPtr);
    138         iBuilder->CreateBlockAlignedStore(value, advanceDataPtr);
    139         /* Very special case - no combine */
    140         if (shiftAmount == mBitBlockWidth) {
    141             return carry_block0;
    142         }
    143         Value* block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carry_block0, iBuilder->getIntNTy(mBitBlockWidth)), mBitBlockWidth - shiftAmount);
    144         Value* block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(value, iBuilder->getIntNTy(mBitBlockWidth)), shiftAmount);
    145         return iBuilder->CreateBitCast(iBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
    146     }
    147     // We need a buffer of at least two elements for storing the advance data.
    148     const unsigned block_shift = shiftAmount % mBitBlockWidth;
    149     const unsigned advanceEntries = mCarryInfo->longAdvanceEntries(shiftAmount);
    150     const unsigned bufsize = mCarryInfo->longAdvanceBufferSize(shiftAmount);
    151     Value * indexMask = ConstantInt::get(iBuilder->getSizeTy(), bufsize - 1);  // A mask to implement circular buffer indexing
    152     Value * blockIndex = mKernelBuilder->getScalarField(mSelf, blockNoScalar);
    153     Value * loadIndex0 = iBuilder->CreateAdd(iBuilder->CreateAnd(iBuilder->CreateSub(blockIndex, ConstantInt::get(iBuilder->getSizeTy(), advanceEntries)), indexMask), advBaseIndex);
    154     Value * storeIndex = iBuilder->CreateAdd(iBuilder->CreateAnd(blockIndex, indexMask), advBaseIndex);
    155     Value * carry_block0 = iBuilder->CreateBlockAlignedLoad(iBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex0));
    156     // If the long advance is an exact multiple of mBITBLOCK_WIDTH, we simply return the oldest
     338Value * CarryManager::longAdvanceCarryInCarryOut(const unsigned shiftAmount, Value * value) {
     339
     340    assert (shiftAmount > mBitBlockWidth);
     341
     342    Type * const streamVectorTy = iBuilder->getIntNTy(mBitBlockWidth);
     343    value = iBuilder->CreateBitCast(value, mBitBlockType);
     344    Value * buffer = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex++), iBuilder->getInt32(0)});
     345
     346    const unsigned blockShift = shiftAmount % mBitBlockWidth;
     347    const unsigned entries = ceil_udiv(shiftAmount, mBitBlockWidth);
     348
     349    if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {
     350        Value * const summaryPtr = iBuilder->CreateGEP(buffer, iBuilder->getInt32(0));
     351        assert (summaryPtr->getType()->getPointerElementType() == mBitBlockType);
     352        Value * carry = iBuilder->CreateZExtOrBitCast(iBuilder->bitblock_any(value), streamVectorTy);
     353        const auto limit = ceil_udiv(shiftAmount, std::pow(mBitBlockWidth, 2));
     354        assert (limit == summaryPtr->getType()->getPointerElementType()->getArrayNumElements());
     355        for (unsigned i = 0;;++i) {
     356            Value * ptr = iBuilder->CreateGEP(summaryPtr, iBuilder->getInt32(i));
     357            Value * prior = iBuilder->CreateBitCast(iBuilder->CreateBlockAlignedLoad(ptr), streamVectorTy);
     358            Value * stream = iBuilder->CreateOr(iBuilder->CreateShl(prior, 1), carry);
     359            if (LLVM_LIKELY(i == limit)) {
     360                stream = iBuilder->CreateAnd(stream, iBuilder->bitblock_mask_from(iBuilder->getInt32(entries % mBitBlockWidth)));
     361                addToSummary(stream);
     362                iBuilder->CreateBlockAlignedStore(stream, ptr);               
     363                buffer = iBuilder->CreateGEP(buffer, iBuilder->getInt32(1));
     364                break;
     365            }
     366            addToSummary(stream);
     367            iBuilder->CreateBlockAlignedStore(stream, ptr);
     368            carry = iBuilder->CreateLShr(prior, mBitBlockWidth - 1);
     369        }
     370    }
     371    assert (buffer->getType()->getPointerElementType() == mBitBlockType);
     372
     373    // Create a mask to implement circular buffer indexing
     374    Value * indexMask = ConstantInt::get(iBuilder->getSizeTy(), nearest_pow2(entries) - 1);
     375    Value * blockIndex = mKernel->getScalarField(mSelf, blockNoScalar);
     376    Value * carryIndex0 = iBuilder->CreateSub(blockIndex, iBuilder->getSize(entries));
     377    Value * loadIndex0 = iBuilder->CreateAnd(carryIndex0, indexMask);
     378    Value * storeIndex = iBuilder->CreateAnd(blockIndex, indexMask);
     379    Value * carryIn = iBuilder->CreateBlockAlignedLoad(iBuilder->CreateGEP(buffer, loadIndex0));
     380    assert (carryIn->getType() == mBitBlockType);
     381    // If the long advance is an exact multiple of mBitBlockWidth, we simply return the oldest
    157382    // block in the long advance carry data area. 
    158     if (block_shift == 0) {
    159         iBuilder->CreateBlockAlignedStore(value, iBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex));
    160         return carry_block0;
     383    if (blockShift == 0) {
     384        iBuilder->CreateBlockAlignedStore(value, iBuilder->CreateGEP(buffer, storeIndex));
     385        return carryIn;
    161386    }
    162387    // Otherwise we need to combine data from the two oldest blocks.
    163     Value * loadIndex1 = iBuilder->CreateAdd(iBuilder->CreateAnd(iBuilder->CreateSub(blockIndex, ConstantInt::get(iBuilder->getSizeTy(), advanceEntries-1)), indexMask), advBaseIndex);
    164     Value * carry_block1 = iBuilder->CreateBlockAlignedLoad(iBuilder->CreateGEP(mCarryBitBlockPtr, loadIndex1));
    165     Value* block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carry_block0, iBuilder->getIntNTy(mBitBlockWidth)), mBitBlockWidth - block_shift);
    166     Value* block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(carry_block1, iBuilder->getIntNTy(mBitBlockWidth)), block_shift);
    167     iBuilder->CreateBlockAlignedStore(value, iBuilder->CreateGEP(mCarryBitBlockPtr, storeIndex));
     388    Value * carryIndex1 = iBuilder->CreateSub(blockIndex, iBuilder->getSize(entries - 1));
     389    Value * loadIndex1 = iBuilder->CreateAnd(carryIndex1, indexMask);
     390    Value * carry_block1 = iBuilder->CreateBlockAlignedLoad(iBuilder->CreateGEP(buffer, loadIndex1));
     391    Value * block0_shr = iBuilder->CreateLShr(iBuilder->CreateBitCast(carryIn, streamVectorTy), mBitBlockWidth - blockShift);
     392    Value * block1_shl = iBuilder->CreateShl(iBuilder->CreateBitCast(carry_block1, streamVectorTy), blockShift);
     393    iBuilder->CreateBlockAlignedStore(value, iBuilder->CreateGEP(buffer, storeIndex));
    168394    return iBuilder->CreateBitCast(iBuilder->CreateOr(block1_shl, block0_shr), mBitBlockType);
    169395}
    170396
    171397/** ------------------------------------------------------------------------------------------------------------- *
    172  * @brief generateSummaryTest
    173  ** ------------------------------------------------------------------------------------------------------------- */
    174 Value * CarryManager::generateSummaryTest(Value * condition) {
    175     if (mCarryInfo->hasCarries()) {
    176         Value * summary_pack = getCarryPack(summaryPack());
    177         condition = iBuilder->simd_or(condition, summary_pack);
    178     }
    179     return iBuilder->bitblock_any(condition);
    180 }
    181 
    182 /** ------------------------------------------------------------------------------------------------------------- *
    183  * @brief storeCarryOutSummary
    184  ** ------------------------------------------------------------------------------------------------------------- */
    185 void CarryManager::storeCarryOutSummary() {
    186     if (LLVM_LIKELY(mCarryInfo->explicitSummaryRequired())) {
    187         const unsigned carrySummaryIndex = summaryPack();
    188         if (LLVM_UNLIKELY(mCarryInfo->hasLongAdvances())) { // Force if entry
    189             assert (carrySummaryIndex < mCarryOutPack.size());
    190             mCarryOutPack[carrySummaryIndex] = Constant::getAllOnesValue(mCarryPackType);
    191         }
    192         storeCarryOut(carrySummaryIndex);
    193     }
    194 }
    195 
    196 /** ------------------------------------------------------------------------------------------------------------- *
    197  * @brief addOuterSummaryToNestedSummary
    198  ** ------------------------------------------------------------------------------------------------------------- */
    199 void CarryManager::addOuterSummaryToNestedSummary() {
    200     if (LLVM_LIKELY(mCarrySummary.size() > 0)) {
    201         addToSummary(mCarrySummary.back());
    202     }
    203 }
    204 
    205 /** ------------------------------------------------------------------------------------------------------------- *
    206  * @brief buildCarryDataPhisAfterIfBody
    207  ** ------------------------------------------------------------------------------------------------------------- */
    208 void CarryManager::buildCarryDataPhisAfterIfBody(BasicBlock * const entry, BasicBlock * const end) {
    209     if (mCarryInfo->getWhileDepth() > 0) {
    210         // We need to phi out everything for the while carry accumulation process.
    211         const unsigned scopeBaseOffset = scopeBasePack();
    212         const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
    213         for (unsigned i = scopeBaseOffset; i < scopeBaseOffset + scopeCarryPacks; ++i) {
    214             assert (i < mCarryOutPack.size());
    215             Type * const type = mCarryOutPack[i]->getType();
    216             PHINode * phi = iBuilder->CreatePHI(type, 2);
    217             phi->addIncoming(Constant::getNullValue(type), entry);
    218             phi->addIncoming(mCarryOutPack[i], end);
    219             mCarryOutPack[i] = phi;
    220         }
    221     }
    222     if (LLVM_LIKELY(mCarrySummary.size() > 0)) {
    223         const unsigned summaryIndex = summaryPack();
    224         assert (summaryIndex < mCarryOutPack.size());
    225         Value * carrySummary = mCarryOutPack[summaryIndex];
    226         if (mCarrySummary.back() != carrySummary) {
    227             Value * outerCarrySummary = mCarrySummary.back();
    228             Value * nestedCarrySummary = mCarryOutPack[summaryIndex];
    229             assert (outerCarrySummary->getType() == nestedCarrySummary->getType());
    230             PHINode * const phi = iBuilder->CreatePHI(outerCarrySummary->getType(), 2, "summary");
    231             phi->addIncoming(outerCarrySummary, entry);
    232             phi->addIncoming(nestedCarrySummary, end);
    233             mCarryOutPack[summaryIndex] = phi;
    234         }
    235     }
    236 }
    237 
    238 /** ------------------------------------------------------------------------------------------------------------- *
    239  * @brief initializeWhileEntryCarryDataPhis
    240  ** ------------------------------------------------------------------------------------------------------------- */
    241 void CarryManager::initializeWhileEntryCarryDataPhis(BasicBlock * const end) {
    242     const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
    243     mCarryOutAccumPhis.resize(scopeCarryPacks);
    244     #ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
    245     const unsigned currentScopeBase = scopeBasePack();
    246     mCarryInPhis.resize(scopeCarryPacks);
    247     #endif
    248     for (unsigned index = 0; index < scopeCarryPacks; ++index) {
    249         #ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
    250         PHINode * phi_in = iBuilder->CreatePHI(mCarryPackType, 2);
    251         phi_in->addIncoming(mCarryInPack[currentScopeBase+index], whileEntryBlock);
    252         mCarryInPhis[index] = phi_in;
    253         #endif
    254         PHINode * phi_out = iBuilder->CreatePHI(mCarryPackType, 2);
    255         phi_out->addIncoming(Constant::getNullValue(mCarryPackType), end);
    256         assert (index < mCarryOutAccumPhis.size());
    257         mCarryOutAccumPhis[index] = phi_out;
    258     }
    259 }
    260 
    261 /** ------------------------------------------------------------------------------------------------------------- *
    262  * @brief finalizeWhileBlockCarryDataPhis
    263  ** ------------------------------------------------------------------------------------------------------------- */
    264 void CarryManager::finalizeWhileBlockCarryDataPhis(BasicBlock * const end) {
    265     const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
    266     const unsigned currentScopeBase = scopeBasePack();
    267     for (unsigned index = 0; index < scopeCarryPacks; ++index) {
    268         #ifdef SET_WHILE_CARRY_IN_TO_ZERO_AFTER_FIRST_ITERATION
    269         mCarryInPhis[index]->addIncoming(Constant::getNullValue(mCarryPackType), whileBodyFinalBlock);
    270         #endif
    271         assert (index < mCarryOutAccumPhis.size());
    272         PHINode * phi = mCarryOutAccumPhis[index];
    273         Value * carryOut = iBuilder->CreateOr(phi, mCarryOutPack[currentScopeBase + index]);
    274         phi->addIncoming(carryOut, end);
    275         mCarryOutPack[currentScopeBase + index] = carryOut;
    276     }
    277 }
    278 
    279 /** ------------------------------------------------------------------------------------------------------------- *
    280  * @brief ensureCarriesLoadedRecursive
    281  ** ------------------------------------------------------------------------------------------------------------- */
    282 void CarryManager::ensureCarriesLoadedRecursive() {
    283     const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
    284     const unsigned currentScopeBase = scopeBasePack();
    285     if (mCarryInfo->getWhileDepth() == 1) {
    286         for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
    287             getCarryPack(i);
    288         }
    289     }
    290 }
    291 
    292 /** ------------------------------------------------------------------------------------------------------------- *
    293  * @brief ensureCarriesStoredRecursive
    294  ** ------------------------------------------------------------------------------------------------------------- */
    295 void CarryManager::ensureCarriesStoredRecursive() {
    296     const unsigned scopeCarryPacks = mCarryInfo->getScopeCarryPackCount();
    297     const unsigned currentScopeBase = scopeBasePack();
    298     if (mCarryInfo->getWhileDepth() == 1) {
    299         for (auto i = currentScopeBase; i < currentScopeBase + scopeCarryPacks; ++i) {
    300             storeCarryOut(i);
    301         }
    302     }
    303 }
    304 
    305 /** ------------------------------------------------------------------------------------------------------------- *
    306  * @brief getCarryIn
    307  ** ------------------------------------------------------------------------------------------------------------- */
    308 Value * CarryManager::getCarryIn(const unsigned localIndex) {
    309     return getCarryPack(addPosition(localIndex));
    310 }
    311 
    312 /** ------------------------------------------------------------------------------------------------------------- *
    313  * @brief setCarryOut
    314  ** ------------------------------------------------------------------------------------------------------------- */
    315 void CarryManager::setCarryOut(const unsigned localIndex, Value * carryOut) {
    316     const unsigned index = addPosition(localIndex);
    317     assert (index < mCarryOutPack.size());
    318     mCarryOutPack[index] = carryOut;
    319     if (LLVM_LIKELY(hasSummary())) {
     398 * @brief getNextCarryIn
     399 ** ------------------------------------------------------------------------------------------------------------- */
     400Value * CarryManager::getNextCarryIn() {
     401    assert (mCurrentFrameIndex < mCurrentFrame->getType()->getPointerElementType()->getStructNumElements());
     402    Value * carryInPtr = iBuilder->CreateGEP(mCurrentFrame, {iBuilder->getInt32(0), iBuilder->getInt32(mCurrentFrameIndex++)});
     403    mCarryPackPtr = carryInPtr;
     404    if (mLoopDepth > 0) {
     405        carryInPtr = iBuilder->CreateGEP(carryInPtr, {iBuilder->getInt32(0), mLoopSelector});
     406    }
     407    assert (carryInPtr->getType()->getPointerElementType() == mCarryPackType);
     408    return iBuilder->CreateBlockAlignedLoad(carryInPtr);
     409}
     410
     411/** ------------------------------------------------------------------------------------------------------------- *
     412 * @brief setNextCarryOut
     413 ** ------------------------------------------------------------------------------------------------------------- */
     414void CarryManager::setNextCarryOut(Value * carryOut) {
     415    if (LLVM_LIKELY(mCarryInfo->hasExplicitSummary())) {       
    320416        addToSummary(carryOut);
    321417    }
    322     if (mCarryInfo->getWhileDepth() == 0) {
    323         storeCarryOut(index);
    324     }
     418    Value * carryOutPtr = mCarryPackPtr;
     419    if (mLoopDepth > 0) {
     420        Value * selector = iBuilder->CreateXor(mLoopSelector, ConstantInt::get(mLoopSelector->getType(), 1));
     421        carryOutPtr = iBuilder->CreateGEP(mCarryPackPtr, {iBuilder->getInt32(0), selector});
     422    }
     423    carryOut = iBuilder->CreateBitCast(carryOut, mCarryPackType);
     424    if (inCollapsingCarryMode()) {
     425        Value * accum = iBuilder->CreateBlockAlignedLoad(carryOutPtr);
     426        carryOut = iBuilder->CreateOr(carryOut, accum);
     427    }
     428    assert (carryOutPtr->getType()->getPointerElementType() == mCarryPackType);
     429    iBuilder->CreateBlockAlignedStore(carryOut, carryOutPtr);
     430}
     431
     432/** ------------------------------------------------------------------------------------------------------------- *
     433 * @brief addToSummary
     434 ** ------------------------------------------------------------------------------------------------------------- */
     435void CarryManager::addToSummary(Value * value) { assert (value);
     436    assert (mIfDepth > 0 && mCarrySummary.size() > 0);
     437    Value * const summary = mCarrySummary.back(); assert (summary);
     438    if (LLVM_UNLIKELY(summary == value)) {
     439        return;  //Nothing to add.
     440    }
     441    value = iBuilder->CreateBitCast(value, mCarryPackType);
     442    if (LLVM_UNLIKELY(isa<Constant>(value))) {
     443        if (LLVM_UNLIKELY(cast<Constant>(value)->isZeroValue())) {
     444            return;
     445        } else if (LLVM_UNLIKELY(cast<Constant>(value)->isAllOnesValue())) {
     446            mCarrySummary.back() = value;
     447            return;
     448        }
     449    } else if (LLVM_UNLIKELY(isa<Constant>(summary))) {
     450        if (LLVM_UNLIKELY(cast<Constant>(summary)->isZeroValue())) {
     451            mCarrySummary.back() = value;
     452            return;
     453        } else if (LLVM_UNLIKELY(cast<Constant>(summary)->isAllOnesValue())) {
     454            return;
     455        }
     456    }   
     457    mCarrySummary.back() = iBuilder->CreateOr(summary, value);
     458}
     459
     460/** ------------------------------------------------------------------------------------------------------------- *
     461 * @brief collapsingCarryMode
     462 ** ------------------------------------------------------------------------------------------------------------- */
     463bool CarryManager::inCollapsingCarryMode() const {
     464    return (mCurrentScope->getBranch() && isa<While>(mCurrentScope->getBranch()) && !mCarryInfo->variableLength);
    325465}
    326466
     
    328468 * @brief enumerate
    329469 ** ------------------------------------------------------------------------------------------------------------- */
    330 unsigned CarryManager::enumerate(PabloBlock * blk, unsigned ifDepth, unsigned whileDepth) {
    331     unsigned idx = blk->getScopeIndex();
    332     CarryData * cd = new CarryData(blk, mBitBlockWidth, 1, mBitBlockWidth);
    333     mCarryInfoVector[idx] = cd;
    334 
    335     cd->setIfDepth(ifDepth);
    336     cd->setWhileDepth(whileDepth);
    337     unsigned nestedOffset = cd->nested.frameOffset;
    338 
    339     for (Statement * stmt : *blk) {
    340         if (If * ifStatement = dyn_cast<If>(stmt)) {
    341             const unsigned ifCarryDataBits = enumerate(ifStatement->getBody(), ifDepth + 1, whileDepth);
    342             CarryData * nestedBlockData = mCarryInfoVector[ifStatement->getBody()->getScopeIndex()];
    343             if (1 == mBitBlockWidth) {  // PACKING
    344                 if (cd->roomInFinalPack(nestedOffset) < ifCarryDataBits) {
    345                     nestedOffset = alignCeiling(nestedOffset, mBitBlockWidth);
     470unsigned CarryManager::enumerate(PabloBlock * const scope, unsigned index) {
     471    scope->setScopeIndex(index++);
     472    for (Statement * stmt : *scope) {
     473        if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     474            index = enumerate(cast<Branch>(stmt)->getBody(), index);
     475        }
     476    }
     477    return index;
     478}
     479
     480/** ------------------------------------------------------------------------------------------------------------- *
     481 * @brief requiresVariableLengthMode
     482 ** ------------------------------------------------------------------------------------------------------------- */
     483bool CarryManager::requiresVariableLengthMode(const PabloBlock * const scope) {
     484    if (const Branch * const br = scope->getBranch()) {
     485        for (const Var * var : br->getEscaped()) {
     486            for (const PabloAST * user : var->users()) {
     487                if (const Extract * e = dyn_cast<Extract>(user)) {
     488                    if (LLVM_UNLIKELY(e->getIndex() == var)) {
     489                        // If we assign this Var a value and read the value as the index parameter
     490                        // of a nested Extract statement, then we cannot collapse the carries.
     491                        const PabloBlock * parent = e->getParent();
     492                        for (;;) {
     493                            if (parent == scope) {
     494                                return true;
     495                            }
     496                            parent = parent->getPredecessor();
     497                            if (parent == nullptr) {
     498                                break;
     499                            }
     500                        }
     501                    }
    346502                }
    347503            }
    348             nestedBlockData->setFramePosition(nestedOffset);
    349             nestedOffset += ifCarryDataBits;
    350             if (cd->maxNestingDepth <= nestedBlockData->maxNestingDepth) {
    351                 cd->maxNestingDepth = nestedBlockData->maxNestingDepth + 1;
     504        }
     505    }
     506    return false;
     507}
     508
     509/** ------------------------------------------------------------------------------------------------------------- *
     510 * @brief analyse
     511 ** ------------------------------------------------------------------------------------------------------------- */
     512StructType * CarryManager::analyse(PabloBlock * const scope, const unsigned ifDepth, const unsigned loopDepth) {
     513
     514    std::vector<Type *> state;
     515
     516    assert (mCarryPackType);
     517
     518    Type * const carryPackType = (loopDepth == 0) ? mCarryPackType : ArrayType::get(mCarryPackType, 2);
     519
     520    bool hasLongAdvances = false;
     521    for (Statement * stmt : *scope) {
     522        if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
     523            const auto amount = cast<Advance>(stmt)->getAmount();
     524            if (LLVM_LIKELY(amount <= mBitBlockWidth)) {
     525                state.push_back(carryPackType);
     526            } else {
     527                const auto blocks = ceil_udiv(amount, mBitBlockWidth); assert (blocks > 1);
     528                Type * type = ArrayType::get(mBitBlockType, nearest_pow2(blocks));
     529                if (LLVM_UNLIKELY(ifDepth > 0)) {
     530                    Type * carryType = ArrayType::get(mBitBlockType, ceil_udiv(amount, std::pow(mBitBlockWidth, 2)));
     531                    type = StructType::get(carryType, type, nullptr);
     532                    hasLongAdvances = true;
     533                }
     534                state.push_back(type);
    352535            }
    353             cd->nested.entries++;
    354         } else if (While * whileStatement = dyn_cast<While>(stmt)) {
    355             const unsigned whileCarryDataBits = enumerate(whileStatement->getBody(), ifDepth, whileDepth + 1);
    356             CarryData * const nestedBlockData = mCarryInfoVector[whileStatement->getBody()->getScopeIndex()];
    357             if (1 == mBitBlockWidth) {  // PACKING
    358                 if (cd->roomInFinalPack(nestedOffset) < whileCarryDataBits) {
    359                     nestedOffset = alignCeiling(nestedOffset, mBitBlockWidth);
     536        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt) || isa<MatchStar>(stmt))) {
     537            state.push_back(carryPackType);
     538        } else if (LLVM_UNLIKELY(isa<If>(stmt))) {
     539            state.push_back(analyse(cast<If>(stmt)->getBody(), ifDepth + 1, loopDepth));
     540        } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
     541            state.push_back(analyse(cast<While>(stmt)->getBody(), ifDepth, loopDepth + 1));
     542        }
     543    }
     544
     545    assert (scope->getScopeIndex() < mCarryMetadata.size());
     546
     547    CarryData & cd = mCarryMetadata[scope->getScopeIndex()];
     548
     549    StructType * carryState = nullptr;
     550
     551    // Add the summary pack if needed.
     552    cd.summaryType = CarryData::NoSummary;
     553    if (LLVM_UNLIKELY(state.empty())) {
     554        carryState = StructType::get(iBuilder->getContext());
     555    } else {
     556        cd.variableLength = loopDepth > 0 && requiresVariableLengthMode(scope);
     557        if (ifDepth > 0) {
     558            // A non-collapsing loop requires a unique summary for each iteration. Thus whenever
     559            // we have a non-collapsing While within an If scope with an implicit summary, the If
     560            // scope requires an explicit summary.
     561
     562            if (LLVM_LIKELY(state.size() > 1 || hasLongAdvances)) {
     563                cd.summaryType = CarryData::ExplicitSummary;
     564                state.insert(state.begin(), mCarryPackType);
     565            } else {
     566                cd.summaryType = CarryData::ImplicitSummary;
     567                if (state[0]->isStructTy()) {
     568                    cd.summaryType = CarryData::BorrowedSummary;
    360569                }
    361570            }
    362             nestedBlockData->setFramePosition(nestedOffset);
    363             nestedOffset += whileCarryDataBits;
    364             if (cd->maxNestingDepth <= nestedBlockData->maxNestingDepth) {
    365                 cd->maxNestingDepth = nestedBlockData->maxNestingDepth + 1;
    366             }
    367             cd->nested.entries++;
    368         }
    369     }
    370 
    371     cd->scopeCarryDataSize = nestedOffset;
    372 
    373     if (cd->explicitSummaryRequired()) {
    374         // Need extra space for the summary variable, always the last
    375         // entry within an if block.
    376         if (1 == mBitBlockWidth) {  // PACKING
    377             cd->scopeCarryDataSize = alignCeiling(cd->scopeCarryDataSize, mBitBlockWidth);
    378         }
    379         cd->summary.frameOffset = cd->scopeCarryDataSize;
    380         cd->scopeCarryDataSize += 1;  //  computed summary is a full pack.
    381     } else {
    382         cd->summary.frameOffset = 0;
    383     }
    384 
    385     return cd->scopeCarryDataSize;
    386 }
    387 
    388 /** ------------------------------------------------------------------------------------------------------------- *
    389  * @brief addToSummary
    390  ** ------------------------------------------------------------------------------------------------------------- */
    391 void CarryManager::addToSummary(Value * const value) {
    392     const unsigned summaryIndex = summaryPack();
    393     assert (summaryIndex < mCarryInPack.size());
    394     Value * summary = mCarryOutPack[summaryIndex];
    395     assert (summary);
    396     assert (value);
    397     if (LLVM_UNLIKELY(summary == value)) return;  //Nothing to add.
    398    
    399     Type * summaryTy = summary->getType();
    400     Type * valueTy = value->getType();
    401 
    402     if (LLVM_UNLIKELY(isa<Constant>(value))) {
    403         if (LLVM_LIKELY(cast<Constant>(value)->isZeroValue())) return;
    404         if (cast<Constant>(value)->isAllOnesValue()) {
    405             mCarryOutPack[summaryIndex] = Constant::getAllOnesValue(summaryTy);
    406             return;
    407         }
    408     }
    409 
    410     Value * v = value;
    411     if (valueTy != summaryTy) {
    412         // valueTy must be an integer type.
    413         unsigned summaryWidth = summaryTy->isIntegerTy() ? summaryTy->getIntegerBitWidth() : cast<VectorType>(summaryTy)->getBitWidth();       
    414         if (valueTy->getIntegerBitWidth() != summaryWidth) {
    415             v = iBuilder->CreateZExt(v, iBuilder->getIntNTy(summaryWidth));
    416         }
    417         if (!(summaryTy->isIntegerTy())) {
    418             v = iBuilder->CreateBitCast(v, summaryTy);
    419         }
    420     }
    421     if (LLVM_UNLIKELY(isa<Constant>(summary))) {
    422         if (LLVM_LIKELY(cast<Constant>(summary)->isZeroValue())) {
    423             mCarryOutPack[summaryIndex] = v;
    424             return;
    425         } else if (cast<Constant>(summary)->isAllOnesValue()) {
    426             return;
    427         }
    428     }
    429     mCarryOutPack[summaryIndex] = iBuilder->CreateOr(summary, v, "summary");
    430 }
    431 
    432 /** ------------------------------------------------------------------------------------------------------------- *
    433  * @brief getCarryPack
    434  ** ------------------------------------------------------------------------------------------------------------- */
    435 Value * CarryManager::getCarryPack(const unsigned packIndex) {
    436     assert (packIndex < mCarryInPack.size());
    437     if (mCarryInPack[packIndex] == nullptr) {
    438         Value * const packPtr = iBuilder->CreateGEP(mCarryPackBasePtr, ConstantInt::get(iBuilder->getSizeTy(), packIndex));
    439         assert (packIndex < mCarryPackPtr.size());
    440         mCarryPackPtr[packIndex] = packPtr;
    441         mCarryInPack[packIndex] = iBuilder->CreateBlockAlignedLoad(packPtr);
    442     }
    443     return mCarryInPack[packIndex];
    444 }
    445 
    446 /** ------------------------------------------------------------------------------------------------------------- *
    447  * @brief storeCarryOut
    448  ** ------------------------------------------------------------------------------------------------------------- */
    449 void CarryManager::storeCarryOut(const unsigned packIndex) {
    450     assert (packIndex < mCarryOutPack.size());
    451     assert (mCarryOutPack[packIndex]);
    452     assert (packIndex < mCarryPackPtr.size());
    453     Value * const ptr = mCarryPackPtr[packIndex];
    454     assert (ptr);
    455     assert (cast<PointerType>(ptr->getType())->getElementType() == mBitBlockType);
    456     Value * const value = iBuilder->CreateBitCast(mCarryOutPack[packIndex], mBitBlockType);
    457     iBuilder->CreateBlockAlignedStore(value, ptr);
    458 }
    459 
    460 /* Helper routines */
    461 
    462 inline unsigned CarryManager::relativeFrameOffset(const unsigned frameOffset, const unsigned index) const {
    463     return mCurrentFrameIndex + frameOffset + index;
    464 }
    465 
    466 inline unsigned CarryManager::addPosition(const unsigned localIndex) const {
    467     assert (mCarryInfo);
    468     return relativeFrameOffset(mCarryInfo->addWithCarry.frameOffset, localIndex);
    469 }
    470 
    471 inline unsigned CarryManager::unitAdvancePosition(const unsigned localIndex) const {
    472     assert (mCarryInfo);
    473     return relativeFrameOffset(mCarryInfo->unitAdvance.frameOffset, localIndex);
    474 }
    475 
    476 inline unsigned CarryManager::shortAdvancePosition(const unsigned localIndex) const {
    477     assert (mCarryInfo);
    478     return relativeFrameOffset(mCarryInfo->shortAdvance.frameOffset, localIndex);
    479 }
    480 
    481 inline unsigned CarryManager::longAdvancePosition(const unsigned localIndex) const {
    482     assert (mCarryInfo);
    483     return (mCurrentFrameIndex + mCarryInfo->longAdvance.frameOffset) + localIndex;
    484 }
    485 
    486 inline unsigned CarryManager::localBasePack() const {
    487     assert (mCarryInfo);
    488     return (mCurrentFrameIndex + mCarryInfo->shortAdvance.frameOffset);
    489 }
    490 
    491 inline unsigned CarryManager::scopeBasePack() const {
    492     return mCurrentFrameIndex;
    493 }
    494 
    495 inline unsigned CarryManager::summaryPack() const {
    496     assert (mCarryInfo);
    497     return relativeFrameOffset(mCarryInfo->summary.frameOffset, 0);
    498 }
    499 
    500 inline bool CarryManager::hasSummary() const {
    501     assert (mCarryInfo);
    502     return mCarryInfo->explicitSummaryRequired() && !(mCarryInfo->hasLongAdvances());
    503 }
    504 
    505 CarryManager::~CarryManager() {
    506     for (auto * cd : mCarryInfoVector) {
    507         delete cd;
    508     }
    509 }
    510 
    511 }
    512 
     571        }
     572        carryState = StructType::get(iBuilder->getContext(), state);
     573        // If we in a loop and cannot use collapsing carry mode, convert the struct into a capacity and pointer pair.
     574        if (LLVM_UNLIKELY(cd.variableLength)) {
     575            carryState = StructType::get(iBuilder->getSizeTy(), carryState->getPointerTo(), nullptr);
     576        }
     577    }
     578    return carryState;
     579}
     580
     581}
     582
  • icGREP/icgrep-devel/icgrep/pablo/carry_manager.h

    r5217 r5227  
    3636
    3737class CarryManager {
     38
     39    enum { LONG_ADVANCE_BASE = 64 };
     40
    3841public:
    3942 
    40     CarryManager(IDISA::IDISA_Builder * idb)
     43    explicit CarryManager(IDISA::IDISA_Builder * idb) noexcept
    4144    : iBuilder(idb)
    42     , mKernelBuilder(nullptr)
     45    , mKernel(nullptr)
    4346    , mSelf(nullptr)
     47    , mFunction(nullptr)
    4448    , mBitBlockType(idb->getBitBlockType())
    4549    , mBitBlockWidth(idb->getBitBlockWidth())
    46     , mRootScope(nullptr)
     50    , mCurrentFrameIndex(0)
    4751    , mCurrentScope(nullptr)
    4852    , mCarryInfo(nullptr)
    49     , mCurrentFrameIndex(0)
    50     , mCarryPackBasePtr(nullptr)
    51     , mCarryBitBlockPtr(nullptr)
    52     , mTotalCarryDataBitBlocks(0)
    53     , mCarryDataAllocationSize(0)
    54     , mFilePosIdx(2)
    55     {
     53    , mCarryPackType(mBitBlockType)
     54    , mCarryPackPtr(nullptr)
     55    , mIfDepth(0)
     56    , mLoopDepth(0) {
    5657
    5758    }
    5859
    59     ~CarryManager();
     60    ~CarryManager() {
     61
     62    }
     63
     64    void initializeCarryData(PabloKernel * const kernel);
     65
     66    void initializeCodeGen(Value * const self, Function *function);
     67
     68    /* Entering and leaving loops. */
     69
     70    void enterLoopScope(PabloBlock * const scope);
     71
     72    void enterLoopBody(BasicBlock * const entryBlock);
     73
     74    void leaveLoopBody(BasicBlock * const exitBlock);
     75
     76    void leaveLoopScope(BasicBlock * const entryBlock, BasicBlock * const exitBlock);
     77
     78    /* Entering and leaving ifs. */
     79
     80    void enterIfScope(PabloBlock * const scope);
     81
     82    void enterIfBody(BasicBlock * const entryBlock);
     83
     84    void leaveIfBody(BasicBlock * const exitBlock);
     85
     86    void leaveIfScope(BasicBlock * const entryBlock, BasicBlock * const exitBlock);
     87
     88    /* Methods for processing individual carry-generating operations. */
    6089   
    61     Type * initializeCarryData(PabloKernel * const kernel);
    62     void initializeCodeGen(PabloKernel * const kernel, Value * selfPtr);
     90    Value * addCarryInCarryOut(const Statement * operation, Value * const e1, Value * const e2);
    6391
    64     void reset();
     92    Value * advanceCarryInCarryOut(const Advance * advance, Value * const strm);
     93 
     94    /* Methods for getting and setting carry summary values for If statements */
     95         
     96    Value * generateSummaryTest(Value * condition);
     97   
     98protected:
    6599
    66     unsigned enumerate(PabloBlock * blk, unsigned ifDepth, unsigned whileDepth);
    67          
     100    static unsigned enumerate(PabloBlock * const scope, unsigned index = 0);
     101    static bool requiresVariableLengthMode(const PabloBlock * const scope);
     102    StructType * analyse(PabloBlock * const scope, const unsigned ifDepth = 0, const unsigned whileDepth = 0);
     103
    68104    /* Entering and leaving scopes. */
    69    
    70105    void enterScope(PabloBlock * const scope);
    71106    void leaveScope();
    72    
    73     /* Methods for processing individual carry-generating operations. */
    74    
    75     Value * addCarryInCarryOut(const unsigned localIndex, Value * const e1, Value * const e2);
    76 
    77     Value * advanceCarryInCarryOut(const unsigned localIndex, const unsigned shiftAmount, Value * const strm);
    78  
    79     /* Methods for getting and setting carry summary values for If statements */
    80    
    81     bool hasCarries() const;
    82        
    83     Value * generateSummaryTest(Value * condition);
    84    
    85     void storeCarryOutSummary();
    86 
    87     void addOuterSummaryToNestedSummary();
    88 
    89     void buildCarryDataPhisAfterIfBody(BasicBlock * const entry, BasicBlock * const end);
    90        
    91     /* Methods for handling while statements */
    92    
    93     void ensureCarriesLoadedRecursive();
    94 
    95     void initializeWhileEntryCarryDataPhis(BasicBlock * const end);
    96 
    97     void finalizeWhileBlockCarryDataPhis(BasicBlock * const end);
    98 
    99     void ensureCarriesStoredRecursive();
    100    
    101     Value * declareCarryDataArray(Module * m);
    102 
    103 protected:
    104 
    105     Value * shortAdvanceCarryInCarryOut(const unsigned index, const unsigned shiftAmount, Value * const value);
    106     Value * longAdvanceCarryInCarryOut(const unsigned index, const unsigned shiftAmount, Value * const value);
    107107
    108108    /* Methods for processing individual carry-generating operations. */
     109    Value * getNextCarryIn();
     110    void setNextCarryOut(Value * const carryOut);
     111    Value * longAdvanceCarryInCarryOut(const unsigned shiftAmount, Value * const value);
    109112
    110     Value * getCarryIn(const unsigned localIndex);
    111     void setCarryOut(const unsigned idx, Value * carryOut);
    112 
    113     /* Helper routines */
    114     Value * getCarryPack(const unsigned packIndex);
    115     void storeCarryOut(const unsigned packIndex);
    116    
     113    /* Summary handling routines */
    117114    void addToSummary(Value * const value);
    118115
    119     bool hasSummary() const;
    120     unsigned relativeFrameOffset(const unsigned frameOffset, const unsigned index) const;
    121     unsigned addPosition(const unsigned localIndex) const;
    122     unsigned unitAdvancePosition(const unsigned localIndex) const;
    123     unsigned shortAdvancePosition(const unsigned localIndex) const;
    124     unsigned longAdvancePosition(const unsigned localIndex) const;
    125     unsigned localBasePack() const;
    126     unsigned scopeBasePack() const;
    127     unsigned summaryPack() const;
     116    bool inCollapsingCarryMode() const;
    128117
    129118private:
    130     IDISA::IDISA_Builder * const iBuilder;
    131     PabloKernel * mKernelBuilder;
    132     Value * mSelf;
    133     Type * const mBitBlockType;
    134     const unsigned mBitBlockWidth;
    135     PabloBlock * mRootScope;
    136     PabloBlock * mCurrentScope;
    137     CarryData * mCarryInfo;
    138     unsigned mCurrentFrameIndex;
    139     Value * mCarryPackBasePtr;
    140     Type * mCarryPackType;
    141     Value * mCarryBitBlockPtr;
    142     unsigned mTotalCarryDataBitBlocks;
    143     unsigned mCarryDataAllocationSize;
    144     std::vector<CarryData *> mCarryInfoVector;
    145     std::vector<Value *> mCarryPackPtr;
    146     std::vector<Value *> mCarryInPack;
    147     std::vector<PHINode *> mCarryInPhis;
    148     std::vector<PHINode *> mCarryOutAccumPhis;
    149     std::vector<Value *> mCarryOutPack;
    150     std::vector<Value *> mCarrySummary;
    151     int mCdArrayIdx;
    152     int mFilePosIdx;
     119
     120    IDISA::IDISA_Builder * const                iBuilder;
     121    PabloKernel *                               mKernel;
     122    Value *                                     mSelf;
     123    Function *                                  mFunction;
     124    Type * const                                mBitBlockType;
     125    const unsigned                              mBitBlockWidth;
     126
     127    Value *                                     mCurrentFrame;
     128    unsigned                                    mCurrentFrameIndex;
     129
     130    PabloBlock *                                mCurrentScope;
     131    CarryData *                                 mCarryInfo;
     132
     133    Type *                                      mCarryPackType;
     134    Value *                                     mCarryPackPtr;
     135
     136    unsigned                                    mIfDepth;
     137
     138    unsigned                                    mLoopDepth;   
     139    Value *                                     mLoopSelector;
     140    std::vector<PHINode *>                      mLoopIndicies;
     141
     142    std::vector<CarryData>                      mCarryMetadata;
     143    std::vector<std::pair<Value *, unsigned>>   mCarryFrame;
     144
     145    std::vector<Value *>                        mCarrySummary;
    153146};
    154 
    155 inline bool CarryManager::hasCarries() const {
    156     return mCarryInfo->hasCarries();
    157 }
    158147
    159148}
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.cpp

    r5217 r5227  
    1212
    1313using StreamType = IDISA::StreamType;
     14
     15inline void printType(const Type * type, raw_string_ostream & out) {
     16    if (auto st = dyn_cast<StreamType>(type)) {
     17        out << "<" << st->getNumElements() << " x s" << st->getFieldWidth() << ">";
     18    } else {
     19        type->print(out);
     20    }
     21}
    1422
    1523namespace pablo {
     
    95103        name = makeName(out.str());
    96104    }
    97     llvm::Type * const type = array->getType();
     105    Type * type = array->getType();
    98106    if (LLVM_LIKELY(isa<StreamType>(type))) {
    99         Type * elementType = cast<StreamType>(type)->getStreamElementType();
    100         return insertAtInsertionPoint(new Extract(array, index, name, elementType));
    101     }
    102     if (LLVM_LIKELY(isa<ArrayType>(type))) {
    103         Type * elementType = cast<ArrayType>(type)->getArrayElementType();
    104         return insertAtInsertionPoint(new Extract(array, index, name, elementType));
    105     }
     107        type = cast<StreamType>(type)->getStreamElementType();
     108    } else if (LLVM_LIKELY(isa<ArrayType>(type))) {
     109        type = cast<ArrayType>(type)->getArrayElementType();
     110    } else {
     111        std::string tmp;
     112        raw_string_ostream out(tmp);
     113        out << "cannot extract element from ";
     114        array->print(out);
     115        out << " : not a StreamType or ArrayType";
     116        throw std::runtime_error(out.str());
     117    }
     118    return insertAtInsertionPoint(new Extract(array, index, name, type));
     119}
     120
     121And * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2, String * name) {
     122    CHECK_SAME_TYPE(expr1, expr2);
     123    if (name == nullptr) {
     124        name = makeName("and");
     125    }
     126    return insertAtInsertionPoint(new And(expr1->getType(), expr1, expr2, name));
     127}
     128
     129And * PabloBlock::createAnd(Type * const type, const unsigned reserved, String * name) {
     130    if (name == nullptr) {
     131        name = makeName("and");
     132    }
     133    return insertAtInsertionPoint(new And(type, reserved, name));
     134}
     135
     136Or * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2, String * name) {
     137    CHECK_SAME_TYPE(expr1, expr2);
     138    if (name == nullptr) {
     139        name = makeName("or");
     140    }
     141    return insertAtInsertionPoint(new Or(expr1->getType(), expr1, expr2, name));
     142}
     143
     144Or * PabloBlock::createOr(Type * const type, const unsigned reserved, String * name) {
     145    if (name == nullptr) {
     146        name = makeName("or");
     147    }
     148    return insertAtInsertionPoint(new Or(type, reserved, name));
     149}
     150
     151Xor * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2, String * name) {
     152    CHECK_SAME_TYPE(expr1, expr2);
     153    if (name == nullptr) {
     154        name = makeName("xor");
     155    }
     156    return insertAtInsertionPoint(new Xor(expr1->getType(), expr1, expr2, name));
     157}
     158
     159Xor * PabloBlock::createXor(Type * const type, const unsigned reserved, String * name) {
     160    if (name == nullptr) {
     161        name = makeName("xor");
     162    }
     163    return insertAtInsertionPoint(new Xor(type, reserved, name));
     164}
     165
     166Add * PabloBlock::createAdd(PabloAST * expr1, PabloAST * expr2) {
     167    CHECK_SAME_TYPE(expr1, expr2);
     168    return new Add(expr1->getType(), expr1, expr2);
     169}
     170
     171Subtract * PabloBlock::createSubtract(PabloAST * expr1, PabloAST * expr2) {
     172    CHECK_SAME_TYPE(expr1, expr2);
     173    return new Subtract(expr1->getType(), expr1, expr2);
     174}
     175
     176LessThan * PabloBlock::createLessThan(PabloAST * expr1, PabloAST * expr2) {
     177    CHECK_SAME_TYPE(expr1, expr2);
     178    return new LessThan(getParent()->getBuilder()->getInt1Ty(), expr1, expr2);
     179}
     180
     181enum class AssignErrorType {
     182    TypeMismatch
     183    , ReadOnlyVar
     184    , NotAVariable
     185};
     186
     187static void reportAssignError(PabloAST * const var, PabloAST * const value, const AssignErrorType type) {
    106188    std::string tmp;
    107189    raw_string_ostream out(tmp);
    108     out << "cannot extract element from ";
    109     array->print(out);
    110     out << " : not a StreamType or ArrayType";
    111     throw std::runtime_error(out.str());
    112 }
    113 
    114 And * PabloBlock::createAnd(PabloAST * expr1, PabloAST * expr2, String * name) {
    115     CHECK_SAME_TYPE(expr1, expr2);
    116     if (name == nullptr) {
    117         name = makeName("and");
    118     }
    119     return insertAtInsertionPoint(new And(expr1->getType(), expr1, expr2, name));
    120 }
    121 
    122 And * PabloBlock::createAnd(Type * const type, const unsigned reserved, String * name) {
    123     if (name == nullptr) {
    124         name = makeName("and");
    125     }
    126     return insertAtInsertionPoint(new And(type, reserved, name));
    127 }
    128 
    129 Or * PabloBlock::createOr(PabloAST * expr1, PabloAST * expr2, String * name) {
    130     CHECK_SAME_TYPE(expr1, expr2);
    131     if (name == nullptr) {
    132         name = makeName("or");
    133     }
    134     return insertAtInsertionPoint(new Or(expr1->getType(), expr1, expr2, name));
    135 }
    136 
    137 Or * PabloBlock::createOr(Type * const type, const unsigned reserved, String * name) {
    138     if (name == nullptr) {
    139         name = makeName("or");
    140     }
    141     return insertAtInsertionPoint(new Or(type, reserved, name));
    142 }
    143 
    144 Xor * PabloBlock::createXor(PabloAST * expr1, PabloAST * expr2, String * name) {
    145     CHECK_SAME_TYPE(expr1, expr2);
    146     if (name == nullptr) {
    147         name = makeName("xor");
    148     }
    149     return insertAtInsertionPoint(new Xor(expr1->getType(), expr1, expr2, name));
    150 }
    151 
    152 Xor * PabloBlock::createXor(Type * const type, const unsigned reserved, String * name) {
    153     if (name == nullptr) {
    154         name = makeName("xor");
    155     }
    156     return insertAtInsertionPoint(new Xor(type, reserved, name));
    157 }
    158 
    159 Add * PabloBlock::createAdd(PabloAST * expr1, PabloAST * expr2, String * name) {
    160     CHECK_SAME_TYPE(expr1, expr2);
    161     if (name == nullptr) {
    162         name = makeName("add");
    163     }
    164     return insertAtInsertionPoint(new Add(expr1->getType(), expr1, expr2, name));
    165 }
    166 
    167 Subtract * PabloBlock::createSubtract(PabloAST * expr1, PabloAST * expr2, String * name) {
    168     CHECK_SAME_TYPE(expr1, expr2);
    169     if (name == nullptr) {
    170         name = makeName("sub");
    171     }
    172     return insertAtInsertionPoint(new Subtract(expr1->getType(), expr1, expr2, name));
     190    out << "Cannot assign ";
     191    value->print(out);
     192    out << " to ";
     193    var->print(out);
     194    out << ": ";
     195    switch (type) {
     196        case AssignErrorType::TypeMismatch:
     197            out << "type mismatch ";
     198            printType(value->getType(), out);
     199            out << " vs. ";
     200            printType(var->getType(), out);
     201            break;
     202        case AssignErrorType::ReadOnlyVar:
     203            var->print(out);
     204            out << " is read only";
     205            break;
     206        case AssignErrorType::NotAVariable:
     207            var->print(out);
     208            out << " is not a variable";
     209            break;
     210    }
     211    llvm::report_fatal_error(out.str());
    173212}
    174213
    175214Assign * PabloBlock::createAssign(PabloAST * const var, PabloAST * const value) {
    176215    CHECK_SAME_TYPE(var, value);
     216
     217    if (LLVM_UNLIKELY(var->getType() != value->getType())) {
     218        reportAssignError(var, value, AssignErrorType::TypeMismatch);
     219    }
     220
     221    PabloAST * test = var;
     222    for (;;) {
     223        if (LLVM_LIKELY(isa<Var>(test))) {
     224            if (LLVM_UNLIKELY(cast<Var>(test)->isReadOnly())) {
     225                reportAssignError(var, value, AssignErrorType::ReadOnlyVar);
     226            }
     227            break;
     228        } else if (isa<Extract>(test)) {
     229            test = cast<Extract>(test)->getArray();
     230        } else {
     231            reportAssignError(var, value, AssignErrorType::NotAVariable);
     232        }
     233    }
     234
    177235    return insertAtInsertionPoint(new Assign(var, value));
    178236}
     
    250308}
    251309
    252 /** ------------------------------------------------------------------------------------------------------------- *
    253  * @brief enumerateScopes
    254  *
    255  * Assign sequential scope indexes, returning the next unassigned index
    256  ** ------------------------------------------------------------------------------------------------------------- */
    257 unsigned PabloBlock::enumerateScopes(unsigned baseScopeIndex) {
    258     mScopeIndex = baseScopeIndex;
    259     unsigned nextScopeIndex = baseScopeIndex + 1;
    260     for (Statement * stmt : *this) {
    261         if (If * ifStatement = dyn_cast<If>(stmt)) {
    262             nextScopeIndex = ifStatement->getBody()->enumerateScopes(nextScopeIndex);
    263         }
    264         else if (While * whileStatement = dyn_cast<While>(stmt)) {
    265             nextScopeIndex = whileStatement->getBody()->enumerateScopes(nextScopeIndex);
    266         }
    267     }
    268     return nextScopeIndex;
    269 }   
    270 
    271 }
     310}
  • icGREP/icgrep-devel/icgrep/pablo/codegenstate.h

    r5217 r5227  
    4545    friend class Branch;
    4646    friend class PabloBuilder;
     47    friend class PabloKernel;
    4748public:
    4849
     
    7677    }
    7778
    78     Advance * createAdvance(PabloAST * expr, PabloAST * shiftAmount, String * const name);
     79    Advance * createAdvance(PabloAST * expr, PabloAST * shiftAmount, String * name);
    7980
    8081    Lookahead * createLookahead(PabloAST * expr, PabloAST * shiftAmount) {
     
    8687    }
    8788
    88     Lookahead * createLookahead(PabloAST * expr, PabloAST * shiftAmount, String * const name);
     89    Lookahead * createLookahead(PabloAST * expr, PabloAST * shiftAmount, String * name);
    8990
    9091    inline Zeroes * createZeroes(Type * const type = nullptr) {
     
    118119    }
    119120
    120     Not * createNot(PabloAST * expr, String * const name);
     121    Not * createNot(PabloAST * expr, String * name);
    121122
    122123    inline Var * createVar(const std::string & name, Type * const type = nullptr) {
     
    140141    }
    141142
    142     InFile * createInFile(PabloAST * expr, String * const name);
     143    InFile * createInFile(PabloAST * expr, String * name);
    143144
    144145    AtEOF * createAtEOF(PabloAST * expr) {
     
    150151    }
    151152
    152     AtEOF * createAtEOF(PabloAST * expr, String * const name);
     153    AtEOF * createAtEOF(PabloAST * expr, String * name);
    153154
    154155    Extract * createExtract(PabloAST * array, const int64_t index) {
     
    168169    }
    169170
    170     Extract * createExtract(PabloAST * array, PabloAST * index, String * const name);
     171    Extract * createExtract(PabloAST * array, PabloAST * index, String * name);
    171172
    172173    Assign * createAssign(PabloAST * const var, PabloAST * const value);
     
    180181    }
    181182
    182     And * createAnd(PabloAST * expr1, PabloAST * expr2, String * const name);
     183    And * createAnd(PabloAST * expr1, PabloAST * expr2, String * name);
    183184
    184185    And * createAnd(Type * const type, const unsigned reserved) {
     
    186187    }
    187188
    188     And * createAnd(Type * const type, const unsigned reserved, String * const name);
     189    And * createAnd(Type * const type, const unsigned reserved, String * name);
    189190
    190191    Or * createOr(PabloAST * expr1, PabloAST * expr2) {
     
    196197    }
    197198
    198     Or * createOr(PabloAST * expr1, PabloAST * expr2, String * const name);
     199    Or * createOr(PabloAST * expr1, PabloAST * expr2, String * name);
    199200
    200201    Or * createOr(Type * const type, const unsigned reserved) {
     
    202203    }
    203204
    204     Or * createOr(Type * const type, const unsigned reserved, String * const name);
     205    Or * createOr(Type * const type, const unsigned reserved, String * name);
    205206
    206207    Xor * createXor(PabloAST * expr1, PabloAST * expr2) {
     
    212213    }
    213214
    214     Xor * createXor(PabloAST * expr1, PabloAST * expr2, String * const name);
     215    Xor * createXor(PabloAST * expr1, PabloAST * expr2, String * name);
    215216
    216217    Xor * createXor(Type * const type, const unsigned reserved) {
     
    218219    }
    219220
    220     Xor * createXor(Type * const type, const unsigned reserved, String * const name);
     221    Xor * createXor(Type * const type, const unsigned reserved, String * name);
    221222
    222223    Sel * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr) {
     
    228229    }
    229230
    230     Sel * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, String * const name);
    231 
    232     Add * createAdd(PabloAST * expr1, PabloAST * expr2) {
    233         return createAdd(expr1, expr2, nullptr);
    234     }
    235 
    236     Add * createAdd(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
    237         return createAdd(expr1, expr2, makeName(prefix));
    238     }
    239 
    240     Add * createAdd(PabloAST * expr1, PabloAST * expr2, String * const name);
    241 
    242     Subtract * createSubtract(PabloAST * expr1, PabloAST * expr2) {
    243         return createSubtract(expr1, expr2, nullptr);
    244     }
    245 
    246     Subtract * createSubtract(PabloAST * expr1, PabloAST * expr2, const std::string & prefix) {
    247         return createSubtract(expr1, expr2, makeName(prefix));
    248     }
    249 
    250     Subtract * createSubtract(PabloAST * expr1, PabloAST * expr2, String * const name);
     231    Sel * createSel(PabloAST * condition, PabloAST * trueExpr, PabloAST * falseExpr, String * name);
     232
     233    Add * createAdd(PabloAST * expr1, PabloAST * expr2);
     234
     235    Subtract * createSubtract(PabloAST * expr1, PabloAST * expr2);
     236
     237    LessThan * createLessThan(PabloAST * expr1, PabloAST * expr2);
    251238
    252239    MatchStar * createMatchStar(PabloAST * marker, PabloAST * charclass) {
     
    258245    }
    259246
    260     MatchStar * createMatchStar(PabloAST * marker, PabloAST * charclass, String * const name);
     247    MatchStar * createMatchStar(PabloAST * marker, PabloAST * charclass, String * name);
    261248
    262249    ScanThru * createScanThru(PabloAST * from, PabloAST * thru) {
     
    268255    }
    269256
    270     ScanThru * createScanThru(PabloAST * from, PabloAST * thru, String * const name);
     257    ScanThru * createScanThru(PabloAST * from, PabloAST * thru, String * name);
    271258
    272259    If * createIf(PabloAST * condition, PabloBlock * body);
    273260
    274261    While * createWhile(PabloAST * condition, PabloBlock * body);
     262
     263    Type * getStreamSetTy(const uint64_t NumElements = 1, const uint64_t FieldWidth = 1) {
     264        return mParent->getStreamSetTy(NumElements, FieldWidth);
     265    }
    275266
    276267    inline PabloBlock * getPredecessor() const {
     
    284275    void insert(Statement * const statement);
    285276
    286     unsigned enumerateScopes(unsigned baseScopeIndex);
    287    
     277    inline void setScopeIndex(const unsigned index) {
     278        mScopeIndex = index;
     279    }
     280
    288281    inline unsigned getScopeIndex() const {
    289282        return mScopeIndex;
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_simplifier.cpp

    r5217 r5227  
    2323 * if no change was made.
    2424 ** ------------------------------------------------------------------------------------------------------------- */
    25 PabloAST * Simplifier::fold(Variadic * var, PabloBlock * const block) {
     25inline PabloAST * Simplifier::fold(Variadic * var, PabloBlock * const block) {
    2626
    2727    assert (var);
     
    263263            return block->createZeroes(stmt->getType());
    264264        }
     265    } else if (isa<Add>(stmt) || isa<Subtract>(stmt)) {
     266       if (LLVM_UNLIKELY(isa<Integer>(stmt->getOperand(0)) && isa<Integer>(stmt->getOperand(1)))) {
     267           const Integer * const int0 = cast<Integer>(stmt->getOperand(0));
     268           const Integer * const int1 = cast<Integer>(stmt->getOperand(1));
     269           Integer::IntTy result = 0;
     270           if (isa<Add>(stmt)) {
     271               result = int0->value() + int1->value();
     272           } else {
     273               result = int0->value() - int1->value();
     274           }
     275           return block->getInteger(result);
     276       }
    265277    } else {
    266278        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     
    372384 ** ------------------------------------------------------------------------------------------------------------- */
    373385void Simplifier::redundancyElimination(PabloBlock * const block, ExpressionTable * const et, VariableTable * const vt) {
    374     ExpressionTable expressions(et);
    375386    VariableTable variables(vt);
    376387
     
    383394        }
    384395    }
     396
     397    ExpressionTable expressions(et);
    385398
    386399    Statement * stmt = block->front();
     
    448461            for (unsigned i = 0; i < stmt->getNumOperands(); ++i) {
    449462                PabloAST * op = stmt->getOperand(i);
    450                 if (isa<Var>(op)) {
     463                if (LLVM_UNLIKELY(isa<Var>(op))) {
    451464                    PabloAST * const value = variables.get(cast<Var>(op));
    452                     if (value) {
     465                    if (value && value != op) {
    453466                        stmt->setOperand(i, value);
    454467                    }
     
    489502        // later mark any Assign statement as dead if the Var is never read.
    490503
     504        /// TODO: this doesn't properly optimize the loop control variable(s) yet.
     505
    491506        const auto escaped = br->getEscaped();
    492507        const auto n = escaped.size();
     
    495510        PabloAST * outgoing[n];
    496511
    497         size_t i = 0;
    498         for (Var * var : escaped) {
     512        for (unsigned i = 0; i < escaped.size(); ++i) {
     513            PabloAST * var = escaped[i];
    499514            incoming[i] = vt->get(var);
    500515            outgoing[i] = variables.get(var);
    501             PabloAST * expr = var;
    502516            if (LLVM_UNLIKELY(incoming[i] == outgoing[i])) {
    503                 expr = incoming[i];
     517                var = incoming[i];
    504518            } else {
    505519                for (size_t j = 0; j != i; ++j) {
    506520                    if ((outgoing[j] == outgoing[i]) && (incoming[j] == incoming[i])) {
    507                         expr = variable[j];
     521                        var = variable[j];
    508522                        break;
    509523                    }
    510524                }
    511525            }
    512             variable[i] = expr;
    513             vt->put(var, expr);
    514             ++i;
     526            variable[i] = var;
     527            vt->put(escaped[i], var);
    515528        }
    516529    }
     
    611624        } else if (LLVM_UNLIKELY(isa<ScanThru>(stmt))) {
    612625            ScanThru * scanThru = cast<ScanThru>(stmt);
    613             if (LLVM_UNLIKELY(isa<Advance>(scanThru->getOperand(0)))) {
     626            if (LLVM_UNLIKELY(isa<Advance>(scanThru->getScanFrom()))) {
    614627                // Replace a ScanThru(Advance(x,n),y) with an ScanThru(Advance(x, n - 1), Advance(x, n - 1) | y), where Advance(x, 0) = x
    615                 Advance * op = cast<Advance>(stmt->getOperand(0));
    616                 if (LLVM_UNLIKELY(op->getNumUses() == 1)) {
     628                Advance * adv = cast<Advance>(scanThru->getScanFrom());
     629                if (LLVM_UNLIKELY(adv->getNumUses() == 1)) {
    617630                    block->setInsertPoint(scanThru->getPrevNode());
    618                     PabloAST * expr = block->createAdvance(op->getOperand(0), block->getInteger(op->getAmount() - 1));
     631                    PabloAST * expr = block->createAdvance(adv->getOperand(0), block->getInteger(adv->getAmount() - 1));
    619632                    scanThru->setOperand(0, expr);
    620633                    scanThru->setOperand(1, block->createOr(scanThru->getOperand(1), expr));
    621                     op->eraseFromParent(false);
    622                 }
    623             } else if (isa<And>(scanThru->getOperand(0))) {
     634                    adv->eraseFromParent(false);
     635                }
     636            } else if (LLVM_UNLIKELY(isa<And>(scanThru->getScanFrom()))) {
    624637                // Suppose B is an arbitrary bitstream and A = Advance(B, 1). ScanThru(B ∧ ¬A, B) will leave a marker on the position
    625638                // following the end of any run of 1-bits in B. But this is equivalent to computing A ∧ ¬B since A will have exactly
     
    631644
    632645            }
    633 
    634 
    635 
    636 
    637646        }
    638647        stmt = stmt->getNextNode();
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.cpp

    r5202 r5227  
    160160        return;
    161161    }     
     162    if (LLVM_UNLIKELY(prior->getType() != value->getType())) {
     163        std::string tmp;
     164        raw_string_ostream out(tmp);
     165        out << "Type mismatch replacing operand ";
     166        prior->print(out);
     167        out << " with ";
     168        value->print(out);
     169        out << " in statement ";
     170        this->print(out);
     171        llvm::report_fatal_error(out.str());
     172    }
    162173    prior->removeUser(this);
    163174    mOperand[index] = value;
  • icGREP/icgrep-devel/icgrep/pablo/pabloAST.h

    r5217 r5227  
    3232    friend class PabloBlock;
    3333    friend class Prototype;
    34     friend class PabloFunction;
    3534    friend class SymbolGenerator;
    3635    friend class Count;
    3736    friend class Var;
     37    friend class Operator;
    3838public:
    3939
     
    6363        , Function
    6464        , Prototype
     65        // Arithmetic expressions
     66        , Add
     67        , Subtract
     68        // Relational expressions
     69        , LessThan
     70        , LessThanEquals
     71        , Equals
     72        , GreaterThanEquals
     73        , GreaterThan
     74        , NotEquals
    6575        /** Statements **/
    6676        // Boolean operations
     
    7989        // Statistics operations
    8090        , Count
    81         // Arithmetic operations
    82         , Add
    83         , Subtract
    8491        // Variable assignments
    8592        , Assign
     
    193200public:
    194201    static inline bool classof(const PabloAST * e) {
    195         switch (e->getClassTypeId()) {
    196             case PabloAST::ClassTypeId::Zeroes:
    197             case PabloAST::ClassTypeId::Ones:
    198             case PabloAST::ClassTypeId::Var:
    199             case PabloAST::ClassTypeId::String:
    200             case PabloAST::ClassTypeId::Integer:
    201             case PabloAST::ClassTypeId::Block:
    202             case PabloAST::ClassTypeId::Function:
    203             case PabloAST::ClassTypeId::Prototype:
    204                 return false;
    205             default:
    206                 return true;
    207         }
     202        return ((unsigned)e->getClassTypeId() >= (unsigned)PabloAST::ClassTypeId::And);
    208203    }
    209204    static inline bool classof(const Statement *) {
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r5217 r5227  
    2323namespace pablo {
    2424
    25 PabloCompiler::PabloCompiler(PabloKernel * kernel)
    26 : iBuilder(kernel->getBuilder())
    27 , mBitBlockType(iBuilder->getBitBlockType())
    28 , mCarryManager(nullptr)
    29 , mKernel(kernel)
    30 , mWhileDepth(0)
    31 , mIfDepth(0)
    32 , mFunction(nullptr)
    33 , mMaxWhileDepth(0) {
     25using TypeId = PabloAST::ClassTypeId;
     26
     27void PabloCompiler::initializeKernelData() {
     28    Examine();
     29    mCarryManager->initializeCarryData(mKernel);
     30}
    3431   
    35 }
    36 
    37 Type * PabloCompiler::initializeKernelData() {
    38     Examine();
    39     mCarryManager = std::unique_ptr<CarryManager>(new CarryManager(iBuilder));
    40     return mCarryManager->initializeCarryData(mKernel);
    41 }
    42    
    43 void PabloCompiler::compile(Value * const self, Function * doBlockFunction) {
     32void PabloCompiler::compile(Value * const self, Function * function) {
    4433
    4534    // Make sure that we generate code into the right module.
    46     mFunction = doBlockFunction;
    4735    mSelf = self;
    48 
    49     #ifdef PRINT_TIMING_INFORMATION
    50     const timestamp_t pablo_compilation_start = read_cycle_counter();
    51     #endif
     36    mFunction = function;
    5237
    5338    //Generate Kernel//
    54     iBuilder->SetInsertPoint(BasicBlock::Create(iBuilder->getContext(), "entry", doBlockFunction, 0));
    55 
    56     mCarryManager->initializeCodeGen(mKernel, mSelf);
     39    iBuilder->SetInsertPoint(BasicBlock::Create(iBuilder->getContext(), "entry", function, 0));
     40
     41    mCarryManager->initializeCodeGen(self, function);
    5742     
    5843    PabloBlock * const entryBlock = mKernel->getEntryBlock(); assert (entryBlock);
     
    9580
    9681inline void PabloCompiler::Examine() {
    97     mWhileDepth = 0;
    98     mIfDepth = 0;
    99     mMaxWhileDepth = 0;
    10082    Examine(mKernel->getEntryBlock());
    10183}
     
    10991                mKernel->setLookAhead(la->getAmount());
    11092            }
    111         } else {
    112             if (LLVM_UNLIKELY(isa<If>(stmt))) {
    113                 Examine(cast<If>(stmt)->getBody());
    114             } else if (LLVM_UNLIKELY(isa<While>(stmt))) {
    115                 mMaxWhileDepth = std::max(mMaxWhileDepth, ++mWhileDepth);
    116                 Examine(cast<While>(stmt)->getBody());
    117                 --mWhileDepth;
    118             }
     93        } else if (LLVM_UNLIKELY(isa<Branch>(stmt))) {
     94            Examine(cast<Branch>(stmt)->getBody());
    11995        }
    12096    }   
     
    155131    //
    156132
    157     Module * const mod = iBuilder->getModule();
    158133    BasicBlock * const ifEntryBlock = iBuilder->GetInsertBlock();
    159     BasicBlock * const ifBodyBlock = BasicBlock::Create(mod->getContext(), "if.body", mFunction, 0);
    160     BasicBlock * const ifEndBlock = BasicBlock::Create(mod->getContext(), "if.end", mFunction, 0);
     134    BasicBlock * const ifBodyBlock = BasicBlock::Create(mFunction->getContext(), "if.body", mFunction);
     135    BasicBlock * const ifEndBlock = BasicBlock::Create(mFunction->getContext(), "if.end", mFunction);
    161136   
    162137    std::vector<std::pair<const Var *, Value *>> incoming;
     
    177152    PabloBlock * ifBody = ifStatement->getBody();
    178153   
    179     Value * const condition = compileExpression(ifStatement->getCondition());
     154    mCarryManager->enterIfScope(ifBody);
     155
     156    Value * condition = compileExpression(ifStatement->getCondition());
     157    if (condition->getType() == iBuilder->getBitBlockType()) {
     158        condition = iBuilder->bitblock_any(mCarryManager->generateSummaryTest(condition));
     159    }
    180160   
    181     mCarryManager->enterScope(ifBody);
    182     iBuilder->CreateCondBr(mCarryManager->generateSummaryTest(condition), ifBodyBlock, ifEndBlock);
     161    iBuilder->CreateCondBr(condition, ifBodyBlock, ifEndBlock);
    183162   
    184163    // Entry processing is complete, now handle the body of the if.
    185164    iBuilder->SetInsertPoint(ifBodyBlock);
    186    
     165
     166    mCarryManager->enterIfBody(ifEntryBlock);
     167
    187168    compileBlock(ifBody);
    188169
    189     BasicBlock * ifExitBlock = iBuilder->GetInsertBlock();
    190 
    191     if (mCarryManager->hasCarries()) {
    192         mCarryManager->storeCarryOutSummary();
    193     }
    194     mCarryManager->addOuterSummaryToNestedSummary();
     170    BasicBlock * ifExitBlock = iBuilder->GetInsertBlock();   
     171
     172    mCarryManager->leaveIfBody(ifExitBlock);
    195173
    196174    iBuilder->CreateBr(ifEndBlock);
    197175    //End Block
    198176    iBuilder->SetInsertPoint(ifEndBlock);
     177
     178    mCarryManager->leaveIfScope(ifEntryBlock, ifExitBlock);
     179
    199180    for (const auto i : incoming) {
    200181        const Var * var; Value * value;
     
    210191        }
    211192
    212         PHINode * phi = iBuilder->CreatePHI(mBitBlockType, 2, getName(var));
     193        Value * const next = f->second;
     194
     195        assert (value->getType() == next->getType());
     196
     197        PHINode * phi = iBuilder->CreatePHI(value->getType(), 2, getName(var));
    213198        phi->addIncoming(value, ifEntryBlock);
    214         phi->addIncoming(f->second, ifExitBlock);
     199        phi->addIncoming(next, ifExitBlock);
    215200        f->second = phi;
    216201
    217202        assert (mMarkerMap[var] == phi);
    218     }
    219     // Create the phi Node for the summary variable, if needed.
    220     mCarryManager->buildCarryDataPhisAfterIfBody(ifEntryBlock, ifExitBlock);
    221     mCarryManager->leaveScope();
     203    }   
    222204}
    223205
     
    228210    BasicBlock * whileEntryBlock = iBuilder->GetInsertBlock();
    229211
    230     Module * const mod = iBuilder->getModule();
    231     BasicBlock * whileBodyBlock = BasicBlock::Create(mod->getContext(), "while.body", mFunction, 0);
    232     BasicBlock * whileEndBlock = BasicBlock::Create(mod->getContext(), "while.end", mFunction, 0);
    233 
    234     mCarryManager->enterScope(whileBody);
    235     mCarryManager->ensureCarriesLoadedRecursive();
     212    BasicBlock * whileBodyBlock = BasicBlock::Create(iBuilder->getContext(), "while.body", mFunction);
     213
     214    BasicBlock * whileEndBlock = BasicBlock::Create(iBuilder->getContext(), "while.end", mFunction);
     215
     216    const auto escaped = whileStatement->getEscaped();
    236217
    237218#ifdef ENABLE_BOUNDED_WHILE
     
    242223    // the loop.
    243224
     225    mCarryManager->enterLoopScope(whileBody);
     226
    244227    iBuilder->CreateBr(whileBodyBlock);
     228
    245229    iBuilder->SetInsertPoint(whileBodyBlock);
    246230
     
    254238#endif
    255239
    256     mCarryManager->initializeWhileEntryCarryDataPhis(whileEntryBlock);
    257 
    258240    std::vector<std::pair<const Var *, PHINode *>> variants;
    259241
    260242    // for any Next nodes in the loop body, initialize to (a) pre-loop value.
    261     for (const auto var : whileStatement->getEscaped()) {       
     243    for (const auto var : escaped) {
    262244        auto f = mMarkerMap.find(var);
    263245        if (LLVM_UNLIKELY(f == mMarkerMap.end())) {
     
    269251            llvm::report_fatal_error(out.str());
    270252        }
    271 
    272         PHINode * phi = iBuilder->CreatePHI(mBitBlockType, 2, getName(var));
    273         phi->addIncoming(f->second, whileEntryBlock);
     253        Value * entryValue = f->second;
     254        PHINode * phi = iBuilder->CreatePHI(entryValue->getType(), 2, getName(var));
     255        phi->addIncoming(entryValue, whileEntryBlock);
    274256        f->second = phi;
    275257        assert(mMarkerMap[var] == phi);
     
    282264    }
    283265#endif
     266
     267    mCarryManager->enterLoopBody(whileEntryBlock);
     268
    284269    //
    285270    // Now compile the loop body proper.  Carry-out accumulated values
    286271    // and iterated values of Next nodes will be computed.
    287     ++mWhileDepth;
    288272    compileBlock(whileBody);
    289273
     
    291275    BasicBlock * whileExitBlock = iBuilder->GetInsertBlock();
    292276
    293     if (mCarryManager->hasCarries()) {
    294         mCarryManager->storeCarryOutSummary();
    295     }
    296     mCarryManager->finalizeWhileBlockCarryDataPhis(whileExitBlock);
     277    mCarryManager->leaveLoopBody(whileExitBlock);
    297278
    298279    // Terminate the while loop body with a conditional branch back.
    299     Value * cond_expr = iBuilder->bitblock_any(compileExpression(whileStatement->getCondition()));
     280    Value * condition = compileExpression(whileStatement->getCondition());
     281    if (condition->getType() == iBuilder->getBitBlockType()) {
     282        condition = iBuilder->bitblock_any(condition);
     283    }
    300284#ifdef ENABLE_BOUNDED_WHILE
    301285    if (whileStatement->getBound()) {
    302286        Value * new_bound = iBuilder->CreateSub(bound_phi, ConstantInt::get(iBuilder->getSizeTy(), 1));
    303287        bound_phi->addIncoming(new_bound, whileExitBlock);
    304         cond_expr = iBuilder->CreateAnd(cond_expr, iBuilder->CreateICmpUGT(new_bound, ConstantInt::getNullValue(iBuilder->getSizeTy())));
    305     }
    306 #endif   
    307     iBuilder->CreateCondBr(cond_expr, whileBodyBlock, whileEndBlock);
     288        condition = iBuilder->CreateAnd(condition, iBuilder->CreateICmpUGT(new_bound, ConstantInt::getNullValue(iBuilder->getSizeTy())));
     289    }
     290#endif
    308291
    309292    // and for any variant nodes in the loop body
     
    319302            llvm::report_fatal_error(out.str());
    320303        }
    321         phi->addIncoming(f->second, whileExitBlock);
     304        Value * exitValue = f->second;
     305        assert (phi->getType() == exitValue->getType());
     306        phi->addIncoming(exitValue, whileExitBlock);
    322307        f->second = phi;
    323308    }
    324309
     310    iBuilder->CreateCondBr(condition, whileBodyBlock, whileEndBlock);
     311
    325312    iBuilder->SetInsertPoint(whileEndBlock);
    326     --mWhileDepth;
    327 
    328     mCarryManager->ensureCarriesStoredRecursive();
    329     mCarryManager->leaveScope();
     313
     314    mCarryManager->leaveLoopScope(whileEntryBlock, whileExitBlock);
     315
    330316}
    331317
     
    359345                    std::string tmp;
    360346                    raw_string_ostream out(tmp);
    361                     out << "Use-before-definition error: ";
     347                    out << "PabloCompiler: use-before-definition error: ";
    362348                    expr->print(out);
    363349                    out << " does not dominate ";
    364350                    stmt->print(out);
    365                     throw std::runtime_error(out.str());
     351                    llvm::report_fatal_error(out.str());
    366352                }
    367353                Value * const ptr = f->second;
     
    374360                    value = iBuilder->CreateAdd(value, count);
    375361                }
    376 
    377 //                cast<PointerType>(ptr->getType())->getElementType()->getPrimitiveSizeInBits() / 8;
    378362
    379363                const Type * const type = value->getType();
     
    392376            Value * index = compileExpression(extract->getIndex());
    393377            value = iBuilder->CreateGEP(array, {ConstantInt::getNullValue(index->getType()), index}, getName(stmt));
    394         } else if (const And * pablo_and = dyn_cast<And>(stmt)) {
    395             value = iBuilder->simd_and(compileExpression(pablo_and->getOperand(0)), compileExpression(pablo_and->getOperand(1)));
    396         } else if (const Or * pablo_or = dyn_cast<Or>(stmt)) {
    397             value = iBuilder->simd_or(compileExpression(pablo_or->getOperand(0)), compileExpression(pablo_or->getOperand(1)));
    398         } else if (const Xor * pablo_xor = dyn_cast<Xor>(stmt)) {
    399             value = iBuilder->simd_xor(compileExpression(pablo_xor->getOperand(0)), compileExpression(pablo_xor->getOperand(1)));
     378        } else if (isa<And>(stmt)) {
     379            value = compileExpression(stmt->getOperand(0));
     380            for (unsigned i = 1; i < stmt->getNumOperands(); ++i) {
     381                value = iBuilder->simd_and(value, compileExpression(stmt->getOperand(1)));
     382            }
     383        } else if (isa<Or>(stmt)) {
     384            value = compileExpression(stmt->getOperand(0));
     385            for (unsigned i = 1; i < stmt->getNumOperands(); ++i) {
     386                value = iBuilder->simd_or(value, compileExpression(stmt->getOperand(1)));
     387            }
     388        } else if (isa<Xor>(stmt)) {
     389            value = compileExpression(stmt->getOperand(0));
     390            for (unsigned i = 1; i < stmt->getNumOperands(); ++i) {
     391                value = iBuilder->simd_xor(value, compileExpression(stmt->getOperand(1)));
     392            }
    400393        } else if (const Sel * sel = dyn_cast<Sel>(stmt)) {
    401394            Value* ifMask = compileExpression(sel->getCondition());
     
    403396            Value* ifFalse = iBuilder->simd_and(iBuilder->simd_not(ifMask), compileExpression(sel->getFalseExpr()));
    404397            value = iBuilder->simd_or(ifTrue, ifFalse);
    405         } else if (const Not * pablo_not = dyn_cast<Not>(stmt)) {
    406             value = iBuilder->simd_not(compileExpression(pablo_not->getExpr()));
    407         } else if (const Advance * adv = dyn_cast<Advance>(stmt)) {
    408             Value * const strm_value = compileExpression(adv->getExpr());
    409             value = mCarryManager->advanceCarryInCarryOut(adv->getLocalIndex(), adv->getAmount(), strm_value);
     398        } else if (isa<Not>(stmt)) {
     399            value = iBuilder->simd_not(compileExpression(stmt->getOperand(0)));
     400        } else if (isa<Advance>(stmt)) {
     401            const Advance * const adv = cast<Advance>(stmt);
     402            // If our expr is an Extract op on a mutable Var then we need to pass the index value to the carry
     403            // manager so that it properly selects the correct carry bit.
     404            value = mCarryManager->advanceCarryInCarryOut(adv, compileExpression(adv->getExpression()));
    410405        } else if (const MatchStar * mstar = dyn_cast<MatchStar>(stmt)) {
    411406            Value * const marker = compileExpression(mstar->getMarker());
    412407            Value * const cc = compileExpression(mstar->getCharClass());
    413408            Value * const marker_and_cc = iBuilder->simd_and(marker, cc);
    414             Value * const sum = mCarryManager->addCarryInCarryOut(mstar->getLocalCarryIndex(), marker_and_cc, cc);
     409            Value * const sum = mCarryManager->addCarryInCarryOut(mstar, marker_and_cc, cc);
    415410            value = iBuilder->simd_or(iBuilder->simd_xor(sum, cc), marker);
    416411        } else if (const ScanThru * sthru = dyn_cast<ScanThru>(stmt)) {
    417             Value * const  marker_expr = compileExpression(sthru->getScanFrom());
    418             Value * const  cc_expr = compileExpression(sthru->getScanThru());
    419             Value * const  sum = mCarryManager->addCarryInCarryOut(sthru->getLocalCarryIndex(), marker_expr, cc_expr);
     412            Value * const marker_expr = compileExpression(sthru->getScanFrom());
     413            Value * const cc_expr = compileExpression(sthru->getScanThru());
     414            Value * const sum = mCarryManager->addCarryInCarryOut(sthru, marker_expr, cc_expr);
    420415            value = iBuilder->simd_and(sum, iBuilder->simd_not(cc_expr));
    421416        } else if (const InFile * e = dyn_cast<InFile>(stmt)) {
     
    473468                    Value * b0 = iBuilder->CreateBitCast(lookAhead, streamType);
    474469                    Value * result = iBuilder->CreateOr(iBuilder->CreateShl(b1, iBuilder->getBitBlockWidth() - bit_shift), iBuilder->CreateLShr(b0, bit_shift));
    475                     value = iBuilder->CreateBitCast(result, mBitBlockType);
     470                    value = iBuilder->CreateBitCast(result, iBuilder->getBitBlockType());
    476471                }
    477472            }
     
    501496    } else if (LLVM_UNLIKELY(isa<Integer>(expr))) {
    502497        return iBuilder->getInt64(cast<Integer>(expr)->value());
     498    } else if (LLVM_UNLIKELY(isa<Operator>(expr))) {
     499        const Operator * op = cast<Operator>(expr);
     500        Value * lh = compileExpression(op->getLH());
     501        Value * rh = compileExpression(op->getRH());
     502        assert (lh->getType() == rh->getType());
     503        switch (op->getClassTypeId()) {
     504            case TypeId::Add:
     505                return iBuilder->CreateAdd(lh, rh);
     506            case TypeId::Subtract:
     507                return iBuilder->CreateSub(lh, rh);
     508            case TypeId::LessThan:
     509                return iBuilder->CreateICmpSLT(lh, rh);
     510            case TypeId::LessThanEquals:
     511                return iBuilder->CreateICmpSLE(lh, rh);
     512            case TypeId::Equals:
     513                return iBuilder->CreateICmpEQ(lh, rh);
     514            case TypeId::GreaterThanEquals:
     515                return iBuilder->CreateICmpSGE(lh, rh);
     516            case TypeId::GreaterThan:
     517                return iBuilder->CreateICmpSGT(lh, rh);
     518            case TypeId::NotEquals:
     519                return iBuilder->CreateICmpNE(lh, rh);
     520            default:
     521                break;
     522        }
     523        std::string tmp;
     524        raw_string_ostream out(tmp);
     525        expr->print(out);
     526        out << " is not a valid Operator";
     527        llvm::report_fatal_error(out.str());
    503528    }
    504529    const auto f = mMarkerMap.find(expr);
     
    517542}
    518543
    519 }
     544PabloCompiler::PabloCompiler(PabloKernel * kernel)
     545: iBuilder(kernel->getBuilder())
     546, mCarryManager(new CarryManager(iBuilder))
     547, mKernel(kernel)
     548, mFunction(nullptr) {
     549
     550}
     551
     552PabloCompiler::~PabloCompiler() {
     553    delete mCarryManager;
     554}
     555
     556}
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.h

    r5217 r5227  
    1212#include <vector>
    1313#include <unordered_map>
    14 #include <pablo/carry_manager.h>
    1514#include <pablo/pablo_kernel.h>
    1615#include <llvm/ADT/Twine.h>
     
    3635class PabloAST;
    3736class PabloBlock;
    38 class PabloFunction;
    3937class String;
    4038class Var;
     
    4341class If;
    4442class While;
     43class CarryManager;
     44class Extract;
    4545
    4646class PabloCompiler {
     47    friend class CarryManager;
     48
    4749    using IntSet = boost::container::flat_set<unsigned>;
    4850    using MarkerMap = std::unordered_map<const PabloAST *, Value *>;
     51
    4952public:
    5053    PabloCompiler(PabloKernel * kernel);
    51     Type * initializeKernelData();
     54    ~PabloCompiler();
     55    void initializeKernelData();
    5256    void compile(Value * const self, Function * doBlockFunction);
    5357
    5458private:
    55 
    56     void verifyParameter(const Var * var, const Value * param);
    5759
    5860    void Examine();
     
    6365    void compileIf(const If * ifStmt);
    6466    void compileWhile(const While * whileStmt);
     67
    6568    Value * compileExpression(const PabloAST * expr, const bool ensureLoaded = true) const;
    66     void GenerateKernel(PabloFunction * const function);
    6769
    68     MarkerMap                           mMarkerMap;
    69     IntSet                              mInputStreamOffset;
    70     IDISA::IDISA_Builder *              iBuilder;
    71     Type* const                         mBitBlockType;
     70private:
    7271
    73     std::unique_ptr<CarryManager>       mCarryManager;
     72    IDISA::IDISA_Builder *  iBuilder;
     73    CarryManager *          mCarryManager;
     74    PabloKernel *           mKernel;
     75    Value *                 mSelf;
     76    Function *              mFunction;
     77    MarkerMap               mMarkerMap;
     78    IntSet                  mInputStreamOffset;
    7479
    75     PabloKernel * const                 mKernel;
    76     Value *                             mSelf;
    77 
    78     unsigned                            mWhileDepth;
    79     unsigned                            mIfDepth;
    80 
    81     llvm::Function *                    mFunction;
    82 
    83     unsigned                            mMaxWhileDepth;
    8480};
    8581
  • icGREP/icgrep-devel/icgrep/pablo/pablo_kernel.cpp

    r5217 r5227  
    55
    66#include <pablo/pablo_kernel.h>
     7#include <pablo/codegenstate.h>
    78#include <pablo/pablo_compiler.h>
    89#include <llvm/Support/Debug.h>
     
    1112#include <IDISA/idisa_builder.h>
    1213#include <pablo/prototype.h>
     14#include <stack>
    1315
    1416using namespace pablo;
     
    1820
    1921Var * PabloKernel::addInput(const std::string name, Type * const type) {
    20     Var * param = new Var(mSymbolTable->make(name), type);
     22    Var * param = new Var(mSymbolTable->make(name), type, true);
    2123    mInputs.push_back(param);
    2224    if (isa<StreamType>(type)) {
    23         Type * const resolvedType = cast<StreamType>(type)->resolveType(iBuilder);
    24         mStreamSetInputs.emplace_back(resolvedType, name);
     25        mStreamSetInputs.emplace_back(type, name);
    2526    } else {
    2627        mScalarInputs.emplace_back(type, name);
     
    3132
    3233Var * PabloKernel::addOutput(const std::string name, Type * const type) {
    33     Var * result = new Var(mSymbolTable->make(name), type);
     34    Var * result = new Var(mSymbolTable->make(name), type, false);
    3435    mOutputs.push_back(result);
    3536    if (isa<StreamType>(type)) {
    36         Type * const resolvedType = cast<StreamType>(type)->resolveType(iBuilder);
    37         mStreamSetOutputs.emplace_back(resolvedType, name);
     37        mStreamSetOutputs.emplace_back(type, name);
    3838    } else {
    3939        mScalarOutputs.emplace_back(type, name);
     
    7878
    7979void PabloKernel::prepareKernel() {
    80     Type * carryDataType = mPabloCompiler->initializeKernelData();
    81     addScalar(carryDataType, "carries");
     80    mPabloCompiler->initializeKernelData();
    8281    KernelBuilder::prepareKernel();
    8382}
     
    8584void PabloKernel::generateDoBlockMethod() {
    8685    auto savePoint = iBuilder->saveIP();
    87     Module * m = iBuilder->getModule();
    88     Function * doBlockFunction = m->getFunction(mKernelName + doBlock_suffix);
    89     auto args = doBlockFunction->arg_begin();
    90     Value * const self = &*(args);
    91     mPabloCompiler->compile(self, doBlockFunction);
     86    Module * const m = iBuilder->getModule();
     87    Function * const f = m->getFunction(mKernelName + doBlock_suffix);
     88    Value * const self = &*(f->arg_begin());
     89    mPabloCompiler->compile(self, f);
    9290    Value * produced = getProducedItemCount(self);
    9391    produced = iBuilder->CreateAdd(produced, ConstantInt::get(iBuilder->getSizeTy(), iBuilder->getStride()));
     
    9593    iBuilder->CreateRetVoid();
    9694    #ifndef NDEBUG
    97     llvm::verifyFunction(*doBlockFunction, &errs());
     95    llvm::verifyFunction(*f, &errs());
    9896    #endif
    9997    iBuilder->restoreIP(savePoint);
     
    125123    iBuilder->CreateRetVoid();
    126124    #ifndef NDEBUG
    127     llvm::verifyFunction(*doBlockFunction, &errs());
     125    llvm::verifyFunction(*finalBlockFunction, &errs());
    128126    #endif
    129127    iBuilder->restoreIP(savePoint);
  • icGREP/icgrep-devel/icgrep/pablo/pablo_toolchain.cpp

    r5217 r5227  
    7777
    7878#ifdef PRINT_TIMING_INFORMATION
    79 unsigned COUNT_STATEMENTS(const PabloFunction * const entry) {
     79unsigned COUNT_STATEMENTS(const PabloKernel * const entry) {
    8080    std::stack<const Statement *> scope;
    8181    unsigned statements = 0;
     
    104104}
    105105
    106 unsigned COUNT_ADVANCES(const PabloFunction * const entry) {
     106unsigned COUNT_ADVANCES(const PabloKernel * const entry) {
    107107
    108108    std::stack<const Statement *> scope;
     
    137137using DistributionMap = boost::container::flat_map<unsigned, unsigned>;
    138138
    139 DistributionMap SUMMARIZE_VARIADIC_DISTRIBUTION(const PabloFunction * const entry) {
     139DistributionMap SUMMARIZE_VARIADIC_DISTRIBUTION(const PabloKernel * const entry) {
    140140    std::stack<const Statement *> scope;
    141141    DistributionMap distribution;
  • icGREP/icgrep-devel/icgrep/pablo/pe_advance.h

    r5217 r5227  
    2525    virtual ~Advance() {
    2626    }
    27     inline PabloAST * getExpr() const {
     27    inline PabloAST * getExpression() const {
    2828        return getOperand(0);
    2929    }
    3030    inline int64_t getAmount() const {
    3131        return cast<Integer>(getOperand(1))->value();
    32     }
    33     inline void setLocalIndex(const unsigned idx) {
    34         localAdvanceIndex = idx;
    35     }
    36     inline unsigned getLocalIndex() const {
    37         return localAdvanceIndex;
    3832    }
    3933protected:
     
    4337        assert(isa<Integer>(shiftAmount));
    4438    }
    45 private:
    46     unsigned localAdvanceIndex;
    4739};
    4840
  • icGREP/icgrep-devel/icgrep/pablo/pe_integer.h

    r5217 r5227  
    99    friend class SymbolGenerator;
    1010public:
    11 
     11    using IntTy = int64_t;
    1212
    1313    static inline bool classof(const PabloAST * e) {
     
    2020
    2121    }
    22     inline int64_t value() const {
     22    inline IntTy value() const {
    2323        return mValue;
    2424    }
    2525protected:
    26     Integer(const int64_t value, Type * type) noexcept
     26    Integer(const IntTy value, Type * type) noexcept
    2727    : PabloAST(ClassTypeId::Integer, type, nullptr)
    2828    , mValue(value)
     
    3131    }
    3232private:
    33     int64_t mValue;
     33    IntTy mValue;
    3434};
    3535
  • icGREP/icgrep-devel/icgrep/pablo/pe_lookahead.h

    r5217 r5227  
    3131        return cast<Integer>(getOperand(1))->value();
    3232    }
    33     inline void setLocalIndex(const unsigned idx) {
    34         localLookaheadIndex = idx;
    35     }
    36     inline unsigned getLocalIndex() const {
    37         return localLookaheadIndex;
    38     }
    3933protected:
    4034    Lookahead(PabloAST * expr, PabloAST * shiftAmount, const String * name)
     
    4337        assert(isa<Integer>(shiftAmount));
    4438    }
    45 private:
    46     unsigned localLookaheadIndex;
    4739};
    4840
  • icGREP/icgrep-devel/icgrep/pablo/pe_matchstar.h

    r5202 r5227  
    2727        return getOperand(1);
    2828    }
    29     inline void setLocalCarryIndex(const unsigned idx) {
    30         localCarryIndex = idx;
    31     }
    32     inline unsigned getLocalCarryIndex() const {
    33         return localCarryIndex;
    34     }
    3529    virtual ~MatchStar() {}
    3630protected:
     
    3933
    4034    }
    41 private:
    42     unsigned localCarryIndex;
    4335};
    4436
  • icGREP/icgrep-devel/icgrep/pablo/pe_scanthru.h

    r5202 r5227  
    2929        return getOperand(1);
    3030    }
    31     inline void setLocalCarryIndex(const unsigned idx) {
    32         localCarryIndex = idx;
    33     }
    34     inline unsigned getLocalCarryIndex() const {
    35         return localCarryIndex;
    36     }
    3731protected:
    3832    ScanThru(PabloAST * from, PabloAST * thru, const String * name)
     
    4034
    4135    }
    42 private:
    43     unsigned localCarryIndex;
    4436};
    4537
  • icGREP/icgrep-devel/icgrep/pablo/pe_var.h

    r5217 r5227  
    1616class Assign;
    1717
    18 // A Var is unique in that it is not a statement but a "lives" within a
    19 // scope and cannot be accessed outside of it. A Var is mutable (via an
    20 // Assign instruction.
    21 
    2218class Var : public PabloAST {
    2319    friend class PabloBlock;
     
    3228        return false;
    3329    }
     30    bool isReadOnly() const {
     31        return mReadOnly;
     32    }
     33    void setReadOnly(const bool value = true) {
     34        mReadOnly = value;
     35    }
    3436protected:
    35     Var(const PabloAST * name, Type * const type)
    36     : PabloAST(ClassTypeId::Var, type, cast<String>(name)) {
     37    Var(const PabloAST * name, Type * const type, const bool readOnly = false)
     38    : PabloAST(ClassTypeId::Var, type, cast<String>(name))
     39    , mReadOnly(readOnly) {
    3740
    3841    }
     42private:
     43    bool mReadOnly;
    3944};
    4045
  • icGREP/icgrep-devel/icgrep/pablo/printer_pablos.cpp

    r5217 r5227  
    8585        } else if (const Advance * adv = dyn_cast<Advance>(stmt)) {
    8686            out << " = pablo.Advance(";
    87             print(adv->getExpr(), out);
     87            print(adv->getExpression(), out);
    8888            out << ", " << std::to_string(adv->getAmount()) << ")";
    8989        } else if (const Lookahead * adv = dyn_cast<Lookahead>(stmt)) {
     
    140140        out << " = ";
    141141        print(assign->getValue(), out);
     142    } else if (const Add * op = dyn_cast<Add>(expr)) {
     143        print(op->getLH(), out);
     144        out << " + ";
     145        print(op->getRH(), out);
     146    } else if (const Subtract * op = dyn_cast<Subtract>(expr)) {
     147        print(op->getLH(), out);
     148        out << " - ";
     149        print(op->getRH(), out);
     150    } else if (const LessThan * op = dyn_cast<LessThan>(expr)) {
     151        print(op->getLH(), out);
     152        out << " < ";
     153        print(op->getRH(), out);
     154    } else if (const LessThanEquals * op = dyn_cast<LessThanEquals>(expr)) {
     155        print(op->getLH(), out);
     156        out << " <= ";
     157        print(op->getRH(), out);
     158    } else if (const Equals * op = dyn_cast<Equals>(expr)) {
     159        print(op->getLH(), out);
     160        out << " == ";
     161        print(op->getRH(), out);
     162    } else if (const GreaterThanEquals * op = dyn_cast<GreaterThanEquals>(expr)) {
     163        print(op->getLH(), out);
     164        out << " >= ";
     165        print(op->getRH(), out);
     166    } else if (const GreaterThan * op = dyn_cast<GreaterThan>(expr)) {
     167        print(op->getLH(), out);
     168        out << " > ";
     169        print(op->getRH(), out);
     170    } else if (const NotEquals * op = dyn_cast<NotEquals>(expr)) {
     171        print(op->getLH(), out);
     172        out << " != ";
     173        print(op->getRH(), out);
    142174    } else if (const Statement * stmt = dyn_cast<Statement>(expr)) {
    143175        out << stmt->getName();
  • icGREP/icgrep-devel/icgrep/re/re_compiler.h

    r5217 r5227  
    1212#include <cc/cc_compiler.h>
    1313#include <pablo/builder.hpp>
    14 
    15 namespace pablo {
    16 class PabloFunction;
    17 }
    1814
    1915namespace UCD {
  • icGREP/icgrep-devel/icgrep/u8u16.cpp

    r5224 r5227  
    3636#include <kernels/deletion.h>
    3737#include <kernels/stdout_kernel.h>
    38 #include <llvm/IR/TypeBuilder.h>
    39 
    4038
    4139// mmap system
     
    313311    Type * const int32ty = iBuilder->getInt32Ty();
    314312    Type * const int8PtrTy = iBuilder->getInt8PtrTy();
    315     Type * const voidPtrTy = TypeBuilder<void *, false>::get(mod->getContext());
     313    Type * const voidPtrTy = iBuilder->getVoidPtrTy();
    316314   
    317315    Function * const main = cast<Function>(mod->getOrInsertFunction("Main", voidTy, inputType, outputType, size_ty, nullptr));
  • icGREP/icgrep-devel/icgrep/wc.cpp

    r5221 r5227  
    135135}
    136136
    137 Function * wcPipeline(Module * mMod, IDISA::IDISA_Builder * iBuilder) {
     137Function * pipeline(Module * mMod, IDISA::IDISA_Builder * iBuilder) {
    138138    Type * mBitBlockType = iBuilder->getBitBlockType();
    139139   
     
    202202    IDISA::IDISA_Builder * idb = IDISA::GetIDISA_Builder(M);
    203203
    204     llvm::Function * main_IR = wcPipeline(M, idb);
     204    llvm::Function * main_IR = pipeline(M, idb);
    205205
    206206    wcEngine = JIT_to_ExecutionEngine(M);
     
    329329    return 0;
    330330}
    331 
    332                        
Note: See TracChangeset for help on using the changeset viewer.