haskell / hoopl Goto Github PK
View Code? Open in Web Editor NEWHigher-order optimization library
Home Page: http://hackage.haskell.org/package/hoopl
License: Other
Higher-order optimization library
Home Page: http://hackage.haskell.org/package/hoopl
License: Other
Currently hoopl.cabal
says:
Maintainer: [email protected], [email protected], [email protected]
I doubt Norman Ramsey does any maintenance work. I know Ning (@mlite) is an active maintainer. @AndreasVoellmy, are you still a maintainer? @michalt, what about you?
This ticket blocks #5.
Found on stackage nightly after re-enabling the test suite
Building test suite 'hoopl-test' for hoopl-3.10.2.2..
[1 of 1] Compiling Main ( testing/Main.hs, dist/build/hoopl-test/hoopl-test-tmp/Main.o )
testing/Main.hs:8:1: error:
Could not find module ‘Test’
Use -v to see a list of the files searched for.
|
8 | import qualified Test
| ^^^^^^^^^^^^^^^^^^^^^
Will add to expected test failures under compile fail tag.
Paper page 5
analyzeAndRewriteFwdBody
:: ( CkpointMonad m -- Roll back speculative actions
, NonLocal n ) -- Extract non-local flow edges
=> FwdPass m n f -- Lattice, transfer, rewrite
-> [Label] -- Entry point(s)
-> Graph n C C -- Input graph
-> FactBase f -- Input fact(s)
-> m ( Graph n C C -- Result graph
, FactBase f ) -- ... and its facts
Again same but single line
analyzeAndRewriteFwdBody :: ( CkpointMonad m, NonLocal n ) => FwdPass m n f -> [Label] -> Graph n C C -> FactBase f -> m (Graph n C C, FactBase f )
analyzeAndRewriteFwdBody :: forall m n f entries. (CheckpointMonad m, NonLocal n, LabelsPtr entries) => FwdPass m n f -> entries -> Body n -> FactBase f -> m (Body n, FactBase f)
[Label]
is type compatible with entries
. But Graph n C C
and Body
are not type compatible. It's not a problem with the code though, the test case also shows that the library works. The paper is mostly clear but it's just not exactly the same. Test case uses a different function
analyzeAndRewriteFwd :: forall m n f e x entries. (CheckpointMonad m, NonLocal n, LabelsPtr entries) => FwdPass m n f -> MaybeC e entries -> Graph n e x -> Fact e f -> m (Graph n e x, FactBase f, MaybeO x f)
I see the lib has been revised, but the test suite still declares a constraint of base < 4.10
Cabal file currently points to http://ghc.cs.tufts.edu/hoopl/ as the website of the library. But there is nothing really useful there - just a bunch of redirections. Can we offer a better link?
So, let's say I have an AliasInfo
fact type, and I have a number of different transfer functions doing different alias analyses. I don't think I can see how to interleave them. Can this be done, currently?
So, let's say I have a lattice which I know happens to be a Heyting algebra - that is, a lattice with an implication operator (every finite, distributive lattice is an example of a Heyting algebra; so are intuitionistic type theories).
There must be some way in which we can use these more advanced properties! For example, a simple constant propagation analysis might produce this fact at an if-then-else node: (b → x = 1) ∧ (!b → x = 5)
Now, this same fact might be able to be derived from interleaving in a dataflow analysis, but it would probably be much harder to automatically take advantage of more complicated facts.
Preprocessing test suite 'hoopl-test' for hoopl-3.10.2.2..
Building test suite 'hoopl-test' for hoopl-3.10.2.2..
[1 of 1] Compiling Main ( testing/Main.hs, dist/build/hoopl-test/hoopl-test-tmp/Main.o )
testing/Main.hs:8:1: error:
Could not find module ‘Test’
Use -v to see a list of the files searched for.
|
8 | import qualified Test
| ^^^^^^^^^^^^^^^^^^^^^
Maybe that file is missing from the release tarball on Hackage?
This ticket was filed by Andreas at https://ghc.haskell.org/trac/ghc/ticket/9853.
I can think of the following solutions:
Any other better solutions?
Repository currently stores things that should not be there:
src
directory stores some unused modules like Compiler.Hoopl.OldDataflow
(perhaps some other as well?).There are other files that might be good candidates for removal but need some more thinking before making such a decision:
mkfile
s - do we actually use them? If so, do they do anything that cannot be done using Cabal?When flattening the blocks to a final linear output order, postorder_dfs
seems useful. One of my exit nodes is a CondJump
, which has a destination and a fall-through label that is expected to be the next block in the flattened CFG.
This works most of the time, but there are cases where it fails. Consider the following sequence (an if-then-else) dispatching with a CondJump
:
CondJump L4 L6 conditional
L6: ..
Jump L3
L4: ..
Jump L3
L3:
There are two blocks L4
and L6
(the fall-through) which handles the true and false case of the if. This comes out as expected from postorder_dfs
.
However, when the conditional expressions contains &&
and ||
, I need to create a dispatch sequence, and it may be rewritten as:
CondJump L6 L9 conditional'
L9: CondJump L4 L6 conditional''
L6: ..
Jump L3
L4: ..
Jump L3
L3:
However, postorder_dfs
comes up with the following:
CondJump L6 L9 conditional'
L9: CondJump L4 L6 conditional''
L4: ..
Jump L3
L6: ..
Jump L3
L3:
The fall-through label from the second CondJump
does not follow immediately after!
The reason is that Hoopl has no idea about the concept of conditional jumps, postorder_dfs
sees the first CondJump
with [L6,L9]
and start to process L6
. This results in that the block acc gets L6
followed by blocks that comes after it, in this case L3
and whatever comes after that.
Now acc is [L6,L3,..]
, and then it looks at L9
with [L4,L6]
as children. It starts with L4
and add whatever comes after (nothing new in this case), so we end up with [L4,L6,L3,..]
, then it gets to L6
, but as it is already visited, so it is skipped.
Questions:
postorder_dfs
be able to handle this?Hello! Could you please upload the 3.10.2.2 release to Hackage.
Its absence is causing problems with downstream tools. My specific motivating example:
$ stack list-dependencies
Didn't see hoopl-3.10.2.2 in your package indices.
Updating and trying again.
Selected mirror https://s3.amazonaws.com/hackage.fpcomplete.com/
Downloading timestamp
No updates to your package list were found
Updating package index Hackage (mirrored at https://s3.amazonaws.com/hackage.fpcomplete.com/) ...The following package identifiers were not found in your indices: hoopl-3.10.2.2
Possible candidates: hoopl-3.10.0.0, hoopl-3.10.0.1, hoopl-3.10.0.2, hoopl-3.10.1.0, hoopl-3.10.2.0, hoopl-3.10.2.1.
Thanks!
hoopl tests are written using test-framework
, which has been abandoned and is not being developed. I suggest migrating tests to tasty
.
Imagine a pass which can use multiple types of facts - for example, a cache locality optimisation pass might want information about aliasing, branch selection frequency, and, optionally, the size of the code in a loop.
This might mean multiple types of fact, as well as the ability to OPTIONALLY use a fact type (i.e. if there is no provider of this type of fact, the pass is still valid, but probably not optimal).
It seems to me that the clearest way to handle this is with Effectful typing: each fact is represented with a separate effect type, and optional effects could be handled by a nondeterministic effect. Something like, e.g.:
myPassAnalysis :: (Member AliasFact r, Member BranchPredictionFact r, Member NonDetEff BlockSize r) => Eff r (Fact x f) -> n e x -> Fact x f
I have found myself using https://hackage.haskell.org/package/enummapset a lot in my code. It provides wrappers around IntSet
/IntMap
that uses Enum
rather than Int
, which allows for better type safety.
Now I am doing more work with Hoopl in my project and it lacks certain useful functions from IntMap
. I am looking at restrictKeys
at the moment. I am trying to wrap my head around how to implement it, but I also realize that in some way this collection code in Hoopl is just the same thing as is also provided by enummapset. I was thinking that maybe it would better to migrate the code in Hoopl to make use of enummapset rather than rolling its own duplicate that tends to be out of date (I have added some missing functions before).
I wonder what the maintainer and people using Hoopl think about this?
Per recent discussion Hoopl should be listed on Library submission Haskell Wiki page in category (3).
https://hackage.haskell.org/package/hoopl still mentions:
Bug tracker http://ghc.haskell.org/trac/ghc/newticket?component=libraries/hoopl
Please update it to point to https://github.com/haskell/hoopl/issues
Hi all,
When reading through the library I often find that inconsistent indentation and coding style is making things more difficult to read and understand. A few examples:
So I was wondering if we could simply agree to some already accepted coding style, e.g.,
https://github.com/tibbe/haskell-style-guide/blob/master/haskell-style.md
What do you think? (I'd be happy to send PRs to convert at least some of the code to the new style, e.g., Dataflow.hs which is non-trivial)
In line 274 of DataFlow, function arfx uses fromJust assuming that looking up a fact always produces a result. Would you please change the implementation into:
arfx arf thing fb =
case lookupFact (entryLabel thing) (joinInFacts lattice fb) of
Nothing -> error $
"Dataflow.hs: arfx => Clueless on label:"
++ (show . entryLabel) thing
Just x -> arf thing x
It was hard to spot where the error was raised. Including clues in the error message should help.
Regards
There should be a combinator to take an arbitrary list of passes, and interleave them into a single pass where the fact type is a type-level list of other fact types:
interleavePasses :: [forall f. FwdPass m n f] -> FwdPass m n '[]
This seems quite Effective (pun most certainly intended).
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.